Abstract: To solve the problem of fast rendering large-scale visual data, a parallel dynamic level-of-detail construct algorithm based on domain decomposition is presented. The main contributions of this article are presented as follows. Firstly, the traditional progressive mesh algorithm is improved by using quadric error metric method, to provide faster implementation. Then, a self-adaptive domain decomposition algorithm based on model’s bounding box is put forward for cutting the original model into several blocks for parallel computing. Finally, a parallel dynamic level-of-detail construct algorithm by executing progressive mesh algorithm on the blocks in parallel is presented. As a result, this algorithm can generate high-qualified level-of-detail models, and has ideal speed-up ratio and expansibility. Compared to serial algorithms, this algorithm greatly reduces the execution time.

Key words: visualization, Level-Of-Detail（LOD）, progressive mesh, domain decomposition, parallel computing

摘要： 面向大规模可视数据的高速绘制问题，提出了一种基于区域分解的并行动态LOD（level-of-detail，层次细节模型）构建算法。算法首先改进了传统的渐进网格方法，实现了基于二次误差测度网格简化算法的渐进网格方法；接着提出了一种基于模型包围盒的区域分解算法，实现了原始模型的自适应区域分解；在每个子区域上，并行地执行渐进网格方法，实现了模型的并行动态LOD构建。实验结果表明，该算法可生成高质量的LOD模型，具备理想的加速比和可扩放性；与串行算法相比，该算法有效地提高了算法的执行效率。

关键词: 可视化, 层次细节模型（LOD）, 渐进网格, 区域分解, 并行计算