[發(fā)明專利]基于泰勒模型的提高連續(xù)碰撞檢測(cè)效率的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201510076544.0
• 申請(qǐng)日: 2015-02-13
• 公開(kāi)（公告）號(hào): CN104615893B
• 公開(kāi)（公告）日: 2017-12-26
• 發(fā)明（設(shè)計(jì)）人: 張新宇;劉要
• 申請(qǐng)（專利權(quán)）人: 華東師范大學(xué)
• 主分類號(hào): G06F19/00
• 分類號(hào): G06F19/00
• 代理公司: 中國(guó)商標(biāo)專利事務(wù)所有限公司11234
• 代理人: 宋義興

技術(shù)領(lǐng)域

本發(fā)明涉及一種連續(xù)碰撞檢測(cè)方法，尤其涉及一種旨在過(guò)濾待計(jì)算碰撞對(duì)中不可能發(fā)生碰撞的檢測(cè)對(duì)、并以此減少連續(xù)碰撞檢測(cè)的計(jì)算量的方法。

背景技術(shù)

在基于物理的模擬、機(jī)器人動(dòng)作規(guī)劃、觸覺(jué)渲染、虛擬原型的容忍度驗(yàn)證等應(yīng)用中，非穿透性約束被廣泛應(yīng)用到可移動(dòng)或可形變的物體上，用來(lái)實(shí)現(xiàn)碰撞的結(jié)果。連續(xù)碰撞檢測(cè)是維持非穿透性約束并較好處理碰撞反饋的一項(xiàng)主要技術(shù)。

物體之間之所以需要進(jìn)行碰撞檢測(cè)，是因?yàn)楝F(xiàn)實(shí)世界中同一空間區(qū)域內(nèi)不能存在兩個(gè)或者多個(gè)不可穿透的物體。隨著虛擬現(xiàn)實(shí)、計(jì)算機(jī)動(dòng)畫(huà)等技術(shù)的興起，人們迫切希望可以對(duì)真實(shí)環(huán)境、以及所構(gòu)想的客觀不存在的環(huán)境進(jìn)行模擬，實(shí)時(shí)的碰撞檢測(cè)越發(fā)重要。三十年來(lái)，許多學(xué)者對(duì)碰撞檢測(cè)問(wèn)題進(jìn)行了大量研究，并形成了三類主要的檢測(cè)方法：靜態(tài)碰撞檢測(cè)算法、離散碰撞檢測(cè)算法和連續(xù)碰撞檢測(cè)算法(Continuous Collision Detection，CCD)。

其中，連續(xù)碰撞檢測(cè)算法定義為在一個(gè)時(shí)間參數(shù)區(qū)間[t₀,t₁]內(nèi)檢測(cè)所有物體和其它物體之間有無(wú)碰撞，也是最為自然的

其最大缺陷在于：無(wú)法排除相鄰接、但是沒(méi)有發(fā)生自碰撞的圖元對(duì)，即使是很平坦的沒(méi)有發(fā)生自碰撞的可變形三角形網(wǎng)格也同樣無(wú)法排除，因此產(chǎn)生很多誤報(bào)(False Positives)，剔除率很低，而每一個(gè)誤報(bào)都要執(zhí)行一個(gè)點(diǎn)-面基本測(cè)試或邊-邊基本測(cè)試，即需要進(jìn)行一次三次方程求解，因此，使得大部分碰撞檢測(cè)的時(shí)間花費(fèi)在誤報(bào)上，導(dǎo)致計(jì)算量大，檢測(cè)速度慢，在一些復(fù)雜的模擬環(huán)境中不能保證測(cè)試的實(shí)時(shí)性。

對(duì)于可移動(dòng)或可形變的物體，目前主要有兩種過(guò)濾技術(shù)被用來(lái)加速連續(xù)碰撞檢測(cè)：一種是寬闊空間的動(dòng)態(tài)邊界體層次方法(BVHs)；另一種是狹小空間的非穿透性過(guò)濾方法。由于對(duì)邊界體的過(guò)度約束，對(duì)于快速移動(dòng)或者劇烈形變的物體，BVHs方法的過(guò)濾效率會(huì)顯著降低。因此，大量可能發(fā)生碰撞的三角形在寬闊空間沒(méi)有被過(guò)濾出來(lái)，并保留到狹窄空間，最終導(dǎo)致幾十萬(wàn)甚至幾百萬(wàn)的碰撞測(cè)試。由于巨大的計(jì)算開(kāi)銷，跟離散的碰撞檢測(cè)相比，連續(xù)碰撞檢測(cè)的效果也有一定的限制。

在最近的研究工作中，出現(xiàn)了許多過(guò)濾算法，其中效果較好的有DNPF過(guò)濾算法和Exact ccd算法。但是這兩個(gè)算法的計(jì)算時(shí)間均較長(zhǎng)，過(guò)濾算法本身具有較大的計(jì)算花銷。

發(fā)明內(nèi)容

針對(duì)現(xiàn)有連續(xù)碰撞檢測(cè)效率低、計(jì)算量大的問(wèn)題，本發(fā)明提供了一種基于泰勒(Taylor)模型的連續(xù)碰撞檢測(cè)方法，旨在減少狹窄空間的基本碰撞測(cè)試次數(shù)，提高連續(xù)碰撞檢測(cè)算法的效率。

本發(fā)明所述的基于泰勒模型的提高連續(xù)碰撞檢測(cè)效率方法，步驟包括：

獲取三維空間中由三角形組成的檢測(cè)對(duì)(圖元對(duì))的點(diǎn)-面碰撞或邊-邊碰撞所涉及的四個(gè)頂點(diǎn)坐標(biāo)；

采用所獲得的頂點(diǎn)坐標(biāo)，根據(jù)向量的共面性定理建立共面方程，得到該檢測(cè)對(duì)所對(duì)應(yīng)的三次方程；

對(duì)所述三次方程，在[0,1]區(qū)間內(nèi)使用泰勒模型，得到所述區(qū)間的值范圍；

根據(jù)所得到的范圍值以及根的存在性原理判斷所述三次方程是否在所述[0,1]區(qū)間內(nèi)存在根，如果不存在根，則剔除所述檢測(cè)對(duì)，如果存在根，則將所述檢測(cè)對(duì)納入連續(xù)碰撞檢測(cè)。

其中，建立共面方程的方法優(yōu)選為：

假設(shè)所述四個(gè)頂點(diǎn)在時(shí)間間隔t∈[0,1]中以恒定的速度移動(dòng)，得到點(diǎn)-面距離或者邊-邊的距離f(t)的三次方程：

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

其中：

發(fā)生碰撞時(shí)：f(t)＝0。

其中，泰勒模型優(yōu)選為t∈[0,1]區(qū)間基于時(shí)間的(n+1)的函數(shù)。優(yōu)選地，f(t)在t∈[0,1]區(qū)間某一點(diǎn)s的n階泰勒模型T_f為：

其中，P_n(t)為f(t)的一個(gè)近似多項(xiàng)式，R_n為余項(xiàng)。

在本發(fā)明的一種優(yōu)選實(shí)施例中，所述泰勒模型可以是包括一階、二階、三階泰勒模型中的任意一種或幾種，并優(yōu)選為至少包括二階、三階泰勒模型中的一種或幾種。

其中，t∈[0,1]區(qū)間的一階泰勒模型優(yōu)選為：