-
实际应用
我们最初的目标比较简单：我们想要找到一种方法可以减少由于过多的爆破特效造成的过多的多边形。但是，经过开发这个多边形减面算法并且在人物模型上得出的比预期好的结果，我们觉得这个技术完全可以用于在游戏引擎中生成模型的细节层次(LOD)。预计这个在基本算法基础上改进的新的版本可以整合进Bioware的3D引擎中。现在，我们的美术人员只需要为每一个游戏中的物体创建一个细致的模型就可以了。一个预处理的过程就可以为模型减面。然后，如果游戏每秒的帧速率低于预定的限度，或者游戏中的一个物体离摄像机相当远的时候，我们就可以拿一个低面的模型来代替高细节的模型。可以在游戏运行期间来做这些事情从而增加游戏的可伸缩性。游戏可以根据当前运行系统的马力来调整这些东西。
-
实现细节
这种算法仅仅能够运用于三角形。如果需要的话可以把其它更多边的多边形简单地分解为三角形，除了这点就没有别的限制了。事实上，许多应用只用三角形。
大多数储存多边形物体的数据结构都是用一组顶点数据和一组三角形数据组成，其中三角形数据中包含了指向顶点数据的顶点索引数据。比如说：
Vector vertices[];
class Triangle {
int v[3]; // indices into vertex list
} triangles[];
VRML中使用的索引面集合节点数据是这种数据结构的另一个例子。当一个物体中的两个三角形有相同的顶点的时候，它们有相同的索引值（因此它们共享顶点列表中的相同的顶点）。
程序清单1 扩展后的数据结构
我们根据我们的多边形减面算法的需要对这个数据结构进行了添加。一个主要的改进是我们现在需要访问的信息已经不仅仅是每个三角形使用哪些顶点——我们同样要知道每个顶点被哪些三角形使用。此外，我们应该可以直接访问每一个顶点的邻接顶点（也就是边）。程序清单1展示了添加后的数据结构。
程序清单2 坍塌值的确定以及进行边的坍塌操作
成员函数 ReplaceVertex() 在多边形减面的过程中被用来处理边坍塌。数据结构中的顶点、三角形的添加、删除、或者替换必须保持正确，构造函数、析构函数以及另外的成员函数保证了这个过程的正确性。我们保存了面法线，因为它们在边选择的方程运算中被大量地用到。为了避免每次重新运算，我们还把每个顶点选择最优坍塌边以及坍塌值记录了下来。因为那些成员函数的实现是非常直观的，因此我没有将它们包含到这篇文章里面。如果你感兴趣，就去Game Developer网站上找到这个算法的源代码，然后简单的找一下就可以了。程序清单2包含了坍塌值的计算代码和进行边坍塌操作的代码。
有了这几个函数之后，多边形减面的操作就变得很简单了。先初始化物体的顶点和三角形数据，然后按照下面这样做：
while(vertices.num > desired) {
Vertex *mn = MinimumCostEdge();
Collapse(mn,mn->collapse);
}
在BUNNYLOD.EXE这个演示中，没有使用这么简单的循环。它还为了动画创建了一个附加的数据结构。
-
更好地利用数据
相比把用过之后移除的顶点、三角形数据信息丢弃，还不如把它们都保留下来，以便以后需要使用这些数据的时候不必重新运算多边形减面。这个特性很容易就能实现，只要把每一个坍塌后的顶点以及坍塌的顺序保存下来就可以了。
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/
文档 源英文文档 PDF
译者简介
卢立祎（bad_fish）
专注于高性能3D图像实时渲染和二进制跨平台复用技术。西南交通大学软件工程工学学士。多年游戏开发、架构设计经验。曾经参与多款单机、网络游戏开发。现任职于网易互动娱乐杭州研究中心
|
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<Triangle *> sides; for(i=0;i<u->face.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;i<u->face.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; List<Vertex *>tmp; // make tmp a list of all the neighbors of u for(i=0;i<u->neighbor.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<tmp.num;i++) { ComputeEdgeCostAtVertex(tmp[i]); } } |
|
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<Vertex *> neighbor; // adjacent vertices List<Triangle *> 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<Vertex *> vertices; List<Triangle *> triangles; |
发表评论 
打印本文
推荐本文
加入收藏
返回顶部
关闭窗口
