[發明專利]三維復雜場景基于層次包圍盒碰撞檢測的路徑規劃優化方法

在審

• 申請號: 201611181066.0
• 申請日: 2016-12-20
• 公開（公告）號: CN106780762A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 秦緒佳;程燕飛;鄭紅波
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06T19/00
• 分類號: G06T19/00
• 代理公司: 杭州斯可睿專利事務所有限公司33241
• 代理人: 王利強

技術領域

本發明涉及圖像處理、計算方法、三維場景、數學等領域，尤其是這三維復雜場景基于層次包圍盒碰撞檢測的路徑規劃優化方法。

背景技術

用戶在三維復雜場景中漫游時，常常由于環境的復雜和可視點的范圍限制而不能意識到自己的位置，不能快速辨認出目的地的位置，因此需要路徑規劃技術，通過該技術辨別自己的位置并快速辨認出目的地的位置和路徑。路徑規劃常用的算法是啟發式A*搜索算法，通過計算代價評估值，尋找最小代價評估值而完成路徑規劃。現存在的多數路徑規劃算法存在著規劃效果和規劃時間效率成正比的現象，如通過機器人視點迭代計算路徑開銷，試圖尋找能夠全部替換已有的最短路徑的改進的視點集，但視點路徑開銷迭代計算會計算該視點所有的可能路徑開銷，從而會重復計算已經走過的路徑開銷，增加了算法的計算量和路勁規劃時間。

發明內容

為克服已有的三維場景路徑規劃的規劃效果不佳、規劃效率低的不足，本發明提供了一種有效提高路徑規劃效果和規劃效率的三維復雜場景基于層次包圍盒碰撞檢測的路徑規劃優化方法。

本發明解決其技術問題所采用的技術方案是：

一種三維復雜場景基于層次包圍盒碰撞檢測的路徑規劃優化方法，包括以下步驟：

1)、定義兩列表：待選列表L1和已選列表L2；

2)、依次遍歷L1表，取出當前結點c，放入L2表。表示對當前結點c找未碰撞領域拓展點；

3)、以結點c為中心，進行粗試探，主要包括設置包圍盒的尺寸與分割大小，沿一定方向進行預碰撞檢測和精細碰撞檢測；

4)、判斷粗試探是否成功，若成功則跳轉L1表中的下一個結點，否則對當前結點C進行精搜索，沿設定方向進行預碰撞檢測和精細碰撞檢測，記錄未碰撞區域拓展點N；

5)、對未碰撞區域拓展點N進行A*代價評估，并進行降序排列插入到L1表；

6)、循環遍歷L1表找出代價評估最小值作為當前結點，重復上述步驟直至到達終點。

進一步，所述的待選列表L1和已選列表L2具體為：表L1用于保存已經過評價函數評估，知道代價值的但領域拓展點未進行評估的結點；表L2用于保存表L1中的且已經對領域拓展點進行評估的結點；

進一步，所述步驟(3)由以下步驟組成：

(3.1)以結點c為中心，構造八叉樹包圍盒，將三維場景進行均勻空間分割；

(3.2)粗試探：遍歷八叉樹包圍盒中，結點c四周的六個方向中除去結點c的父結點方向

和父結點反方向后剩下的四個方向，不斷進行預碰撞檢測和精細碰撞檢測；

(3.3)預碰撞檢測：篩選出與結點c在同一最小子單元的對象三角面片，進行標記，得到

預碰撞檢測三角面片序列；

(3.4)精細碰撞檢測：依次遍歷預碰撞檢測三角面片序列，判斷三角面片與當前結點c是

否相交。主要方法為求解三角面片所在平面與當前結點c的相交關系，若相交則求出交點坐標，再判斷該坐標又位于三角面片上，則可以得出該三角面片與當前結點c相交，產生碰撞；

(3.5)循序上述操作，直至找到未碰撞區域拓展點N。

進一步，若經步驟(3)找到未碰撞區域拓展點N，則可直接計算代價估計值；否則需要經歷步驟(4)尋找未碰撞區域拓展點N。

進一步，所述步驟(4)由以下步驟組成：

(4.1)判斷粗試探是否成功，若找到未碰撞區域，則執行下一步并跳轉L1表中的下一個結點；否則對當前結點C進行精搜索；

(4.2)精搜索：遍歷八叉樹包圍盒中，當前結點c的四周的六個方向中除去結點c的父結點方向和后剩下的五個方向，進行預碰撞檢測和精細碰撞檢測。

(4.3)預碰撞檢測：篩選出與結點c在同一最小子單元的對象三角面片，進行標記，得到預碰撞檢測三角面片序列。

(4.4)精細碰撞檢測：依次遍歷預碰撞檢測三角面片序列，判斷三角面片與當前結點c是否相交。主要方法為求解三角面片所在平面與當前結點c的相交關系，若相交則求出交點坐標，再判斷該坐標又位于三角面片上，則可以得出該三角面片與當前結點c相交，產生碰撞；

(4.5)循序上述操作，直至找到未碰撞區域拓展點N。

進一步，所述步驟(5)由以下步驟組成：