複雜環境之影像式碰撞濾除運算

Abstract

我們設計一個可快速且有效率的對複雜場景進行碰撞偵測的演算法，我們將針對影像式的碰撞濾除加以改進並將潛在碰撞集合(potentially colliding set, PCS)分割成數個子集合。在方法中我們延續CULLIDE的演算法[13]，在線性時間將那些屬於完全可見的物體從潛在碰撞集合內移除，並且我們在兩次的繪圖流程都給定一個從遠到近的順序，這將大幅度的降低因物體投影重疊而影響方法的效率；儘管，有些無發生碰撞的物體被其他的物體給遮蓋著，在我們方法中大多情況下仍能有效濾除。另外，在執行能見度分析也同時計算是否存在分割曲面於潛在碰撞集合中，分割曲面可將潛在碰撞集合分割成數個小的集合，可減少配對碰撞偵測的次數。最後，我們利用50~200個由800個三角形構成的圓環測試執行效能，平均所花費的碰撞偵測時間約為0.85~9毫秒，實驗結果，證實我們的方法能有效率地應用於物理模擬或即時系統之中

We present an algorithm for efficient and exact collision detection between complex geometric models in large environments using graphics hardware. The purpose of our algorithm is to improve image-based collision culling and partition the potentially colliding set (PCS) into subsets. Our algorithm eliminates objects which are fully visible in PCS using occlusion query in linear time. It is based on CULLIDE and decides an order of rendering to supply a more efficient culling performance. We can conspicuously reduce the extent of culling to rely on the depth complexity of the scene along the view direction. Despite there are some collision-free objects are occluded by other objects, they may be pruned in our algorithm. Furthermore, our algorithm determines whether separating surfaces exist between the subsets of the PCS. The computation of collision pairs would be beneficial to divide the PCS into multiple sets during the collision culling. Finally, we measured the performance of our algorithm using 50-200 torii with 800 triangles. The average collision detection time is around 1.3-14 milliseconds. In the experiments, our approach had shown to be efficient for collision detection in physics simulation and applied to real-time applications.