基本光栅图形算法课件.ppt

《基本光栅图形算法课件.ppt》由会员分享，可在线阅读，更多相关《基本光栅图形算法课件.ppt（100页珍藏版）》请在三一办公上搜索。

1、2、,基本光栅图形算法,2、 基本光栅图形算法,数学表示的若干方法,1）数学方程2）点集3）边界表示4）关系表示,数学表示的若干方法1）数学方程,常用的图形对象,线段圆多边形字符等,常用的图形对象线段,一、直线,在光栅显示器的荧光屏上生成一个对象，实质上是往帧缓存寄存器的相应单元中填入数据。线段 理想的是无数多的零面积的点构成。 而在实际显示中，在光栅扫描显示器上，线段是由有限多的像素组成的，像素是有面积的。 画一条从（x1, y1）到（x2, y2）的直线，实质上是一个发现最佳逼近直线的象素序列，并填入色彩数据的过程。这个过程也称为直线光栅化。,一、直线在光栅显示器的荧光屏上生成一个对象，实

2、质上是往帧缓存,而且除了水平、垂直和对角线上的线段，其他的线段像素并不一定能准确地落在线段上。,而且除了水平、垂直和对角线上的线段，其他的线段像素并不一定能,最接近数学上的直线:生成的线要直：但实际选择最靠近直线的可寻址点来逼近。,理想的绘制,绘制线段的要求,最接近数学上的直线:绘制线段的要求,绘制线段的要求,起点和终点要准：在绘制线段的过程中由于受精度 的影响，线段的终点与原终点有一个累积误差， 导致线段的终点不准。,绘制线段的要求起点和终点要准：在绘制线段的过程中由于受精度,绘制线段的要求,粗细要均匀 ：由于选点不均匀，造成线段 粗细不均匀，直观上反映出线段的亮度不均匀。,绘制线段的要求粗

3、细要均匀 ：由于选点不均匀，造成线段,光栅显示平面上，我们只能用二维光栅格网上尽可能靠近这条直线的象素点的集合来表示它。每个象素具有一定的尺寸，是显示平面上可被访问的最小单位，它的坐标x和y只能是整数，也就是说相邻象素的坐标值是阶跃的而不是连续的。,光栅显示平面上，我们只能用二维光栅格网上尽可能靠近这条直线的,实际绘制,实际绘制,线段的笛卡儿斜率截距方程,若其始坐标和终点坐标分别为：,则斜率为,截距为,(1),(2),(3),显示直线的算法可以直线方程（1）、（2）和（3）为基础。,线段的笛卡儿斜率截距方程若其始坐标和终点坐标分别为：则斜率为,1. 逐点比较法,算法的基本思想：在绘制直线的过程

4、中，每绘制一个点，就与原直线进行比较，根据比较的结果决定下一步的走向，这样一步一步逼近直线。,保证要绘制的点尽可能的靠近直线而不发生远离直线的趋向。,1. 逐点比较法算法的基本思想：在绘制直线的过程中，每绘制保,绘制思路,由一个点到下一个点的走法是只在X方向或Y 方向走一步。,绘制思路由一个点到下一个点的走法是只在X方向或Y 方向走一步,计算偏差,K1,K2,计算偏差 K1K2,设 =tg-tg,于是有 1) =0，点在直线上； 2) 0，点在直线上方； 3) 0，点在直线下方。,设偏差计算公式为： = tg-tg=,设 =tg-tg 于是有 1) =0，点在直线,偏差计算,可以简化为,根据

5、计算出偏差，然后确定下一步的走向。初始：,则 =0；,第一步：如果选择X方向，则,若选择Y方向，则,所以选择X方向走，则第一步选择（1，0）点处,偏差计算可以简化为根据 计算出偏差，然后确定下一步,起点（0，0）终点（7，5） XA=7 YA=5,步数走X的偏差走Y的偏差最后选择000（0，0)1-57走X,绘制结果,绘制结果,偏差递推公式,1） 时，走X方向一步，即,2） 时，走Y方向一步，即,偏差递推公式1） 时，走X方向一步，即2,偏差递推公式,以上讨论的是起点为原点，第一象限的情况，对于其他情况下的绘制直线的偏差计算和偏差判别，推导也很简单。,偏差递推公式以上讨论的是起点为原点，第一象

