1、第第4章章 二维图形的光栅显示二维图形的光栅显示4.1 计算机显示系统计算机显示系统4.2 扫描转换扫描转换 第1页，共47页。显示系统是由显示器（显示系统是由显示器（Monitor）和显示控制适配器）和显示控制适配器（Adapter,又称显示卡或图形卡）两部分组成。显示器的又称显示卡或图形卡）两部分组成。显示器的作用是将电信号转换为可以直接观察到的字符、图形或图作用是将电信号转换为可以直接观察到的字符、图形或图像，是像，是CAD中最为重要的人机交互设备。中最为重要的人机交互设备。4.1.1 CRT工作原理工作原理 以前采用阴极射线管以前采用阴极射线管CRT（Cathode Ray Tube）
2、技术）技术。但液晶显示但液晶显示LCD(Liquid Crystal Display)等技术设计的液等技术设计的液晶显示器已获得应用。晶显示器已获得应用。4.1 计算机显示系统计算机显示系统第2页，共47页。1.单色单色CRT它利用电场产生高速的聚焦电子束，偏转到屏幕表面的不它利用电场产生高速的聚焦电子束，偏转到屏幕表面的不同部位，以产生可见的图形。同部位，以产生可见的图形。主要组成部分：电子枪、聚焦系统、偏转系统和荧光屏。主要组成部分：电子枪、聚焦系统、偏转系统和荧光屏。CRT显示器简易结构图显示器简易结构图第3页，共47页。当电子束离开荧光点后，其亮度值随时间按指数规律衰当电子束离开荧光点
3、后，其亮度值随时间按指数规律衰减。余辉时间就是指光亮度衰减到初始减。余辉时间就是指光亮度衰减到初始1/10所需的时间。余所需的时间。余辉时间非常短暂，一般在辉时间非常短暂，一般在0.51ms之间。之间。计算机计算机CRT图形显示卡图形显示卡电子束产生的光点直径通常为电子束产生的光点直径通常为0.250.5mm。分辨率：一个分辨率：一个CRT在水平或垂直方向上能够识别出的最大光在水平或垂直方向上能够识别出的最大光 点数称为分辨率，如点数称为分辨率，如640480,1024768等。有时，等。有时，也把分辨率理解成所能识别的光点的最小距离。也把分辨率理解成所能识别的光点的最小距离。xyxy屏屏幕幕
4、第4页，共47页。2.彩色彩色CRTRGB颜色模型：颜色模型：RGB(0,0,0)black(1,0,1)magentablue(0,0,1)(1,1,1)white(1,1,0)yellow(0,1,0)greencyan(0,0,1)(1,0,0)redgray axisRGB颜色空间颜色空间颜色的加法过程：颜色的加法过程：从黑色开始，通过从黑色开始，通过增加适当的颜色分增加适当的颜色分量值产生所需要的量值产生所需要的颜色。这种过程与颜色。这种过程与显示器的工作原理显示器的工作原理极其相似。极其相似。颜色坐标（颜色坐标（r,g,b),它它既能表示颜色又能表既能表示颜色又能表示亮度。示亮度。
5、第5页，共47页。CRT屏幕内部涂有很多组呈三角形的荧光粉，每一组有三屏幕内部涂有很多组呈三角形的荧光粉，每一组有三个荧光点，当某组荧光粉被激励时，分别发出红、绿、蓝三个荧光点，当某组荧光粉被激励时，分别发出红、绿、蓝三个基色。个基色。荫罩式彩色荫罩式彩色CRT显色原理示意图显色原理示意图第6页，共47页。CRT的刷新频率是指每秒重画图像的次数。为了得到的刷新频率是指每秒重画图像的次数。为了得到稳定的画面，通常刷新频率应为稳定的画面，通常刷新频率应为3050帧帧/秒。秒。第7页，共47页。4.1.2 图形显示器的工作原理图形显示器的工作原理根据电子束的扫描方式，显示器分为随机扫描式显根据电子束
6、的扫描方式，显示器分为随机扫描式显示器和光栅扫描式显示器。示器和光栅扫描式显示器。随机扫描方式指屏幕上的图形是按矢量线段一笔一随机扫描方式指屏幕上的图形是按矢量线段一笔一笔画出的，其顺序完全按用户的绘图指令来决定。笔画出的，其顺序完全按用户的绘图指令来决定。对于光栅扫描方式，电子束按照从左到右，从上到对于光栅扫描方式，电子束按照从左到右，从上到下按固定节拍扫描，遇到图形时，相应的栅格发光，下按固定节拍扫描，遇到图形时，相应的栅格发光，由此显示图形或字符。由此显示图形或字符。第8页，共47页。基本工作过程：要显示的图形由计算机加工成显示器的基本工作过程：要显示的图形由计算机加工成显示器的显示指令
7、显示指令显示文件，存储在显示器的缓冲存储器中。显示文件，存储在显示器的缓冲存储器中。CPUSystem MemoryDisplayProcessorMonitorSystem BusI/O Devices随机扫描所绘制的图形只能是单线条图形。随机扫描所绘制的图形只能是单线条图形。绘制速度与图形的复杂程度有关。绘制速度与图形的复杂程度有关。1.随机扫描显示器随机扫描显示器简单随机扫描系统的体系结构简单随机扫描系统的体系结构第9页，共47页。2.光栅扫描显示器光栅扫描显示器光栅扫描显示器的工作原理是：光栅扫描显示器的工作原理是：首先，屏幕网格化。首先，屏幕网格化。xyxy屏屏幕幕mn个像素个像素其
8、次，图形光栅化。它其次，图形光栅化。它用帧缓存（用帧缓存（frame buffer）存储每个像素点的光亮存储每个像素点的光亮度值。度值。最后，光栅化的像素值由偏转及颜色系统，在最后，光栅化的像素值由偏转及颜色系统，在CRT屏幕显示。屏幕显示。第10页，共47页。特点：特点：帧缓存中存放的不是显示指令，而是对应每个像帧缓存中存放的不是显示指令，而是对应每个像素的亮度或色彩信息。素的亮度或色彩信息。可用于显示真实感的图形。可用于显示真实感的图形。光栅显示与原始图形的复杂程度无关。光栅显示与原始图形的复杂程度无关。屏幕上的每个像素都对应帧缓冲存储器的若干位。屏幕上的每个像素都对应帧缓冲存储器的若干位
9、。各种扫描转换算法已固化在硬件中。各种扫描转换算法已固化在硬件中。图形的近似表示。图形的近似表示。第11页，共47页。CPUSystem MemoryVideoControllerMonitorSystem BusI/O Devices简单的光栅扫描系统的体系结构简单的光栅扫描系统的体系结构帧缓存可以位于系统内存的任何地方。帧缓存可以位于系统内存的任何地方。显示控制器存取帧缓存刷新屏幕。显示控制器存取帧缓存刷新屏幕。第12页，共47页。Raster-Scan GeneratorX RegisterY RegisterMemory AddressFrame BufferPixel Registe
10、rIntensityBasic video-controller refresh operations第13页，共47页。CPUSystem MemoryVideoControllerMonitorSystem BusI/O DevicesFrameBuffer系统内存中一个固定区域作为帧缓存区使用。系统内存中一个固定区域作为帧缓存区使用。显示控制器直接存取帧缓存中的像素颜色值。显示控制器直接存取帧缓存中的像素颜色值。具有固定帧缓存的光栅扫描系统的体系结构具有固定帧缓存的光栅扫描系统的体系结构第14页，共47页。CPUVideoControllerMonitorSystem BusI/O De
11、vicesDisplayProcessor MemoryFrameBufferDisplayProcessorSystemMemory具有显示处理器的光栅扫描系统的体系结构具有显示处理器的光栅扫描系统的体系结构显示处理器的主要任务是进行扫描转换（显示处理器的主要任务是进行扫描转换（Scan-Conversion）第15页，共47页。4.1.3 图形显示卡图形显示卡 图形显示的核心部分是图形加速芯片。图形加速芯图形显示的核心部分是图形加速芯片。图形加速芯片是一个固化了一定数量最常用基本图形程序模块的集成片是一个固化了一定数量最常用基本图形程序模块的集成电路，它大大减轻了电路，它大大减轻了CPU的
12、负荷，加快了图形操作速度。的负荷，加快了图形操作速度。图形适配器从接口形式可分为图形适配器从接口形式可分为ISA,VESA,PCI和和AGP等。等。1.普通显示卡。如普通显示卡。如CGA、EGA、VGA、TVGA。这种卡。这种卡的图形处理完全由主机的图形处理完全由主机CPU完成，价格低廉。完成，价格低廉。第16页，共47页。PCI总线总线显示卡显示卡硬盘硬盘网卡网卡CPU处理器处理器系统内存系统内存传统传统PCI芯片卡芯片卡132MB/s528MB/s传统的传统的PCI总线结构总线结构2.有图形处理芯片的图形显示卡。基于有图形处理芯片的图形显示卡。基于PCI总线并集成总线并集成有图形处理芯片，
13、如有图形处理芯片，如 Intel 82786 和和 TMS 34020。显示卡主要用于解决输入输出总线速度远远慢于显示卡主要用于解决输入输出总线速度远远慢于CPU内部内部处理速度的问题。处理速度的问题。第17页，共47页。3.基于基于AGP的图形卡的图形卡与传统的显示卡相比，与传统的显示卡相比，AGP(Advanced Graphics Port)在在传输总线上有较大改进。它把主存与显存直接连接起来，传输总线上有较大改进。它把主存与显存直接连接起来，是新一代图形卡接口。是新一代图形卡接口。PCI总线总线硬盘硬盘网卡网卡声卡声卡显示卡显示卡系统内存系统内存AGP芯片卡芯片卡132MB/s528M
14、B/sCPU处理器处理器AGP总线结构总线结构第18页，共47页。显示卡一般都有显示缓存。根据不同的要求，显示缓存有显示卡一般都有显示缓存。根据不同的要求，显示缓存有2MB,4MB,8MB等配置。等配置。第19页，共47页。4.2 扫描转换扫描转换 4.2.1 扫描转换的必要性扫描转换的必要性计算机图形学中所研究的图形是从客观世界物体中抽象出来计算机图形学中所研究的图形是从客观世界物体中抽象出来的带灰度（或彩色）及形状的图或形。计算机中表示一个图的带灰度（或彩色）及形状的图或形。计算机中表示一个图形常用的方法有两种：形常用的方法有两种：（1）点阵法：是用具有灰度或色彩的点阵表示图形的一种）点阵
15、法：是用具有灰度或色彩的点阵表示图形的一种方法，它强调由哪些点组成，并具有什么灰度或色彩。方法，它强调由哪些点组成，并具有什么灰度或色彩。（2）参数法：）参数法：是以计算机中所记录的形状参数与属性参数是以计算机中所记录的形状参数与属性参数表示图形的一种方法。形状参数可以是描述其形状的方程的表示图形的一种方法。形状参数可以是描述其形状的方程的系数、线段的起点和终点等；属性参数则包括灰度、色彩、系数、线段的起点和终点等；属性参数则包括灰度、色彩、线型等非几何属性。线型等非几何属性。通常将参数法描述的图形称为参数图形，也称矢量图形。而通常将参数法描述的图形称为参数图形，也称矢量图形。而把点阵法描述的
16、图形叫做像素图形，简称图像。把点阵法描述的图形叫做像素图形，简称图像。第20页，共47页。光栅图形的表示方法是点阵式，它的主要特点是面着色，光栅图形的表示方法是点阵式，它的主要特点是面着色，即在指定的平面区域着上所需要的颜色。与单纯由线条所即在指定的平面区域着上所需要的颜色。与单纯由线条所构成的线划图形相比，采用面着色绘制的光栅图形显得更构成的线划图形相比，采用面着色绘制的光栅图形显得更为生动、直观，真实感更强。为生动、直观，真实感更强。一般地，复杂的图形是由基本的图形元素如点、线、圆及多一般地，复杂的图形是由基本的图形元素如点、线、圆及多边形构成的。这些图形元素通常是在连续的空间定义，而不边
17、形构成的。这些图形元素通常是在连续的空间定义，而不是由离散图像空间中的像素定义。是由离散图像空间中的像素定义。图形系统的任务之一就是将在连续空间中定义的几何元图形系统的任务之一就是将在连续空间中定义的几何元素转化为图像空间中的像素表示。这一转化任务称为扫素转化为图像空间中的像素表示。这一转化任务称为扫描转换或光栅化。描转换或光栅化。矢量图形矢量图形光栅图形光栅图形扫描转换扫描转换第21页，共47页。yx0101像素坐标像素坐标(0,0)扫描线扫描线y=0像素像素:方形区域方形区域用像素中心表示像素用像素中心表示像素像素、像素坐标、扫描线、屏幕坐标像素、像素坐标、扫描线、屏幕坐标yx0101屏幕
18、坐标屏幕坐标(0,0)扫描线扫描线y=0用像素网格的左下角表示像素用像素网格的左下角表示像素第22页，共47页。4.2.2 点的扫描转换点的扫描转换设设(x,y)是图像区域中的一点，其中是图像区域中的一点，其中x,y均为实数。均为实数。我们需要将它转换为图像空间中的一个像素我们需要将它转换为图像空间中的一个像素(x,y)。方法方法1：取：取x和和y分别为分别为x和和y的整数部分。的整数部分。第23页，共47页。PixelCoordinatesyxPixel Grid1.02.00.01.02.0012012P2P3P1P1(1.7,0.8)P2(2.2,1.3)P3(2.8,1.9)这种做法的
19、本质是将连续坐标系统的原点放在图像空间这种做法的本质是将连续坐标系统的原点放在图像空间的像素网格的左下角。的像素网格的左下角。第24页，共47页。方法方法2：采用四舍五入的方法。即：采用四舍五入的方法。即x和和y分别为分别为x+0.5及及y+0.5的的整数部分。整数部分。PixelCoordinatesyxPixel Grid1.02.00.01.02.0012012P2P3P1P1(1.7,0.8)P2(2.2,1.3)P3(2.8,1.9)33.0将连续空间中的整数值与图像空间中的像素坐标对齐。将连续空间中的整数值与图像空间中的像素坐标对齐。第25页，共47页。4.2.3 直线段的扫描转换
20、直线段的扫描转换 典型地，图形学中的一条线指一条线段，它由两个端典型地，图形学中的一条线指一条线段，它由两个端点及直线方程定义。点及直线方程定义。斜率斜率截距式方程不适合表示垂线，因此，水平、截距式方程不适合表示垂线，因此，水平、垂线、对角线线段需特殊处理。无需用下述扫描转换算垂线、对角线线段需特殊处理。无需用下述扫描转换算法。法。OP1(x1,y1)P2(x2,y2)y=mx+bxy第26页，共47页。1.直接应用直线方程直接应用直线方程 首先，将首先，将P1,P2扫描转换为像素坐标（扫描转换为像素坐标（x1,y1）和）和(x2,y2)。其次，设其次，设m=(y2-y1)/(x2-x1),b
21、=y1-mx1。若若|m|1,则对介于则对介于y1和和y2之间的每个整数值之间的每个整数值y，用直线方程计算出用直线方程计算出x值并扫描转换值并扫描转换(x,y)。缺点：因缺点：因m,b都是浮点数，因此这种方法的都是浮点数，因此这种方法的每步都要进行浮点数乘法与加法计算。每步都要进行浮点数乘法与加法计算。第27页，共47页。例例:对于对于|m|=1的直线段，应用斜率的直线段，应用斜率-截距式方程绘制该线截距式方程绘制该线段需要哪些步骤段需要哪些步骤?计算计算dx:dx=x2-x1;计算计算dy:dy=y2-y1;计算斜率计算斜率:m=dy/dx;计算截距计算截距b:b=y1-mx1;设设xen
22、d为为x1与与x2中的最大者，若中的最大者，若dx0,则则x=x1,y=y1,且且xend=x2；检查整条线段是否绘制完毕，如果检查整条线段是否绘制完毕，如果x xend,则停止运行；则停止运行；在当前在当前(x,y)坐标处画点；坐标处画点；增大增大x:x=x+1；根据方程根据方程y=mx+b计算下一个计算下一个y值；值；1.返回第返回第6步。步。第28页，共47页。2.DDA(Digital Differential Analyzer)算法算法 该算法是增量扫描转换方法。假设在第该算法是增量扫描转换方法。假设在第i步求步求出了直线上的点（出了直线上的点（xi,yi）。由于下一点）。由于下一点
23、 满足满足于是，于是，)11,(iiyxiixymxy1i1ixx ,yy ,/xmyyii1myxxii/1或或这些公式在这些公式在DDA算法中的应用如下：算法中的应用如下：当当|m|=1时，我们从时，我们从x=x1(假设假设x11的情况可做类似处理。的情况可做类似处理。1xmyyii1第29页，共47页。例例:用伪码描述用伪码描述DDA算法，假设直线段的斜率满足算法，假设直线段的斜率满足:|m|1。对于直线段的两个端点对于直线段的两个端点(x1,y1)和和(x2,y2)，假设，假设y1y2。int x,y=y1;float xf=x1,minv=(x2-x1)/(y2-y1);while(
24、y=y2)x=Floor(xf+0.5);/Floor(x)表示取表示取x的整数部分的整数部分 setPixel(x,y);/在像素在像素(x,y)处画点处画点 xf=xf+minv;y+;/即将即将y值增加值增加1 第30页，共47页。DDA算法效率的评述算法效率的评述:优点优点:较直接，用直线方程的方法速度更快。较直接，用直线方程的方法速度更快。缺点缺点:浮点数和取整运算仍然费时。浮点数和取整运算仍然费时。克服方法克服方法:将增量将增量m和和1/m分成整数和分数两部分，使所有计算归结分成整数和分数两部分，使所有计算归结为整数操作为整数操作(这里不再深入分析这种算法这里不再深入分析这种算法)
25、。第31页，共47页。3.Bresenhams直线算法直线算法 该算法是扫描转换线段的精确高效的增量算法。它该算法是扫描转换线段的精确高效的增量算法。它仅利用整数加法、减法及被仅利用整数加法、减法及被2乘的乘法就可以得到乘的乘法就可以得到数学上的精确结果。数学上的精确结果。这种方法可推广应用到圆和其他曲线的扫描转换。这种方法可推广应用到圆和其他曲线的扫描转换。第32页，共47页。假设假设0m1syxyiyi+1xixi+1True lineScan-converted pointsP1P2STts像素像素S:xi+1=xi+1,yi+1=yi像素像素T:xi+1=xi+1,yi+1=yi+1已
26、知已知:(xi,yi)确定确定(xi+1,yi+1)?y=mxi+1+bs=y-yi ,t=(yi+1)-y第33页，共47页。当当s-t=0,则选则选T,此时此时di+1=di+2(dy-dx)如果如果di0,则选则选S,此时此时di+1=di+2dy第34页，共47页。可以算出可以算出:d1=2dy-dx推导过程如下推导过程如下:由由di=2dyxi-2dx yi+C,其中其中C=2dy+dx(2b-1)得得d1=2dxmx1-2dxy1+2mdx+dx(2b-1)/注意注意:m=dy/dx=dx2m(x1+1)+2b-2y1-1=dx2(mx1+b-y1)+2m-1由于由于 mx1+b-
27、y1=0,所以所以d1=dx(2m-1)=2dy-dx 第35页，共47页。已知直线段：从已知直线段：从P1(x1,y1)到到P2(x2,y2),其中其中 x1x2,0m1则则Bresenhams直线扫描算法如下：直线扫描算法如下：int x=x1,y=y1;int dx=x2-x1,dy=y2-y1,dT=2(dy-dx),dS=2dy;int d=2dy-dx;setPixel(x,y);while(xx2)x+;if(d0)d=d+dS;第36页，共47页。elsey+;d=d+dT;setPixel(x,y);例：已知线段端点（例：已知线段端点（20,10)及（及（30,18）,斜率斜
28、率m=0.8，这时，这时，dx=10,dy=8,dT=-4,dS=16,d=6我们首先画初始点（我们首先画初始点（20，10），然后依），然后依次画点：次画点：第37页，共47页。4.2.4 多边形的扫描转换与区域填充多边形的扫描转换与区域填充一个区域是指一组相邻而又相连的像素，且具有一个区域是指一组相邻而又相连的像素，且具有同样的属性。同样的属性。区域可以由像素级定义，也可以由几何级定义。区域可以由像素级定义，也可以由几何级定义。在像素级，区域可以用内点表示和边界表示。在在像素级，区域可以用内点表示和边界表示。在几何级，区域可以由抽象的轮廓线定义，如相互几何级，区域可以由抽象的轮廓线定义，如
29、相互连接的线段和曲线。连接的线段和曲线。多边形区域多边形区域第38页，共47页。1.多边形的扫描转换多边形的扫描转换 在计算机图形学中，多边形有两种重要的表示方法：顶在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。点表示和点阵表示。顶点表示是用多边形的顶点的序列来刻画多边形。这种顶点表示是用多边形的顶点的序列来刻画多边形。这种方法直观、几何意义强。方法直观、几何意义强。点阵表示是用位于多边形内的像素的集合来刻画多边形。点阵表示是用位于多边形内的像素的集合来刻画多边形。该方法失去了许多重要的几何信息，但便于运用帧缓冲器表该方法失去了许多重要的几何信息，但便于运用帧缓冲器表示图形
30、。示图形。P0P1P2P3P4多边形的顶点表示多边形的顶点表示多边形的点阵表示多边形的点阵表示 第39页，共47页。多边形的扫描线填充算法：多边形的扫描线填充算法：xy 对每条穿过多边形的扫描线，对每条穿过多边形的扫描线，求出该扫描线与多边形边界求出该扫描线与多边形边界的交点，将这些交点按照从的交点，将这些交点按照从左到右进行排序，在每对交左到右进行排序，在每对交点之间相应的帧缓存位置设点之间相应的帧缓存位置设置指定的填充色。置指定的填充色。一些扫描线在多边形顶点处一些扫描线在多边形顶点处的交点需要特殊处理。的交点需要特殊处理。1211211处理方法：若该顶点不是处理方法：若该顶点不是局部极值
31、点，当扫描线与局部极值点，当扫描线与该点相交时，按一个交点该点相交时，按一个交点处理。处理。第40页，共47页。提高算法效率的基本方法：（提高算法效率的基本方法：（1）利用同一条扫描线上相）利用同一条扫描线上相邻像素的相关性；（邻像素的相关性；（2）利用同一条边两个相邻扫描线的）利用同一条边两个相邻扫描线的相关性。相关性。扫描线扫描线yk扫描线扫描线yk+1(xk,yk)(xk+1,yk+1)xk+1=xk+1/m=xk+dy/dx容易推出递推公式：容易推出递推公式：与多边形一条边相交的两条相邻的扫描线与多边形一条边相交的两条相邻的扫描线于是，于是，xk+1=x0+k/m第41页，共47页。2
32、.区域填充算法区域填充算法 这里所说的区域是指已经表示成点阵形式的像素的这里所说的区域是指已经表示成点阵形式的像素的集合。集合。区域填充是指先将区域内的一点区域填充是指先将区域内的一点(常称种子点常称种子点)赋予赋予给定颜色，然后将这种颜色扩展到整个区域的过程。这给定颜色，然后将这种颜色扩展到整个区域的过程。这种技术广泛应用于动画和美术画的计算机辅助制作中。种技术广泛应用于动画和美术画的计算机辅助制作中。区域的两种定义方法区域的两种定义方法:内点表示和边界表示。内点表示和边界表示。将给定区域内的所有像素表示成点阵形式的方法称将给定区域内的所有像素表示成点阵形式的方法称为内点表示法。在内点表示中
33、区域内的所有像素都着同为内点表示法。在内点表示中区域内的所有像素都着同一种颜色一种颜色(常称为原色常称为原色)，而区域的边界上的像素则不着，而区域的边界上的像素则不着这种颜色。这种颜色。以内点表示法为基础，将该区域中的全部像素都设以内点表示法为基础，将该区域中的全部像素都设置为新值的算法，称为漫水法置为新值的算法，称为漫水法(flood-fill algorithm)。第42页，共47页。将给定区域边界上的所有像素表示成点阵形式的方法将给定区域边界上的所有像素表示成点阵形式的方法称为边界表示法。在边界表示中，区域边界上的所有像素称为边界表示法。在边界表示中，区域边界上的所有像素都具有特定的颜色
34、或亮度值，而在区域内的像素则具有不都具有特定的颜色或亮度值，而在区域内的像素则具有不是新值的某种颜色或亮度值。是新值的某种颜色或亮度值。基于边界表示法，将该区域中的全部像素值都设置为基于边界表示法，将该区域中的全部像素值都设置为新值的算法称为边界填充算法新值的算法称为边界填充算法(boundary-fill algorithm)。第43页，共47页。简单的递归填充算法简单的递归填充算法 这类方法的基本思想是这类方法的基本思想是:首先，确定区域内的点首先，确定区域内的点(x,y)是否是老像素值，若是，将其改变成新像素值是否是老像素值，若是，将其改变成新像素值;其其次，若某点为新像素值，则用四连通
35、或八连通方法检次，若某点为新像素值，则用四连通或八连通方法检测该点相邻的像素值。这是一个递归调用过程。测该点相邻的像素值。这是一个递归调用过程。四连通、八连通搜索方法如图所示：四连通、八连通搜索方法如图所示：四个方向的运动四个方向的运动八个方向的运动八个方向的运动第44页，共47页。在区域填充算法中，要求区域具备一定的连通性：在区域填充算法中，要求区域具备一定的连通性：四连通或八连通。四连通或八连通。取区域内任意两点，在该区域内若从一点出发通过取区域内任意两点，在该区域内若从一点出发通过上、下、左、右四种运动到达另一点时，则称该区域为上、下、左、右四种运动到达另一点时，则称该区域为四连通的。四
36、连通的。若取区域内任意两点，在该区域内通过沿水平方向、若取区域内任意两点，在该区域内通过沿水平方向、垂直方向和对角线方向的八种运动到达另一点时，则称垂直方向和对角线方向的八种运动到达另一点时，则称该区域为八连通的。该区域为八连通的。第45页，共47页。3.多边形的扫描转换与区域填充的比较多边形的扫描转换与区域填充的比较联系：联系：是两类典型的面着色问题，具有密切的联系。是两类典型的面着色问题，具有密切的联系。如在一定条件下，多边形的扫描问题与区域填充问如在一定条件下，多边形的扫描问题与区域填充问题可互相转化。题可互相转化。差别：差别：（1）基本思想不同。基本思想不同。（2）对边界的要求不同。对边界的要求不同。（3）出发点不同。出发点不同。结论：不能互相取代。结论：不能互相取代。第46页，共47页。回顾二维图形输出流水线回顾二维图形输出流水线从应用程序得到图形的用户坐标对窗口区进行裁剪窗口区到视图区的规格化变换视图区从规格化坐标系到设备坐标系的变换在图形设备上输出图形二维变换二维变换 二维裁剪二维裁剪规范化变换规范化变换/窗口窗口-视区变换视区变换工作站变换工作站变换观察变换观察变换图形显示图形显示结束语：结束语：第47页，共47页。
