三维图形学基础

1、三维图形学基础第1页，共146页，2022年，5月20日，17点32分，星期日屏幕坐标及图形坐标显示器上的位置用整型的屏幕坐标来描述，与帧缓存中的像素位置相对应。 y坐标给出像素的行序号，x坐标给出列序号。屏幕刷新硬件一般从屏幕的左上角开始对像素进行编址，从最上面的第0行到最下面的第ymax行，对扫描行进行编号；每行从左到右，从第0到第xmax对扫描列进行编号。图形软件可以按照任意方式设定屏幕位置的图形坐标系统，如可以设定屏幕区域的左下角为原点(视区的默认值)，用整数坐标或非整数笛卡尔坐标来描述图形。描述物体对象的坐标值最终转换为帧缓存中的整数像素位置。图元的扫描转换根据给定的坐标来确定要显示

2、的像素位置，如给定一条直线段的两个端点，显示函数必须计算出两端点间位于线段上的所有像素的位置。由于一个像素位置占有屏幕上的一个有限范围，因此图形显示算法必须考虑像素的有限大小，一般假定像素坐标对应于像素区域的中心。第2页，共146页，2022年，5月20日，17点32分，星期日屏幕上的笛卡尔坐标系第3页，共146页，2022年，5月20日，17点32分，星期日显示窗口OpenGL函数库中用gluOrtho2D(xmin, xmax, ymin, ymax)函数设定一个二维视见空间(二维笛卡尔坐标系)，其参数指定了显示窗口（裁剪窗口）的x、y坐标范围。显示窗口的左下角位于坐标(xmin，ymin

3、)处，右上角位于坐标(xmax，ymax)处。如果一个图元的坐标范围完全在显示窗口（裁剪窗口）内，该图元将完整地显示出来，否则，仅仅位于显示窗口范围内的部分图元能显示出来，这涉及到裁剪。第4页，共146页，2022年，5月20日，17点32分，星期日随机扫描显示器20世纪60年代中期较早出现的是随机扫描显示器(也称为向量显示器 vector diaplay)，只能显示线条图形。这些线条由随机扫描系统按定义图形时的顺序绘制并刷新。笔试绘图仪也以类似的方式进行绘图。随机扫描系统的刷新频率依赖于显示的线条数目。图形的定义保存在刷新显示文件存储区中，是一组画线指令，刷新显示文件称为显示列表。为了显示指

4、定的图形，系统必须按显示文件中的一组命令依次画出各个线条，当所有画线命令处理完后，系统返回到该列表的第一条画线命令，然后重新开始绘制。随机扫描显示器以每秒3060次的刷新速度画出图形的所有线条。第5页，共146页，2022年，5月20日，17点32分，星期日光栅扫描显示器大约在1980年左右，诞生了光栅扫描显示器，它采用彩色电视技术，用三个电子束逐行扫描荧光屏上整齐排列的红、绿、蓝三基色点簇，一条电子束对准一种基色，一个点簇称作一个像素。荫罩法(shadow-mask)常用于光栅扫描系统。该方法基于红、绿、蓝三原色原理，对每个像素位置，荫罩CRT有三个荧光彩色点：一个荧光点发射红光，另一个发射

5、绿光，第三个发射蓝光。这类CRT有三支电子枪，与每个彩色点一一对应，而荫罩栅格位于紧靠涂覆有荧光层的屏幕之后。由于人眼可将三点发出的光合成为一种彩色，因此三种荧光粉发出的光生成一个小彩色点，称为像素点。第6页，共146页，2022年，5月20日，17点32分，星期日与光栅扫描显示器有关的几个基本概念在光栅扫描系统中，电子束横向扫描屏幕，一次一行，从顶到底依次进行，每一行称为一个扫描行。当电子束横向沿每一行移动时，电子束的强度不断变化，由不同的颜色和亮度生成图形。图形定义保存在帧缓存 (frame buffer)中，这里帧指整个屏幕范围，该存储器保存一组对应于屏幕所有点的强度值，电子束在屏幕上逐

6、点移动时从帧缓存中取出对应位置的值，控制其强度。每个可由电子束点亮的屏幕点称为一个像素(pixel，是picture 与 element的简写)，像素的阵列为光栅。一幅图像的像素全部存放在帧缓存的内存里。第7页，共146页，2022年，5月20日，17点32分，星期日与光栅扫描显示器有关的几个基本概念光栅扫描系统对屏幕的每一点都有存储颜色及亮度信息的能力，从而能适用于包含细微阴影和色彩变化的真实感图形显示。显示器的像素个数称为分辨率，如1024768，12801024。显示器的另一特征是纵横比(aspect ratio)，定义为系统能显示的像素列数除以行数。纵横比还可由屏幕上显示相同长度的水平

7、和垂直线段所需像素点数之比来描述。如纵横比为4/3，表示用4个点绘出的水平线与用3个点绘出的垂直线的物理长度相同。光栅系统可显示的颜色数目依赖于帧缓存中的位数，每个像素的位数称为缓存深度或精度。如1位深度缓存只能显示两种颜色，8位深度缓存则可以显示28(=256)中颜色，在真彩色系统里，深度为24位，红、绿、蓝三基色各8位，可以显示224(=16777216)种颜色数，能表示大多数真实感图形。第8页，共146页，2022年，5月20日，17点32分，星期日光栅化帧缓存通常采用特殊类型的内存芯片，可以快速显示帧缓存的内容，在一些基于软件的图形系统里，帧缓存是系统内存的一部分。在一些简单的图形系统

