〈新〉第四章二维填充图元的生成1.ppt

4.1.1概念 多边形分为凸多边形、凹多边形、含内环的多边形。 多边形的表示方法 顶点表示 点阵表示 顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。 点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。 多边形的扫描转换： 把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。 两种方法：扫描线算法；边界标志法。 扫描线算法 目标：利用相邻像素之间的连贯性，提高算法效率 处理对象：非自交多边形 （边与边之间除了顶点外无其它交点） 交点的取整规则 要求：使生成的像素全部位于多边形之内 用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用 假定非水平边与扫描线y=e 相交，交点的横坐标为x, 规则如下 ●规则1： X为小数，即交点落于扫描线上两个相邻像素之间 (a)交点位于左边之上，向右取整 (b)交点位于右边之上，向左取整 ●规则2： 边界上象素的取舍问题，避免填充扩大化。 ●解决方法： 边界象素：规定落在右上边界的象素不予填充。 具体实现时，只要对扫描线与多边形的相交区间左闭右开 ●规则3： 扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。 ●解决方法： 检查两相邻边在扫描线的哪一侧。 只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。 算法步骤： (1)确定多边形所占有的最大扫描线数。即得到多边形顶点的最小和最大y值。（Ymin和Ymax) (2)从y=ymin到y=ymax:每次用一条扫描线填充。 (3)填充步骤： 求交：计算扫描线与多边形各边的交点。 排序：所有交点按递增的顺序排序。 交点配对：第一个与第二个，第三个与第四个等，每对交点代表扫描线与多边行的一个相交区间。　 区间填色：把这些相交区间内的像素置成不同于背景的填充色。　　　　　 存在的问题： 　　当扫描线与多边形顶点相交时，交点的取舍问题． 解决的方法： 　　共享顶点的两条边分别落在扫描线的两边，则交点只算一个． 　　共享顶点的两条边在扫描线的一侧，则交点算０或者２个． (2)边表（ＥＴ：Edge Table):是一个包含多边形全部边记录的表。 边表 (4)算法实现步骤 这样，当建立了边的分类表ET后，扫描线算法可按下列步骤进行： （1）取扫描线纵坐标y的初始值为ET中非空元素的最小序号。 （2）将边的活化链表AEL设置为空。 （3）按从下到上的顺序对纵坐标值为y的扫描线（当前扫描线）执行下列步骤，直到边的分类表ET和边的活化链表都变成空为止。 1）如边分类表ET中的第y类元素非空，则将属于该类的所有边从ET中取出并插入边的活化链表中，AEL中的各边按照x值（当x值相等时，按Δx值）递增方向排序。 2）若相对于当前扫描线，边的活化链表AEL非空，则将AEL中的边两两依次配对，即1，2边为一对，3，4边为一对，依次类推。每一对边与当前扫描线的交点所构成的区段位于多边形内，依次对这些区段上的点（象素）按多边形属性着色。 3）将边的活化链表AEL中满足y=ymax的边删去。 4）将边的活化链表AEL剩下的每一条边的x域累加Δx，即x:=x+Δx。 5）将当前的扫描线的纵坐标值y累加1，即y=y+1。 扫描线算法 特点：算法效率较高。 缺点：对各种表的维持和排序开销太大，适合软件实现而不适合硬件实现。 扫描线算法 问题： 如何处理多边形的水平边？ 如何修改扫描线算法，使它能处理边自交的多边形？ 边界标志算法:算法过程 void edgemark_fill(polydef, color) 多边形定义 polydef； int color; { 对多边形polydef 每条边进行直线扫描转换； inside = FALSE; for (每条与多边形polydef相交的扫描线y ) for (扫描线上每个象素x ) { if(象素 x 被打上边标志) inside = ! (inside); if(inside！= FALSE) drawpixel (x, y, color); else drawpixel (x, y, background); } } 边界标