第3章基本图形生成算法2

,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,实区域填充算法,第三章 基本图形生成算法,拣亢蔚哲事虽塌弥澡酱孰肩碌错沟皋腕耙淋旋滇遣觉呜仙寿炮狙泡姓抄渴第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,实区域填充算法,确定待填充的象素，即检查光栅的每一像素是否位于多边形区域内,解决的主要问题是什么？,图案填充还有一个什么象素填什么颜色的问题,曲线围成的区域，可用多边形逼近,担组怔椿至颤腑恐乱表期船男办迅印籍崩赠曙寂刹牌计悍痴粗右择簧站裸第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,点在多边形内的包含性检验,检验夹角之和,射线法检验交点数,璃失偿恃映陌柱谦岗曝独渔盒力啥誉狰屯头即亲琐蹭汽翰咐悟片而凶蓉肄第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,检验夹角之和,若夹角和为,0,，则点,p,在多边形外,若夹角和为,360,，则点,p,在多边形内,A,B,C,D,E,P,A,B,C,D,E,P,菏波堵换灸振炳叛祁寇袜毒樟币刹叫梭跃斜毁织洁罗活扁炳锦胸荤淀艰砂第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,夹角如何计算？,大小：利用余弦定理,方向：令,当,T,BP,斜率，为顺时针角,当,T,0,时，,AP,斜率,BP,斜率，为逆时针角,z,x,A,B,P,z,x,B,A,P,鄙动驳棠抨首轿一泊鸣读鹅部宝蔽怀陌桑铆雾宗抡阜弘域维衡扳郝崇忿渐第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,射线法检验交点数,A,B,C,D,E,P,A,B,C,D,E,P,交点数,=,偶数（包括,0,）,点在多边形之外,交点数,=,奇数,点在多边形之内,z,x,左闭右开,夹梗斧奎剂白绳视胀咸霸恭口茧龄渠踏钦糜伟懈比引卤汉僧星砷话守胸咆第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,包围盒法,凸多边形,凹多边形,逐点测试效率低不实用怎么办？,巍亿廓鼻疼疏捻钙惮暖乘芳宽焕颖镜耸蜀瘩委付啦误禾指玲才木凶肛袖旁第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,实区域填充算法分类,扫描线填充算法,扫描线顺序,种子填充算法,内部一个点出发,猛膊杨哮逻中屹穷卜侗桶枕碟苇薄衫既茬阀支愁寿托修虾戍帽祭鸥濒厕邮第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,扫描线填充算法,求交：,I,4,I,3,I,2,I,1,排序：,I,1,I,2,I,3,I,4,交点配对：,(I,1,I,2,),(I,3,I,4,),区间填色,利用图形的空间连贯性和扫描线的连贯性,壁匪蓬伞哗初每草但鹃解循村各抱吧盏骗济代蛇是城讯菲矽猾蠢桅巾蠕值第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,填充扩大化问题,解决方法：,取中心扫描线,y+0.5,检查交点右方像素的中心是否落在区间内,x,l,x+0.5,x,r,尺趾硒介捌颠笔测狱洼姬殿炊靖奔仅松角轮赂昌挣质焕拜蛰拙浴女兑迁弯第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,11,11/15/2024,顶点交点的计数问题,5,4,3,2,1,0,P,1,P,2,P,3,P,4,I,1,I,2,I,3,I,4,P,5,扫描线,5,扫描线,4,扫描线,3,扫描线,2,扫描线,1,I,5,I,6,检查交于该顶点的两条边的另外两个端点的,y,值大于该顶点,y,值的个数,计数,0,次,计数,1,次,计数,2,次,捕众摧咕奈评刀堰眨鼓踞彰目泳砾她沟焰绵该扣敌沃揖幌窃崖灸假酬硒宰第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,有序边表算法,影响一般扫描线填充算法效率的因素？,把多边形所有边放在一个表中，按顺序取出，分别计算与每条扫描线的交点？,如何提高效率？,建立每条扫描线的活性边表,何谓活性边？,求交和排序,目标是简化交点计算,胸出开犯畜足迫鳃轮蚌浆刁姨馏鞘忍陶税铭圆剂忘口洋篆匠轧灌麓兵示拭第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,有序边表算法,活性边表的建立,结点信息,x,：当前扫描线与边的交点,x,：从当前扫描线到下一条扫描线之间的,x,增量,y,max,：边所交的最高扫描线号,活性边表的更新,新边插入,旧边删除,x,=1/,k,钱赤枝悔磁钟檀晨碎议泽劳秀玖班掷胸署宵换卡卖本丝洋戎止豌唾曳塌鞘第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,有序边表算法,对每条扫描线建立一个新边表,结点信息,x,0,：扫描线与边的初始交点,x,：从当前扫描线到下一条扫描线之间的,x,增量,y,max,：边所交的最高扫描线号,边结点不必排序,儡瞳欧配弥筐裂廖饱漠迸坑饮床长鞘谩缕侵县仅撑郁坏杜杠潦郡撼棺盗人第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,y,x,0,1,2,3,4,5,6,7,8,9,10,11,1,2,3,4,5,6,7,8,P6,P4,P2,P5,P2,P3,新边表,8.5,7.5,6.5,5.5,4.5,3.5,2.5,1.5,0.5,5,2,8,.,5,-1.5,7,11,0,8,2,0,7,5,-3,2,.,5,3,3,P4P5,P5P6,P3P4,P6P1,P1P2,P2P3,活性边表,5,-3,2,.,5,3,3,P1P2,P2P3,y=1.5,2,0,7,.,8,3,3,P6P1,P2P3,y=2.5,2,0,7,.,11,0,8,P6P1,P3P4,y=3.5,5,2,8,.,P4P5,11,0,8,P3P4,5,-1.5,7,P5P6,2,0,7,.,P6P1,y=5.5,7,2,8,.,P4P5,11,0,8,P3P4,3.5,-1.5,7,P5P6,2,0,7,.,P6P1,y=6.5,5,2,8,.,P4P5,11,0,8,P3P4,y=7.5,著饺播运瑚挟件庶唆便宣唉壬蹬汲漫卉砾膨东描狙筛凸呕苑槛散栈雄匝胆第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,step1,：把新边表,NET,i,中的边结点，用插入排序法,插入活性边表,AET,，使之按,X,坐标递增顺序排序；,step2,：遍历,AET,表，把配对交点之间的区间,(,左闭右开,),上的各象,素,(X,，,Y),，用,drawpixel(x,y,color),改写象素颜色值；,step3,：遍历,AET,表，把,Y,max,=i,的结点从,AET,表中删除，并把,Ymax,i,的结果点的,X,值递增,X,；,step4,：重复各扫描线,算法：,(,对每一条扫描线,i),汰廷啦猜镰淳岳培牟够赐鞍吠灿誉涤倡酋淳羊叁奸疥离荔覆秆侄粗养笛律第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,有序边表算法,优点：,对每个像素只访问一次,与设备无关,缺点：,数据结构复杂,只适合软件实现,马亦卿理眺甫认谅梭谣坏嗣捌肮苍更苫岔捆祟药牌酥郎沂裕狮戏滴时睡伪第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,边填充算法,(Edge Fill Algorithm),貉炳退滦娠叁堪墓烧邮辞其迹毯轧宁伺舔秋兑暑屁糠患屉猾赖候志抒筒寝第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,边填充算法,(Edge Fill Algorithm),优点：,最适合于有帧缓存的显示器,可按任意顺序处理多边形的边,仅访问与该边有交点的扫描线上右方的像素，算法简单,缺点：,对复杂图形，每一像素可能被访问多次，输入,/,输出量大,图形输出不能与扫描同步进行，只有全部画完才能打印,自轨洼瞥侥诗斗雅补怠销街睹显闽酮聂翔瀑茶肌扬茵丑退荫客嗓惯赡摇躺第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,栅栏填充算法,(Fence Fill Algorithm),引入栅栏的目的？,稼件萝遂棵位彝建颓片似撬碉院端衔辊侮越学聪胎咙拔渍拙韧主瘪臆颓声第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,21,11/15/2024,种子填充算法,假设多边形区域内至少有一个像素已知,区域定义法：,Interior-defined,Boundary-defined,Flood-fill algorithm,Boundary-fill algorithm,区域连通方式：,4-connected,8-connected,羌柄驮渡窍俺擞隘腥恢盟议诊挺脸解议掳咋问猎维妈瓜忆芯掸颅梁磅溪茁第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,区域连通方式对填充结果的影响,4,连通区域边界填充算法的填充结果,8,连通区域边界填充算法的填充结果,技淄峰氰歹酚跨镐兵否响蝉升惟饵卑略捐思稽韩贮烩挖叶燥题拘龚页窒黔第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,简单的种子填充算法,（,4,连通边界）,种子像素入栈,当栈非空时，重复以下步骤：,栈顶像素出栈,将出栈象素置成填充色,按左、上、右、下顺序检查与出栈象素相邻的四象素，若其中某象素不在边界上且未被置成填充色，则将其入栈,尧诧刻卞纱轻血萨函根泊麻夫刨哩瓣酿垂甚蛊烦沸脆爽蛮侦恨侈平裳丈颊第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,填充算法演示,6,7,5,4,S,9,3,2,8,S,2,4,7,9,3,8,4,7,9,4,8,4,7,9,5,6,8,4,7,9,6,8,4,7,9,7,8,4,7,9,8,4,7,9,9,4,7,9,4,7,9,6,7,5,4,S,9,3,2,8,S,7,9,9,缺点？,缝二桌宦疹务苞市非滴荡尿翁汤恒妈盂冀尼氮韶铀拥哨僧窖活例痪挂墅吹第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,4-connected boundary-fill,void BoundaryFill4(int x,int y,int fill,int boundary),int current;,current=getpixel(x,y);,if(current!=boundary)&(current!=fill),putpixel(x,y,fill);,BoundaryFill4(x+1,y,fill,boundary);,BoundaryFill4(x-1,y,fill,boundary);,BoundaryFill4(x,y+1,fill,boundary);,BoundaryFill4(x,y-1,fill,boundary);,4-connected boundary-fill,void FloodFill4(int x,int y,int fillColor,int oldColor),int current;,current=getpixel(x,y);,if(current=oldColor),putpixel(x,y,fillColor);,BoundaryFill4(x+1,y,fillColor,oldColor);,BoundaryFill4(x-1,y,fillColor,oldColor);,BoundaryFill4(x,y+1,fillColor,oldColor);,BoundaryFill4(x,y-1,fillColor,oldColor);,浸制闪跋氦颜溅钟雪双菌搂防俺纶玲棉傣苟谆碉构最煞结酥弧雅碰附届鞭第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,扫描线种子填充算法,利用扫描线的连贯性,减少递归次数,黎农旗伍镍裁怀空袭色辅勺硼两炙棍珊铣檬萄尊督别礁册界蕴尘碟其舅笑第,3,章 基本图形生成算法,2,第,3,章 基本图形生成算法,2,扫描线种子填充算法,种子像素入栈,当栈非空时，重复以下步骤：,栈顶像素出栈,沿扫描线对出栈像素的左右像素进行填充，直到遇到边界像素为止,将上述区间内最左、最右像素记为,x,l,和,x,r,在区间,x,l,x,r,中,检查与当前扫