直线和二次曲线

1、计算机图形学计算机图形学武汉大学电子信息学院 王泉德第二章 直线n在光栅显示器的荧光屏上生成一个图形，实质上是往帧缓存寄存器的相应单元中填入数据。n计算机生成图形时，需要绘制大量的直线，设计快速有效的直线绘制算法意义重大。n一般来讲，水平、垂直直线和对角线能准确地画出，但要准确绘制一条斜线并不容易。n在光栅显示器上画（x1, y1）到（x2, y2）的直线，实质上是确定最佳逼近直线的象素序列。（1）生成的直线要直）生成的直线要直 选择最靠近直线的象素点来逼近直线。 理想绘制效果理想绘制效果1、绘制直线的要求 实际绘制效果实际绘制效果（2）起点和终点要准确）起点和终点要准确： 在绘制直线的过程中

2、由于受精度的影响，直线的终点与原终点有一个累积误差，导致直线的终点不准。 （3 3）直线的粗细要均匀）直线的粗细要均匀 由于选点不均匀，造成直线粗细不均匀，直观上反映出直线的亮度不均匀。 （4 4）直线宽度应该与线段的长度和斜率无关：）直线宽度应该与线段的长度和斜率无关： 要取得均匀的线段宽度，应该保持每单位长度的点数是常数。（5 5）显示线段的速度应快：）显示线段的速度应快： 直线的绘制是生成计算机图形的基础，其绘制速度直接影响到计算机图形生成的效率，常采用硬件来实现。2、直线的方程bxmy若其始坐标和终点坐标分别为：),(11yx),(22yx1212xxyym则斜率为11xmyb截距为(

3、1)(2)(3)直线的绘制算法以直线方程（1）、（2）和（3）式为基础。直线的点斜式方程为：对任何沿直线给定的x的增量x，对应的y增量y： ymx同样，对应于y的增量y，x的增量x为： x(1/m)y3、 逐点比较法（1）算法的基本思想： 在绘制直线的过程中，每绘制一个点，就与原直线进行比较，根据比较的结果决定下一步的走向，这样一步一步逼近直线。保证要绘制的点尽可能的靠近直线而不发生远离直线的趋向。 偏差判别选择象素点终点判别偏差计算结束否（2）绘制思路n 由当前点到下一个点的走法是只在X方向或Y 方向走一步。OA计算当前点偏差： =tg-tg OA K1K21) =0，点在直线上； 2) 0

4、，点在直线上方，下一步走X方向；3) 0，点在直线下方，下一步走Y方向。可以简化为FY XYXkkAAk根据 计算出偏差，然后确定下一步的走向。初始：Fk则 =0；第一步：第二步：; 0; 11101YXX; 0; 000YX51*57*0111XYXYFAA0F; 11; 11212YYXX21*57*1222XYXYFAA假定起点为坐标原点偏差计算公式为：kAkAAkkXXXYXYtgtgF(7,5)A(0,0)偏差递推公式1） 时，走X方向一步，即0iF;1111AiiiiiiYFFYYXX2） 时，走Y方向一步，即0iF; 1111AiiiiiiXFFYYXXFY XYXkkAAk偏差