6、限的情况，对于其他,Fi=0Fi01象限X1Y12象限Y1X1,终点判别,判别终点的方法：设立计数器，计数取X或Y方向的最大增量值（计长方向），在计长方向每走一步，计数器减1，直到计数器值为零为止。,终点判别判别终点的方法：设立计数器，计数取X或Y方向的,绘制直线,绘制直线,2. DDA(Digital Differential Analyzer)数字微分,该算法是建立在微分方程的基础上。由 到 的直线段满足的微分方程为：,2. DDA(Digital Differential An,因此有,则有,令,有,因此有则有令有,此递归式的初值为直线的起点 ，这样，就可以用加法来生成一条直线。,Voi

7、d dda_line (xa, ya, xb, yb,c) float delta_x, delta_y, x, y; int dx, dy, steps, k; dx=xb-xa; dy=yb-ya; if (abs(dx)abs(dy) steps=abs(dx); else steps=abs (dy);delta_x=(float)dx / (float)steps;delta_y=(float)dy / (float)steps;x=xa;y=ya;putpixel(round(x),round(y), c);for (k=1; k=steps; k+)x+=delta_x;y+=d

8、elta_y;putpixel(round(x),round(y), c);,此递归式的初值为直线的起点 ，这,DDA绘制的直线,1/15；,DDA绘制的直线1/15；,基本光栅图形算法课件,算法特点：,该算法简单，实现容易，但由于在循环中涉及实型数的运算，因此生成直线的速度较慢。,算法特点：该算法简单，实现容易，但由于在循环中涉及实型数的,3. Bresenham算法,设直线从起点（x1, y1）到终点（x2, y2）。直线可表示为方程y=mx+b。其中 b = y1 - m * x1, m = 本算法由Bresenham在1965年提出。算法的基本思想：每次迭代在增量最大方向上均走一步，其

9、方向由增量的正负而定，另一方向上是否也走，取决于计算出来的点与直线上的点的误差，根据误差决定是否走一步。,3. Bresenham算法设直线从起点（x1, y1）到终,xi+1=xi+Dxyi+1=yi+Dy按照直线从（x1，y1）到（x2，y2）的方向不同，分为8个象限。对于方向在第1a象限内的直线而言，D x=1，D y=m。对于方向在第1b象限内的直线而言，取值Dy=1，Dx=1/m。各象限中直线生成时Dx, Dy的取值列在下页表中。,xi+1=xi+Dx,象限|dx|dy|?D xD y1a 1m1bX1/m,绘制的直线时点的选取,yi,yi+1,绘制的直线时点的选取 yi yi+1,

10、选择哪一个点？(Xi1， Yi,r)还是 (Xi1，Yi+1,r)用Yi+1与Yi,r进行误差计算，误差大于0.5选择上面的点，否则选择下面的点。使用偏差来计算确定那一个点。,选择哪一个点？,偏差计算,设偏差为,当 时，计算的点（实际直线上的点）在 中点的上方，取当 0 时，计算的点（实际直线上的点）在 中点的下方，取,整理后，有,偏差计算设偏差为当 时，计算,偏差的递推关系,误差,因为,有,偏差的递推关系误差因为有,此时，算法中仍有浮点数运算，而且m=dy/dx, 并且dx0，所以我们引入 F = 2*dx*F与 的符号相同可以用来作为判别式。因此，初始x=x1,y=y1,F1=2dy-dx

11、其递推公式：若Fi=0,则xi+1=xi+1,yi+1=yi+1, Fi+1=Fi+2(dy-dx);,此时，算法中仍有浮点数运算，而且m=dy/dx, 并且dx,总结：算法公式,初始条件： F1=2dy-dx当Fi0时： yi+1=yi+1,xi+1=xi+1，Fi+1=Fi+2(dy-dx)否则：yi+1=yi,xi+1=xi+1， Fi+1=Fi+2dy,总结：算法公式初始条件：,第一象限下算法思想如下：,此时满足：0m1且x10 则yi+1=yi+1； 否则yi+1=yi；3、画点（xi+1, yi+1）；4、求下一个误差Pi+1； if Pi0 则Pi+1=Pi+2dy-2dx; 否

12、则Pi+1=Pi+2dy；5、i=i+1; if idx+1则转4；否则end,第一象限下算法思想如下：此时满足：0m1且x1x2,算法的完善，所有象限,线段的方向可分为八种，从原点出发射向八个区。由线段所在区域位置可决定xi+1和yi+1的变换规律。,1a、2a,3a、4a,1b、4b,2b、3b,算法的完善，所有象限线段的方向可分为八种，从原点出发射向八个,容易证明：当线段处于a区时，以|dx|和|dy|代替前面公式中的dx和dy，当线段处于b区时，将公式中的|dx|和|dy|对换，则上述两公式仍有效。,容易证明：当线段处于a区时，以|dx|和|dy|代替前面公式,Bresenham算法的

13、优点,Bresenham算法的优点是：1、不必计算直线之斜率，因此不做除法；2、不用浮点数，只用整数；3、只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。Bresenham算法速度很快，并适于用硬件实现。,Bresenham算法的优点Bresenham算法的优点是：,程序代码：,由上述算法思想编制的程序如下。这个程序适用于所有8个方向的直线的生成。程序用色彩C画出一条端点为（x1, y1）和（x2, y2）的直线。其中变量的含义是：P是误差；const1和const2，是误差的逐点变化量；inc是y的单位递变量，值为1或-1；tmp是用作象限变换时的临时变量。程序以判断|dx|dy|为

14、分支，并分别将2a, 3a象限的直线和3b, 4b象限的直线变换到1a, 4a和2b, 1b方向去，以求得程序处理的简洁。,程序代码：由上述算法思想编制的程序如下。这个程序适用于所有8,代码：,void line (x1, y1, x2, y2, c)int x1, y1, x2, y2, c;int dx, dy,x, y, p, const1, const2, inc, tmp;dx=x2-x1;dy=y2-y1;if (dx*dy=0) /*准备x或y的单位递变值。*/ inc=1;elseinc= -1;if (abs(dx)abs(dy) if(dx0) tmp=x1; /*将2a,

15、 3a象限方向*/ x1=x2; /*的直线变换到1a, 4a*/ x2=tmp; /*象限方向去*/ tmp=y1; y1=y2; dx=-dy; dy=-dy; ,=2*dy-dx; const1=2*dy; /*注意此时误差的*/ const2=2*(dy-dx); /*变化参数取值. */ x=x1; y=y1; set_pixel(x, y, c); while (xx2) x+; if (p0) p+=const1; else y+=inc; p+=const2; set_piexl(x, y, c); ,代码：void line (x1, y1, x2, y2,代码：,else

16、if (dy0) tmp=x1; /* 将3b, 4b象限方向的*/ x1=x2; /*直线变换到2b, 1b */ x2=tmp; /*象限方向去. */tmp=y1; y1=y2; dx=-dy; dy=-dy; p=2*dx-dy; /*注意此时误差的*/ const1=2*dx; /*变化参数取值. */ const2=2*(dx-dy); x=x1; y=y1; set_pixel (x, y, c);,while (yy2) y+; if(p0) p+=const1; else x+=inc; p+=const2; set_pixel (x, y, c); ,代码：else whi

17、le (yy2),总结,前面所介绍的逐点比较法、数值微分法以及Bresenham算法，都是一种单点生成直线的的算法。它们各有优缺点，因此在使用不同的图形输出设备时要选用最适合于该设备的方法，如在绘图仪中多采用逐点比较法，在点迹技术的显示设备中多用DDA法和Bresenham算法。,总结 前面所介绍的逐点比较法、数值微分法以及,单点生成直线的算法已经没有优化的余地,比如bresenham算法，其计算量主要体现在主循环上，没有再减少的余地。每计算一个点的计算量有：循环语句所需的一次结束判断。每个点都要进行判断，然后确定是否到了线段的结束。对x和y坐标进行的加法，1+min(dx,dy)/max(d

18、x,dy)次。对 的一次加法和一次比较操作。但是对于单点生成来说，这已经是最少计算量的算法了，一个点要花费的计算量是2+min(dx,dy)/max(dx,dy)次加法和2次比较而已。,单点生成直线的算法已经没有优化的余地比如bresenham算,双点bresenham画线算法,双点的画线绘制，每次决定两个点，因而效率大约提高了一倍。我们先考虑第一象限的情况。这时会出现四种模式，如图所示：,1,2,3,4,当m= 1/2时，1的情况不会出现。而当m=1/2时，4的情况不是出现。,双点bresenham画线算法双点的画线绘制，每次决定两个点,算法：,0=0，则采用模式2或者3，并且进一步判断为，

19、如果，Fi2*y，则选择用模式2，否则，选择3模式。,1/2=0，则采用模式4，并且（2）如果Fi0，则采用模式2或者3，并且进一步判断为，如果，Fi2*(y-x)，则选择用模式2，否则，选择3模式。,算法：0=m=1/2时，初始判别式1/2=m=1时，,圆,圆也是图形系统中常用的元素。我们将圆定义为所以距离中心位置 为给定值r的点集。圆的方程为：,利用这个方程，我们可以沿x轴，从到 以单位步长计算对应的y值，从而得到圆周上每点的位置。,圆 圆也是图形系统中常用的元素。我们将圆定义为利用这个,但这样做，由于有乘方和平方根运算，并且都是浮点运算，算法效率不高。而且这样求出的圆周上的点是不均匀的；

20、|x-xc|越大，由于圆的斜率趋于无穷大，使得圆周上有较大的间隙 。对应生成圆周点之间的圆周距离也就越长。因此，所生成的圆不美观。,但这样做，由于有乘方和平方根运算，并且都是浮点运算，算法效率,也可以用极坐标表示x=xc+rcosy=yc+rsin当 从0 度到360 作加1递增时，由此式便可求出圆周上均匀分布的360个点的x, y坐标。利用圆周坐标的对称性，此算法还可以简化：将圆周分为8个象限。只要将第1b象限中的圆周光栅点求出，其余7部分圆周就可以通过对称法则计算出来。图给出了圆心在0，0点时的对称变换法则。但即使作了如此简化，用上述公式每算一点，都要经过三角函数计算，仍有相当大的计算量。

21、,(y,-x),极坐标法,也可以用极坐标表示(y,-x)极坐标法,下面的函数CirclePoints()用来显示P(x，y)及其七个对称点。 void CirclePoints(x,y,color)int x,y,color;putpixel(x,y,color);putpixel(x,y,color);putpixel(x,y,color);putpixel(x,y,color);putpixel(y,x,color);putpixel(y,x,color);putpixel(y,x,color);putpixel(y,x,color);,下面的函数CirclePoints()用来显示P(x

22、，y)及,圆的位图,圆的位图,1. 中点圆算法,考虑圆心在原点的圆。设函数：,故有 （x,y)位于圆边界内 （x,y)位于圆边界上 （x,y)位于圆边界外,对上述函数在每个取点步骤上，对接近圆周的两个象素点的中点进行测试来决定取点。,1. 中点圆算法考虑圆心在原点的圆。设函数：故有,考虑一个八分之一圆弧,从x=0到x=y的情况，曲线的曲率从0变化到-1，在该段弧上的正x方向取单位步长，并根据决策参数确定每一步可能的y的位置，哪一个更接近圆弧的位置。设已经取的点为P根据在第二象限的圆的走向，下一列中接近圆的像素只能在P的正右方点或者是右下方点中选择。,考虑一个八分之一圆弧从x=0到x=y的情况，

23、曲线的曲率从0变,如下图所示，图中有两条圆弧A和B，假定当前取点为Pi(xi，yi)，如果顺时针生成圆，那么下一点只能取正右方的点E(xi+1，yi)或右下方的点SE(xi+1，yi-1)两者之一。,如下图所示，图中有两条圆弧A和B，假定当前取点为Pi(xi，,LPH),(kkyx1-ky1+kx),(1+kkyx,选择标准：,以此来判断下一步 的点如何取。是 还是 。,理想的选择标准是计算H和L到圆弧的距离，然后选择距离小的点。在此算法中我们选择用两个点的中点作为标准，判断这个中点落在圆上、外还是内？分别选择L和H。,选择标准：以此来判断下一步,故有,中点位于圆边界内中点位于圆边界上中点位于

24、圆边界外,故有中点位于圆边界内),(kkyx1-ky1+kx),(1+,递推判决函数,其中 的取值，决定于 的符号。,递推判决函数其中 的取值，决定于,有：,若， 0 说明中点在圆内，那么下点取H，则判别式,若， =0 说明中点在圆外或上，那么下点取L，则判别式,有：若， 0 说明中点在圆内，那么下点取H，,初始时在圆点，所以D0=(0+1)2+（r-0.5)2-r2=1.25-r但是此算法中有浮点运算，因此我们令F=d-0.25 则F0=1-r则上面的递推判别式为Fk= -0.25 选择L 每次迭代计算都是整数，而且初始F也为整数，所以可以等价于以0作为判别界限。,初始时在圆点，所以,中点画

25、圆,中点画圆,2.Bresenham算法,仍然考虑圆心在原点的一个第二象限的圆弧 。对于圆弧上的点p，其下一个可选择的点如图。,2.Bresenham算法仍然考虑圆心在原点的一个第二象限的,选择方法：,可以计算出这两点到圆心的距离和半径平方的差为：即两点与圆弧的距离：,若：|D(H)| |D(L)| 则取L点。 |D(H)|= |D(L)| 则两点都可以取，我们约定取L。,选择方法：可以计算出这两点到圆心的距离和半径平方的差为：若：,令,则选择标准可以表示为 di =0，下一点选择L。根据分析,可以用 代替上面的式子，计算可以不用绝对值计算。因此，可以由这样的递推公式：若，di=0，则 走右下

26、方点，y坐标减1，x坐标加1， di+1=di+4(xi-yi)+10,令则选择标准可以表示为PABCDEHL,3.逐点比较法插补圆弧,首先确定顺时针还是逆时针方向画圆若逆时针第一象限 C（Cx，Cy）圆心，起点S（Xs，Ys）末点E（Xe，Ye） 另一点M（Xm，Ym）,半径Rs M点到圆心的距离Rm点M和圆的关系：以FmRm2Rs2（XmXc）2（YmYc）2 为判别函数 则有： Fm0 点在圆外，Fm0，在圆内，Fm=0 在圆上,3.逐点比较法插补圆弧首先确定顺时针还是逆时针方向画圆半径R,起点在圆上，F00，根据约定，走x方向-x，x1=xs -x，y1=ys F1（x1-xc)2+(

27、y1-yc)2-Rs2 F02 x(xs-xc)+ -x2,F00 x2 0 xs-xc0 F10 走y,F2（x2-xc)2+(y2-yc)2-Rs2 F12 y(y1-yc)+ -y2,起点在圆上，F00，根据约定，走x方向-x，x1=xs,递推公式 第i步，Fi 则第i1步,Fi= 0 ，走 x ， xi+1 = xi x ， yi+1 = yi,Fi 0 ，走 +y ， xi+1 = xi ， yi+1 = yi + y,递推公式 第i步，Fi 则第i1步Fi= 0 ，走 ,终点比较： 当前点和终点的坐标值进行比较 其差的绝对值小于给定的一个小的正整数,终点比较： 当前点和终点的坐标值

