第3章基本图形生成.ppt

《第3章基本图形生成.ppt》由会员分享，可在线阅读，更多相关《第3章基本图形生成.ppt（56页珍藏版）》请在三一文库上搜索。

1、第3章 基本图形生成,现在的计算机能够生成非常复杂的图形，但图形无论多么复杂，它都是由基本图形组合而成的。因此，学习基本图形的生成算法是掌握计算机图形学的基础。,本章主要讨论一些基本图形的生成原理，如直线、圆、椭圆的生成问题，二维封闭图形（多边形、圆、椭圆）的填充问题（包括颜色填充、影线填充和图案填充）以及线型和线宽的处理。,第3章 基本图形生成,为什么要学习基本图形的生成？ 基本图形生成原理及算法是计算机图形学的基本原理，如果不学习这些基本原理，那么以后还要涉及的其他计算机图形学原理就无从谈起 Visual C+虽然提供了许多绘图函数，但总有满足不了用户特殊绘图要求的时候。如果仅仅学会使用V

2、isual C+的绘图函数，不掌握基本图形生成原理及算法，那么你就永远无法超越Visual C+的限制,第3章 基本图形生成,图元的概念 包含坐标及其它属性信息的基本几何结构，是构成图形的最基本元素。 图形的扫描转换 完成从图元的参数表现形式到点阵表现形式的转换,假定：编程语言（以C语言为例）提供了一个最底层的像素操作函数： putpixel (x, y, color),第3章 基本图形生成,屏幕网格坐标与点绘制,问题：给定两个坐标点 ，要求画出它们的直线。 计算机屏幕上画线与纸上画线区别？ 可否用数学公式直接画线？,第3章 基本图形生成直线的生成,解决关键：如何确定y?,生成算法： 数值微分

3、（DDA）算法 中点画线法 Bresenham算法,第3章 基本图形生成直线的生成,DDA算法 基本思想,第3章 基本图形生成直线生成,当 时， 即：当x每递增1，y递增k(即直线斜率),第3章 基本图形生成直线生成,注意： 上述分析的算法仅适用于k 1的情形。在这种情况下，x每增加1, y最多增加1。 当 k 1时，必须把x，y互换,图3.1 DDA画线法示意图,上述采用的增量计算方法称为数值微分算法(Digital Differential Analyzer简称DDA)。以下是用数值微分算法(DDA)生成直线(斜率在0l)的C语言描述。,void DDALine (int x1, int

4、y1, int x2, int y2, int color) int x；float k, 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章 基本图形生成DDA,DDA算法实现,缺点： 在此算法中，y、k必须是float，且每一步都必须对y进行舍入取整，不利于硬件实现。,例：画直线段P0(0,0)-P1(5,2) x int(y+0.5) y 0 0 0 1 0 0.4 2 1 0.8 3 1 1.2 4 2 1.6 5 2

5、2.0 新思路： DDA算法采用点斜式，可否采用其他的直线表示方式？,第3章 基本图形生成DDA,假定直线斜率0K1，且已确定点亮象素点P（Xp ,Yp ）,则下一个与直线最接近的像素只能是P1点或P2点。 设M为中点，Q为交点。 现需确定下一个点亮的象素。,第3章 基本图形生成直线生成,中点画线法 基本思想,第3章 基本图形生成中点画线法,当M在Q的下方- P2离直线更近更近-取P2 。 M在Q的上方- P1离直线更近更近-取P1 M与Q重合， P1、P2任取一点。 问题：如何判断M与Q点的关系？,第3章 基本图形生成中点画线法,基本思想 直线隐式方程为：F (x, y)= ax + by

6、+ c 0 假设直线的起点和终点分别为(x1,y1)和(x2,y2)，则上述参数：a = y1 - y2，b = x2 - x1，c = x1y2 - x2y1。 判断点M与直线的关系(直线正负划分)：,问题：若对每个像素进行计算判定，那么每一个象素的计算量是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.

7、5)+c =d+a； 增量为a,第3章 基本图形生成中点画线法,第一个中点与直线的关系： d= F(xi+1, yi+0.5)=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

