计算机图形学与角色仿真

在计算机二维（2 Dimension，2D）图形学中，由于图形学算法的大量应用限制于计算机硬件的计算能力，研究者们在这方面花费了大量的精力，进行了深入的研究，也出现了很多著名的算法。计算机二维图形学中的一些关键技术包括几何变换、裁剪算法、扫描变换算法以及隐藏面隐藏线消除等算法。这些二维图形学中的算法，同样可以应用在三维（3D）图形学中，只是它们已经不再是研究的重点内容。在各位读者学习的过程中，也会涉及这些算法与技术。这些算法在某些方面也与本书的主题——计算机群组仿真技术相关，是几乎所有图形学技术及应用的基础。

1.图形学中的几何变换

在计算机图形学中，无论是二维图形学还是三维图形学，都离不开几何变换，以三维图形学的观点看来，二维变换是三维变换的特例。在几何变换算法中，变换是通过矩阵对向量的操作实现的。每一次几何变换都可以对应为一个变换矩阵，每一个顶点的坐标使用一个向量来表示，顶点的位置改变相当于将其坐标与变换矩阵相乘，从而得到一个新的坐标向量。当一个物体的所有顶点位置发生了同样的位置改变，而顶点之间的相对位置不变，那么就相当于针对该物体完成了位置改变。当物体的各个顶点相对位置发生了不同的改变，则该物体发生了变形操作。

2.裁剪算法

裁剪算法是计算机图形学中的一个重要部分，对于计算机图形学的执行速度有重大影响。裁剪是针对一个场景中物体可见性进行判断的算法，对于一个计算机所显示的场景来说，在逻辑上可能有上千上万件物体，但在计算机屏幕上，能同时被看到的可能只有几件，那么，对于本次计算机绘制来说，看不到的这些物体，就可以排除在当前的显示计算过程之外。

对于一个二维平面图像来说，看不到的部分包括屏幕外上下左右四个部分。由于图形系统中的每一个图形基本元素，都需要进行裁剪判断工作，因此，能否快速地判断物体是否位于窗口内，直接影响整个图形系统的效率。

裁剪算法有很多，效率的高低常常与所渲染的场景情况有关，因此需要根据实际情况选择裁剪算法。Sutherland-Cohen算法是一种针对直线的快速裁剪算法，该算法通过计算线段的两个端点与屏幕的位置关系，获取直线是否位于屏幕内。梁友栋-Barsky算法是另一种经典的图形裁剪算法，它不再考虑线段与屏幕边界的位置关系，而是直接将线段所在的直线与四条屏幕边界线方程进行求交，根据交点排序而决定裁剪结果。

3.多边形的扫描变换(www.xing528.com)

在计算机图形学的内部表示中，物体使用点、线、面、体表示，如三角形的图形只需要存储其三个顶点的位置即可。而要在计算机屏幕上显示，需要转换成像素表示，也称为点阵表示。顶点表示是用多边形的顶点序列来表示多边形，该方法几何意义强，占有内存少，但它不利于在屏幕显示时进行像素着色。点阵表示是用位于多边形内的像素的集合来表示多边形，该方法不包含多边形的几何信息，但便于使用帧缓冲器存储图像，并在屏幕上显示。

图形由顶点表示转换为点阵表示的过程称为光栅化。以多边形为例，图形的光栅化，即求出多边形内部的各个像素，并在帧缓冲器的对应元素上设置相应的灰度和颜色。这个过程也称为多边形的扫描转换，其转换算法主要有逐点判断法、扫描线算法、边缘填充算法、边界标志算法等。

4.隐藏面和隐藏线的消除

隐藏面和隐藏线的消除是计算机图形学中的另一个基本问题，讨论关于图形在二维屏幕上显示时，如何消除二义性的问题，消除的结果是使得图形能够反映不透光物体中被遮挡的部分。

消除算法的主要原理就是对曲面按Z值的递减顺序（即由前到后）进行排序，然后计算各曲线或曲面间的交线，针对交线之间的某一个区域内，选择位于前面的曲线或曲面作为该区域的最终颜色。Z缓冲器算法是最简单的隐藏面消除算法之一，用一个Z缓冲器存储着一个屏幕（X，Y）位置上的最大Z值，对于每一个显示对象，与相应的Z缓冲器内的值进行比较，如果更靠近观察者则修改颜色显示，并同时修改Z缓冲器的值，直至所有对象绘制完成。

对于隐藏面和隐藏线的消除，进一步的算法改进有扫描线算法、区域子分算法、曲线扫描线算法以及区间扫描线算法。