28、进行比较 其差,4.角度DDA画圆,圆的参数方程，t从02x=xc+rcosty=yc+rsint,圆点（xc，yc），半径r ，若从起始点ts到末点te 一段圆弧离散化圆弧，运动步数n可求出为 n（tets）/ dt + 0.5 titstdtdt如何确定？可以根据半径的大小给定dt的经验数据，并根据精度和速度进行调整由dt变化的值，只要把ti带入上面的参数方程中就能计算出xi，yi，连接点划线，绘制直线逼近圆弧即可,4.角度DDA画圆圆的参数方程，t从02圆点（xc，yc,如果给定圆周上的3个点：起末点坐标和任一个圆周上点的坐标。求出圆心坐标和半径以及起末点所对应的角度，就可以用角度DDA

29、法绘制圆弧了。,如果给定圆周上的3个点：起末点坐标和任一个圆周上点的坐标。求,椭圆,圆是椭圆的一种特殊情况。若考虑椭圆的中心在坐标原点，长半轴为a，短半轴为b，则椭圆满足这样的参数方程：参数方程也可以表示为令函数 则可以由F(x,y)的值来判断点与椭圆的关系。 因此，我们可以将画圆的算法推广来画椭圆。,椭圆圆是椭圆的一种特殊情况。,1.中点画椭圆,椭圆也具有对称性，只要绘制出来第一象限的1/4，其他的就可以用对称来生成。也就是说我们只要绘制出（0，b）到（a，0）部分的按顺时针方向的最接近理想椭圆弧段的像素序列。思想：将第一象限的1/4圆弧分为两部分，分界点为椭圆弧线的斜率为-1的点，即该点法

