计算机图形学教材第二章光栅图形学(希赛教育基础学院)

★第二章光栅图形学【课前思考】计算机是如何在屏幕上画一条直线或一个圆的？在计算机屏幕上画直线时，经常出现锯齿，这是为什么？如何解决？【学习目标】了解光栅图形学的特点；掌握直线、圆弧和椭圆的光栅显示方法；学习反走样的几种算法，并能够编程实现。【学习指南】在数控插补技术中也有关于直线、圆弧和椭圆的NC插补的更多算法，可以参考有关的数控编程的书或资料；某些图象处理方法对学习和掌握反走样技术会有帮助。【难重点】Bresenham画直线和画圆算法；直线的反走样。【知识点】Bresenham画直线算法；Bresenham画圆算法；多边形区域填充；直线反走样；离散区域反走样算法。◇第一节画线算法光栅图形显示器可以看成是由许多可发光的离散点（即像素）组成的矩阵，它需要专门的算法来生成直线、圆弧和曲线等等图形。本章将介绍生成光栅图形的相关算法。这些算法对于开发图形设备驱动程序是必需的。不过，在Windows、Unix或Linux操作系统上开发计算机图形时，现在都有支持OpenGL的图形硬件和软件开发工具可供使用，而OpenGL程序库本身都提供了光栅图形显示的驱动程序，这为图形软件开发人员提供了便利。2.1画线算法在数学上，理想的点和直线都是没有宽度的。但是，由于每个像素对应于图形设备上的一个矩形区域，当我们在光栅图形设备上显示一个点时，实际上它是有用一个发光的矩形区域来表示的；当在光栅图形设备上显示一条直线时，我们只能在显示器所给定的有限个像素组成的矩阵中，按扫描线顺序，依次确定最佳逼近于该直线的一组像素，并且对这些像素进行写操作。这个过程称为直线的扫描转换。对于水平线、垂直线和45º斜线，选择哪些像素是显而易见的，但是对于其它的直线，确定用哪些像素来表示它就不那麽简单了。本节我们介绍用于直线扫描转换的常用算法：Bresenham画线算法。在介绍画线算法之前，我们先讨论画直线的基本要求：直线必须有精确的起点和终点，外观要直，线宽应当均匀一致、且与直线的长度和方向无关，最后，算法速度要快。Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。该方法最初是为数字绘图仪设计的，后来被广泛地应用于光栅图形显示和数控（NC）加工。该算法构思巧妙，使得每次只需检测误差项的符号就能决定直线上的下一个像素的位置。算法原理如下：过各个像素的中心构造一组虚拟网格线，首先按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后，采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列像素中与此交点最近的像素。先考虑斜率k=dy/dx≤1的直线。如图2.1所示，设直线方程为，其中，k=dy/dx。假设当前像素的x坐标已经确定为xi，其y坐标为yi，由于坐标（xi，yi）（i=0,1,…）只能取整数，那么下一个像素的x坐标，而yi＋1的坐标有两种可能：1)保持不变，即yi＋1＝yi；或者2)y坐标递增1，即yi＋1＝yi＋1。令，y坐标是否增加1取决于如图所示误差项di的值。因为直线的起始点在像素中心，所以初始误差d0＝0。x每增加1，y的值相应递增直线的斜率值k，即。一旦di+1≥1，就把它减去1，这样保证di+1在0～1之间。当di+1≥0.5时，直线与x＝xi＋1的垂线的交点最接近于当前像素（xi，yi）的右上方像素（xi＋1，yi＋1）；而当di+10.5时，其交点更接近于（xi，yi）右边的像素（xi＋1，yi）。为方便计算，令e0=－0.5，ei+1＝di+1－0.5，增量为k。当ei+1≥0时，取当前像素（xi，yi）的右上方像素（xi＋1，yi＋1）；而当ei+10时，更接近于右方像素（xi＋1，yi）。直线的基本要求因此，算法2.1可以改进如下：图2.1Bresenham画线算法上述算法在计算直线斜率和误差时要用到浮点运算和除法，可以改用整数运算并避免使用除法，以便提高运算速度。由于上述算法中只用到误差项的符号，因此可作一个简单变换：。考虑到xy平面上各种八分和四分区域的对称性，Bresenham画线算法的原理对任意斜率的直线都有其通用性。例如，对于斜率k1的直线，只要在上述算法中交换x和y之间的规则即可。算法2.1画斜率0≤k≤1的直线的改进的Bresenham画线算法：voidBresenhamLine(intx0,inty0,intx1,inty1,longcolor){intx,y,dx,dy;floatk,e;dx=x1-x0；dy=y1-y0；e=-dx;x=x0；y=y0；if(dx==0){for(i=0；i≤dy；i++){DrawPixel(x,y+i,color)；//画像素（x,y+i）}return;}for(i=0；i≤dx；i++){DrawPixel(x,y,color)；//画像素（x,y）x++；e+=e+2*dy；if(e≥0){y++；e-＝2*dx；}}}2.2画圆这一节中，我们介绍画圆弧的Bresenham算法。不失一般性，假设圆的圆心位于坐标原点（如果圆心不在原点，可以通过坐标平移使其与原点重合），半径为R。以原点为圆心的圆C有四条对称轴：x=0,y=0,x=y和x=-y。若已知圆弧上一点P1＝C（x,y），利用其对称性便可以得到关于四条对称轴的其它7个点，即：P2＝C（x,－y），P3＝C（－x,y），P4＝C（－x,－y），P5＝C（y，x），P6＝C（－y，x），P7＝C（y，－x），P8＝C（－y，－x）。这种性质称为八对称性。因此，只要扫描转换八分之一圆弧，就可以通过圆弧的八对称性得到整个圆。为了方便起见，考虑位于第一象限的四分之一圆弧。如果以点（0，R）为起点按顺时针方向生成圆，则在第一象限内y是x的单调递减函数。假设圆心和起点均精确地落在像素中心上。如果已经知道圆弧上的一点(x,y)，下一像素的选取有三种可能：正右方像素，右下角像素和正下方像素，分别用H,D和V表示，如图2.2所示。这三个像素的偏差的平方为：。令，。如果，说明圆弧到D向像素的距离大于到H向像素的距离，因此，下一个像素应当取H向的像素（xi+1，yi）；反之，下一个像素应当取D向的像素（xi+1，yi－1）。经过更进一步地分析后，可以得到：如公式（2－2－1）如公式（2－2－2）我们可以按以下规则选取下一个像素作为圆弧的最佳逼近点：当时，如果，则取为下一个像素点，否则取D为下一个像素点。当时，如果，则取D为下一个像素点，否则取V为下一个像素点；当时取D为下一个像素点。为了提高计算速度，我们可以在Bresenham画圆算法中采用只有加、减和移位（即：乘以2）操作的递推公式如下：可见，只用加、减和移位操作便完全可以实现Bresenham画圆算法。和改进的Bresenham画线算法一样，Bresenham画圆算法具有很高的速度和效率，因此得到广泛的应用。八对称性图2.2第一象限圆弧的像素选取2.3画椭圆中心在原点、轴对齐的椭圆的非参数化方程为：。上式可用隐式方程表示为：由于椭圆的对称性，仅考虑在第一象限的椭圆弧即可。椭圆弧的法向量计算公式为：椭圆弧上斜率为－1的点将椭圆弧分为上、下部分，见图2.3所示。在上部分（区域2），法向量的y向分量较大，选择像素时增量Δy比较重要；在下部分（区域1），法向量的x分量较大，选择像素时增量Δx比较重要。下面我们分开进行讨论。在区域2，设当前位置为点，下一个可能的点是像素点H和D，这时可构造判别式：若0,表示像素点H和D的中点在椭圆内，这时可取H为下一个像素点；若=0,表示像素点H和D的中点在椭圆外，这时应当取D为下一个像素点。所以，对于在区域2的椭圆弧，我们可以按左边的规则选取下一个像素作为椭圆弧的最佳逼近点：图2.3第一象限椭圆弧的像素选取2.4其它曲线二次曲线的一般方程为令，我们可以对二次曲线进行分类：二次曲线也可以用参数方程表示为：如果时，则r(t)是一条抛物线；当时，r(t)是一条双曲线；当时，r(t)是椭圆。当Δ0，图形为椭圆或圆弧；当Δ＝0，图形为抛物线；当Δ0，图形为双曲线对于椭圆和圆弧，我们可以用前面的方法进行光栅化显示。对于双曲线，我们可以采用差分的方法进行光栅图形显示。对于三次或三次以上的多项式曲线f(x,y)=0，可以采用递归空间子分算法进行光栅图形显示。其基本思想是：首先建立有顶点（，）和（，）构成的包围盒，如果曲线f(x,y)=0通过包围盒，而且包围盒的大小大于一个像素，则对包围盒再进行子分，直到包围盒只有一个像素大为止，然后用给定曲线的颜色输出；如果曲线f(x,y)=0不通过包围盒，则该区域用背景色显示，并忽略处理。2.5区域填充1)多边形由一系列首尾相连的直线段构成的图形称为多边形。如果在多边形内任意选取不相同的两点，其连线上的所有点均在该多边形内，这样的多边形称为凸多边形；否则，称为凹多边形。2)种子填充算法种子填充算法又称为边界填充算法。其基本思想是：从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。如果边界是以一种颜色指定的，则种子填充算法可逐个像素地处理直到遇到边界颜色为止。种子填充算法常用四连通域和八连通域技术进行填充操作。从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。用这种方法填充的区域就称为四连通域；这种填充方法称为四向连通算法。从区域内任意一点出发，通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。一般来说，八向连通算法可以填充四向连通区域，而四向连通算法有时不能填充八向连通区域。例如，八向连通填充算法能够正确填充如图2.4a所示的区域的内部，而四向连通填充算法只能完成如图2.4b的部分填充。图2.4四向连通填充算法四向连通填充算法：a）种子像素压入栈中；b）如果栈为空，则转e)；否则转c)；c）弹出一个像素，并将该像素置成填充色；并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是，则将该像素压入栈；d）转b）；e）结束。四向连通填充方法可以用递归函数实现如下：算法2.3四向连通递归填充算法：voidBoundaryFill4(intx,inty,longFilledColor,longBoundaryColor){longCurrentColor;CurrentColor=GetPixelColor(x,y);if(CurrentColor!=BoundaryColor&&CurrentColor!=FilledColor){SetColor(FilledColor);SetPixel(x,y);BoundaryFill4(x+1,y,FilledColor,BoundaryColor);BoundaryFill4(x-1,y,FilledColor,BoundaryColor);BoundaryFill4(x,y+1,FilledColor,BoundaryColor);BoundaryFill4(x,y-1,FilledColor,BoundaryColor);}}上述算法的优点是非常简单，缺点是需要大量栈空间来存储相邻的点。一个改进的方法就是：通过沿扫描线填充水平像素段，来处理四连通或八连通相邻点，这样就仅仅只需要将每个水平像素段的起始位置压入栈，而不需要将当前位置周围尚未处理的相邻像素都压入栈，从而可以节省大量的栈空间。3)其它填充算法扫描线填充算法是另一个常用的多边形填充算法。其基本思想是：对于一个给定的多边形，用一组水平或垂直的扫描线进行扫描，分别求出每条扫描线与多边形的交点，这些交点将扫描线分割为相间排列的落在多边形内和多边形外的线段，将落在多边形内的所有线段上的每个像素点赋以给定的多边形填充色。具体算法可以参考第7章消隐显示的相关内容。2.6字符生成在计算机图形学中，字符指计算机在文本方式下能够在屏幕上显示的数字、字母、音标、标点符号、数学符号、汉字等符号。计算机中的字符由一个数字编码唯一标识。最流行的字符集是美国信息交