第七章
光栅图形的扫描转换与区域填色
可编辑ppt
1
多边形的两种表示方法
可编辑ppt
2
两种表示方法的优缺点
可编辑ppt
3
什么是多边形的扫描转换
可编辑ppt
4
逐点判断算法
算法思想：逐个像素判别，检测其是否 在多边形内部，从而给出位于多边形内 部的像素集合。
可编辑ppt
5
逐点判断算法的具体实现
假设P=P0P1P2…PnP0为一个给定多边形， P0,P1,P2…Pn为其顶点表示。 假设inside(P,x,y)是验证点(x,y)是否在多 边形P内的布尔函数。
可编辑ppt
20
出现奇点的两种情况的讨论
极值点就是附近的点都比其小或都比其 大，满足数学表达式为(yi-1-yi)(yi+1-yi)>0 不是极值点的顶点称为非极值点。
可编辑ppt
21
对于奇点的两种情况的处理
可编辑ppt
22
扫描线算法的数据结构
可编辑ppt
23
边的分类表ET
边的分类表ET是按边下端点的纵坐标y 对非水平边进行分类的链表数组。
可编辑ppt
24
边的活化表AEL
边的活化表AEL由与当前扫描线相交的
所有多边形的边组成，它记录了多边形
边沿扫描线的交点序列，并根据递推式：
xe,ir
xd, jr
1 mr
不断刷新交点序列。
可编辑ppt
25
扫描线算法的描述
步骤1：(y初始化)建立ET表，并且取扫 描线纵坐标y的初始值为ET中非空元素的 最小序列。
可编辑ppt
27
子算法步骤
2)若相对于当前扫描线，边的活化链表 AEL非空，则将AEL中边两两依次配对 (位置位于1,2的配对；位置位于3,4的配 对)，依次配对的边的内部点(像素)按多 边形的颜色属性进行着色。
可编辑ppt
28
子算法步骤
3)将边的活化链表AEL中ymax＝y的边删去 4)将边的活化链表AEL剩下的每一条边的 x域累加Δx，即x:=x+Δx 5)将当前扫描线的纵坐标值y累加1，即 y:=y+1
xerxdrxxdrm 1r
可编辑ppt
17
怎样得到y=e上的交点序列
通过递推式可以算出与y=e和y=d都相交 的点 若再求出与扫描线y=d不相交但与下一扫 描线y=e相交的所有边PqPq+1上的交点xeq 然后把这些点按底层的顺序排列，就能 得到了y=e上的交点序列
可编辑ppt
18
边的连贯性
当取某一整数k，0<=k<=n-1，使
可编辑ppt
6
Inside函数的实现原理
计算从(x,y)到(+∞,y)的射线与多边形的交 点个数。 若交点个数是奇数的话，就表明该点在 多边形内部，否则该点在多边形外部。
可编辑ppt
7
逐点判断算法的具体实现
假设framebuffer(x,y)是与(x,y)对应的帧 缓冲器中的元素，用以存放对应像素的 颜色值。设polygon_color为多边形内的 颜色值，background_color为背景颜色。可编辑pLeabharlann t13分割后区域的分类
这些梯形分为两类：在多边形P内部和在 多边形P外部。 两类梯形交替地排列在长方形区域内。 如果知道了某点q所在区域在多边形内 (或外)，就能知道整个长方形区域内的 梯形排列情况。 此性质称为区域的连贯性。
可编辑ppt
14
扫描线的连贯性
假设e为一整数满足 yineyi0若扫描 线y=e与多边形P的边Pi-1Pi相交，则记 其交点的横坐标xei。 现在假设xei1,xei2,…,xeil为扫描线与P的 边界各交点的横坐标的递增序列，称为 交点序列。
步骤2：(AEL初始化)将边的活化链表 AEL设置为空。
步骤3：按从下到上的顺序对纵坐标值为 y的扫描线(当前扫描线)执行子算法，直 到ET和AEL都变为空为止。
可编辑ppt
26
子算法步骤
1)如果边分类表ET中第y类元素为非空， 则将属于该类的所有边从ET中取出并插 入边的活化链表AEL中，AEL中各边按x的 值(当x的值相等时，按Δx值)递增方式 排序。
可编辑ppt
15
交点序列的性质
l是偶数。 在该扫描线上只有区段(xeik,xei,k+1)， (k=1,3,5…l-1)位于多边形P内，其余均在 多边形P外，两种区段沿扫描线相间排列。 此性质称为扫描线的连贯性。
可编辑ppt
16
交点序列
若d=e-1，则位于扫描线y=d上的交点序 列为xdj1,xdj2,…,xdjk。 若多边形P的边Pr-1Pr与扫描线y=e和 y=d都相交，则xer和xdr满足：
可编辑ppt
8
逐点判断算法的伪代码程序
for y:=screen_ymin to screen_ymax do for x:=screen_xmin to screen_xmax do if inside(P,x+0.5,y+0.5) then
setpixel(framebuffer,x,y,polygon_color) else setpixel(framebuffer,x,y,background_co
yi,k1e,dyi,k
1)两序列元素数个数相等
2)点(xeir,e)与(xdjr,d)位于多边形同一条边
上，即ir=jr，得到
xe,ir xd, jr
1 mr
由上式就可递推出xeir。
可编辑ppt
19
奇点的处理
当扫描线与多边形P的边界的交点是P的 顶点时，该交点称为奇点。 由于连贯性，每一条扫描线与多边形P的 边界交点个数都是偶数。但是过奇点的 扫描线可能出现奇数。
lor)
可编辑ppt
9
逐点判断算法的优缺点
优点：简单，易于理解。 缺点：忽略了像素与像素之间的联系， 如果整个平面有几千万个像素，也要一 一进行判别，要做大量的计算工作，效 率太低。
可编辑ppt
10
扫描线算法
扫描线算法利用了相邻像素之间的连贯 性，避免了反复求交的运算。 扫描线算法综合利用了区域的连贯性， 扫描线的连贯性和边的连贯性。
可编辑ppt
11
区域的连贯性
假设多边形P的顶点Pi(xi,yi),i=0,1,2…n
各个顶点Pi的纵坐标按yi递减排序：
yi0, yi1, yi2… yin
其中yi,k>= yi,k+1
可编辑ppt
12
区域的分割
现在作两条扫描线y=yi,k和y=yi,k+1，这 两条扫描线之间的区域被多边形分割成 若干个梯形。 梯形上下两底分别为两条扫描线，腰在 多边形P的边上或在显示屏幕的边界上。