30、向量的x分量和y分量相等。也就是2b2x=2a2y处。（1）上部分：待选择的点（xi,yi）是已经绘制点的正右方点或者右下方点。用这两点的中点(xi+1,yi-0.5)和椭圆参数函数计算出来这一点和椭圆的关系。因此有判别式：选择的标准和递推公式： di=0，选择右下方点，此时，di+1=di+b2(2xi+3)+a2(-2yi+2),1.中点画椭圆椭圆也具有对称性，只要绘制出来第一象限的1/4,初始时，x0=0，y0=b，代入则可得到d0=F(1，（b-0.5）)=b2+a2(-b+0.25)结束点(xi,yi)满足条件2b2xi=2a2yi（2）下半部分，即2b2xi = 2a2yi已选点(

31、xi,yi)，选择下一点是在右下方或者正下方点中选择。,则选择标准：di=0，选择正下方点，此时，di+1=di+a2(-2yi+3)初始点处d0=F(xi+0.5，yi-1)=b2(xi+0.5)2+a2(yi-1)2-a2b2,初始时，x0=0，y0=b，代入则可得到则选择标准：,2.DDA绘椭圆,椭圆的长、短半轴a、b起始点S(Xs,Ys)，起点角度ts，末点角度te，长轴和x轴方向的夹角,x,o,y,E,S,xx,x,y,y,ts,C,2.DDA绘椭圆椭圆的长、短半轴a、b起始点S(Xs,Ys),坐标系xcy中， S点坐标为,坐标系xcy中，S的坐标为,坐标系xoy中，S的坐标为,坐标

