复杂三维游戏模型网格简化算法的研究文献综述

文献综述（或调研报告）：

本课题主要涉及三维网格模型的简化算法，本节将对现下流行的各种算法和研究现状做一个陈述。

（一）网格简化算法的研究现状

随着科学技术的进步，在计算机图形学、虚拟现实、计算机辅助设计技术、地理信息系统、医学图像系统等领域所构造和使用的模型越来越精细、越来越复杂，这些复杂的模型动辄就产生数以百万计的面片，而斯坦福大学的数字米开朗基罗计划(digital Michelangelo project)中著名的大卫(David)雕像的三角面片更是高达20亿。这些复杂的模型对计算机的存储容量、处理速度、绘制速度、传输效率等都提出了很高的要求。然而在很多情况下，高分辨率的模型并不总是必要的，模型的准确度以及需要处理的时间也要有一个折衷，因此必须用一些相对简单的模型来代替原始模型，这就是对模型进行简化。模型化简是指在保持原模型几何形状不变的前提下，采用适当的算法减少该模型的面片数、边数和顶点数。化简对于几何模型的存储、传输、处理，特别是对实时绘制有着重要的意义。早在20世纪70年代，就有学者讨论网格模型的化简问题，然而直到90年代以后，网格化简才得到深入的研究，并有了很多成功的应用。网格化简算法分类有多种，此处具体分为静态和动态两种。

1、静态化简

1.1顶点聚类法

顶点聚类方法首先用一个包围盒将原始模型包围起来，然后通过空间划分将包围盒分成若干个区域，这样，原始模型的所有顶点就分别落在这些小区域内，将区域类的顶点合并成一个新顶点，再根据原始网格的拓扑关系对这些新顶点进行三角化，就得到简化模型。这是一种通用的不保持拓扑结构的简化算法，它可以处理任意拓扑类型的网格模型，且速度较快。由于这个方法是将模型的包围盒均匀分割，所以无法保持那些大于分割频率的特征。同时新顶点的生成只是采取简单的加权平均，而没有较好的误差控制，因此这种方法生成模型的质量不高。

1.2区域合并法