计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (6): 168-177.DOI: 10.3778/j.issn.1002-8331.1610-0260

• 图形图像处理 • 上一篇    下一篇

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

魏子衿1,2,3,肖  丽2,3   

  1. 1.中国工程物理研究院 研究生部,北京 100088
    2.北京应用物理与计算数学研究所,北京 100094
    3.中国工程物理研究院 高性能数值模拟软件中心,北京 100088
  • 出版日期:2018-03-15 发布日期:2018-04-03

Parallel dynamic level-of-detail construct algorithm based on domain decomposition

WEI Zijin1,2,3, XIAO Li2,3   

  1. 1.Graduate School of China Academy of Engineering Physics, Beijing 100088, China
    2.Institute of Applied Physics and Computational Mathematics, Beijing 100094, China
    3.CAEP Software Center for High Performance Numerical Simulation, Beijing 100088, China
  • Online:2018-03-15 Published:2018-04-03

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

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

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