8、里，帧缓存只存储像素的颜色值，可以简单地将帧缓存称为颜色缓存(color buffer)。目前，对于大多数的图形系统，帧缓存能存储更多的信息，如三维图形的深度信息等。在这些系统里，帧缓存可以由多个缓存器组成。处理器的图形处理功能是根据应用程序的要求生成各种图元(如直线、圆和多边形)，把颜色值赋给帧缓存中的像素，使这些像素能表现这些实体。如三角形可用三个顶点来描述，为了显示三角形的三条边，图形系统必须生成一组像素，使这组像素看起来像三角形的边线。将几何形体的数据转换为像素在帧缓存里的位置和颜色的过程称为光栅化或扫描转换。第9页，共146页，2022年，5月20日，17点32分，星期日帧缓存在早期

9、的图形系统里，帧缓存是标准存储器的一部分，CPU可以直接对它进行存取操作。目前，几乎所有的图形系统都采用了专用的图形处理单元(Graphics Processing Uints，简称GPU)，这种专用的图形处理单元是专门针对某些特定的图形功能而设计的。GPU可以在主板上，也可以在图形显示卡上。计算机通过GPU对帧缓存进行存取操作，因此常把帧缓存包含在GPU内。第10页，共146页，2022年，5月20日，17点32分，星期日直线段的扫描转换算法直线的扫描转换: 根据直线的几何特征，可确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。两种常用算法：数值微分法（DDA）Bre

10、senham算法。问题：怎样又快又好地绘制一条直线段？第11页，共146页，2022年，5月20日，17点32分，星期日数字微分法基本思想：根据线段斜率的不同，在某个坐标轴上以单位间隔对线段采样，在另一个坐标轴上确定最靠近线段的对应整数值。 已知过端点P0 (x0, y0)， P1(x1, y1)的直线段L的方程为： y=kx+b 直线斜率为 当斜率的绝对值小于1时，从x的左端点x0开始，向x的右端点逐步递增。步长=1(象素单位)，计算相应的y坐标y=kx+b；取象素点(x, round(y)作为当前点的坐标。第12页，共146页，2022年，5月20日，17点32分，星期日由直线方程可得下一

11、个采样点的y坐标为： yi+1= kxi+1+b = kxi+b+kx = yi+kx 当x =1时;yi+1 = yi+k 即：当x每递增1，y递增k(即直线斜率)；注意上述分析的算法仅适用于k 1的情形。在此情况下，x每增加1，y最多增加1。当 k 1时，必须把x，y的地位互换： xi+1= xi+1/k该算法能在有限的线段长度内，根据斜率的不同合理确定尽可能多的像素来逼近该直线段。 DDA算法计算像素的位置比直接使用直线方程计算的速度要快，它利用光栅特性消除了直线方程中的乘法，在x或y方向使用合适的增量，在直线路径上逐步得到各像素的位置。但在浮点增量的连续累加中，取整误差的积累使得对于较

12、长线段所得到的像素位置偏离实际线段，且该过程中的取整操作和浮点运算仍然十分耗时。促使人们考虑既能用于直线，又能用于曲线的更通用的扫描线算法。第13页，共146页，2022年，5月20日，17点32分，星期日例：画直线段P0(0,0)-P1(5,2)k=0.4 x int(y+0.5) y+0.5 0 0 0 1 0 0.4+0.5 2 1 0.8+0.5 3 1 1.2+0.5 4 2 1.6+0.5 5 2 2.0+0.5第14页，共146页，2022年，5月20日，17点32分，星期日Bresenham算法Bresenham画线算法是一种精确而有效的光栅线生成算法，该算法还可用于圆和其它曲

13、线。思路：固定直线的两个端点，控制总体误差。如下图，首先考虑斜率小于1的直线的扫描转换过程，沿线段路径的像素位置由以单位x间隔的采样来确定。从给定线段的左端点(x0, y0)开始，逐步处理每个后继列(x位置)，并在其扫描线y值最接近线段的像素上绘出一点。下图显示了这个过程的第k步。假设当前已显示的像素点在(xk, yk)，那么下一步需要确定在列xk+1= xk+1上绘制哪个像素，是在位置(xk+1, yk)，还是在(xk+1, yk+1)。从 (xk, yk)像素开始，绘制斜率0m0 )。假如yk处的像素比yk+1的像素更接近于线段(即dlower dupper) ，那么参数pk是负的，此时绘

14、制下面的像素，反之，绘制上面的像素。可以利用递增整数运算得到后继的决策参数值。在k+1步，可得决策参数为： pk+1 = 2y xk+1 2x yk+1+c 3-2将两式相减，可得： pk+1 pk = 2y(xk+1 xk ) 2x(yk+1 yk )但xk+1 = xk +1，因而 pk+1 = pk + 2y 2x(yk+1 yk )其中yk+1 yk 取0或1，取决于参数pk的符号。决策参数的递归运算在线段的坐标端点开始的每个整数x位置进行，起始像素位置 (x0, y0)的第一个参数p0由式3-1及m=y/x可得：p0 = 2y x递推时，仅进行两个常量2y及2y 2x之间的整数加减。

15、第17页，共146页，2022年，5月20日，17点32分，星期日正斜率小于1的线段的Bresenham画线算法的主要步骤概括如下：(1) 输入线段的两个端点，并将左端点储存在(x0, y0)中；(2) 将(x0, y0)装入帧缓存，画出第一个点；(3) 计算常量x 、y 、2y 和2y 2x，并得到决策参数的第一个值； p0 = 2y x(4) 从k=0开始，在线段路径的每个xk处，进行下列检测： 如果pk0，下一个要绘制的点是(xk+1, yk)，并且pk+1 = pk + 2y 否则，下一个要绘制的点是(xk+1, yk+1)，并且 pk+1 = pk + 2y 2x(5) 重复步骤4

