基于数据并行的碰撞检测

Collision Detection Based on Data Parallelism

在建筑信息建模的精确碰撞检测应用中,数据量日趋庞大,但串行执行无法随处理机主频的增加而持续加速。针对该问题,构建面向多核及众核处理机的数据并行计算模型,基于此提出一种数据并行碰撞检测方法。对参与碰撞检测的模型进行立方体细分,去除数据相关性,设计数据并行的模型组合、冲突检测和归约计算过程,并分析算法的抽象形式和理论执行时间。实验结果表明,该方法具有可行性和持续可扩展性,可为解决数据密集型问题提供一种高效的数据并行方式。

The application of accurate collision detection in Building Information Modeling（ BIM） is facing the increasingly large amount of data,but the serial execution cannot continue to accelerate with the increasing frequency of the processor. Aiming at this problem,this paper constructs a data parallel computing model for multi-core and many-core machines and proposes a data parallel collision detection method based on this model. Firstly,models within collision detection are divided into cubes and the data correlation is removed. Secondly,the data parallel computing process with model combination, conflict detection and reduction calculation is designed. At last,the abstract forms and the theoretical execution times of the algorithm are analyzed. Experimental result shows that the proposed method has feasibility and continuous scalability which provides an efficient data parallel mode for solving data intensive problem.