基于区域分解的并行动态LOD构建算法

摘要

面向大规模可视数据的高速绘制问题,提出了一种基于区域分解的并行动态LOD(level-of-detail,层次细节模型)构建算法.算法首先改进了传统的渐进网格方法,实现了基于二次误差测度网格简化算法的渐进网格方法;接着提出了一种基于模型包围盒的区域分解算法,实现了原始模型的自适应区域分解;在每个子区域上,并行地执行渐进网格方法,实现了模型的并行动态LOD构建.实验结果表明,该算法可生成高质量的LOD模型,具备理想的加速比和可扩放性;与串行算法相比,该算法有效地提高了算法的执行效率.%To solve the problem of fast rendering large-scale visual data,a parallel dynamic level-of-detail construct algo-rithm 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 implemen-tation.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 algo-rithm by executing progressive mesh algorithm on the blocks in parallel is presented.As a result,this algorithm can gener-ate 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.