基于泰勒模型的提高连续碰撞检测效率的方法

摘要

本发明提供了一种基于泰勒模型的连续碰撞检测方法，包括：获取空间中需要进行碰撞检测的两个三角形的顶点坐标，以及向量共面性得到碰撞的三次方程，对所述三次方程，在[0,1]区间内使用泰勒模型，得到所述区间的范围值；根据所得到的范围值以及根的存在性原理判断所述三次方程是否在所述[0,1]区间内存在根，如果不存在根，则剔除所述检测对，如果存在根，则将所述检测对纳入连续碰撞检测。本发明其能够有效的过滤掉大部分不会发生碰撞的检测对，过滤率最高达到90％，能够显著提高连续碰撞检测算法的效率。

说明书

技术领域

本发明涉及一种连续碰撞检测方法，尤其涉及一种旨在过滤待计算碰撞对中 不可能发生碰撞的检测对、并以此减少连续碰撞检测的计算量的方法。

背景技术

在基于物理的模拟、机器人动作规划、触觉渲染、虚拟原型的容忍度验证等 应用中，非穿透性约束被广泛应用到可移动或可形变的物体上，用来实现碰撞的 结果。连续碰撞检测是维持非穿透性约束并较好处理碰撞反馈的一项主要技术。

物体之间之所以需要进行碰撞检测，是因为现实世界中同一空间区域内不能 存在两个或者多个不可穿透的物体。随着虚拟现实、计算机动画等技术的兴起， 人们迫切希望可以对真实环境、以及所构想的客观不存在的环境进行模拟，实时 的碰撞检测越发重要。三十年来，许多学者对碰撞检测问题进行了大量研究，并 形成了三类主要的检测方法：静态碰撞检测算法、离散碰撞检测算法和连续碰撞 检测算法(Continuous Collision Detection，CCD)。

其中，连续碰撞检测算法定义为在一个时间参数区间[t₀,t₁]内检测所有物体 和其它物体之间有无碰撞，也是最为自然的

其最大缺陷在于：无法排除相邻接、但是没有发生自碰撞的图元对，即使是 很平坦的没有发生自碰撞的可变形三角形网格也同样无法排除，因此产生很多误 报(False Positives)，剔除率很低，而每一个误报都要执行一个点-面基本测试 或边-边基本测试，即需要进行一次三次方程求解，因此，使得大部分碰撞检测 的时间花费在误报上，导致计算量大，检测速度慢，在一些复杂的模拟环境中不 能保证测试的实时性。

对于可移动或可形变的物体，目前主要有两种过滤技术被用来加速连续碰撞 检测：一种是宽阔空间的动态边界体层次方法(BVHs)；另一种是狭小空间的非 穿透性过滤方法。由于对边界体的过度约束，对于快速移动或者剧烈形变的物体， BVHs方法的过滤效率会显著降低。因此，大量可能发生碰撞的三角形在宽阔空 间没有被过滤出来，并保留到狭窄空间，最终导致几十万甚至几百万的碰撞测试。 由于巨大的计算开销，跟离散的碰撞检测相比，连续碰撞检测的效果也有一定的 限制。

在最近的研究工作中，出现了许多过滤算法，其中效果较好的有DNPF过 滤算法和Exact ccd算法。但是这两个算法的计算时间均较长，过滤算法本身具 有较大的计算花销。

发明内容

针对现有连续碰撞检测效率低、计算量大的问题，本发明提供了一种基于泰 勒(Taylor)模型的连续碰撞检测方法，旨在减少狭窄空间的基本碰撞测试次数， 提高连续碰撞检测算法的效率。

本发明所述的基于泰勒模型的提高连续碰撞检测效率方法，步骤包括：

获取三维空间中由三角形组成的检测对(图元对)的点-面碰撞或边-边碰撞所涉 及的四个顶点坐标；

采用所获得的顶点坐标，根据向量的共面性定理建立共面方程，得到该检测对所 对应的三次方程；

对所述三次方程，在[0,1]区间内使用泰勒模型，得到所述区间的值范围；

根据所得到的范围值以及根的存在性原理判断所述三次方程是否在所述[0,1]区 间内存在根，如果不存在根，则剔除所述检测对，如果存在根，则将所述检测对 纳入连续碰撞检测。

其中，建立共面方程的方法优选为：

假设所述四个顶点在时间间隔t∈[0,1]中以恒定的速度 移动，得到点-面距离或者边-边的距离f(t)的三次方程：

f(t)＝a₃t³+a₂t²+a₁t+a₀  (1)

