CG02图形基础算法.ppt

第二章图形算法基础,DDA画线算法,是用舍入的方法获得离直线最近的点。舍入就是我们常用的四舍五入，在程序中实现四舍五入的方法是将值加0.5然后取整。由于在求线上的点的时候用的是数值微分的方法。因而此方法也称为数值微分法(DDA,digitaldifferentialanalyzer)方法,用上式可求出图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/tyi+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=xsyexeys对于直线上的点，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=cosy=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-r20M点在圆外，取Pbf(M)=0AB在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（xi1，yi）和Pd（xi1，yi1）的中点M（xi1，yi0.5）代入隐函数，构造中点偏差判别式：,（3-16）,当d10时，中点M在椭圆外，下一像素点应点亮Pd，即y方向退一步；当d0时，中点M在椭圆上，Pu、Pd和椭圆的距离相等，点亮Pu或Pd均可，约定取Pd，如图3-13所示。,x,y,P（xi，yi）,Pu（xi1，yi）,M（xi+1，yi-0.5）,Pd（xi1，yi1）,图3-13上半部分像素点的选取,因此，,（3-17）,上半部分的递推公式,P（xi，yi),M（xi1，yi0.5）,M（xi2，yi0.5）,P（xi，yi）,M（xi1，yi0.5）,M（xi2，yi1.5）,d10,d10,图3-14上半部分中点偏差判别式的递推,1.中点偏差判别式的递推公式现在如果考虑主位移方向再走一步，应该选取哪个中点代入,图3-13中，为了能够继续判断椭圆上的每个点，需要给出中点偏差判别式d1的递推公式和初始值。,（3-18）,当d10时，下一步的中点坐标为：M（xi2，yi1.5）。所以下一步中点偏差判别式为：,（3-19）,中点偏差判别式以决定应该点亮的像素，如图3-14所示，分两种情况讨论。当d10时，下一步的中点坐标为：M（xi2，yi-0.5）。所以下一步中点偏差判别式为：,2.中点偏差判别式d1的初值上半部分椭圆的起点为A（0，b），因此，第一个中点是（1，b0.5），对应的d1的初值为：,（3-20）,构造中点偏差判别式,构造中点偏差判别式：,（3-21）,y,x,P（xi，yi）,Pl（xi，yi1）,Pr（xi1，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（xi0.5，yi1）,M（xi1.5，yi2）,d20,P（xi，yi）,M（xi0.5，yi1）,M（xi0.5，yi2）,d20,图3-16下半部分中点偏差判别式的递推,当d20时，下一步的中点坐标为：M（xi1.5，yi2）。所以下一步中点偏差判别式为：,（3-23）,当d20时，下一步的中点坐标为：M（xi0.5，yi2）。所以下一步中点偏差判别式为：,（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下半部分的初值,直线距离加权反走样技术,走样,直线扫描算法在处理斜线时会出现锯齿，这是因为直线在油印机扫描显示器上显示的图像是由一系列高密度相同而面积不为0的离散像素点形成的结果。这种由离散量表示边疆量而引起失真称为“走样(aliasing)”。,基本原理,加权反走样算法是采用空间混色原理来对直线进行修正。空间混色原理是指，人眼对某一区域颜色的识别是取这个区域的颜色的平均值。算法是根据像素和理想直线的距离对像素的色饱和度别进行调节。,实现方法,距离加权反走样算法原理是对理想直线上的任一点，同时用色饱和度不同的相邻像素显示。点与理想直线距离与该点的色饱和度成反比。,