第3章基本图形的生成二.ppt
《第3章基本图形的生成二.ppt》由会员分享,可在线阅读,更多相关《第3章基本图形的生成二.ppt(66页珍藏版)》请在第壹文秘上搜索。
1、2023-11-21第三章 基本图形的生成光栅图形的扫描转换与区域填充扫描转换矩形扫描转换多边形区域填充扫描转换矩形2023-11-22问题:问题:矩形是简单的多边形,那么为什么要单独处理矩形?矩形是简单的多边形,那么为什么要单独处理矩形?比一般多边形可简化计算。应用非常多,窗口系统。共享边界如何处理?共享边界如何处理?原则:左闭右开,下闭上开原则:左闭右开,下闭上开属于谁?扫描转换矩形2023-11-23方法:方法:void FillRectangle(Rectangle*rect,int color)int x,y;for(y=rect-ymin;y ymax;y+)for(x=rect-
2、xmin;x xmax;x+)PutPixel(x,y,color);/*end of FillRectangle()*/扫描转换多边形2023-11-24多边形分为凸多边形、凹多边形、含内环的多边形。扫描转换多边形2023-11-25多边形的表示方法多边形的表示方法顶点表示顶点表示点阵表示点阵表示顶点表示:用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少;不能直接用于面着色。点阵表示:用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息;便于运用帧缓冲存储器表示图形,易于面着色。多边形的扫描转换2023-11-26多边形的扫描转换:多边形的扫描转换:把多边形的顶点表示转
3、换为点阵表示,也就是从多边形的给定边界出发,求出位于其内部的各个象素,并给帧缓冲器内的各个对应元素设置相应的灰度和颜色,通常称这种转换为多边形的扫描转换。几种方法:几种方法:逐点判断法;扫描线算法;边缘填充法;栅栏填充法;边界标志法。2023-11-27逐点判断法void FillPolygonPbyP(Polygon*P,int polygonColor)int x,y;for(y=ymin;y=ymax;y+)for(x=xmin;x e,dyik+1成立时,则由区域的连贯性可知d的交点序列和e的交点序列之间有以下关系:1)两序列元素的个数相等,如上图所示。2)点(xeir,e)与(xdj
4、r,d)位于多边形P的同一边上,于是 xeir=xdjr+1/kjr (2)这样,运用递推关系式(2)可直接由d的交点序列和e的获得e的交点序列。以上性质称为边的连贯性,它是区域的连贯性在相邻两扫描线上的反映。2023-11-226奇点的处理当扫描线与多边形P的交点是P的顶点时,则称该交点为奇点。以上所述多边形的三种形式的连贯性都基于这样的几何事实:每一条扫描线与多边形P的边界的交点个数都是偶数。但是如果把每一奇点简单地计为一个交点或者简单地计为两个交点,都可能出现奇数个交点。那么如果保证交点数为偶数呢?奇点的处理2023-11-227若奇点做一个交点处理,则情况A,交点个数不是偶数。若奇点做
5、两个交点处理,则情况B,交点个数不是偶数。奇点的处理2023-11-228多边形P的顶点可分为两类:极值奇点和非极值奇点。如果(yi-1-yi)(yi+1-yi)0,则称顶点Pi为极值点;否则称Pi为非极值点。规定:奇点是极值点时,该点按两个交点计算,规定:奇点是极值点时,该点按两个交点计算,否则按一个交点计算。否则按一个交点计算。奇点的预处理:数据结构与实现步骤2023-11-229首先取d=yin。容易求得扫描线y=d上的交点序列为xdj1,xdj2,xdjn,这一序列由位于扫描线y=d上的多边形P的顶点组成。由yin的交点序列开始,根据多边形的边的连贯性,按从上到下的顺序求得各条扫描线的
6、交点序列;根据扫描线的连贯性,可确定各条扫描线上位于多边形P内的区段,并表示成点阵形式。2023-11-230数据结构与实现步骤 即算法中采用较灵活的数据结构。它由边的分类表ET(Edge Table)和边的活化链表AEL(Active Edge List)两部分组成。表结构ET和AEL中的基本元素为多边形的边。边的结构由以下四个域组成:ymax 边的上端点的y坐标;x 在ET中表示边的下端点的x坐标,在AEL中则表示边与扫描线的交点的坐标;x 边的斜率的倒数;next 指向下一条边的指针。数据结构与实现步骤2023-11-231边的分类表ET是按边的下端点的y坐标对非水平边进行分类的指针数组
7、。下端点的y坐标的值等于i的边归入第i类。有多少条扫描线,就设多少类。同一类中,各边按x值(x值相等时,按x的值)递增的顺序排列成行。数据结构与实现步骤2023-11-232与当前扫描线相交的边称为活性边(active edge),把它们按与扫描线交点x坐标递增的顺序存入一个链表中,边的活化链表(AEL,Active edge table)。它记录了多边形边沿扫描线的交点序列。例子2023-11-233已知多边形P=(P0P1P2P3P4P5P6P0);其各边坐标分别为(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)建立其边表和边的活化链表例子2023-11-2
8、34边表2023-11-2352023-11-236活动边表的例子y=3Y=8算法实现步骤2023-11-237这样,当建立了边的分类表ET后,扫描线算法可按下列步骤进行:(1)取扫描线纵坐标y的初始值为ET中非空元素的最小序号。(2)将边的活化链表AEL设置为空。(3)按从下到上的顺序对纵坐标值为y的扫描线(当前扫描线)执行下列步骤,直到边的分类表ET和边的活化链表都变成空为止。算法实现步骤2023-11-2381)如边分类表ET中的第y类元素非空,则将属于该类的所有边从ET中取出并插入边的活化链表中。递增方向排序。2)若相对于当前扫描线,边的活化链表AEL非空,则将AEL中的边两两依次配对
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基本 图形 生成