游戏引擎中的三角形栅格化

这篇文章讲游戏引擎中的三角形栅格化是什么。三角形栅格化是对3D物体的一种描述方式，是在游戏引擎中绘制3D场景的第一步。

在游戏引擎中，绘制一个场景之前，需要准备好四个要素：

场景本身。也就是需要绘制的对象
虚拟摄像头。从哪个角度观察要绘制的场景
光源。需要一个或多个光源来照亮场景
对象的材质。决定了绘制的对象如何对光源做出反应，产生不同的效果

本文中，重点讲述场景本身，即需要绘制的对象是如何表示并储存在计算机中的。

描述场景

场景由一些3D对象组成。对于那些不透明的对象，它是实心的还是空心的对于观察者并没有影响。所以我们可以把它们当做空心的处理，只需画出它们的表面。

对于透明的对象，因为考虑到折射的效果，实心和空心就不完全一样。不过，实际上大部分游戏引擎忽略了折射效果，因为这既浪费计算资源，提升场景逼真程度也有限。

所以，我们只介绍怎样在计算机中描述对象的表面。

曲面

数学方程可以描述空间中的曲面。比如 $x^2+y^2+z^2=1$ 描述了一个球心在原点、半径为1的球面。

然而，用数学曲面来描述游戏对象的表面不太现实。大部分游戏对象的表面不规则，比如人体表面，很难找到一个数学方程能精确刻画。

不过，不规则表面上很小的一部分却可以用数学方程去近似。考虑平面曲线，你可以在曲线上采样一些点，将相邻的点连接起来得到近似曲线的形状。采样点越密集，得到的线段就越逼近原来的曲线。

同样的道理，要描述一个3D曲面，也可以在这个曲面上采样很多的点，并将相邻的点连接成面。这些小的平面组合在一起，就很接近原来的曲面。采样点越密集，结果就越逼真。

栅格化

三角形栅格化

用来逼近平面曲线的最小单元是线段，那么在用来逼近3D曲面的最小单元是什么呢？是三角形。因为三个点可以确定一个平面（除了三点共线的特殊情况），而任意选择四个点就有可能不在一个平面上。

用三角形的集合近似一个3D曲面，就叫做三角形栅格化。这个三角形集合被称为网格(Mesh)。不过，三角形栅格化面临一个问题，就是网格的密集程度的问题。三角形越小，网格越密，需要的存储空间就越多，绘制时消耗的计算资源越大。相反，如果网格很粗，三角形很大，曲面就会粗糙。如下图所示

固定栅格化

把握网格的疏密(又称为细节级别，Level of Details，简称LOD)很重要。特别是在游戏中，同一个对象在不同的情形下可能需要不同LOD。比如一个对象距离摄像头很远时，LOD就没有必要很高。而当它距离摄像头很近时，LOD太低就会使它看起来粗糙。所以，没有一个LOD能够适应所有情形。

因此，有些自适应的栅格化技术被发明出来，为同一个对象在以不同的大小绘制时提供不同的LOD。

网格的数据结构

网格用什么样的数据结构来表示呢？

三角形列表

一个三角形可被三个顶点的位置决定。因此，每个三角形存储三个点的坐标即可。如果要把一个有 $n$ 个三角形的三角形网格存储下来，最直接的方式是使用一个 $3n$ 大小的顶点数组，索引为 $k$ 的三角形的三个顶点分别存储在索引为 $3k$ ， $3k+1$ 和 $3k+2$ 的位置。这样的一个数组称为三角形列表。

三角形列表

顶点顺序

一个三角形存储三个顶点坐标，这三个坐标的顺序是任意的么？如果这个三角形的两面完全一样，三个顶点的顺序就随便了。不过，3D对象表面是一个封闭曲线，将空间隔开为内部和外部。如果我们把一个三角形面向外部的一面称为正面，另一面称为反面，那么三角形的反面从来不会被绘制(对于不透明的物体)。所以，要绘制这个三角形时，如果发现它是反面面向镜头，就可以跳过这个三角形。

我们可以用三角形的三个顶点的存储顺序来标记一个三角形哪里是正面，哪里是反面。如果从一个方向看，三个顶点按照存储顺序是逆时针旋转的，就把这面当做正面，反之，如果是顺时针，就当作反面。