基於視角的連續自我碰撞偵測以及在圖形處理器上之加速

Abstract

在這篇論文中，我們提出了一個新的基於視角的方法來對可變形物體進行連續自我碰撞偵測，首先我們會利用一個點或是一條線段等簡單的幾何元件來當作基準，這些基準元件會被放置於可變形物體的內部，在整個物理模擬過程中，我們會確保它們不會穿過該可變形物體，接著，我們會利用這些基準元件來定義可變形物體中所有三角形的方向，根據每一個三角形的方向將整個可變形物體的三角形做分堆，放進不同的視角集合裡，這個過程稱為視角測試。如果所有的三角形都朝向基準元件，則該可變形物體中是沒有自我碰撞存在的，否則，我們將會對某些成對的視角集合做進一步地處理。視角測試的計算量遠小於傳統的方法，使用我們的方法來偵測自我碰撞，整體的效能是比較快的。此外，由於我們的方法適合於平行運算，所以我們進一步地利用圖形處理器來實作我們的方法，進而加速及改進整體的效能，實驗的數據顯示，利用我們的方法來偵測可變形物體的自我碰撞，其效能不管是在CPU上還是GPU上都是令人滿意的。

In this thesis, we propose a novel view-based approach for continuous self-collision detection with deformable triangle meshes. At first, we compute a simple geometric primitive, such as a point or a line segment. The primitive is put inside the deformable object, and we assume that it does not penetrate the object during the simulation. Then, the primitive is employed to determine the orientation of all triangles of the object. The triangles are divided into several view sets according to their orientation each frame, and this procedure is called view test. If all triangles face the primitives, then the object is self-collision free. Otherwise, self-collision is detected for certain pairs of the view sets. The computation of the view-based approach is lower than traditional methods, such as regular patches division and contour tests. Besides, our approach is suitable for parallel computing. We implement the view-based approach on GPUs with CUDA and improve the performance significantly. The experimental results show that the performance of the view-based approach for continuous self-collision detection is satisfied on both CPUs and GPUs.