第三讲基本图元输出

Computergraphics山东师范大学传播学院李大锦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;ksteps;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画线算法以m1为例，如下图所示。在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当m1时3.2画线算法如果△d0则在处选择点（Xk+1,yk+1），否则选择(Xk+1,yk)。取△x=xb-xa△y=yb-ya则m=△y/△x(xa,ya）和(xb,yb）是线段的两个端点。d1d2xkXk+1Xk+2ykyk+1y当m1时3.2画线算法引入参数pk=△x△d=△x(d1-d2)=△x(2m(xk+1)-2yk+2b-1)=2△yxk-2△xyk+2△y+△x(2b-1)，①因△x0，所以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)当pk0时，yk+1-yk=1pk+1=pk+2(△y-△x)当pk0时，yk+1-yk=0pk+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算法的实现(0m1，xbxa)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);pk0时，pk+1=pk+2(△y-△x)当pk0时，pk+1=pk+2△yP0=2△y-△x3.2画线算法while(xxEnd){x++;if(p0)p+=twoDy;else{y++;＊p+=twoDyDx;}setpixel(x,y);}}对于斜率大于1的情况下，将此算法调换x,y次序即可，对于m0的情况下，将＊处的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的符号。pk0时yk+1=yk-1pk0时yk+1=yk所以pk+2xk+1+1pk0（增量为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开始，完成下列检测：假如pk0，中心在(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(xy){x++if(p0)p+=2*x+1;else{y--;p+=2*(x-y)+1;}circlePlotPoints(xCenter,yCenter,x,y);}}pk+2xk+1+1pk