32、系xcy中， S点坐标为坐标系xcy中，S的,后面的问题就是求出S到E的椭圆上的各点坐标,n（tets）/ dt + 0.5 titstdt,后面的问题就是求出S到E的椭圆上的各点坐标n（tets）,抛物线,抛物线的方程分析其p为正的情况下，抛物线右边的情况，左半边可以使用其对称性绘制出来。对其方程求导由此可以知道抛物线的性质，在p大于0的情况下，右边的斜率为正，并且随着x值的增大而增大，在xpa的时候，斜率为1，两边分别小于和大于1。 因此 可以以xpa为分界点，左边斜率小于1，抛物线趋于水平，选择最逼近抛物线的点则应该是当前点的正右方点或者是右上方点；右边斜率大于1，抛物线趋于垂直方向，所

33、选择的下一个点则应该是当前点的正上方点或者是右上方点。,抛物线抛物线的方程,（1）x =pa,从当前的象素点（xi，yi）的右方或者右上方点中选择一个合适的点作为下一点的位置。此时xi1xi1 抛物线上对应的y值为,然后判断yi1和yi哪个离yr更近,若di0，说明右上点离的近，否则右方点为最近点。,（1）x =pa从当前的象素点（xi，yi）的右方或者右,判别式变换，因为只有用到判别式的符号，所以避免使用除法和小数运算，所以对其进行边换，给其乘以p，由于p是正数所以判别式的符号没有变化。 Fidi p 2pyi p (xi 1a)22bp可以计算出其递推关系式 Fi1 2pyi1 p (xi

34、1 1a)22bp 如果选择右上点 则 yi1 yi 1 此时 Fi1 2p（yi 1）p (xi1 1a)22bp Fi 2p 2xi1 2a 1 如果选择右方点 则 yi+1 = yi 此时 Fi1 2pyi p (xi1 1a)22bp Fi 2xi1 2a 1,判别式变换，因为只有用到判别式的符号，所以避免使用除法和小数,总结如下： 若Fi0 则,否则：,起始点若为（x0，y0）则F02py0p（x01a）2 2bp 由于起点是无误差点，即起坐标满足抛物线方程，所以 F0p2（x0a）1,总结如下：否则：起始点若为（x0，y0）则F02py0p,（2）x pa,从当前的象素点（xi，y

