第三讲：基本图元输出

1、山东师范大学传播学院 李大锦2008.9.16 图像可以有多种方式来描述，在光栅设备上，任何的图像可以有多种方式来描述，在光栅设备上，任何的图形都可以用一个指定亮度的各位置点的集合来表示。另图形都可以用一个指定亮度的各位置点的集合来表示。另一方面我们也可以用一系列基本的图形对象来表示，这些一方面我们也可以用一系列基本的图形对象来表示，这些图形对象的的颜色和形状可以用像素点阵或一系列基本的图形对象的的颜色和形状可以用像素点阵或一系列基本的几何结构来描述。例如线段和内部填充颜色的多边形，显几何结构来描述。例如线段和内部填充颜色的多边形，显示场景的时候，可以将像素点阵装入贞缓存，或者将定义示场景的时

2、候，可以将像素点阵装入贞缓存，或者将定义的基本几何结构扫描转换为像素的形式写入贞缓存。一些的基本几何结构扫描转换为像素的形式写入贞缓存。一些图形软件包提供了一些基本函数用于描述输出基本几何结图形软件包提供了一些基本函数用于描述输出基本几何结构，这样的基本几何结构叫做构，这样的基本几何结构叫做基本输出图元基本输出图元。利用这些基。利用这些基本输出图元可以组成复杂物体的显示。最简单的基本图元本输出图元可以组成复杂物体的显示。最简单的基本图元是点和线，基本图元的是通过指定图元的坐标、颜色等要是点和线，基本图元的是通过指定图元的坐标、颜色等要显示的信息来定义的。将这样定义的基本图元按照其属性显示的信息

3、来定义的。将这样定义的基本图元按照其属性转换为像素点阵的过程称为转换为像素点阵的过程称为光栅化光栅化3.13.1点和线点和线 在在CRT显示器中，点的绘制是将程序中点的坐标转化显示器中，点的绘制是将程序中点的坐标转化为屏幕上确定的位置，当扫描至该位置点时，开启电为屏幕上确定的位置，当扫描至该位置点时，开启电子枪点亮该点荧光。在随即扫描显示器中，点在显示子枪点亮该点荧光。在随即扫描显示器中，点在显示列表中定义，根据点的坐标产生偏转电压，控制电子列表中定义，根据点的坐标产生偏转电压，控制电子枪的偏转并点亮该点的荧光。枪的偏转并点亮该点的荧光。 线的绘制是根据定义线的两个端点，插值计算中间点线的绘制

4、是根据定义线的两个端点，插值计算中间点的位置，并点亮这些中间点。在随即扫描设备中，可的位置，并点亮这些中间点。在随即扫描设备中，可以产生连续的中间点绘制出光滑的线段。以产生连续的中间点绘制出光滑的线段。在在CRT设备设备中，需要将直线离散化成若干个点，根据线段的直线中，需要将直线离散化成若干个点，根据线段的直线方程计算出这些离散的中间点位置，并在扫描这些点方程计算出这些离散的中间点位置，并在扫描这些点的位置上开启电子枪点亮荧光屏。的位置上开启电子枪点亮荧光屏。3.1点和线点和线线的离散化表示线的离散化表示点在屏幕上的位置坐标用像素为单位，点的像素坐标只点在屏幕上的位置坐标用像素为单位，点的像素

5、坐标只能是整数。能是整数。 所以，通过计算得到的中间点在屏幕上的坐标所以，通过计算得到的中间点在屏幕上的坐标都要取整数，如在线段上某点上计算的坐标是都要取整数，如在线段上某点上计算的坐标是（10.48，20.51），则点在屏幕上的位置是（），则点在屏幕上的位置是（10，21）。）。3.2 画线算法画线算法 任何图元的绘制算法都要遵循的一个原则任何图元的绘制算法都要遵循的一个原则:尽量使绘尽量使绘制速度加快，加快绘制速度的一个途径就是制速度加快，加快绘制速度的一个途径就是尽量减少尽量减少浮点运算和乘除运算浮点运算和乘除运算。绘制线的基本思想是沿水平或绘制线的基本思想是沿水平或垂直方向，依次增加一

