计算机图形学 第五章.ppt

1、计 算 机 图 形 学 Computer Graphics,翟瑞芳 ,本章主要介绍以下内容： 如何在指定的输出设备上根据坐标描述构造基本二维几何图形（点、直线、曲线及其相关属性等）。,第五章 二维图形生成技术,图形的生成：是在指定的输出设备上，根据坐标描述构造二维几何图形。 图形的扫描转换：在光栅显示器等数字设备上确定一个最佳逼近于图形的象素集的过程。,第五章 二维图形生成技术,5.1 基本绘图元素,1. 点,2. 直线,3. 曲线,5.1 基本绘图元素,5.2 直线段的生成算法,直线的扫描转换: 确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。,1. 生成的直线要直,

2、在生成直线时，对于水平线和垂直线是可以准确地画出来的，但对于一般的直线，由两点确定的线段不一定都能准确地通过网格交点。,(1)水平线,(2)垂直线,(3)一般线,在设计算法时就必须考虑点的选取。应该选择最靠近直线的可寻点来逼近直线，选择得好，绘出来的直线就直，否则就会产生弯曲。,5.2 直线段的生成算法,2. 直线的终止点要准,在绘制直线过程中，由于精度的影响，直线的终点与原终点有一个累积误差。,例如：,在提高设备的精度外，也要从算法上保证绘图的误差最小。,终点不准造成图形不封闭,5.2 直线段的生成算法,3.直线的粗细要均匀,对于由象素点组成的显示器来说，如果输出的直线选点不均匀，则造成直线

3、粗细不均匀，从直线上反映直线亮度不均匀；对于其他设备来说，给人感觉直线有粗有细。,不均匀的直线,5.2 直线段的生成算法,4.速度要快,虽然图形系统中硬件设备影响绘图的速度，但算法的好坏也影响速度，能够以较快的速度完成图形，这是每一个图形系统希望的。所以在选择和设计生成直线的算法时，速度指标也要加以重视。,5. 要求直线具有不同的色泽、亮度、线型等,5.2 直线段的生成算法,解决的问题： 给定直线两端点P0(x0,y0)和P1(x1,y1)，画出该直线。 常用算法： 逐点比较法 数值微分法（DDA） 中点画线法 Bresenham算法。,5.2 直线的生成算法,5.2.2 数值微分(DDA)法