8、, y0)在直线上，所以d0= F(x0, y0)+a+0.5b = a+0.5b 在实际应用中，只关心d的正负，故用2d代替d,可简化初使值中的小数,第3章 基本图形生成中点画线法,void MidpointLine (int x1, int y1, int x2, int y2, int color) int x,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; else d+

9、=d1; putpixel(x,y,color); ,第3章 基本图形生成中点画线法,算法实现,例：用中点画线法P0(0,0) P1(5,2) a=y0-y1=-2 b=x1-x0=5 d0=2a+b=1 d1=2a=-4 d2=2(a+b)=6 i xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 5 4 2 5,第3章 基本图形生成中点画线法,第3章 基本图形生成Bresenham,第3章 基本图形生成Bresenham,基本思想 设斜率0k1,利用d1,d2差值符号判断下一点的y坐标是yi+1或yi,d1 = y yi = (k (xi + 1) +b)

10、 yi d2 = (yi+1) y = yi + 1 (k (xi + 1) +b) 那么 d1 d2 =2k (xi + 1) 2yi + 2b 1 (3-1),k = y/x，代入上式，得： x(d1d2)= 2yxk2xyk +2y+2xb-x =2yxk2xyk + c (32),令Pi = x(d1 d2) Pi=2yxk2xyk + c (3-2),第3章 基本图形生成Bresenham画线,基本思想,Pi+1 = 2yxi+1 2xyi+1 + c (3-3) Pi+1-Pi = 2y(xi+1 xi) 2x(yi+1 yi)= 2y 2x(yi+1 yi),第3章 基本图形生成

11、Bresenham画线,例:从(20,10)到(30,18),画直线.,x=10, y=8;初始决策参数为p0=2y-x=6,void Bresenham_Line (int x1, int y1, int x2, int y2, int color) int x, y, dx, dy, dk, i； dx = x2 x1；dy = y2 y1； P = 2dy dx； x = x1；y = y1； for (i = 0; i=0) y = y + 1； P = P 2 * dx； ,第3章 基本图形生成Bresenham画线,算法实现,3.2 圆与椭圆的生成,3.2.1 圆的特性及八分画圆法

12、,由于圆是图形和图像中经常使用的元素，因此在大多数图形软件中都包含有生成圆和圆弧的过程。也会提供一个既能显示圆曲线，又能显示椭圆曲线的绘图函数。,笛卡尔积坐标参数方程 中心位置(xc，yc)，半径r的圆，用如下方程表示： (x xc)2 +(y yc)2 = r 2,极坐标参数方程 x = xc + r cos y = yc + r sin,八分画圆法 使用圆的对称性，只要能生成8分圆，那么圆的其他部分可通过一系列的简单反射变换得到。,3.2 圆与椭圆的生成,注：我们只考虑中心在原点，半径为整数R的圆。对于中心不在原点的圆，可通过平移变换，化为中心在原点的圆，再进行扫描转换，把所得的像素坐标加

13、上一个位移量即得所求像素坐标。,3.2.3 简单方程画圆法,基本原理： 利用函数方程，离散实现,离散点 开方运算 离散角度 三角函数运算 缺点： 计算量大 所画像素位置间的间距不一致,常用算法 中点画圆法 Bresenham画圆算法,3.2 圆与椭圆的生成,3.2.3 中点画圆法,问题提出：假定当前已确定了圆弧上的一个像素点为P(xi,yi)，那么，下一个像素是正右方的P1(xi+1,yi)还是右下方的P2(xi+1, yi1)？,基本原理：,F(X,Y)=X2+Y2-R2=0 当F(M)0时，M在圆内,P1 当F(M)0时，M在圆外,P2 当F(M)=0时，M在圆上,P2,开始点（xi,yi

