计算机图形学 课件 第7章光栅图形生成

计算机图形学第七章栅格图学主要内容7.1光栅图形学概述7.2直线光栅化7.3多边形光栅化7.4反走样7.5隐藏面消除7.1光栅图形学概述在计算机图形学中，图形的生成过程以应用程序为起点，以图像的生成为终点输入：程序定义的顶点和状态变量，即几何对象、属性和虚拟照相机的参数设置；输出：位于帧缓存中的彩色像素阵列；中间需要完成：几何变换、裁剪、着色、隐藏面消除和图元的光栅化；必须使每个几何对象都通过图形系统，也必须为每个像素进行颜色赋值。7.1光栅图形学概述现代图形系统都是基于光栅的。在这样的图形系统中，在输出设备上看到的图像是一个由图形系统的图形元素（像素）组成的矩阵，它是离散的。因此，在输出设备上绘制具有连续性质的直线、曲线或区域等基本图形时，需要确定最佳逼近它们的像素，这个过程称为光栅化。光栅化也是是图形绘制流水线中几何处理的最后一步，一般是使用write_pixel来设置某个位置像素的颜色值。当光栅化按照扫描线的顺序进行时，它被称为扫描转换。7.1光栅图形学概述无论图形多么复杂，它都是由基本的点、线和面组合而成的对于零维的点图形，在不考虑点大小时，用一个像素表示。点的光栅化非常简单，不需要特别的算法。对于一维图形，在不考虑线宽时，用一个像素宽的直、曲线来显示图形。二维图形的光栅化必须确定区域对应的像素集，并用指定的属性或图案显示，即区域填充。7.2直线光栅化由于曲线和各种复杂的图形均被离散成许多直线段后绘制，因而直线是光栅化的基础。因此，直线光栅化有如下绘制要求：1.直线要直；2.直线的端点要准确，即无定向性和断裂情况；3.直线的亮度、色泽要均匀；4.画线的速度要快；5.要求直线具有不同的色泽、亮度、线型等7.2直线光栅化

7.2直线光栅化

算法中的round函数用于对一个实数进行四舍五人取整处理。7.2直线光栅化直线生成数值微分法（DDA法）DDA算法的基本思想就是对于每个x值，计算一个最佳的y值。对于斜率大于1的线段，由于两个着色像素之间的间隔很大，所以生成的线段无法令人接受。如果交换x和y,那么该算法就变为:对于每个y值，计算一个最佳的x值。对于同样的线段，可得到如图所示的近似线段。7.2直线光栅化直线生成Bresenham算法DDA算法看起来好像很有效，且该算法的编码实现确实非常容易，但是每生成一个像素都要用到一次浮点加法运算。Bresenham提出的线段光栅化算法采用加减与乘2运算来实现，可以有效地避免使用浮点运算，而且它已经成为硬件和软件光栅化模块的标准算法。7.2直线光栅化

7.2直线光栅化

7.2直线光栅化

7.2直线光栅化

7.2直线光栅化

