《【教学课件】第4章二维填充图元的生成.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第4章二维填充图元的生成.ppt（78页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计通学院计通学院 计算机科学系计算机科学系计算机图形学计算机图形学第第4章章 二维填充图元的生成二维填充图元的生成1本章目标l掌握如何绘制填充图元（矩形、多边形等）掌握如何绘制填充图元（矩形、多边形等）n扫面转换算法（扫描线算法）扫面转换算法（扫描线算法）n填充算法填充算法l学会使用学会使用OpenGL的绘制函数的绘制函数2主要内容l填充图元填充图元l扫描转换矩形扫描转换矩形l扫描转换多边形扫描转换多边形l扫描转换扇形区域扫描转换扇形区域l区域填充区域填充l以图像填充区域以图像填充区域l字符的表示与输出字符的表示与输出lOpenGL相关函数相关函数34.1 填充图元l填充（填充（Filling
2、）n矩形矩形(Rectangle)n多边形多边形(Polygon)n扇形扇形(Ellipse Arc)l步骤步骤n确定那些像素位于填充图元的内部确定那些像素位于填充图元的内部n用指定颜色绘制这些像素用指定颜色绘制这些像素l两类方法两类方法n扫描转换（扫描转换（Scan Converting）:参数参数点阵点阵n填充（填充（Filling）:点阵点阵点阵点阵44.2 扫描转换矩形l含义含义n用指定颜色填充矩形内部区域用指定颜色填充矩形内部区域l定义矩形的参数定义矩形的参数n左下角坐标左下角坐标(xmin,ymin)n右上角坐标右上角坐标(xmax,ymax)void FillRectangle(
3、Rectangle*rect,int color)int x,y;for(y=rect-ymin;y ymax;y+)for(x=rect-xmin;x xmax;x+)SetPixel(x,y,color);/*end of FillRectangle()*/(xmin,ymin)(xmax,ymax)54.2 扫描转换矩形l问题问题n矩形是简单的多边形，那么为什么要单独处理矩形？矩形是简单的多边形，那么为什么要单独处理矩形？u比一般多边形可简化计算比一般多边形可简化计算u应用非常多，如窗口系统应用非常多，如窗口系统n共享边界如何处理？共享边界如何处理？u原则：左闭右开，下闭上开原则：左闭右
4、开，下闭上开属于谁？属于谁？64.3 扫描转换多边形l多边形的表示方法多边形的表示方法n顶点表示顶点表示顶点序列顶点序列P0P1P2Pnn点阵表示点阵表示n扫描转换多边形：将顶点表示形式转换成点阵表示形式扫描转换多边形：将顶点表示形式转换成点阵表示形式n三种方法：三种方法：逐点判断法；扫描线算法；边缘填充法l多边形分类（只考虑：简单多边形，即多边形边不自相交）多边形分类（只考虑：简单多边形，即多边形边不自相交）n凸多边形凸多边形(convex)：内角小于：内角小于180度度n凹多边形凹多边形(concave)：存在内角大于：存在内角大于180度度74.3 扫描转换多边形 如何识别多边形的凸凹性
5、如何识别多边形的凸凹性方法方法1：观察多边形边的延长线是否划分顶点在两侧：观察多边形边的延长线是否划分顶点在两侧方法方法2：向量的叉积：向量的叉积每条边建立一个向量，测试相邻边的叉积每条边建立一个向量，测试相邻边的叉积z坐标的正负坐标的正负（1）如果叉积同号，那么是凸多边形）如果叉积同号，那么是凸多边形（2）如果叉积不同号，那么是凹多边形）如果叉积不同号，那么是凹多边形(E1E2)z 0(E2E3)z 0(E3E4)z 0(E5E6)z 0(E6E1)z 084.3 扫描转换多边形向量叉积（向量叉积（Cross Product of Two Vector）当当a与与b为二维向量时，为二维向量时
6、，ab 矢量中矢量中x，y 分量为分量为0 094.3.1 逐点判断法l基本原理基本原理n判断绘图窗口内的像素是否位于多边形内，若是，则用判断绘图窗口内的像素是否位于多边形内，若是，则用指定颜色绘制该像素指定颜色绘制该像素l问题问题n如何判断点在多边形的内外关系？如何判断点在多边形的内外关系？u射线法射线法u累计角度法累计角度法*u编码法编码法*P1P2(xmin,ymin)(xmax,ymax)104.3.1 逐点判断法l算法算法n假设判断点是否在多边形内的函数为假设判断点是否在多边形内的函数为IsInside（）（）void FillPolygon(Polygon*P,int polygo
7、nColor)int x,y;for(y=ymin;y=ymax;y+)for(x=xmin;x=xmax;x+)if(IsInside(P,x,y)SetPixel(x,y,polygonColor);else SetPixel(x,y,backgroundColor);/*end of FillPolygonPbyP()*/#define MAX 100typedef struct /多边形顶点个数多边形顶点个数 int PolygonNum;/多边形顶点数组多边形顶点数组 Point vertexcesMAX Polygon;/多边形结构多边形结构114.3.1 逐点判断法l判断点是否在
8、多边形内判断点是否在多边形内射线法射线法 步骤步骤n从待判别点从待判别点 v 发出射线发出射线n求与多边形交点个数求与多边形交点个数 knk 的奇偶性决定了点与多边形的内外关系的奇偶性决定了点与多边形的内外关系u偶数：外偶数：外u奇数：内奇数：内v1p2p1p3v2124.3.1 逐点判断法l判断点是否在多边形内判断点是否在多边形内射线法射线法 奇异情况奇异情况n射线在边上：无数个点射线在边上：无数个点 判断是否与边同线判断是否与边同线n交点为顶点：算几个？交点为顶点：算几个？u异侧：异侧：1个个u同侧：同侧：2个个134.3.1 逐点判断法l逐点判断扫描转换方法逐点判断扫描转换方法n特点特点
9、u程序简单程序简单u测试点是否在多边形内的算法速度太慢，效率低测试点是否在多边形内的算法速度太慢，效率低n改进改进u逐点判断法孤立考虑各个像素与多边形的内外关系逐点判断法孤立考虑各个像素与多边形的内外关系u利用内部点的连续性利用内部点的连续性144.3.1 逐点判断法l思考题思考题 下图是某油田油井分布图，已知每口油井的位置（下图是某油田油井分布图，已知每口油井的位置（x,y坐坐标值）和产油量，如何求任意多边形（虚线所示）中的标值）和产油量，如何求任意多边形（虚线所示）中的总产油量？总产油量？利用射线法判断油井利用射线法判断油井是否在多边形内？是否在多边形内？154.3.2 扫描线算法l英文：
10、英文：Scan-Line Algorithml目标目标n利用相邻像素之间的连贯性，提高算法效率利用相邻像素之间的连贯性，提高算法效率l处理对象：简单多边形处理对象：简单多边形n非自交多边形非自交多边形（边与边之间除了顶点外无其它交点）（边与边之间除了顶点外无其它交点）l扫描线扫描线(Scanning Line)n平行于坐标轴的直线平行于坐标轴的直线n一般取平行于一般取平行于X轴轴n区间：扫描线与边的交点间的线段区间：扫描线与边的交点间的线段164.3.2 扫描线算法l连贯性连贯性(Coherence)n边的连贯性边的连贯性(Edge Coherence)u某条边与当前扫描线相交，也可能与下一条
11、扫描线相交某条边与当前扫描线相交，也可能与下一条扫描线相交n扫描线的连贯性扫描线的连贯性(Scan-line Coherence)u当前扫描线与各边的交点顺序与当前扫描线与各边的交点顺序与 下一条扫描线与各边的交下一条扫描线与各边的交点顺序可能相同或类似点顺序可能相同或类似n区间的连贯性区间的连贯性(Span Coherence)u同一区间上的像素取同一颜色属性同一区间上的像素取同一颜色属性174.3.2 扫描线算法l基本原理基本原理n将整个绘图窗口内扫描多边形的问题分解到一条条扫描将整个绘图窗口内扫描多边形的问题分解到一条条扫描线，只要完成每条扫描线的绘制就实现了多边形的扫描线，只要完成每条
12、扫描线的绘制就实现了多边形的扫描转换转换n一条扫描线与多边形的边有偶数个交点，每一条扫描线与多边形的边有偶数个交点，每2个点形成一个点形成一区间区间l步骤步骤(对于每一条扫描线对于每一条扫描线)(1)计算扫描线与边的交点计算扫描线与边的交点(2)交点按交点按x坐标从小到大排序坐标从小到大排序(3)交点两两配对，填充区间交点两两配对，填充区间184.3.2 扫描线算法l计算交点计算交点n分类分类u第一类交点：位于同一条边上的后继交点第一类交点：位于同一条边上的后继交点-(P2,P4)u第二类交点：新出现的边与扫描线的交点第二类交点：新出现的边与扫描线的交点-(P3)n计算：由扫描线计算：由扫描线
13、ye与多边形的交点递推计算扫描线与多边形的交点递推计算扫描线 ye1的交点的交点u第一类交点：第一类交点：xx1/mu第二类交点：第二类交点：线段的下端点即为交点线段的下端点即为交点P3P4P0P2P1194.3.2 扫描线算法l计算交点（续）计算交点（续）n交点取整规则：交点取整规则：u要求：使生成的像素全部位于多边形之内要求：使生成的像素全部位于多边形之内u用于线画图元扫描转换的四舍五入原则导致部分像素位于用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用多边形之外，从而不可用扫描转换扫描转换位于多边形内位于多边形内204.3.2 扫描线算法n取整规则取整规则假定非水
14、平变与扫描线假定非水平变与扫描线 y=e y=e 相交，交点的横坐标为相交，交点的横坐标为x x规则规则1 X为小数，即交点落于扫描线上两个相邻像素之间为小数，即交点落于扫描线上两个相邻像素之间 (a)交点位于左边之上，向右取整交点位于左边之上，向右取整 (b)交点位于右边之上，向左取整交点位于右边之上，向左取整214.3.2 扫描线算法规则规则2落在右上边界的像素不予填充。落在右上边界的像素不予填充。具体实现时，只要对扫描线与多边形的相交区间左闭具体实现时，只要对扫描线与多边形的相交区间左闭右开右开224.3.2 扫描线算法规则规则3 扫描线与多边形的顶点相交时，采用上开下闭及右开左闭扫描线
15、与多边形的顶点相交时，采用上开下闭及右开左闭取交点，保证交点正确配对。取交点，保证交点正确配对。检查两相邻边在扫描线的哪一侧。检查两相邻边在扫描线的哪一侧。只要检查顶点的两条边的另外两个端点的只要检查顶点的两条边的另外两个端点的Y值，两个值，两个Y值值中大于交点中大于交点Y值的个数是值的个数是0，1，2，来决定取，来决定取0，1，2个交点个交点234.3.2 扫描线算法l计算交点（续）计算交点（续）n水平边水平边u不考虑不考虑l排序排序n扫描线连贯性扫描线连贯性n采用插入排序采用插入排序l交点两两配对与区间绘制交点两两配对与区间绘制n区间连续性区间连续性n连续绘制区间上的像素连续绘制区间上的像
16、素HFABCDGJA，B算交点算交点C不算不算，D算算I不算不算，H算算G，F不算不算Y244.3.2 扫描线算法l算法实现算法实现数据结构数据结构（1）边的分类表）边的分类表ET（Edge Table）（又称新边表）（又称新边表）u按照边的下端点按照边的下端点 y 坐标，对非水平边进行分类的链表坐标，对非水平边进行分类的链表u下端点下端点 y 坐标值等于坐标值等于i 的边属于第的边属于第i类类u作用：避免盲目求交作用：避免盲目求交254.3.2 扫描线算法 ET定义定义u每条扫描线，对应一个链表每条扫描线，对应一个链表u链表中每个结点的结构链表中每个结点的结构typedef struct i
17、nt ymax;float x,deltax;Edge*nextEdge;Edge;ET的结点信息：的结点信息：ymax:边的上端点的边的上端点的y坐标值坐标值x：边的下端点的边的下端点的 x 坐标坐标deltax：边的斜率的倒数边的斜率的倒数nextEdge:下一条边的指针下一条边的指针264.3.2 扫描线算法结点结构解释结点结构解释typedef struct int ymax;float x,deltax;Edge*nextEdge;Edge;float x,deltax;用于递推计算交点用于递推计算交点 xx1/mint ymax；当扫描线当扫描线 y=e+1=ymax，说明下说明下
18、一条扫描线与此边不相交一条扫描线与此边不相交274.3.2 扫描线算法（2）活性边表）活性边表AEL(Active Edge List)存放活性边的顺序链表，且按交点存放活性边的顺序链表，且按交点 x 的值从小到大排序的值从小到大排序 活性边：与当前扫描线相交的边活性边：与当前扫描线相交的边 边结构定义：边结构定义：typedef struct int ymax;float x,deltax;Edge*nextEdge;Edge;AEL 的结点信息的结点信息：lymax:所交边的最高扫描线号所交边的最高扫描线号lx：当前扫描线与边的交点的当前扫描线与边的交点的x坐标坐标ldeltax：边的斜率
19、的倒数边的斜率的倒数lnextEdge:下一条边的指针下一条边的指针284.3.2 扫描线算法l实例实例(a)Y=6对应的活性边表对应的活性边表(b)Y=7对应的活性边表对应的活性边表294.3.2 扫描线算法l算法算法(Scan-Line Algorithm)1、建立、建立ET；2、将扫描线纵坐标、将扫描线纵坐标y的初值置为的初值置为ET中非空中非空 元素的最小序号，如图中，元素的最小序号，如图中，y=1；3、置、置AEL为空；为空；4、执行下列步骤直至、执行下列步骤直至ET和和AEL都为空都为空4.1、如、如ET中的第中的第y类非空，则将其中的所有类非空，则将其中的所有 边取出并插入边取出
20、并插入AEL中；中；4.2、如果有新边插入、如果有新边插入AEL，则对，则对AEL中各边排序；中各边排序；4.3、对、对AEL中的边两两配对，（中的边两两配对，（1和和2为一对，为一对，3和和4为一对，为一对，），），将每对边中将每对边中x坐标按规则取整，获得有效的填充区段，再填充坐标按规则取整，获得有效的填充区段，再填充4.4、将当前扫描线纵坐标、将当前扫描线纵坐标 y 值递值值递值1；4.5、将、将AEL中满足中满足y=ymax边删去（因为每条边被看作下闭上开的）边删去（因为每条边被看作下闭上开的）；4.6、对、对AEL中剩下的每一条边的中剩下的每一条边的x递增递增deltax，即，即x=
21、x+deltax304.3.2 扫描线算法4.3.2 扫描线算法l例子例子 y=5 y=6 y=7 y=8AET:y=1 y=2 y=3 y=44 4 -15 7 5/4 4 5 -15 33/4 5/4 5 19/2 5/4 4 3 -18 2 05 43/4 5/4 8 2 08 2 08 2 011 12 0 11 12 0 8 7 -511 7 5/411 12 0 11 33/4 5/411 12 0 314.3.2 扫描线算法l思考问题思考问题n算法如何体现连贯性？算法如何体现连贯性？n对凸多边形而言，算法是否可以简化？如何简化？对凸多边形而言，算法是否可以简化？如何简化？n对三角
22、形而言，算法如何简化？对三角形而言，算法如何简化？三角形广泛应用于物体建模三角形广泛应用于物体建模32思考题l思考问题思考问题 如何高效计算平面上如何高效计算平面上 n 条线段的交点？条线段的交点？利用扫描线和边的连贯性，时间复杂性利用扫描线和边的连贯性，时间复杂性mn （m为扫描线条数为扫描线条数,n为与扫描线相交边的平均条数，为与扫描线相交边的平均条数，n n）一般方法：两两求交点，时间复杂性一般方法：两两求交点，时间复杂性 n2334.3.3 边缘填充算法*l写像素的逻辑操作写像素的逻辑操作n主要包括：拷贝、异或（求余）等主要包括：拷贝、异或（求余）等n写模型：像素的颜色与源像素及像素当
23、前颜色相关写模型：像素的颜色与源像素及像素当前颜色相关344.3.3 边缘填充算法*l求余运算求余运算n假定假定A为一个正整数，则为一个正整数，则 M 的余定义为的余定义为 A M,记为记为 n求余运算可用异或逻辑运算实现求余运算可用异或逻辑运算实现n例例n性质性质354.3.3 边缘填充算法*l求余运算（续）求余运算（续）n应用：光标移动、橡皮筋线和加亮菜单等操作应用：光标移动、橡皮筋线和加亮菜单等操作n如：交互绘制线段时的橡皮筋线如：交互绘制线段时的橡皮筋线交互方式：交互方式：（1 1）点击鼠标左键输入线段的一个端点）点击鼠标左键输入线段的一个端点（2 2）点击右键（或左键）输入另一端点）
24、点击右键（或左键）输入另一端点（3 3）鼠标移动过程中绘制瞬时线段）鼠标移动过程中绘制瞬时线段注意：不能采用直接绘制注意：不能采用直接绘制（复制、拷贝）方法（复制、拷贝）方法364.3.3 边缘填充算法*l边缘填充算法边缘填充算法n光栅图形中，如果某区域已着上值为光栅图形中，如果某区域已着上值为M的颜色值后，做的颜色值后，做偶数次求余运算，该区域颜色不变；而做奇数次求余偶数次求余运算，该区域颜色不变；而做奇数次求余运算，则该区域颜色变为值为运算，则该区域颜色变为值为 的颜色的颜色n这一规律应用于多边形扫描转换，称为边缘填充算法。这一规律应用于多边形扫描转换，称为边缘填充算法。l算法基本思想算法
25、基本思想n对于每条扫描线和每条多边形边的交点，将该扫描线对于每条扫描线和每条多边形边的交点，将该扫描线上交点右方的所有像素取余上交点右方的所有像素取余nM为填充色，为填充色，A为当前背景色为当前背景色374.3.3 边缘填充算法*l算法算法1（以扫描线为中心的边缘填充算法）（以扫描线为中心的边缘填充算法）n1、将当前扫描线上的所有像素着上值为、将当前扫描线上的所有像素着上值为 颜色；颜色；n2、求余：、求余：for(i=0;i=m;i+)在当前扫描线上，从横坐标为在当前扫描线上，从横坐标为xi的交点向右求余；的交点向右求余；图中次序图中次序：x0,x1,x2,x3次序可以任意次序可以任意384
26、.3.3 边缘填充算法*l算法算法2（以边为中心的边缘填充算法）（以边为中心的边缘填充算法）1 1、将绘图窗口的背景色置为、将绘图窗口的背景色置为 ；2 2、对多边形的每一条非水平边做：、对多边形的每一条非水平边做：从该边上的每个像素开始向右求余从该边上的每个像素开始向右求余39l特点特点n适合用于具有帧缓存的图形系统。处理后，按扫描线顺适合用于具有帧缓存的图形系统。处理后，按扫描线顺序读出帧缓存的内容，送入显示设备序读出帧缓存的内容，送入显示设备n优点：算法简单优点：算法简单n缺点：对于复杂图形，每一像素可能被访问多次，输入缺点：对于复杂图形，每一像素可能被访问多次，输入/输出的量比扫描线算
27、法大得多输出的量比扫描线算法大得多4.3.3 边缘填充算法*40l扇形区域的描述扇形区域的描述n圆的半径圆的半径Rn起始角度：起始角度：1n终止角度：终止角度：2l原理：同扫描转换多边形原理：同扫描转换多边形n对每条扫描线，首先计算与扇形区域边界的交点，再用对每条扫描线，首先计算与扇形区域边界的交点，再用指定颜色绘制绘制配对交点间的像素指定颜色绘制绘制配对交点间的像素l问题问题n如何确定扫描线与直线段和圆弧段的交点及相交顺序？如何确定扫描线与直线段和圆弧段的交点及相交顺序？4.4 扫描转换扇形区域41l方法：分类方法：分类n按点按点 P1(x,y)和和P2(x,y)点所处象限的不同，需要将扇形
28、点所处象限的不同，需要将扇形区域分成区域分成44=16种情况种情况 n假设假设 P1 点落在第一象限点落在第一象限 u扫描线和区域边界只有扫描线和区域边界只有2个交点个交点u扇形区域的扫描转换分四种情况扇形区域的扫描转换分四种情况(1)P2落在第一象限落在第一象限区域：区域：OP1A和和AP1P24.4 扫描转换扇形区域42(2)P2落在第二象限，此时又分为两种情况落在第二象限，此时又分为两种情况 n当当 时时u三个区域：三个区域：OAP1、AP1BP2和和P2BCn当当 时时u三个区域：三个区域：OAP2、AP1BP2和和P1BC4.4 扫描转换扇形区域43(3)P2 落在第三象限落在第三象
29、限u三个区域：三个区域：P1CA、BOP1A和和P2OB(4)P2落在第四象限落在第四象限u三个区域：三个区域：AP1D、BOP1 A、CP2OB和和CEP24.4 扫描转换扇形区域44l遗留问题：当遗留问题：当 P1 落在其它区域时落在其它区域时?nP1 落在第二、三、四象限时，将扇形区域绕坐标原点顺落在第二、三、四象限时，将扇形区域绕坐标原点顺时针旋转时针旋转90度（度（180，270），使），使 P1 落在第落在第1象限象限n扫描转换扫描转换n再逆时针旋转再逆时针旋转90度（度（180，270）4.4 扫描转换扇形区域P1P2P2P1P1落在第四象限落在第四象限P2P1P1落在第一象限落
30、在第一象限P1P2P1落在第四象限落在第四象限旋转旋转270度度扫描转换扫描转换逆旋转逆旋转270度度45l区域：点阵表示的图形，像素集合区域：点阵表示的图形，像素集合l表示方法：内点表示、边界表示表示方法：内点表示、边界表示l内点表示内点表示n枚举出区域内部的所有像素枚举出区域内部的所有像素n内部的所有像素为同一个颜色内部的所有像素为同一个颜色n边界像素与内部像素的颜色不同边界像素与内部像素的颜色不同l边界表示边界表示n枚举出边界上所有的像素枚举出边界上所有的像素n边界上的所有像素为同一颜色边界上的所有像素为同一颜色n内部像素与边界像素的颜色不同内部像素与边界像素的颜色不同4.5 区域填充4
31、6l种子填充法种子填充法n对区域重新着色的过程对区域重新着色的过程 将指定的颜色从将指定的颜色从种子点种子点开始扩展到整个区域开始扩展到整个区域n区域填充算法要求区域是连通的区域填充算法要求区域是连通的4.5 区域填充47l连通性连通性n4连通区域：区域中任意两点连通区域：区域中任意两点可通过上下左右四个方向互相可通过上下左右四个方向互相 到达到达n8连通区域：区域中任意两点连通区域：区域中任意两点可通过上下左右和对角线八可通过上下左右和对角线八 个方向互相到达个方向互相到达4.5 区域填充484.5 区域填充4连通与连通与8连通区域的区别连通区域的区别n连通性：连通性：4连通可看作连通可看作
32、8连通区域，但对边界有要求不同连通区域，但对边界有要求不同n依据区域内点能否访问到区域外的点，对边界的要求是依据区域内点能否访问到区域外的点，对边界的要求是u4连通区域，边界只要连通区域，边界只要8连通即可连通即可u8连通区域，边界必须是连通区域，边界必须是4连通连通n例：如左图例：如左图（1）4连通区域，边界为连通区域，边界为 像素像素（2）8连通区域，边界为连通区域，边界为 和和 像素像素494.5.1 种子填充法l种子填充算法（泛滥填充：种子填充算法（泛滥填充：flood-fill）（1）内点表示的）内点表示的4连通区域连通区域n种子种子P(x,y)，原色，原色oldColor，新颜色，
33、新颜色newColor方法：先判断方法：先判断P(x,y)的颜色，若其值不等于的颜色，若其值不等于oldColor，说明该像，说明该像素位于区域外，或已设置为素位于区域外，或已设置为newColor，算法结束；，算法结束；否则，置像素颜色否则，置像素颜色为为newColor，再对，再对其相邻的上下左右四其相邻的上下左右四个像素分别作为种子个像素分别作为种子作上述递归处理。作上述递归处理。void FloodFill4(int x,int y,int oldColor,int newColor)if(GetPixel(x,y)=oldColor)SetPixel(x,y,newColor);Fl
34、oodFill4(x,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1,y,oldColor,newColor);/*end of FloodFill4()*/504.5.1 种子填充法FloodFill4(x,y+1,oldColor,newColor);FloodFill4(x,y-1,oldColor,newColor);FloodFill4(x-1,y,oldColor,newColor);FloodFill4(x+1
35、,y,oldColor,newColor);51（2）边界表示的）边界表示的4连通区域连通区域4.5.1 种子填充法void BoundaryFill4(int x,int y,int oldColor,int newColor)/oldColor边界像素颜色边界像素颜色 int color;color=GetPixel(x,y);if(color!=oldColor)&(color!=newColor)SetPixel(x,y,newColor);BoundaryFill4(x,y+1,oldColor,newColor);BoundaryFill4(x,y-1,oldColor,newCo
36、lor);BoundaryFill4(x-1,y,oldColor,newColor);BoundaryFill4(x+1,y,oldColor,newColor);/*end of BoundaryFill4()*/52l缺点缺点n有些像素需要重复判断，降低算法效率有些像素需要重复判断，降低算法效率n栈结构占空间栈结构占空间n递归执行，算法简单，但效率不高，区域内每一像素都递归执行，算法简单，但效率不高，区域内每一像素都引起一次递归，进引起一次递归，进/出栈，费时费内存出栈，费时费内存l改进改进n减少递归次数，提高效率减少递归次数，提高效率n方法之一使用扫描线填充算法方法之一使用扫描线填充算
37、法4.5.1 种子填充法53 扫描线算法*l扫描线算法扫描线算法n目标：减少递归层次目标：减少递归层次n适用于内点表示的适用于内点表示的4连通区域连通区域n基本过程：基本过程：当给定种子点时，首先填充种子点所在的扫当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段，然后确描线上的位于给定区域的一个区段，然后确定与这一区段相通的上下两条扫描线上位于定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。反复给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束这个过程，直到填充结束54 扫描线算法*l算法步骤算法步骤n1、初始化、初始化：将种子区段压入堆栈
38、：将种子区段压入堆栈n2、出栈：如果堆栈为空，则算法结束；、出栈：如果堆栈为空，则算法结束；u否则取栈顶元素否则取栈顶元素(x,y)作为种子点作为种子点n3、区段填充：从种子点、区段填充：从种子点(x,y)开始沿纵坐标为开始沿纵坐标为y的扫描行的扫描行向左右两个方向逐个像素填色，直到边界为止向左右两个方向逐个像素填色，直到边界为止n4、定范围：以、定范围：以 xLeft,xRight为为(3)得到的区段得到的区段 n5、进栈：分别在与当前扫描线相邻的上下扫描线上，确、进栈：分别在与当前扫描线相邻的上下扫描线上，确定位于区间定位于区间xLeft,xRight内的区段。内的区段。u如果区段内的像素
39、颜色值为如果区段内的像素颜色值为newColor或或boundaryColor，则转到（则转到（2）u区段压入堆栈，转到（区段压入堆栈，转到（2）55例例 扫描线算法*像素中的序号标指它所在像素中的序号标指它所在区段位于堆栈中的位置区段位于堆栈中的位置56l多边形扫描转换与区域填充方法比较多边形扫描转换与区域填充方法比较n基本思想不同基本思想不同u前者：顶点表示转换成点阵表示前者：顶点表示转换成点阵表示u后者：只改变区域内填充颜色，没有改变表示方法后者：只改变区域内填充颜色，没有改变表示方法n对边界的要求不同对边界的要求不同u前者：扫描线与多边形边界交点个数为偶数前者：扫描线与多边形边界交点个
40、数为偶数u后者：区域封闭，防止递归填充跨界后者：区域封闭，防止递归填充跨界n基本的条件不同基本的条件不同u前者：从边界顶点信息出发前者：从边界顶点信息出发u后者：区域内种子点后者：区域内种子点4.5.3 扫描转换与区域填充的比较57l填充方式填充方式n（1）均匀着色（）均匀着色（2）位图不透明）位图不透明(3)位图透明位图透明(4)像素图填充像素图填充n在确定区域内的像素后，查询它对应的位图或图像中的单元，在确定区域内的像素后，查询它对应的位图或图像中的单元，再以该单元的值按填充方式的不同显示该像素再以该单元的值按填充方式的不同显示该像素l方法方法n(1)均匀着色方法：将图元内部像素置成同一颜
41、色均匀着色方法：将图元内部像素置成同一颜色n(2)位图不透明：若像素对应的位图单元为位图不透明：若像素对应的位图单元为1，则以，则以前景色前景色显示显示该像素；若为该像素；若为0，则以背景色显示该像素；，则以背景色显示该像素；n(3)位图透明：若像素对应的位图单元为位图透明：若像素对应的位图单元为1，则以，则以前景色前景色显示该显示该像素；像素；若为若为0，则不做任何处理。，则不做任何处理。n(4)像素图填充：以像素对应的像素图单元的颜色值显示该像像素图填充：以像素对应的像素图单元的颜色值显示该像素。素。4.6 以图像填充区域58l基本问题基本问题n建立区域与图像间的对应关系建立区域与图像间的
42、对应关系方法方法1：建立整个绘图空间与图像空间的：建立整个绘图空间与图像空间的1-1映射映射4.6 以图像填充区域图像（纹理）图像（纹理）绘图空间绘图空间59l例例 适用：动画中漫游图适用：动画中漫游图像，像，如透过车窗看外景如透过车窗看外景4.6 以图像填充区域60方法方法2：建立区域局部坐标空间与图像空间的：建立区域局部坐标空间与图像空间的1-1映射映射4.6 以图像填充区域适用：图像作为区域表面属性的情况，例如，桌面与适用：图像作为区域表面属性的情况，例如，桌面与其上的木纹其上的木纹61l字符集字符集nASCII码：码：128个字符个字符nGB231280：汉字：汉字6763个，个，68
43、2个图形符号个图形符号l点阵字体点阵字体n存储（压缩与非压缩）存储（压缩与非压缩）n显示：检索与写缓冲显示：检索与写缓冲l矢量字体矢量字体n表示：笔画组成曲线（参数）表示：笔画组成曲线（参数）n扫描转换：参数到点阵扫描转换：参数到点阵n显示：显示：1、由编码检索、由编码检索 2、扫描转换、扫描转换n存储：空间少存储：空间少（windows下的仿宋体库：下的仿宋体库：SIMFANG.TTF 为为3904K）4.7 字符的表示与输出624.8 OpenGLOpenGL相关函数l区域函数（填充作用）区域函数（填充作用）n矩形函数：矩形函数：glRecti|s|f|dv()nglBegin()中的参数
44、中的参数 GL_POLYGON、GL_TRIANGLES、GL_TRIANGLE_STRIP、GL_TRIANGLE_FANn三角形的三种绘制参数三角形的三种绘制参数int p1=20,100,p2=50,50;int p3=110,50,p4=140,100;int p5=110,150,p6=50,150;glBegin(GL_TRIANGLES);glVertex2iv(p1);glVertex2iv(p2);glVertex2iv(p3);glVertex2iv(p4);glVertex2iv(p5);glVertex2iv(p6);glEnd();GL_TRIANGLE_STRIPG
45、L_TRIANGLESGL_TRIANGLE_FANp1p1p163l菜单函数菜单函数nint glutCreateMenu(void(*func)(int value);/创建菜单创建菜单nvoid glutAddMenuEntry(char*name,int value);/添加菜单项添加菜单项nvoid glutAddSubMenu(char*name,int menu);/添加子菜单添加子菜单nglutAttachMenu(int button);n例：例：4.8 OpenGL相关函数void MenuInit()int sub_menu1=glutCreateMenu(objectM
46、enu);glutAddMenuEntry(直线直线,11);glutAddMenuEntry(多边形多边形,12);glutCreateMenu(topMenu);glutAddSubMenu(图形图形,sub_menu1);glutAddMenuEntry(退出退出,2);glutAttachMenu(GLUT_RIGHT_BUTTON);void objectMenu(int id)if(id=11)GraphicsType=11;else if(id=12)GraphicsType=12;else GraphicsType=0;void topMenu(int id)if(id=2)e
47、xit(0);64l线框图与填充图线框图与填充图n函数：函数：glPloygonMode(face，displayMode)nface：指定前后面。可选值：指定前后面。可选值：GL_FRONT、GL_BACK和和GL_FRONT_AND_BACKndisplayMode：GL_FILL和和GL_LINE4.8 OpenGL相关函数void display(void)glClearColor(1.0,1.0,1.0,0.0);glClear(GL_COLOR_BUFFER_BIT);glPolygonMode(GL_FRONT,GL_LINE);glBegin(GL_POLYGON);glCol
48、or3f(1.0,0,0);glVertex2f(0.5,0);glVertex2f(-0.5,0.5);glVertex2f(-0.5,-0.5);glVertex2f(0.6,-0.5);glEnd();glFlush();前向面：顶点序列逆前向面：顶点序列逆时针顺序排列时针顺序排列65l颜色插值模式颜色插值模式n函数：函数：glShadeModel(mode)nMode:GL_FLAT和和GL_SMOOTHn例：例：4.8 OpenGL相关函数void display(void)glClearColor(1.0,1.0,1.0,0.0);glClear(GL_COLOR_BUFFER_B
49、IT);glShadeModel(GL_FLAT);/默认为默认为GL_SMOOTH glBegin(GL_POLYGON);glColor3f(1,0,0);glVertex2f(-0.5,0.5);glColor3f(0,1,0);glVertex2f(-0.5,-0.5);glColor3f(0,0,1);glVertex2f(0.5,-0.5);glColor3f(1,1,1);glVertex2f(0.5,0.5);glEnd();glFlush();GL_FLAT方式下方式下以第以第1个点颜色填充个点颜色填充66l顶点数组顶点数组n原因：复杂图形需要很多坐标描述，导致函数调用量大原
50、因：复杂图形需要很多坐标描述，导致函数调用量大增，影响程序的执行效率增，影响程序的执行效率n采用顶点数组减少函数调用采用顶点数组减少函数调用n方法方法u调用函数调用函数glEnableClientState(GL_VERTEX_ARRAY),激激活顶点数组特性活顶点数组特性u调用调用glVertexPointer指定顶点坐标的位置和数据格式指定顶点坐标的位置和数据格式u使用与数组相关的函数绘制图形使用与数组相关的函数绘制图形4.8 OpenGL相关函数67例：例：glClear(GL_COLOR_BUFFER_BIT);glColor3f(1.0,0.0,0.0);vertex2 pt=20,