以數學規劃研究多面體離散元素在三維空間之接觸分析與運動模擬

Contact and Motion Analysis of Polyhedral Discrete Elements Using Linear and Quadratic Programming

周靖江(Ching-Chiang Chou)

指導教授 ： 陳俊杉

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

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

摘要

多面體間的接觸判斷是使用離散元素法在處理多面體運動模擬時的關鍵。目前既有的演算法都將其視作為幾何問題並試圖以向量計算求解之，然而在向量計算的過程中經常存在著釵h處理上瓶頸。

本研究提出之三維多面體離散元素接觸判斷與運動模擬演算法主要參考Cundall之共用平面之概念定義接觸方向等接觸參數，並將原本的幾何求解問題轉化為線性規劃與二次規劃之數值規劃問題，再使用最佳化技巧求解之。其中，我們以線性規劃求解兩多面體是否有接觸發生，接著以二次規劃求解兩多面體之共用平面，藉此決定接觸點以及接觸方向，最後再以線性規劃求解正向接觸深度。由於二次規劃僅能求解兩個無接觸多面體間的共用平面，對此我們也提出收縮多面體的概念加以克服。經由實際測試結果顯示以數值規劃求解可有效避免以往向量演算法之缺點，且在其處理的多面體愈形複雜時，仍可維持相同的演算效率。

關鍵字

多面體 ； 線性規劃 ； 離散元素法 ； 二次規劃 ； 共用平面

並列摘要

The technique to detect and represent the contacts between three-dimentional polyhedra is important for the Discrete Element Method. It was generally acknowledged as a geometric problem by the previous methods and solved by vector operations in space. However, these operations usually suffer from many difficulties when dealing with the discontinuous features of the geometric description. A new algorithm is proposed in this thesis. It adopted Cundall's common-plane concept for contact analysis. Furthermore, this study transforms the geometric problem into linear and quadratic programming problems which can be solved by optimization methods. Firstly, the linear programming method is used to determine whether there is contact between two polyhedra. Secondly, the common-plane between two polyhedra can be determined by using the quadratic programming method. Finally, the linear programming method is used again to determine the normal contact depth. In addition, we introduce the concept of contract-polyhedron to overcome the difficulty when two polyhedra are already in contact. Numerical results indicate that the difficulties of geometric operations can be successfully eliminated by using the proposed methods. Besides, its performance scales well with the complexity of the polyhedra.

並列關鍵字

Discrete Element Method ； Quadratic Programming ； Polyhedron ； Linear Programming ； Common Plane

參考文獻

[2] Cundall, P.A., and Strack, O.D., "A Discrete Numerical Model for Granular Assemblies, Geotechnique, Vol. 29, No. 1, pp. 47-65 (1979).

[3] 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," Int. J. Rock Mech. Min. Sci. & Geomech. Abstr., Vol. 25, No. 3, pp. 107-116 (1988).

[4] Hart, R., Cundall, P.A., and Lemos, J., "Formulation of a Threedimensional Distinct Element Model Part II. Mechanical Calculations for Motion and Interaction of a System Composed of Many Polyhedral Blocks," Int. J. Rock Mech. Min. Sci. & Geomech. Abstr., Vol. 25, No. 3, pp. 117-125 (1988).

[10] Yang, C.T., and Hsieh, S.H., "An Object-Oriented Framework for Versatile Discrete Objects Simulations Using Design Patterns,"

Computational Mechanics (accepted 2004).