4、,基本思想 已知过端点 的直线段L： 直线斜率为 从 的左端点 开始，向 右端点步进。步长=1(个象素)，计算相应的y坐标 ；取象素点(x, round(y)作为当前点的坐标。,计算量分析： 每个点计算量：上边的算法每个点需要 一个“+” 一个“*” 用到浮点数的乘法、加法和取整运算 作为最底层的光栅图形算法，在通常的CAD/图形系统中，会被大量应用，因此，哪怕节约一个加法或减法，也是很了不起的改进。 由此出发点，导致增量算法的思想。,5.2.2 数值微分(DDA)法,增量算法的思想,设步长为 计算 当 时; 即：当x每递增1，y递增k(即直线斜率)； 计算量：每个点只有一个“+” 注意：上述

5、算法仅适用于|K|1时，把X、Y互换。,5.2.2 数值微分(DDA)法,增量算法： 在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。 DDA算法就是一个增量算法。,5.2.2 数值微分法（DDA）,5.2.2 数值微分法（DDA）,DDA算法原理：,=1/max(|x|,|y|),直线的微分方程：,5.2.2 数值微分法（DDA）,max(|x|,|y|)=|x|，即|k|1的情况：,max(|x|,|y|)=|y|，此时|k|1：,5.2.2 数值微分法（DDA）,注意： round(x)=(int)(x+0.5),void DDALine(int

6、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; xx1, x+) drawpixel (x, int(y+0.5), color); y=y+k; ,5.2.2 数值微分法（DDA）,例：画直线段 x int(y+0.5) y+0.5 000 +0.5 100.4+0.5 210.8+0.5 311.2+0.5 421.6+0.5 522.0+0.5 注：网格点表示象素,5.2.2 数值微分法（DDA）,用DDA算法计算出

7、端点(20,10)(30,18)之间的中间点坐标。,5.2.2 数值微分法（DDA）,5.2.2 数值微分法（DDA）,例如:,绘制从(0,0)到(-8,-4)的直线,运用DDA方法计算如下:,初始值计算:,x = 0 , y = 0 , k = 0.4 ,dx = -1 , dy = -0.5,绘制过程如下:,(1)c = 7 x = -1 y = -0.5 画点(-1 , -1 ),(2)c = 6 x = -2 y = -1 画点(-2 , -1 ),(3)c = 5 x = -3 y = -1.5 画点(-3 , -2 ),(4)c = 4 x = -4 y = -2 画点(-4 ,

8、-2 ),(5)c = 3 x = -5 y = -2.5 画点(-5 , -3 ),(6)c = 2 x = -6 y = -3 画点(-6 , -3 ),(7)c = 1 x = -7 y = -3.5 画点(-7 , -4 ),(8)c = 0 x = -8 y = -4 画点(-8 , -4 ),5.2.2 数值微分法（DDA）,优点： 增量算法 直观、易实现 缺点： 有浮点数取整运算 不利于硬件实现 效率低,采用增量思想的DDA算法，每计算一个象素，只需计算一个加法，是否最优？ 如非最优，如何改进？ 目标：进一步将一个加法改为一个整数加法。 新思路 DDA算法采用点斜式，可否采用其他

9、的直线表示方式？,5.2.3 中点Bresenham算法,5.2.3 中点Bresenham算法,直线的方程：,5.2.3 中点Bresenham算法,基本原理（假定0k1，x是最大位移方向）：,当前象素点为(xi, yi) 。下一个象素点为Pd 或Pu 。 设M=(xp+1, yp+0.5)，为pu与pd 之中点，Q为理想直线与x=xi+1 垂线的交点。将Q与M的y坐标进 行比较。 当M在Q的下方，则Pu 应为 下一个象素点； M在Q的上方，应取Pd为下一点,如何判断M点与Q点之间的关系？,由常识可知： 对于直线上的点， F(x,y)=0； 对于直线上方的点，F(x,y)0； 对于直线下方的

10、点，F(x,y)0。,5.2.3 中点Bresenham算法,欲判断中点M是否在Q点上方还是Q点下方，只需把M带入F（X,Y)，并检查其符号。,构造判别式：,则有： 当d0，M在L(Q点)上方，取右方Pd为下一个象素； 当d=0，选Pd或Pu均可，约定取Pd为下一个象素(注意：所有的点都采取相同规则）。,5.2.3 中点Bresenham算法,但这样做，每一个象素的计算量包括加法，减法，乘法，除法 “山穷水尽疑无路” 如果也采用增量算法呢？ d是xi, yi的线性函数，因此可采用增量计算，提高运算效率。,5.2.3 中点Bresenham算法,若当前象素处于d0情况，则取正右方象素Pd (xi

11、+1, yi), 要判下一个象素位置，应计算,5.2.3 中点Bresenham算法,增量为-k,5.2.3 中点Bresenham算法,若当前象素处于d0情况，则取右上方象素Pu (xi+1, yi+1), 要判下一个象素位置，应计算,增量为1-k,5.2.3 中点Bresenham算法,初始值d的计算,5.2.3 中点Bresenham算法,0k1时中点Bresenham算法的算法步骤为： 1. 输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2. 计算初始值x、y、d=0.5-k、x=x0、y=y0； 3. 绘制点(x,y)。判断d的符号； 若d0，则(x,y)更新为(x+1,

12、y+1)，d更新为d+1-k； 否则(x,y)更新为(x+1,y)，d更新为d-k。 4. 当直线没有画完时，重复步骤3。否则结束。,5.2.3 中点Bresenham算法,至此，至少新算法可以和DDA算法一样好。 能否再做改进？ 能否实现整数运算？,5.2.3 中点Bresenham算法,改进：用2dx代替d 1. 输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2. 计算初始值x、y、d=x-2y、x=x0、y=y0。 3. 绘制点(x,y)。判断d的符号。 若d0，则(x,y)更新为(x+1,y+1)，d更新为 d+2x-2y； 否则(x,y)更新为(x+1,y), d更新为d

13、-2y。 4. 当直线没有画完时，重复步骤3。否则结束。,例：用中点画线法 x=5, y=2, d=1, 2x-2 y=6, -2y=-4 i xi yi d 1 0 0 1 2 1 0 -3 3 2 1 3 4 3 1 -1 5 4 2 5,5.2.3 中点Bresenham算法,5.2.3 中点Bresenham算法,用中点Bresehem算法计算出端点(20,10)(30,18)之间的中间点坐标。,d=x-2y=-6, 2x-2y=4, -2y=-16 x y d 20 10 -6 21 11 -2 22 12 2 23 12 -14 24 13 -10 25 14 -6 26 15 -

14、2 27 16 2 28 16 -14 29 17 -10 30 18 -6,void Midpoint Line (int x0,int y0,int x1, int y1,int color) int dx, dy, d, UpIncre, DownIncre, x, y; if(x0 x1) x=x1; x1=x0; x0=x; y=y1; y1=y0; y0=y; x=x0, y=y0; dx=x1-x0; dy=y1-y0; d=dx-2*dy; UpIncre=2*dx-2*dy; DownIncre=-2*dy; while(x=x1) drawpixel(x, y, color

15、); x+; if(d0) y+; d+=UpIncre; else d+=DownIncre; /* while */ /* mid PointLine */,5.2.3 中点Bresenham算法,优点： 只有整数运算，不含乘除法 可用硬件实现,5.2.3 中点Bresenham算法,基本思想 DDA算法采用点斜式，中点法采用隐式表示。 中点法可以有整数算法。 其他表示可以推出整数算法吗？,5.2.4 改进的Bresenham算法,算法思想：,过行、列像素中心构造一组虚拟网格线，将直线从起点到终点的顺序计算直线与各垂直网格线的交点，交点与网格线之间的误差值为di，根据di确定该网格中与此交

16、点最近的像素。 即每次在最大位移方向上走一步，而另一个方向是否走步取决于误差项的判断。,5.2.4 改进的Bresenham算法,5.2.4 改进的Bresenham算法,基本原理（假定直线段的0k1）：,误差项的计算 d初=0， 每走一步：d=d+k 一旦y方向上走了一步，d=d-1,5.2.4 改进的Bresenham算法,5.2.4 改进的Bresenham算法,算法步骤： 1.输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2.计算初始值x、y、d=0、x=x0、y=y0。 3.绘制点(x,y)。 4.d更新为d+k，判断d的符号。若d0.5，则(x,y)更新为(x+1,y+

17、1)，同时将d更新为d-1；否则(x,y)更新为(x+1,y)。 5.当直线没有画完时，重复步骤3和4。否则结束。,5.2.4 改进的Bresenham算法,改进1：令e=d-0.5,e初=-0.5， 每走一步有e=e+k。 if (e0) then e=e-1,5.2.4 改进的Bresenham算法,1. 输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2. 计算初始值x、y、e=-0.5、x=x0、y=y0。 3. 绘制点(x,y)。 4. e更新为e+k，判断e的符号。若e0，则(x,y)更新为(x+1,y+1)，同时将e更新为e-1；否则(x,y)更新为(x+1,y)。 5

18、. 当直线没有画完时，重复步骤3和4。否则结束。,算法步骤为：,void Bresenhamline (int x0,int y0,int x1, int y1,int color) int x, y, dx, dy; float k, e; dx = x1-x0, dy = y1- y0, k=dy/dx; e=-0.5, x=x0, y=y0; for (i=0; idx; i+) drawpixel (x, y, color); x=x+1，e=e+k; if (e0) y+, e=e-1; ,算法过程,5.2.4 改进的Bresenham算法,例：Line: P0(0, 0), P1(

19、5,2) k=dy/dx=0.4 x y e 0 0 -0.5 1 0 -0.1 2 1 0.3(-0.7) 3 1 -0.3 4 2 0.1(-0.9) 5 2 -0.5,5.2.4 改进的Bresenham算法,改进2：用2ex来替换e e初=-x， 每走一步有e=e+2y。 if (e0) then e=e-2x,5.2.4 改进的Bresenham算法,5.2.4 改进的Bresenham算法,算法步骤： 1. 输入直线的两端点P0(x0,y0)和P1(x1,y1)。 2. 计算初始值x、y、e=-x、x=x0、y=y0。 3. 绘制点(x,y)。 4. e更新为e+2y，判断e的符号

20、。若e0，则(x,y) 更新为(x+1,y+1)，同时将e更新为e-2x；否则 (x,y)更新为(x+1,y)。 5. 当直线没有画完时，重复步骤3和4。否则结束。,例：用Bresehem算法计算出端点(0,0), (8,5)之间的中间点坐标。x=8, 2y=10, -2 x=-16 计算初始值x、y、e=-x； e更新为e+2y，判断e的符号。若e0，则(x,y) 更新为(x+1,y+1)，同时将e更新为e-2x；否则 (x,y)更新为(x+1,y),5.2.4 改进的Bresenham算法,void InterBresenhamline (int x0,int y0,int x1, int

21、 y1,int color) dx = x1-x0, dy = y1- y0, e=-dx; x=x0, y=y0; for (i=0; idx; i+) drawpixel (x, y, color); x+, e=e+2*dy; if (e0) y+; e=e-2*dx; ,改进的Bresenham算法过程,5.2.4 改进的Bresenham算法,用Bresehem算法计算出端点(20,10)(30,18)之间的中间点坐标。,5.2.4 改进的Bresenham算法,Bresenham算法的优点是： 不必计算直线斜率，因此不做除法； 不用浮点数，只用整数； 只做整数加减法和乘2运算，而乘2运算可以用硬件移位实现。 Bresenham算法速度很快，并适于用硬件实现。 Bresenham is fast, and fast is good!,5.2.4 改进的Bresenham算法,思考： 利用DDA算法、中点Bresenham算法、改进的Bresenham算法画出同一条直线如（0，0）， （5，4）所获得的像素点是否相同？为什么？,作业： P149 5.2, 5.3, 5.6 查资料，对各个直线生成算法进行对比归纳，查找是否还有新的算法或算法优化思想。 用算法实现直线的生成，并对生成结果进行比较（包括算法效率、画线效果等方面）。,本 次