14、)，则下一个像素点的中点M坐标为（xi+1,yi-0.5） di = F(M)= F (xi+1，yi 0.5) =(xi+ 1)2 +(yi 0.5)2 r2,当d0时，M在圆内，P1距离圆弧近，取P1(xi+1,yi) 下一个中点M（ xi + 2，yi 0.5 ） di+1 = F (xi + 2，yi 0.5) =(xi + 2)2 +(yi 0.5)2 R2 = di + 2xi + 3,3.2.3 中点画圆法,当d=0时，M在圆外，P2距离圆弧近，取P2(xi+1,yi-1),初始点P0(0,R) 第一个中点M (xi+1,yi-0.5）与圆关系,3.2.3 中点画圆法,void

15、MidpointCircle (int xc, int yc, int r, int color) int x = 0, y = r, d = 1 r； WholeCircle（xc，yc，x，y，color）；/显示 圆弧上八个对称点 while（x=y） if（d0） d += 2 * x +3；x+； else d += 2 *（x y）+ 5；x+; y ； WholeCircle（xc，yc，x，y，color）； ,算法实现,3.2.3 中点画圆法,void WholeCircle (int xc, int yc, int x, int y, int color) putpixel

16、 (xc + x，yc + y，color)； putpixel (xc x，yc + y，color)； putpixel (xc + x，yc y，color)； putpixel (xc x，yc y，color)； putpixel (xc + y，yc + x，color)； putpixel (xc y，yc + x，color)； putpixel (xc + y，yc x，color)； putpixel (xc y，yc x，color)； ,算法实现,3.2.3 中点画圆法,3.2.4 Bresenham画圆算法,考虑圆心在原点，半径为r的第一个8分圆。取(0, r)为起点

17、，按顺时针方向生成圆。如图3.6所示。从这段圆弧的任意一点出发，按顺时针方向生成圆时。在这种情况下，x每步增加1，即：,图3.6 y的位置,xi+1=xi+1 则相应的y有二种选择： yi+1=yi 或 yi+1=yi-1,Bresenham画圆算法采用一个决策值来确定到底是选择yi还是yi-1。在x=xi+1位置上，用d1和d2来标识两个候选像素的y值与圆弧上理想y值的差值，则：y2=r2-(xi+1) 2 d1=yi2-y2=yi2-r2+(xi+1) 2 d2= y2- (yi-1)2= r2-(xi+1) 2- (yi-1)2,令di=d1-d2，并代入d1、d2，则有： di=2(x

18、i+1)2+yi2+(yi-1)2-2r2 这里di就是Bresenham画圆算法的第i步决策值。如果di0，则yi+1=yi，否则yi+1=yi-1。若di=0，则可任选一个，我们约定yi+1=yi-1。,3.2.4 Bresenham画圆算法,下面来推导di的递推公式。在i+1步，di+1为： di+1=2(xi+1+1)2+yi+12+(yi+1-1)2-2r2,若di0，取右方像素，yi+1= yi，则： di+1=2(xi+1+1)2+yi2+(yi-1)2-2r2= di+4xi+6,而决策值的初值d0由x=0,y=r代入前面公式，得： d0=2(0+1)2+r2+(r-1)2-2

19、r2=3-2r,已知xi+1=xi+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.4 Bresenham画圆算法,void BresenhamCircle (int xc, int yc, int r, int color) int x =0, y =r, d=3-2*r; while (xy) WholeCircle(xc, yc,

20、x, y, color); if(d0) d=d+4*x+6; else d=d+4*(x-y)+10; y-; x+; if(x= =y) WholeCircle(xc, yc, x, y, color); ,3.2.4 Bresenham画圆算法,3.2.5 椭圆的生成算法,椭圆的特征,3.2.5 椭圆的生成算法,中点画圆法可以推广到一般二次曲线的生成。给定椭圆参数中心（xc，yc）、长半轴a和短半轴b，该椭圆的一般方程为： (x xc) 2 / a2 + (y yc) 2 / b2 = 1,中心平移到坐标原点，确定好中心在原点的标准位置的椭圆像素点集后，再平移到(xc,yc)位置。 如果

21、椭圆的长轴和短轴方向不与坐标轴x和y平行，绕中心点进行旋转变换，确定变换矩阵，然后用本方法生成椭圆像素点集，再用变换矩阵乘以这些点集，就可绘出倾斜的椭圆。,椭圆特征,标准位置的椭圆： x2 / a2 + y2 / b2 = 1 隐式方程： F (x,y)= b2x2a2y2 a2b2 = 0,3.2.5 椭圆的生成算法,解决问题,椭圆的对称性，只考虑第一象限椭圆弧生成。以切线斜率为-1的点作为分界点分上下两部分。 椭圆上一点（x,y）处的法向量：,3.2.5 椭圆的生成算法,在上半部分，法向量y的分量更大，椭圆弧上各点的切线斜率k满足-1 k 0 在下半部分，法向量x的分量更大，椭圆弧上各点的

22、切线斜率k满足 k -1,3.2.5 椭圆的生成算法,弧上一点（x,y) 处的法向量,从而弧上斜率为-1的点满足： 2b2x = 2a2y,可求得斜率为-1的点坐标：,M2,在当前中点处，法向量（ 2b2 (Xp+1) ，2a2 (Yp-0.5)的y分量比 x分量大,即： b2 (Xp+1) a2 (Yp-0.5) 在下一中点，不等式改变方向，则说明椭圆弧从上部分转入下部分,3.2.5 椭圆的生成算法,3.2.5 椭圆的生成算法,算法原理:从(0,b)到(a,0)顺时针地确定最佳逼近于第一象限椭圆弧的像素序列。 在上半部分， -1 k 0 , 最大位移方向为x; 在下半部分， k -1 , 最

