第3章 二维图元生成技术 计算机图形学.pptVIP

*区域填充(扫描线算法)像素中的序号标指它所在区段位于堆栈中的位置。第62页，共93页，星期日，2025年，2月5日*3.3.2多边形扫描线填充算法利用图形的空间连贯性和扫描线的连贯性第63页，共93页，星期日，2025年，2月5日*扫描线算法(1/7)目标：利用相邻像素之间的连贯性，提高算法效率处理对象：非自交多边形(边与边之间除了顶点外无其它交点)第64页，共93页，星期日，2025年，2月5日*基本原理一条扫描线与多边形的边有偶数个交点步骤(对于每一条扫描线)：(1)求交点(2)交点排序(3)交点配对(4)填充区段。实现多边形扫描线填充算法的关键在于：如何有效地简化交点的计算，如何有效地表示交点和填充区域第65页，共93页，星期日，2025年，2月5日*填充扩大化问题解决方法：取中心扫描线y+0.5检查交点右方像素的中心是否落在区间内xl≤x+0.5≤xr第66页，共93页，星期日，2025年，2月5日*顶点交点的计数问题543210P1P2P3P4I1I2I3I4P5扫描线5扫描线4扫描线3扫描线2扫描线1I5I6检查交于该顶点的两条边的另外两个端点的y值大于该顶点y值的个数计数0次计数1次计数2次第67页，共93页，星期日，2025年，2月5日*边的连贯性为了减少求交的计算量，可利用边的连贯性第一类交点：新出现的边与扫描线的交点(不用计算)第二类交点：位于同一条边上的后继交点第68页，共93页，星期日，2025年，2月5日*活性边表AET活性边表AET(ActiveEdgeTable)节点各项的内容依次是x：当前扫描线与边的交点x坐标Dx:从当前扫描线到下一条扫描线之间的x增量，即边的斜率倒数ymax:活性边对应的最大y坐标。第69页，共93页，星期日，2025年，2月5日3.1.3Bresenham算法已经确定的像素为P(xiyi)，下一个可选择的像素点为P1(xi＋1,yi)和P2(xi＋1,yi＋1))两者中的一个第30页，共93页，星期日，2025年，2月5日3.1.3Bresenham算法在x=xi＋1处直线上点y=k(xi＋1)+b，该点到P1(xi＋1,yi)和P2(xi＋1,yi＋1)的距离分别令为d1和d2：两个距离的差若此差值为正，则d1＞d2，下一个像素点应取P2(xi＋1,yi＋1)；若此差值为负，d1d2,下一个像素点应取P1(xi＋1,yi)；若此差值为零，则dl＝d2，下一个像素点可取两个像素点中的任意一个.第31页，共93页，星期日，2025年，2月5日3.1.3Bresenham算法为了简化d1-d2，考虑到，引入一个新的同正负的判别变量当di≥0时，yi+1=yi+1，当di≤0时，yi+1=yi初始判别量d0第32页，共93页，星期日，2025年，2月5日3.1.3Bresenham算法voidCDrawDemoView::BresenhamLine(intx1,inty1,intx2,inty2){ intiTag=0;intdx,dy,tx,ty,inc1,inc2,d,curx,cury; SetGrid(x1,y1,m_crCurColor); if(x1==x2y1==y2) { return; } dx=abs(x2-x1); dy=abs(y2-y1); if(dxdy){iTag=1;Swap(x1,y1);Swap(x2,y2);Swap(dx,dy);} tx=(x2-x1)0?1:-1;ty=(y2-y1)0?1:-1; curx=x1;cury=y1; inc1=2*dy;inc2=2*(dy-dx);d=inc1-dx; while(curx!=x2) {curx+=tx;if(d0){d+=inc1;} else{cury+=ty;d+=inc2; } if(iTag){SetGrid(cury,curx,m_crCurColor);} else{SetGrid(curx,cury,m_crCurColor);} }}第33页，共93页，星期日，2025年，2月5日*用Bresenham方法扫描转换连接两点P0(20,10)和P1(30