35、i）的上方或者右上方点中选择一个合适的点作为下一点的位置。此时yi1yi1 抛物线上对应的x值为,然后判断xi1和xi哪个离xr更近,若di0，说明右上方点离的近，否则上方点为最近点。,（2）x pa从当前的象素点（xi，yi）的上方或者右上,判别式变换，因为只有用到判别式的符号，而且上式的两项分别都为正（因为我们所考虑的式抛物线的右半边且此情况为xp+a；所以为了避免开方运算，对其进行变换；令：,可以计算出其递推关系式,如果选择右上点 则 Xi1 Xi 1,否则选择上方点 则 Xi1 Xi,判别式变换，因为只有用到判别式的符号，而且上式的两项分别都为,总结如下： 若Fi0 则,否则：,此段的

36、起点（xi，yi）为上一段即x=p+a的末点，则F可由F变换而来， 此点处F4（Fxipa）3,总结如下：否则：此段的起点（xi，yi）为上一段即x=p+,对称部分的抛物线 抛物线关于xa对称因此右半部分的点（x，y）根据对称性就可以知道其左半边的对应的电为（2ax，y）。,对称部分的抛物线,算法程序：,输入参数：（Xs，Ys），（Xe，Ye）顶点（a，b）参数p。 xXs； y = Ys； putpixel(x，y)； F p2（Xsa）1； /*设置F的值While x != (p+a) x = x+1 if (F0) then y = y +1; F = F2（pax）1； else F

37、 = F+2( ax)-1 putpixel( x,y); putpixel( 2a x , y); if xXe 结束； /*这一段计算的式x =pa段；,算法程序：输入参数：（Xs，Ys），（Xe，Ye）顶点（a，,F 4（Fxpa）3；/*设置F的值While y != Ye y = y+1 if (F pa段；,F 4（Fxpa）3；/*设置F的值,*二次曲线的参数拟合,二次曲线的一般参数方程,所对应的代数方程是：,通常给三个控制点P0，P1，P2,*二次曲线的参数拟合二次曲线的一般参数方程所对应的代数方程是,可计算出各系数为,3点就可确定曲线位置De124e2 表示曲线线型D0 抛物

38、线D0 双曲线D0 椭圆,可计算出各系数为3点就可确定曲线位置,抛物线,D0 e1e20,抛物线D0 e1e20,若以t1/2时点Pm为起末点外的另一点则：,若以t1/2时点Pm为起末点外的另一点,得出参数方程的系数，就可以计算出离散化方程为,t从0到1变化,得出参数方程的系数，就可以计算出离散化方程为t从0到1变化,双曲线,e11 e20,双曲线e11 e20,基本光栅图形算法课件,得出参数方程的系数，就可以计算出离散化方程为,t从0到1变化,得出参数方程的系数，就可以计算出离散化方程为t从0到1变化,椭圆,e10 e21,椭圆e10 e21,基本光栅图形算法课件,得出参数方程的系数，就可以计算出离散化方程为,t从0到1变化,得出参数方程的系数，就可以计算出离散化方程为t从0到1变化,