第4章基本图形生成算法1第4章基本图形生成算法4.1直线的扫描转换重点4.2圆与椭圆的扫描转换4.3区域填充4.4线宽与线形的处理4.5字符略4.6裁减4.7反走样本节要求1本节的教学目标结合光栅扫描原理学习图形填充的基本算法理解多边形区域填充算法和种子填充算法。2本节的教学效果领悟到计算机屏幕上显示的彩色图案竟然是一个点一个点设置的这是显示图形耗费时间的原因之一。注意到在光栅扫描显示器上显示一个图形仅仅显示图形边界是不够的还应该填充各种颜色或图案。填充的过程既要准确又要迅速原因是屏幕上要画的东西太多。如果遇到相关的研究或开发课题查阅资料后可以完成任务。3本节的教学要求当堂理解讲授的内容。4.3区域填充区域填充研究如何用一种颜色或一个图案来充满一个二维区域。区域填充绿色图案填充热气球第4章基本图形生成算法2区域是指一组具有相同的属性并相邻又相连的象素。区域填充根据边或顶点的简单描述生成区域的过程叫作区域填充。区域填充要做的工作有两个一是在什么地方填充二是填充什么内容。区域填充可以分为两大类扫描转换填充算法和种子填充算法。1扫描转换填充算法按扫描线的顺序确定《计算机图形学基础》唐P99以及陈元琰P67。2种子填充算法种子填充算法是假设在多边形或区域的内部至少有一个象素是已知的然后设法找到区域内所有其它象素并对它们进行填充。《计算机图形学》孙家广P1854.3.1多边形域的填充见FLASH“X-扫描线算法填充”该算法与输入/输出的细节无关因而也与设备无关。它的缺点是对各种表的维持和排序开销太大适于软件而不适合于硬件。本节讨论用单一颜色或图案填充二维多边形区域的方法。这里所讨论的多边形区域可以是凸的、凹的还可以是带孔的。常用的办法是按扫描线顺序计算扫描线与多边形的相交区间再用要求的颜色显示这些区间的象素即可完成填充工作。区间的端点可以通过计算扫描线与多边形边界的交点获得。由实际情况看填充方法孙P179图4.3.1扫描线6与多边形的边界线交于四点A、B、C、D。这四点把扫描线分为五个区间02y轴到A不填充23.5A到B填充3.57B到C不填充711C到D填充1112D到x12的直线段。其中23.5711两个区间落在多边形内该区间内的像的素应取多边形色红色。其他区间内的像素取背景色。由分析寻找填充的规律一般情况的多边形填充步骤1求交点计算扫描线与多边形各边的交点。例如按P1—P6的顺序可得交点DCBA。2排序所有的交点按x值的递增排序。例如A的x值最小D的x值最大则排序结果为ABCD。3交点配对第1与第2第3与第4等等每对交点代表扫描线与多边形的一个相交区间。例如A与B为一个相交区间C与D为另一个相交第4章基本图形生成算法3区间。4区间填色相交区间之内的像素置成多边形颜色之外置成背景色。例如AB之间置成红色CD之间置成红色特殊情况的多边形填充方法以上填充方法并不一定适用于所有情况例如扫描线2在P1点就与P6P1线段和P1P2两个线段相交故得到x坐标序列为228这导致22之间填充多边形色而由于28区间是第2个区间故错误地填充背景色。所以填充过程中必须解决两个特殊问题。即交点的取舍问题以便保证交点的正确配对。还有边界上的像素的取舍问题以便避免填充扩大化。交点的取舍问题分析为了正确地进行交点取舍必须对两种情况区别对待。1第一种情况扫描线交于一顶点而共享顶点的两条边分别落在扫描线的两边例如上图中的P1点。这时交点只算一个。2第二种情况共享交点的两条边在扫描线的同一边这时交点作为零个或两个如果交点处于多边形的局部最高点则取零个例如P6点如果交78654321P122P251P3113P4118P556P627ABCD第4章基本图形生成算法4点处于多边形的局部最低点则取两个例如P2点。处理综合第一第二种情况在具体实现时只需检查顶点的两条边的另外的两个端点的y值。按这两个y值中大于交点y值的个数是012来决定是取零个、一个还是两个。例如扫描线1与P2相交共享该点的两条边的另外两个顶点P1和P3均高于扫描线故取交点P2两次。P2点设置为多边形色。例如扫描线2与P1相交共享该点的两条边的一个顶点P6均高于扫描线另一个顶点P2均低于扫描线故取交点P1一次。例如扫描线7与P6相交共享该点的两条边的另外两个顶点P1和P5均低于扫描线故取交点P60次该点不与填充。4.3.2边填充算法略见FLASH“边缘填充算法的过程”该算法优点是简单缺点是对于复杂图形每一个象素可能被多次访问输入/输出的量大。第4章基本图形生成算法54.3.3种子填充算法见FLASH“4-连通边界填充”以上讨论的多边形填充算法都是按扫描线顺序进行的。种子填充算法则采用不同的原理假设在多边形区域内部有一象素已知由此出发找到区域内的所有象素。在本节讨论中假设区域采用边界定义即区域边界上所有象素均具有