16、，共x 1次。当 斜率 1时，也必须把x，y的地位互换。例：绘制一条线段，端点为(20,10)和(30，18)。该线段的斜率为0.8，且x =10， y =8初始决策参数为： p0 = 2y x =6后继决策参数的增量为：2y =16， 2y 2x = -4绘制初始点(x0, y0) = (20,10)，并根据决策参数确定后继像素点的位置为：第18页，共146页，2022年，5月20日，17点32分，星期日kpk(xk+1, yk+1)06(21,11)12(22,12)2-2(23,12)314(24,13)410(25,14)kpk(xk+1, yk+1)56(26,15)62(27,16

17、)7-2(28,16)814(29,17)910(30,18)沿端点(20,10)和(30,18)用Bresenham画线算法绘制的像素点第19页，共146页，2022年，5月20日，17点32分，星期日圆的生成算法圆的方程为：(x-xc)2+(y-yc)2=r2 利用这个方程，可以沿x轴从xc-r到xc+r以单位步长计算对应的y值，从而得到圆周上每点的位置： y=yc(r2-(x-xc)2)1/2 该方法的每一步包含很大的计算量，而且所绘制像素的间距不一致，如下图所示。我们可以在圆斜率的绝对值大于1后，交换x和y(即步进y值并计算x值)来调整间距，但增加了计算量和处理过程。总之，该方法不是一

18、种理想的画圆方法。 用方程3.4.2绘制的正半圆第20页，共146页，2022年，5月20日，17点32分，星期日另一种消除不等间距的方法是使用极坐标r和来计算圆周上的点，圆的极坐标方程为： x=xc+rcos y=yc+rsin 使用上述方法以固定角度为步长可以生成等间距的点来绘制圆，尽管利用极坐标能生成等距点，但三角函数的计算十分耗时。可以利用圆的对称性减少计算量，圆的形状在每个象限中是相似的，如果确定了圆在第一象限中的位置，则可以生成圆在第二象限的部分，因为圆相对于y轴是对成的。根据圆相对于x轴的对称性，由第一象限和第二象限中的圆弧，可以得到第三象限和第四象限中的圆弧。在八分圆之间也有对

19、称性，一个象限中相邻八分圆的圆弧对于45直线是对称的，如下图。图中八分之一圆上的一点(x, y)可映射到其它7个八分圆的点。利用圆的对称性，可由1个八分圆上的点，映射到其余7个八分圆上的点第21页，共146页，2022年，5月20日，17点32分，星期日利用圆的对称性，仅需计算从x=0到x=y这段圆弧的点就可得到整个圆的所有像素位置。在该八分圆中，圆弧斜率的绝对值1，x=0时的斜率为0，x=y时圆弧的斜率为-1.0。使用对称性及圆的方程来确定圆周上的像素位置，仍然需要大量的计算，更有效地画圆算法是采用类似Bresenham画线算法，通过设定在每一步采样步骤中寻找最接近圆周像素的决策参数。但圆的

20、方程是非线性的，包含平方运算，一个避免平方运算的方法是：检验两像素间的中点位置是在圆边界之内还是之外。中点画圆算法：对于中心为(xc， yc)、半径为r的圆，先计算圆心在 (0, 0)的圆的像素位置，然后通过将xc加到x且yc加到y，将圆平移到真正位置。在第一象限，圆弧段从x=0到x=y，曲线的斜率从0变到- 1.0。可以在该八分圆上的正x方向取单位步长，并使用决策参数来确定每一步两个可能的y位置中，哪一个更接近于圆的位置，其余7个八分圆中的位置可由对称性得到。定义圆函数： f(x,y)=x2+y2-r2任何点的相对位置可由圆函数的符号来决定：第22页，共146页，2022年，5月20日，17

21、点32分，星期日 0, 如果(x, y)位于圆外圆函数即为决策参数，下图给出了采样位置xk+1上两个候选像素间的中点。圆周上采样位置xk+1上候选像素间的中点假设已在(xk, yk)绘制了一个像素，下一步需要确定是像素(xk+1, yk)还是像素(xk+1, yk1)更接近于圆，在两像素的中点求决策参数的值： pk=f(xk+1, yk1/2) =(xk+1)2+(yk1/2)2r2假若pk 0，则该中点位于圆内，扫描线yk上的像素接近于圆周边界。否则该中点位于圆外或圆周上，选择扫描线yk1的像素。第23页，共146页，2022年，5月20日，17点32分，星期日后续的决策参数可以使用增量运算

22、得到，如对采样位置 xk+1= xk+2处的圆函数求值，可以得到下一个决策参数的循环表达式： pk+1=f(xk+1+1, yk+11/2) =(xk+1)+12+(yk+11/2)2r2 = pk+2(xk+1)+(y2k+1y2k) (yk+1yk)+1其中，yk+1是yk或yk-1 ，取决于pk的符号。若pk为负，则yk+1=yk ，pk+1的增量为2xk+1+1；若pk为正，则yk+1=yk1， pk+1的增量为2xk+1+12yk+12xk+1和2yk+1的求值也可以通过增量的方式求得： 2xk+1 =2xk+2 2yk+1 =2yk2在起始位置(0, r)处，这两项的初始值分别为0

23、和2r。在起始位置(0, r)处，初始决策参数为： p0=f(1, r1/2)=1+(r1/2)2r2=5/4r如果将半径r指定为整数，可以对p0进行简单的取整，p0=1r，则中点方法使用整数加减来计算圆周的像素位置。第24页，共146页，2022年，5月20日，17点32分，星期日中点画圆算法的步骤：(1) 输入圆半径r和圆心(xc, yc)，并得到圆周(圆心在原点)上的第一个点： (x0, y0)=(0, r)(2) 计算决策参数的初始值： p0=5/4r(3) 在每个xk位置，从k=0开始，计算决策参数，若pk0，则圆周下一像素位置为(xk+1,yk)，并且 pk+1=pk+2xk+1+

