资源描述:
《光栅图形的转换与区域填充》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第四章光栅图形的扫描转换与区域填充扫描转换矩形扫描转换多边形区域填充扫描转换矩形问题:矩形是简单的多边形,那么为什么要单独处理矩形?比一般多边形可简化计算。应用非常多(窗口系统)。共享边界如何处理?原则:左闭右开,下闭上开属于谁?方法:voidFillRectangle(Rectangle*rect,intcolor){intx,y;for(y=rect->ymin;y<=rect->ymax;y++)for(x=rect->xmin;x<=rect->xmax;x++)PutPixel(x,y,color);}/*endofFillRectangle()*/扫描转换矩形扫描
2、转换多边形凸多边形凹多边形含内环的多边形多边形的表示方法顶点表示点阵表示顶点表示:用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少;不能直接用于面着色。点阵表示:用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息;便于运用帧缓冲存储器表示图形,易于面着色。扫描转换多边形多边形的扫描转换多边形的扫描转换:把多边形的顶点表示转换为点阵表示,也就是从多边形的给定边界出发,求出位于其内部的各个象素,并给帧缓冲器内的各个对应元素设置相应的灰度和颜色,通常称这种转换为多边形的扫描转换。几种方法:逐点判断法;扫描线算法;边缘填充法;栅栏填充法;边界标志法。voidF
3、illPolygonPbyP(Polygon*P,intpolygonColor){intx,y;for(y=ymin;y<=ymax;y++)for(x=xmin;x<=xmax;x++)if(IsInside(P,x,y))PutPixel(x,y,polygonColor);elsePutPixel(x,y,backgroundColor);}/*endofFillPolygonPbyP()*/#defineMAX100Typedefstruct{intPolygonNum;//多边形顶点个数Pointvertexces[MAX]//多边形顶点数组}Polygon//多
4、边形结构逐点判断法逐个判断绘图窗口内的像素如何判断点在多边形的内外关系?1)射线法;2)累计角度法;3)编码法;逐点判断法1)射线法步骤:从待判别点v发出射线求交点个数kK的奇偶性决定了点与多边形的内外关系逐点判断法2)累计角度法步骤从v点向多边形P顶点发出射线,形成有向角计算有向角的和(逆时针为正,顺时针为负)预处理逐点判断法3)编码方法:累计角度方法的离散方法(略)Step:a.预处理,测试点在边上否?b.V为中点作局部坐标系,对象限按逆时针(或顺时针)编码;c.顶点编码Ipi,d.边编码。PiPi+1:△PiPi+1=Ipi+1-Ipie.计算∑△PiPi+1(其中△P
5、nPn+1=△PnP0):若∑为0,V在P外;若∑为+/-4,V在P内;逐点判断法程序简单,速度太慢,效率低。P0P1P2v逐点判断法逐点判断的算法虽然程序简单,但不可取。原因是速度太慢,主要是由于该算法割断了各象素之间的联系,孤立地考察各象素与多边形的内外关系,使得几十万甚至几百万个象素都要一一判别,每次判别又要多次求交点,需要做大量的乘除运算,花费很多时间。逐点判断法扫描线算法目标:利用相邻像素之间的连贯性,提高算法效率处理对象:非自交多边形(边与边之间除了顶点外无其它交点)交点的取整规则要求:使生成的像素全部位于多边形之内用于线画图元扫描转换的四舍五入原则导致部分像素位
6、于多边形之外,从而不可用假定非水平边与扫描线y=e相交,交点的横坐标为x,规则如下扫描线算法由中点算法求出的多边形边界上的像素规则1:X为小数,即交点落于扫描线上两个相邻像素之间(a)交点位于左边之上,向右取整(b)交点位于右边之上,向左取整扫描线算法规则2:边界上象素的取舍问题,避免填充扩大化。解决方法:边界象素:规定落在右上边界的象素不予填充。具体实现时,只要对扫描线与多边形的相交区间左闭右开扫描线算法规则3:扫描线与多边形的顶点相交时,交点的取舍,保证交点正确配对。解决方法:检查两相邻边在扫描线的哪一侧。只要检查顶点的两条边的另外两个端点的Y值,两个Y值中大于交点Y值的
7、个数是0,1,2,来决定取0,1,2个交点。扫描线算法扫描线算法特殊情况处理水平边:扔掉!尖角:反混淆扫描线算法是多边形扫描转换的常用算法。与逐点判断算法相比,扫描线算法充分利用了相邻象素之间的连贯性,避免了对象素的逐点判断和反复求交的运算,达到了减少了计算量和提高速度的目的。开发和利用相邻象素之间的连贯性是光栅图形算法研究的重要内容。扫描转换算法综合利用了区域的连贯性、扫描线连贯性和边的连贯性等三种形式的连贯性。扫描线算法设多边形P的顶点Pi=(xi,yi),i=0,1,…,n,又设yi0,yi1,…