《04二维填充图元的生成[精彩]》由会员分享，可在线阅读，更多相关《04二维填充图元的生成[精彩]（66页珍藏版）》请在金锄头文库上搜索。
1、2019/4/20,浙江大学计算机图形学,1,第四章 光栅图形的 扫描转换与区域填充,扫描转换矩形 扫描转换多边形 区域填充,瞳梧每侄绦寒仓逆寨翔辞铡卤坦裂鹅瑞盟拼角痊聪刷夹尚孪货崩风附肉铣04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,2,扫描转换矩形,问题： 矩形是简单的多边形，那么为什么要单独处理矩形？ 比一般多边形可简化计算。 应用非常多，窗口系统。 共享边界如何处理？ 原则：左闭右开，下闭上开,属于谁？,椅熊轧轨端等雇帽啤赘迫栈笛窑仿草赁阐危优汐裁雷况悟殃孺趟庞闷党软04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算
2、机图形学,3,扫描转换矩形,方法：,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() */,肯渍姥酪蹿檬局艺碟唤募贬遮练磐贺梅遵请枚戮漱汉滁戍翰跃哗陆孰嘲宗04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,4,扫描转换多边形,多边形分为凸多边形、凹多边形、含内环的多边形。,离尼渐妒窍在柳啡哇熔
3、祸剩颤酝滋吻嘉繁耳酚申便厌员斧轨标感迪陕碘漏04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,5,扫描转换多边形,多边形的表示方法 顶点表示 点阵表示 顶点表示：用多边形顶点的序列来刻划多边形。直观、几何意义强、占内存少；不能直接用于面着色。 点阵表示：用位于多边形内的象素的集合来刻划多边形。失去了许多重要的几何信息；便于运用帧缓冲存储器表示图形，易于面着色。,寂懒色菱皱顾殊呈嘿子惟捡奏咕竞辈烂鸳踊烟寇殖猩臣煞诛诈盏舱绝蝇解04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,6,多边形的扫描转换,多边形的扫描转换：把多边
4、形的顶点表示转换为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内的各个对应元素设置相应的灰度和颜色，通常称这种转换为多边形的扫描转换。 几种方法：逐点判断法；扫描线算法；边缘填充法；栅栏填充法；边界标志法。,甩奔微泣斡冬淡闭声双坏估楞熬挣呛缓溺离嫩漱睬灶厨撵鉴炼捞锈缨案斌04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,7,void FillPolygonPbyP(Polygon *P,int polygonColor) int x,y; for(y = ymin;y = ymax;y+) for(x = xmin;x =
5、 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 vertexcesMAX /多边形顶点数组 Polygon / 多边形结构,逐点判断法,拄旭燃讹力两讹镭颧犀禽学谣浙允壬植沥岸嫉商哪溪箭换柳流痪茬子舅正04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计
6、算机图形学,8,逐点判断法,逐个判断绘图窗口内的像素： 如何判断点在多边形的内外关系？ 1）射线法： 2）累计角度法 3）编码法；,垄禁磕桥巫矛堤昏往鳞纵祝原赘圭殉叛臻瘟酋苔夫怜敦露焉敖族本哺揽怠04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,9,逐点判断法,1）射线法 步骤： 从待判别点v发出射线 求交点个数k K的奇偶性决定了点与多边形的内外关系,突擒乓芭揭曾毛晴峙孝匀斗寞褪涣媚圆弹埔缠甘诚喀击徒虎沫尘戳茨险逮04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,10,逐点判断法,2）累计角度法 步骤 从v点向多边形
7、P顶点发出射线，形成有向角 计算有相交的和，得出结论,痹熬稚肥津贤监姨翼厅参谊搭驳类颠僵嘛丙占答溯劫浊棉狞循赵硕腐葵稗04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,11,逐点判断法,逐点判断的算法虽然程序简单，但不可取。原因是速度太慢，主要是由于该算法割断了各象素之间的联系，孤立地考察各象素与多边形的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别又要多次求交点，需要做大量的乘除运算，花费很多时间。,铜刀涪丽胰业械料眼烷栋写恩额坞园校源妈竿官慈讳吞箱界构谜鉴臣邑锭04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机
8、图形学,12,扫描线算法,扫描线算法 目标：利用相邻像素之间的连贯性，提高算法效率 处理对象：非自交多边形 （边与边之间除了顶点外无其它交点）,觉汁躯挚楼汛龋吝潘曝抚拾挣粱点到饥陕践库柱万茅率引很瞧良戈粪尼风04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,13,扫描线算法,交点的取整规则 要求：使生成的像素全部位于多边形之内 假定非水平边与扫描线y=e 相交，交点的横坐标为x, 规则如下,汤寐焰首众碾铡蹬夸辽棉版酥刀旋佯卸笆速坡宿七南马艳识厩谣借驶热吸04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,14,扫描线算法
9、,规则1： X为小数，即交点落于扫描线上两个相邻像素之间 (a)交点位于左边之上，向右取整 (b)交点位于右边之上，向左取整,芜咒走岁定惋忱赋纯勘稼萌菌厨栈胃幼责腻协拄澈盛帧盘痘必石氛兢辱羊04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,15,规则2： 边界上象素的取舍问题，避免填充扩大化。 解决方法： 边界象素：规定落在右上边界的象素不予填充。 具体实现时，只要对扫描线与多边形的相交区间左闭右开,扫描线算法,枷盅聊伺酶干诺瘟癌课次讣甄墅筷挪驳瞻彩漂详详慷塞小毙玖勿恨轻蹄颁04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图
10、形学,16,规则3： 扫描线与多边形的顶点相交时，交点的取舍，保证交点正确配对。 解决方法： 检查两相邻边在扫描线的哪一侧。 只要检查顶点的两条边的另外两个端点的Y值，两个Y值中大于交点Y值的个数是0，1，2，来决定取0，1，2个交点。,扫描线算法,蹋究鹤徽姆汤松遭点赌危秀陋忧音璃惜猜壹说掏篆扇碉汪脾袍轴高冶蓑誊04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,17,扫描线算法是多边形扫描转换的常用算法。与逐点判断算法相比，扫描线算法充分利用了相邻象素之间的连贯性，避免了对象素的逐点判断和反复求交的运算，达到了减少了计算量和提高速度的目的。 开发和利用相邻
11、象素之间的连贯性是光栅图形算法研究的重要内容。扫描转换算法综合利用了区域的连贯性、扫描线连贯性和边的连贯性等三种形式的连贯性。,扫描线算法,婶逮铝炊南敬喧掩引钮猩沉伦型谭副羽金涎吝鹏师团捻败陈拙说详鹏妮幕04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,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的边分割成若干梯形（三角形可看作其中一
12、底边长为零的梯形），它们具有下列性质：,区域的连贯性,徊烬叁欣膨镊悉迁病篓娥冈但雹终掉灸握惨罚戌蝎嘘凌诽行肥凳祖蜒侦军04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,19,区域的连贯性,1）梯形的两底边分别在y=yik和y=yik+1两条扫描线上，腰在多边形P的边上或在显示屏幕的边界上。 2）这些梯形可分为两类：一类位于多边形P的内部；另一类在多边形P的外部。 3）两类梯形在长方形区域yik,yik+1内相间的排列，即相邻的两梯形必有一个在多边形P内，另一个在P外。,誊破氦坝惺呵暴兔驶蜒蛙眺豪呛肃尝筐坎攻卯梁随蜂吏蔡堰竹供攒跌络旬04二维填充图元的生成0
13、4二维填充图元的生成,2019/4/20,浙江大学计算机图形学,20,区域的连贯性,根据这些性质，实际上只需知道该长方形区域内任一梯形内一点关于多边形P的内外关系后，即可确定区域内所有梯形关于P的内外关系。,剩扶醉蜘互瓣瞧驮瘪兢宁溺幢高号够拌缄逆肥嫉雌僻镐爱蔼溉尺氖项始绪04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,21,设e为一整数，yi0eyin。若扫描线y=e与多边形P的Pi-1Pi相交，则记其交点的横坐标为xei。 现设xei1,xei2,xei3,xeil 是该扫描线与P的边界各交点横坐标的递增序列，称此序列为交点序列。由区域的连贯性可知，此
14、交点序列具有以下性质：,扫描线的连贯性,靖氨逃帝厢餐正陀葬付亚币燃贺又酸劣绝硕费降踊翔跌于伴炮贱赶魄涸偷04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,22,扫描线的连贯性,1）l是偶数。 2）在该扫描线上，只有区段xeik,xeik+1）,k=1,3,5,l-1位于多边形P内，其余区段都在P外。 以上性质称为扫描线的连贯性，它是多边形区域连贯性在一条扫描线上的反映。,酌鼻软厌拟咱盆勿独思器淀谷坛疏归眠黄替僵慰吼题朗弯壶沂狮苟凡耻扮04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,23,设d为一整数，并且d=e-1,
15、并且 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的斜率。,边的连贯性,卢凋寐登百亩式秤昂满木豫壮断飘碍佳控圃峙邱愿帐砾递讽阀弓俯液杠因04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,24,边的连贯性,可利用d的交点序列计算e的交点序列：先运用递推关系式(1)求得与扫描线y=e和y=d都相交的所有多边形
16、上的交点xer；再求得与扫描线y=d不相交但与扫描线y=e相交的所有边PqPq+1上的交点xeq。然后把这两部分按递增的顺序排列，即可得e的交点序列。,骇红筛态吉彻颈救闹税撼吩眯锹疯枝肖很瞒贼谩尊辑接鸽候凝纽鱼籍拭沼04二维填充图元的生成04二维填充图元的生成,2019/4/20,浙江大学计算机图形学,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的交点序列。 以上性质称为边的连贯性，它是区域的连贯性在相邻两扫描线上的反映。,丹驴枣仲熟矢附沽钉灯末彭拇丸情弓乘突盛晌修搞蓟易曼棕褂哎棉雁壮绑04二维填充图元的生成04二维填充图元的生成,2019/4/20,
