《第3章基本图形生成》由会员分享，可在线阅读，更多相关《第3章基本图形生成（56页珍藏版）》请在金锄头文库上搜索。
1、第第3章章基本图形生成基本图形生成现现在在的的计计算算机机能能够够生生成成非非常常复复杂杂的的图图形形，但但图图形形无无论论多多么么复复杂杂，它它都都是是由由基基本本图图形形组组合合而而成成的的。因因此此，学学习习基基本本图图形形的的生生成成算法是掌握计算机图形学的基础。算法是掌握计算机图形学的基础。本章主要讨论一些基本图形的本章主要讨论一些基本图形的生成原理生成原理，如直线、圆、，如直线、圆、椭圆的生成问题，二维封闭图形（多边形、圆、椭圆）的椭圆的生成问题，二维封闭图形（多边形、圆、椭圆）的填充问题（包括颜色填充、影线填充和图案填充）以及线填充问题（包括颜色填充、影线填充和图案填充）以及线型
2、和线宽的处理。型和线宽的处理。第第3章章基本图形生成基本图形生成为什么要学习基本图形的生成？基本图形生成原理及算法是计算机图形学的基本基本图形生成原理及算法是计算机图形学的基本原理，如果不学习这些基本原理，那么以后还要原理，如果不学习这些基本原理，那么以后还要涉及的其他计算机图形学原理就无从谈起涉及的其他计算机图形学原理就无从谈起VisualC+虽然提供了许多绘图函数，但总有满虽然提供了许多绘图函数，但总有满足不了用户特殊绘图要求的时候。如果仅仅学会足不了用户特殊绘图要求的时候。如果仅仅学会使用使用VisualC+的绘图函数，不掌握基本图形生的绘图函数，不掌握基本图形生成原理及算法，那么你就永
3、远无法超越成原理及算法，那么你就永远无法超越VisualC+的限制的限制第第3章章基本图形生成基本图形生成图元的概念包含坐标及其它属性信息的基本几何结构，是构成图形的最基本元素。图形的扫描转换完成从图元的参数表现形式到点阵表现形式的转换假定假定：编程语言（以：编程语言（以C语言为例）提供语言为例）提供了一个最底层的像素操作函数了一个最底层的像素操作函数：putpixel(x, y, color)第第3章章基本图形生成基本图形生成屏幕网格坐标与点绘制问题问题：给定两个坐标点：给定两个坐标点，要求画出它们，要求画出它们的直线。的直线。1.计算机屏幕上画线与纸上画线区别？2.可否用数学公式直接画线？
4、第第3章章基本图形生成基本图形生成直线的生成直线的生成 从 的左端点 开始，向 右端点步进。步长=1(个象素)，计算相应的y坐标 ；取象素点(x, round(y)作为当前点的坐标。解决关键：如何确定y?生成算法：生成算法：数值微分（数值微分（DDA）算法）算法中点画线法中点画线法Bresenham算法算法第第3章章基本图形生成基本图形生成直线的生成直线的生成DDA算法基本思想第第3章章基本图形生成基本图形生成直线生成直线生成当 时，即：当x每递增1，y递增k(即直线斜率)第第3章章基本图形生成基本图形生成直线生成直线生成(xi,yi)(xi,(int)(yi+0.5)(xi+1,yi+1)(
5、xi+1,(int)(yi+1+0.5)注意：注意：1.上述分析的算法仅适用于上述分析的算法仅适用于 k 1的情形。在这种情况下，的情形。在这种情况下，x每增加每增加1,y最多增加最多增加1。2.当当 k 1时，必须把时，必须把x，y互换互换图图3.1 DDA3.1 DDA画线法示意图画线法示意图 上上述述采采用用的的增增量量计计算算方方法法称称为为数数值值微微分分算算法法( (DigitalDifferentialAnalyzer简简称称DDA)。以以下下是是用用数数值值微微分分算算法法(DDA)生生成成直直线线(斜斜率率在在0l)的的C语言描述。语言描述。voidDDALine(intx1
6、,inty1,intx2,inty2,intcolor)intx；floatk,dx，dy，y=y1；dx=x2x1；dy=y2y1；k=dy/dx;for(x=x1；x=x2；x+)putpixel(x,(int)(y+0.5),color);y=y+k;第第3章章基本图形生成基本图形生成DDADDA算法实现缺点： 在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。例：画直线段P0(0,0)-P1(5,2)x int(y+0.5) y0 00100.4210.8311.2421.65 22.0新思路： DDA算法采用点斜式，可否采用其他的直线表示方式？第第3
7、章章基本图形生成基本图形生成DDA 假定直线斜率0K P2离直线更近更近-取P2 。M在Q的上方- P1离直线更近更近-取P1M与Q重合， P1、P2任取一点。问题：如何判断M与Q点的关系？P=(xp,yp)P2P1MQ图图3 3.2中点画线法示意图中点画线法示意图 第第3章章基本图形生成基本图形生成中点画线法中点画线法基本思想直线隐式方程为：F (x, y)= ax + by + c 0假设直线的起点和终点分别为(x1,y1)和(x2,y2)，则上述参数：a = y1 - y2，b = x2 - x1，c = x1y2 - x2y1。判断点M与直线的关系(直线正负划分)：问问题题：若若对对每
8、每个个像像素素进进行行计计算算判判定定，那那么么每一个象素的计算量是4个加法，两个乘法。能能否采用增量算法提高效率？否采用增量算法提高效率？第第3章章基本图形生成基本图形生成中点画线法中点画线法第一个中点与直线的关系： d1= F(xi+1, yi+0.5)=a(xi+1)+b(yi+0.5)+c若d0，则取正右方象素P1 (xi+1, yi ), 要判下一个象素位置，则计算: d2=F(xi+2, yi+0.5) =a(xi+2)+b(yi+0.5)+c =d+a； 增量为a第第3章章基本图形生成基本图形生成中点画线法中点画线法第一个中点与直线的关系： d= F(xi+1, yi+0.5)=
9、a(xi+1)+b(yi+0.5)+c若d0时，则取右上方象素P2 (xi+1, yi+1)。要判断再下一象素，则计算: d2= F(xi+2, yi+1+0.5) =a(xi+2)+b(yi+1.5)+c =d+a+b ；增量为ab 第第3章章基本图形生成基本图形生成中点画线法中点画线法画线从(x0, y0)开始，第一个中心点与直线的关系，即d的初值： d0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+c F(x0, y0)= ax0+by0+c 因(x0, y0)在直线上，所以d0= F(x0, y0)+a+0.5b = a+0.5b在实际应用中，只关心d的正
10、负，故用2d代替d,可简化初使值中的小数 第第3章章基本图形生成基本图形生成中点画线法中点画线法voidMidpointLine(intx1,inty1,intx2,inty2,intcolor)intx,y,a,b,d1,d2,d;a=y1-y2;b=x2-x1;d=2*a+b;d1=2*a;d2=2*(a+b);x=x1;y=y1;putpixel(x,y,color);while(xx2)x=x+1;if(d0)y=y+1;d+=d2;elsed+=d1;putpixel(x,y,color);第第3章章基本图形生成基本图形生成中点画线法中点画线法算法实现例：用中点画线法P0(0,0)
11、P1(5,2)a=y0-y1=-2 b=x1-x0=5d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6i xiyid1 0012 10-33 2134 31-15 425第第3章章基本图形生成基本图形生成中点画线法中点画线法第第3章章基本图形生成基本图形生成Bresenham第第3章章基本图形生成基本图形生成Bresenham基本思想 设斜率0k1,利用d1,d2差值符号判断下一点的y坐标是yi+1或yi xiyiyi+1yxi+1d1d2 d1=y yi=(k(xi+1)+b)yid2=(yi+1)y=yi+1(k(xi+1)+b)那么那么d1d2=2k(xi+1)2yi+2b1
12、(3-1) k=y/x，代入上式，得：，代入上式，得：x(d1d2)=2yxk2xyk+2y+2xb-x=2yxk2xyk+c(32)令令Pi=x(d1d2)Pi=2yxk2xyk+c (3-2)第第3章章基本图形生成基本图形生成Bresenham画线画线基本思想 Pi+1=2yxi+12xyi+1+c (3-3)Pi+1-Pi=2y(xi+1xi)2x(yi+1yi)=2y2x(yi+1yi)第第3章章基本图形生成基本图形生成Bresenham画线画线例例: :从从(20,10)到(30,18),画直线画直线. .x=10, y=8;x=10, y=8;初始决策参数为初始决策参数为p0=2y
13、-x=6p0=2y-x=6ixiyipiixiyipi02010662615212111272716-222212-28281614323121492917104241310103018525146voidBresenham_Line(intx1,inty1,intx2,inty2,intcolor)intx,y,dx,dy,dk,i；dx=x2x1；dy=y2y1；P=2dydx；x=x1；y=y1；for(i=0;i=0)y=y+1；P=P2*dx；第第3章章基本图形生成基本图形生成Bresenham画线画线算法实现 3.2圆与椭圆的生成圆与椭圆的生成3.2.1圆的圆的特性及八分画圆法特性
14、及八分画圆法 由于圆是图形和图像中经常使用的元素，因此由于圆是图形和图像中经常使用的元素，因此在大多数图形软件中都包含有生成圆和圆弧的过程。在大多数图形软件中都包含有生成圆和圆弧的过程。也会提供一个既能显示圆曲线，又能显示椭圆曲线也会提供一个既能显示圆曲线，又能显示椭圆曲线的绘图函数。的绘图函数。笛卡尔积坐标参数方程笛卡尔积坐标参数方程中心位置中心位置(xc，yc)，半径，半径r的圆的圆，用如下方程表示：，用如下方程表示：(x xc) )2+(yyc) )2= r 2极坐标参数方程极坐标参数方程x=xc+rcosy=yc+rsin八分画圆法八分画圆法 使用使用圆的对称性，圆的对称性，只要能生成
15、只要能生成8分圆分圆，那么圆的，那么圆的其他部分可通过一系列的简单其他部分可通过一系列的简单反射变换反射变换得到。得到。3.2圆与椭圆的生成圆与椭圆的生成(y,x)(y,-x)(x,y)(x,-y)(-x,y)(-x,-y)(-y,-x)(-y,x)注：我们只考虑中心在原点，半径为整数注：我们只考虑中心在原点，半径为整数R的圆。对于的圆。对于中心不在原点的圆，可通过平移变换，化为中心在原中心不在原点的圆，可通过平移变换，化为中心在原点的圆，再进行扫描转换，把所得的像素坐标加上一点的圆，再进行扫描转换，把所得的像素坐标加上一个位移量即得所求像素坐标。个位移量即得所求像素坐标。3.2.3简单方程简
16、单方程画圆法画圆法基本原理： 利用函数方程，离散实现 离散点开方运算离散角度三角函数运算缺点：计算量大所画像素位置间的间距不一致 常用算法常用算法n n中点画圆法中点画圆法n nBresenhamBresenham画圆算法画圆算法3.2圆与椭圆的生成圆与椭圆的生成3.2.3中点画圆法中点画圆法问题提出：假定当前已确定了圆弧上的一个像素点为问题提出：假定当前已确定了圆弧上的一个像素点为P( (xi, ,yi) )，那么，下一个像素是正右方的，那么，下一个像素是正右方的P1( (xi+1, ,yi) )还是还是右下方的右下方的P2( (xi+1,yi1) )？基本原理：F(X,Y)=X2+Y2-R
17、2=0当当F(M)0时，时，M在圆内在圆内,P1当当F(M)0时，时，M在圆外在圆外,P2当当F(M)=0时，时，M在圆上在圆上,P2开始点（开始点（xi,yi)，则下一个像素点的中点，则下一个像素点的中点M坐标为（坐标为（xi+1,yi-0.5）di =F(M)=F (xi+1，yi0.5)=( (xi+1)2+(yi0.5)2r2当当d0时时，M在在圆圆内内，P1距距离离圆圆弧弧近近，取取P1(xi+1,yi)下一个中点下一个中点M（ xi+2，yi0.5）di+1=F (xi+2，yi0.5)=(xi+2)2+(yi0.5)2R2=di+2xi+33.2.3中点画圆法中点画圆法当当d=0
18、时时，M在在圆圆外外，P2距距离离圆圆弧弧近近，取取P2(xi+1,yi-1)初始点初始点P0(0,R)第一个中点第一个中点M(xi+1,yi-0.5）与圆关系）与圆关系3.2.3中点画圆法中点画圆法voidMidpointCircle(intxc,intyc,intr,intcolor)intx=0,y=r,d=1r；WholeCircle（xc，yc，x，y，color）；）；/显示显示圆弧上八个对称点圆弧上八个对称点while（x=y）if（d0）d+=2*x+3；x+；elsed+=2*（xy）+5；x+;y；WholeCircle（xc，yc，x，y，color）；）；算法实现 3.
19、2.3中点画圆法中点画圆法voidWholeCircle(intxc,intyc,intx,inty,intcolor)putpixel(xc+x，yc+y，color)；putpixel(xcx，yc+y，color)；putpixel(xc+x，ycy，color)；putpixel(xcx，ycy，color)；putpixel(xc+y，yc+x，color)；putpixel(xcy，yc+x，color)；putpixel(xc+y，ycx，color)；putpixel(xcy，ycx，color)；算法实现 3.2.3中点画圆法中点画圆法3.2.4Bresenham画圆算法画圆
20、算法考考虑虑圆圆心心在在原原点点，半半径径为为r的的第第一一个个8分分圆圆。取取(0,r)为为起起点点，按按顺顺时时针针方方向向生生成成圆圆。如如图图3.6所所示示。从从这这段段圆圆弧弧的的任任意意一一点点出出发发，按按顺顺时时针针方方向向生生成圆时。在这种情况下，成圆时。在这种情况下，x每步增加每步增加1，即：，即：yxyiyi-1xixi+1y图图3.63.6y的位置的位置xi+1=xi+1则相应的则相应的y有二种选择：有二种选择：yi+1=yi或或 yi+1=yi-1Bresenham画画圆圆算算法法采采用用一一个个决决策策值值来来确确定定到到底底是是选选择择yi还还是是yi-1。在在x
21、=xi+1位位置置上上，用用d1和和d2来来标标识识两两个个候候选选像像素素的的y值值与与圆圆弧弧上上理理想想y值值的的差差值值，则：则：y2=r2-(xi+1)2d1=yi2-y2=yi2-r2+(xi+1)2d2=y2-(yi-1)2=r2-(xi+1)2-(yi-1)2 令令di=d1-d2，并代入，并代入d1、d2，则有：，则有：di=2(xi+1)2+yi2+(yi-1)2-2r2这里这里di就是就是Bresenham画圆算法的第画圆算法的第i步决策值。步决策值。如果如果di0，则，则yi+1=yi，否则，否则yi+1=yi-1。若。若di=0，则，则可任选一个，我们约定可任选一个，
22、我们约定yi+1=yi-1。3.2.4Bresenham画圆算法画圆算法下面来推导下面来推导di的递推公式。在的递推公式。在i+1步，步，di+1为：为：di+1=2(xi+1+1)2+yi+12+(yi+1-1)2-2r2若若di=0，取右下方像素，取右下方像素，yi+1=yi-1，则：，则：di+1=2(xi+1+1)2+(yi-1)2+(yi-1-1)2-2r2=di+4(xi-yi)+10 由此，可写出由此，可写出Bresenham画圆算法的画圆算法的C程序：程序：3.2.4Bresenham画圆算法画圆算法voidBresenhamCircle(intxc,intyc,intr,in
23、tcolor)intx=0,y=r,d=3-2*r;while(xy)WholeCircle(xc,yc,x,y,color);if(d0)d=d+4*x+6;elsed=d+4*(x-y)+10;y-;x+;if(x=y)WholeCircle(xc,yc,x,y,color);3.2.4Bresenham画圆算法画圆算法3.2.5椭圆的生成算法椭圆的生成算法椭圆的特征椭圆的特征3.2.5椭圆的生成算法椭圆的生成算法 中中点点画画圆圆法法可可以以推推广广到到一一般般二二次次曲曲线线的的生生成成。给给定定椭椭圆圆参参数数中中心心（x xc c，y yc c）、长长半半轴轴a a和短半轴和短半轴
24、b b，该椭圆的一般方程为：，该椭圆的一般方程为： ( (x x x xc c) ) 2 2 / / a a2 2 + ( + (y y y yc c) ) 2 2 / / b b2 2 = 1 = 1 中心平移到坐标原点，确定好中心在原点的标准位置的椭圆中心平移到坐标原点，确定好中心在原点的标准位置的椭圆像素点集后，再平移到像素点集后，再平移到(x(xc c,y,yc c) )位置。位置。 如果椭圆的长轴和短轴方向不与坐标轴如果椭圆的长轴和短轴方向不与坐标轴x x和和y y平行，绕中心平行，绕中心点进行旋转变换，确定变换矩阵，然后用本方法生成椭圆像素点点进行旋转变换，确定变换矩阵，然后用本方
25、法生成椭圆像素点集，再用变换矩阵乘以这些点集，就可绘出倾斜的椭圆。集，再用变换矩阵乘以这些点集，就可绘出倾斜的椭圆。 椭圆特征椭圆特征 标准位置的椭圆：标准位置的椭圆： x x2 2 / a / a2 2 + y + y2 2 / b / b2 2 = 1 = 1隐式方程：隐式方程： F (x,y)= b F (x,y)= b2 2x x2 2a a2 2y y2 2 a a2 2b b2 2 = 0 = 0 3.2.5椭圆的生成算法椭圆的生成算法 该式可作为中点算法的判别式：该式可作为中点算法的判别式： 0 ( 0 ( 0 (x x, , y y) )在椭圆边界外在椭圆边界外 解决问题解决问
26、题椭椭圆圆的的对对称称性性，只只考考虑虑第第一一象象限限椭椭圆圆弧弧生生成成。以以切切线线斜斜率率为为-1-1的点作为分界点分上下两部分。的点作为分界点分上下两部分。椭圆上一点（椭圆上一点（x,yx,y）处的法向量：）处的法向量：3.2.5椭圆的生成算法椭圆的生成算法在上半部分，法向量在上半部分，法向量y y的分量更的分量更大，椭圆弧上各点的切线斜率大，椭圆弧上各点的切线斜率k k满足满足-1 k 0-1 k 0在下半部分，法向量在下半部分，法向量x x的分量更的分量更大，椭圆弧上各点的切线斜率大，椭圆弧上各点的切线斜率k k满足满足 k -1k -13.2.5椭圆的生成算法椭圆的生成算法弧上
27、一点（弧上一点（x,y) 处的法向量处的法向量从而弧上斜率为从而弧上斜率为-1-1的点满足：的点满足： 2b2x = 2a2y可求得可求得斜率为斜率为-1-1的点坐标：的点坐标：在上半部分在上半部分,法向量的法向量的y分量大分量大在下半部分在下半部分,法向量的法向量的x分量大分量大上半部分下半部分法向量法向量两分量相等两分量相等M1M2在当前中点处，法向量（在当前中点处，法向量（ 2b2 (Xp+1) ，2a2 (Yp-0.5)的的y分量比分量比x分量大分量大,即：即： b2 (Xp+1) a2 (Yp-0.5)在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分在下一中点，不等式改变方
28、向，则说明椭圆弧从上部分转入下部分3.2.5椭圆的生成算法椭圆的生成算法3.2.5椭圆的生成算法椭圆的生成算法算算法法原原理理:从从(0,b)到到(a,0)顺顺时时针针地地确确定定最最佳佳逼逼近近于于第第一一象限椭圆弧的像素序列。象限椭圆弧的像素序列。在上半部分，在上半部分，-1k0,最大位移方向为最大位移方向为x;在下半部分，在下半部分，k-1,最大位移方向为最大位移方向为y;椭圆弧的上部分椭圆弧的上部分设设 (Xp(Xp， Yp)Yp)已已 确确 定定 ， 则则 下下 一一 待待 选选 像像 素素 的的 中中 点点 是是(X(Xp p+1,Y+1,Yp p-0.5)-0.5) 3.2.5椭
29、圆的生成算法椭圆的生成算法判别式判别式若dp=0，取Pd(xp+1,yp-1)3.2.5椭圆的生成算法椭圆的生成算法 若若d dp p0=0：中中点点在在椭椭圆圆之之外外，这这时时 应应 取取 右右 下下 方方 像像 素素 , ,取取Pd(xp+1,yp-1) 增量为：增量为：b2(2xi+3)+a2(-2yi+2)3.2.5椭圆的生成算法椭圆的生成算法d dp p的的初初始始条条件件: :弧弧起起点点(0, (0, b b) )，第第一一个个中中点点(1, (1, b b0.5)0.5) 在生成椭圆弧的上部分时，在每步迭代中，必须随时计算和在生成椭圆弧的上部分时，在每步迭代中，必须随时计算和
30、比较从上部分转入下部分的条件比较从上部分转入下部分的条件（ 2b2 (Xp+1) 0，取(xi,yi-1)用上半部分计算的最后点(x，y)来计算下半部分中d的初值： d=b2(x+0.5)2+a2(y-1)2-a2b23.2.5椭圆的生成算法椭圆的生成算法d0,取正下方元素（xi，yi-1）3.2.5椭圆的生成算法椭圆的生成算法d0,取右下方元素（xi+1，yi-1）3.2.5椭圆的生成算法椭圆的生成算法椭圆生成算法描述(1)输入椭圆的长半轴输入椭圆的长半轴a和短半轴和短半轴b。(2)计算初始值：计算初始值：d=b2+a2(-b+0.25),x=0,y=b.(3)绘制点绘制点(x,y)及其在四
31、分象限上的另外及其在四分象限上的另外3个对称点个对称点.(4)判判断断d的的符符号号。若若d=0，则则先先将将d更更新新为为d+b2(2xi+3),再再将将（xi,yi）更更新新为为（xi+1,yi）;否否则则先先将将d更更新新为为d+b2(2xi+3)+a2(-2yi+2),再再将将（xi,yi）更新为（）更新为（xi+1,yi-1）(5)当当b2(x+1)a2(y-0.5)时，重复步骤时，重复步骤(3)和和(4)，否则转，否则转(6)(6)用上半部分计算的最后点用上半部分计算的最后点(x，y)来计算下半部分中来计算下半部分中d的初值：的初值：d=b2(x+0.5)2+a2(y-1)2-a2
32、b2(7)绘制点绘制点(x,y)及其在四分象限的另外及其在四分象限的另外3个对称点个对称点b(8)判判断断d的的符符号号.若若d=0，则则先先将将d更更新新为为d+b2(2xi+2)+a2(-2yi+3),再再将将(x,y)更新为更新为(x+1,y-1);否则先将否则先将d更新为更新为d+a2(-2yi+3),再将（再将（x，y）更新为）更新为(x，y1).(9)当当y0时，重复步骤时，重复步骤(7)和和(8)，否则结束。，否则结束。voidMidpointEllipse(intxc,intyc,inta,intb,intcolor)intaa=a*a,bb=b*b;inttwoaa=2*aa,twobb=2*bb;intx=0,y=b;intdx=0,dy=twoaa*y;intd=(int)(bb+aa*(b+0.25)+0.5);WholeEllipse(xc,yc,x,y,color);while(dxdy)x+;dx+=twobb;if(d0)y;dy=twoaa;if(d0)d+=aady;elsex+;dx+=twobb;d+=aady+dx;WholeEllipse(xc,yc,x,y,color);3.2.5椭圆的生成算法椭圆的生成算法
