逐片操作
三角网格是顶点和三角形的列表。三角网格的一系列基本操作都是逐点和逐三角形应用基本操作的结果。最明显的,渲染和转换都属于这种操作。为渲染三角网格,我们逐个三角形渲染,如要向三角网格应用转换,如旋转和缩放等,应逐顶点进行。
焊接顶点
当两个或更多顶点(也许有误差)时,将它们焊接在一起是有益处的。更加准确地说,删除其余的,只剩一个。例如,我们要焊接图14.9中的A和B,有两个步骤:
(1)步骤1,扫描三角形列表,将对B的引用全部替换成对A的引用。
(2)步骤2,现在B是孤立点,将它从顶点列表中删除。
焊接顶点的目的有两个。首先,去除重复顶点,节约内存。这是一种重要的优化方法,使得对网格的操作(如渲染和转换)更快。其次,使几何上相邻的边在逻辑上也是相邻的。
上面讨论的是两个顶点的焊接,实践中,我们常常希望找出与焊接点邻近的所有顶点。这个想法是非常直接的,但有几个细节需要明确。
(1)焊接前应去除孤立点,我们不想让任何未被使用的点影响正被使用的点,如图14.10所示:
(2)当两个顶点均来自"细长"三角形,焊接可能产生退化三角形,如图14.11所示(这和边缩坍类似)。这样的三角形应被删除,通常它们的数量并不大。焊接常会显著减少顶点数,同时也会除去一小部分细长面。
(3)焊接时,似乎应该用原顶点的平均作为新顶点,而不是简单地选择其中一个而抛弃另一个。这种方式不偏向任何一个顶点,,在只有少量顶点需要焊接时这似乎是个好主意。然而,焊接自动进行的时候可能引起"多米诺"效应,导致原来不在误差容限内的多个点被焊接。
图14.12中,点A和B在误差容限内应被焊接。我们"聪明地"焊接这两个点,计算A和B的平均值得到一个新的点D。现在C和D又在容限范围内被焊接,最终产生E。结果是点A和C被焊接了,它们本不在误差容限内的。并且,我们"聪明的"尝试也失败了,因为A、B和C被焊接,但结果并不是这三个点的平均。
这还不是最坏的情形,至少没有点跑出误差容限外去。但确实可以故意用更多顶点和不同顺序制造这种恶毒的例子,更不幸的是实践中确实存在这种问题,建模程序和自动生成程序常这么干。其实,即使不平均生成新坐标,依然会有上面的问题。例如不考虑平均坐标,以为应用一个简单的规则"总是将高序数顶点焊接到低序数顶点"就可以解决这个问题。
有一些防止出现上述问题的方法。比如,可以先找出所有误差容限内的顶点组,再焊接它们;或者不考虑已经焊接过的顶点;或者记录原顶点坐标,当顶点和它们相比在容限外时就不焊接。这些方法都过于复杂,我们不应为不显著的性能而增加复杂性。焊接是为了去除重复顶点,而不是为了网格消减:即大量减少三角形数,而尽量保持三角网外形不变。关于网格消减,必须使用更加高级的算法。
另外一个问题是关于三角网的附加信息的,如表面法向量、纹理映射坐标等。当点焊接时,先前的不连续消失了,图14.8就是一个例子。
最后,顶点焊接的直接实现非常慢。即使在当今的硬件条件下,数千个点和面的焊接也要用掉数秒钟。寻找焊接顶点对的算法是O(n2)复杂度的。一次焊接后的顶点索引替换需要遍历整个三角形列表;删除一个顶点也需要遍历三角形列表以修复比删除点序号高的顶点的索引。幸运的是,加以思考,我们可以找到一个快得多的算法。
面拆分
面拆分即复制顶点,使边不再被共用,它和焊接刚好相反。显然,面拆分会导致拓扑间断,因为面不再邻接。而这正是我们的目的,使得几何间断的地方拓扑也是间断的(如角和边)。图14.13显示了两个三角形的拆分,尽管我们把两个三角形分开以显示这里有多个边和顶点,这只是为了显示,顶点没有移动,新的顶点和边其实是重合的。
实践中,我们经常要拆分所有面。
边缩坍
边缩坍是将边缩减为顶点的方法,与之对应的是顶点拆分。如图14.14所示,注意到边缩坍使边的两个顶点变为一个,共享该边的三角形(图14.14中阴影部分)消失。边缩坍常用于网格消减,因为它减少了顶点和三角形数量。
网格消减
网格消减是将三角形和顶点数较多的网格变为三角形和顶点数相对较少的网格,并且要求网格外观和主要顶点尽可能保持不变。Hugues
Hoppe指出zhi只用边缩坍就可以达到好的效果,选择要缩坍的边相对费时,视启发方法的复杂性而定。尽管选取缩坍对象的时间较长,但缩坍操作本身并不复杂。我们可将此过程离线记录下来,在实时需要时"重放"它,即可得到任意精细程序的风格。Hoppe的论文描述了如何利用顶点拆分来反演边缩坍过程,用此反演法生成的网格称为渐进式网格。