一种简单、快速、高效的多边形减面算法
A Simple, Fast, and Effective Polygon Reduction Algorithm    

如果你是一个游戏开发者，那么3D 多边形模型已经成为你日常生活中的一部分，并且你一定对一些3D概念例如每秒多边形数量、低面模型以及细节层次等等非常熟悉了。你可能也同样知道多边形减面算法的目的在于通过一个有着大量多边形的高细节的模型生成一个多边形数量比它少、但是看起来却跟原模型很相像的低面模型。这篇文章解释了一种实现自动减面的方法，并且附带的讨论了多边形减面的有用之处。在我们开始之前，我建议你去下载我的一个程序：BUNNYLOD.EXE，它展示了我将要阐述的这项技术。你可以在Game Develop网站上找到它。

• 问题的由来

　　在深入这个很“牛Ｘ”的3D算法之前，你可能会问你自己真的有必要关注它吗？要知道，已经有一些商业的插件和工具来为你减少多边形数量了。
　　然而，下面的几条理由会告诉你为什么需要实现自己的减面算法：

• 你使用的多边形减面工具生成的结果无法满足你的特殊需求，因此你希望做一个自己的工具。
• 你当前使用的多边形减面工具可能无法产生减面过程中的变化信息，而你却希望利用这些变化信息来使不同的细节层次之间的转换更加平滑。
• 你希望将生产过程自动化，这样的话美术人员就仅仅需要创建一个细节适当的模型，然后游戏引擎就能自动创建模型其余的细节层次。
• 你正在制作一个VRML浏览器，你希望提供一个菜单项来简化那些巨大的VRML文件。那些把这些巨大的文件放到网上的超级计算机用户没有想到这些文件在普通家用电脑上显示帧速率会比较低。
• 你在你的游戏中使用的特效改变了物体的几何形状，增加了多边形的数量，你需要一个方法来使你的引擎能够实时地快速减少多边形数量。

　　你对此怀疑？图1展示了一个具体的实例，一个游戏引擎对减少多边形这种特性的需求。
图1 爆炸效果对多边形数量的影响 　　在Bioware，我实现了实时的爆炸效果，并且把它们应用在了我们开发的一个游戏原型上，以便给我们的出版商留下深刻印象。玩家可以射击和爆破他们瞄准的实心物体表面的任意块。通过子弹撞击而改变游戏环境比典型的“定点爆破”这种只能在游戏世界中改变预先设定项的技术更棒。遗憾的是，重复不断的使用爆破效果会在物体上产生大量附加的三角形，如同你在图1中看到的一样。许多添加的面是很小的或者是碎片，不会对游戏的视觉效果产生丝毫的影响——它们仅仅是让游戏更慢。这种情况下就要求有实时的多边形减面功能，所以我开始寻找一种能够高效地完成这项工作的算法。

• 坍塌边

　　在我着手处理这个问题之前，我跟亚伯达大学图形实验室的一些人学习了多边形减面。（它让我跟一个团队一起工作，从而弄明白这个非常难的算法是如何工作的，并且弄明白什么样的技术适用于什么样的任务。）最近这个领域出现了很多研究成果，但其中大多数比较好的技术都是 H.Hpppe 的渐进网格算法的改进和变形（参见“更多的信息”）。那些技术都是通过重复不断的使用一个简单的边坍塌操作来降低模型的复杂度，见图2。
图2 边塌陷 　　在这个操作里面，u和v两个顶点（边uv）被选中并且其中一个顶点（这里是u）“移动”或者说“坍塌”到另一个顶点（这个例子里是v）。下面这些步骤说明如何实现这个操作：
1. 去除所有既包含顶点u又包含顶点v的三角形（换一种说法，去除所有以uv为边的三角形）。
2. 更新所有剩下的三角形，把所有用到顶点u的地方都用顶点v代替。
3. 移除顶点u。
重复以上的过程，直到多边形的数量达到了预期数量。每一次重复的过程中，通常会移除一个顶点、两个面、三条边。图3展示了一个简单的例子。
图3 多边形经过一系列边坍塌之后减少了面数

• 选择下一条边进行坍塌

