计算机图形学5多边形扫描转换和区域填充.ppt

《计算机图形学5多边形扫描转换和区域填充.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、多边形的扫描转换与区域填充一、多边形的扫描转换前面讲的画直线是一维图形的光栅化，就是如何在计算机屏幕上即在一个离散的像素集上表示一个连续的图形。而多边形的扫描转换和区域填充这个问题是怎么样在离散的像素集上表示一个连续的二维图形。多边形有两种重要的表示方法：顶点表示和点阵表示。点阵表示P1P2P3P4P5顶点表示P6顶点表示是用多边形的顶点序列来表示多边形。这种表示直观、几何意义强、占内存少，易于进行几何变换，但由于它没有明确指出哪些象素在多边形内，故不能直接用于面着色。点阵表示是用位于多边形内的象素集合来刻画多边形。这种表示丢失了许多几何信息（如

2、边界、顶点等），但它却是光栅显示系统显示时所需的表示形式。这涉及到两个问题：第一个问题是如果知道边界，能否求出这个多边形哪些像素在多边形内。众所周知，在计算机上画图形，实际上就是写帧缓存（framebuffer）。如果知道多边形哪些像素在里面，就直接写到帧缓存里即可。第二个问题是知道多边形内部的像素，反过来求多边形的边界。很遗憾，这个问题不是图形学关心的问题，是模式识别所关心的问题。图形学、图像处理、模式识别、计算机视觉有密切的联系。我们只关心从顶点表示到点阵表示。光栅图形的一个基本问题是把多边形的顶点表示转换为点阵表示。这种转换称为多边形的扫描

3、转换。为什么叫扫描转换？因为光栅显示器是逐行扫描！区域填充:指先将区域的一点赋予指定的颜色，然后将该颜色扩展到整个区域的过程。多边形分为凸多边形、凹多边形、含内环的多边形等：（1）凸多边形任意两顶点间的连线均在多边形内。（2）凹多边形任意两顶点间的连线有不在多边形内的部分。凸多边形凹多边形含内环的多边形有关概念1)区域：一组相邻而且又相连的像素，而且具有相同属性的封闭区域。3)区域填充：以某种属性对整个区域进行设置的过程。2）种类：①单域②复合域逐点判断填充算法区域填充的基本(初级)方法:逐点判断填充算法逐点判断绘图窗口内的每一个像素；若在区域的

4、内部：用指定的属性设置该点；否则不予处理；设有如下函数：TruewhenxDInside(D,x,y)=FalsewhenxDD取矩形R(x1≤x≤x2,y1≤y≤y2)，使R包围D，则逐点判断填充算法如下：for(y=y1;y<=y2;y++)for(x=x1;x<=x2;x++)if(inside(D,x,y))drawpixel(x,y,color);上述算法原理简单、实用，但效率低；效率低的原因是没有考虑各象素之间的联系，孤立地考察象素与区域的关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费

5、很多时间。1）射线法；2）累计角度法；3）编码法；4）……..如何判断点在多边形的内或外？（包含性检查的方法）1）射线法；过被检测点任作一条射线,求其与边界的交点,若交点数为偶数,则该点在边界之外,否则在边界之内。PP逐点判断法2）累计角度法步骤从v点向多边形P顶点发出射线，形成有向角计算有相交的和，得出结论现在的问题是，知道多边形的边界，如何找到多边形内部的点，即把多边形内部填上颜色。对每条横越多边形的扫描线，扫描转换算法确定扫描线与多边形边的交点位置。扫描线交点交点交点交点X-扫描线算法填充多边形的基本思想是按扫描线顺序，计算扫描线与多边形的

6、相交区间，再用要求的颜色显示这些区间的像素，即完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。根据该原理，X-扫描线算法可以填充凸的、凹的、还可以是带孔的多边形。1、x-扫描线算法扫描线交点交点交点交点对于每条穿越多边形的扫描线，X-扫描线算法确定扫描线与多边形边相交区间的像素点位置。x-扫描线算法填充多边形xy213456789111234567891011121012如扫描线y=3与多边形的边界相交于4点：（2，3）、（4，3）、（7，3）、（9，3）。这四点定义了扫描线从X=2到X=4，从X=7到X=9两个落在多边形内的

7、区间，该区间内的像素应取填充色。从该例可以看出，算法的核心是需按x递增顺序排列交点的x坐标序列。由此，可得到X-扫描线算法步骤如下：（1）确定多边形所占有的最大扫描线数，得到多边形顶点的最小和最大y值（ymin和ymax）。（2）从y=ymin到y=ymax，每次用一条扫描线进行填充。（3）对一条扫描线填充的过程可分为四个步骤：a、求交：计算扫描线与多边形各边的交点；b、排序：把所有交点按递增顺序进行排序；注意：交点在计算时未必是按递增顺序排列的。c、交点配对：第一个与第二个，第三个与第四个等等，每对交点就代表扫描线与多边形的一个相交区间；d、区

8、间填色：把这些相交区间内的像素置成不同于背景色的填充色。在填充过程，当扫描线与多边形顶点相交时，交点的取舍问题??（交点的个数应保证为偶