【作者】 刘湘云；

【导师】 邹北骥；

【作者基本信息】 湖南大学 ， 计算机应用技术， 2004， 硕士

【摘要】 在计算机辅助设计、计算机动画、科学计算可视化、虚拟现实等许多图形应用系统中，三维物体常用三角网格模型表示，复杂的三角网格模型将给计算机存储与传输三维物体带来困难。可是，很多情况下人们并不需要对每一模型的细节都作详细的刻画，如：一个复杂的场景中，远景物体就没有必要有过多的细节。因此，可根据对模型细节程度的要求不同而对复杂模型进行一定的简化。 本文针对三角网格模型的快速简化方法进行研究。首先，论文介绍了三角网格模型的有关概念和误差的评估方法，对当前各种简化算法进行了详细的综述。然后，在总结折叠型简化算法简化过程的基础上，提出了一个基于概率值连续折叠的三角网格简化算法。算法以三角形折叠为基本简化操作，可调加权控制函数作为折叠误差控制三角形的简化顺序，根据所有三角形的误差分布，构造一个概率分布函数，为每个待折叠的三角形计算一个折叠概率值。在简化过程中，所有三角形按其概率进行折叠，误差较小、概率值较大的三角形优先得到简化。由于满足简化条件的三角形个数增加，每次误差排序后，三角形折叠的个数由传统的1个增加为若干个，折叠的方式也由传统的单次折叠简化改进为连续折叠简化。在简化率要求相同的条件下，连续折叠简化的排序次数大大减少。因此，从误差优先级排序的角度加快了简化速度。 最后，本文设计了一个演示系统，实现了本文算法，并从理论分析与实际系统运行两方面验证了本文算法和传统的单次折叠简化算法的时间效率，得出了连续折叠简化的排序时间较单次折叠简化的排序时间快m倍的结论(m为平均连续折叠的三角形个数)。演示系统的实验结果表明，本算法在保持误差基本相同的情况下，整体简化速度较单次折叠提高10倍以上。另外，本文还将本算法与包络控制简化算法进行了比较，结果表明，本算法简化速度快，简化结果更加均匀。最后通过一组实验验证了选择不同的控制权值可以得到不同形状的简化结果。更多还原

【Abstract】 Triangle mesh models are widely used in many computer graphics systems, such as computer-aided design, computer animation, scientific visualization and virtual reality. A complex triangle mesh model will be heavy burden for computer to access and transfer it. However, not all 3D objects are constructed with much more details, for example, an object far away from viewers may have less detail than an object nearby. So in most of cases, we can simplify a complex triangle mesh model to suit different demands.This thesis is dedicated to a high efficiency method on simplifing triangle mesh models. First, we introduce some basic concepts about triangular mesh models and error evaluating methods, and then we survey some existed model simplification algorithms. On the basis of our research work, we present a new algorithm for simplifying triangle mesh models, which is based on probability function and applications of continuous collapse operation for triangles in meshes. In our algorithm, an adjustable weighted control function is used in controlling the simplification procedure. Specially, a probability function is constructed by means of error distribution. Each triangle in a mesh is distributed to a corresponding probability value by computing. All triangles are gradually collapsed according to their probability value. Triangles with a lower error and an upper probability are collapsed preferentially. In this way, after reordering triangles’ errors, the number of collapsed triangles increases from one to several ones, and the single collapse mode is improved to the continuous collapse mode. Under same simplification rate, the sorting operation in continuous collapse simplification algorithms reduced remarkably when compared with that in single collapse simplification algorithms. As a result, the algorithm for simplifying triangle mesh model based on probability continuous collapse can speed up the simplification procedure on the aspect of error priority sort.In this paper, we give an analysis on the efficiency of our algorithm in theory and have also developed a demo system based on our algorithm. Results from our system show that the speed of continous collapsing operation is m times faster than single collapsing operation (m is the average number of continuous collapses), which is just consistent to the result from our theoretic analysis. And also, time consumption by running our demo system is 10 times less than that of any single collapsesimplification algorithm under the same error tolerance. Besides, we also compare our algorithm with simplification method by using the envelope as error tolerance. Result indicates that the speed of our algorithm is much faster than that of simplification method by using the envelope as error tolerance.更多还原