gjlchp二维填充图元的生成课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《gjlchp二维填充图元的生成课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- gjlchp 二维 填充 生成 课件
- 资源描述:
-
1、2022-6-9浙江大学计算机图形学1扫描转换矩形n问题:问题:n矩形是简单的多边形,那么为什么要单独处矩形是简单的多边形,那么为什么要单独处理矩形?理矩形?比一般多边形可简化计算。应用非常多,窗口系统。n共享边界如何处理?共享边界如何处理?n原则:左闭右开,下闭上开原则:左闭右开,下闭上开属于谁?2022-6-9浙江大学计算机图形学2扫描转换矩形n方法:方法:void FillRectangle(Rectangle *rect,int color) int x,y; for(y = rect-ymin;y ymax;y+) for(x = rect-xmin;x xmax;x+) PutPi
2、xel(x,y,color);/*end of FillRectangle() */2022-6-9浙江大学计算机图形学3扫描转换多边形n多边形分为凸多边形、凹多边形、含内环的多边形。2022-6-9浙江大学计算机图形学4扫描转换多边形n多边形的表示方法多边形的表示方法n顶点表示顶点表示n点阵表示点阵表示n顶点表示:用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少;不能直接用于面着色。n点阵表示:用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息;便于运用帧缓冲存储器表示图形,易于面着色。2022-6-9浙江大学计算机图形学5多边形的扫描转换n多边形的扫描转换:多边形的
3、扫描转换:把多边形的顶点表示转换为点阵表示,也就是从多边形的给定边界出发,求出位于其内部的各个象素,并给帧缓冲器内的各个对应元素设置相应的灰度和颜色,通常称这种转换为多边形的扫描转换。n几种方法:几种方法:逐点判断法;扫描线算法;边缘填充法;栅栏填充法;边界标志法。2022-6-9浙江大学计算机图形学6void FillPolygonPbyP(Polygon *P,int polygonColor) int x,y; for(y = ymin;y = ymax;y+) for(x = xmin;x e, dyik+1成立时,则由区域的连贯性可知d的交点序列和e的交点序列之间有以下关系: 1)两
4、序列元素的个数相等,如上图所示。 2)点(xeir,e)与(xdjr,d)位于多边形P的同一边上,于是 xeir= xdjr + 1/kjr (2)这样,运用递推关系式(2)可直接由d的交点序列和e的获得e的交点序列。以上性质称为边的连贯性,它是区域的连贯性在相邻两扫描线上的反映。2022-6-9浙江大学计算机图形学25当扫描线与多边形P的交点是P的顶点时,则称该交点为奇点。以上所述多边形的三种形式的连贯性都基于这样的几何事实:每一条扫描线与多边形P的边界的交点个数都是偶数。但是如果把每一奇点简单地计为一个交点或者简单地计为两个交点,都可能出现奇数个交点。那么如果保证交点数为偶数呢?奇点的处理
5、2022-6-9浙江大学计算机图形学26奇点的处理n若奇点做一个交点处理,则情况A,交点个数不是偶数。n若奇点做两个交点处理,则情况B,交点个数不是偶数。2022-6-9浙江大学计算机图形学27奇点的处理n多边形P的顶点可分为两类:极值奇点和非极值奇点。如果(yi-1 - yi)(yi+1 - yi)0,则称顶点Pi为极值点;否则称Pi为非极值点。n规定:奇点是极值点时,该点按两个交点计算,规定:奇点是极值点时,该点按两个交点计算,否则按一个交点计算。否则按一个交点计算。n奇点的预处理:2022-6-9浙江大学计算机图形学28数据结构与实现步骤首先取d=yin。容易求得扫描线y=d上的交点序列
6、为xdj1,xdj2,xdjn ,这一序列由位于扫描线y=d上的多边形P的顶点组成。 由yin的交点序列开始,根据多边形的边的连贯性,按从上到下的顺序求得各条扫描线的交点序列;根据扫描线的连贯性,可确定各条扫描线上位于多边形P内的区段,并表示成点阵形式。2022-6-9浙江大学计算机图形学29 即算法中采用较灵活的数据结构。它由边的分类表ET(Edge Table)和边的活化链表AEL(Active Edge List)两部分组成。 表结构ET和AEL中的基本元素为多边形的边。边的结构由以下四个域组成: ymax 边的上端点的y坐标; x 在ET中表示边的下端点的x坐标,在AEL中则表示边与扫
7、描线的交点的坐标; x 边的斜率的倒数; next 指向下一条边的指针。 数据结构与实现步骤2022-6-9浙江大学计算机图形学30数据结构与实现步骤边的分类表ET是按边的下端点的y坐标对非水平边进行分类的指针数组。下端点的y坐标的值等于i的边归入第i类。有多少条扫描线,就设多少类。同一类中,各边按x值(x值相等时,按x的值)递增的顺序排列成行。 2022-6-9浙江大学计算机图形学31数据结构与实现步骤与当前扫描线相交的边称为活性边(active edge),把它们按与扫描线交点x坐标递增的顺序存入一个链表中,边的活化链表 ( AEL, Active edge table)。它记录了多边形边
8、沿扫描线的交点序列。2022-6-9浙江大学计算机图形学32例子n已知多边形P=(P0P1P2P3P4P5P6P0);其各边坐标分别为n(2,5)(2,10)(9,6)(16,11)(16,4)(12,2)(7,2)n建立其边表和边的活化链表2022-6-9浙江大学计算机图形学33例子2022-6-9浙江大学计算机图形学34边表2022-6-9浙江大学计算机图形学35y=3Y=8活动边表的例子2022-6-9浙江大学计算机图形学36算法实现步骤这样,当建立了边的分类表ET后,扫描线算法可按下列步骤进行: (1)取扫描线纵坐标y的初始值为ET中非空元素的最小序号。 (2)将边的活化链表AEL设置
9、为空。 (3)按从下到上的顺序对纵坐标值为y的扫描线(当前扫描线)执行下列步骤,直到边的分类表ET和边的活化链表都变成空为止。 2022-6-9浙江大学计算机图形学37算法实现步骤1)如边分类表ET中的第y类元素非空,则将属于该类的所有边从ET中取出并插入边的活化链表中。递增方向排序。2)若相对于当前扫描线,边的活化链表AEL非空,则将AEL中的边两两依次配对,依此类推。并填色。3)将边的活化链表AEL中满足y=ymax的边删去。4)x:=x+x。5)y:=y+1。2022-6-9浙江大学计算机图形学38扫描线算法n特点:算法效率比逐点填充法高很多。n缺点:对各种表的维持和排序开销太大,适合软
10、件实现而不适合硬件实现。2022-6-9浙江大学计算机图形学39扫描线算法问题:如何处理多边形的水平边?如何修改扫描线算法,使它能处理边自交的多边形?有孔的多边形如何处理?如何处理圆、椭圆的扫描线算法?2022-6-9浙江大学计算机图形学40边缘填充算法求余运算求余运算:假定A为一个正整数,则M的余定义为A M, 记为 。计算机中取A为n位能表示的最大整数。即,A=0 xFFFFFFFFA=0 xFFFFFFFF由来由来:光栅图形中,如果某区域已着上值为M的颜色值做偶数次求余运算,该区域颜色不变;而做奇数次求余运算,则该区域颜色变为值为 的颜色。这一规律应用于多边形扫描转换,就为边缘填充算法。
展开阅读全文