24、1否则圆的下一点为(xk+1,yk1)，并且 pk+1=pk+2xk+1+12yk+1其中， 2xk+1 =2xk+2且2yk+1 =2yk2(4) 确定其它7个八分圆中的对称点。(5) 将每个计算出来的像素位置(x,y)平移到圆心在(xc, yc)的圆周上，并绘出各点(x+xc, y+yc)。(6) 重复步骤3到步骤5 ， 直至xy。第25页，共146页，2022年，5月20日，17点32分，星期日例， 使用中点画圆算法画圆给定圆半径r=10，确定在第一象限从x=0到x=y沿八分圆的各像素点位置。决策参数的初始值为: p0=1r=9对于中心在原点的圆，初始点(x0, y0)=(0, 10)，

25、决策参数的初始增量值： 2x0=0, 2y0=20使用中点画圆法计算的后续决策参数值及像素位置如下：kpkxk+1, yk+12xk+1,2yk+109(1,10)22016(2,10)4202 1(3,10)62036(4,9)8184 3(5,9)101858(6,8)121665(7,7)1414第26页，共146页，2022年，5月20日，17点32分，星期日用中点画圆法得到的像素位置(空心圆为第一象限的对称位置)第27页，共146页，2022年，5月20日，17点32分，星期日使用折线来逼近曲线常见的曲线除圆以外，还有椭圆、圆锥曲线、三角和指数函数、样条曲线等。显示曲线的简单方法是使

26、用直线段来逼近曲线，仅需确定一组曲线上的点并将它们连接成一组直线段。折线中的线段越多，曲线越平滑。第28页，共146页，2022年，5月20日，17点32分，星期日3.5 填充区图元图形学中常常需要用某种颜色或某种图案来填充一个区域，尽管有可能使用各种形状，但图形库一般不支持任意的填充形状，多数库函数要求填充区为多边形。多边形是由三个或更多的顶点连接而成的封闭图形，由于多边形的边界为直线段，因而比它形状更容易处理。可将曲线转换为由分段折线构成的多边形，曲面也可以用一系列多边形面片来逼近。如果一个多边形的所有内角均小于180，则该多边形为凸(convex)多边形。等价定义：它的内部完全在它的任一

27、边及其延长线的一侧。如果任意两点位于凸多边形的内部，则其连线上的任一点也在凸多边形的内部。不是凸多边形的多边形称为凹(concave)多边形。退化多边形是指有共线或重合顶点的多边形，共线的顶点生成一条线段，重叠的顶点可以生成多余线段、重叠边或长度为0的边。为了软件的鲁棒性，图形软件可以拒绝退化或非平面的多边形。凹多边形也会产生一些问题，对凹多边形的填充及其它处理比较复杂，常常将凹多边形分割成一组凸多边形以提高效率。第29页，共146页，2022年，5月20日，17点32分，星期日可以为多边形的每一条边建立一个向量，用相邻边的叉积来测试凸凹性，凸多边形的所有向量叉积均同号，如果某些叉积为正而另一

28、些为负，则为凹多边形。识别凹多边形的另一个方法是观察多边形顶点位置与每条边延长线的关系。如果有些顶点在某一延长线的一侧而有些顶点在另一侧，则为凹多边形。多边形的填充算法分为扫描线填充算法和种子填充算法。扫描线的含义来源于光栅显示器，对屏幕上的每个像素点，按从上到下，从左到右的顺序进行显示，水平方向从左到右每扫描一行，就是一条y方向的扫描线，同理，从上到下也能形成x方向的扫描线。扫描线填充算法的原理是：待填充区域按y方向(或x方向)扫描线的顺序，计算扫描线与多边形的相交区间，再用指定的颜色填充这些区间的像素，区间的端点可以通过计算扫描线与多边形边界的交点求得。第30页，共146页，2022年，5

29、月20日，17点32分，星期日通用多边形的扫描线填充算法下图给出了多边形区域实心填充的扫描线过程。对每一条与多边形相交的扫描线，与边的交点从左到右排序，且将每一对交点之间的像素位置包括这对像素在内，设定为指定颜色，本例中与边界的四个交点定义了两段内部像素：从x=10到14的5个像素，以及从x=18到x=24的7个像素。如果是用图案填充多边形，则沿一条扫描线的每一个像素颜色由与图案重叠的位置确定。穿过多边形区域的扫描线上的内部像素第31页，共146页，2022年，5月20日，17点32分，星期日有时情况比较复杂，当一条扫描线经过多边形的一个顶点时，扫描线在该顶点处与多边形的两条边相交，这种情况可

30、能导致在这条扫描线上的交点要增加两个点。下图给出了在顶点处与多边形相交的两条扫描线。扫描线y与偶数条边相交，必须将该顶点处的交点作为2个交点，才能正确标识该扫描线上的两对交点之间为内部像素段。扫描线y与多边形的5条边相交，必须将该顶点处的交点作为1个交点，才能正确标识该扫描线上的两对交点之间为内部像素段。通过观察相交边相对于扫描线的位置，可以发现扫描线y和扫描线y间的拓扑差异。对于扫描线y，共享一个顶点的两条相交边位于扫描线的两侧，对于扫描线y，两条相交边位于扫描线的同一侧。扫描线与多边形顶点相交，y生成奇数个交点，y生成偶数个交点第32页，共146页，2022年，5月20日，17点32分，星

