大规模复杂场景中非刚体模型的碰撞检测研究

季宏宇

吉林农业大学信息技术学院，吉林长春 130118

0 引言

随着图形图像学的进一步发展，在计算机图形仿真领域，大规模复杂场景中非刚体模型的碰撞检测已成为重要的研究课题。为了使模拟效果更加真实，需要对碰撞的发生时间发生点做出准确及时的检测，并做出相应的处理，否则会发生穿透现象，破坏真实感。

1 非刚性物体模型分析

非刚性物体是指现实物理世界中的物体，它们是非刚性的，在运动的过程中会产生一定的形变。物体的变形一直是计算机图形学的研究热点，1986年，Weil[1]首次讨论了基于物理模型的非刚性物体的变形问题。当时仅是用来模拟布料悬挂在钉子上的形态。Feynman则提出了一个更完善的布料悬挂模型。后来，许多研究者相继开始采用各种物理模型来对非刚性物体进行运动变形模拟。

Provot[1]作为此领域的权威人士，对于非刚性物体的自碰撞检测问题提出了一种解决方案。方案中指出，在某一区域内，若曲率足够小，则在这块区域内不会发生自交现象。经进深入的研究与分析，我们可以将大规模复杂场景中的非刚性物体进行三角面片划分，当三角面片划分到足够小的空间时，可看作该点不发生自碰撞检测。如果检测到该点已经发生碰撞，那么该点只能与复杂场景中其他物体发生了碰撞检测。这样我们将非刚性物体的自碰撞检测问题归结到刚性物体的碰撞检测问题。

2 非刚体模型的建立

在多种非刚体模型中，Provot建立的质点-弹簧模型较好地将织物的物理特性进行了抽象。该模型不仅简单，且能达到实时的效果。他把非刚体划分为矩形网格，网格的交点称为虚拟质点，每两个质点之间用弹簧相连。

该模型的主要思想是把一块非刚性物体划分为m×n的矩形网格，每个网格节点是一个虚拟质点，每个质点用弹簧相连，弹簧无质量且其长度不能为零。非刚体的质量分布在质点上。用作连接的弹簧有三类，分别是：结构弹簧、剪切弹簧和柔性弹簧。

每个质点受到内力和外力的作用。内力是指连接到质点的各个弹簧对其作用力的合力；外力是指重力、风力、空气阻力、人机交互环境中人为的作用力等各种力对质点作用力的合力。

利用质点-弹簧模型可以非常方便的对非刚性物体进行三角分割，每个三角形是构成非刚性物体表面的基本几何单元。

3 基于层次包围盒的并行碰撞检测

3.1 基于层次包围盒的并行碰撞检测概述

空间分解法与层次包围盒法是当前的两类碰撞检测算法。空间分解法以对某一单元格或相邻单元格的几何对象进行相交测试。八叉树、BSP树是应用较广的方法。层次包围盒法是利用体积略大而几何特性简单的包围盒将复杂几何对象包裹起来，在进行碰撞检测时，首先进行包围盒之间相交测试，只有包围盒相交时，才对其所包裹的对象，做进一步求交计算。在构造碰撞体的包围盒时，引入树状层次结构，可快速剔除不发生碰撞的元素，减少大量不必要的相交测试，从而提高碰撞检测效率。在非刚体模型中，基本几何体为三角形；同时，对非刚性物体周围的物体也进行三角化分割。

在对非刚性物体进行三角化分割后，为每个三角形建立包围盒，然后自下而上建立一棵层次包围盒二叉树；同时，非刚性物体周围的物体也按一定的规则建立层次包围盒二叉树。于是碰撞检测归结为两棵二叉树的判交算法。

由于非刚性物体本身结构非常复杂，为了保证实时效果，本文经分析论证，采用了当前较为流行的层次包围盒[2，3]算法来实现碰撞检测。

3.2 基于层次包围盒的串行原理与算法设计

两个物体的层次包围盒构建完成，就可以通过遍历他们的平衡树来进行他们之间的碰撞检测，在此，我们引入任务树的概念[4-5]。将遍历两个物体的平衡包围盒树的过程定义成一颗任务树的遍历。

碰撞检测的过程可以通过一个任务树的遍历来实现。如果任意子任务中发生了碰撞，则判定两个物体发生了碰撞。如果遍历了任务树后没有检测到有子任务发生过碰撞，则判定两个物体发生了碰撞。因此一个任务的结果可以通过将所有子任务碰撞结果作逻辑或运算。

基于层次包围盒的算法设计首先为非刚性物体建立树A，为周围物体建立树B。通过任务树，进行遍历和判交。

4 结论

对非刚性物体进行碰撞检测及处理是计算机图形仿真领域中一项非常复杂而耗时的工作，而在应用中对其实时性的碰撞检测算法成为非刚性物体碰撞检测的关键，也是当今学术领域正在不断探索和研究的一项技术，需要我们在应用中不断总结并改进算法。

[1]Xavier Provot，Collision and self-collision handling in cloth model dedicated to design garment[J].Eurographics Workshop on Animation and Simulation，September 1997.

[2]石教英.虚拟现实基础及使用算法[M].北京：科学出版社，2002：216-253.

[3]高成英，刘宁，罗笑南.虚拟穿衣中织物模拟的建立和碰撞检测的处理[J].计算机应用，2002，22(5)：34-37.

[4]赵伟，谭瑞璞，李文辉.基于混合包围体的OpenMP并行化碰撞检测算法 软件学报Journal of Software，Vol.19，Supplement，December 2008：190-201.

[5]赵伟，何艳爽，王晓兵.一种基于分治和流水线技术的并行碰撞检测算法[J].长春工业大学学报：自然科版，2007，28(3)：241-246.