论文部分内容阅读
如何提高大规模柔体碰撞检测的执行效率一直是计算机图形学领域的技术难点之一。传统的主流算法是通过选定一种或者多种包围盒(BV),构建包围盒层次结构(BVHs),将碰撞物体之间的碰撞检测转化为BVHs之间的碰撞检测,这样就可以加速检测的效率。选定包围盒之后,要建立BVHs数据结构,这个过程涉及到复杂的几何计算,虽然一般作为预计算的部分(pre-computation),但是所消耗的时间代价是高昂的;另外,基于包围盒的检测算法并不能很好地解决复杂形变几何体(complex deformable objects)的内部碰撞问题。本文提出一种基于图像空间的碰撞检测算法。不仅可以避免复杂的几何预计算,而且将物体间的碰撞检测和内部的碰撞检测有机地结合起来。算法主要分为两个部分:一部分是面片模型的光栅化,通过对碰撞物体的三角面片模型进行三维空间上的栅格化,将面片模型转化为栅格模型;另一部分是基于栅格模型计算碰撞发生后的最小相交体积。每个节点的受力可以转化为一系列栅格(文中称为像素,pixels)受力的累加,这样不仅可以避免复杂的积分运算,也可以将内部碰撞检测自然地包括在其中。本算法的主要时间消耗体现在面片模型的栅格化和受力计算这两个步骤上。为了解决这个问题,实验加入了GPU硬件加速技术,使得栅格化可以在多个运行模块上并行处理,从而大大加速了执行的速度和效率。