LH计算机图形学作业：共九道题
P1=2dy-dx
1.3.2 Bresenham算法实现步骤
综述上面1.3.1的推导，第1a象限内的直线Bresenham算法思想如下：
1、画点(x1, y2); dx?x2?x1; dy? y2?；y1计算误差初值P1=2dy-dx; i=1； 2、求直线的下一点位置：
xi+1=xi+1；
if Pi>0 则yi+1=yi+1； 否则yi+1=yi； 3、画点（xi+1, yi-1）； 4、求下一个误差Pi+1；
if Pi>0 则Pi+1=Pi+2dy-2dx; 否则Pi+1=Pi+2dy；
5、i=i+1; if i 由上述算法思想编制的程序见附录3。这个程序适用于所有8个方向的直线（图1.1）的生成。程序用色彩C画出一条端点为（x1, y1）和的直线。其中变量的含义是：P是误差；const1和const2，是（x2, y2）误差的逐点变化量；inc是y的单位递变量，值为1或-1；tmp是用作象限变换时的临时变量。程序以判断dx>d为y分支，并分别将2a,3a象限的直线和3b,4b象限的直线变换到1a,4a和2b,1b方向去，以求得程序处理的简洁。 1.3.4 Bresenham算法流程图 （略） 1.4 生成直线算法的进一步改进 除过前面所讲到的3种基本直线生成算法外，还有一些其它的方法，由于过多，这里仅列举几种如下： （1）二步法。虽然Bresenham直线生成算法是一效率很高的算法，但是人们仍在寻找更有校的算法。1987年又有人提出了一种二步法。 5 LH计算机图形学作业：共九道题 即每循环一次不是绘制一个像素，而是绘制两个像素，这样无疑可把生成直线的速度提高一倍。 （2）改进的Bresenham算法。对于对于传统的直线生成算法，人们往往把注意力集中在算法本身，却忽略了算法之外的一些有用信息:画线之前，从起点坐标和终点坐标，我们就可以获知该线段的斜率，由此可进一步得出在主轴方向连续走l个步长，在副轴方向才走一个坐标单位，这就是本算法提高Bresenham算法执行效率的一个方面。提高算法效率的第二个方面是利用线段本身的对称性，则新算法所产生的起点一侧的半条线段与用Bresenham算法产生的相同。至于终点一侧的半条线段，可以看成以终点为起点线段的生成。 算法实现： 特殊地，对于水平线(?y?0)，垂直线(?x?0)和对角线(x?y)，它们都可直接装人帧缓冲器，而无需进行画线算法处理。 从以上的描述可以实现优于Bresenham的直线生成算法。其中待生成直线的已知数据为:(x1,y1)为线段起点的横、纵坐标；(x2,y2)为线段终点的横、纵坐标。 算法的输人数据为: (x1,y1)，(x2,y2)。 （3）基于类最佳逼近的散步直线生成算法。一种新的直线逼近方法—类最佳逼近,基于这种逼近方法,斜率k??0,0.5直线和斜率为1?k?的的直线具有某种互补性质。利用该性质,设计出一种新的三步直线方法,该算法揭示了直线计算的互补性,理论简单,精度达到最好。这种算法改善了Bresenham算法和双步算法的计算效率。该算法对于硬件实现将更有益处。 除此之外直线生成算法还有对称扫描四步增量画线算法、基于Bresenham的高效直线生成集成算法、基于Bresenham算法的四步画直线算法、基于直线特性的直线生成集成算法、基于自适应步长的直线生成算法、基于等分像素点的直线生成算法、6步直线生成算法、基于对角线行程的直线生成算法等等。 1.5 各种直线生成算法的优缺点对比分析 DDA算法的优点是：绘制实数直线效果好，误差小；缺点是：实现较复杂，不利于硬件实现。因为该算法涉及到实数乘除法运算，y与k必须用浮点数表示，而且每一步都要对y四舍五入后取整。 6 LH计算机图形学作业：共九道题 中点画线算法优点是：只有整数运算，不含乘除法；可用硬件实现。 Bresenham算法的优点是： 1、不必计算直线之斜率，因此不做除法； 2、不用浮点数，只用整数； 3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。 4、Bresenham算法速度很快，并适于用硬件实现。 1.6 直线生成算法的发展趋势 （略） 2 椭圆的Bresenham生成算法 2.1 椭圆曲率分析 nt椭圆r??acost,bsi?（ 方向的短半轴长度，且 a为沿x轴方向的长半轴长度，b为沿y轴 22223/2a?b），曲率为kr?ab/(asint?bcost)，在 第一象限t??0,?/2?，将kr对t求导数，有dkr/dt?0，即曲率为减函数， )即t?0）处的曲率在点(a,0（ kr(t?0)?a/b2；在点(0,b)（即t??/2）处的 曲率 22kr(t??/2?b/aa/aa。半径为的圆的曲率为，半径为b的圆的曲)率为 b/b2，两圆的曲率关系为b/b2?a/a2(a?b)，则两圆的曲率在椭 22)(0,b)的曲率之间，圆上点(a,0与四者的关系为：a/b?1/b?1/a?b/a。 2.2 椭圆方程分析 根据椭圆及圆的曲率分析，椭圆弧分别由半径为 a和b的圆弧逼近 生成。为了更准确的由圆弧生成椭圆弧，在椭圆弧上确定一点P0，将椭圆弧分成曲率较小和曲率较大的两段，椭圆方程为： F?x,y??b2x2?a2y2?a2b2?0。 其中度，且 a为沿x轴方向的长半轴长度，b为沿y轴方向的短半轴长 a?b?0。由于椭圆的对称性，这里只要讨论第一象限椭圆弧 7 LH计算机图形学作业：共九道题 的生成。将椭圆弧分为上下两部分，以弧上曲率为-1的点（即法向量两个分量相等的点）作为分界。该椭圆上一点(x,y)处的法向量为： N(x,y)??F?Fi?j?2b2xi?2a2yj ?x?y结合椭圆方程可计算出分界点P0的坐标为： (a2/a2?b2,b2/a2?b2)。 以P0点为分界点，将第一象限的圆弧分成曲率较大和较小的两段弧。如图2.1所示， y?[b2/a2?b2,b]椭圆弧，与半径为a的圆在点的 22222T1(0a,到)T2(a/a?b,ab/a?b)的圆弧上对应。在椭圆弧上任取一 点Q1，过Q1作垂直线与圆交于P1点，连接圆心与P1点，与Y轴的夹角为 θ。则 椭圆的参数方程可表示为： '??x?asinθ,?' ??y?bcosθ.圆的参数方程可表示为： ?x?asinθ, ?y?acosθ.?对于同一θ，椭圆弧上存在唯一的点与圆弧上的点对应，并且对应点的坐标存在如下关系： '??x?x,?' y?(b/a)y.?? 图2.1 圆弧与椭圆弧对应点之一 图2.2 圆弧与椭圆弧对应点之一 8 LH计算机图形学作业：共九道题 如图2.2所示，半径为 22222b的圆上，从点T3(a/ab?b,b/a?b)到 T4(b,0)的圆弧与椭圆上y?(0,b2/a2?b2的)椭圆弧对应，在椭圆弧上任 取一点Q2，过Q2作垂直线与圆交于P2点，连接圆心与P2点，与Y轴的夹角为 θ。则 椭圆的参数方程可表示为： '??x?asinθ,?' y?bcosθ.??圆的参数方程可表示为： ?x?bsinθ, ?y?bcosθ.?对于同一θ，椭圆弧上存在唯一的点与圆弧上的点对应，并且对应点的坐标存在如下关系： '??x?(a/b)x,?' y?y.??2.3 椭圆生成算法 当圆弧上的点从(a,0)沿着图2.1、图2.2的对应关系方向变化到 (b,0)时，椭圆弧上相对应的点也从该方向变化到(a,0)。 2.3.1 算法实现过程 1、计算分界点P0(x0,y) 0。 2、用Bresenham算法生成两段圆弧C1、C2。C1半径为a， x?[0,a2/a2?b2]；C2半径为b，y?[0,b2/a2?b2]。 3、将圆弧C1进行比例变换：例系数为 x方向的比例系数为 1， y方向的比 b/a；将圆弧C2进行比例变换：x方向的比例系数为a/b， 1。 y方向的比例系数为 9