基於放射視角以及動態分群的封閉可變形物體連續自我碰撞偵測

Abstract

在這篇論文中，我們使用RVBC放射視角的概念，並且改善自我碰撞culling的效率。 從RVBC的實驗數據可以發現，物體群集的數量影響自我碰撞偵測的效率。群集的數量越多， inter cluster check花費的時間越多，但是intra-cluster check花費的時間越少。 在RVBC中，經由前處理決定群集的數量，模擬過程中不再改變群集的數量。當物體嚴重變形的時候， 一開始的群集可能會出現較多 negatively oriented 或是 uncertain 三角形。因此，我們提出一個動態分群的方法， 動態地調整群集的數量讓inter-cluster check和intra-cluster check花費的時間能達到平衡， 幫助改善culling的效率。

我們也發現有些物體在分成群集之後，出現較多的negatively oriented or uncertain三角形。因此， 我們提出一個新的分群方法幫助改善分群。 除此之外，RVBC在模擬的過程使用骨架的資訊更新observer primitives的位置。 為了降低我們的方法的限制，在模擬的過程 我們藉由observer primitives的barycentric coordinates更新observer primitives的位置。

In this thesis, we use the concept of Radial view based culling (RVBC) to perform self-collision culling and improve the RVBC method. Experimental results of RVBC show the more the number of clusters is, the lower the cost of inter-cluster check is. However, the more the number of clusters is, the higher the cost of intra-cluster check is. RVBC determines the number of clusters at the preprocessing stage and then the number of clusters is fixed. When an object deforms, the cluster distribution may result in more negatively oriented triangles. Thus, we propose a dynamic clustering to dynamically adjust the number of clusters so that the cost of inter-cluster check and intra-cluster check is balanced to improve culling performance.

We also find the result of cluster decomposition in RVBC can be improved. % There are more negatively oriented or uncertain triangles. There are negatively oriented or uncertain triangles should be assigned to the other atomic clusters. Moreover, cluster decomposition in RVBC spends a lot of time. Thus, we propose a new cluster decomposition method to improve clustering. Besides, RVBC uses skeleton motion to update positions of observer primitives at the runtime stage. % In order to reduce the limitation of using our method, We compute barycentric coordinates of observer primitives at the preprocessing stage and use it to update positions of observer primitives at the runtime stage.