31、期日可以通过顺时针或逆时针方向来搜索多边形边界，并观察从一条边移动到另一条边时顶点y坐标的相对变化来判别这个点。假如两条相邻边的三个端点y坐标值单调递增或递减，那么对于任何穿过该顶点的扫描线，必须将该相交顶点(中间的共享顶点)计为1个交点。否则，该相交顶点(中间的共享顶点)即为多边形边界上的一个局部极值，(极大或极小)，须将该相交顶点计为2个交点。总结：对凹多边形的填充判断比较复杂。凸多边形的扫描线填充对于凸多边形，扫描线填充过程可以简化，每一条扫描线与多边形至多有两个交点，可以使用坐标范围来确定哪些边与扫描线相交，当扫描线与单个顶点相交时，仅绘出该点本身，当有两个交点时，两交点之间的部分都是

32、多边形内部的点。第33页，共146页，2022年，5月20日，17点32分，星期日种子填充算法区域填充的另一种方法是从区域的一个内部点开始，由内向外逐点绘制直到边界。可以使用单一颜色或一个图案来填充一个区域。假如边界是以单一颜色指定的，则填充算法可逐个像素地向外处理，直至遇到边界颜色。该算法从一个内点开始检测相邻位置的颜色，若检测位置不是该边界颜色，就将它设置成边界颜色，再检测其相邻位置，这个过程持续到检测完区域边界颜色范围内的所有像素为止。区域填充算法要求区域是连通的。从一个当前位置检测其相邻像素有两种方法：4-连通和8-连通。4-连通即检测当前位置的上、下、左、右4个方向的相邻像素，8-连

33、通即检测当前位置的上、下、左、右、左上、右上、左下及右下8个方向的相邻像素。4-连通 8-连通4-连通区域 8-连通区域第34页，共146页，2022年，5月20日，17点32分，星期日第35页，共146页，2022年，5月20日，17点32分，星期日图案填充可以将一个区域填充为某种单一颜色，也可以用某种图案进行填充，还可以不填充而只绘制其边界。对多边形可以使用不同颜色、线宽和线型绘制其边框，还可以为区域的前向面和后向面设置不同的显示属性。填充图案可以用一个对不同位置指定不同颜色的矩形颜色阵列来给出，即一个填充图案可当作一个点阵来处理，其中每一位置点指定一种颜色。描述填充图案的矩阵是一个应用于

34、显示区域的掩模。有些图形系统可以设置掩模的初始位置，从该初始位置开始，掩模在水平方向和垂直方向反复填充直到整个区域都填满无重叠的掩模。这种用矩形图案填充一个区域的处理称为平铺，而矩形填充图案有时也称为平铺图案。填充图案的起始位置可设定在填充区内的任意位置，有些软件包将显示窗口的坐标原点作为图案的起始位置。第36页，共146页，2022年，5月20日，17点32分，星期日字符图元图形显示中常包括文字信息，包括字母、数字或其他字符等。字体是指一组按照特定尺寸和格式的模板字符样式。字体有两种不同的表示方法，第一种称为位图字体(或光栅字体)，每个字符都由一个二值形式的点阵图案表示，如图3.6a ，由于

35、所有字符都已完成扫描转换，绘制一个字符只需将该字符的位图直接映射或复制到帧缓存的指定位置，值为1的位对应的像素位置将用当前颜色进行显示。尽管可以由一组点阵字符生成不同尺寸以及类似粗体、斜体等其它字体，但字符放大时会有锯齿现象。第二种表示方法称为轮廓字体，又称笔画字体或向量字体。每个字符的外形轮廓均由直线和曲线段来描述，如图3.6b，字符轮廓的内部按填充区进行扫描转换处理。与位图字符相比，轮廓字体在进行放大时其字符形状不会变形。第37页，共146页，2022年，5月20日，17点32分，星期日第38页，共146页，2022年，5月20日，17点32分，星期日反走样在图形光栅化的过程中由于图元的坐

36、标点离散化为整数像素位置，因此光栅化后生成的图元具有锯齿形或阶梯状的外观。当我们把对象的连续表示(无限的分辨率)变换为对象的离散表示时，不可避免地会出现这类误差，这种由于低频采样(不充分采样)而造成的图形失真称为走样(aliasing)。另一个不太引人注目的走样现象是不同走向的线段具有不同的亮度，虽然所有线段都用同样的颜色亮度来显示，但一条斜线看上去要比一条水平或垂直线暗一些。这一现象的原因可由图解释，图中水平线上的像素间的距离为一个单位长度，而斜线上的像素间的距离大约为1.414个单位长度，密度上的差异造成亮度感觉上的差异。如果一个物体没有与像素栅格对齐，或者不能与像素栅格吻合，会出现篱栅问

37、题。图3.7.2(a)表示一道桩与桩之间的距离并非像素间距整数倍的篱栅。将该篱栅扫描转换后桩的端点都要向像素位置靠拢对齐，结果是桩之间的距离不再均匀相等图3.7.2(b) 。此现象有时称为局部走样，这时篱栅的总长度基本上是正确的。若要保持桩距均匀，篱栅的总长度就会明显失真图3.7.2(c) ，这一现象有时称为总体走样。第39页，共146页，2022年，5月20日，17点32分，星期日反走样尽管数学上的线段只有长度没有宽度，但光栅化后的线段为了可见，必须有一个宽度，帧缓存以像素为最小单位，若一条理想的线段在帧缓存里的宽度为一个像素，当仔细观察一个像素宽的直线时，会发现该线段只是部分覆盖了1个像素

38、大小的方形区域，如图。第40页，共146页，2022年，5月20日，17点32分，星期日第41页，共146页，2022年，5月20日，17点32分，星期日反走样提高显示器的分辨率只能减轻而不能消除锯齿问题。第42页，共146页，2022年，5月20日，17点32分，星期日反走样对于能显示两级以上亮度的光栅系统，可以采用反走样方法适当地修改沿图元边界的像素亮度，平滑边界，减小锯齿状、斑块状的亮度差异，改善显示效果。一种简单、直接的反走样方法，就是把屏幕看成由比实际更细的网格所覆盖，从而增加采样频率，然后根据这种更细网格，使用采样点来确定每个屏幕像素的合适亮度。这种在高分辨率下对对象进行采样并在较

