基于FDH包围盒的布料碰撞检测

摘  要： 在布料仿真中，碰撞检测与响应十分复杂，很难同时具备真实感和实时性。针对此问题，采用质点弹簧模型进行建模，基于FDH包围盒提出一种快速的检测基本几何元素间碰撞的方法。通过分析点的位置向量与三角平面的夹角，利用向量内积的性质来判断点与三角形的位置关系，同时进行了相应的碰撞响应处理。实验结果表明，采用该方法进行碰撞检测既保证了模拟的真实性，同时又提高了系统的实时性。
关键词： 布料模拟；质点-弹簧模型；FDH包围盒；碰撞检测；碰撞响应

　随着计算机图形学、虚拟现实和计算机动画等技术的兴起和普遍应用，用高质量的计算机动画对极易变形的柔性物体进行真实感仿真成为当前研究的热点课题[1]。在布料动态模拟过程中，碰撞是一个不容回避的问题，如果不能及时地进行碰撞检测并作出相应的响应处理，就会出现物体之间相互穿透和重叠等不真实现象[2]。碰撞检测是影响布料模拟速度的重要因素，碰撞问题解决得好坏直接影响到布料仿真的实时性和精确性。
　空间中几何模型间的碰撞检测算法一般可以分为空间分解法和层次包围盒法两大类[3]。后者的应用比较广泛且种类很多，它的基本思想是用体积略大但形状特性简单的包围盒来近似代替几何模型，并通过构造树状层次结构逐渐逼近对象的几何特性。若两个几何模型的包围盒不相交，可认为两物体之间没有发生碰撞；否则，需要对两物体进行精确的检验。这样通过包围盒间的相交测试快速排除了不相交的基本几何元素，从而减少了相交测试的次数。较典型的有沿坐标轴的包围盒AABB（Axis Aligned Bounding Box）和球包围盒Spheres，这两类包围盒的相交测试十分简单，但紧密性相对较差。方向包围盒OBB（Oriented Bounding Box）是近些年应用比较广泛的包围盒，它的最大特点是其方向的任意性，这使得它可根据被包围对象的特点尽可能紧密地包围对象，但同时造成相交测试变得复杂。固定方向凸包FDH（Fixed Direction Hull）[4]是一种特殊的凸包，它既继承了凸包紧密性好的优点，同时也可以看做AABB的扩展，具有其简单性的特点。鉴于其紧密性和简单性优点，本文采用FDH包围盒方法进一步优化了布料碰撞检测的过程。
　本文首先建立布料的质点-弹簧分析模型，并基于FDH包围盒的碰撞检测原理引入向量，优化了基本几何元素间的碰撞检测。实验结果表明，该方法进一步提高了布料与模型的碰撞检测效率，而且大大增强了布料仿真过程的实时性和真实性。
1 布料模型的建立
　自1986年WEIL J[5]采用余弦曲线及其几何变换对悬垂布料进行模拟，大量学者研究了布料建模的方法。目前应用较为广泛的是由PROVOT X[6]提出的质点-弹簧模型，他把布料划分为矩形网格，网格交点称为质点。为了模拟布料拉伸压缩、沿平面方向剪切和平面外方向弯曲，分别设置了结构弹簧、剪切弹簧和弯曲弹簧，质点之间用这3种弹簧相连，如图1所示。

　一个复杂的几何模型是由上万个基本几何元素构成的，若采用原始的方法对两个几何模型中的所有基本几何元素进行两两相交测试，时间复杂度将高达O（n2）[6]，所以本文通过构造几何模型的包围盒树的层次结构来逐渐逼近几何对象。设几何模型的FDH包围盒为父节点，采用自上而下的方法构造包围盒树。
　一棵FDH二叉树的构造过程如下：首先，确定分裂轴，在方向集合D中选择使包围盒沿此轴线方向最长的一个向量作为分裂轴；然后，确定分裂平面，计算集合中所有基本几何元素的中心在分裂轴上的投影中值，此值作为分裂轴上分裂点划分父节点，这样父节点一分为二；接下来，分别以这两个节点为基，继续分裂直到最小的节点单元为几何模型的基本几何元素。
3 改进的FDH树碰撞检测算法
　进行碰撞检测，首先分别为布料和其周围几何对象的三角化模型建立相对应的FDH包围盒二叉树，然后对两棵二叉树进行遍历判交，这样可先排除对象间一定不相交的部分，从而只对包围盒相交的部分进行基本几何元素间的精确检测，并对发生碰撞的部分进行碰撞响应处理。本文采用FDH包围盒，依据上述思想设计了基于FDH树的碰撞检测算法。对于两棵FDH二叉树A和B，若两棵树的根节点包围盒不相交，那么可以判断两棵树不相交；若存在树A的根节点与树B的内部节点的FDH包围盒不相交，则停止向下遍历；若一直遍历到树B的叶子节点，那么继续用该叶子节点遍历树A；如果遍历到树A的叶子节点，那么近一步对基本几何元素进行检测。算法描述如下：
TraverseTree（A，B）
if（root（A）∩root（B）= 椎）
   return树A与树B不相交
 else if（leaf（A）and leaf（B））
   对基本几何元素进行精确求交
 else if（leaf（A）and NotLeaf（B））
   for each child Cb
   TraverseTree（Cb，A）
else
   for each child Ca
   TraverseTree（Ca，B）
