非遞迴式多面體接觸偵測之演算法及其在明考夫斯基和之應用

Efficient Algorithms for Non-Iterative Contact Detection of Convex Polyhedra and Application on Minkowski Sum

劉千嘉(Chien-Chia Liu)

指導教授 ： 陳俊杉

國立臺灣大學/工學院/土木工程學研究所/碩士(2010年)

https://doi.org/10.6342/NTU.2010.00421

摘要

本研究提出了非遞迴式的方法來解決多面體之接觸偵測的問題。傳統上，幾何形狀限制多面體接觸偵測的計算，當形狀越複雜，計算所需的時間會大幅地增加。
本研究聚焦在非遞迴式共同平面法(Common plane approach)之多面體接觸偵測的演算法與實作。直接實作的複雜度為 ，其中n 為多面體的邊數。而本研究發展出控制頂點之資料結構(Control vertex data structure)與弧之向前交點尋找與分解演算法(Arc Forward Intersection Decomposition (AFID))來使複雜度簡化為線性。此外，本研究點出利用Cudall的遞迴式演算法計算的錯誤。
再者，控制頂點與弧之向前交點尋找與分解演算法可利用於明考夫斯基和(Minkowski sum)的計算。而明考夫斯基和被廣泛地用運在電腦輔助設計、機器人、影像處理、空間計畫等。改進明考夫斯基和的計算，對電腦科學會有很大的影響。因此，控制點與弧之向前交點尋找與分解演算法可以使計算多面體之碰撞偵測與明考夫斯基和更有效率。

關鍵字

明考夫斯基和 ； 共同平面法 ； 接觸偵測 ； 高斯映射 ； 多面體 ； 控制頂點

並列摘要

The non-iterative method proposed in this research solves the contact detection problem of polyhedral blocks analytically and efficiently. The traditional contact detection of polyhedral blocks is limited to geometrical shapes. As the shapes become more complex, the computing time increases dramatically.
This research focuses on the algorithms and the implementation of polyhedral contact detection based on a non-iterative method of common plane approach. The complexity of naïve implementation is O(n^2), which n is the number of edges of the polyhedron. This research develops a control vertex data structure and the Arc Forward Intersection Decomposition (AFID) algorithm for reducing the complexity to linear order. In addition, the errors while calculating the gap in using the Cundall’s iterative scheme are shown.
Moreover, the control vertex and the AFID algorithm can apply on Minkowski sum, a well know mathematic operation. The Minkowski sum is used in many application domains, such as computer-aided design, robotics, spatial planning, mathematical morphology, and image processing. There is a great impact for computer science that improving computation of Minkowski sum. Thus, the control vertex and the AFID algorithm enable computing both contact detection for convex polyhedral and Minkowski sum efficiently.

並列關鍵字

Contact detection ； Control vertex ； Minkowski sum ； Common plane ； Gaussian map ； Slope diagram ； Convex polyhedra ； Computational geometry

參考文獻

[1] Cundall P. A., "Formulation of a three dimensional distinct element model-Part I: a scheme to detect and represent contacts in a system composed of many polyhedral blocks," Interational Journal of Rock Mechanics and Mining Science and Geomechanics Abstract, no. 25, pp. 107-116, 1988.

[2] Chang SW, Chen CS, "A non-iterative derivation of the common plane for contact detection of polyhedral blocks," International Journal For Numerical Methods in Engineering, no. 74, pp. 734-753, 2008.

[4] Zeghaln M, El Shamy U, "A continuum-discrete hydromechanical analysis of granular deposit liquefaction," IJNME, vol. 28, no. 14, pp. 1361-83, 2004.

[5] Kaul A, Rossignac J, "Solid-interpolating deformations: Construction and animation of PIPs.," Comput Graph, no. 16(1), pp. 107-15, 1992.

[8] Ghosh P, "A unified computational framework for Minkowski operations," Comput Graph, no. 17, pp. 357-78, 1993.