第三讲：基本图元输出

2008.9.16第三讲：

基本图元的光栅化（1）

OutputPrimitives

图像可以有多种方式来描述，在光栅设备上，任何的图形都可以用一个指定亮度的各位置点的集合来表示。另一方面我们也可以用一系列基本的图形对象来表示，这些图形对象的的颜色和形状可以用像素点阵或一系列基本的几何结构来描述。例如线段和内部填充颜色的多边形，显示场景的时候，可以将像素点阵装入贞缓存，或者将定义的基本几何结构扫描转换为像素的形式写入贞缓存。一些图形软件包提供了一些基本函数用于描述输出基本几何结构，这样的基本几何结构叫做基本输出图元。利用这些基本输出图元可以组成复杂物体的显示。最简单的基本图元是点和线，基本图元的是通过指定图元的坐标、颜色等要显示的信息来定义的。将这样定义的基本图元按照其属性转换为像素点阵的过程称为光栅化3.1点和线在CRT显示器中，点的绘制是将程序中点的坐标转化为屏幕上确定的位置，当扫描至该位置点时，开启电子枪点亮该点荧光。在随即扫描显示器中，点在显示列表中定义，根据点的坐标产生偏转电压，控制电子枪的偏转并点亮该点的荧光。线的绘制是根据定义线的两个端点，插值计算中间点的位置，并点亮这些中间点。在随即扫描设备中，可以产生连续的中间点绘制出光滑的线段。在CRT设备中，需要将直线离散化成若干个点，根据线段的直线方程计算出这些离散的中间点位置，并在扫描这些点的位置上开启电子枪点亮荧光屏。3.1点和线线的离散化表示点在屏幕上的位置坐标用像素为单位，点的像素坐标只能是整数。

所以，通过计算得到的中间点在屏幕上的坐标都要取整数，如在线段上某点上计算的坐标是（10.48，20.51），则点在屏幕上的位置是（10，21）。3.2画线算法任何图元的绘制算法都要遵循的一个原则:尽量使绘制速度加快，加快绘制速度的一个途径就是尽量减少浮点运算和乘除运算。绘制线的基本思想是沿水平或垂直方向，依次增加一个像素的长度，计算出相应的另一个方向个上的增量，从而确定线上的某一个点的屏幕坐标，电子枪点亮该点。3.2.1DDA算法（digitaldrflerentialanalyzer）

假设定义直线段的两个端点的坐标为（x1,y1),（x2,y2），直线的斜截方程为

y=mx+b3.2画线算法

得：ｍ＝（y2-y1）／（x2-x1）

b=y1-mx1设在ｘ方向上的增量为⊿x，则

⊿ｙ＝ｍ⊿x①⊿x＝⊿ｙ/ｍ②若|m|<=1则以⊿x作为步进的基础，取⊿x=1，计算相应的y坐标，由①得

yk+1=yk+m|m|<=1，按x轴方向采样xy3.2画线算法

若|m|>1,则以⊿y为步进的基础，取⊿y=1，计算相应的x坐标，由②得

