基本图形生成算法

如何在指定的输出设备上根据坐标描述构造基本几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）?第3章基本图形生成算法2图形生成的概念直线段的扫描转换圆的扫描转换多边形的扫描转换与区域填充属性处理反走样技术第3章基本图形生成算法点的生成

点是图形中最基本的图元，直线、曲线以及其它的图元都是点的集合。在几何学中，一个点既没有大小，也没有维数，点只是表示坐标系统中一个位置。在计算机图形学中，点是用数值坐标来表示的。在直角坐标系中点由（x,y)两个数值组成的坐标表示，在三维坐标系中点是由（x,y,z)三个数值组成的坐标表示。在输出设备上输出一个点，就要把应用程序中的坐标信息转换成所用输出设备的相应位置。对于一个CRT监视器来说，输出一个点就是要在指定的屏幕位置上打上电子束，使该位置上的荧光点亮。在PC机中，点亮屏幕上一个点是由BIOS控制完成的，各种程序语言中都有描点语句。例如C语言为putpixel(x,y,color),putpixel(放,摆-像素)。3.1图形生成的概念3图形的生成：是在指定的输出设备上，根据坐标描述构造二维几何图形。图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的像素集的过程。

用像素点集逼近直线3.1图形生成的概念3.1图形生成的概念

在数学上，理想的直线是没有宽度的、由无数个点构成的集合。当我们对直线进行光栅化时，只能在显示器所给定的有限个像素组成的矩阵中，确定最佳逼近该直线的一组像素，并且按扫描线顺序对这些像素进行写操作，这就是通常所说的直线的扫描转换。

通常用于直线光栅化的算法有数值微分法（DDA）、中点画线法和Bresenham画线算法。3.2直线的扫描转换直线光栅化算法直线段生成求与直线段充分接近的像素集直线的绘制要求（1）直线要直；（2）直线的端点要准确，无定向性无断裂；（3）直线的亮度、色泽要均匀；（4）画线的速度要快；（5）具有不同的色泽、亮度、线型等。3.2直线的扫描转换解决的问题：给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。数值微分法(DDA算法)中点画线算法Bresenhan算法3.2直线的扫描转换已知一条直线段L（P0,P1）,其端点坐标为：P0(x0,y0),P1(x1,y1)。可计算出直线的斜率k为：DDA（DigitalDifferentialAnalyzer）画线算法也称数值微分法，是一种增量算法。它的算法实质是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。3.2.1数值微分法(DDA法)假定端点坐标均为整数，取直线起点P0(x0,y0)作为初始坐标。画线过程从x的左端点x0开始，向x右端点步进，每步x递增1，计算相应的y坐标，y=kx+b，取像素点（x，round（y））作为当前点的坐标。问题:每步需要用到浮点数的乘法、加法和取整运算，效率不高。怎么办??3.2.1数值微分法(DDA法)11增量算法因为:

y=kx+b,所以:yi+1=kxi+1+b=k(xi+1)+b=kxi+b+k=yi+k(xi,yi)→(xi+1,yi+k)3.2.1数值微分法(DDA法)

r例图中

k<1△X=1

△Y=kr将算得的直线上每个点的当前坐标，按四舍五入得到光栅点的位置

r浮点数取整:yi=round(yi)=(int)(yi+0.5)12

有：

yi+1=yi+k•△Xr若0<k<1，即x>y

q因光栅单位为1，

q可以采用每次x方向增加1，

q而y方向增加k的办法得到下一个直线点。因:3.2.1数值微分法(DDA法)演示说明13例：画直线段P0(0,0)--P1(5,2)解：斜率K=2/5=0.4，所以X方向每次步长为1，Y方向递增K。初始点为（0，0）。xint(y+0.5)y0 0 01 0 0.42 1 0.8

3 1 1.24 2 1.65 2 2.0当k

