CG02图形基础算法.ppt

第二章图形算法基础,DDA画线算法,是用舍入的方法获得离直线最近的点。舍入就是我们常用的四舍五入，在程序中实现四舍五入的方法是将值加0.5然后取整。 由于在求线上的点的时候用的是数值微分的方法。因而此方法也称为数值微分法(DDA,digital differential analyzer)方法,用上式可求出图2-1中直线PsPe上红色的各点,但显示时用像素(图中的黑点)表示,用舍入的方法找到靠近红点的像素。 舍入就是我们常用的四舍五入，在程序中实现四舍五入的方法是将值加0.5然后取整。 也可以使用直线的斜截式方程：y=mx+b来求出y值。但是使用这种方法的效率比较低。,算法原理,设有一直线，其两端点为P(xs,ys)、P(xe,ye) 令：x=xe-xs, y=ye-ys,则要会制的直线的微分 方程为：,t=max(|x|,|y|) 取步长为:1/t,则可得到递 推公式2-3:,xi+1=xi+ x /t yi+1=yi+ y /t,Bresenham画线算法是一种精确而有效的光栅线段生成算法，它可用于圆和其他曲线显示的整数增量运算,Bresenham画线算法,算法原理,选择表示直线的最佳像素的位置，即用最靠近直线的网格点来代表这一直线。根据直线的斜率确定或选择变量x或y每次递增一个单位，另一个变量y或x每次增量为0或1，这取决于理论直线段与最近像素点的距离。避免了低效率的取整运算。,设直线段的斜率m0,1（即倾角45）其中m=y/x，则要生成的直线的微分方程为：,令xi为像素所在点的横坐标，是一个整数，则由 yi+1=yi+m(xi+1-xi) 因为xi+1-xi=1则得到： yi+1=yi+m 由于m不一定是整数，所以求出的yi+1也不一定是整数。令： (xi+1)=yi+1-yir-0.5 得到：,Yir+1 (xi+1)0,Yir (xi+1)0,Yi+1,r=,中点画线法,基本原理,如果直线在x方向上增加一个单位，则在y方向上的增量只能在0和1之间。假设x坐标为xk的各象素点中，与直线最近者已经确定，为(xk,yk),用黑色的小圆点表示。那么，下一个与直线最近的象素只能是正右方的Pu(xk+1,ykr)或者右下方的Pb(xk+1,ykr-1)两者之一，用红色小圆点表示。用M表示Pu与Pb的中点，M=(xk +1,ykr +0.5)。而Q是直线与x=xk+1的理想交点。显然，若M在Q的下方则Pu离直线近，就取其为下一个象素。,Pk(xk，ykr),Pu,Pb,M,Q,具体实现： 设有直线，起点和终点分别为（xs,ys）,(xe,ye)，斜率m0,1，两点式直线方程为： (y-y1)/(y2-y1)=(x-x1)/(x2-x1) 整理成标准形式： F(x,y)=ax+by+c=0 得： a=xe-xs,b=ye-ys,c=xsye xe ys 对于直线上的点，F(x,y)=0; 对于直线上方的点F(x,y)0; 对于直线下方的点F(x,y)0,欲判断Q是否在M的上方还是下方，只要把M的坐标代入F(x,y),并判断它的符号。构造判别式： d=F(x,y)=F(xk +1,ykr +0.5)+c 如果d0取正右方的点 如果d0取右上方的点,思考题：,一、将中点画线算法推广以便能画出任意斜率的直线。 二、试设计端点为浮点数坐标的Bresenham画直线算法,画圆弧算法,一、一般方法： 1.直角坐标法： 设圆心为坐标原点，半径为r，则该圆的直角坐标方程为 x2+y2=r2 沿X轴从-r到r的单位步长计算的y值来得到圆周上生一点的位置，即,2.极坐标法： 圆的极坐标方程为： x=cos y=sin 为p(x,y)处的半径与x轴的夹角，此法解决了直角坐标法中所画直线相邻两像素间距不一致性总问题。但计量仍然很大。 3.折线逼近法： 我们也可以用圆的内接正多边形来逼近，每段线段越短，圆弧逼近越好，但其执行时间也越长，所以当对圆的精度要求很高的时候，这种方法就不能满足要求了。,利用圆的对称性，只要能生成8分圆，那么贺的其他部分可得用一个反射 变换得到。这种算法存在着计算量大，和两个相邻像素位置的间距不一致的缺点。,中点画线法：,Pk(xk,yk) Pu(xk+1,yk),M,设圆的中心在坐标原点、半径为r，第二个1/8分圆部分。 顺时针确定离该理想圆最近的像素的序列。 已知横坐标为xk的像素中与该圆的最近者已经确定为Pk(xk,yk) 则下一个点只能是直线x=xk+1的 Pu(xk+1,yk) 或Pu(xk+1,yk-1) 现构造函数：f(x,y)=x2+y2-r2 中点M=(xk+1,yk-0.5) 令：dk=f(M)=(xk+1)2+(yk-0.5)2-r2 0 M点在圆外，取Pb f(M)= 0 M点在圆内，取Pu,Pb(xk+1,yk-1),Bresenham生成圆弧算法,R,Rs,Pi-1(xi-1,yi-1) Hi(xi,yi-1),Li(xi,yi-1-1),S,S,我们仍讨论第二个1/8圆。设有半径为R圆心在坐标原点。 AB为第二个1/8圆的圆弧，圆的方程为： x2+y2=R2 Pi-1(xi-1,yi-1)是已选中的点，则下一个点应在Hi(xi,yi-1)和Li(xi,yi-1-1)选取。 设有圆弧S满足： xHi2+yHi2-Rs2+ xLi2+yLi2-Rs2=0 2-18 当AB在S的上方时取Hi点作为下一点，否则取Li点为下一点。 令：F(P)=(x2+y2)-R2,di=F(Hi)+F(Li) 所以：di= xi2+yi-12-R2+ xi2+（yi-1-1）2-R2 可知： diRs。 di0 AB在S下方，当RRs,A,B,Q,1。我们讨论的生成圆的算法是1/8圆的。试说明怎样才能 绘出整个圆。 2。如果圆心不在原点，试说明生成圆的算法。 3。完成中点画圆法和Bresenham画圆法的递推公式。,椭圆的画法,考虑到椭圆的对称性，只要绘制1/4椭圆的中点就可绘出整个椭圆。,(x,y),(-x,y),(-x,-y),(x,-y),算法原理,圆心在原点、长半轴为a、短半轴为b的椭圆方程的隐函数表达式为：,椭圆将平面划分成三个区域：对于椭圆上的点，F(x，y)0；对于椭圆外的点，F（x，y）0；对于椭圆内的点，F（x，y）0。,在处理第一象限的1/4椭圆弧时，进一步以法矢量两个分量相等的点把它分为两部分，上半部分和下半部分。该椭圆上一点P（x，y）处的法矢量为：,在图示的部分的AC椭圆弧段，法矢量的x向分量小于y向分量，斜率k处处满足|k|1，|x|y|，所以x方向为主位移方向；在C点，法矢量的x向分量等于y向分量，斜率k满足k1，|x|y|；在部分的CB椭圆弧段，法矢量x向分量大于y向分量，斜率k处处满足|k|1，|y|x|，所以y方向为主位移方向。,A（0，b）,B（a，0）,y向分量,法矢量,x向分量,C( , ),椭圆的中点Bresenham算法的原理：在部分：每次在主位移x方向上走一步，y方向上退不退步取决于中点偏差判别式的值；在部分：每次在主位移方向y上退一步，x方向上走不走步取决于中点偏差判别式的值。,A（0，b）,B（a，0）,P,Pu,Pd,P,Pl,Pr,图3-12椭圆中点Bresenham算法原理,构造上半部分中点偏差判别式,在上半部分，x方向每次加1，y方向上减不减1取决于中点偏差判别式的值。从P（xi，yi）走第一步，为了选取下一像素点的，需将Pu（x i1，y i）和Pd（x i1，yi1）的中点M（x i1，y i0.5）代入隐函数，构造中点偏差判别式：,（3-16）,当d10时，中点M在椭圆外，下一像素点应点亮Pd，即y方向退一步；当d0时，中点M在椭圆上，Pu、Pd和椭圆的距离相等，点亮Pu或Pd均可，约定取Pd，如图3-13所示。,x,y,P（xi，yi）,Pu（x i1，y i）,M（x i+1，y i-0.5）,Pd（x i1，yi1）,图3-13 上半部分像素点的选取,因此，,（3-17）,上半部分的递推公式,P（xi，yi ),M（x i1，y i0.5）,M（x i2，y i0.5）,P（xi，yi）,M（x i1，y i0.5）,M（x i2，y i1.5）,d10,d10,图3-14 上半部分中点偏差判别式的递推,1.中点偏差判别式的递推公式 现在如果考虑主位移方向再走一步，应该选取哪个中点代入,图3-13中，为了能够继续判断椭圆上的每个点，需要给出中点偏差判别式d1的递推公式和初始值。,（3-18）,当d10时，下一步的中点坐标为：M（x i2，y i1.5）。所以下一步中点偏差判别式为：,（3-19）,中点偏差判别式以决定应该点亮的像素，如图3-14所示，分两种情况讨论。 当d10时，下一步的中点坐标为：M（x i2，y i-0.5）。所以下一步中点偏差判别式为：,2.中点偏差判别式d1的初值 上半部分椭圆的起点为A（0，b），因此，第一个中点是（1，b0.5），对应的d1的初值为：,（3-20）,构造中点偏差判别式,构造中点偏差判别式：,（3-21）,y,x,P（xi，yi）,Pl（x i，y i1）,Pr（x i1，yi1）,图3-15 下半部分像素点的选取,当d20时，中点M在椭圆外，下一像素点应点亮Pl，即x方向上不走步；当d20时，中点M在椭圆上，Pl、Pr和椭圆的距离相等，点亮Pl或Pr均可，约定取Pl，如图3-15所示。,因此，,（3-22）,下半部分的递推公式,1.中点偏差判别式的递推公式 现在如果考虑主位移方向上再走一步，应该选择哪个中点代入中点偏差判别式以决定应该点亮的像素，如图3-16所示，分两种情况讨论。,P（xi，yi）,M（x i0.5，y i1）,M（x i1.5，y i2）,d20,P（xi，yi）,M（x i0.5，y i1）,M（x i0.5，y i2）,d20,图3-16 下半部分中点偏差判别式的递推,当d20时，下一步的中点坐标为：M（x i1.5，y i2）。所以下一步中点偏差判别式为：,（3-23）,当d20时，下一步的中点坐标为：M（x i0.5，y i2）。所以下一步中点偏差判别式为：,（3-24）,y向分量为：,。则对于上半部分椭圆上一点任意P（xi，yi），,如果在其当前中点M（xi1，yi0.5）处，满足x向分量小于y 向分量：,2.中点偏差判别式d2的初值 由图3-11知道，在上半部分，法矢量的x向分量小于y向分量；在C点，法矢量的x向分量等于y向分量；在下半部分，法矢量的x向分量大于y向分量。由公式3-15知道：x向分量为：,（3-25）,假定图3-17中P（xi，yi）点是椭圆上半部分的最后一个像素，M（xi1，yi0.5）是用于判断点亮Pu和Pd像素的中点。由于下一像素转入了下半部分，所以其中点改为判断Pl和Pr的中点M（xi0.5，yi1），所以下半部分的初值d20为：,（3-26）,P（xi，yi）,Pu（xi1，yi）,Pl（xi，yi1）,M（xi1，yi0.5）,Pd（xi1，yi1）= Pr（xi1，yi1）,M（xi0.5，yi1）,图3-17 下半部分的初值,直线距离加权反走样技术,走 样,直线扫描算法在处理斜线时会出现锯齿