6、个像素的长度，计算出相应的垂直方向，依次增加一个像素的长度，计算出相应的另一个方向个上的增量，从而确定线上的某一个点的另一个方向个上的增量，从而确定线上的某一个点的屏幕坐标，电子枪点亮该点。屏幕坐标，电子枪点亮该点。3.2 .1 DDA算法（算法（digital drflerential analyzer） 假设定义直线段的两个端点的坐标为（假设定义直线段的两个端点的坐标为（x1,y1),),（x2,y2），直线的斜截方程为），直线的斜截方程为 y=mx+b3.2 画线算法画线算法 得：得：（y2-y1 ）（）（x2-x1） b=y1-mx1设设 在方向上的增量为在方向上的增量为x，则，则 x

7、 x / 若若|m|=1则以则以x作为步进的基础，取作为步进的基础，取x=1，计算相，计算相应的应的y坐标，由坐标，由得得 yk+1=yk+m|m|1,则以则以y为步进的基础，取为步进的基础，取y=1，计算相应，计算相应的的x坐标，由坐标，由得得 xk+1=xk+1/m假设已经定义了底层函数假设已经定义了底层函数Setpixel(x,y)，此函数用于向，此函数用于向贞缓存中坐标为（贞缓存中坐标为（x,y）处按）处按指定的颜色写入颜色值，则指定的颜色写入颜色值，则DDA算法可描述如下。算法可描述如下。|m|1，按，按y轴方向采样轴方向采样3.2 画线算法画线算法void lineDDA (int

8、 xa, int ya, int xb, int yb) int dx = xb - xa,； int dy = yb - ya,；int steps, k; float xincrement, yincrement；float x = xa,; float y = ya; if (abs (dx) abs(dy) steps = abs (dx) ; else steps = abs (dy); xIncrement = dx / (float) steps; yIncrement = dy /(float) steps; setpixel (xa, ya ) ； for (k=0; kst

9、eps; k+) x += xIncrment; y += yIncrement; setpixel (round(x), round(y)；/函数函数round(x)为将为将x四舍五入四舍五入 DDA算法的特点？算法的特点？消除了乘法，但是有误差积累消除了乘法，但是有误差积累和浮点计算。和浮点计算。3.2 画线算法画线算法3.2.2 Bresenham算法算法 Bresenham算法的优点是指使用整形的增量来计算算法的优点是指使用整形的增量来计算点的坐标，所以速度更快，也易于硬件实现。点的坐标，所以速度更快，也易于硬件实现。 1 2 3 4 5 6 75 4 3 2 1 以斜率小于以斜率小于

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

11、1)-b ； d =d1-d2=2m(xk+1)-2yk+2b-1 ； d1d2xkXk+1Xk+2ykyk+1y当 m0则在处选择点（则在处选择点（ Xk+1, yk+1），否则选择），否则选择(Xk+1, yk)。 取取x=xb-xa y=yb-ya 则则m= y/ x (xa , ya）和）和(xb , yb）是线段的两个端点。）是线段的两个端点。 d1d2xkXk+1Xk+2ykyk+1y当 m0，所以，所以pk和和d同号，可作为判断同号，可作为判断d 正负正负号的参数。这里号的参数。这里2y+x(2b-1）是常数，设）是常数，设 c= 2y+x(2b-1) 由由 得得 pk= xd

12、=2yxk-2xyk+c 同样同样 ： pk+1=2yxk+1-2xyk+1+c pk+1 pk= 2y(xk+1-xk）-2x(yk+1-yk)x=xb-xa y=yb-ya m= y/ x3.2 画线算法画线算法 xk+1=xk+1 pk+1=pk+ 2y-2x(yk+1-yk) 当当pk0时，时，yk+1-yk=1 pk+1=pk+2(y-x) 当当pk0时，时，yk+1-yk=0 pk+1=pk+2y 根据根据式可得式可得 p0= 2yxa-2x(mxa+b)+ 2y+x(2b-1) = = 2yxa-2 x(y/ x )xa- 2x b + 2y+2xb -x = 2y-xp0是从线

13、段的起点是从线段的起点x0 后的第一个采样点的决策值后的第一个采样点的决策值 pk+1 pk= 2y(xk+1-xk)-2x(yk+1-yk)3.2 画线算法画线算法 Bresenham算法的优点算法的优点 从从pk的计算公式可以看出，的计算公式可以看出， Bresenham算法只进行算法只进行加减运算，并且只进行的整数的运算，所以运算速度加减运算，并且只进行的整数的运算，所以运算速度很高，并且易于用硬件实现。很高，并且易于用硬件实现。3.2 画线算法画线算法Bresenham算法的实现算法的实现(0mxa) void LineBres(int xa,int ya,int xb,int yb)

14、 int dx=xb-xa,dy=yb-ya; int p=2*dy-dx; int twoDy=2*dy； int twoDyDx=2*(dy-dx); int x=xa,y=ya, xEnd; xEnd=xb; setpixel(x,y); pk0时，时， pk+1=pk+2(y-x)当当pk0时，时， pk+1=pk+2yP0=2y-x3.2 画线算法画线算法 while(xxEnd) x+; if(p0 ) p+=twoDy; else y+; p+=twoDyDx; setpixel(x,y); u对于斜率大于对于斜率大于1的情况下，将此算法调换的情况下，将此算法调换x,y次序次序即

15、可，对于即可，对于m0的情况下，将的情况下，将处的处的y+改为改为y-即可即可,而对于垂直和水平线可直接而对于垂直和水平线可直接 画出线画出线3.3 贞缓冲的写入贞缓冲的写入 前面我们用前面我们用setpixel(x,y)函数在贞缓存的函数在贞缓存的(x,y)处写入颜处写入颜色亮度。贞缓存在逻辑上是一个二维数组，物理上是色亮度。贞缓存在逻辑上是一个二维数组，物理上是一个一维的连续空间，所以在一个一维的连续空间，所以在setpixel(x,y)中要计算具中要计算具体的内存地址。下面介绍在扫描过程中贞缓存的内存体的内存地址。下面介绍在扫描过程中贞缓存的内存地址计算。地址计算。 设（xmax，yma

16、x) )是光栅显示器的最大横坐标和最是光栅显示器的最大横坐标和最大纵坐标（也是贞缓存矩阵的宽度和高度）。任意点大纵坐标（也是贞缓存矩阵的宽度和高度）。任意点（x,y)x,y)的地址为：的地址为： addr(x,y)=addr(0,0)+y(xmax+1)+xu沿扫描线移动，像素沿扫描线移动，像素(x+1,y)处的帧缓冲器地址可从位处的帧缓冲器地址可从位置置(x,y)的地址做偏移来计算：的地址做偏移来计算： addr(x+1,y)= addr(x,y)+13.3 贞缓冲的写入贞缓冲的写入u从从(x,y)对角跳到下一条扫描线，对角跳到下一条扫描线，(x+1,y+1)的帧缓冲的帧缓冲器地址的计算公式

17、为：器地址的计算公式为： addr(x+1,y+1)=addr(x,y)+xmax+2u从从(x,y)对竖直方向跳到下一条扫描线对竖直方向跳到下一条扫描线(x,y+1)的帧缓的帧缓冲器地址的计算公式为：冲器地址的计算公式为： addr(x,y+1)=addr(x,y)+xmax+1 这样，在光栅扫描过程中按扫描顺序，以增量的这样，在光栅扫描过程中按扫描顺序，以增量的方式计算贞缓存地址，就避免了乘法计算。方式计算贞缓存地址，就避免了乘法计算。3.4圆的生成算法圆的生成算法 圆是图形中常用的图形元素，多数的图形软件中都包圆是图形中常用的图形元素，多数的图形软件中都包含了生成圆和圆弧的过程。含了生成

18、圆和圆弧的过程。 圆的方程：圆的方程： (x-xc)2+(y-yc)2=r2 圆的最简单的绘制方法是沿一个方向递增，计算出另圆的最简单的绘制方法是沿一个方向递增，计算出另一个方向上的坐标。一个方向上的坐标。 y=(r2- (x-xc)2) +yc 但是这样画出来的原在某些但是这样画出来的原在某些 位置有很多断点，计算量也位置有很多断点，计算量也 很大。很大。3.4圆的生成算法圆的生成算法 另一种方法是采用极坐标法另一种方法是采用极坐标法 x=rcosy=rsin 0360 按一定的增量步进，按一定的增量步进，较大时，可以用沿着圆弧较大时，可以用沿着圆弧画直线来代替圆弧。为了减少计算量，可以只画

19、出画直线来代替圆弧。为了减少计算量，可以只画出1/4圆或圆或1/8圆，其他部分按对称计算得到。但是这种圆，其他部分按对称计算得到。但是这种方法同样计算量非常大。方法同样计算量非常大。3.4.13.4.1中点画圆算法中点画圆算法 和光栅画线算法中一样，以单位间隔取样并在每和光栅画线算法中一样，以单位间隔取样并在每个步长中确定离指定圆最近的像素位置个步长中确定离指定圆最近的像素位置。3.4圆的生成算法圆的生成算法 只考虑只考虑1/8圆，圆，x从到（从到（R/2）1/2结束结束.、首先，定义一个圆函数：首先，定义一个圆函数： fcircle(x,y)=x2+y2-r2 则可按如下规则判断任意点（则可

20、按如下规则判断任意点（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）引入决策参数引入决策参数pk pk= 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 候选点中点候选

21、点中点3.4圆的生成算法圆的生成算法- 得得pk+1=pk+2xk+1+(y2k+1-y2k)-(yk+1-yk)+1很明显，很明显，yk+1的值取决于的值取决于pk的符号。的符号。 pk0 时时yk+1=yk-1 pk0 时时yk+1=yk所以所以 pk+2xk+1+1 pk0 （增量为（增量为2xk+1+1 ）pk+1= pk+2xk+1+1-2yk+1 pk0 （增量为（增量为2xk+1-2yk+1 +1 ）3.4圆的生成算法圆的生成算法起始位置起始位置(x0,y0)=(0,r)处的决策参数为处的决策参数为 p0= fcircle(1,r-0.5)=5/4 r如果如果r为整数的话，可以舍

22、入为整数的话，可以舍入 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)的圆

