臺灣博碩士論文加值系統

本研究的主旨即是建立一套適用於多方面可偵測干涉的電腦模擬技法以及提供使用者易於操作之工具。本文中以一般在任何物體上常見的或在圖型設計上常用的幾何形狀，有圓柱、四角錐、球與長方體四種物件作為測試的對象。
而幾何模型間的干涉偵測分為三個步驟，初步利用均勻網格進行空間劃分以減少空間中物件之兩兩相測所產生的計算消耗，接著以邊界球包覆物件作為粗略的估計物件之間的距離。透過計算邊界球之間已互相接觸後，再進一步以分離軸定理執行細部的計算。利用三階段式的計算方法可以執行快速的剔除測試，因為只有當物件之間是近距離時，才有必要進一步計算物件是否發生干涉。
本文將以座標轉換矩陣進行幾何形狀的運動模擬。最後，本程式以Visual Basic 6.0，套用OpenGL函式庫撰寫。

The purpose of this research is to establish wide range computer simulation techniques to detect interference through a user-friendly computer aided tools. This study uses geometrical object includes: cylinder, pyramid, sphere, and cuboids which commonly use in graphics design as test objects.

The interference detection between geometrical models is divided into three steps. First, we use uniform grid to create spatial partitioning to reduce the computation consumption between objects. Next we use bounding sphere to rough compute objects distances. After the objects contact with each other, at last we use Separating Axis Theorem to perform detail computation. Using this three-step computation method we can reduce unnecessary computation. We just need calculate object with near distance, whether if it has interference with each other.

This study use coordinate transformation matrix to simulate motion of geometrical objects. Finally, we use Visual Basic 6.0 programming language combine with OpenGL to create the simulation.

目 錄
ABSTRACT I
表目錄 X
第一章 緒論 1
1.1前言 1
1.2研究動機與目的 1
1.3文獻回顧 2
1.3.1空間劃分的方法（Spatial Partitioning Method） 2
1.3.2干涉偵測演算法（Interference Detection Algorithm） 5
1.4 論文架構 10
第二章 模擬物件的方法 11
2.1座標轉換矩陣（COORDINATE TRANSFORMATION MATRIX） 11
2.1.1 平移矩陣（Translation Matrix） 11
2.1.2 旋轉矩陣（Rotation Matrix） 13
第三章 干涉判斷的公式推導 15
3.1粗估 16
3.1.1圓柱的邊界球 17
3.1.2四角錐的邊界球 17
3.1.3球的邊界球 18
3.1.4長方體的邊界球 19
3.1.5各物件的粗估 20
3.2細估 23
3.2.1長方體與長方體的測試 26
3.2.2長方體與四角錐的測試 28
3.2.3四角錐與四角錐的測試 30
3.2.4球與長方體的測試 32
3.2.5球與四角錐的測試 35
3.2.6球與圓柱的測試 36
3.2.7圓柱與長方體的測試 38
3.2.8圓柱與四角錐的測試 42
3.2.9圓柱與圓柱的測試 43
3.2.10分離軸定理的運算流程 48
3.3空間劃分（SPATIAL PARTITIONING） 50
3.3.1均勻網格（Uniform Grids） 50
第四章 程式設計與執行結果 53
4.1程式功能簡介 54
4.2程式執行畫面 55
第五章 結論與建議 61
5.1結果與貢獻 61
5.2建議 62

