作　　者： ; ;

机构地区： 同济大学软件学院

出　　处： 《系统仿真学报》 2008年第S1期21-24,共4页

摘　　要： 高效的网格精简算法对于大规模DVE场景的实时绘制与传输均十分重要。目前已经提出了大量关于网格精简方法,但绝大多数网格优化算法都是面向实际应用的。我们却从计算机科学理论的角度出发,对这一经典问题重新进行了深入研究。首先,我们发现网格精简是一个最优顶点覆盖问题,即NP-Hard问题。然后,我们又提出了一种基于贪心算法的用于网格精简的最优顶点覆盖问题的近似算法。理论推导与实验数据都说明本文所给出的近似算法有效地减少了DVE场景的网格数量,能进一步提高DVE场景数据的网络传输速度。 High efficient mesh simplification algorithms are extremely important for interactive rendering and transmitting virtual world on Internet.Currently,huge publication on mesh simplification methods have been proposed for the purpose of optimizing large distributed virtual environments already.However,almost all of the proposed methods are oriented to practical applications.In this paper,with the perspective of theoretical computer science,we revisited this problem and reduced that this problem is Vertex Cover problem actually,which is one of classical NP-Hard problems.Moreover,we propose a new approximation algorithm DSS to it based on greedy algorithm.Both theoretical proof and experimental data show that the approximated algorithm can effectively decrease the mesh quantity of DVE,and improve transmission speed of DVE on Internet furthermore.

关 键 词： 虚拟现实 问题 顶点覆盖 近似算法 贪心算法 网格精简

领　　域： [自动化与计算机技术] [自动化与计算机技术]