　　要产生效果比较好的底面模型的诀窍在于要正确地选择坍塌的边，能够在坍塌的时候最小程度的影响模型的视觉变化。研究者提出了各种各样的方法来使在每一次坍塌的时候能够选择出“最小影响”的边。但遗憾的是，最好的那种方法非常非常复杂（也就是说，很难实现），并且要花大量时间用于运算。因此这推动我要找到一种能够在游戏运行阶段减少多边形面数的方法，我做了很多实验，最后终于为这个选择边的过程开发了一种简单又超快的方法来生成相当不错的低面模型。 　　显然，先要去除那些小细节。同时要注意的是，对于那些在同一平面上的表面，只需要很少的多边形就可以表示，同时高度弯曲的曲面则需要更多的多边形来表示。根据以上这些，我们定义了：一条边是否要坍塌，取决于它的边长与曲率值的乘积。为了找到在uv方向上距离别的三角形最远的u的临接三角形，我们通过比较两个面的法线的点积得到坍塌边uv的曲率值。方程式1展现了用更多正式符号表示的求边坍塌值的公式。详见源码（你可以在Game Developer网站上下载到源代码）。
Tu是包含顶点u的三角形的集合，Tuv是同时包含顶点u和顶点v的三角形的集合。
方程式1 求边坍塌值的方程式 　　你可以看到，这个算法在决定哪一条边坍塌的时候对于面的曲率和大小做了平衡。要注意的是顶点u到v的坍塌值不一定和顶点v到u的坍塌值相同。此外，这个公式对于脊状的边的坍塌也是有效的。即使这条脊有可能是一个锐角，或者是直角，都没有关系。图4举例说明了这种情况。非常明显的，在平面区域中间的顶点B，可以被坍塌到顶点A或者顶点C。角上的顶点C应该最后被保留下来。如果把上面的顶点A坍塌到内部的顶点B，那就会非常糟糕。不过，顶点A可以沿着脊坍塌到顶点C，这丝毫不会影响这个模型的外观。
图４　好的和差的边坍塌 　　如果你正在实作你自己的减面算法，你可能希望能够用这个公式做实验，来看看是否满足你的要求。例如，对于一个动画模型，你可能希望能够改进公式，使它能够在判断潜在的坍塌边的时候可以参考不止一个动画关键帧的数据。如果对于你来说，模型质量比减面算法所需要的执行时间更重要的话，你应该考虑使用Hoppe的函数。我们已经添加了很多扩展用来处理贴图坐标、顶点法线、邻接边，以及表面断裂（比如贴图接缝）。

• 结果

　　先显示一个原来的模型，然后显示简化后的模型，这是对多边形减面算法效果的最好证明。大多数的研究论文都用非常高面高细节的模型减面来证明它们的效果，原始模型接近100,000个多边形，简化后的模型只有10,000个多边形。对于3D游戏来说，更恰当（并且跟有挑战性）的测试是生成一个只有几百个多边形的模型，以此展示算法的强大威力。
图5 453个、200个以及100个顶点的小兔子模型（从左到右）
图6 随机选择坍塌边（200个顶点） 　　举个例子，图5展示了一个小兔子的模型，它是从一个由 Viewpoint Datalabs 制作的VRML文件中提取出来的。模型的最初版本（左边）包含有453个顶点和902个多边形。后边显示的是减少到200个顶点（中间）和100个顶点（右边）的模型。希望你能够对图中不同数量多边形模型的视觉外观看起来感到满意。图6展示了由于没有选择出正确的坍塌边而简化的模型，这里坍塌边的选择是随机的。
　　
图7 一个女性的人物模型，左边100%多边形数量，中间20%多边形数量，右边是4%多边形数量  当我们完成了动物实验之后，就要开始把这种算法应用在人物模型上了。图7展示了一个Bioware制作的女性人物模型的三个版本——4,858;1,000以及200个顶点。（根据欧拉公式，我们知道多边形的数量大致为顶点数的两倍。）这些模型图片是用平坦的方式渲染的，你能够明显的看到模型之间的不同之处。当我们使用平滑的方式渲染并且应用上贴图的话，那么这些差别就不会那么明显了。
　

• 实际应用

　　我们最初的目标比较简单：我们想要找到一种方法可以减少由于过多的爆破特效造成的过多的多边形。但是，经过开发这个多边形减面算法并且在人物模型上得出的比预期好的结果，我们觉得这个技术完全可以用于在游戏引擎中生成模型的细节层次(LOD)。预计这个在基本算法基础上改进的新的版本可以整合进Bioware的3D引擎中。现在，我们的美术人员只需要为每一个游戏中的物体创建一个细致的模型就可以了。一个预处理的过程就可以为模型减面。然后，如果游戏每秒的帧速率低于预定的限度，或者游戏中的一个物体离摄像机相当远的时候，我们就可以拿一个低面的模型来代替高细节的模型。可以在游戏运行期间来做这些事情从而增加游戏的可伸缩性。游戏可以根据当前运行系统的马力来调整这些东西。
　

• 实现细节