39、低分辨率上显示其结果的技术称为过采样(supersampling)，也称为后滤波(postfiltering)。另一种方法是通过计算待显示的每个像素在对象上的覆盖区域来确定像素的亮度。计算覆盖区域的反走样称为区域采样(area sampling)，也称为前滤波(prefiltering)。还可以通过移动像素区域的显示位置而实现反走样，这种技术称为像素移相(pixel phasing)。第43页，共146页，2022年，5月20日，17点32分，星期日前滤波与后滤波滤波的概念来源于信号处理领域。若将亮度作为信号，则颜色均匀的、亮度缓慢变化的区域对应于低频部分，具有清晰边界的、亮度快速变化的区域对

40、应于高频部分。为了减少图像空间里的线段与其它线段的参差不齐现象，希望将亮度的突变 “抹平”，从信号处理角度来看，就是将高频率的成分“过滤掉”。前滤波就是在采样前对原始连续信号进行处理直接获取各个像素应有的亮度(在采样之前进行滤波) 。后滤波则首先从原始连续信号获取离散采样值，然后再用这些采样值计算像素值(在采样之后进行滤波)。第44页，共146页，2022年，5月20日，17点32分，星期日区域采样区域采样属于前滤波技术，把一个栅格网叠放在需要栅格化的物体上，对于每一个与该物体叠交的像素区域，计算该区域与物体叠交的百分比。该百分比决定了该像素的总体颜色中有多少成分来源于该物体，该像素区域与物体

41、叠交的百分比越高，该物体对像素总体颜色的影响就越大。图中用宽度为1个像素的长方形区域来代表一条直线，该长方形区域与每个叠交的像素的面积百分比通过解析方式算出。如果背景为黑色，直线为白色，计算所得的百分比可直接用来设定各像素的颜色(图3.7.4b) 。第45页，共146页，2022年，5月20日，17点32分，星期日 虽然图3.7.4b所示经过区域采样得到的直线的离散逼近看起来有些“模糊”，但它不再有从物体颜色到背景颜色之间的突然过渡。而这种突然过渡是使用普通扫描转换的结果(图3.7.4c) 。在减少图像失真与造成图像模糊两者之间力求折中是以滤波为基础的反走样技术的特征。第46页，共146页，2

42、022年，5月20日，17点32分，星期日直线段的过采样直线段的过采样可以用多种方式来完成。对于直线段，可以把每个像素分成一定数目的子像素，并统计沿直线路径的子像素数目，再将每个像素的亮度设置为正比于子像素数目的值。图中，每个正方形像素区域被分成9个大小相等的正方形子像素，阴影区域表示由Bresenham算法选择的子像素。由于任何像素中可供选择的子像素的最大数目为3，因次该方法能提供0以上的3种亮度等级。该例中位置(10,20) 像素的亮度设置为3；位置(11,21) 和(12,21)像素的亮度设置为2；位置(11,20) 和(12,22)像素的亮度设置为1。因此，该直线分布在较多数目的像素上

43、，并且通过在阶梯状附近显示有些模糊的直线路径，从而平滑阶梯状效果。如果要使用更多的亮度等级来实现直线段的反走样，就需要增加每个像素中的子像素采样数目，如16个子像素能给出0以上的4个亮度等级，25个子像素能给出5个等级。对于宽度超过1个像素的直线段的反走样，也可以采用该方法处理，如图。第47页，共146页，2022年，5月20日，17点32分，星期日 由于首先获得离散的采样值，然后再由这些采样值计算像素值，因此过采样是一种后滤波技术。但由于这只不过是用每个像素范围内有限的采样值来求准确的解析解的近似值，过采样技术也可认为是区域采样法的一种近似实现。第48页，共146页，2022年，5月20日，

44、17点32分，星期日低通滤波低通滤波是一种给每个像素计算出一个新值的后滤波技术。这个新值是该像素的原始值及其相邻若干像素的加权平均。计算所需的权值存放在一个(2n+1) (2n+1)形式定义的模板中，模板里所有权值的总和为1，图3. 7.7a为一个33的滤波器。为某一像素计算新值就是将滤波器以该像素为中心与像素栅格对齐。模板中每个权系数与其对应的像素值的乘积之和就是该像素的加权平均值。用这个滤波器处理图的像素值的结果如图3.7.7b 。第49页，共146页，2022年，5月20日，17点32分，星期日图形变换计算机绘图是产生三维场景的二维图像(屏幕上只能绘出二维图像)，计算机对物体绘图的过程类

45、似于用一部相机拍摄照片，如图4.1.第50页，共146页，2022年，5月20日，17点32分，星期日第51页，共146页，2022年，5月20日，17点32分，星期日绘图与拍照过程对比用照相机拍照的步骤大致如下：(1) 把照相机固定在三脚架上，并让它对准场景(视图变换)。(2) 对场景进行安排，使各个物体在照片中的位置是我们所希望的(模型变换)。(3) 选择照相机的镜头，并调整放大倍数(投影变换)。(4) 确定最终照片的大小(视口变换)。与此类似，把一个物体的三维坐标变换到屏幕上的像素坐标，共需要三个步骤：(1) 坐标变换，包括模型、视图和投影变换，变换过程用矩阵乘法表示，包括平移、旋转、缩

