计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (13): 181-190.DOI: 10.3778/j.issn.1002-8331.1703-0029

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

改进顶点聚类方法的并行核外模型简化算法

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

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

Parallel out-of-core model simplification algorithm based on improved vertex clustering

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, Beijing 100094, China
    3.CAEP Software Center for High Performance Numerical Simulation, Beijing 100088, China
  • Online:2018-07-01 Published:2018-07-17

摘要: 面向大型网格模型的简化问题,提出了一种基于顶点聚类方法采用多数据流策略的并行核外模型简化算法。算法首先将传统顶点聚类简化算法中的代表点计算方法改进为顶点筛选方法,进而设计了一种适用于分布式计算环境的数据外存储策略,最后采用多数据流的思想改进单元筛选与顶点筛选两个方法的执行过程,从而形成完整的并行核外模型简化算法。实验结果表明,该算法有效避免了基于区域分解的并行算法对模型结构的破坏,提高了模型简化的质量;相比于多种现有的并行算法,该算法极大程度优化了并行资源的负载分配问题,具备更为理想的加速比和并行效率。

关键词: 大型网格模型, 网格简化, 核外算法, 顶点聚类, 多数据流, 并行计算

Abstract: To solve the problem of model simplification for large meshes, a parallel out-of-core model simplification algorithm based on vertex clustering and multi data stream is presented. The main contributions of this paper are presented as follows. Firstly, the procedure for representative point calculation in traditional vertex clustering algorithm is promoted by using the vertex filtering method. Secondly, a strategy for data external storage in distributed computing environment is presented. Thirdly, the execution of two methods named cell filtering and vertex filtering is improved using the multi data stream theory. Finally, the three improvements are put together to form the integrated parallel out-of-core model simplification algorithm. As a result, this algorithm can avoid the destruction of original models generated by the domain decomposition procedure, so as to improve the simplified models’ quality. Compared to several parallel algorithms, this algorithm drastically optimizes the load distribution efficiency, and has a better acceleration and parallel efficiency.

Key words: large meshes, model simplification, out-of-core algorithm, vertex clustering, multi data stream, parallel computing