其中：

$a_0={\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31}·{\overrightarrow{v}}_{41};$

$a_1=({\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31}+{\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31})·{\overrightarrow{v}}_{41}+{\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31}·{\overrightarrow{v}}_{41};$

$a_2={\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31}·{\overrightarrow{v}}_{41}+({\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31}+{\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31})·{\overrightarrow{v}}_{41};$

$a_3={\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31}·{\overrightarrow{v}}_{41}.$

发生碰撞时：f(t)＝0。

其中，泰勒模型优选为t∈[0,1]区间基于时间的(n+1)的函数。优选地，f(t) 在t∈[0,1]区间某一点s的n阶泰勒模型T_f为：

$T_f=P_n\left(t\right)+R_n=\underset{i=0}{\overset{n}{\Sigma }}\frac{f^{\left(i\right)}\left(s\right)}{i!}{(t-s)}^i+[r_0,r_1]$

其中，P_n(t)为f(t)的一个近似多项式，R_n为余项。

在本发明的一种优选实施例中，所述泰勒模型可以是包括一阶、二阶、三阶 泰勒模型中的任意一种或几种，并优选为至少包括二阶、三阶泰勒模型中的一种 或几种。

其中，t∈[0,1]区间的一阶泰勒模型优选为：

f([0,1])＝a₃×[0,1]³+a₂×[0,1]²+a₁×[0,1]+a₀

因此，通过一阶泰勒模型得到的f(t)在t∈[0,1]区间的范围值为：

$d_{\mathrm{TM}1}^{\min }=\underset{i=1}{\overset{3}{\Sigma }}\min (a_i,0)+a_0$

$d_{\mathrm{TM}1}^{\min }=\underset{i=1}{\overset{3}{\Sigma }}\max (a_i,0)+a_0$

为最小值，为最大值。

其中，t∈[0,1]区间的二阶泰勒模型优选为：

P₂+R₂＝a₂t²+a₁t+a₀+[r₀,r₁]

其中，P₂是一个近似二次多项式，R₂是一个余项，令公式(2)中S＝0， R₂为at³的闭包，并且在t∈[0,1]区间内是单调的，则：

如果则通过二阶泰勒模型得到的f(t)在[0,1]区间内的极 值为：

$d_{\mathrm{TM}2}^{\min }=\min (P_2\left(t_c\right),P_2\left(0\right),P_2\left(1\right))+\min (0,a_3)$

$d_{\mathrm{TM}2}^{\min }=\max (P_2\left(t_c\right),P_2\left(0\right),P_2\left(1\right))+\max (0,a_3)$

为最小值，为最大值。

如果那么P₂的值介于区间边界的值P(0)和P(1)之间。

其中，t∈[0,1]区间的三阶泰勒模型优选为：

f(t)＝a₃t³+a₂t²+a₁t+a₀

对该三阶泰勒模型的函数求导后得到3a₃t²+2a₂t+a₁＝0，计算得到根t₁和t₂，其中，t_i(i＝1,2)∈[0,1]，则该三阶泰勒模型得到的f(t)在[0,1]区间内的 极值为：

$d_{\mathrm{TM}3}^{\min }=\min (f\left(t_1\right),f\left(t_2\right),f\left(0\right),f\left(1\right))$

$d_{\mathrm{TM}3}^{\min }=\max (f\left(t_1\right),f\left(t_2\right),f\left(0\right),f\left(1\right))$

其中，为最小值，为最大值。

本发明内容中，统称为最小值统称为最大值

本发明上述内容中，根存在性定量为：在区间[0,1]内，如果d^min>0， d^max<0，那么函数在此区间没有实根。

本发明提出了一种基于泰勒模型的过滤算法，它能够快速并低开销的过滤伪 碰撞对，最终减少狭窄空间基本碰撞检测次数，显著提高连续碰撞检测算法的效 率。

附图说明

图1为两个三角形碰撞检测对示意图(A为点-面碰撞、B为边-边碰撞)；

图2为本发明基于泰勒模型的提高连续碰撞检测效率的方法流程示意图；

图3为本发明实施例中运用一阶、二阶、三阶泰勒模型分别得到的值区间示 意图。

具体实施方式

参照图1和图2，两个三角形组成的碰撞检测对，包括6个点-面碰撞(A) 和9个边-边碰撞(B)，每一个点-面碰撞或者边-边碰撞均涉及到四个顶点，设 定四个顶点顶点移动速度为

点-面碰撞时点-面的距离或者边-边碰撞时的边-边距离f(t)可以表示为：