1时，必须把x，y地位互换yi+1=yi+k14程序实现：voidDDALine(intx0,inty0,intx1,inty1,intcolor){intx;floatdx,dy,k,y;dx=x1-x0;dy=y1-y0;k=dy/dx;y=y0;for(x=x0;x<=x1;){

drawpixel(x,int(y+0.5),Color);x++;y=y+k;}}15通常情况下，直线的方向分为8个不同的区域，每个区域的处理方法有所不同。K=△y/△x区域dxdy1a(1)1k1b(2)1/k12a(4)-1k2b(3)-1/k13a(5)-1-k3b(6)-1/k-14a(8)1-k4b(7)1/k-13.2.1数值微分法(DDA法)163.2.1数值微分法(DDA法)18增量算法直观、易实现不利于用硬件实现数值微分法(DDA法)——特点3.2.2中点画线算法中点画线算法的基本思想为了讨论方便，假设直线的斜率在0到1之间，若直线在x方向上增加一个光栅单位，则在y方向上的增量只能在0到1之间。设P（xp,yp）是直线上的一点，与P点最近的网格点为（xi,yi）,那么，下一个与直线最近的像素只能是正右方的网格点P1（xi+1,yi）或右上方的网格点P2（xi+1,yi+1）两者之一。再以点M（xi+1,yi+0.5）表示P1和P2的中点，设Q是直线与垂直线x=xi+1的交点。显然，若M在Q的下方，则P2离直线较近，应取P2为下一个像素点，否则应取P1做为下一个像素点，这就是中点画线算法的基本思想。

问题：如何判断M与Q点的关系？19图

直线将平面分为三个区域3.2.2中点画线算法假设直线的起点、终点分别为：（X0,Y0),(X1,Y1)

则直线方程可表示为：

F(x,y)=a*x+b*y+c（1）

其中：

a=Y0-Y1,b=X1-X0,c=X0*Y1-X1*Y0

空间某点（x,y）与直线的关系：

当：20

设直线的起点和终点分别为（x0,y0)和(x1,y1)则直线方程为F(x,y)=ax+by+c=0（1）∴欲判断中点M点是在Q点上方还是在Q点下方，只需:将中点M坐标代入（1）式，并判断其符号即可确定像素点的选取。构造如下判别式：采用增量计算

d=F(M)=F(x+1,y+0.5)=a(x+1)+b(y+0.5)+c在d≥0的情况下(M在直线上(Q点)或上方)，取正右方像素P1在d<0的情况下(M在直线(Q点)下方)，取右上方像素P23.2.2中点画线算法能否采用增量算法呢？3.2.2中点画线算法若d0->M在直线上方->取P1;此时再下一个像素的判别式为

d1=F(x+2,y+0.5)(F(x,y)=ax+by+c=0)=a(x+2)+b(y+0.5)+c=a(x+1)+b(y+0.5)+c+a=d+a；增量为ad=F(M)=F(x+1,y+0.5)=a(x+1)+b(y+0.5)+c若d<0->M在直线下方->取P2;此时再下一个象素的判别式为

d2=F(x+2,y+1.5)=a(x+2)+b(y+1.5)+c=a(x+1)+b(y+0.5)+c

+a+b=d+a+b

；增量为a＋b3.2.2中点画线算法d=F(M)=F(x+1,y+0.5)=a(x+1)+b(y+0.5)+c画线从(x0,y0)开始，d的初值（F(x,y)=a*x+b*y+c）

d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=ax0+a+by0+0.5b+c=ax0+by0+c+a+0.5b=F(x0,y0)+a+0.5b=a+0.5b注：由于（x0,y0）在直线上，故F(x0,y0)=0所以，d的初始值d0=a+0.5b

3.2.2中点画线算法由于只用d的符号作判断，为了只包含整数运算,可以用2d代替d来摆脱小数，提高效率。用2d代替d后，d0=2a+bd的增量都是整数(d1:2a,d2:2(a+b))如果进一步把算法中2*a改为a+a等等，那么这个算法不仅只包含整数变量，而且不包含乘除法，适合硬件实现。3.2.2中点画线算法演示说明d的初始值d0=a+0.5b

