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