DVE场景精简的NP-Hard问题及其近似算法
高效的网格精简算法对于大规模DVE场景的实时绘制与传输均十分重要.目前已经提出了大量关于网格精简方法,但绝大多数网格优化算法都是面向实际应用的.我们却从计算机科学理论的角度出发,对这一经典问题重新进行了深入研究.首先,我们发现网格精简是一个最优顶点覆盖问题,即NP-Hard问题.然后,我们又提出了一种基于贪心算法的用于网格精简的最优顶点覆盖问题的近似算法.理论推导与实验数据都说明本文所给出的近似算法有效地减少了DVE场景的网格数量,能进一步提高DvE场景数据的网络传输速度.
DVE场景 虚拟现实 NP-Hard问题 最优顶点覆盖 网格精简 近似算法
陈庆 贾金原
同济大学软件学院图形图像研究中心,上海,201804
国内会议
福州
中文
21-24
2008-09-01（万方平台首次上网日期，不代表论文的发表时间）