23、大位移方向为y;,椭圆弧的上部分 设(Xp，Yp)已确定，则下一待选像素的中点是(Xp+1,Yp-0.5),3.2.5 椭圆的生成算法,判别式,若dp=0，取Pd(xp+1,yp-1),3.2.5 椭圆的生成算法,若dp0，中点在椭圆内，则应取正右方像素.,3.2.5 椭圆的生成算法,增量为：b2(2xi+3),dp=0：中点在椭圆之外，这时应取右下方像素,取Pd(xp+1,yp-1),增量为：b2(2xi+3)+a2(-2yi+2),3.2.5 椭圆的生成算法,dp的初始条件:弧起点(0, b)，第一个中点(1, b0.5),在生成椭圆弧的上部分时，在每步迭代中，必须随时计算和比较从上部分转

24、入下部分的条件（ 2b2 (Xp+1) 2a2 (Yp-0.5)是否成立，这是由于在下一部分步进方向由x改为y，因此算法也就不同。在下部分，应改为从正下方和右下方两个像素中选择下一像素。 下半部分弧的终止条件为 y = 0,3.2.5 椭圆的生成算法,3.2.5 椭圆的生成算法,推导椭圆弧下半部分的绘制公式 原理,请思考？,判别式和初始值,若d20，取 (xi+1,yi-1) 若d20，取(xi,yi-1),用上半部分计算的最后点(x，y)来计算下半部分中d的初值： d=b2(x+0.5)2+a2(y-1)2-a2b2,3.2.5 椭圆的生成算法,d0,取正下方元素（xi，yi-1）,3.2.

25、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)及其在四分象限上的另外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)用上半部分计算的

26、最后点(x，y)来计算下半部分中d的初值： d=b2(x+0.5)2+a2(y-1)2-a2b2 (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)，否则结束。,void MidpointEllipse(int xc,int yc,int a,int b,int color) int aa = a * a, bb = b * b; int tw

27、oaa = 2 * aa, twobb = 2 * bb; int x = 0, y = b; int dx = 0, dy = twoaa * y; int d =( int) (bb + aa * ( b + 0.25 ) + 0.5 ); WholeEllipse(xc,yc,x,y,color); while (dx dy ) x +; dx += twobb; if (d 0 ) d += bb + dx; else y ; dy = twoaa; d += bb + dx dy; WholeEllipse(xc,yc,x,y,color); ,3.2.5 椭圆的生成算法,void

28、WholeEllipse(xc,yc,x,y,color) int xc,yc,x,y,color; putpixel (xc + x, yc + y, color ); putpixel (xc + x, yc y, color ); putpixel (xc x, yc + y, color ); putpixel (xc x, yc y, color ); ,d=(int)(bb*(x+0.5)*(x+0.5)+aa*(y1)*(y1)aa*bb +0.5); while (y 0) y ; dy = twoaa; if (d 0 ) d += aa dy; else x +;dx += twobb; d += aa dy + dx; WholeEllipse(xc,yc,x,y,color); ,3.2.5 椭圆的生成算法,