基于八叉树的柔性体切割仿真中并行化的碰撞算法

发布时间：2018-03-16 18:27

本文选题：柔性体　切入点：碰撞检测　出处：《计算机辅助设计与图形学学报》2017年12期 　论文类型：期刊论文

【摘要】：为了提高柔性体切割仿真中碰撞处理的运行效率,并解决切割影响变形计算稳定性问题,提出基于八叉树的柔性体切割仿真中碰撞算法的并行化实施方法.该方法使用基于链接体素和自适应八叉树网格的柔性体模型,前者用于描述物质的连接性和构造用于碰撞和图形显示的面网格,后者用于变形计算;在粗略碰撞阶段对八叉树网格构造空间Hash表并构造潜在碰撞对;在精细碰撞阶段根据体素中心的距离场值,使用考虑拓扑关系的距离场插值方法检测碰撞并计算入侵深度;柔性体之间的碰撞和自碰撞处理使用独创的多级检测和约简方法在GPU上运行,同时在CPU上使用多线程运行切割工具与柔性体的碰撞处理;切割算法切断被切割工具扫过的链接,重构切口附近的面网格,递归细分并复制被切割工具扫过的八叉树单元,并使用快速行进法更新距离场.仿真实验结果表明,与3个CPU线程的实现相比,文中GPU加速的柔性体碰撞和自碰撞算法可以将处理速度提高76%~215%;而与单个CPU线程的实现相比,3个CPU线程实现的切割工具与柔性体的碰撞算法可以将处理速度提高132%~190%.
[Abstract]:In order to improve the running efficiency of collision processing in flexible body cutting simulation, and to solve the problem that cutting affects the stability of deformation calculation, A parallel implementation method of collision algorithm in flexible body cutting simulation based on octree is proposed, which uses flexible body model based on link voxel and adaptive octree mesh. The former is used to describe the connectedness of matter and to construct the plane mesh used for collision and graphic display, the latter is used for deformation calculation, and the spatial Hash table and potential collision pair are constructed for octree grid in rough collision stage. According to the distance field value of voxel center in fine collision phase, the distance field interpolation method considering topological relation is used to detect collision and calculate intrusion depth. Collision between flexible bodies and self-collision processing uses the original multi-level detection and reduction method to run on the GPU, at the same time, the multi-thread is used to run the collision processing between the cutting tool and the flexible body on the CPU; the cutting algorithm cuts off the links swept by the cutting tool. The mesh near the notch is reconstructed, the octree unit swept by the cutting tool is subdivided recursively, and the distance field is updated by using the fast moving method. The simulation results show that compared with the implementation of three CPU threads, In this paper, the flexible body collision and self-collision algorithm accelerated by GPU can increase the processing speed by 76 / 215, and compared with the implementation of a single CPU thread, the collision algorithm between the cutting tool implemented by three CPU threads and the flexible body can increase the processing speed by 132 / 190.
【作者单位】：青岛大学计算机科学技术学院;
【基金】：国家自然科学基金(61303078) 山东省科技发展计划(2014GGX101048)
【分类号】：TP391.9

【相似文献】