计算机图形学学习笔记（5.2）：规则形体的表示

实体模型的三类表示：

构造实体几何表示（Constructive Solid Geometry，CSG），它将实体表示成立 方体、长方体、圆柱体、圆锥体等基本体素的组合，可以采用并、交、差等运算构造新的形体。

空间分割表示（Space-Partitioning），用来描述物体的内部性质，将包含一物体的空间区域划分成一组小的、非重叠的、连续实体（通常是立方体）。

边界表示(B-reps)的最普遍方式是多边形表面模型，它使用一组包围物 体内部的平面多边形，也即平面多面体，来描述实体。

表面模型的数据结构如下图：

对于一个多边形平面，其几何信息用几何表来组织，它包括顶点坐标和标识多边形平面空间方向的参数。具体包括：顶点表、边表、多边形表。

任何多边形平面都有两个面，内侧面和外侧面。一般来说，法向量方向指向物体外 部。当多边形顶点序列指定后，它满足右手定则。

除了这三张表给出的几何信息外，还需要增加额外的信息来表示其拓扑信息。例如， 将边表扩充成包括指向面表和顶点表的指针。如下图的例子：

由此可构造出翼边结构表示（Winged Edges Structure），它对于一个多面体的每一 条边指出它的两个相邻面、两个端点，以及四条邻边。这四条邻边好象伸展的翅膀， 所以叫翼边结构表示。

在存储多边形的几何信息和拓扑信息后，还需要用属性表存储多边形面的属性，指明 物体透明度、表面材质和纹理特征等。

多边形网格：

三维形体的曲面边界通常用多边形网格（polygon mesh）的拼接来模拟。这些多边形往往是简单的三角形或四边形。

下图是Maya中的多边形网格：

在构造实体几何法中，集合运算的实现过程可以用一棵二叉树（称为CSG树）来描述：

其中，树的叶子表示基础几何对象，非终端节点表示交并差补操作，根节点就是最终的CSG对象。

这种方法的优缺点如下：

优点：如果体素设置比较齐全，通过集合运算就可以构造出多种不同的符合需要的实体。 缺点：当用户输入体素时，主要是给定体素的有关参数，然后由系统给出该体素的表面方程，再由系统进行集合的求交运算，最后得到生成的实体。

这里面存在两个问题： （1）一是集合运算的中间结果难以用简单的代数方程表示，求交困难； （2）CSG树不能显式地表示形体的边界，因而无法直接显示CSG树表示的形体。

为了解决这两个问题，引入了光线投射算法。

光线投射算法

光线投射算法的核心思想是从显示屏幕（投影平面）的每一象素位置发射一根光线（射线）， 求出射线与距离投影平面最近的可见表面的交点和交点处的表面法矢量，然后根据光照模型计算出表面可见点的色彩和亮度，生成实体的光栅图形。 该算法的关键之处在于确定光线与距离投影平面最近的可见表面的交点，这可以通过集合成员分类算法实现。

具体算法步骤： (1)将射线与CSG树中的所有基本体素求交，求出所有的交点； (2)将所有交点相对于CSG树表示的物体进行分类，确定位于物体边界上的那部分交点； (3)对所有位于物体边界上的交点计算它们在射线上的参数值并进行排序，确定距离最 近的交点。

有三种表示方法：空间位置枚举表示、八叉树、BSP树。

空间位置枚举表示

将包含实体的空间分割为大小相同、形状规则（正方形或立方体）的体素，然 后，以体素的集合来表示图形对象。

用三维数组P[I][J][K]表示物体，数组中的元素与单位小立方体一一对应。

如上图，当P[I][J][K] = 1时，表示对应的小立方体被物体占据。当P[I][J][K] = 0时，表示对应的小立方体没有被物体占据

八叉树

八叉树（octrees）又称为分层树结构，它对空间进行自适应划分，采用具有层次结构的八叉树来表示实体。

下图展示了平面区域的四叉树表示：

对于3维实体，就需要八叉树来表示了。如下图所示，八叉树表示的形体非常容易进行集合运算：

BSP树

二叉空间分割（Binary Space Partitioning，BSP）方法每次将一实体用任一位置和任一方向的平面分为二部分。

最早应用BSP树的是在商业游戏《DOOM》中。与八叉树相比，它有两个好处：

自适应分割：BSP树可以减少场景树的深度，减少搜索时间；

有向超平面：有效地识别前向面和后向面