解:

K=dy/dx=2/5=0.4<1,故x方向增1,y方向根据d的符号判断.

a=y0-y1=-2;b=x1-x0=5;d0=2a+b=1;d1=2a=-4;d2=2(a+b)=6;xyd00110-321331-1425521例:按照中点画线算法，确定直线（0，0）（5，2）的点亮像素。列出计算过程，并列出所选像素坐标。在d≥0的情况下，取正右方像素P1，判断再下一像素应计算

d1=a(x+2)+b(y+0.5)+c=d+a,故d的增量为a.在d<0的情况下，取右上方像素P2，判断再下一像素应计算

d2=a(x+2)+b(y+1.5)=d+a+b,故d的增量为a+b.d的初始值d0=a+0.5b用2d代替d后，d0=2a+bd的增量都是整数d1：2ad2：2(a+b)程序实现：voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,b,d1,d2,d,x,y;a=y0-y1,b=x1-x0,d=2*a+b;d1=2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,color);while(x<x1){if(d<0){x++;y++;d+=d2;}else{x++;d+=d1;}drawpixel(x,y,color);}}在d<0的情况下(M在直线(Q点)下方)，取右上方像素P2,再下一个像素的判别式为d2.在d>=0的情况下(M在直线(Q点)上方)，取正右方像素P1,再下一个像素的判别式为d1.3.2.3Bresenham画线算法

Bresenham算法是计算机图形学领域使用最广泛的直线生成算法。假设直线斜率kЄ[0,1]。Bresenham画线算法的基本原理是：按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。

这是计算机科学教授JackEltonBresenham最知名的一项创新，开发于1962年。

因为斜率较小，所以每条垂直线上最多选取一个像素。如果像素点Pi-1(xi-1，yi-1)是已经选定的离直线最近的像素点，现在要决定下一个像素点Pi是Ti

还是Si。如图3-5所示。由图3-5不难看出：若s<t，则Si比较靠近理想直线，应选Si;若s≥t，则Ti比较靠近理想直线，应选Ti。3.2.3Bresenham画线算法令dx=x2-x1，dy=y2-y1递推公式：di的初值：当di≥0时，选Ti，当di<0时，选Si，由于只包含加、减法和左移（乘2）的运算，而且下一个像素点的选择只需检查di的符号，因此Bresenham画线算法很简单，速度也相当快。3.2.3Bresenham画线算法请看下面的推导过程结论已知，Pi(xi,yi)，xi

＝xi－1＋1，当Pi＝Ti时，yi

＝yi-1+1；当Pi＝Si时，yi

＝yi-1显然，无论下一个像素点是Ti还是Si

，x方向都增1，即xi

＝xi－1＋1，要决定的是y方向是否增1。由图3-5不难看出

:若s<t,则Si比较靠近理想直线，应选Si

；若s≥t，则Ti比较靠近理想直线，应选Ti

。设一直线段由(x1，y1)到(x2,y2)，则直线方程可表示为：(yi+1=yi+k•△X)式中，dx=x2-x1,dy=y2-y1。经变换后可表示为从(0,0)到(dx，dy)的直线，此时方程为:3.2.3Bresenham画线算法f(x)=kx因此有：因为dx>0，所以可将dx(s-t)的正负作为选择Ti

或Si的依据。若记其为di，则：(1)

3.2.3Bresenham画线算法注:Si的坐标(xi-1+1,yi-1),Ti的坐标(xi-1+1,yi-1+1)f(x)=kx(di≥0时，选Ti,否则选Si)将每一个下标加1，则有：两式相减得(2-1)因为xi-xi-1=1，所以得到递推公式：因此，当di≥0时，选Ti

