计算机图形学-基本图形的生成与显示

1、2p如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、圆、椭圆、多边形域、字符串及其相关属性等）。第第2 2章章 基本图形的生成与显示基本图形的生成与显示3p图形生成的概念p直线段的扫描转换p圆的扫描转换p椭圆的扫描转换第第2 2章章 基本图形的生成与显示基本图形的生成与显示u图形的生成：是在指定的图形的生成：是在指定的输出设备上，根据坐标描输出设备上，根据坐标描述构造二维几何图形。述构造二维几何图形。u图形的扫描转换图形的扫描转换：在光栅：在光栅显示器等数字设备上确定显示器等数字设备上确定一个最佳逼近于图形的一个最佳逼近于图形的像像素素集的过程。集的过程。 4图图1. 用像素

2、点集逼近直线用像素点集逼近直线图形生成和扫描转换的概念图形生成和扫描转换的概念1 直线的扫描转换直线的扫描转换u直线的绘制要求直线的绘制要求 （1 1）直线要直；）直线要直； （2 2）直线的端点要准确，无断裂；）直线的端点要准确，无断裂； （3 3）直线的亮度、色泽要均匀；）直线的亮度、色泽要均匀； （4 4）画线的速度要快；）画线的速度要快； （5 5）具有不同的色泽、亮度、线型等。）具有不同的色泽、亮度、线型等。5直线的扫描转换直线的扫描转换6o 在屏幕像素点阵中点亮最佳逼近于理想直线的在屏幕像素点阵中点亮最佳逼近于理想直线的像素点集的过程像素点集的过程o解决的问题解决的问题：给定直线两

