[發明專利]一種基于三維模型體素化的內部球改進構造方法

無效

• 申請號: 201310138285.0
• 申請日: 2013-04-19
• 公開（公告）號: CN103236079A
• 公開（公告）日: 2013-08-07
• 發明（設計）人: 李重;王君良;許鴻堯
• 申請（專利權）人: 浙江理工大學
• 主分類號: G06T17/00
• 分類號: G06T17/00;G06T17/30
• 代理公司: 浙江英普律師事務所 33238
• 代理人: 陳小良

技術領域

本發明涉及到一種智能仿真技術，具體是指一種基于三維模型體素化的內部球改進構造方法。

背景技術

碰撞檢測技術是視景仿真中的重要研究內容，也是虛擬環境產生沉浸感的重要手段，在計算機視覺、虛擬現實、機器人等領域有著廣泛應用。通過碰撞檢測可以確定兩個或者多個物體彼此之間有沒有發生接觸或穿透。三維模型近似逼近為碰撞檢測提供了可行性，能夠快速而精確地檢測出物體間是否發生碰撞并進行相應處理，因而在碰撞檢測中發揮著重要應用，越來越多地受到人們的關注。

三維模型逼近中，有多種幾何圖元用于構建模型的“包圍盒層次結構”(BVH)作預處理。按包圍盒的不同又分為包圍球法(Sphere)、軸向包圍盒法(AABB)、方向包圍盒法(OBB)、離散方向多面體法(k-DOP)、固定方向凸包(FDH)等。目前普遍采用的碰撞檢測是空間二叉劃分BSP（Binary?Space?Partitioning）樹和AABB包圍盒方式。相比計算量和方便性來講還是模型的立方體和球體逼近更方便些。其中，球體之間的碰撞檢測可以說是最簡單的數學模型，由于只有一個自由度，我們只要知道球體的球心和半徑就能進行檢測，但也存在精度不高等問題。為了提高模型包圍球逼近時碰撞檢測的速度和效率，人們又構造了球體樹方法。現行球體逼近方法有很多，核心問題是對模型球體個數和逼近誤差的優化。文獻[8]提出了基于中軸的內部球層次樹結構，用于碰撞檢測，球體數目相對較少但模型逼近誤差相對較大。文獻[9]使用橢球體代替球體，用于物體間碰撞檢測，取得了較好效果，但橢球繪制時需要確定長短軸方向，增加了模型繪制負擔。文獻[10]提出了基于體素化的內部球層次樹數據結構，用于碰撞檢測和穿透量計算，但存在球體數目較多和內部球聚類效果不理想等問題。我們知道，聚類是一種研究數據之間可能存在相互關系的技術，其聚類分析的結果不僅能表明數據之間的內在聯系和本質區別，還能為進一步數據處理與知識發現提供保證。球體樹結構是提高碰撞檢測時效性的一種很好解決方法，而球體聚類不僅為構造這種層次樹結構提供方法，在模型分割中也能得到有意義的分割效果。

本文在文獻[10]基礎上改進了內部球構造方式和層次結構聚類方法，主要貢獻有：基于改進內部球半徑計算減少內部球數目；通過局部細分提高球體連續性；并使用測地距離作為聚類參數，得到較好的聚類效果。

發明內容

本發明針對現有技術中的不足，提出一種在三維模型體素化基礎上，構建模型的內部球逼近，并對內部球聚類得到球體內部球層次結構的方法。

本發明是通過下述技術方案得以實現的：

一種基于三維模型體素化的內部球改進構造方法，其特征在于包括下述步驟：

（1）模型表面體素化

首先計算出模型的AABB包圍盒，然后根據體素單位對包圍盒進行劃分，得到每個大小為L×L×L空間體素列表，分辨率為X/L×Y/L×Z/L，接著使用立方體和三角面求交算法確定這些基本體元作為邊界體素，并將這些體素標記為非空，從而完成3D模型表面的體素化操作；其中，L是體素單位長度，X、Y、Z分別表示三維方向的長度；

其中，AABB包圍盒是指一個其表面法向與坐標軸方向相一致的長方體，用兩個頂點坐標a^max和a^min來表示一個模型的AABB，其中，a^max=(X_max,Y_max,Z_max)，a^min=(X_min,Y_min,Z_min)，以這兩點為對角頂點構成的包圍盒即為模型AABB包圍盒；

其中，立方體和三角面求交：以立方體的中心為原點建立坐標系，基于分離軸定理，對13條軸線進行測試，步驟如下：

(A)計算出檢測的13條軸線，分別為立方體法向3條軸線，三角形面法向1條軸線，立方體三個法向和三角形三條邊叉積構成的9條軸線；

如果上述立方體和三角形面均能被13條軸線分離，則立方體和三角面不相交；反之，只要其中有一條軸線不能將兩者分離，則立方體和三角面相交；

(B)當軸線為立方體法向時，進行三角形面和立方體最小包圍盒的重疊檢測；

(C)當軸線為三角形面法向時，先確定立方體對角線和三角面法線的方向最接近的對角線兩個頂點；

若對角線頂點中小的那一個頂點在三角形面的正面一側或對角線頂點中大的那一個頂點在三角形面的反面一側，則立方體和三角面不相交；反之，兩者相交；