第四章光栅图形的扫描转换与区域填充.ppt
《第四章光栅图形的扫描转换与区域填充.ppt》由会员分享,可在线阅读,更多相关《第四章光栅图形的扫描转换与区域填充.ppt(69页珍藏版)》请在三一文库上搜索。
1、第四章 光栅图形的扫描转换与区域填充,扫描转换矩形 扫描转换多边形 区域填充,扫描转换矩形,问题: 矩形是简单的多边形,那么为什么要单独处理矩形? 比一般多边形可简化计算。 应用非常多(窗口系统)。 共享边界如何处理? 原则:左闭右开,下闭上开,属于谁?,方法:,void FillRectangle(Rectangle *rect,int color) int x,y; for(y = rect-ymin;y ymax;y+) for(x = rect-xmin;x xmax;x+) PutPixel(x,y,color); /*end of FillRectangle() */,扫描转换矩形
2、,扫描转换多边形,凸多边形 凹多边形 含内环的多边形,多边形的表示方法 顶点表示 点阵表示 顶点表示:用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少;不能直接用于面着色。 点阵表示:用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息;便于运用帧缓冲存储器表示图形,易于面着色。,扫描转换多边形,多边形的扫描转换,多边形的扫描转换:把多边形的顶点表示转换为点阵表示,也就是从多边形的给定边界出发,求出位于其内部的各个象素,并给帧缓冲器内的各个对应元素设置相应的灰度和颜色,通常称这种转换为多边形的扫描转换。 几种方法:逐点判断法;扫描线算法;边缘填充法;栅栏填充法;边界标志法
3、。,void FillPolygonPbyP(Polygon *P,int polygonColor) int x,y; for(y = ymin;y = ymax;y+) for(x = xmin;x = xmax;x+) if(IsInside(P,x,y) PutPixel(x,y,polygonColor); else PutPixel(x,y,backgroundColor); /*end of FillPolygonPbyP() */,#define MAX 100 Typedef struct int PolygonNum; / 多边形顶点个数 Point vertexcesMA
4、X /多边形顶点数组 Polygon / 多边形结构,逐点判断法,逐个判断绘图窗口内的像素 如何判断点在多边形的内外关系? 1)射线法; 2)累计角度法; 3)编码法;,逐点判断法,1)射线法 步骤: 从待判别点v发出射线 求交点个数k K的奇偶性决定了点与多边形的内外关系,逐点判断法,2)累计角度法 步骤 从v点向多边形P顶点发出射线,形成有向角 计算有向角的和(逆时针为正,顺时针为负) 预处理,逐点判断法,3)编码方法:累计角度方法的离散方法(略) Step: a.预处理,测试点在边上否? b.V为中点作局部坐标系,对象限按逆 时针(或顺时针)编码; c.顶点编码Ipi, d.边编码。Pi
5、Pi+1: PiPi+1=Ipi+1-Ipi e.计算 PiPi+1 (其中PnPn+1 = PnP0): 若 为0, V在P外; 若 为+/-4,V 在P内; 逐点判断法程序简单, 速度太慢,效率低。,逐点判断法,逐点判断的算法虽然程序简单,但不可取。原因是速度太慢,主要是由于该算法割断了各象素之间的联系,孤立地考察各象素与多边形的内外关系,使得几十万甚至几百万个象素都要一一判别,每次判别又要多次求交点,需要做大量的乘除运算,花费很多时间。,逐点判断法,扫描线算法,目标:利用相邻像素之间的连贯性,提高算法效率 处理对象:非自交多边形 (边与边之间除了顶点外无其它交点),交点的取整规则 要求:
6、使生成的像素全部位于多边形之内 用于线画图元扫描转换的四舍五入原则导致部分像素位于多边形之外,从而不可用 假定非水平边与扫描线y=e 相交,交点的横坐标为x, 规则如下,扫描线算法,由中点算法求出的多边形边界上的像素,规则1: X为小数,即交点落于扫描线上两个相邻像素之间 (a)交点位于左边之上,向右取整 (b)交点位于右边之上,向左取整,扫描线算法,规则2: 边界上象素的取舍问题,避免填充扩大化。 解决方法: 边界象素:规定落在右上边界的象素不予填充。 具体实现时,只要对扫描线与多边形的相交区间左闭右开,扫描线算法,规则3: 扫描线与多边形的顶点相交时,交点的取舍,保证交点正确配对。 解决方
7、法: 检查两相邻边在扫描线的哪一侧。 只要检查顶点的两条边的另外两个端点的Y值,两个Y值中大于交点Y值的个数是0,1,2,来决定取0,1,2个交点。,扫描线算法,扫描线算法,特殊情况处理 水平边:扔掉! 尖角:反混淆,扫描线算法是多边形扫描转换的常用算法。与逐点判断算法相比,扫描线算法充分利用了相邻象素之间的连贯性,避免了对象素的逐点判断和反复求交的运算,达到了减少了计算量和提高速度的目的。 开发和利用相邻象素之间的连贯性是光栅图形算法研究的重要内容。扫描转换算法综合利用了区域的连贯性、扫描线连贯性和边的连贯性等三种形式的连贯性。,扫描线算法,设多边形P的顶点Pi=(xi,yi),i=0,1,
8、 ,n,又设yi0,yi1,yin是各顶点Pi的坐标yi的递减数列,即yikyik+1,0kn-1.这样,当yikyik+1,0kn-1时,屏幕上位于y=yik和y=yik+1两条扫描线之间的长方形区域被多边形P的边分割成若干梯形(三角形可看作其中一底边长为零的梯形),它们具有下列性质:,区域的连贯性,1)梯形的两底边分别在y=yik和y=yik+1两条扫描线上,腰在多边形P的边上或在显示屏幕的边界上。 2)这些梯形可分为两类:一类位于多边形P的内部;另一类在多边形P的外部。 3)两类梯形在长方形区域yik,yik+1内相间的排列,即相邻的两梯形必有一个在多边形P内,另一个在P外。,区域的连贯
9、性,根据这些性质,实际上只需知道该长方形区域内任一梯形内一点关于多边形P的内外关系后,即可确定区域内所有梯形关于P的内外关系。,区域的连贯性,设e为一整数,yi0eyin。若扫描线y=e与多边形P的Pi-1Pi相交,则记其交点的横坐标为xei。 现设xei1,xei2,xei3,xeil 是该扫描线与P的边界各交点横坐标的递增序列,称此序列为交点序列。由区域的连贯性可知,此交点序列具有以下性质:,扫描线的连贯性,1)l是偶数。 2)在该扫描线上,只有区段(xeik,xeik+1),k=1,3,5,l-1位于多边形P内,其余区段都在P外。 以上性质称为扫描线的连贯性,它是多边形区域连贯性在一条扫
10、描线上的反映。,扫描线的连贯性,设d为一整数,并且d=e-1,并且 yi0dyin。设位于扫描线y=d上的交点序列为xdj1,xdj2,xdj3,xdjk 现在来讨论扫描线d,e交点序列之间的关系。若多边形P的边Pr-1Pr与扫描线y=e,y=d都相交,则交点序列中对应元素xer,xdr满足下列关系: xer= xdr + 1/mr (1) 其中mr为边Pr-1Pr的斜率。,边的连贯性,于是,可利用d的交点序列计算e的交点序列,即先运用递推关系式(1)求得与扫描线y=e和y=d都相交的所有多边形上的交点xer,再求得与扫描线y=d不相交但与扫描线y=e相交的所有边PqPq+1上的交点xeq。如
11、果P的顶点的坐标是整数,那么xeq=xq或xeq=xq+1,然后把这两部分按递增的顺序排列,即可得e的交点序列。,边的连贯性,特别是当存在某一个整数k,0kn-1,使得 yike, dyik+1 成立时,则由区域的连贯性可知d的交点序列和e的交点序列之间有以下关系: 1)两序列元素的个数相等,如上图所示。 2)点(xeir,e)与(xdjr,d)位于多边形P的同一边上,于是 xeir= xdjr + 1/kjr (2) 这样,运用递推关系式(2)可直接由d的交点序列获得e的交点序列。 以上性质称为边的连贯性,它是区域的连贯性在相邻两扫描线上的反映。,边的连贯性,当扫描线与多边形P的交点是P的顶
12、点时,则称该交点为奇点。 以上所述多边形的三种形式的连贯性都基于这样的几何事实:每一条扫描线与多边形P的边界的交点个数都是偶数。但是如果把每一奇点简单地计为一个交点或者简单地计为两个交点,都可能出现奇数个交点。那么如何保证交点数为偶数呢?,奇点的处理,若奇点做一个交点处理,则情况A,交点个数不是偶数。 若奇点做两个交点处理,则情况B,交点个数不是偶数。,奇点的处理,多边形P的顶点可分为两类:极值奇点和非极值奇点。如果(yi-1 - yi)(yi+1 - yi)0,则称顶点Pi为极值点;否则称Pi为非极值点。 规定:奇点是极值点时,该点按两个交点计算,否则按一个交点计算。 奇点的预处理:,奇点的
13、处理,数据结构与实现步骤,算法基本思想:首先取d=yin。容易求得扫描线y=d上的交点序列为xdj1,xdj2,xdjn ,这一序列由位于扫描线y=d上的多边形P的顶点组成。 由yin的交点序列开始,根据多边形的边的连贯性,按从上到下的顺序求得各条扫描线的交点序列;根据扫描线的连贯性,可确定各条扫描线上位于多边形P内的区段,并表示成点阵形式。,所有的边和扫描线求交,效率很低。因为一条扫描线往往只和少数几条边相交。 如何判断多边形的一条边与扫描线是否相交? 与当前扫描线相交的边称为活性边(active edge),把它们按与扫描线交点x坐标递增的顺序存入一个链表中,称为活化边表( AEL, Ac
14、tive edge table)。它记录了多边形边沿扫描线的交点序列。 只需对当前扫描线的活动边表作更新,即可得到下一条扫描线的活动边表。,数据结构与实现步骤,如何计算下一条扫描线与边的交点? 直线方程:ax+by+c = 0 当前交点坐标:(xi, yi) 下一交点坐标:(xi+1,yi+1) xi+1= (-byi+1)-c)/a = (-byi+1)-c)/a =xi-b/a 活化边表中需要存放的信息: x:当前扫描线与边的交点 dx-b/a:从当前扫描线到下一条扫描线之间的x增量 ymax:边所交的最高扫描线,数据结构与实现步骤,增加哪一条边呢? 为了方便边的活化链表的更新,建立另一个
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四 光栅 图形 扫描 转换 区域 填充
链接地址:https://www.31doc.com/p-3500316.html