。这时y方向增1，即yi-yi-1=1，则(2)3.2.3Bresenham画线算法注:当di≥0时,说明:s>=t,反之t>s问:当di≥0时，为什么选Ti?当di<0时，选Si。这时yi-yi-1=0，则：di的初值可由(1)式得出，当i=1时(x0,y0)=(0,0)即d1d1=2(x0dy-y0dx)+2dy-dx。由我们的假设，x0=0,y0=0。即3.2.3Bresenham画线算法

例:请指出用Bresenham算法扫描转换

从像素点p1（0，0）到p2（5，2）的线段时的像素位置。

解:K=dy/dx=2/5=0.4<1,故x方向增1,y方向根据d的符号判断.dx=x2-x1=5-0=5dy=y2-y1=2-0=2

d1=2*dy-dx=4-5=-1

td1=2(dy-dx)=2(2-5)=-6

td2=2*dy=2*2=4xyd00-110321-331142-552-1d1=2dy-dxd>=0,x=x+1,y=y+1di+1=d+2(dy-dx)td1=2(dy-dx)d<0,x=x+1,y=ydi+1=d+2dytd2=2*dy在上述关于斜率和起点的假设下，bresenham算法程序为:3.2.3Bresenham画线算法

bresenham算法简单，只包括加减和移位运算,并且全部为整数运算，因此效率很高，对硬件要求低。对该算法执行过程的跟踪模拟演示。1．线型2．线宽3．线色

线型一般可用16位二进制的掩膜表示，其中为0的位对应位置像素不显示。如虚线表示为：0011001100110011

线宽处理起来比想像到的可能要复杂一点，一般只能近似。

线色一般光栅扫描系统可以提供多种颜色，通常用0，1，2…等整数值表示不同颜色。详见P49--503.2.4直线属性

圆弧是图形图像中经常使用的元素。3.3.1圆的特性圆心位于原点的圆有四条对称轴：x=0，y=0，x=y和x=-y直线。若已知圆弧上一点（x,y），可以得到其关于四条对称轴的其它7个点，这种性质称为八对称性，如下图所示。本节讨论的圆的生成算法均只计算从x=0到x=y分段内（1b区域）的像素点，其余的像素位置利用八对称性即可得出。

3.3生成圆弧的常用算法38显示圆弧上的八个对称点算法voidCircle_Points(intx,inty,intcolor){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);}圆的扫描转换简单方程生成圆弧中点画圆算法简单方程产生圆弧(1)给定圆心在原点，利用其函数方程，直接离散计算为:X2+Y2=R2Y=Sqrt(R2-X2)在一定范围内，每给定一X值，可得一Y值。当X取整数时，Y须取整。缺点：浮点运算，开方，取整，不均匀。yx演示简单方程产生圆弧(2)

显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得像素坐标。但要采用浮点运算、乘法运算、取整运算。圆的极坐标方程为：42假设中心在原点，半径为整数R的圆的lb区域的1／8圆部分，现讨论如何从x＝０到x＝y顺时针确定离理想圆弧最近的像素集合。假设x坐标为xp的各像素点中与该圆弧最近者已确定，为P（xp,yp），那么，下一个与圆弧最近的像素只能是正右方的P1(xp+1,yp)，或右下方的P2（xp+1,yp-1）两者之一。令M为P1和P2的中点，易知M的坐标为（xp+1,yp-0.5）。显然，若M在圆内，则P1离圆弧近，应取为下一个像素；否则应取P2。3.3.2中点画圆算法43将M点的坐标代入圆方程F(x,y)=x2+y2-R2=0，得到判别式d：可知:d>0点M在圆外,应取p2作为下一个像素d=0点M在圆上,约定取p2作为下一个像素d<0点M在圆内,应取p1作为下一个像素即根据每一个像素计算判别式d,根据它的符号确定下一个像素.与中点画线一样,d也可以采用增量计算:3.3.2中点画圆算法在d≥0的情况下，取右下方像素P2，再下一个像素取哪个应计算:

