多核体系结构下变形物体实时连续碰撞检测算法研究

项目名称： 多核体系结构下变形物体实时连续碰撞检测算法研究

项目编号： No.60803054

项目类型： 青年科学基金项目

立项/批准年度： 2009

项目学科： 金属学与金属工艺

项目作者： 唐敏

作者单位： 浙江大学

项目金额： 19万元

中文摘要： 柔性物体的连续碰撞检测是当前碰撞检测领域的热点问题之一，本研究针对柔性物体连续碰撞检测中的效率瓶颈展开，拟研究柔性物体自碰撞检测剔除算法、元素测试冗余消除算法、多核体系结构下的碰撞检测任务分解算法。通过降低物体自碰撞检测数目，消除元素测试冗余，将碰撞检测任务在多核体系结构下并行分解，预期将复杂仿真场景中的冗余元素测试数目降低2 个数量级，并获得1 个数量级的处理加速。将最终使得复杂柔性物体（100k 数量级三角形）的连续碰撞检测在多核计算机上可以实时完成（平均每帧处理时间33ms 以下）。本研究具有通用性（支持拓扑结构固定/变化的柔性物体，支持物体间碰撞检测/自碰撞检测）、高剔除效率（降低冗余元素测试2 个数量级）、实时响应速度（1 个数量级的处理加速）、可扩展性（与核心数目近似成正比加速）。我们相信本项目的研发将为柔性物体碰撞检测计算加速开辟新的道路，同时为其他基于多核体系结构的算法加速提供参考。

中文关键词： 柔性物体；连续碰撞检测；多核体系结构；自碰撞检测；冗余元素测试

英文摘要： Continuous collision detection between deformable models is a key problem studying by recent collision detection community. The project is aimed to solve the efficiency bottleneck of continuous collision detection between deformable models by proposing an effective culling algorithm to reduce the potential candidate set of self-collision, an redundant removal algorithm of elementary tests, and an method to distribute computations under multi-core architecture. We are expecting to reduce the number of elementary tests by 2 orders of magnitude, and achieve speeding up in performance by 1 order of magnitude in scenes of complex deformable models. Eventually the continuous collision detection process for complex deformable models (100K triangles) can be performed in real-time (33ms per frame). The features of this project include generality (supporting fixed/changing topological structure, supporting inter-/intra objects collision detection), high culling efficiency (reduce the number of elementary tests by 2 orders of magnitude), real-time speed (improving performance by 1 order of magnitude), and scalability (quasi-linear acceleration by number of CPU kernels). We believe this research will open a new road for accelerating the computation of continuous collision detection between deformable models, and will provide a good reference for other algorithms on accelerating under multi-core architecture.

英文关键词： Defomable models; continuous collision detection; multi-core architecture; self-collision detection; redundant elementary tests