end if
3.1 包围盒间的相交检测
　使用包围盒进行碰撞检测，目的是尽早排除所有不可能相交的基本几何元素对。包围盒间的相交测试速度直接影响碰撞检测的速度。本文首先利用FDH在运动方向上的值排除一部分肯定不发生碰撞的包围盒，对于可能发生碰撞的再利用投影判交的方法作进一步检测。
　以平行于XoZ面放置的布料与桌面碰撞为例，当布料下落时最先发生碰撞的一定是布料（0，-1，0）方向和桌面（0，1，0）方向上的包围盒。因此可以选取布料包围盒（0，-1，0）方向上的FDH值yc与桌面包围盒（0，1，0）方向上的FDH值yd，若yc>yd，则布料包围盒与桌面包围盒一定不发生碰撞。若yc≤yd，则观察两个包围盒的投影区间的相交情况：如果两向量集合在某个方向上的投影区间不相交，则两包围盒必不相交；若在所有方向上的投影区间都相交，那么两包围盒相交，但并不说明布料与桌面一定发生碰撞，还要对基本几何元素作进一步检测。采用这种方法可以在进行投影判交之前先排除一部分不可能相交的包围盒，省略很多不必要的投影比较，当几何模型的点比较多时明显地提高了检测效率。
3.2 基本几何元素的碰撞检测
　通过FDH包围盒间的相交测试之后，排除了肯定不会发生碰撞的区域，但对于包围盒发生碰撞的区域，尚不能确定包围盒内的基本几何元素之间是否发生碰撞[10]。此时有必要进行基本几何元素间的碰撞检测。本文利用质点-弹簧模型模拟布料运动并以三角网格作为布料的基本几何元素，同时对场景中几何模型也进行了三角化分割，这样基本几何元素间碰撞转化为三角形间求交问题，此类问题可归结为点-三角形碰撞检测问题。
　现有的点-三角形碰撞检测方法是通过求解一个三元一次方程组或求解多个一元一次方程的方法来确定基本几何元素之间的距离[11]，从而判断两者是否发生碰撞，计算比较复杂。本文提出一种新的点-三角形碰撞检测方法，通过分析点的位置向量与三角平面的夹角来判断点与三角形的位置关系，从而得出是否发生碰撞。
如图3和图4所示，假设 驻ABC、 驻DEF分别为两模型的基本几何元素，其中点B是最可能发生碰撞的点，为碰撞粒子，则问题转化为检测点B与 驻DEF的碰撞情况。图3为在第k个时间步长 驻ABC和 驻DEF的相对位置，其中点N为点B在面DEF上的投影。若到了k+1步，点B运动到B′位置，那么判断点B与 驻DEF是否相交的算法描述如下：

　由此，可根据不同情况获得碰撞后质点的速度，进而获得该时间步长后质点的新位置，有效处理碰撞，逼真地模拟布料运动。
5 实验结果及分析
　本文在奔腾IV 2.8 GHz，1 GB内存的PC上，以OpenGL图形库为基础，使用VC++作为开发环境进行仿真。首先定义布料和碰撞对象的初始位置，然后布料在各种内力和外力的共同作用下向下运动，实现了具有不同质点个数的布料与桌子和球体的碰撞检测和碰撞响应实验。
　图5是布料与桌子的碰撞检测，可见图中布料自然下垂，在方形桌子的棱角处十分自然，并产生了真实的褶皱效果。图6、图7为各种状态下的布料与不同数量的球体的碰撞检测，模拟效果自然逼真。

　本文基于质点，弹簧模型建立FDH包围盒，实现了布料与几何模型的碰撞检测及响应。在进行基本几何元素间的碰撞检时，利用向量内积的性质判断点-三角形是否发生碰撞，从而省去了对点到平面距离等繁复的运算的求解。实验结果表明，采用本文方法模拟布料与几何模型的碰撞，在产生自然逼真模拟效果的前提下，使得系统实时性有较大的提高。
参考文献
[1] 沈才樑，李伟，余立丰，等.基于局部自适应混合积分的动态布料模拟快速方法[J].计算机应用研究，2012，29（7）：2740-2742.
[2] 陈昕，徐乃平.真实感布仿真中布与刚体的碰撞检测及修正[J].软件学报，2001，12（12）：1874-1880.
[3] 汤亮，曹卫星，朱艳.作物可视化中的碰撞检测及相应研究[J].计算机科学，2011，38（10）：263-284.
[4] 魏迎敏，王涌，吴泉源，等.碰撞检测中的固定方向凸包包围盒的研究[J].软件学报，2001，12（7）：1056-1062.
[5] WEIL J. The synthesis of cloth objects[J]. ACM SIGGRAPH Computer Graphics， 1986，20（4）：49-54.
[6] PROVOT X. Deformation constraints in a mass-spring model to describe rigid cloth behavior[J]. Proceedings of Graphics Interface，1995：147-154.
[7] LING L， DAMODARAN M， GAY K L. A model for animating cloth motion in air flow[C].  TENCON′94. IEEE Region 10′s Ninth Annual  International Conference， 1994：118-122.
[8] 金一庆，陈越，王冬梅.数值方法[M].北京：机械工业出版社，2007.
[9] 汪嘉业，王文平，屠长河，等.计算机几何及应用[M].北京：科学出版社，2011.
[10] 赵慧青.虚拟服装设计中的布料仿真与碰撞检测算法研究[D].成都：成都理工大学，2008.
[11] 罗谦.基于三角网格的变形体碰撞检测算法研究[D].杭州：浙江大学，2006.
[12] BRIDSOU R， FEDKIW R， ANDERSON J. Robust treatment of collisions，contact and friction for cloth animation[A]. Computer Graphics Proceedings， Annual Conference Series， ACM SIGGRAPH， SanAntonio，Texas，2002：594-603.
[13] 顾尔丹，许端清，王靖斌，等.结合一种面-面碰撞   检测算法的服装动态模拟[J].计算机辅助设计与图形学学报，2002，14（11）：1036-1040.