《多边形的转换》PPT课件

《《多边形的转换》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章多边形的扫描转换与区域填充4.1多边形扫描转换4.2区域填充多边形分为凸多边形、凹多边形、含内环的多边形。4.1多边形的扫描转换4.1多边形的扫描转换多边形的表示方法顶点表示点阵表示顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。4.1多边形的扫描转换多边形的扫描转换：把多边形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置

2、相应的灰度和颜色，通常称这种转换为多边形的扫描转换。两种方法：扫描线算法；边界标志法。扫描线算法扫描线算法目标：利用相邻像素之间的连贯性，提高算法效率处理对象：非自交多边形（边与边之间除了顶点外无其它交点）扫描线算法交点的取整规则要求：使生成的像素全部位于多边形之内用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外，从而不可用假定非水平边与扫描线y=e相交，交点的横坐标为x,规则如下扫描线算法●规则1：X为小数，即交点落于扫描线上两个相邻像素之间(a)交点位于左边之上，向右取整(b)交点位于右边之上，向左取整●规则2：边界上象素的取舍问题，避免

3、填充扩大化。●解决方法：边界象素：规定落在右上边界的象素不予填充。具体实现时，只要对扫描线与多边形的相交区间左闭右开扫描线算法●规则3：扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。●解决方法：检查两相邻边在扫描线的哪一侧。只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。扫描线算法扫描线算法是多边形扫描转换的常用算法。与逐点判断算法相比，扫描线算法充分利用了相邻象素之间的连贯性，避免了对象素的逐点判断和反复求交的运算，达到了减少了计算量和提高速度的目的。开发和利用相邻象素之间的连贯

4、性是光栅图形算法研究的重要内容。扫描转换算法综合利用了区域的连贯性、扫描线连贯性和边的连贯性等三种形式的连贯性。扫描线算法设多边形P的顶点Pi=(xi,yi),i=0,1,…,n，又设yi0,yi1,…yin是各顶点Pi的坐标yi的递减数列，即yik≥yik+1,0≤k≤n-1这样，当yik≥yik+1,0≤k≤n-1时，屏幕上位于y=yik和y=yik+1两条扫描线之间的长方形区域被多边形P的边分割成若干梯形（三角形可看作其中一底边长为零的梯形），它们具有下列性质：区域的连贯性y=yiky=yik+1区域的连贯性1）梯形的两底边分别在y=yik和y=y

5、ik+1两条扫描线上，腰在多边形P的边上或在显示屏幕的边界上。2）这些梯形可分为两类：一类位于多边形P的内部；另一类在多边形P的外部。3）两类梯形在长方形区域{yik,yik+1}内相间的排列，即相邻的两梯形必有一个在多边形P内，另一个在P外。y=yik+1y=yik区域的连贯性根据这些性质，实际上只需知道该长方形区域内任一梯形内一点关于多边形P的内外关系后，即可确定区域内所有梯形关于P的内外关系。设e为一整数，yi0≥e≥yin。若扫描线y=e与多边形P的Pi-1Pi相交，则记其交点的横坐标为xei。现设xei1,xei2,xei3,…,xeil是该扫

6、描线与P的边界各交点横坐标的递增序列，称此序列为交点序列。由区域的连贯性可知，此交点序列具有以下性质：扫描线的连贯性扫描线的连贯性1）设L是偶数。2）在该扫描线上，只有区段(xeik,xeik+1）,k=1,3,5,…,L-1位于多边形P内，其余区段都在P外。以上性质称为扫描线的连贯性，它是多边形区域连贯性在一条扫描线上的反映。设d为一整数，并且d=e-1,并且yi0≥d≥yin。设位于扫描线y=d上的交点序列为xdj1,xdj2,xdj3,…,xdjk现在来讨论扫描线d，e交点序列之间的关系。若多边形P的边Pr-1Pr与扫描线y=e,y=d都相交，则交

7、点序列中对应元素xer,xdr满足下列关系：xer=xdr+1/mr(1)其中mr为边Pr-1Pr的斜率。边的连贯性y=ey=d边的连贯性于是，可利用d的交点序列计算e的交点序列，即先运用递推关系式(1)求得与扫描线y=e和y=d都相交的所有多边形上的交点xer,再求得与扫描线y=d不相交但与扫描线y=e相交的所有边PqPq+1上的交点xeq。如果P的顶点的坐标是整数，那么xeq=xq或xeq=xq+1,然后把这两部分按递增的顺序排列，即可得e的交点序列。y=ey=d边的连贯性特别是当存在某一个整数k,0≤k≤n-1,使得yik>e,d>yik+1成立时

8、，则由区域的连贯性可知d的交点序列和e的交点序列之间有以下关系：1）两序列元素的