　　这种算法仅仅能够运用于三角形。如果需要的话可以把其它更多边的多边形简单地分解为三角形，除了这点就没有别的限制了。事实上，许多应用只用三角形。 　　大多数储存多边形物体的数据结构都是用一组顶点数据和一组三角形数据组成，其中三角形数据中包含了指向顶点数据的顶点索引数据。比如说：
Vector vertices[];
class Triangle {
　int v[3]; // indices into vertex list
} triangles[];
 VRML中使用的索引面集合节点数据是这种数据结构的另一个例子。当一个物体中的两个三角形有相同的顶点的时候，它们有相同的索引值（因此它们共享顶点列表中的相同的顶点）。   　 class Triangle { public: Vertex * vertex[3];// the 3 points that make this tri Vector normal; // orthogonal unit vector Triangle(Vertex *v0,Vertex *v1,Vertex *v2); ~Triangle(); void ComputeNormal(); void ReplaceVertex(Vertex *vold,Vertex *vnew); int HasVertex(Vertex *v); }; class Vertex { public: Vector position; // location of this point int id; // place of vertex in original list List neighbor; // adjacent vertices List face; // adjacent triangles float cost; // cached cost of collapsing edge Vertex * collapse; // candidate vertex for collapse Vertex(Vector v,int _id); ~Vertex(); void RemoveIfNonNeighbor(Vertex *n); }; List vertices; List triangles;   程序清单1 扩展后的数据结构 　　我们根据我们的多边形减面算法的需要对这个数据结构进行了添加。一个主要的改进是我们现在需要访问的信息已经不仅仅是每个三角形使用哪些顶点——我们同样要知道每个顶点被哪些三角形使用。此外，我们应该可以直接访问每一个顶点的邻接顶点（也就是边）。程序清单1展示了添加后的数据结构。
　　
　　
程序清单2 坍塌值的确定以及进行边的坍塌操作
　　　
　　成员函数 ReplaceVertex() 在多边形减面的过程中被用来处理边坍塌。数据结构中的顶点、三角形的添加、删除、或者替换必须保持正确，构造函数、析构函数以及另外的成员函数保证了这个过程的正确性。我们保存了面法线，因为它们在边选择的方程运算中被大量地用到。为了避免每次重新运算，我们还把每个顶点选择最优坍塌边以及坍塌值记录了下来。因为那些成员函数的实现是非常直观的，因此我没有将它们包含到这篇文章里面。如果你感兴趣，就去Game Developer网站上找到这个算法的源代码，然后简单的找一下就可以了。程序清单2包含了坍塌值的计算代码和进行边坍塌操作的代码。
　　　　
　　有了这几个函数之后，多边形减面的操作就变得很简单了。先初始化物体的顶点和三角形数据，然后按照下面这样做：
while(vertices.num > desired) {
　　Vertex *mn = MinimumCostEdge();
　　Collapse(mn,mn->collapse);
}
　　在BUNNYLOD.EXE这个演示中，没有使用这么简单的循环。它还为了动画创建了一个附加的数据结构。　 float ComputeEdgeCollapseCost(Vertex *u,Vertex *v) { // if we collapse edge uv by moving u to v then how // much different will the model change, i.e. the “error”. float edgelength = magnitude(v->position - u->position); float curvature=0; // find the “sides” triangles that are on the edge uv List sides; for(i=0;iface.num;i++) { if(u->face[i]->HasVertex(v)){ sides.Add(u->face[i]); } } // use the triangle facing most away from the sides // to determine our curvature term for(i=0;iface.num;i++) { float mincurv=1; for(int j=0;j < sides.num;j++) { // use dot product of face normals. float dotprod = u->face[i]->normal ^ sides[j]->normal; mincurv = min(mincurv,(1-dotprod)/2.0f); } curvature = max(curvature,mincurv); } return edgelength * curvature; } void ComputeEdgeCostAtVertex(Vertex *v) { if(v->neighbor.num==0) { v->collapse=NULL; v->cost=-0.01f; return; } v->cost = 1000000; v->collapse=NULL; // search all neighboring edges for “least cost” edge for(int i=0;i < v->neighbor.num;i++) { float c; c = ComputeEdgeCollapseCost(v,v->neighbor[i]); if(c < v->cost) { v->collapse=v-neighbor[i]; v->cost=c; } } } void Collapse(Vertex *u,Vertex *v){ // Collapse the edge uv by moving vertex u onto v if(!v) { // u is a vertex all by itself so just delete it delete u; return; } int i; Listtmp; // make tmp a list of all the neighbors of u for(i=0;ineighbor.num;i++) { tmp.Add(u->neighbor[i]); } // delete triangles on edge uv: for(i=u->face.num-1;i>=0;i--) { if(u->face[i]->HasVertex(v)) { delete(u->face[i]); } } // update remaining triangles to have v instead of u for(i=u->face.num-1;i>=0;i--) { u->face[i]->ReplaceVertex(u,v); } delete u; // recompute the edge collapse costs in neighborhood for(i=0;i ComputeEdgeCostAtVertex(tmp[i]); } }  

• 更好地利用数据

　　相比把用过之后移除的顶点、三角形数据信息丢弃，还不如把它们都保留下来，以便以后需要使用这些数据的时候不必重新运算多边形减面。这个特性很容易就能实现，只要把每一个坍塌后的顶点以及坍塌的顺序保存下来就可以了。
　　BUNNYLOD.EXE这个演示就是使用这个方法。一开始，小兔子模型在大约1秒钟时间内从450个顶点减少到0个。然后，模型会不断的增加细节，并且是在一些特殊的多边形数量的阶段，左边的进度条会同时通过动画方式来表示这个过程。另外还有一种动画方式是从0到全部顶点不断增加。
　　　　
　　边坍塌序列也可以用在渐进传输中。就像交错存储的.GIF和.JPG图片可以在网络传输中不断增加细节一样，一个物体的顶点可以通过坍塌过程的倒序排列来进行数据广播。接受的计算机可以不断的根据接收到的数据流来重建并且显示这个模型。这个主意非常棒，但是或许现在来看和游戏开发者还没有什么关系。 　　模型的LOD在很多游戏中是一个非常重要的组件。根据我们的算法生成的坍塌序列，可以生成很多细节层次的模型来表示模型的不同的LOD。在交换模型的时候有一个问题就是玩家常常会注意到它的发生（这种现象叫做“跳出”）。一个对付“跳出”现象的解决方案是在两个模型中间做平滑变形。为了能够在两个模型之间做变形，必须把其中一个模型的顶点映射到另一个模型上。幸运的是，这些信息可以从边的坍塌序列中提取出来。BUNNYLOD.EXE也演示了变形的例子。

• 可供选择的边坍塌技术

　　多边形减面算法不是创建低面模型的唯一选择。美术人员做出来的底面模型往往比通过算法算出来的低面模型更好。其中一个原因是算法无法从宏观上把握模型。从一方面来讲，美术人员了解他（她）所创建的模型（比如兔子、椅子，等等），并且能够从审美的角度上决定如何去减少物体的面数。人类的视觉系统会偏向于某几个细节，比如说眼睛和嘴部，并且很少去关心其它部位的细节，比如锁骨或者膝盖。另一方面，我们这个简单的算法仅仅比较了很少的点积和边长，并且明显缺乏一种智慧来自动识别那些人感觉比较重要的部位并进行优化。使用多边形减面算法的优势在于能够让这个过程自动化。
　　 　　
　　图8 技术对比 　
　　另一种在游戏中使用的制作LOD的技术是使用参数化曲面来描述几何物体，参数曲面片可以镶嵌在需要细化的部位。Shiny的MESSIAH引擎使用了相似的方法。当然，这些基于表面的方法更加可取（也许是最佳的）。图8举了一个2D的例子说明了这个优势。一个正八边形通过参数化的方法去掉一条边生成了一个正七边形。如果用坍塌掉一条边的话正八边形就生成了一个不规则的图形。 　　遗憾的是，并不是所有的情况都适用参数化曲面的。有一些情况要求物体在渲染时生成多边形的时候相邻的表面能够很好的吻合在一起（没有裂缝和T型连接）。并且，有很多锯齿状的物体使用参数化表面无法取得良好的效果，这是因为需要的表面也许并不会比多边形的数量少。以多边形为基础的减面的方法一般来说更加有用，并且可以工作在当前类型的模型上。 　　我希望我提供的这些信息和例子程序能够派上用场，虽然这篇文章没有触及到贴图坐标、顶点法线、邻接边、单一拓扑、贴图接缝等等。这些题目都留作给读者的练习题。此外，对此算法的变化和改进都是有探索价值的。一个令人兴奋的主题是适应性简化，可以根据运行时的参数来使模型的不同部分使用不同的细节层次进行渲染。这个对于室外地形环境非常有用，这样的话离视点近的部分就可以又更多的细节表现。

• 更多的信息

　　最近多边形减面已经成为一个很热门的搜索主题，并且大部分的文献都能够在计算机图形学会议的会议记录里面找到。另外一些资料你可以看：

• Cohen, J., M. Olano, and D. Manocha. “Appearance-Preserving Simplification”, SIGGRAPH ‘98.
• Hoppe, H. “Progressive Meshes,” SIGGRAPH ‘96, pp. 99-108.
• Luebke, D. and C. Erikson. “View-Dependent Simplification of Arbitrary Polygonal Environments”, SIGGRAPH ‘97, pp. 199-207.
• I have a demo on my university web site at http://www.cs.ualberta.ca/~melax/polychop
• H. Hoppe, the Guru of polygon reduction, maintains a web site at p://research.microsoft.com/~hoppe/