计算机图形学 第三章 从图形到图像(精品·公开课件).pptVIP

第三章 从图形到图像 3.1 图形图像的关系： 1）区别： 图形是用矢量表示的，是用几何学的点、线、面对客观世界建模的结果。图形中不但包含坐标、拓扑等几何信息，而且可以包含颜色、纹理等非几何信息。这些信息是设备无关的。 图像是用点阵表示的，其中只有各个点的颜色信息，不含拓扑关系，也没有几何学的点、线、面。从数学上说，图像是定义域和值域都不连续的一个函数（数字图像）。 图形和图像各有其优点，图形适合表达几何信息（建模），图像适合表达视觉信息（照片）。 2）存储： 图形使用矢量文件，图像使用点阵文件。 3）转换关系： 图形通过光栅扫描可以转化为光栅图像；图像通过识别和处理可以转化为矢量表示的图形形式，但通常它无法完全恢复图形信息。 3.2 直线生成算法 1）数值微分(DDA:Digital Differential Analyzer )法 过两点(x0,y0)，(xn,yn)作直线： 其直线方程为：(y-y0)/(yn-y0)=(x-x0)/(xn-x0) 整理后为：y=kx+b 其中k＝(yn-y0)/(xn-x0) 当|k|≤1时，取x方向步长为1， 则有，对中间需要计算的点（i=0,…,n-2） xi＋1=xi＋1 yi+1=kxi+1+b = k(xi+1)+b = kxi+b+k = yi+k 这里xi为整数，yi、k为浮点数 在屏幕上显示点(x0,y0),(x1,int(y1+0.5)),…,(xn-1,int(yn-1+0.5)),(xn,yn), 则显示出该直线。 由于y方向增量每次小于1，所以直线是连通的。 当|k|≥1时，交换x，y位置进行处理。 实例：用DDA方法在点（0,0）和（5,2）之间画线 xi yi int(yi+0.5) 0 0 0 1 0.4 0 2 0.8 1 3 1.2 1 4 1.6 2 5 2 2 n=5 (x0,y0) = (0,0) (xn,yn) = (5,2) k=(2-0)/(5-0) = 0.4 2)Bresenham算法 （最常用） ??? 前面已知当直线的斜率|k|≤1时，x方向每次增加一个步长，y方向增加不到一个步长。 ??? 如右图所示，当0≤k≤1时，每次y是否增加取决于误差项d，d≥0.5，y取直线上面的网格点，否则y取直线下面的网格点。 即对中间象素(i=0,…, i=n-2)，作下列操作： 1）xi+1= xi+1 2）ei+1= ei+k，(e0=-0.5，e不同于d，e=d-0.5) 3）当ei+1≥0时 {yi+1 = yi+1；ei+1= ei+1-1} 否则 yi+1= yi 这里的xi，yi均为整数，即象素点的坐标。e为浮点数。 4）显示（xi+1,yi+1) 实例：用Bresenham方法在点（0,0）和（5,2）之间画线 xi ei yi ei 0 -0.5 0 1 -0.1 0 -0.1 2 0.3 1 -0.7 3 -0.3 1 -0.3 4 0.1 2 -0.9 5 2 n=5 (x0,y0) = (0,0) (xn,yn) = (5,2) k=(2-0)/(5-0) = 0.4 Bresenham算法的整型化 原算法中的浮点计算为： e0=-0.5 ei+1=ei+k=ei+(yn-y0)/(xn-x0) 当ei＋1=0.0时，ei＋1=ei＋1-1.0; 下面开始整型化： 两边同乘(xn-x0)，有： (xn-x0) *ei+1= (xn-x0)*ei+(yn-y0) 两边再同乘2，则： 2*(xn-x0) *ei+1= 2*(xn-x0)*ei+2*(yn-y0) 令Ei= 2*(xn-x0) *ei 则有Ei+1=Ei+2*(yn-y0);E0=-(xn-x0); 判别式变为：当Ei+1=0时，Ei+1=Ei+1-2*(xn-x0) 结论： 通过整型化，算法中只有整型运算，效率大大提高，这正是Bresenham算法被广泛采用的原因。 3.3 圆的生成算法(中点画圆法) 圆的特点决定只需要计算1/8圆弧上的点（右上图） 假设圆的方程为：x2+y2=r2 函数F(x,y) = x2+y2-r2，则 F(x,y)0，对圆外点 F(x,y) = 0，对圆上点 F(x,y) 0，对圆内点 在第一象限上半1/8圆弧，如果已得到圆弧的象素点P(xp,yp)，则下一可能的象素点是P1(xp+1,yp)和P2(xp+1,yp-1)。究竟是P1还是P2 ，由P1和P2的中点M(xp+1,yp-0.5)的函数值F(xm,ym)来决定： 如果F(xm,ym)0，说明圆弧在P1和M之间，取P1点为下一象素。 且下一象素的F(xp+2,yp-0.5)