第二章 二维图形生成技术.ppt

第2章 二维图形生成技术 2.1 直线的生成 图2.1 直线和近似表示它的像素集 2.1.1 直接生成法 直接生成法即直接由直线方程计算出(x，y)值，并生成直线。 2.1.1 直接生成法 图2.2所示直线的方程可表示为 式中，m是直线的斜率；b是y方向的截距。 2.1.2 数值微分法 此算法可总结为以下过程：以直线的两个端点(x0，y0)及(x1，y1)作为此过程的输入，由两个方向输入坐标值的差可得参数dx及dy： 此两参数的绝对值哪一个大，就作为步长参数(n)，此参数作为沿直线所画出的点的数目。 2.1.3 中点画线法 图2.3 中点画线算法原理示意图 2.1.3 中点画线法 假设直线的起点和终点分别为 和 ，则直线方程为 ，对于直线上的点满足 ；对于直线上方的点满足 ；对于直线下方的点满足 已知当前已经确定的点为 ，构造判别式： d=f(m)=f(Xp+1,Yp+0.5)=a(Xp+1)+b(Yp+0.5)+c 2.1.3 中点画线法 (1) 若d≥0，取正右方像素P1，再下一个像素的判定，由 d1=f(Xp+2, Yp+0.5)=a(Xp+2)+b(Yp+0.5)+c =a(Xp+1)+b(Yp+0.5)+c+a=d+a；可知d的增量是a (2) 若d＜0，取右上方像素P2，再下一个像 素，由： d2=f(Xp+2,Yp+1.5)=a(Xp+2)+b(Yp+1.5)+c =d+a+b ； 可知d的增量为a+b 2.1.3 中点画线法 下面确定判别式的初始值。 由于已知的第一个确定的直线的扫描点为给定直线的起始点，所以d的初始值可按下式计算： d0 =f(x0+1,y0+0.5) = a(x0+1)+b(y0+0.5)+c = f(x0,y0)+a+0.5b = a+0.5b 由于只用d的符号作判断，为了只包含整数运算，可取2d代替d，2a改写成a+a。 2.1.4 Bresenham画线算法 将直线段与列的交点记为M，P1与P2的中点记为K，选择的标准是：如果交点M在K的下方，那么下一点取P2；如果M在中点K的上方，那么下一点取P1；如果M恰好与K重合，那么下一点可以取P1，也可以取P2，我们约定取P1。 2.1.4 Bresenham画线算法 将M点到y=yi行的距离记为Δi，即Δi =m(xi+1)+b－yi，则选择的标准可以表达为：如果Δi 0.5，说明M在K的下方，那么下一点取P2；如果Δi≥0.5，说明M在K的上方或与K重合，那么下一点取P1。 由于Bresenham算法以P1与P2的中点K作为选择的标准，因此也称为中点算法。 令判别式为 2.1.4 Bresenham画线算法 则有： ① 如果 ，说明 ，新的判别式为 2.1.4 Bresenham画线算法 ② 如果 ≥0，说明 ≥0.5，新的判别式为 2.1.4 Bresenham画线算法 适用于第一象限的Bresenham画线算法可以方便地推广到一般情况：如果m＞1，只需将x和y的位置对调，即以y方向为记数方向；如果Δx＜0或Δy＜0，则只需将x或y的增量变为负数即可。 2.1.5 双步画线算法 Bresenham算法是每次决定一个像素的走法，而双步画线算法是每次决定两个像素的走法，因此效率比Bresenham算法提高了大约一倍。双步画线算法是对中点画线算法的改进。假设线段的起始点为 ，终止点为 ，令dx=x1-x0，dy=y1-y0。首先考虑线段在第一象限的情况，此时dx0，dy≥0，0≤k≤1。如图2.5所示 2.1.5 双步画线算法 图2.5 双步画线算法的四种模式 2.1.5 双步画线算法 当0≤k≤1/2时，初始判别式为d0=4dy-dx，增量算法为： ① 如果di＜0，那么采用模式1，并且di+1=di+4dy； ② 如果di≥0，那么采用模式2或模式3，并且di+1=di+4dy-2dx。进一步的判断为：如果di2dy，那么采用模式2；否则采用模式3。 当1/2≤k≤1时，初始判别式为d0=4dy-3dx，增量算法为： ① 如果di≥0，那么采用模式4，并且di+1=di+4(dy-dx)； ② 如果di＜0，那么采用模式2或模式3，并且di+1=di+4dy-2dx。进一步的判断为：如果di＜2(dy-dx)，那么采用模式2；否则采用模式3。 2.2 圆 的