7.3多边形光栅化多边形光栅化实际是对多边形内部区域填充某种颜色在图形系统中，多边形区域可用顶点表示，也可以用点阵表示。顶点表示是用多边形的顶点序列来表示多边形。这种表示方法直观、集合意义强、占内存少，易于进行集合变换，但由于这种表示方法没有明确指出哪些像素在多边形内，故不能直接进行区域填充。点阵表示则是用位于多边形内的像素集合来刻画多边形。这种表示方法丢失了许多几何信息，但便于进行填充。不同方法定义的多边形可以采用不同的填充算法，其中最具代表性的是：适合顶点表示的扫描线类算法和适合于点阵表示的种子填充类算法。7.3多边形光栅化扫描线填充算法扫描线源于光栅显示器的显示原理：光栅显示器屏幕是一个像素阵列，这些像素是按从上到下、自左至右的方式进行显示的。每一趟自左至右的显示所涉及的像素集合具有相同的y坐标值，形成了一条直线，这就是一条y方向的扫描线。同理，每一趟从上到下同样也能形成一条x方向的扫描线。出于习惯的原因，一般使用自左至右即y方向的扫描线。扫描线填充算法(scan-linealgorithm)的基本原理为待填充区间是由y方向(x方向亦可)扫描线与多边形的边形成的交点序列确定的。具体实现时，首先按照扫描线顺序，计算扫描线于多边形的相交区间，再用指定的颜色填充这些区间内的像素，即完成这一条扫描线的填充工作。区间的端点可以通过计算扫描线与多边形的交点获得。7.3多边形光栅化扫描线填充算法对于每一条扫描线，多边形的填充过程可以分为以下四个步骤：（1）求交点：计算当前扫描线与多边形所有边的交点；（2）排序与配对：把所有交点按x值递增顺序排序；排序后的交点两两配成区间，如第一个和第二个交点之间为一个区间，第三个和第四个交点之间为一个区间，以此类推；每对交点代表扫描线与多边形的一个相交区间；（3）填色：将相交区间内的像素值设置为目标颜色值，把相交区间外的像素设置为背景色。7.3多边形光栅化扫描线填充算法假设有一个凸多边形，顶点坐标分别为A(2,4),B(6,6),C(8,4),D(6,2),E(4,2)。现在要使用扫描线多边形填充算法对该多边形进行填充。1）首先，确定扫描线的范围。扫描线的范围由多边形的最高点和最低点决定，即在本例中扫描线的范围为y=2到y=6。2）从最高点开始，逐行进行扫描线填充。在本例中，从y=6开始扫描。3）对于每一条扫描线，确定与多边形交点的X坐标。在本例中，对于y=4,与多边形交点的x坐标为x=2和x=8。4）将交点按照升序排列，得到交点序列。在本例中，交点序列为(2,4)，(8,4)。5）根据交点序列，对每一对交点进行填充。在本例中，对于(2,4)和(8,4)，在扫描线y=4上的像素点进行填充。6）继续向下扫描，重复步骤3至步骤5，直到扫描到最低点y=2。7.3多边形光栅化扫描线填充算法但是，每当一条扫描线经过多边形的一个顶点时，扫描线在该顶点处与多边形的两条边相交可能出现如下两种情况两条相交边在扫描线的一侧可以把扫描线与多边形的边在顶点处的交点数量计为0个或2个(扫描线与交点所在的两条边都相交)两条相交边在扫描线两侧扫描线与多边形的边在顶点处的交点数量计为1个(扫描线只与交点所在的两条边中的一条边相交)7.3多边形光栅化扫描线填充算法7.3多边形光栅化种子填充算法如果多边形区域采用点阵形式定义，即多边形区域边界像素用一种颜色表示，区域内的其他像素为其他颜色表示，这种情况适合使用种子填充算法进行区域填充。区域填充规则为:如果某个点位于多边形的内部，那么使用多边形内部色(填充色)给它着色简单种子填充算法也称漫水填充算法(floodfillalgorithm)，其原理如下：假定只有两种颜色:背景色(白色)、前景色或绘制色(黑色)。对多边形的边进行光栅化处理后，把边的颜色置成前景色，此时帧缓存中的着色效果如图所示的简单多边形(深灰色)。如果能够在多边形的内部区域找到一个初始点(x，y)(浅灰色),即种子点(seedpoint)，那么就可以递归地寻找它的相邻像素：如果它的相邻像素不在多边形的边上，那么就用前景色对它着色。7.3多边形光栅化种子填充算法相邻像素可以是4连通相邻，即上、下、左、右四个方向相邻，也可以是8连通相邻，即上、下、左、右、左上、左下、右上、右下八个方向相邻。4连通相邻的简单种子填充算法的算法如下：functionfloodFill(x,y){if(readPixel(x,y)==WHITE){writePixel(x,y,BLACK);floodFill(x-1,y);floodFill(x+1,y);floodFill(x,y-1);floodFill(x,y+1);}}7.3多边形光栅化种子填充算法简单种子填充算法原理和程序都很简单，但由于使用了递归，导致算法费时、费内存且效率不高。为了减少递归次数，提高效率可以采用扫描线种子填充算法。该算法的基本过程如下：当给定种子点(x，y)时，首先填充种子点所在扫描线上位于给定区域内的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并以此保存下来。反复这个过程，直到填充结束。具体实现时可按如下4个步骤进行：（1）初始化：堆栈置空。将种子线(x，y)入栈。（2）出栈：若栈为空则结束。否则取栈顶元素(x，y)，以y作为当前扫描线。（3）填充并确定种子点所在区段：从种子点(x，y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标xl和xr。（4）确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的像素。若存在非边界、未填充的像素，则把每一区间的最右像素作为种子点压入堆栈，并返回第2步。7.3多边形光栅化多边形光栅化实际是对多边形内部区域填充某种颜色从理论上来说，相当于判断多边形所在的平面哪些点是多边形内部区域中的点；相交测试(crossingtest)或奇偶性测试(odd-eventest)是判断多边形内部-外部区域最广泛使用的方法；假定p是多边形内部的某个点，则从p点出发的射线一定与多边形有奇数条边相交；从多边形外部某点发出并进入多边形的任一射线与多边形的偶数边相交；通常使用扫描线代替射线，并根据扫描线与多边形交点的数量来确定多边形的内部和外部。7.3多边形光栅化多边形光栅化实际是对多边形内部区域填充某种颜色然而，我们希望使用填充算法填充星形多边形的效果应该如图c所示的那样，而不是图b所示的效果。使用环绕测试法(windingtest)可以解决这个问题。环绕测试法认为多边形是一个绕某个点或某条线形成的一个结。为了实现环绕测试，我们把多边形的边视为有向边，即从任意一个顶点出发,按某个特定的方向(究竟是哪个方向并不重要)环绕多边形直到回到出发点。在多边形的边上使用箭头表示环绕的路径，如图a所示。7.3多边形光栅化多边形光栅化实际是对多边形内部区域填充某种颜色对于平面上一个任意的点，该点的环绕次数(windingnumber)定义为多边形的边环绕该点的次数。规定顺时针环绕为正，而逆时针环绕为负(或者相反)。因此，对于位于下图所示的星形多边形之外的点，因为没有边环绕它，所以它的环绕次数等于0;对于图b所示的已被填充的区域，位于该区域内的点的环绕次数等于1;对于图b所示的星形多边形中央未被填充的区域，位于该区域内的点的环绕次数等于2。如果改变填充规则，即规定环绕次数为非0的点位于多边形内部区域，那么星形多边形内部的填充效果如图c所示。7.3多边形光栅化为了保证填充的正确性，所以要求多边形填充前应为简单凸多边形因为三角形总是平面凸多边形，一种方法是要求应用程序确保所生成的多边形都是三角形。另一种方法是通过软件把给定的一般多边形细分成多个平面凸多边形(一般是三角形)。把给定的一般多边形细分成多个三角形的方法很多。一种好的细分算法不会产生细长的三角形，如果可能的话，细分算法生成的一组三角形应该满足良好的几何特性，如三角形条带或三角形扇形。7.3多边形光栅化

7.3多边形光栅化一种多边形细分算法(或三角剖分)之后可以使用上面提到的方法对这两个多边形进行迭代细分处理，直到生成了所有的三角形。

7.4反走样当对图形进行光栅化时，用离散的像素表示连续直线和区域边界引起的失真现象（呈锯齿状）称为走样。用于减少或消除走样的技术称为反走样。与低分辨率的光栅显示器相比，高分辨率的光栅图形显示器所显示的图形质量更高，锯齿不明显。因此，可以通过提高显示设备的分辨率来改善图形质量。然而，硬件分辨率不能无限制地提高，通过软件方式来提高分辨率成为选择，区域平均反走样技术和超采样即通过软件方式来提高分辨的比较常用的反走样方法7.4反走样区域平均反走样技术(antialiasingbyareaaveraging)如图a，用真实像素来近似表示一个像素宽的理想直线，可发现它有一部分覆盖了许多单个像素大小的方形区域。如果根据像素在理想直线上所占面积的比例来设置像素的亮度，就会得到如图b所示的看起来更平滑的图像。这就是所谓的区域平均反走样技术(antialiasingbyareaaveraging)。7.4反走样

7.5隐藏面消除虽然通过光栅化处理生成的每个片元都对应于颜色缓存中的某个位置，但是如果某个片元所在的对象位于另一个不透明对象的后面(即被不透明对象所遮挡),那么我们并不希望通过给该片元对应的像素着色而显示该片元。对于位于视见体内的每个对象，隐藏面消除(或可见面判定)用来确定视见体中每个对象的哪些部分是可见的,或者确定哪些对象在视线上被其他对象所遮挡。根据在处理消隐问题时存在对象空间和图像空间之间的区别，隐藏面消除有对象空间和图像空间消隐算法。7.5隐藏面消除对象空间空间消隐算法在场景中，每个多边形都被认为是一个独立的对象。当从投影中心观察场景中所有的对象对，通过视线方向上的遮挡关系来确定消隐的对象如图，考虑场景中两个这样的多边形A和B,它们之间的位置关系为下面4种可能的情形:1)在视线方向上A完全遮挡了B,只显示A。2)在视线方向上B完全遮挡了A,只显示B。3)A和B都完全可见，既显示A也显示B。4)A或者B有一部分被对方所遮挡，必须计算被遮挡的多边形的可见部分。7.5隐藏面消除

7.5隐藏面消除

7.5隐藏面消除

7.5隐藏面消除

7.5隐藏面消除z缓存算法z缓存算法(z-bufferalgorithm)是使用最广泛的隐藏面消除算法。尽管该算法工作在图像空间，但是它的外层循环遍历每个多边形而不是每个像素，所以可以把它看成是多边形扫描转换过程的一部分。假定正在对如图所示的两个多边形中的一个多边形进行光栅化处理。从投影中心向某个