$f\left(t\right)=[{\overrightarrow{x}}_2\left(t\right)-{\overrightarrow{x}}_1\left(t\right)]\times [{\overrightarrow{x}}_3\left(t\right)-{\overrightarrow{x}}_1\left(t\right)]·[{\overrightarrow{x}}_4\left(t\right)-{\overrightarrow{x}}_1\left(t\right)]---(1-1)$

从而得到三次函数

f(t)＝a₃t³+a₂t²+a₁t+a₀   (1-2)

$a_3={\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31}·{\overrightarrow{v}}_{41}$

$a_2={\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31}·{\overrightarrow{v}}_{41}+({\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31}+{\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31})·{\overrightarrow{v}}_{41}$

$a_1=({\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31}+{\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31})·{\overrightarrow{v}}_{41}+{\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31}·{\overrightarrow{v}}_{41}$

$a_0={\overrightarrow{v}}_{21}\times {\overrightarrow{v}}_{31}·{\overrightarrow{v}}_{41}$

该三次代数式等于0就是一个碰撞发生的必要条件。根据这个条件我们可以 得到如下方程：

f(t)＝0   (1-3)

基于泰勒模型获取碰撞方程的值域

[0,1]区间的泰勒模型：

f(t)为在[0,1]区间基于时间的(n+1)次函数。那么f(t)在[0,1]中的某一点s的 n阶泰勒模型T_f可以表示为：

$T_f=P_n\left(t\right)+R_n=\underset{i=0}{\overset{n}{\Sigma }}\frac{f^{\left(i\right)}\left(s\right)}{i!}{(t-s)}^i+[r_0,r_1]---(2-1)$

其中，P_n(t)是f(t)的一个近似多项式。

三阶泰勒模型：

三次多项式(1-2)的三阶泰勒模型就是这个三次多项式本身。所以获取函 数的值范围可以等价于寻找区间里的极值点。通过对公示2求导，得到：

3a₃t²+2a₂t+a₁＝0，

根t_i(i＝1,2)∈[0,1],那么我们可以得到区间[0,1]的极值

$d_{\mathrm{TM}3}^{\min }=\min (f\left(t_1\right),f\left(t_2\right),f\left(0\right),f\left(1\right))$

$d_{\mathrm{TM}3}^{\min }=\max (f\left(t_1\right),f\left(t_2\right),f\left(0\right),f\left(1\right))$

二阶泰勒模型：

三次多项式的二阶泰勒模型如下：

P₂+R₂＝a₂t²+a₁t+a₀+[r₀,r₁]     (2-2)

P₂是一个二次多项式，R₂是一个余项。令公示5中的S＝0，并且R₂是a₃t³ 的闭包。R₂在给定的区间[0,1]中是单调的，所以容易得到R₂的值区间；通过代 数的分析可以得到P₂的准确值区间。因此，我们能得到如下结果：

如果那么通过二阶泰勒模型得到的f(t)在[0,1]的极值：

$d_{\mathrm{TM}2}^{\min }=\min (P_2\left(t_c\right),P_2\left(0\right),P_2\left(1\right))+\min (0,a_3)$

$d_{\mathrm{TM}2}^{\min }=\max (P_2\left(t_c\right),P_2\left(0\right),P_2\left(1\right))+\max (0,a_3)$

如果那么P₂的值介于区间边界的值P(0)和P(1)之间。

一阶泰勒模型：

对于三次多项式的一阶泰勒模型，可以直接将变量的区间[0,1]通过简单的数 学计算得到包含原多项式准确值区间的更大的区间：

f([0,1])＝a₃×[0,1]³+a₂×[0,1]²+a₁×[0,1]+a₀  (2-3)

显然可以得到[0,1]范围内的极值：

$d_{\mathrm{TM}1}^{\min }=\underset{i=1}{\overset{3}{\Sigma }}\min (a_i,0)+a_0$

$d_{\mathrm{TM}1}^{\min }=\underset{i=1}{\overset{3}{\Sigma }}\max (a_i,0)+a_0$

通过代数区间的计算可以快速的得到三阶多项式的值区间，但是这样得到的 区间会比前面三阶和二阶泰勒模型得到的结果更不精确。即我们会有如下的区间 关系：

