首页 理论教育虚拟现实技术助力凸体碰撞检测

虚拟现实技术助力凸体碰撞检测

【摘要】:如果刚体是凸体,或者可通过凸分解表达,则刚体间的碰撞检测可以被更快地执行。首先,当它们不相交时,仿真引擎跟踪凸体间最近点是可行的,而不是必须像非凸情形中要求的一样,计算每个相交区域的最深贯穿点然后用它们作为碰撞点的近似。从ti时刻的最近点信息开始,几何搜索能很快地收敛于ti+1时刻凸体间实际的最近点。这个上界和凸体在ti时刻最近距离一起用来估计碰撞时刻的下界。

如果刚体是凸体,或者可通过凸分解表达,则刚体间的碰撞检测可以被更快地执行。

首先,当它们不相交时,仿真引擎跟踪凸体间最近点是可行的,而不是必须像非凸情形中要求的一样,计算每个相交区域的最深贯穿点然后用它们作为碰撞点的近似。这是因为对于凸体,连续迭代中最近点间距离的变化是单调的。因此,当一个几何搜索算法沿着刚体边界运动试图找到在迭代ti+1中它们之间的最近点时,它能舍弃所有对应当前值增加的搜索方向,这个当前值是在迭代ti中获得的最近距离。从ti时刻的最近点信息开始,几何搜索能很快地收敛于ti+1时刻凸体间实际的最近点。

其次,凸体上任意一点沿着n方向经过的最大距离的上界可以在时步[ti,ti+1]中计算,假设凸体在时步中以恒定平动和转动运动。已知刚体在ti时刻不相交,碰撞检测模块可以计算每个刚体上任意一点沿着它们最近的方向(方向由ti时刻最近点的连线定义)在时步[ti,ti+1]移动的最大距离的上界。这个上界和凸体在ti时刻最近距离一起用来估计碰撞时刻的下界。注意到这个下界是保守的,即,保证对于给定时刻tm,刚体在tm时刻靠得足够近但还不至于碰撞。很明显,执行这个保守时间推进算法收敛到碰撞时间的迭代次数比采用二分法迭代的次数少得多。(www.chuimin.cn)

作为基于特征的算法,Mirtich的维诺裁剪算法是目前已知的最有效的算法。基于特征是指算法以使用待检查碰撞的刚体特征(即面、边和顶点)的几何运算为基础。另外,Gilbert-Johnson-Keerthi(GJK)算法是迄今为止性能最优的单纯型算法。所谓“单纯型算法”是指算法仅使用刚体的顶点信息来构建一系列凸包,然后对属于此类凸包的点(即单纯形)子集进行运算。本书仅对GJK算法进行介绍。