圖目錄
圖1-1 均勻網格之示意圖（大寫1~4為物件）【3】 3
圖1-2 八元樹之父節點下的8個子節點【5】 3
圖1-3 (A)2D空間分解過程圖；(B)K-D樹的布局結果 4
圖1-4 (A)將空間劃分為6個子空間；(B)BSP樹之結構圖【9】 5
圖1-5 物體KA與KB間之最短距離D14【12】 6
圖1-6 方向性包覆盒【13】 6
圖1-7 軸L為分離軸【13】 6
圖1-8 平面上物體A與B之分離狀態 7
圖1-9 以球體組合近似物體的外型【15】 7
圖1-10 管件縮成一條線、元件向外膨脹管件的半徑長示意圖【16】 8
圖1-11 3D空間中的AABB與AABB干涉 8
圖2-1 二維平移轉換矩陣示意圖 12
圖2-2 三維平移轉換矩陣示意圖 13
圖2-3 二維旋轉轉換矩陣示意圖 14
圖2-4三維旋轉轉換矩陣示意圖(從左圖RXΘ、RYΒ、RZΓ) 14
圖3-1測試對象示意圖 16
圖3-2圓柱之邊界球 17
圖3-3四角錐之邊界球 18
圖3-4球之邊界球 19
圖3-5 長方體之邊界球 19
圖3-6長方體與圓柱的粗估 20
圖3-7長方體與四角錐的粗估 20
圖3-8長方體與球的粗估 21
圖3-9圓柱與四角錐的粗估 21
圖3-10圓柱與球的粗估 21
圖3-11四角錐與球的粗估 22
圖3-12長方體與長方體的粗估 22
圖3-13圓柱與圓柱的粗估 22
圖3-14四角錐與四角錐的粗估 23
圖3-15球與球的粗估 23
圖3-16 兩物件頂點投影到分離軸L上處於分離狀態 24
圖3-17 物件A與B頂點投影到分離軸上的示意圖 26
圖3-18長方體A、B的頂點及面法向量 28
圖3-19長方體與四角錐的頂點及面法向量 30
圖3-20四角錐與四角錐的頂點及面法向量 31
圖3-21 球體與長方體測試邊的分離軸 33
圖3-22 球體與長方體測試頂點的分離軸 34
圖3-23 球體與四角錐測試邊的分離軸 36
圖3-24 球體與四角錐測試頂點的分離軸 36
圖3-25 球體與圓柱測試邊的分離軸 38
圖3-26球體與圓柱底部邊緣的分離軸 38
圖3-27 圓柱與長方體測試面的分離軸 40
圖3-28 圓柱與長方體測試邊的分離軸 41
圖3-29 圓柱與四角錐的測試 42
圖3-30圓柱與圓柱之干涉的六種情況 43
圖3-31圓柱間之柱體與邊緣的分離軸 44
圖3-32邊緣-柱體的分離軸 44
圖3-33邊緣與邊緣的非最近距離點 45
圖3-34兩相異平面分別通過兩個圓柱的端面 48
圖3-35通過兩個交點的切線向量 及 48
圖3-36 分離軸定理運算流程 49
圖3-37 2D網格 50
圖3-38劃分結果 52
圖4-1程式流程圖 53
圖4-2程式主視窗 54
圖4-3 8個件物的邊界球 55
圖4-4均勻網格對空間劃分示意圖 55
圖4-5 物件組合測試之結果 56
圖4-6空間中100個任意位置的物件 57
圖4-7均勻網格對空間劃分示意圖 57
圖4-8空間中64個物件分別堆積在四個區塊 58
圖4-9執行結果 59
圖4-10機械手臂範例圖 59
圖4-11編號組 60
圖4-12編號組的物件 60

表目錄
表3-1 兩個多面體之六種不同的干涉情況 24
表3-2 長方體與長方體的分離軸 27
表3-3 長方體與四角錐的分離軸 29
表3-4四角錐與四角錐的分離軸 31
表3-5 球體與長方體的分離軸 34
表3-6 球體與四角錐的分離軸 35
表3-7 球體與圓柱的分離軸 37
表3-8圓柱與長方體的分離軸 41
表3-9圓柱與四角錐的分離軸 42
表3-10 圓柱與圓柱的分離軸 47
表3-11 欄X中的物體 51
表3-12 列Y中的物體 51
表4-1 功能簡介 54
表4-2 範例一 56
表4-3 範例二 58

【1】J. C. Latombe, “Robot Motion Planning,” Kluwer Academic Publishers, Boston, 1991.

【2】D. H. Eberly, “3D Game Engine Desing A Practical Approach to Real-Time Computer Graphics,”Morgan Kaufmann Publishers, USA, 2001.

【3】WM. Randolph Franklin,“Adaptive Grids For Geometric Operations,” Computer-Aided Design, Vol. 21, No. 17, pp. 410-420, 1989.

【4】H. Samet, “Applications Of Spatial Data Structures,” Computer Graphics, Image Processing, and GIS, Addison-Wesley, 1990.

【5】H. Samet, “Spatial Data Structures,” Addison Wesley ACM Press, MA, pp. 361-385, 1995.

【6】D. Meagher, “Geometric Modeling Using Octree Encoding,” Computer Graphics and Image Processing, pp. 129-147, 1982.

【7】A. W. Moore, “An Introductory Tutorial On KD-Trees,” PhD. Thesis, Technical Report, No. 209, 1991.