3、端点：给定直线两端点P0(x0,y0)和和P1(x1,y1)，确定其他像素点，画出该直线确定其他像素点，画出该直线o 数值微分法数值微分法o 中点画线算法中点画线算法o Bresenham算法算法数值微分法(DDA法)bkxy7直线直线P0 P1的斜率：的斜率：kxxyyxydxdy0101图图2. DDA算法原理算法原理从从P0 到到P1的点坐标满足的点坐标满足Pi (x, round(y+0.5)浮点乘法，假发，取整运算浮点乘法，假发，取整运算数值微分法(DDA法) 迭代增量计算公式： 对点阵而言，相邻的点，x和y只能为1(-1)或08 11yyyxxxiiii数值微分法数值微分法(DDA

4、法法)9o |k|1的情况，的情况，x方向为主位移方向，方向为主位移方向，x=1：p|k|1的情况，的情况，y方向为主位移方向，方向为主位移方向，y=1 ： 111kyyyyxxxxiiiiii 1111iiiiiiyyyykxxxxvoid DDALine(float x1,float y1, float x2,float y2,int color, HDC hdc) float k,dx,dy,x,y; dx=x2-x1; dy=y2-y1; if(fabs(dx)=fabs(dy) k=dy/dx; else k=dx/dy; /1/k x=x1; y=y1; while(x=dy) y

5、=y+k; x+; else x=x+k; y+; 10数值微分法数值微分法(DDA法法)特点特点u迭代增量算法迭代增量算法u直观、易实现直观、易实现u不利于用硬件实现不利于用硬件实现(浮点数浮点数) 11u给定理想直线的起点坐标为给定理想直线的起点坐标为P0(x(x0 0，y y0 0) )，终，终点坐标为点坐标为P1 (x(x1 1，y y1 1) )，则直线的隐函数方程，则直线的隐函数方程为：为：120bkxyy)F(x,0101xxyyxyk01xxx其中，直线的斜率：其中，直线的斜率： 直线水平方向位移直线水平方向位移 直线垂直方向位移直线垂直方向位移01yyy中点画线算法中点画线算

6、法中点画线算法中点画线算法u直线与空间的关系直线与空间的关系13图图3 直线将平面分为三个区域直线将平面分为三个区域u假定假定0k1，即即0y/x1，x是最大位移方向是最大位移方向u当前点当前点 P 的下一点只能取的下一点只能取 Pu 或或 Pd，可用中点与直线，可用中点与直线的位置关系来判定，中点偏差判别式的位置关系来判定，中点偏差判别式图图4 中点算法生成直线的原理中点算法生成直线的原理中点中点M坐标为（坐标为（xi+1, yi+0.5）, 判别式：判别式： ) 1(5 . 0)5 . 0, 1(),(bxkyyxFyxFdiiiiMM则有：则有：) 0( ) 0( 1111dydyyxx

7、iiiii图图5 中点算法生成直线的原理中点算法生成直线的原理M（x i2，y i1.5）M（x i1，y i0.5）P（xi，yi）M（x i1，y i0.5）M（x i2，y i0.5）P（xi，yi）中点偏差判别式的递推中点偏差判别式的递推d0d0u中点偏差判别式的中点偏差判别式的递推公式递推公式在主位移在主位移x x方向上已走一步的情况下，现在考虑沿主方向上已走一步的情况下，现在考虑沿主位移方向再走一步，应该选择哪个中点代入中点偏位移方向再走一步，应该选择哪个中点代入中点偏差判别式以决定下一步该点亮的像素差判别式以决定下一步该点亮的像素? ?如图所示，分两种情况讨论。如图所示，分两种情

8、况讨论。 (1)(1)当当d0d0时时, , 取右上方的取右上方的PuPubxkyyxFdiiiii)2(5 . 1)5 . 1, 2(1kdkbxkyiii11) 1(5 . 0当当d0d0时时, , 取正右方的取正右方的PdPdbxkyyxFdiiiii)2(5 . 0)5 . 0, 2(1kdkbxkyiii) 1(5 . 0u中点偏差判别式的递推公式中点偏差判别式的递推公式直线的起点坐标为直线的起点坐标为P P0 0（x x0 0，y y0 0），），x x为主位移方向。为主位移方向。因此，第一个中点是（因此，第一个中点是（x x0 01 1，y y0 00.50.5），相应），相应的

9、的d d的初始值为：的初始值为：bxkyyxFd) 1(5 . 0) 5 . 0, 1(000005 .000kbkxy其中，因为其中，因为P P0 0（x x0 0，y y0 0）在直线上，所以）在直线上，所以000bkxy则：则：kd5 .00(x0,y0)(x0+1,y0+0.5)00+111122(0.5)20022(1)222220022()2iiiiiiiiiiiiiDxdxkxydDDxdx dkxdxyDxydDDxdx dkDy 19改进：用改进：用2dx代替代替d, 令令D2dx 则：则：中点算法的改进中点算法的改进整数化判别式整数化判别式u输入直线的两端点输入直线的两端点

10、P0(x0,y0)和和P1(x1,y1)。u计算初始值计算初始值x、y、D=x-2y、x=x0、y=y0。u绘制点绘制点(x,y)。判断判断D的符号。的符号。 若D0.5,y+，d=d-1改进1：令e=d-0.5，改为只判断符号0.5)(d 0.5)(d 1 111iiiiiyyyxx0)(e 0)(e 1 111iiiiiyyyxxe0=-0.5，每走一步每走一步: e=e+kif (e0) then e=e-1,y+误差项的计算误差项的计算d0=0，每走一步：每走一步：d=d+k if (d0.5) then d=d-1, y+改进改进2：用：用E=e*2x来替换来替换e, 去掉去掉kue

11、0=-0.5u每走一步有每走一步有e=e+k, x+uif (e0) then e=e-1,y+uE0=-0.5*2x=-xu每走一步有每走一步有E=(e+k)*2x=E+2y uif (e0) then E=(e-1)*2x=E-2xBresenham算法算法算法步骤算法步骤1.输入直线的两端点输入直线的两端点P0(x0,y0)和和P1(x1,y1)2.计算初始值计算初始值x、y、e=-x、x=x0、y=y03.绘制点绘制点(x,y)4.e更新为更新为e+2y，判断判断e的符号：的符号：若e0，则(x,y)更新为(x+1,y+1)，将e更新为e-2x；否则，(x,y)更新为(x+1,y)5.

12、当直线没有画完时，重复步骤当直线没有画完时，重复步骤3和和4；否则结束；否则结束272 圆的扫描转换圆的扫描转换u解决的问题：解决的问题：绘出圆心在原点，半径为绘出圆心在原点，半径为整数整数R的圆的圆x2+y2=R2。28P P（-y-y，x x）P P（-y-y，-x-x）x=-yx=-yP P（-x-x，-y-y）P P（x x，-y-y）P P（y y，-x-x）P P（y y，x x）P P（x x，y y）P P（-x-x，y y）x=yx=yx=0 x=0y=0y=0圆的对称性圆的对称性八分法画圆八分法画圆u只要绘制出第一象限内的只要绘制出第一象限内的1/81/8圆弧圆弧，根据，根

13、据对称性就可绘制出整圆，这称为八分法画对称性就可绘制出整圆，这称为八分法画圆算法圆算法u假定第一象限内的任意点为假定第一象限内的任意点为P(x,y)P(x,y)，可以，可以顺时针确定另外顺时针确定另外7 7个点：个点： P P（y y，x x）P P（y y，x x）,P,P（x,x,y y ）, ,P P（x x，y y），），P P（y y，x x），），P P（y y，x x），），P P（x x，y y）。）。圆的扫描转换圆的扫描转换解决问题：解决问题：31图图 2 1/8圆弧圆弧圆的扫描转换圆的扫描转换u简单方程生成圆弧简单方程生成圆弧u中点画圆算法中点画圆算法uBresenham算

14、法算法32简单方程产生圆弧简单方程产生圆弧算法原理算法原理：利用其函数方程，直接离散计算。：利用其函数方程，直接离散计算。33圆的函数方程为：圆的函数方程为： 222Ryx122111 x0, 2() iiiiRxxyroundRx34圆的圆的极坐标方程极坐标方程为：为： sincosRyRx)sin( )cos()( 11111iiiiiiRroundyRroundx为一固定角度步长简单方程产生圆弧简单方程产生圆弧中点画圆中点画圆构造函数构造函数F(x,y)=x2+y2-R2。u对于圆上的点，对于圆上的点，F(x,y)=0；u对于圆外的点，对于圆外的点，F(x,y)0；u对于圆内的点，对于圆

15、内的点，F(x,y)00F F（x x，y y）=0=0F F（x x，y y）00时，下一点取时，下一点取 Pd(xi +1,yi-1)38构造判别式：构造判别式：222) 5 . 0() 1() 5 . 0, 1(),(RyxyxFyxFdiiiiMM误差项的递推（误差项的递推（d0） 32)5 . 0(32) 1()5 . 0() 11()5 . 0()2( )5 . 0, 2(12222222222iiiiiiiiiixdRyxxRyxRyxyxFd图图14 d0的情况的情况5)( 25)( 2) 5 . 0() 1(1) 5 . 0( 2) 5 . 0(32) 1() 15 . 0(

16、) 11() 5 . 1() 2() 5 . 1, 2(1222222222222iiiiiiiiiiiiiiiiyxdyxyxRyyxxRyxRyxyxFd误差项的递推（误差项的递推（d0）图图15 d0的情况的情况中点画圆中点画圆判别式的初始值判别式的初始值41RRRRFyxFd25. 1 )5 . 0(1 )5 . 0, 1 ()5 . 0, 1(22000改进：用改进：用d-0.25代替代替d此时有：此时有：Rddyxdddxddiii125. 05)(225. 0320025. 0025. 0ddddd为整数为整数中点画圆中点画圆算法步骤算法步骤1.输入圆的半径输入圆的半径R。2.计

17、算初始值计算初始值d=1-R、x=0、y=R。3.绘制点绘制点(x,y)及其在八分圆中的另外七个对称及其在八分圆中的另外七个对称点。点。4.判断判断d的符号：的符号：若d0，d更新为d+2x+3， (x,y)更新为(x+1,y)；否则，d更新为d+2(x-y)+5,(x,y)更新为(x+1,y-1)。5.当当x0时，下一点取时，下一点取 Pd(xi +1,yi-1) 递推公式为：递推公式为：（3）计算判别式的初值。初始点为（）计算判别式的初值。初始点为（0，R），则：），则：641111iiiiiiixddyyxx10)(411111iiiiiiiiyxddyyxxRRRRd232) 1(22

18、220算算法法实实现现 void CMyView:OnBresenhamcircle() CDC *pDC=GetDC();int x0=100,y0=100,x,y,r=80,c=0; /黑色圆弧黑色圆弧float e,d;e=3-2*r;x=0;y=r;while(x=y)if (eSetPixel(x+x0,y+y0,c);/加圆心坐标加圆心坐标pDC-SetPixel(-x+x0,y+y0,c);pDC-SetPixel(-x+x0,-y+y0,c);pDC-SetPixel(x+x0,-y+y0,c); pDC-SetPixel(y+x0,x+y0,c); pDC-SetPixel(

19、-y+x0,x+y0,c); pDC-SetPixel(-y+x0,-x+y0,c);pDC-SetPixel(y+x0,-x+y0,c);ReleaseDC(pDC);椭圆的生成算法椭圆的生成算法1. 椭圆的特征椭圆的特征49椭圆的生成算法椭圆的生成算法0),(222222bayaxbyxF椭圆函数椭圆函数:u对于椭圆上的点，对于椭圆上的点，F(x,y)=0；u对于椭圆外的点，对于椭圆外的点，F(x,y)0；u对于椭圆内的点，对于椭圆内的点，F(x,y)0。1. 椭圆的特征椭圆的特征解决第解决第1象限问题：象限问题：以弧上斜率为以弧上斜率为1的点作为分界将第的点作为分界将第一象限椭圆弧分为上

20、下两部分。一象限椭圆弧分为上下两部分。A（0，b）B（a，0）y向分量向分量法矢量法矢量x向分量向分量椭圆的法矢量椭圆的法矢量222/bab222/baa引理：引理：若在当前的中点（若在当前的中点（xm,ym） ，法向量的，法向量的y分量比分量比 x 分量大，即：分量大，即： )5 . 0() 1(22iiyaxb而在下一个中点，不等号改变方向，则说而在下一个中点，不等号改变方向，则说明椭圆弧从上部分转入下部分。明椭圆弧从上部分转入下部分。yjaxibjyFixFyxN2222),(法向量法向量1. 椭圆的特征椭圆的特征先推导上半部分的椭圆绘制公式先推导上半部分的椭圆绘制公式2.上部分算法推导

21、上部分算法推导判别式判别式222222)5 . 0() 1()5 . 0, 1(bayaxbyxFdiiiii 若若 di0，取，取 Pu(xi+1,yi) 若若 di 0，取，取 Pd(xi+1,yi-1)2.上部分算法推导上部分算法推导误差项的递推误差项的递推di0：)32(2ixb(a) d0的情况Pxixi+2xi+1yi-1yiyi-2判别式的初始值：判别式的初始值：102222222(1,0.5)(0.5)(0.25)dFbba ba bbab 增量为：增量为：)22()32(22iiyaxb2.上部分算法推导上部分算法推导ya22u椭圆上法矢量的分量椭圆上法矢量的分量x x向分量

22、为：向分量为： y y向分量为：向分量为：u在上半部分在上半部分，法矢量的，法矢量的x x向分量小于向分量小于y y向分量向分量u在在C C点，法矢量的点，法矢量的x x向分量等于向分量等于y y向分量向分量u在下半部分在下半部分，法矢量的，法矢量的x x向分量大于向分量大于y y向分量向分量u则对于则对于上半部分椭圆上任意一点上半部分椭圆上任意一点P P( (x xi i，y yi i) )在在其当前中点其当前中点M M（x xi i1 1，y yi i0.50.5）处，满足）处，满足x x向分向分量小于量小于y y 向分量：向分量：) 5 . 0() 1(22iiyaxbxb223.下部分

23、算法推导下部分算法推导P（xi，yi）Pu（xi1，yi）Pl（xi，yi1）M（xi1，yi0.5）Pd（xi1，yi1）= Pr（xi1，yi1）图图 下半部分的中点下半部分的中点3.下部分算法推导下部分算法推导3.下部分算法推导下部分算法推导u假定图中假定图中P(P(x xi i，y yi i) )点是椭圆上半部分点是椭圆上半部分的的最后一个像素，最后一个像素，M M( (x xi i1 1，y yi i0.5)0.5)是用是用于判断点亮于判断点亮P Pu u和和P Pd d像素的中点。像素的中点。u由于下一像素转入了下半部分由于下一像素转入了下半部分，所以其，所以其中点改为判断中点改为

24、判断 Pl 和和 Pr 的中点的中点 M M( (x xi i0.50.5，y yi i1)1)椭圆弧下半部分的绘制公式椭圆弧下半部分的绘制公式原理原理3.下部分算法推导下部分算法推导判别方法：判别方法： 222222) 1()5 . 0() 1, 5 . 0(bayaxbyxFdiiiii若若di0，取，取Pl(xi,yi-1)若若di0的情况Pxiyi-2xi+1yiyi-1xi+2误差项的递推误差项的递推di0：122222222222222 (0.5,2)(0.5)(2)(0.5)(1)( 23)( 23)iiiiiiiiiidF xy bxaya b bxaya bay day增量：

25、增量：) 32(2iya3.下部分算法推导下部分算法推导di0： ) 32()22( ) 32()22() 1()5 . 0( )2()5 . 1()2, 5 . 1(22222222222222221iiiiiiiiiiiiyaxbdyaxbbayaxbbayaxbyxFd(b) dSetPixel(x,y,color); pDC-SetPixel(-x,-y,color); pDC-SetPixel(-x,y,color); pDC-SetPixel(x,-y,color); while(b*b*(x+1)a*a*(y-0.5) if(d1SetPixel(x,y,color);pDC-S

26、etPixel(-x,-y,color);pDC-SetPixel(-x,y,color);pDC-SetPixel(x,-y,color);/*while上半部分上半部分*/d2=b*b*(x+0.5)*(x+0.5)+a*a*(y-1)*(y-1)-a*a*b*b;while(y0) if(d2SetPixel(x,y,color);pDC-SetPixel(-x,-y,color);pDC-SetPixel(-x,y,color);pDC-SetPixel(x,-y,color); 65u用离散量表示连续量引起的失真，就叫做用离散量表示连续量引起的失真，就叫做走样走样（Aliasing）

27、。）。反走样反走样图图 绘制直线时的走样现象绘制直线时的走样现象反走样反走样u产生原因：产生原因： 数学意义上的图形是由无线多个连续的、数学意义上的图形是由无线多个连续的、面积为零的点构成；但在光栅显示器上，面积为零的点构成；但在光栅显示器上，用有限多个离散的，具有一定面积的象素用有限多个离散的，具有一定面积的象素来近似地表示他们。来近似地表示他们。6667走样现象：走样现象：u一是光栅图形产生的阶梯形。一是光栅图形产生的阶梯形。u一是图形中包含相对微小的物体时，这一是图形中包含相对微小的物体时，这些物体在静态图形中容易被丢弃或忽略，些物体在静态图形中容易被丢弃或忽略，在动画序列中时隐时现，产

28、生闪烁。在动画序列中时隐时现，产生闪烁。反走样反走样例子例子图。图。 丢失细节与运动图形的闪烁丢失细节与运动图形的闪烁u用于减少或消除这种效果的技术，称为用于减少或消除这种效果的技术，称为反走反走样样（antialiasing，图形保真）。图形保真）。u一种简单方法一种简单方法：硬件分辨率：硬件分辨率图图 分辨率提高一倍，阶梯程度减小一倍分辨率提高一倍，阶梯程度减小一倍软件反走样方法软件反走样方法u空间混色原理空间混色原理u人眼对某一区域颜色的识别是取这个区域人眼对某一区域颜色的识别是取这个区域颜色的平均值。颜色的平均值。p过取样（过取样（supersampling），），或后滤波或后滤波p区域取样（区域取样（area sampling），），或前滤波或前滤波7071u过取样过取样：在高于显示分辨率的较高分辨率：在高于显示分辨率的较高分辨率下用点取样方法计算，然后对几个象素的下用点取样方法计算，然后对几个象素的属性进行平均得到较低分辨率下的象素属属性进行平均得到较低分辨率下的象素属性。性。反走样反走样过取样（过取样（super sampli