故d的增量为2(xp-yp)+5在d<0的情况下，取正右方像素P1，再下一个像素取哪个应计算:

故d的增量为2xp+33.3.2中点画圆算法这样得到了dp的递推公式，从中可以导出圆的中点算法。当然，还需要一个初始条件。在1b区域，假定x0=0,y0=R。则3.3.2中点画圆算法如果半径是整数,则可以对d0简单取整:d0=1-R(R是整数)46voidmidpointcircle(intr,intcolor){intx,y;floatd;x=0;y=r;d=1.25-r;Circle_Points(x,y,color);while(x<=y){if(d<0)d=d+2*x+3;else{d=d+2(x-y)+5;y--;}x++;Circle_Points(x,y,color);}}使用中点画圆算法绘制一个1/8光栅圆程序voidCircle_Points(intx,inty,intcolor){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);}例:利用中点画圆算法,绘制一条圆弧:中心在坐标原点,半径R为10,从

x=0到x=y的1/8圆弧.解判别式d的初始值为:d0=1-R=1-10=-9

初始点(x0,y0)的坐标为(0,10),则

2x0=0,2y0=20

绘制初始点(0,10),并确定沿圆弧路径的其余像素位置为:xyd010-9110-6210-1310649-3598685

776在d≥0的情况下，取右下方像素,d的增量:d=d+2(x-y)+5在d<0的情况下，取正右方像素,d的增量:d=d+2x+348为了进一步提高算法的效率，可以将上面的算法中的浮点数改写成整数，将乘法运算改成加法运算，即仅用整数实现中点画圆法。使用e=d-0.25代替de0=1-R3.3.2中点画圆算法(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)

八分法画圆51解决问题：图1/8圆弧3.3.2中点画圆算法图5.13中点Bresenham画圆的原理Bresenham算法是生成圆弧算法的最有效算法之一。 设圆的半径为r。先考虑圆心在（0,0），并从x=0,y=r开始的顺时针方向的1/8圆周的生成过程。在这种情况下，x每步增加1。从x=0开始，到x=y结束。即有：

xi+1=xi+1

相应的yi+1则在两种可能中选择：

yi+1=yi，或者yi+1=yi-1

选择的原则是考察精确值y靠近yi还是靠近yi-1。3.3.3Bresenham画圆法3.3.3Bresenham画圆法y的计算式为:y2=r2-(xi+1)2令d1、d2分别为yi到y,yi-1到y的距离，可知：

d1=yi2-y2=yi2-r2+(xi+1)2d2=yi2-(yi-1)2=r2-(xi+1)2-(yi-1)2令判别式di+1=d1-d2,并代入d1、d2,则有判别式：

di+1=2(xi+1)2+yi2+(yi-1)2-2r2

判断式d的初始值为：(x0=0,y0=r,代入上式得)d0=3-2r。如果di+1>=0，则y=yi-1，选择右下方点(p2)

xi+1=xi+1,yi+1=yi-1,

di+2=2(xi+2)2+(yi-1)2+(yi-2)2-2r2=2xi2+8xi+8+yi2+yi2-2yi+1-4yi+4-2r2=di+1+

4(xi-yi)+10如果di+1<0，则y=yi，选择正右方点(p1)di+2=di+1+4xi+6通过比较距离的平方，避免平方根的计算Rd0=3-2r=3-20=-17

d1=-17+4*0+6=-11d2=-11+4*1+6=-1d3=-1+4*2+6=13d4=13+4*(3-10)+10=-5d5=-5+4*4+6=17d6=17+4*(5-9)+10=11例:Bresenham画圆算法举例圆半径r=10如果di+1>=0，则y=yi-1，选择右下方点(p2)

xi+1=xi+1,yi+1=yi-1

