[發明專利]一種基于包圍盒樹法的并行碰撞檢測方法在審
| 申請號： | 201410836384.0 | 申請日： | 2014-12-23 |
| 公開（公告）號： | CN104867177A | 公開（公告）日： | 2015-08-26 |
| 發明（設計）人： | 熊玉梅 | 申請（專利權）人： | 上海電機學院 |
| 主分類號： | G06T17/00 | 分類號： | G06T17/00 |
| 代理公司： | 上海思微知識產權代理事務所(普通合伙) 31237 | 代理人： | 鄭瑋 |
| 地址： | 200240 *** | 國省代碼： | 上海;31 |
| 權利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關鍵詞： | 一種 基于 包圍 盒樹法 并行 碰撞 檢測 方法 | ||
1.一種基于包圍盒樹法的并行碰撞檢測方法，其特征在于，包括如下步驟：
步驟(S1)：提供兩個待檢測是否發生碰撞的物體；
步驟(S2)：建立每個所述物體整體的包圍盒，所述包圍盒作為所述物體的包圍盒樹的根節點；
步驟(S3)：利用與局部坐標軸垂直的平面將所述包圍盒劃分成兩個子包圍盒，即左包圍盒和右包圍盒，以形成根節點的兩個子節點，即左子節點和右子節點；
步驟(S4)：對上述步驟得到的所述兩個子節點分別遞歸地執行所述包圍盒的分割過程，以得到最終的包圍盒樹，并且給定最大樹深度和葉子節點所包含的幾何元素的個數；
步驟(S5)：將上述步驟得到的兩個物體的所述包圍盒樹的當前節點兩兩之間進行檢測，判斷是否發生碰撞，若發生碰撞，執行步驟(S6)，否則執行步驟(S7)；
步驟(S6)：若所述當前結點為葉子結點，記下該結點，返回，并檢測是否發生碰撞；若所述當前結點不是葉子結點，則取所述當前結點的所有子結點作為所述包圍盒樹的當前結點，遞歸執行步驟(S5)；
步驟(S7)：若所述當前結點無未檢測的兄弟結點，表明未發生碰撞，記下所述當前結點后，返回；若仍有未檢測的兄弟結點，表明發生碰撞，則依次將下所述兄弟結點作為所述包圍盒樹的當前結點；遞歸執行步驟(S5)。
2.根據權利要求1所述的基于包圍盒樹法的并行碰撞檢測方法，其特征在于，所述兩個待測物體為可以劃分成多個四面體，所述四面體之間具有相關性。
3.根據權利要求1所述的基于包圍盒樹法的并行碰撞檢測方法，其特征在于，所述步驟(S6)中檢測是否發生碰撞的檢測方法為空間分解法。
4.根據權利要求2所述的基于包圍盒樹法的并行碰撞檢測方法，其特征在于，所述空間分解法為八叉樹算法或者k-d樹算法或者BSP樹算法。
5.根據權利要求1所述的基于包圍盒樹法的并行碰撞檢測方法，其特征在于，所述包圍盒為AABB包圍盒或者方向包圍盒或者固定方向凸包圍盒或者包圍球。
6.根據權利要求1所述的基于包圍盒樹法的并行碰撞檢測方法，其特征在于，設計所述步驟(S4)的出口為遞歸深度超過了所述給定的最大樹深度。
7.根據權利要求1所述的基于包圍盒樹法的并行碰撞檢測方法，其特征在于，設計所述步驟(S4)的出口為所述子節點所包含的基本幾何元素個數少于所述給定的葉子節點所包含幾何元素個數的最小值。
8.根據權利要求1所述的基于包圍盒樹法的并行碰撞檢測方法，其特征在于，設計所述步驟(S4)的出口為所述左、右子節點至少有一個包含的幾何元素個數與其父節點所包含幾何元素個數相差在10以下。
9.根據權利要求1所述的基于包圍盒樹法的并行碰撞檢測方法，其特征在于，所述包圍盒樹的每一個節點包含兩個子對象，分別為多面體子對象和包圍盒子對象。
該專利技術資料僅供研究查看技術是否侵權等信息，商用須獲得專利權人授權。該專利全部權利屬于上海電機學院，未經上海電機學院許可，擅自商用是侵權行為。如果您想購買此專利、獲得商業授權和技術合作，請聯系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201410836384.0/1.html，轉載請聲明來源鉆瓜專利網。
