[發明專利]一種基于特征的空間哈希連續碰撞檢測方法

有效

• 申請號: 202110062332.2
• 申請日: 2021-01-18
• 公開（公告）號: CN112802203B
• 公開（公告）日: 2023-02-28
• 發明（設計）人: 劉謙;黃團送
• 申請（專利權）人: 華中科技大學鄂州工業技術研究院;華中科技大學
• 主分類號: G06T17/20
• 分類號: G06T17/20
• 代理公司: 北京眾達德權知識產權代理有限公司 11570
• 代理人: 張曉冬

一種基于特征的空間哈希連續碰撞檢測方法，所述方法包括步驟：獲取待檢測物體的物理網格模型；獲取所述物理網格模型中各特征的鄰接信息；根據所述鄰接信息建立所述物理網格模型的結構約束關系；計算所述物理網格模型中各質點在下一時刻的預測位置；基于各所述特征的空間哈希碰撞檢測所述物理網格模型中實際發生碰撞的特征對。本申請提供的一種基于特征的空間哈希連續碰撞檢測方法相比于基于三角形的空間哈希碰撞檢測方法具有完全排除重復檢測、剔除效率高的優點；相比于其他基于特征的BVH方法，避免了額外的耗時步驟，開發難度更小，易并行，且能無差別的實現碰撞和自碰撞檢測的優點；本發明中的方法碰撞檢測效率高，耗時少，易實現。

技術領域

本發明屬于連續碰撞檢測技術領域，具體涉及一種基于特征的空間哈希連續碰撞檢測方法。

背景技術

基于物理模擬技術對真實世界中的各種物體(包括剛體、軟體及柔性物體)進行物理建模，利用計算機的計算和渲染能力展現出動態逼真的效果已被廣泛應用于電影工業、電子游戲、虛擬現實等諸多領域。碰撞檢測是其中非常重要且耗時的一部分，目前有許多方法用來加速碰撞檢測，大體可分為兩類，一類是基于對象劃分，如層次包圍盒樹(BVH)方法，另一類是基于空間劃分，如空間八叉樹、二叉空間分割樹(BSP)、K-d樹以及空間哈希法等。然而，Bac i u G.等注意到基于圖形基元的碰撞檢測算法存在大量重復檢測的問題，為此他們提出一種隨機標記的方法，將每一個特征(即頂點和邊)唯一的分配到一個鄰接三角形，從而避免碰撞對的重復檢測。Hutter M.等發現除了大量重復檢測外，基于圖形基元的碰撞檢測還存在剔除效率低的問題，進而為頂點和邊引入特征包圍盒提高了剔除效率，使用Bac i u G.的方法避免重復檢測，進一步提升了碰撞檢測的效率和速度。Manocha D.等在以上二者的思想上，提出基于“代表三角形”的層次包圍盒樹方法，同時使用特征包圍盒提高剔除效率。

雖然以上碰撞檢測方法有各自的優點，且能排除重復檢測并解決剔除效率低的問題，但仍存在以下問題：1、

(1)排除重復碰撞檢測需要將每一個特征分配到唯一一個相鄰三角形，這一步需要額外消耗時間，尤其是當網格拓撲結構發生變化時，需要對斷裂部位重新分配；

(2)以上改進算法都是基于層次包圍盒樹，對于布料等柔性物體而言，當發生較大形變時，BVH的剔除效率會大大降低，需要對BVH樹做調整，必要時甚至需要重建，這會嚴重影響碰撞檢測的性能；

(3)BVH樹方法需要對對象間的碰撞檢測和對象的自碰撞檢測使用不同的遍歷方法，此外還需要選用某種優化策略對BVH樹進行調整，增大了算法實現難度。

而相對來說，空間哈希方法能避免以上幾點，同時能很容易的實現并行計算，但盡申請人所知，目前尚未有基于特征的空間哈希連續碰撞檢測方法。

發明內容

鑒于上述問題，本發明提供克服上述問題或者至少部分地解決上述問題的一種基于特征的空間哈希連續碰撞檢測方法。

為解決上述技術問題，本發明提供了一種基于特征的空間哈希連續碰撞檢測方法，所述方法包括步驟：

獲取待檢測物體的物理網格模型；

獲取所述物理網格模型中各特征的鄰接信息；

根據所述鄰接信息建立所述物理網格模型的結構約束關系；

計算所述物理網格模型中各質點在下一時刻的預測位置；

基于各所述特征的空間哈希碰撞檢測所述物理網格模型中實際發生碰撞的特征對。

優選地，所述獲取所述物理網格模型中各特征的鄰接信息包括步驟：

將所述物理網格模型導入物理仿真系統中；

讀取所述物理網格模型的頂點位置信息、三角形信息及法向信息；