基本图形生成算法.ppt

计算机图形学与数字地图,第4章 基本图形生成算法,Email： ,余接情,4.1 绘图元素及其计算机表示,4.2 线段的生成,4.3 曲线的生成,4.4 区域的生成,4.1 基本绘图元素,图形设备显示曲线段时，最终还是将曲线段转化成一系列直线段逼近表示 。无论什么复杂图形，它们无非是由直线段和曲线段组成（三维图形经投影后最终变成了二维图形）,图形,三维图形,二维图形,曲面、平面,点,直线,曲线,平面,投影变化,4.1 基本绘图元素,4.1 基本绘图元素,显示器划分的像素点越多分辨率越高，直线绘制就越精确。,绘图仪绘制线段是笔在X,Y方向移动，画线时单方向的一次移动距离称为步矩，设备的步矩越小，绘出的图形越精确。,4.1 基本绘图元素,几何图形i | Pi 最接近图形的象素 基本图形的生成算法任务之一就是找出所有的i,4.1 基本绘图元素,在图形输出时，从图形对象的几何和拓扑信息出发，如何确定最佳逼近图形的象素集合，并用指定的颜色和灰度设置象素的过程称为图形的扫描转换或光栅化。 扫描转换一般分为两个步骤： 1）先确定有关象素；2)用图形的颜色或其他属性对象素进行某种写操作。后者通常通过调用设备驱动程序来实现，所以扫描转换的主要工作就是确定最佳逼近图形的象素集。,对于一维图形，在不考虑线宽时，用一个象素宽的直线或曲线来显示图形。 二维图形的光栅化必须确定区域对应的象素集，将各个象素设置成指定的颜色和灰度，该过程被称之为区域填充。,在数学上，点是一个抽象的概念，没有大小或面积，直线则是由无数个点构成的集合，它只有长度没有宽度。 在光栅图形中，点是由有一定大小和面积的象素来表示。直线则只能近似地表示，需要确定最佳逼近该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作，这个过程称为直线的扫描转换。 一条直线是指所有在它上面的点的集合，在图形学中研究的对象是直线段。,4.2 线段的生成,直线段是最基本的图形，因此，直线段生成的质量好坏与速度快慢将直接影响整个图形生成的质量和速度。根据光栅图形的特点，直线的绘制算法应该遵循以下5点要求： （1）所绘直线应尽可能地直，尽量避免阶梯效应； （2）所绘制的直线应该具有精确的起点与终点，具有连续性； （3）所显示的亮度或颜色应该在直线长度范围内是均匀不变的，与直线的长度和方向无关； （4）直线的生成速度要快； （5）尽量适合硬件实现。,4.2 线段的生成,问题： 如何生成以下直线段？,4.2 线段的生成,直接使用直线方程,最简单的方法； 步骤： 1、将P1,P2分别转换为象素坐标（x1,y1）,（x2,y2）; 2、设置k=(y2-y1)/(x2-x1)和b=y1-kx1; 3、如果k1，对(x1,x2)开区间的整数x代入方程得到y得到(x,y)； 3、如果k1，对(y1,y2)开区间的整数y代入方程得到x得到(x,y); 优点：简单 缺点：浮点运算（乘法和加法）计算复杂；,4.2 线段的生成,三种常用的直线扫描转换算法 数值微分法（DDA） 中点画线法 Bresenham算法,4.2 线段的生成,4.2.1 数值微分法（）(1/3) 假定直线的起点、终点分别为：（X0,Y0), (X1,Y1)，且都为整数。 直线的斜率： k = (Y1-Y0)/(X1-X0) 直线方程： = k*X+B,4.2 线段的生成,Yi+1 = k Xi+1 + B = k (Xi + Dx) + B = kXi + B + k Dx = Yi + k Dx,设的增量为x=，可得如下的增量方程： Yi+1= Yi + k,K的取值对分上述绘线方法的影响的影响。,起点,终点,未四舍五入前,最后选定的点,1,7,2,3,4,5,6,0,8,9,1,2,3,4,5,6,7,8,0,从起点开始朝终点方向 画点(x, y) 在x轴或y轴上走一个单位长（沿x轴还是y轴取决于直线的倾斜角） 由直线的倾斜程度（斜率或斜率的倒数）决定另一坐标的增量，获得下一点的座标 将x或y四舍五入，得(x, y) 若(x, y)不是终点则继续,4.2 线段的生成,4.2.1 数值微分法（）(2/3),void DDALine(int x0，int y0，int x1，int y1，int color) int x； float dx， dy， y， k； dx = x1-x0； dy=y1-y0； k=dy/dx；y=y0； for (x=x0；x= x1；x+) SetPixel (x，int(y+0.5)，color); y=y+k; ,缺点： 浮点运算 取整运算 不利于硬件实现。 上述存在什么问题？ 1）K 2）起点终点顺序,4.2 线段的生成,4.2.1 数值微分法（）(3/3),4.2 线段的生成,4.2.2 中点画线法(1/6),|K|1,原理： 假定直线斜率k在01之间，当前象素点为（xp,yp），则下一个象素点有两种可选择点P1（xp+1,yp）或P2（xp+1,yp+1）。若P1与P2的中点（xp+1,yp+0.5）称为M，Q为理想直线与x=xp+1垂线的交点。当M在Q的下方时，则取P2应为下一个象素点；当M在Q的上方时，则取P1为下一个象素点。,过点(x0,y0)、(x1, y1)的直线段L的方程式为 F(x, y)=ax+by+c=0 欲判断中点M在Q点的上方还是下方，只要把M代入F（x，y），并判断它的符号即可。,为此，我们构造判别式: d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c 当d0时，M在L(Q点)上方，取P1为下一个象素； 当d=0时，P1、P2均可，约定取P1为下一个象素；,4.2.2 中点画线法(2/6),4.2 线段的生成,1)若d=0，则取正右方象素P1(xp+1, yp) 此时，若要计算下一个象素位置，则构造下一中点的判别式： d1=F(xp+2,yp+0.5) =a(xp+2)+b(yp+0.5) =d+a （增量为a）,4.2.2 中点画线法(3/6),2）若d0，则取右上方象素P2(xp+1, yp+1) 此时，若要计算下一个象素位置，则构造下一中点的判别式： d2= F(xp+2, yp+1.5) =a(xp+2)+b(yp+1.5)+c =d+a+b (增量为ab)。,4.2 线段的生成,画线从(x0, y0)开始，d的初值: d0=F(x0+1, y0+0.5) =F(x0, y0)+a+0.5b 因F(x0, y0)=0，所以d0=a+0.5b 若di0,则di+1= di+a 其中，a=y0-y1, b=x1-x0 既然像素取舍只与di的符号有关，则可对di同乘2。,4.2.2 中点画线法(4/6),D0=2d0=2a+b,Di+1=2di+1= Di+2a+2b,Di+1=2di+1=Di+2a,4.2 线段的生成,起点,终点,a=-4; b=7; D0= -1;,1、X0=0, Y0=0,2、X1=1, Y1=1,3、X2=2, Y2=1,4、X3=3, Y3=2,5、X4=4, Y4=2,6、X5=5, Y5=3,7、X6=6, Y6=3,7,1,2,3,4,5,6,1,2,3,4,5,6,7,8,0,0,8、X6=7, Y6=4,4.2 线段的生成,D0=2a+b,Di0 (右上):Di+1=Di+2a+2b=Di+dD,Di0（右): Di+1=Di+2a= Di+dD,a=y0-y1, b=x1-x0,D0=-1,D1=5,dD=6; dD=-8,D2=-3,D3=3,D4=-5,D5=1,D6=-7,D7=-1,void MidpointLine (int x0，int y0，int x1，int y1，int color) int a， b， d1， d2， d， x， y； a=y0-y1； b=x1-x0；d=2*a+b； d1=2*a；d2=2* (a+b)； x=x0；y=y0； while (x=x1) SetPixel (x， y， color); if (d0) x+；y+； d+=d2; else x+； d+=d1; /* while */ /* midPointLine */,4.2 线段的生成,问题： -11 斜率-1 肿么办？,优点： 只有乘法和整数运算 进一步改进： 2a改为a+a,4.2.2 中点画线法(6/6),4.2.3 Bresenham (1/6),使用最广泛 与中点画线法的思想类似,算法原理是：过各行、各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。,4.2 线段的生成,设偏差为,当 时，下一点为右上方像素点 ，取 当 0 时，下一点为右方像素点， 取,整理后，有,4.2.3 Bresenham (2/6),4.2 线段的生成,偏差的递推关系：,误差,因为,有,4.2.3 Bresenham (3/6),4.2 线段的生成,4.2.3 Bresenham (4/6),4.2 线段的生成,void Bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy; float k, d; dx = x1-x0; dy = y1- y0; k=dy/dx; x=x0; y=y0; d=-0.5; for (i=0；i=dx；i+) Setpixel (x, y, color); x=x+1; d=d+k; if (d0) y+; d=d-1; ,4.2.3 Bresenham (5/6),如何去除浮点运算、乘除法？,4.2 线段的生成,void Bresenhamline (int x0,int y0,int x1, int y1,int color) dx = x1-x0,；dy = y1- y0,；d=-dx; x=x0； y=y0; for (i=0; i=dx; i+) Setpixel (x, y, color); d=d+2*dy; x+; if (d0) y+; d=d-2*dx ,从速度考虑，还有那些可以改进？,4.2.3 Bresenham (6/6),4.2 线段的生成,4.3 曲线的生成,4.3.1 圆的生成 4.3.2 椭圆的生成 4.3.3 其它曲线的生成,圆的生成：找出逼近圆的一组象素，按扫描线顺序，对这些象素进行写操作。 下面仅以圆心在原点的圆为例，讨论圆的生成算法。 1. 圆弧扫描算法,4.3.1 圆的生成,在一定范围内，每给定一X值，可得一Y值。 缺点：浮点运算，开方，像素不均匀。,2. 角度DDA法 （1/2） 圆的参数方程： x = x0 + Rcos y = y0 + Rsin 求导： dx =- Rsind dy = Rcosd 因此： xn+1 =x n + dx= x n - (y n - y 0)d y n+1 =y n + dy= y n + (x n - x 0)d,显然，确定x,y的初值及d值后，即可以增量方式获得圆周上的坐标，然后取整可得象素坐标。,4.3.1 圆的生成,缺点： 采用浮点运算、乘法运算，并且d的取值不容易确定，与半径大小有关，容易出现重复象素或漏失象素。,2. 角度DDA法 （2/2）,4.3.1 圆的生成,利用圆的对称性，只须讨论1/8圆。,4.3.1 圆的生成,3. 中点法 (1/5),2019/5/30,33 / 59,圆弧的隐函数： F(X,Y)=X2+Y2-R2=0 中点M=(Xp+1,Yp- 0.5), 当F(M)0时，M在圆内， 说明P1距离圆弧更近，取P1； 当F(M)0时，P取P2,切线斜率k为-1,0,4.3.1 圆的生成,3. 中点法 (2/5),构造判别式 d=F(M)=F(Xp+1,Yp-0.5)=(Xp+1)2+(Yp-0.5)2-R2 1）若di0，取P1，再下一个象素的判别式为： di+1 =F(Xp+2,Yp-0.5)= di +2Xp+3， 沿正右方向， di的增量为2Xp+3； 2）若di 0，取P2，再下一个象素的判别式为： di +1=F(Xp+2,Yp-1.5)= di +(2Xp+3)+(-2Yp+2) 沿右下方向， di的增量为2(Xp-Yp)+5 d的初始值(在第一个象素(0,R)处)： d0=F(1,R-0.5)=(0+1)(0+1)+(R-0.5)(R-0.5)-RR=1.25-R,4.3.1 圆的生成,3. 中点法 (3/5),MidpointCircle(int r) int x,y; float d; x=0; y=r; d=1.25-r; while(xy) setpixel(x,y); if(d0) d+ = 2*x+3; x+ else d+ = 2*(x-y) + 5; x+;y-; ,算法中有浮点数：有待改进,3. 中点法 (4/5),4.3.1 圆的生成,d0=0.25-R di0，di+1 =di +2Xp+3， 沿正右方向， di的增量为2Xp+3 di 0，di += di + 2(Xp-Yp)+5 沿右下方向，di的增量为2(Xp-Yp)+5,令：e=d-0.25,e0=1-R,ei -0.25,ei -0.25,又由于e的初值为整数，且在运算过程中的增量也是整数，故e始终是整数，所以e-0.25等价于e0,2Xp+3,2(Xp-Yp)+5,3. 中点法 (5/5),4.3.1 圆的生成,假设圆的半径为R， 当xhi2 + yhi2 -R2 R2 - (xli2 + yli2)时，应该取Li ，否则取Hi。 令di = xhi2 + yhi2+ xli2 + yli2- 2R2 ， 当di 0 时应该取Li ，否则取Hi。 剩下的问题是如何快速的计算di，设图中Pi的坐标为(xi，yi)，则Hi和Li的坐标为(xi+1，yi)和(xi+1，yi-1 )。,4.3.1 圆的生成,4. Bresenham算法 (1/3),当di0时，取Hi，yi+1=yi，则 di+1= di+4xi+6； 当di0时，取Li，yi=yi-1，则 di+1= di+4(xi-yi)+10,易知：x0=0；y0=R；x1=x0+1；d0= 3 - 2R；,4. Bresenham算法 (2/3),4.3.1 圆的生成,BresenhamCircle(int r, int color) int x=0,y=r,d=3-2*r; while(x=y) circlepoints (x,y,color); if (d0) d=d+4*x+6; else d=d+4*(x-y)+10; y-; x+; ,4. Bresenham算法 (3/3),4.3.1 圆的生成,中点法 椭圆方程：,对于椭圆上的点，有F(x,y)=0； 对于椭圆外的点，F(x,y)0； 对于椭圆内的点，F(x,y)0；,以弧上斜率为1的点作为分界将第一象限椭圆弧分为上下两部分。,4.3.2 椭圆的生成,椭圆方程：,法向量：,1、上半部分： M（Xi+1，Yi-0.5) 2、下半部分： M（Xi+0.5，Yi-1),4.3.2 椭圆的生成,构造判别式,若di0，取Pu(xi+1,yi) 若di0，取Pd(xi+1,yi-1),4.3.2 椭圆的生成,若di0，下一像素取Pu(xi+1,yi),若di0，下一像素取Pd(xi+1,yi-1),4.3.2 椭圆的生成