[發明專利]一種基于鏈表排序平衡二叉樹的層次包圍盒樹構建方法

在審

• 申請號: 201710717268.0
• 申請日: 2017-08-21
• 公開（公告）號: CN107689078A
• 公開（公告）日: 2018-02-13
• 發明（設計）人: 葉秀芬;江帆;梅新奎;劉文智;王天;趙新華;崔建文;賈同超;宮垠;孫晶
• 申請（專利權）人: 哈爾濱工程大學
• 主分類號: G06T17/00
• 分類號: G06T17/00;G06T19/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明屬于虛擬現實中軟體碰撞檢測技術領域，具體涉及一種基于鏈表排序平衡二叉樹的層次包圍盒樹構建方法。

背景技術

虛擬現實(Virtual Reality，簡稱VR)技術是一門正在被越來越多的人所熟知并且高速發展的技術，其利用計算機硬件、軟件和網絡生成一個三維立體環境，操作人員借助一些穿戴式傳感器設備可以與之交互，對環境中的物體施加操作，同時虛擬環境提供給人視覺、聽覺、觸覺、嗅覺、味覺等感官的模擬，讓人有種身臨其境之感。

包圍盒的主要原理就是使用固定的幾何體將復雜多變的虛擬物體進行封閉包圍，如果要判斷兩個物體是否相交，只要判斷封閉住的這兩個物體的包圍盒是否相交，從而將復雜的三維物體之間的碰撞簡化成規則幾何體之間的碰撞。以上的簡單的包圍盒法只能應用于剛體之間的碰撞檢測，如果要處理軟體器官或者柔軟布料等物體的碰撞檢測，需要考慮軟組織自身圖元之間的碰撞，這就需要使用層次包圍法。

層次包圍盒法的原理是對三維幾何物體進行圖元劃分，比如常用的三角片元，對這些單獨的片元建立一個個的包圍盒，然后根據三角片元的各自的相對位置組織成層次包圍盒樹的形式。當軟體產生形變而發生軟體自身圖元的自碰撞時，通過遍歷包圍盒樹的方式來檢測出發生碰撞的圖元節點。如果要檢測兩個物體之間是否發生了碰撞，需要從根節點出發，判斷出根節點包圍盒是否發生接觸，如果接觸便對兩個根節點的子節點進行檢測，這樣從根節點出發直到被檢測出來的兩個物體的節點都是葉子節點，最后對這兩個葉子節點的包圍盒所包圍的幾何圖元進行精確檢測和位置響應的計算。

虛擬手術系統中不僅包含手術器械這種剛體物體，還具有手術對象如肝臟、胃等軟體組織，所以選擇的層次包圍盒的類型不僅要適用于剛體，還要適用與軟體，由于軟體形變的自碰撞特性，既需要包圍盒與幾何物體有較好的緊密性，又同時需要有較快的更新速度，因此適應性高、時間復雜度低的AABB層次包圍盒方法更適合虛擬手術系統的碰撞檢測方法。

目前常用的構造層次包圍盒樹的方法為霍夫曼法，這種方法的具體實現方式為：

(1)為物體的所有給定的基本元素創建一個AABB包圍盒，作為一個獨立的二叉樹，選擇一個參照物；

(2)遍歷所有二叉樹，計算二叉樹根節點與參照物之間的距離，該距離為二叉樹根節點對應AABB包圍盒中心點與參照物之間的距離，按照距離由小到大進行排序；

(3)選擇距離最小和次小的兩個二叉樹進行合并，生成合并后圖形的包圍盒作為這兩個包圍盒的父節點，形成一顆新的二叉樹；

(4)重復執行步驟(2)至步驟(3)，直到所有二叉樹合并為一個二叉樹為止。

使用霍夫曼編碼構造層次包圍盒樹時，每次選擇距離最近的兩個節點進行合并，可以保證當物體不發生形變時，構造出的層次包圍盒樹結構相同，保證了層次包圍盒樹的穩定性。但是霍夫曼法中4個節點構造出的層次包圍盒樹的樹高為4，即使用霍夫曼樹方式構建出的樹的樹高為O(n)級別，增加了遍歷層次包圍盒樹的耗時。此外，使用霍夫曼編碼方式構建樹時，每一次合并后均需要重新計算距離并按照距離重新排序，因此構造樹也是十分耗時的，實時性大大降低。

對于一棵平衡二叉樹而言，搜索從根結點到葉結點的一條路徑時，花費的總工作量最小，此外，層次包圍盒樹是否平衡，即樹中各結點的大小是否大致相當則直接影響到二叉樹的運算效率，使用霍夫曼編碼的方式構造AABB層次包圍盒樹需要頻繁計算距離和排序，復雜度高、實現難度大。因此，針對上述問題，本發明公開了一種基于鏈表排序平衡二叉樹的層次包圍盒樹構建方法。

發明內容

本發明的目的在于提供一種能夠降低二叉樹高度、解決二叉樹合并過程中重復排序問題、復雜度低且能夠簡化計算的基于鏈表排序平衡二叉樹的層次包圍盒樹構建方法。

本發明的目的是這樣實現的：

本發明公開了一種基于鏈表排序平衡二叉樹的層次包圍盒樹構建方法，具體的實現步驟包括：

(1)將所要建立包圍盒樹的物體按照合理精度劃分成基本幾何圖元，對每一個幾何圖元生成一個AABB層次包圍盒，將每個獨立的包圍盒看做為一棵二叉樹，每個二叉樹只有一個根節點，選擇一個物體或者地點作為參照物；

(2)創建一個鏈表存儲二叉樹：對步驟(1)中所建立所有只有根節點的二叉樹進行遍歷，對鏈表中每個二叉樹對象增加一個屬性值，存儲該二叉樹到參照地點的長度；

(3)根據鏈表中每個二叉樹到參照地點的長度對鏈表進行升序排列；