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

* 改进算法，减少递归次数，提高效率。 方法之一使用扫描线填充算法； * 2)区域填充(扫描线算法) 扫描线算法 目标：减少递归层次 适用于内点表示的4连通区域 基本过程： 当给定种子点时，首先填充种子点所在的扫描线上的位于给定区域的一个区段，然后确定与这一区段相通的上下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。 * 区域填充(扫描线算法) 像素中的序号标指它所在区段位于堆栈中的位置。 * 3.3.2 多边形扫描线填充算法 利用图形的空间连贯性和扫描线的连贯性 * 扫描线算法(1/7) 目标：利用相邻像素之间的连贯性，提高算法效率 处理对象：非自交多边形 (边与边之间除了顶点外无其它交点) * 基本原理 一条扫描线与多边形的边有偶数个交点 步骤 (对于每一条扫描线)： (1) 求交点 (2) 交点排序 (3) 交点配对 (4) 填充区段。 实现多边形扫描线填充算法的关键在于： 如何有效地简化交点的计算，如何有效地表示交点和填充区域 * 填充扩大化问题 解决方法： 取中心扫描线y+0.5 检查交点右方像素的中心是否落在区间内 xl≤x+0.5≤xr * 顶点交点的计数问题 5 4 3 2 1 0 P1 P2 P3 P4 I1 I2 I3 I4 P5 扫描线5 扫描线4 扫描线3 扫描线2 扫描线1 I5 I6 检查交于该顶点的两条边的另外两个端点的y值大于该顶点y值的个数 计数0次 计数1次 计数2次 * 边的连贯性 为了减少求交的计算量，可利用边的连贯性 第一类交点：新出现的边与扫描线的交点(不用计算) 第二类交点：位于同一条边上的后继交点 * 活性边表AET 活性边表AET(Active Edge Table)节点各项的内容依次是 x： 当前扫描线与边的交点x坐标 D x: 从当前扫描线到下一条扫描线之间 的x增量，即边的斜率倒数 ymax: 活性边对应的最大y坐标。 * 按扫描线号从小到大的顺序为每一条扫描线建立一个新边表，存放在该扫描线第一次相交的边。若一条边的较低端点为ymin，则该边就放在扫描线ymin 的新边表中 * while(yy1) { if(d0) { y++;x+=ystp;d+=dt2; }else { y++; d+=dt1; } SetGrid(x,y,m_crCurColor); } } * * 中点画线法 例：用中点画线法P0(0,0) P1(5,2) a=y0-y1=-2 b=x1-x0=5 d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6 d3= 2a=-4 d4= 2(a+b)=6 i xi yi d 1 0 0 1 2 1 0 -3(1-4) 3 2 1 3(-3+6) 4 3 1 -1(3-4) 5 4 2 5(-1+6) 0 1 2 3 4 5 3 2 1 3.1.3 Bresenham算法 已经确定的像素为P(xi yi)，下一个可选择的像素点为P1(xi＋1, yi)和P2(xi＋1, yi＋1) )两者中的一个 3.1.3 Bresenham算法 在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)；若此差值为零，则d l＝d2，下一个像素点可取两个像素点中的任意一个. 3.1.3 Bresenham算法 为了简化d1-d2，考虑到 ， 引入一个新的同正负的判别变量 当di≥0时，yi+1=yi+1， 当di≤0时，yi+1=yi 初始判别量d0 3.1.3 Bresenham算法 void CDrawDemoView::BresenhamLine(int x1, int y1, int x2, int y2) { int iTag=0; int dx,dy,tx,ty,inc1,inc2,d,curx,cury; SetGrid(x1,y1, m_crC