陳俊杉臺灣大學：土木工程學研究所周靖江Chou, Ching-ChiangChing-ChiangChou2007-11-252018-07-092007-11-252018-07-092004http://ntur.lib.ntu.edu.tw//handle/246246/50042多面體間的接觸判斷是使用離散元素法在處理多面體運動模擬時的關鍵。目前既有的演算法都將其視作為幾何問題並試圖以向量計算求解之，然而在向量計算的過程中經常存在著釵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.誌謝 ii 摘要 iii Abstract iv 1 導論 1.1 研究動機與背景 . . . . . . . . . . . . . . . . . . . 1 1.2 研究目的 . . . . . . . . . . . . . . . . . . . . . . 3 1.3 論文內容與架構 . . . . . . . . . . . . . . . . . . . 4 2 三維多面體運動模擬之理論與實作 2.1 多面體運動模擬相關理論 . . . . . . . . . . . . . . . 5 2.2 多面體運動模擬演算法 . . . . . . . . . . . . . . . . 11 2.2.1 多面體三維模型之數值定義 . . . . . . . . . . . . . 11 2.2.2 線性規劃與二次規劃演算法 . . . . . . . . . . . . . 12 2.2.3 碰撞偵測 . . . . . . . . . . . . . . . . . . . . . 15 2.2.4 接觸點與接觸方向判定 . . . . . . . . . . . . . . . 15 2.2.5 接觸深度 . . . . . . . . . . . . . . . . . . . . . 18 2.2.6 接觸作用力計算 . . . . . . . . . . . . . . . . . . 20 2.2.7 多面體運動方程式 . . . . . . . . . . . . . . . . . 22 2.3 系統模擬流程 . . . . . . . . . . . . . . . . . . . . 23 2.4 系統實作 . . . . . . . . . . . . . . . . . . . . . . 23 2.4.1 VEDO(VErsatile Discrete Objects) Framework . . . 23 2.4.2 OOQP(Object-Oriented Quadratic Programming) . . . 26 3 案例展示與分析 3.1 模擬案例 . . . . . . . . . . . . . . . . . . . . . . 30 3.1.1 骨牌推倒測試 . . . . . . . . . . . . . . . . . . . 30 3.1.2 篩分析測試 . . . . . . . . . . . . . . . . . . . . 31 3.2 模擬效能分析 . . . . . . . . . . . . . . . . . . . . 34 3.2.1 gprof 效能分析工具 . . . . . . . . . . . . . . . . 36 3.2.2 分析方法 . . . . . . . . . . . . . . . . . . . . . 36 3.2.3 演算法效能分析 . . . . . . . . . . . . . . . . . . 36 3.3 模擬參數分析 . . . . . . . . . . . . . . . . . . . . 39 3.3.1 收縮多面體收縮率 . . . . . . . . . . . . . . . . . 39 3.3.2 Critical Delta T . . . . . . . . . . . . . . . . . 41 3.4 案例展示 . . . . . . . . . . . . . . . . . . . . . . 42 3.4.1 螺旋骨牌 . . . . . . . . . . . . . . . . . . . . . 42 3.4.2 混合顆粒尺寸之篩分析 . . . . . . . . . . . . . . . 42 4 結論與建議 4.1 結論 . . . . . . . . . . . . . . . . . . . . . . . . 46 4.2 建議 . . . . . . . . . . . . . . . . . . . . . . . . 47 參考文獻 . . . . . . . . . . . . . . . . . . . . . . . . 491388220 bytesapplication/pdfen-US多面體線性規劃離散元素法二次規劃共用平面Discrete Element MethodQuadratic ProgrammingPolyhedronLinear ProgrammingCommon Planethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/50042/1/ntu-93-R90521609-1.pdf