$[d_{\mathrm{TM}3}^{\min },d_{\mathrm{TM}3}^{\max }]\subseteq [d_{\mathrm{TM}2}^{\min },d_{\mathrm{TM}2}^{\max }]\subseteq [d_{\mathrm{TM}{1}^{`}}^{\min },d_{\mathrm{TM}1}^{\max }]$

其中，分别是三阶、二阶、一阶 泰勒模型得到的值区间。

根存在性定理：

对于函数f(t)∈[d^min,d^max]，在区间[0,1],如果d^min>0，d^max<0， 那么函数在此区间没有实根。

公式(1-3)所表示的三次方程在t∈[0,1]的最小根就是碰撞发生的时间。 对于的根，则不用考虑。如果在t∈[0,1]没有根则表示这两个三角形在 这个时间间隔里不会发生碰撞。

根据泰勒模型得到的方程的值范围，和根的存在性定理，可以判断该方程是 否存在[0,1]区间内的根。然后将没有根的三次方程过滤，不必进行这一方程对 应检测对的碰撞检测。

下面，以图1中边和边碰撞测试为例，将这 四个点的坐标进行运算，得到三个向量，令f(t)等于三个向 量的混合积，则可以得到函数：

f(t)＝0.2566t³+0.4388t²-0.4446t+0.2215

用公式(2-1)分别表达出f(t)在[0,1]区间的三阶、二阶、一阶泰勒模型。

对于三阶泰勒模型，通过对三次方程本身求导，通过数值分析，可以得到在 区间[0,1]上的函数极值

$d_{\mathrm{TM}3}^{\min }=0.1299,d_{\mathrm{TM}3}^{\max }=0.4723$

对于二阶泰勒模型，通过对于P₂项进行数值分析得到P₂的值区间，由于余 项R₂在区间[0,1]单调增加，可以得到f(t)在[0,1]区间的极值

$d_{\mathrm{TM}2}^{\min }=0.1089,d_{\mathrm{TM}2}^{\max }=0.4781$

对于一阶泰勒模型，将函数转化为公式(2-3)的形式，通过在[0,1]区间的 分析，可以得到f(t)在[0,1]区间的极值

$d_{\mathrm{TM}1}^{\min }=0.2231,d_{\mathrm{TM}1}^{\max }=0.9169$

三种泰勒模型所得值区间如图3所示(方框所圈定数值区域)，其中A为三 阶泰勒模型值区间，B为二阶泰勒模型值区间，C为一阶泰勒模型值区间。

表1给出了这三种泰勒模型所获得的值区间以及所花费的计算时间。本实验 在PC机上Windows7操作系统下进行,其硬件配置是3.30GHz Intel Core(TM) i5-4590 CPU、4GB RAM。

表1

泰勒模型 值区间 一次计算所用时间(10^-6秒) 三阶泰勒模型 [+0.1299,+0.4723] 0.1348 二阶泰勒模型 [+0.1089,+0.4781] 0.05919 一阶泰勒模型 [-0.2231,+0.9169] 0.03205

通过表1结果可以看出，一阶泰勒模型计算时间最短，但是该实施例中所得 到的值区间无法确定原方程在[0,1]没有实根，所以无法过滤该检测对，需要进 一步的碰撞检测，过滤效率相对较低。

但二阶和三阶泰勒模型所得值区间均为正值，表明原三阶方程在[0,1]区间 上没有实根，所以可以将该三次方程所对应的碰撞检测对过滤，虽然所用时间相 对于一阶泰勒模型更长，但是准确率明显提高，

过滤率统计方法

令不使用泰勒过滤方法时需要进行碰撞检测次数为S0，使用泰勒过滤方法 过滤后需要进行的碰撞检测次数为S1，实验的过滤率可用(S0-S1)/S0计算得 到。我们采用两种方法来统计过滤率。

方法1

随机生成15000对三角形进行实验，三角形坐标均为随机生成，实验的S0 值为225000，使用我们的泰勒过滤方法后，S1为20457，所以过滤率为 (S0-S1)/S0＝(225000-20457)/225000≈90.9％。

方法2

通过读取三维仿真实验(比如龙兔仿真)三维模型文件，我们得到如下结果： S0为9692475，S1为637498。因此使用泰勒过滤方法后，统计得到的过滤率 为(S0-S1)/S0＝(9692475-637498)/9692475≈93.4％。

可见，本发明方法的过滤率可达到90％以上，能够显著提高计算机连续碰 撞的检测效率。

以上对本发明的具体实施例进行了详细描述，但其只是作为范例，本发明并 不限制于以上描述的具体实施例。对于本领域技术人员而言，任何对本发明进行 的等同修改和替代也都在本发明的范畴之中。因此，在不脱离本发明的精神和范 围下所作的均等变换和修改，都应涵盖在本发明的范围内。