46、放、投影等。(2) 由于场景是在一个矩形窗口(相当于取景框)中绘制的，因此位于窗口之外的物体(或物体的一部分)必须被裁减掉。(3) 最后，经过变换的坐标和屏幕像素之间必须建立对应关系，这个过程称为视口变换。人们对上述过程总结出了一套规范的标准流程，首要任务是将场景中的各个对象进行建模，然后按规范流程对物体的顶点坐标分阶段地进行统一处理，最终获得二维屏幕图像。第52页，共146页，2022年，5月20日，17点32分，星期日几何变换计算机图形系统的基本功能之一就是模拟在三维空间中对物体进行操纵，这种模拟的空间操纵称为变换。在构建三维物体和场景的过程中，通过将简单图元进行平移、旋转、缩放等操作来构

47、建复杂对象和场景。可以从两种互补的观点来描述物体的变换。第一种是物体相对于一个固定的坐标系进行变换，即对物体的每一个点(顶点)进行变换，改变它的位置、方向或大小，称为几何变换。第二种观点将物体看做固定不动，而坐标系则相对于物体做变换，称为坐标变换。如要显示一辆在一片风景前驶过的汽车，我们既可以保持背景不动而让汽车移动(几何变换)，也可以保持汽车不动而让背景移动(坐标变换)。几何变换有时也称为建模变换。第53页，共146页，2022年，5月20日，17点32分，星期日基本二维几何变换平移、旋转和缩放是所有图形软件包中都具有的基本几何变换。平移：通过将位移量加到一个点的坐标上生成一个新的坐标位置，

48、可以实现一次平移。对于一个由多个顶点定义的对象，可以通过对所有顶点使用相同的位移量来实现平移。设原始坐标为(x, y)，平移向量为(tx, ty)，新坐标为(x, y )，则：若用列向量来表示坐标位置和平移向量(以前有些文献用行向量表示，目前的规范大多用列向量表示)，则：用矩阵形式表示二维平移方程为：第54页，共146页，2022年，5月20日，17点32分，星期日平移 平移是一种移动对象而不改变其形状的刚体变换。对象上的每一点移动了相同的距离。一条直线段的平移通过对其两端点分别平移而实现，多边形的平移也以类似的方法实现。第55页，共146页，2022年，5月20日，17点32分，星期日二维旋

49、转通过指定一个旋转轴和一个旋转角度，可以进行一次旋转变换，将对象的所有顶点按指定角度绕指定旋转轴旋转后，该对象的所有点都旋转到新位置。可以将对象绕与xy平面垂直的旋转轴(与z轴平行)旋转。二维旋转的参数包括旋转角、旋转基准点(xr，yr)，如图。基准点是旋转轴与xy平面的交点，正角度表示将对象绕基准点作逆时针旋转，负角度表示将对象绕基准点作顺时针旋转。第56页，共146页，2022年，5月20日，17点32分，星期日绕原点的二维旋转为了简化，先考虑当基准点为坐标原点时点P进行旋转的变换方程。如下图，r是点P到原点的固定距离，角是点的原始位置向量与水平轴的夹角， 是旋转角，利用三角等式，可得旋转

50、后的点坐标为：点的原始坐标为：第57页，共146页，2022年，5月20日，17点32分，星期日二维旋转的矩阵形式代入上式得：用列向量表示坐标位置，则旋转方程的矩阵形式为：其中，旋转矩阵为旋转变换的矩阵形式中，用列向量来表示坐标是目前标准的数学形式，早期的文献及图形系统有些用行向量表示坐标位置，这会改变执行旋转时矩阵相乘的顺序，现在OpenGL、Java、PHIGS、GKS等都按标准列向量方式表示。第58页，共146页，2022年，5月20日，17点32分，星期日绕任意点的二维旋转上图给出了绕任意基准点旋转的例子，利用图中的三角关系，可得绕任意基准点旋转的变换方程：这个通用的旋转方程包含了一个

51、加项，后面章节中将讨论更一致的方法。旋转也是一种不变形地移动对象的刚体变换，物体上的所有点旋转相同的角度，线段、多边形的旋转可通过将每个顶点旋转指定的角度来实现。第59页，共146页，2022年，5月20日，17点32分，星期日二维缩放改变一个对象的大小，可使用缩放变换，一个简单的二维缩放可通过将缩放系数sx 、sy与对象坐标相乘来实现（相对于坐标原点的缩放）。写成矩阵形式为：或其中S为缩放矩阵，缩放系数sx在x方向缩放对象， sy在y方向缩放对象，值小于 1将缩小对象的尺寸，值大于1则放大对象，若sx和sy不等将产生差值缩放，有些系统中，缩放系数可为负值，这不仅改变对象的尺寸，还产生相对于坐

52、标轴的反射。第60页，共146页，2022年，5月20日，17点32分，星期日相对于固定点的缩放可以选择一个在缩放变换后不改变位置的点，称为固定点（缩放的基准点），以控制缩放后对象的位置。固定点的坐标(xf，yf)可以选择为对象的中心，也可以选择为任意其他位置。多边形通过缩放每个顶点到固定点的距离而进行缩放。如下图，顶点(x, y)经过缩放后的坐标(x, y )为：第61页，共146页，2022年，5月20日，17点32分，星期日相对于固定点的缩放将乘法项与加法项重新组合后为：其中加法项xf(1sx)和yf(1sy)对于对象中的任何点都是常数。在缩放公式中包含固定点的坐标，类似于在旋转公式中包

53、含基准点的坐标。多边形的缩放可以通过将变换方程应用于每个顶点，然后利用变换后的顶点重新生成多边形而实现。第62页，共146页，2022年，5月20日，17点32分，星期日复合变换与齐次坐标在实际绘图时，常常需要对物体连续进行多次变换，例如先平移，再旋转，然后再放大，这就需要对该物体的点集按变换顺序依次进行，计算量较大。如果只对物体进行旋转和缩放两类变换，则可以先将这两种变换合成为一个复合变换，将两次运算简化为一次性的复合矩阵与坐标向量的乘法。对图形做上述一系列变换时，只要用点集与这个复合矩阵相乘即可。但如果在变换中有平移变换，矩阵就不容易合并了，因为平移变换与旋转、缩放变换的表示形式不一样；平

