基於電荷分佈的變形物體連續自身碰撞偵測

Continuous Self-Collision Detection for Deformable Objects Based on Charge Distribution

葉喬之

指導教授 ： 黃世強

國立交通大學/資訊學院/多媒體工程研究所/碩士(2012年)

https://doi.org/10.6842/NCTU.2012.00707

摘要

在這篇論文中，我們提出了一個對封閉物體的連續自身碰撞偵測的新方法，
它結合了物體分割和 detector-based 的碰撞偵測。Detector-based 的碰撞偵測是在一個區域中，利用一個區域內部的點來檢查此區域中所有三角形的面向，並以三角形面向的資訊對此區域作自我碰撞偵測的方法。在物體分割部分，我們在前置處理的過程中，利用計算電荷分佈的方法來分析一個物體，電荷的分佈關係能表現出一個物體結構上的強度。一個區域的電荷分佈少，代表它在一個局部區域之中是一個比較凹陷的區塊，我們將它看成是局部結構強度較低的部分，也是物體容易發生形變的部分；反之，一個區域的電荷分佈多，表示是一個局部區域中比較凸的區塊，我們將它看成是局部結構強度較高的部分。我們根據這種物體結構強度的物理特性將物體切割成幾個在模擬過程中較不易發生形變的區域。在模擬的過程中，我們對這些分割好的區域分別作 detector-based 的自我碰撞偵測，區域和區域之間則利用物體間的碰撞偵測。我們利用幾個不同的實驗來對我們的方法和利用 K-means 分割物體的方法以及我們實作的 ICCD 方法做比較。實驗的結果展現出，我們的方法整體效能比 K-means 穩定，而比 ICCD 提升了1.88X ∼ 2.19X。

關鍵字

自我碰撞偵測 ； 電荷分佈

並列摘要

In this thesis, we propose a new method to accelerate self-collision detection with closed objects. Our method includes object decomposition and detector-based collision detection. In detector-based collision detection, it utilizes a point that inside a region to check all triangles¦ orientation of this region. And this is a method that performs self-collision detection based on triangles¦ orientation of this region. On the part of object decomposition,
we analyze the physical property of an object by computing its charge distribution in the preprocessing phase. The charge distribution of an object could present strength of structure of the object. A region with less charge means that the region is concave part at the local area. We regard the region as lower structural strength at the local area, and it is easily deformed region of an object. On the other hand, a region with more charge indicates that the region is convex part at the local area. We regard the region as higher structural strength at the local area. We segment an object into several not easily deformed regions based on structural intensity of the object. In the simulation phase, we perform view-based self-collision detection on these segmented regions and inter-collision detection between each region. We use some different experiments to compare our method with K-means decomposition method and our implementation on ICCD. The experiment results show that our approach is more stable than K-means decomposition method. Compared to ICCD, our method improves self-collision detection by a factor of 1.88X ∼ 2.19X.

並列關鍵字

self collision detection ； charge distribution

參考文獻

[2] R. Bridson, R. Fedkiw, and J. Anderson. Robust treatment of collisions,contact and friction for cloth animation. In ACM Transactions on Graphics(TOG), volume 21, pages 594--603, 2002.

[4] Y.C. Cheng. View-based continuous self-collision detection with graphics hardware. Mater Thesis, National Chiao Tung University, Tiawan, R.O.C, 2011.

[5] S. Curtis, R. Tamstorf, and D. Manocha. Fast collision detection for deformable models using representative-triangles. In Proceedings of the 2008 symposium on Interactive 3D graphics and games, pages 61--69. ACM, 2008.

[6] Aleksey Golovinskiy and Thomas Funkhouser. Randomized cuts for 3D

[8] E. Grinspun and P. Schroder. Normal bounds for subdivision-surface interference detection. In Proceedings in Visualization, pages 333--570, 2001.