23、的下一个点为的圆的下一个点为(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-2 4. 确定在其它确定在其它7个个8分圆中的对称点分圆中的对称点 5. 将每个计算出的像素位置将每个计算出的像素位置(x,y)移动到中心在移动到中心在(xc, yc)的的圆路径上，并画坐标值：圆路径上，并画坐标值： x=xc+x y=yc+y 6. 重复步骤重复步骤3到到5，直至，直至xy。3.4圆的生成算法圆的生成算法中点圆算法的中

24、点圆算法的C实现：实现：void circleMidpoint( int xCenter, int yCenter, int radius) int x=0; int y=radius; int p=1-radius; circlePlotPoints( xCenter,yCenter,x,y); /画出第一个点画出第一个点 while(xy) x+ if (p0) p+=2*x+1; else y-; p+=2*(x-y)+1; circlePlotPoints( xCenter, yCenter,x,y); pk+2xk+1+1 pk0 pk+1= pk+2xk+1+1-2yk+1 pk0

25、 3.4圆的生成算法圆的生成算法void circlePlotPoints(int xCenter,int yCenter,int x,int y) 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

26、(xCenter-y,yCenter-x);3.5椭圆的生成算法椭圆的生成算法 椭圆的特点椭圆的特点 椭圆被定义为到两个定点椭圆被定义为到两个定点(焦点焦点)的距离之和等于常数的距离之和等于常数的点的集合。椭圆上任意点的点的集合。椭圆上任意点p(x,y)到两个焦点的距离记为到两个焦点的距离记为d1和和d2，那么，椭圆方程可表示为：，那么，椭圆方程可表示为： d1+d2=常数常数 设两个焦点坐标设两个焦点坐标F1=(x1,y1)和和 F2=(x2,y2)来表示的椭圆方程：来表示的椭圆方程：(x-x1)2+(y-y1)21/2+ (x-x2)2+(y-y2)21/2=常数常数本节内容不本节内容不作

27、要求作要求3.5椭圆的生成算法椭圆的生成算法 标准位置的椭圆：长轴和短轴与标准位置的椭圆：长轴和短轴与X和和Y轴平行，椭圆中心轴平行，椭圆中心可在可在(xc,yc)。标准位置椭圆方程：。标准位置椭圆方程： (x-xc)/rx2+(y-yc)/ry2=1 其中：其中：rx 和和ry分别为长半轴和短半轴。分别为长半轴和短半轴。 在平面坐标系中椭圆在四个象限中是对称的，所以只需要在平面坐标系中椭圆在四个象限中是对称的，所以只需要计算完整一个象限内的点。计算完整一个象限内的点。 椭圆中点算法椭圆中点算法 只考虑椭圆原心在坐标原点的标准椭圆，通过将计算只考虑椭圆原心在坐标原点的标准椭圆，通过将计算后的坐

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

29、定义椭圆函数， f ellipse (x, y)=(x-xc)/rx2+(y-yc)/ry2-1 圆心为圆心为（0,0) f ellipse (x, y)=ry2x2+ rx2y2- rx2ry2 0 (x,y)位于椭圆边界外位于椭圆边界外斜率为-1123.5椭圆的生成算法椭圆的生成算法 由式两边对由式两边对x求导数得求导数得 dy/dx=-ry2x/rx2y 在椭圆上斜率为在椭圆上斜率为-1的点即为两个递增区域的分界点的点即为两个递增区域的分界点 所以从区域所以从区域1转为区域转为区域2的分界点为的分界点为 2ry2x=2rx2y 当当2ry2x2rx2y时位于时位于2区区域域斜率为-112