5、计算公式为：n以上讨论的是起点为原点，X为最大步长方向的情况，对于起点是任意点，最大步长方向为其他情况下的绘制直线的偏差计算和偏差判别，可类似推导。n判别终点的方法：设立计数器，计数取X或Y方向的最大增量值（计长方向），在计长方向每走一步，计数器减1，只到计数器值为零为止。OA2、DDA算法(Digital Differential Analyzer)DDA算法是建立在微分方程的基础上。由 到 的直线段满足的微分方程为：),(AAyx),(BByxABAByydtdyxxdtdx因此有ABAByytyxxtx则有tyyytxxxABAB)()(令),max(1ABAByyxxt有yyyxxxi

6、iii11DDA绘制的直线t1/15；6.01591yxDDA绘制直线的算法1.if |xb-xa|yb-ya| then计算直线在y方向上的增量：length=|yb-ya|2.else 计算直线在x方向上的增量：length=|xb-xa|3.计算x方向的单位增量：dx=(xb-xa)/length4.计算y方向的单位增量：dy=(yb-ya)/length5.置初值：x=xa，y=ya6.for i=1 to length do begin7. 输出点(trunc(x), trunc(y)8. 计算下一个点坐标 x=x+dx，y=y+dy end9.end of algorithm3、

7、Bresenham算法算法的基本思想：每次迭代在增量最大方向上走一步，另一方向上是否也走，取决于计算出来的点与直线上的点的误差，根据误差决定是否走一步。即x方向的步长总是方向的步长总是1(斜率小于斜率小于1的情况的情况)， y方向是否有变化，取决于直线的方向是否有变化，取决于直线的理论值与假设点之间的误差值大小。理论值与假设点之间的误差值大小。例如取X方向为最大增量方向，则有：,111xymmyyxxiiii其中 1；m0绘制的直线时点的选取riy,riy, 1 yi yi+1 偏差计算设偏差为5 . 0)(,11riiiyyx当 时，计算的点（实际直线上的点）在 中点的上方，取当 0 时，计

8、算的点（实际直线上的点）在 中点的下方，取0)(1ix)(1ix1, 1ririyyririyy, 1整理后，有0)(0)(111,1, 11iriiririiixyxyyxxriy,riy, 1 yi yi+1 偏差的递推关系5 .0)(,11riiiyyx误差因为myyii1有0)()(0)(1)(0)(5 . 00)(5 . 0) 1(5 . 05 . 0)(, 1, 1,11iiiiiriiiriiriiriiixmxxmxxmyyxmyyymyyyx偏差初值0=m0.5 将乘以2x记为2x ，则同有相同的符号，根据的符号确定象素点的过程仍然正确。此时偏差的表示式做如下变动：初始误差项

9、： 02x 0 2y-x；积累误差 k+1 km修改为： k+12x k+1 2x(ky/x） 2x k2y k2y；如果选取上面的象素点，积累误差还要减去1，修改为： k+12x（ k+11） k 2y 2x Bresenham直线生成算法描述1.计算x和y方向的增量：dx=|xb-xa|，dy=|yb-ya|2.计算递推公式的初值d1: d=2dy-dx3.计算两个单位增量：incr1=2dy , incr2=2(dy-dx)4.if(xaxb) then 置起点为x=xb，y=yb，置终点为xe=xa, ye=ya5.else 置起点为x=xa，y=ya，置终点为xe=xb，ye=yb6

10、.输出起点(x,y)7.while(xxe) do 8.begin9. x=x+110. if(d0) then d=d+incr111. else y=y+1，d=d+incr212. 输出点(x,y) 13.end14.end of algorithm总结 前面所介绍的逐点比较法、数值微分法以及Bresenham算法，它们各有优缺点。因此在使用不同的图形输出设备时要选用最适合于该设备的方法，如在绘图仪中多采用逐点比较法，在点迹技术的显示设备中多用DDA法和Bresenham算法。 4、直线的属性任何影响图元显示方法的参数称为属性参数。线段的基本属性有线型、宽度和颜色。线型：线型：实线、虚线

11、、点线等。 通过设置沿直线路径显示的实线线段的长度和间距来修改画线算法，产生各种类型的直线。线宽：线宽：线刷子：沿着生成直线时获得的象素点，移动一把具有一定宽度的“刷子”来实现。斜率k=1 ，刷子设置为垂直方向，否则设置为水平方向线的连接：线的连接：一定宽度的折线段时，线段的接头处会出现缺口，典型的处理方式有：尖头，圆头和方头三种线头：线头：绘制具有宽度的线段，需要对线头进行处理，典型的线头有下述三种第三章 二次曲线 圆也是图形系统中常用的元素。圆可以定义为所有以距离中心位置 为给定值r的点集。圆的方程为：),(ccyx222)()(ryyxxcc利用这个方程，我们可以沿x轴，从到 以单位步长

12、计算对应的y值，从而得到圆周上每点的位置。rxcrxc可以利用圆的对称性：可以先绘制八分之一圆弧，再利用对称性绘制整个圆1、中点画圆算法考虑圆心在原点的圆。设函数：222),(ryxyxF故有 （x,y)位于圆边界内 （x,y)位于圆边界上 （x,y)位于圆边界外000),(yxF对上述函数在每个取点步骤上，对接近圆周的两个象素点的中点进行测试来决定取点。考虑一个四分之一圆弧从x=0到x=y的情况（第一象限的上八分之一圆弧），圆的曲率从0变化到-1，在该段弧上的正x方向取单位步长，并确定每一步更接近圆弧的y的位置。设已经取的点为 ，决策参数为：222)5 . 0() 1()5 . 0, 1(r

13、yxyxFpkkkkk),(kkyx以此来判断下一步 的点如何取。是 还是 。),(11kkyx), 1(kkyx) 1, 1(kkyx),(kkyx1ky1kx),(11kkyx故有1000111kkkkkkkkkyypyypyyp中点位于圆边界内中点位于圆边界上中点位于圆边界外222)5.0()1()5.0, 1(ryxyxFpkkkkk递推决策函数1)()() 1(2)5 . 0( 1) 1()5 . 0, 1(1221212111kkkkkkkkkkkyyyyxpryxyxFp其中 的取值，决定于 的符号。kp1ky中点画圆圆弧上点的对称关系只画1/8圆，其余点通过对称关系求得。),(

14、iiyx),(iiyx ),(iiyx ),(iiyx),(iixy),(iixy ),(iixy ),(iixy象限判别在进行绘制圆弧曲线时，需要考虑轨迹点所在象限的情况，因此需要进行象限的判别。对于在坐标轴上的点，需要根据绘制圆的方向来决定。ABCD2、Bresenham算法仍然考虑圆心在原点的一个第一象限的圆弧 。对于圆弧上的点p(x, y)，其下一个可选择的点如图。)2,2(), 0 (rrr圆弧上点与该二点之间的关系1. H、D全在圆外；2. H在圆外， D在圆内；3. H在圆外， D在圆上；4. H、D全在圆内；可以计算出这三点到圆心的距离与半径的差：222222222)1()1(

15、)1()1(ryxVryxDryxH分析：1）当 时，圆弧在D的上方，可以取的点是H或D，只要看H和D两个点，哪个与圆弧的距离近。设：0DDHHD0HD0HD0HD时，H点距离圆弧近，H为可取的下一个点。表示了表示了H和和D点到圆弧的距离之差。点到圆弧的距离之差。时，H和D点均为可取的下一个点。时，D点距离圆弧近，D为可取的下一个点。当2）当 时，圆弧在D的下方，可以取的点是D或V，只要看D和V两个点，哪个与圆弧的距离近。设：0DDVHD0VD0VD0VD时，V点距离圆弧近， V为可取的下一个点。时，V和D点均为可取的下一个点。时，D点距离圆弧近，D为可取的下一个点。当3) 当 时，D点在圆上

16、，取D点。0D3、多边形逼近法考虑绘制圆心在 (xc, yc)，半径为r的圆，一个第一象限的圆弧。对于内接正多边形顶点Pi(xi, yi)，其幅角为i，则：sin,cosryyrxxcici下一个顶点Pi+1坐标为：)cos()()sin()()sin()sin()()cos()()cos(11cicicciciciciciyyxxyryyyyxxxrxx只需要计算一次sin()，cos()，就可以递推计算其他顶点，计算一个顶点只需四次乘法。3、二次曲线参数拟合法研究二次曲线的参数方程以及通过已知的型值点构造二次曲线的参数拟合方法。 二次曲线的参数方程为： 1 , 01)(2212210ttetetataatr其中 是常数向量， 是常数，则r(t)表示了二次曲线的轨迹。210,aaa21,ee构造二次曲线已知二次曲线上的三个型值点 ，当t=0时，过 点，且与 相切，当t=1时，过 点，且与 相切。根据已知条件，可以建立方程：321,ppp1p3p32pp21pp1p3p2p建立方程组);()1 ()2)()1)(2() 1 ();()0(;1) 1 (;)0(232212121021211211110132121010ppLeeeeaaaeeaarppKpeaeaarpeeaaa