一種基于體素八叉樹的碰撞算法研究

朱卓 劉云飛 汪坤 劉森

摘 要：碰撞檢測算法是虛擬仿真系統中的關鍵技術。本文利用OPENGL和CHAI3D庫實現對模型的視覺和觸覺渲染。同時，針對復雜的軟體模型，采用一種多方向體素算法和哈希算法來存儲模型的離散化數據。碰撞算法采用包圍盒和空間分解的混合算法，粗略碰撞利用八叉樹判斷兩個模型是否在同一節點內，精確碰撞是通過基本片元的距離計算來確定是否發生碰撞。仿真結果表明，該算法可以有效實時反饋碰撞點的位姿和反饋力。

關鍵詞：虛擬仿真;體素化;碰撞檢測;八叉樹

中圖分類號：TP391 文獻標識碼：A 文章編號：1003-5168（2019）34-0039-05

A Research about Collision Algorithm Based on Voxel Octree

ZHU Zhuo LIU Yunfei WANG Kun LIU Sen

（The 28th Research Institute of China Electronics Technology Group Corporation，Nanjing Jiangsu 210007）

Abstract： Collision detection algorithm is a key technology in virtual simulation system. In this paper， OPENGL and CHAI3D libraries were used to realize visual and tactile rendering of the model. For complex software models， a multidirectional voxel algorithm and hash algorithm were used to store discrete data of the model. The collision algorithm was divided into bounding box and space decomposition， octree was used to judge whether two model were in the same node as rough collision， and whether collision would happen by the distance calculation of the basic elements. The simulation results shows that， the algorithm can feedback the attitude and force of the collision point in real time.

Keywords： virtual simulation;voxelization;collision detection;octree

1 研究背景

在實時仿真中，模型間的交互類型有移動、觸碰、穿刺、切割、縫合等。其中，碰撞檢測[1]是這些操作的先決條件，只有判斷碰撞與否，才能計算產生的碰撞力并刷新變形效果。因此，精確快速的碰撞響應是虛擬仿真的重要因素。

碰撞方式按照碰撞主體類型可分為剛體間的碰撞和剛體與軟件間碰撞[2]兩種情況。碰撞檢測方法主要有層次包圍盒法[3]和空間分解法[4]。常見的包圍盒算法有AABB包圍盒法、Sphere球包圍盒法、方向包圍盒及K-DOP包圍盒法等。包圍盒算法的原理是根據物體形狀，分別用立方體、圓等多邊體將物體包圍，并自動檢測兩個物體包圍盒的距離，當距離值小于指定閾值時，則認定兩個物體發生碰撞。國內外研究包圍盒方法均有一定歷史，國內最具代表性的是國防科大[5]提出的基于固定方向的凸包包圍盒方法，該方法能適應軟組織變形過程中拓撲結構的變化。……