di+2=di+1+4(xi-yi)+10如果di+1<0，则y=yi，选择正右方点(p1)xi+1=xi+1,yi+1=yi

di+2=di+1+4xi+6Bresenham生成圆弧的程序如下：

根据算法，可得Bresenham生成圆弧的程序如下：voidBresenham_Circle(intR,intcolor){intx,y,d;x=0;y=R;d=3-2*R;while(x<y){Circle_Points(x,y,color);if(d<0)d+=4*x+6;else{d+=4*(x-y)+10;y-=1;}x++;}

if(x==y)Circle_Points(x,y,color);}voidCircle_Points(intx,inty,intcolor){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);}演示作业讲解:P36/2.4答:22*22*22=64P89/3.13.1请用伪代码程序描述使用DDA算法扫描转换一条斜率介于45°和－45°（即|m|>1)之间的直线所需的步骤。解答：假设线段的两个端点（x1,y1）和（x2，y2），且y1<y2

int

x,y=y1; floatxf=x1,m=(x2－x1)/(y2–y1)；

while(y<=y2) { x=int(xf+0.5);

setPixel(x,y);

xf=xf+m;y++;}区域dxdy1a(1)1k1b(2)1/k12a(4)-1k2b(3)-1/k13a(5)-1-k3b(6)-1/k-14a(8)1-k4b(7)1/k-157补充题:请用伪代码程序描述使用斜截式方程画一条斜率介于45°和－45°（即|m|>1）之间的直线所需的步骤。

解答：假设线段的两个端点为（x1，y1）和（x2，y2），且y1<y2 intx=x1,y=y1; floatxf, m=（y2－y1）/（x2－x1）, b=y1

－mx1; setPixel(x,y);

/*画一个像素点*/ while(y<y2) { y++; xf=(y－b)/m; x=int(xf+0.5); setPixel(x,y);}

DDA的算法基本思想

选定x2－x1和y2－y1中较大者作为步进方向（假设x2－x1较大）取该方向上的Δx为一个像素单位长，即x每次递增一个像素，然后利用前面公式计算相应的y值，把每次计算出的（xi＋l,yi＋1）经取整后顺序输出到显示器，则得光栅化后的直线。为什么取x2－xl和y2－y1中较大者步进方向？此图中Y2－Y1＝8>X2-X1=4若取△x为一个像素单位，则由yi＋1=yi＋·Δx则可能出现像素点不连续的情况若取△y为一个像素单位，则由xi＋1=xi＋·Δy则像素点连续今天作业”P893.2,3.43.2

请指出用Bresenham算法扫描转换从像素点（1，1）到（8，5）的线段时的像素位置。

dx=x2-x1=8-1=7dy=y2-y1=5-1=4d1=2*dy-dx=8-7=1td1=2(dy-dx)=2(4-7)=-6td2=2*dy=2*4=8d1=2dy-dxd>=0,x=x+1,y=y+1di+1=d+2(dy-dx)td1=2(dy-dx)d<0,x=x+1,y=ydi+1=d+2dytd2=2*dy61下周上机时间:10月27日地点:15#407机房内容:3.4区域填充区域填充即给出一个区域的定义，要求对此区域范围内的所有像素赋予指定的颜色代码。只要算法设计合理，运用着色的方法就可以使光栅图形的画面色彩逼真，更能形象而具有真实感地利用二维光栅技术显示三维图形。多边形可以是构成平面图形的几何元素，也可以是构成三维物体表面的投影。如果物体的表面是曲面，也可由适当的多边形去逼近。因此，区域填充中最常用的是多边形填色。对于区域填充来说，它要解决两个问题：①确定需要填充哪些象素，②确定用什么颜色或图案。区域填充就是将区域内的像素置成新的颜色值或图案处于一个封闭轮廓线内的所有像素点即构成一个区域3.4区域填充3.4.1区域的表示和类型在计算机图形学中，区域有两种重要的表示方法：顶点表示和点阵表示。