【8】J. L. Bentley, “Multidimensional Binary Search Trees Used For Associative Searching,” Communications of the ACM, Vol. 18, No. 9, pp. 509-517, 1975.

【9】W. C. Thibault, “Set Operations on Polyhedra Using Binary Space Partitioning Trees,” Computer Graphics, Atlanta, Vol. 21, No. 4, pp. 135-162, 1987.

【10】J. D. Cohen, M. C. Lin, D. Manocha and M. K. Ponamgi, “I-COOLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments,” Symposium on Interactive 3D Graphics, Monterey CA USA, pp. 189-196, 1995.

【11】A. Guttman, “R-Trees: A Dynamic Index Structure For Spatial Searching,” Proceedings of ACM SIGMOD, Boston, MA, pp. 47-57, 1984.

【12】E. G. Gilbert, D. W. Johnson, S. S. Keerthi, “A Fast Procedure for Computing the Distance Between Complex Objects in Three-Dimensional Space,” IEEE Journal of Robotics and Automation, Vol. 4, No. 2, pp. 193-203, 1988.

【13】S. Gottschalk, M. C. Lin and D. Manocha, “OBBTree : A Hierarchical Structure for Rapid Interference Detection,” Department of Computer Science, University of North Carolina Chapel Hill, pp. 171-180, 1996.

【14】B. Mirtich, “V-Clip: Fast and Robust Polyhedral Collision Detection,” Mitsubishi Electric Research Laboratories(MERL), Inc, 1997.

【15】O. Sullivan, C. Dingliana, “Real-Time Collision Detection and Response Using Sphere-Trees,” Image Synthesis Group, Trinity College Dublin, 1999.

【16】張加欣， “電腦輔助彎管機的運動模擬與碰撞偵測分析”，碩士論文，國立中正大學機械工程研究所，嘉義，2003.

【17】M. Eisemann, T. Grosch, S. Mueller and M. Magnor, “Fast Ray / Axis-Aligned Bounding Box Overlap Tests using Ray Slopes,” Computer Graphics Lab, TU Braunschweig, 2008.

【18】林俊敏， “動作射擊遊戲的進階碰撞偵測演算法研究”，碩士論文，私立中華大學資訊工程研究所，新竹，2001.

【19】周武宏， “實體曲面的碰撞偵測”，碩士論文，國立中興大學機械工程研究所，台中，2001.

【20】周振邦， “電腦輔助彎管設計與干涉偵測之研究”，碩士論文，國立中正大學機械工程研究所，嘉義，2004.

【21】M. Dickerson, C. A. Duncan and M. T. Goodrich, “K-D Trees Are Better When Cut On The Longest Side,” Springer-Verlag Berlin Heidelberg, pp. 179-190, 2000.

【22】J. H. Youn, and K. Wohn, “Realtime Collision Detection For virtual Reality Applications,” IEEE virtual Reality Annual International Symposuim, pp. 415-421, 1993.

【23】M. C. Lin, D. Manocha, and M. K. Ponamgi, “Fast Algorithm for Penetration and Contact Determination Between Non-Convex Polyhedral Models,” Proc. Of ICRA, pp. 2707-2712, 1995.

【24】A. Garcia-Alonso, N. Serrano, and J. Flaquer, “Solving the Collision Detection Problem,” IEEE Computer Graphics and Applications, Vol. 14, No. 3, pp. 36-43, 1994.

【25】K. S. Klimaszewski and T. W. Sederberg, “Faster Ray Tracing Using Adaptive Grids,” IEEE Computer Graphics and Applications, Vol. 17, No. 1, pp. 42-51, 1997.

【26】黃弘欽，“五軸虛擬工具機系統之技術研究”，碩士論文，國立中正大學機械工程研究所，嘉義，2007.

【27】洪榮星，“六軸CNC加工機之運動學與碰撞分析及模擬”，碩士論文，國立中正大學機械工程研究所，嘉義，2006.

【28】劉原呈， “三軸 CGT 工具機之碰撞偵測”，碩士論文，國立中正大學機械工程研究所，嘉義，2005.

【29】麥焜燦， “電腦繪圖的數學基礎及應用”，全華科技圖書股份有限公司，1996.

【30】徐芳真， “利用影像對應技術在手術模擬中進行立體物件之碰撞檢測”，碩士論文，國立成功大學工業設計研究所，台南，2005.