30、3.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 当当p1k0 p2k+1=p2k-rx2yk+1+rx2+2ry2xk+1 当当p2k0 中点椭圆算法步骤：中点椭圆算法步骤

31、： 1. 输入输入rx, ry和椭圆中心和椭圆中心(xc,yc)，并得到中心在原点的，并得到中心在原点的椭圆上的第一个点。椭圆上的第一个点。 2. 计算第一分象限的第计算第一分象限的第1段椭圆曲线的决策参数的初段椭圆曲线的决策参数的初值：值： p10= ry2 -rx2ry+rx2/43.5椭圆的生成算法椭圆的生成算法3. 在第在第1段曲线的每个段曲线的每个xk处，从处，从k=0开始，完成下列测试：假如当开始，完成下列测试：假如当p1k0，则下一个点为，则下一个点为(xk+1,yk+1)= (xk,yk-1)，且，且p2k+1= p2k-2rx2 (yk-1)+ rx2，否则下一个点为，否则下

32、一个点为(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其他曲线生成方法其他曲线生成方法 各种曲线在建模、动画运动轨迹的指定、功能和数据图表、以及其他图形应用中非常有用，常见的曲线除了介绍的圆和椭圆，还有圆锥曲线、三角函数曲线、概率分布曲线、样条曲线和