xk+1=xk+1/m假设已经定义了底层函数Setpixel(x,y)，此函数用于向贞缓存中坐标为（x,y）处按指定的颜色写入颜色值，则DDA算法可描述如下。|m|>1，按y轴方向采样3.2画线算法voidlineDDA(intxa,intya,intxb,intyb){intdx=xb-xa,；

intdy=yb-ya,；intsteps,k;floatxincrement,yincrement；floatx=xa,;floaty=ya;if(abs(dx)>abs(dy)steps=abs(dx);elsesteps=abs(dy);xIncrement=dx/

(float)steps;yIncrement=dy/(float)steps;setpixel(xa,ya)；for(k=0;k<steps;k++){x+=xIncrment;y+=yIncrement;setpixel(round(x),round(y))；//函数round(x)为将x四舍五入

}}DDA算法的特点？——消除了乘法，但是有误差积累和浮点计算。3.2画线算法3.2.2Bresenham算法

Bresenham算法的优点是指使用整形的增量来计算点的坐标，所以速度更快，也易于硬件实现。123456754321

以斜率小于1的直线为例，如右图是（1，1）到（6，4）的一条直线段，当我们沿x轴每次递增1采样像素，在绘制第二个点时，需要选择是（2，2）还是（2，1），Bresenham算法就是计算一个决策参数用于判断哪一个像素点离直线最近。3.2画线算法以m<1为例，如下图所示。在Xk+1处

y=mXk+1+b=m(Xk+1)+b；

d1=y-yk=m(xk+1)+b-yk；

d2=yk+1

–y=yk+1-m(xk+1)-b；⊿d=d1-d2=2m(xk+1)-2yk+2b-1；

d1d2xkXk+1Xk+2ykyk+1y当m<1时3.2画线算法

如果△d>0则在处选择点（Xk+1,

yk+1），否则选择(Xk+1,

yk)。取△x=xb-xa△y=yb-ya则m=△y/△x(xa,

ya）和(xb,

yb）是线段的两个端点。

d1d2xkXk+1Xk+2ykyk+1y当m<1时3.2画线算法引入参数

pk=△x△d=△x(d1-d2)=△x(2m(xk+1)-2yk+2b-1)=2△yxk-2△xyk+2△y+△x(2b-1)，①因△x>0，所以pk和△d同号，可作为判断△d正负号的参数。这里2△y+△x(2b-1）是常数，设

c=2△y+△x(2b-1)由①得

pk=△x△d=2△yxk-2△xyk+c②同样：pk+1=2△yxk+1-2△xyk+1+cpk+1–pk=2△y(xk+1-xk）-2△x(yk+1-yk)△x=xb-xa△y=yb-yam=△y/△x3.2画线算法xk+1=xk+1pk+1=pk+2△y-2△x(yk+1-yk)

当pk>0时，yk+1-yk=1

pk+1=pk+2(△y-△x)

当pk<0时，yk+1-yk=0

pk+1=pk+2△y

根据②式可得

p0=2△yxa-2△x(mxa+b)+2△y+△x(2b-1)==2△yxa-2△x(△y/△x)xa-2△xb+2△y+2△xb-△x=2△y-△xp0是从线段的起点x0后的第一个采样点的决策值

pk+1–pk=2△y(xk+1-xk)-2△x(yk+1-yk)3.2画线算法Bresenham算法的优点从pk的计算公式可以看出，Bresenham算法只进行加减运算，并且只进行的整数的运算，所以运算速度很高，并且易于用硬件实现。3.2画线算法Bresenham算法的实现(0<m<1，xb>xa)

voidLineBres(intxa,intya,intxb,intyb){intdx=xb-xa,dy=yb-ya;intp=2*dy-dx;inttwoDy=2*dy；

inttwoDyDx=2*(dy-dx);intx=xa,y=ya,xEnd;xEnd=xb;setpixel(x,y);

pk>0时，pk+1=pk+2(△y-△x)当pk<0时，pk+1=pk+2△yP0=2△y-△x3.2画线算法while(x<xEnd){x++;if(p<0)p+=twoDy;else{y++;＊

p+=twoDyDx;}setpixel(x,y);}}对于斜率大于1的情况下，将此算法调换x,y次序即可，对于m<0的情况下，将＊处的y++改为y--即可,而对于垂直和水平线可直接画出线3.3贞缓冲的写入前面我们用setpixel(x,y)函数在贞缓存的(x,y)处写入颜色亮度。贞缓存在逻辑上是一个二维数组，物理上是一个一维的连续空间，所以在setpixel(x,y)中要计算具体的内存地址。下面介绍在扫描过程中贞缓存的内存地址计算。设（xmax，ymax)是光栅显示器的最大横坐标和最大纵坐标（也是贞缓存矩阵的宽度和高度）。任意点（x,y)的地址为：

addr(x,y)=addr(0,0)+y(xmax+1)+x沿扫描线移动，像素(x+1,y)处的帧缓冲器地址可从位置(x,y)的地址做偏移来计算：

addr(x+1,y)=addr(x,y)+13.3贞缓冲的写入从(x,y)对角跳到下一条扫描线，(x+1,y+1)的帧缓冲器地址的计算公式为：

addr(x+1,y+1)=addr(x,y)+xmax+2从(x,y)对竖直方向跳到下一条扫描线(x,y+1)的帧缓冲器地址的计算公式为：

addr(x,y+1)=addr(x,y)+xmax+1

这样，在光栅扫描过程中按扫描顺序，以增量的方式计算贞缓存地址，就避免了乘法计算。3.4圆的生成算法圆是图形中常用的图形元素，多数的图形软件中都包含了生成圆和圆弧的过程。圆的方程：

(x-xc)2+(y-yc)2=r2圆的最简单的绘制方法是沿一个方向递增，计算出另一个方向上的坐标。

y=(r2-(x-xc)2)½+yc

但是这样画出来的原在某些位置有很多断点，计算量也很大。3.4圆的生成算法另一种方法是采用极坐标法

x=rcosθ y=rsinθ 0≤θ≤360θ按一定的增量步进，θ较大时，可以用沿着圆弧画直线来代替圆弧。为了减少计算量，可以只画出1/4圆或1/8圆，其他部分按对称计算得到。但是这种方法同样计算量非常大。3.4.1中点画圆算法和光栅画线算法中一样，以单位间隔取样并在每个步长中确定离指定圆最近的像素位置。3.4圆的生成算法

只考虑1/8圆，x从０到（R/2）1/2结束.、首先，定义一个圆函数：

fcircle(x,y)=x2+y2-r2①则可按如下规则判断任意点（x,y)在圆上的位置

<0(x,y)位于圆边界内fcircle(x,y)=0(x,y)位于圆边界上

>0(x,y)位于圆边界外3.4圆的生成算法如图，为了求下一个扫描点的位置，将下一个扫描点的两个候选点(xk+1,yk)，（xk+1,yk-1）的中点坐标(xk+1,yk-0.5)代入①式，如果在在圆外或圆上，则选择(xk+1,yk），否则选（xk+1,yk-1）引入决策参数pkpk=fcircle(xk+1,yk-0.5)=xk+12+(yk-0.5)2-r2②

同样：

pk+1=(xk+1+1)2+(yk+1-0.5)2-r2③候选点中点3.4圆的生成算法②-③得pk+1=pk+2xk+1+(y2k+1-y2k)-(yk+1-yk)+1很明显，yk+1的值取决于pk的符号。

pk>0时yk+1=yk-1pk<0时yk+1=yk所以

pk+2xk+1+1pk<0（增量为2xk+1+1）pk+1=pk+2xk+1+1-2yk+1pk≥0（增量为2xk+1-2yk+1+1）3.4圆的生成算法起始位置(x0,y0)=(0,r)处的决策参数为

p0=fcircle(1,r-0.5)=5/4–r如果r为整数的话，可以舍入

p0=1–r

这是因为其后计算pk时增量都是整数，所以这样的舍入不影响pk的符号。中点画圆算法的步骤：

1.输入圆半径r和圆心(xc,yc),并得到圆心在原点的圆周上的第一点为:(x0,y0)=(0,r)2.计算决策参数的初始值：p0=5/4–r3.4圆的生成算法3.在每个xk位置处，从k=0开始，完成下列检测：假如pk<0，中心在(0,0)的圆的下一个点为(xk+1,yk)，且

pk+1=pk+2xk+1+1

否则，圆的下一个点为(xk+1,yk-1)，且

pk+1=pk+2xk+1+1-2yk+1

其中：2xk+1=2xk+1，2yk+1=2yk-24.确定在其它7个8分圆中的对称点

5.将每个计算出的像素位置(x,y)移动到中心在(xc,yc)的圆路径上，并画坐标值：

x=xc+xy=yc+y6.重复步骤3到5，直至x≥y。3.4圆的生成算法中点圆算法的C实现：voidcircleMidpoint(intxCenter,intyCenter,intradius){intx=0;inty=radius;intp=1-radius;circlePlotPoints(xCenter,yCenter,x,y);//画出第一个点

while(x<y){x++if(p<0)p+=2*x+1;else{y--;p+=2*(x-y)+1;}circlePlotPoints(xCenter,yCenter,x,y);}}

pk+2xk+1+1pk<0pk+1=pk+2xk+1+1-2yk+1pk≥03.4圆的生成算法voidcirclePlotPoints(intxCenter,intyCenter,intx,inty){setpixel(xCenter+x,yCenter+y);setpixel(xCenter-x,yCenter+y);setpixel(xCenter+x,yCenter-y);setpixel(xCenter-x,yCenter-y);setpixel(xCenter+y,yCenter+x);setpixel(xCenter-y,yCenter+x);setpixel(xCenter+y,yCenter-x);setpixel(xCenter-y,yCenter-x);}3.5椭圆的生成算法椭圆的特点椭圆被定义为到两个定点(焦点)的距离之和等于常数的点的集合。椭圆上任意点p(x,y)到两个焦点的距离记为d1和d2，那么，椭圆方程可表示为：

d1+d2=常数

设两个焦点坐标F1=(x1,y1)和

F2=(x2,y2)来表示的椭圆方程：

[(x-x1)2+(y-y1)2]1/2+[(x-x2)2+(y-y2)2]1/2=常数本节内容不作要求3.5椭圆的生成算法标准位置的椭圆：长轴和短轴与X和Y轴平行，椭圆中心可在(xc,yc)。标准位置椭圆方程：

[(x-xc)/rx]2+[(y-yc)/ry]2=1

①

其中：rx

和ry分别为长半轴和短半轴。在平面坐标系中椭圆在四个象限中是对称的，所以只需要计算完整一个象限内的点。椭圆中点算法

只考虑椭圆原心在坐标原点的标准椭圆，通过将计算后的坐标平移可以得到圆心不在坐标系原点的椭圆。和圆的中点算法相似，通过计算两个候选点的中点是否在圆内来判断两个候选点中哪一个离椭圆最近。3.5椭圆的生成算法安椭圆上切线的斜率将第一象限的椭圆划分为两个递增区域区域，如图，区域1，沿x方向依次递增，区域2沿y方向依次递增。两个区域的分界点是该点斜率为-1定义椭圆函数，

fellipse(x,y)=[(x-xc)/rx]2+[(y-yc)/ry]2-1

圆心为（0,0)

fellipse(x,y)=ry2x2+rx2y2-rx2ry2② <0(x,y)位于椭圆边界内

fellipse(x,y)=0(x,y)位于椭圆边界上

>0(x,y)位于椭圆边界外斜率为-1123.5椭圆的生成算法由②式两边对x求导数得

dy/dx=-ry2x/rx2y

在椭圆上斜率为-1的点即为两个递增区域的分界点所以从区域1转为区域2的分界点为

2ry2x=2rx2y

当2ry2x<2rx2y时位于1区域，当2ry2x>2rx2y时位于2区域斜率为-1123.5椭圆的生成算法首先考虑区域1的情况和圆的中点画法相同，引入决策参数

p1k=fellipse(xk+1,yk-0.5)=ry2(xk+1)2+rx2(yk-0.5)2-rx2ry2③同样

p1k+1=p1k+2ry2(xk+1)+ry2+rx2[(yk+1-0.5)2-(yk-0.5)2]其中yk+1的值取决于p1k的符号p1k+1=p1k+2ry2xk+1+ry2

当p1k<0p1k+1=p1k+2ry2xk+1+ry2-2rx2yk+1当p1k≥0将(x0,y0)=(0,ry)带入③式求得初始位置的参数p10=fellipse(1,ry-0.5)=ry2-rx2ry+rx2/43.5椭圆的生成算法用同样的方法可以计算出区域2内的决策参数公式

p20=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry2yk+1=yk-1p2k+1=p2k-2rx2yk+1+rx2,当p2k>0p2k+1=p2k-rx2yk+1+rx2+2ry2xk+1当p2k≤0中点椭圆算法步骤：

1.输入rx,ry和椭圆中心(xc,yc)，并得到中心在原点的椭圆上的第一个点。

2.计算第一分象限的第1段椭圆曲线的决策参数的初值：

p10=ry2-rx2ry+rx2/43.5椭圆的生成算法3.在第1段曲线的每个xk处，从k=0开始，完成下列测试：假如当p1k<0，则下一个点为(xk+1,yk+1)=(xk+1,yk)，且：p1k+1=p1k+2ry2(xk+1)+ry2，否则，下一个点为(xk+1,yk+1)=(xk+1,yk-1)，且：p1k+1=p1k+2ry2(xk+1)+ry2-2rx2(yk-1)。且循环至2ry2x≥2rx2y，循环结束得到最后点(x0,y0)。4.使用第1段曲线计算最后得到的点(x0,y0)，来计算第2段曲线的初始决策参数：

p20=ry2(x0+0.5)2+rx2(y0-1)2-rx2ry25.在第2段曲线的每个yk处，从k=0开始，完成下列检测：假如p2k>0，则下一个点为(xk+1,yk+1)=(xk,yk-1)，且p2k+1=p2k-2rx2(yk-1)+rx2，否则下一个点为(xk+1,yk+1)=(xk+1,yk-1)，且p2k+1=p2k-2rx2(yk-1)+rx2+2ry2(xk+1)，且循环至2rx2y=0即y=0。6.确定其它三个分象限中对称的点。7.将每个计算出像素位置(x,y)移到中心在(xc,yc)的椭圆轨迹上，并按坐标画点：x=x+xc，y=y+yc。3.6其他曲线生成方法各种曲线在建模、动画运动轨迹的指