54、移变换为矩阵的加法，而旋转和缩放变换为矩阵的乘法。为了使各种变换的表示形式一致，使变换的合成更容易，人们引入了齐次坐标的概念。第63页，共146页，2022年，5月20日，17点32分，星期日齐次坐标如果将22的矩阵表达式扩充为33的矩阵，就可以把平移也表示为乘法形式，此时变换矩阵的第三列用于平移项，因而所有的变换公式都可以表示为矩阵乘法的形式。为了实现这种操作，必须解释从二维坐标到三元列向量的矩阵表示。标准的实现技术是将二维坐标(x, y)扩充到三维表示(xw, yw, w)，称为齐次坐标，其中齐次参数w是一个非零值，定义 ,这样，普通的二维齐次坐标可表示为(xw, yw, w) 。对于二维

55、几何变换，可以把齐次参数w取为任何非零值，因而坐标点(x, y)可以有无数个等价的齐次表达式，最方便的选择是简单地设置w =1，因此每个二维位置都可用齐次坐标(x, y, 1)来表示。利用齐次坐标，可以使我们能用统一的矩阵相乘的形式来表示所有的几何变换公式，这是图形系统中使用的标准方法。二维坐标位置用三元列向量表示，而二维变换用一个33的矩阵表示。第64页，共146页，2022年，5月20日，17点32分，星期日二维平移矩阵的齐次坐标表示使用齐次坐标，二维平移可表示为下面的乘法。该式可简写为：其中T(tx, ty)是上式中的33矩阵，可以简单地用T来表示平移矩阵。齐次坐标的诡秘性在于把2阶(或

56、3阶)的列矩阵相加变成了3阶(或4阶)的矩阵与矩阵相乘的运算。第65页，共146页，2022年，5月20日，17点32分，星期日二维旋转矩阵的齐次坐标表示使用齐次坐标，绕坐标原点的二维旋转可表示为下面的矩阵乘法。该式可简写为：其中R()为上式中的33矩阵，可以简单地用R来表示旋转矩阵。有些图形软件包只支持绕坐标原点的旋转，绕任意基准点的旋转需要一系列的变换操作来完成。第66页，共146页，2022年，5月20日，17点32分，星期日二维缩放矩阵的齐次坐标表示使用齐次坐标，相对于原点的二维缩放可表示为如下的矩阵乘法。该式可简写为：其中S(sx, sy)为上式中的33矩阵，可以简单地用S来表示缩放

57、矩阵。有些图形软件包仅支持相对于坐标原点的缩放，相对于另一固定点的缩放需要用一系列的变换操作来完成。此外还有其他一些变换，如反射、错切等。第67页，共146页，2022年，5月20日，17点32分，星期日逆变换对于平移变换，通过对平移距离取负值而得到逆矩阵，二维平移距离为tx和ty的逆平移矩阵为：这产生相反方向的平移，而平移矩阵与其逆矩阵的乘积是一个单位矩阵。逆旋转通过用负的旋转角度来实现，绕坐标原点旋转角为的二维逆旋转矩阵为：第68页，共146页，2022年，5月20日，17点32分，星期日逆变换旋转角的负值生成顺时针方向的旋转，因而旋转矩阵与其逆旋转矩阵的乘积为单位矩阵。将缩放矩阵用缩放系

58、数的倒数取代就得到缩放变换的逆矩阵。以坐标原点为中心、缩放参数为sx、sy的二维逆缩放矩阵为：该矩阵生成相反的缩放变换，因而缩放矩阵与其逆缩放矩阵的乘积为单位矩阵。第69页，共146页，2022年，5月20日，17点32分，星期日复合变换矩阵实际应用中对物体作几何变换时往往是多种简单变换的组合，可以将一系列连续的变换矩阵合成为一个复合变换矩阵，称为矩阵的合并或复合。由于引入了齐次坐标，基本的几何变换均可以表示为P= T P的形式，一个顶点坐标用列矩阵表示，复合变换时必须按操作的次序将每一步的变换矩阵左乘该列矩阵。因此复合变换的结合是每次的变换矩阵相乘，即将多个基本变换进行串乘： P= Tn (

59、T3 (T2 (T1 P)由于矩阵的乘法满足结合律，因此 P= （Tn T3 T2 T1 ) P= T P最后的结果也具有P= T P的形式， 这里， T= Tn T3 T2 T1由于场景中许多顶点用相同的顺序进行变换，通常在计算时先求出复合矩阵T，再用T与顶点列矩阵相乘，这与逐步用矩阵相乘相比能有效提高计算效率。第70页，共146页，2022年，5月20日，17点32分，星期日矩阵的串乘复合变换就是将多个基本变换进行串乘，这种方法非常适合于流水线结构的图形系统。假设对某点P执行一系列的变换操作后得到新点Q，这一变换序列表示为如下形式： Q=CBAP式中并没有括号，但变换的执行次序会直接影响计

60、算效率。一种方式是先执行变换A，再执行B,最后执行C。该执行顺序与下图的组合次序相同，是按步骤对多个点进行变换，每一步都是对已经变换过的点再进行新的变换。 Q=(C(B(AP)第71页，共146页，2022年，5月20日，17点32分，星期日图形系统的流水线结构如果只对原始的点进行一次总的变换，这个执行次序是最有效的，因为每次变换只是用一个总的变换矩阵与点的列矩阵相乘。如果需要对多个点进行变换，就把运算过程分成两个步骤。第一步，先计算： M=CBA第二步，把这个矩阵应用到每一点上： Q=MP这种运算次序对应于右图的流水线结构：在这种流水线结构中，先计算矩阵M，然后把M装载到流水线结构的变换处理