资源描述：
《计算机图形学第七章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第七章光栅图形的扫描转换与区域填色多边形的两种表示方法多边形的表示方法顶点表示－用多边形的顶点来表示点阵表示－用多边形内的象素来表示两种表示方法的优缺点顶点表示：直观，几何意义强，占内存少，用得普遍，但不能直接用于面着色。点阵表示：便于用帧缓冲器表示图形，便于面着色。什么是多边形的扫描转换顶点表示点阵表示多边形的扫描转换逐点判断算法算法思想：逐个像素判别，检测其是否在多边形内部，从而给出位于多边形内部的像素集合。逐点判断算法的具体实现假设P=P0P1P2…PnP0为一个给定多边形，P0,P1,P2…Pn为其顶点表示。假设inside(P,x,y)
2、是验证点(x,y)是否在多边形P内的布尔函数。Inside函数的实现原理计算从(x,y)到(+∞,y)的射线与多边形的交点个数。若交点个数是奇数的话，就表明该点在多边形内部，否则该点在多边形外部。逐点判断算法的具体实现假设framebuffer(x,y)是与(x,y)对应的帧缓冲器中的元素，用以存放对应像素的颜色值。设polygon_color为多边形内的颜色值，background_color为背景颜色。逐点判断算法的伪代码程序fory:=screen_ymintoscreen_ymaxdoforx:=screen_xmintoscreen_x
3、maxdoifinside(P,x+0.5,y+0.5)thensetpixel(framebuffer,x,y,polygon_color)elsesetpixel(framebuffer,x,y,background_color)逐点判断算法的优缺点优点：简单，易于理解。缺点：忽略了像素与像素之间的联系，如果整个平面有几千万个像素，也要一一进行判别，要做大量的计算工作，效率太低。扫描线算法扫描线算法利用了相邻像素之间的连贯性，避免了反复求交的运算。扫描线算法综合利用了区域的连贯性，扫描线的连贯性和边的连贯性。区域的连贯性假设多边形P的顶点Pi
4、(xi,yi),i=0,1,2…n各个顶点Pi的纵坐标按yi递减排序：yi0,yi1,yi2…yin其中yi,k>=yi,k+1区域的分割现在作两条扫描线y=yi,k和y=yi,k+1，这两条扫描线之间的区域被多边形分割成若干个梯形。梯形上下两底分别为两条扫描线，腰在多边形P的边上或在显示屏幕的边界上。分割后区域的分类这些梯形分为两类：在多边形P内部和在多边形P外部。两类梯形交替地排列在长方形区域内。如果知道了某点q所在区域在多边形内(或外)，就能知道整个长方形区域内的梯形排列情况。此性质称为区域的连贯性。扫描线的连贯性假设e为一整数满足若扫描线
5、y=e与多边形P的边Pi-1Pi相交，则记其交点的横坐标xei。现在假设xei1,xei2,…,xeil为扫描线与P的边界各交点的横坐标的递增序列，称为交点序列。交点序列的性质l是偶数。在该扫描线上只有区段(xeik,xei,k+1)，(k=1,3,5…l-1)位于多边形P内，其余均在多边形P外，两种区段沿扫描线相间排列。此性质称为扫描线的连贯性。交点序列若d=e-1，则位于扫描线y=d上的交点序列为xdj1,xdj2,…,xdjk。若多边形P的边Pr-1Pr与扫描线y=e和y=d都相交，则xer和xdr满足：怎样得到y=e上的交点序列通过递推式
6、可以算出与y=e和y=d都相交的点若再求出与扫描线y=d不相交但与下一扫描线y=e相交的所有边PqPq+1上的交点xeq然后把这些点按底层的顺序排列，就能得到了y=e上的交点序列边的连贯性当取某一整数k，0<=k<=n-1，使1)两序列元素数个数相等2)点(xeir,e)与(xdjr,d)位于多边形同一条边上，即ir=jr，得到由上式就可递推出xeir。奇点的处理当扫描线与多边形P的边界的交点是P的顶点时，该交点称为奇点。由于连贯性，每一条扫描线与多边形P的边界交点个数都是偶数。但是过奇点的扫描线可能出现奇数。出现奇点的两种情况出现奇点的两种情况
7、的讨论极值点就是附近的点都比其小或都比其大，满足数学表达式为(yi-1-yi)(yi+1-yi)>0不是极值点的顶点称为非极值点。P所有的顶点极值点非极值点对于奇点的两种情况的处理交点个数加一交点个数不变扫描线算法的数据结构数据结构边的分类表ET边的活化链表AELYmax:边的上端点的y坐标x:在ET中表示边的下端点的x坐标，在AEL中则表示边与扫描线交点的x坐标Δx:边的斜率的倒数next:指向下一条边的指针边的分类表ET边的分类表ET是按边下端点的纵坐标y对非水平边进行分类的链表数组。1016e7e5e7e5e4e4e1e1e2e2e3e3边
8、的活化表AEL边的活化表AEL由与当前扫描线相交的所有多边形的边组成，它记录了多边形边沿扫描线的交点序列，并根据递推式：AELe1e2e
