利用LSS技術改進ODE的碰撞偵測與碰撞時間計算｜國立臺灣科技大學博碩士論文系統

簡易檢索 / 詳目顯示

回結果列表

研究生：	黃宏倫 Hung-Lung Huang
論文名稱：	利用LSS技術改進ODE的碰撞偵測與碰撞時間計算 Improving Collision Detection and Collision Time Calculation of Open Dynamic Engine by Line-Swept Sphere Technique
指導教授：	鄧惟中 Wei-chung Teng
口試委員:	林彥君 Yen-chun Lin 項天瑞 Tien-ruey Hsiang
學位類別：	碩士 Master
系所名稱：	電資學院 - 資訊工程系 Department of Computer Science and Information Engineering
論文出版年：	2010
畢業學年度：	98
語文別：	英文
論文頁數：	64
中文關鍵詞：	碰撞偵測、碰撞時間、物理學模擬引擎
外文關鍵詞：	collision time calculation, Line-Swept Sphere, ODE, Open Dynamic Engine
相關次數：	點閱：134 下載：1
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

碰撞問題是攸關機器人能否正確且安全運作的重要原因之一，在預模擬工作已經蔚為主流的現在，模擬器如何能夠精確的反應機器人在現實世界中碰撞的情況，以及能否提供完整的功能性，是值得研究的。

本研究利用最常見且能提供基本碰撞偵測功能的物理學模擬引擎Open Dynamic Engine為基礎，增加一種具方向性且表示法不複雜的新的模擬方式Line-Swept Sphere來模擬物件以達到更貼近物件原型的效果，並藉由這個新的模擬方式提出了一個新的碰撞偵測方法，針對數種不同形狀的幾何物件，依照物件形狀選擇適合的模擬方式做包覆，並對不同的模擬方式組合採取不同的碰撞偵測策略，以達到更佳的偵測結果。透過實驗，這個方法能改善碰撞偵測結果的準確率，降低需要進行第二階段碰撞偵測的物件數目。

另一方面，我們計算出物件未來的軌跡，並藉由這些資料來預測物件可能在什麼時間點會發生碰撞。碰撞產生的時間點這項資訊可提供給使用者作為調整模擬的參考。透過實驗，我們驗證了這項資訊的正確性，以及用於讓物件避開碰撞的可用性。

Collision problem is one of the most vital issues that determine if robots could operate correctly and safely. Nowadays, pre-simulation has been wildly used in robot motion design and development. Hence, it is worthwhile to study on how to make the simulator responses the collision situation more accurate and offer more complete functionality.
This research is based on Open Dynamic Engine, one of the most famous and popular open source simulator for rigid body physics. To improve the basic collision detection functions equipped in ODE, we add a new simulation method, Line-Swept Sphere, in order to provide bounding volume which is, in some cases, more close to the geometry shape of objects. LSS has the advantages of directional and simple representation. Furthermore, we propose an improved collision detection method based on this work. For geometric objects with different shapes, the bounding volumes with smaller size are chosen to contain them separately. According to the results of experiment, we confirmed that this proposed method improves the accuracy of collision detection result.
Additionally, we developed a module to predict the collision time via calculating future trajectories of the moving objects. A simple experiment is performed to verify correctness of the predicted collision time. This experiment also illustrates a possible application of this prediction.

中文摘要	                                                  I
Abstract	                                                 II
致謝	                                                        III
Table of Contents	                                         IV
List of Figures	                                                 VI
List of Tables	                                               VIII
Chapert 1. Introduction                	                          1
    1.1 Motivation	                                          2
    1.2 Research goals	                                          4
    1.3 Contributions of this thesis	                          5
    1.4 Thesis organization	                                  5
Chapert 2. Preliminaries	                                  6
    2.1 Collision detection technologies	                  6
        2.1.1 Object types	                                  6
        2.1.2 Bounding volume	                                  7
        2.1.3 Swept volume	                                  9
        2.1.4 Posteriori versus priori	                         10
    2.2 Open Dynamic Engine	                                 10
    2.3 Other physical libraries and simulators	                 11
Chapert 3. Proposed Method	                                 15
    3.1 Problem definition	                                 15
    3.2 The collision detection method	                         18
        3.2.1 Representation of AABB and LSS	                 18
        3.2.2 Two axis-aligned bounding boxes	                 22
        3.2.3 Axis-aligned bounding box to line-swept sphere	 23
        3.2.4 Two line-swept spheres	                         25
    3.3 Collision anticipation	                                 28
        3.3.1 Calculate trajectory of objects	                 29
        3.3.2 Conditional collision prediction	                 31
Chapert 4. Experiments	                                         35
    4.1 Experiment platform	                                 35
    4.2 Collision detection method experiment	                 36
        4.2.1 Experiment environment	                         36
        4.2.2 Experiment procedure	                         37
        4.2.3 Experiment result and analysis	                 39
    4.3 Experiment for collision prediction                	 43
        4.3.1 Experiment environment	                         43
        4.3.2 Experiment procedure	                         43
        4.3.3 Experiment results	                         44
Chapert 5. Conclusions	                                         45
    5.1 Conclusions	                                         45
    5.2 Future Work	                                         45
References	                                                 47
Appendix	                                                 50

                                

[1] S. Redon, A. Kheddar, and S. Coquillart, “An Algebraic Solution to the Problem of Collision Detection for Rigid Polyhedral Objects,” in Proceedings of IEEE international Conference on Robotics and Automation, pp. 3733–3738, 2000.
[2] P.Jiménez, F. Thomas, and C. Torras, “3D Collision Detection: A Survey,” Computers and Graphics, vol. 25, no. 2, pp. 269-285, Apr. 2001.
[3] M.C. Lin and S. Gottschalk, “Collision Detection Between Geometric Models: A Survey,” in Proceedings of IMA Conference on Mathematics of Surfaces, vol. 1, pp. 602–608, May. 1998.
[4] S. Kockara, T. Halic, K. Iqbal, C. Bayrak, and R. Rowe, “Collision Detection: A Survey,” in IEEE International Conference on Systems, Man and Cybernetics, pp. 4046–4051, Oct. 2007.
[5] M. Moore and J. Wilhelms, “Collision Detection and Response for Computer Animation,” Computer Graphics, vol. 22, no. 4, pp.289-298, Aug. 1988.
[6] M.C. Lin, “Efficient Collision Detection for Animation and Robotics,” Ph.D. Thesis, Department of Electrical Engineering and Computer Science, University of California, Berkeley, Dec. 1993.
[7] C.Y. Lin, “Development and Evaluation of A Virtual Haptic Environment,” M.S. Thesis, Department of Mechanical and Electro-Mechanical Engineering, University of National Sun Yat-sen, June 2004.
[8] C.C. Kuo, “Visual Effects and Collision Detection for A Virtual Environment,” M.S. Thesis, Department of Computer Science and Information Engineering, University of National Central, June 2006.
[9] K.C Lai and S.C Kang, “Collision Detection Strategies for Virtual Construction Simulation,” Automation in Construction, vol.18, is. 6, pp. 724-736, Oct. 2009.
[10] M. Figueiredo, “Adjustable Approach for Collision Detection in Virtual Prototype Environments,” in Geometric Modeling and Imaging, pp. 44–47, July 2007.
[11] J. Ketchel and P. Larochelle, “Collision Detection of Cylindrical Rigid Bodies for Motion Planning,” in Proceedings of IEEE International Conference on Robotics and Automation, pp. 1530-1535, May 2006.
[12] S. Redon, A. Kheddar, and S. Coquillart, “Fast Continuous Collision Detection between Rigid Bodies,” Computer Graphics Forum, vol. 21, is. 3, pp. 279-288, 2002.
[13] M. Hutter and A. Fuhrmann, “Optimized Continuous Collision Detection for Deformable Triangle Meshes,” in Proceedings of International Conferences on Computer Graphics, Visualization and Computer Vision, vol. 15, no. 1-3, pp. 25–32, 2007.
[14] S. Kim, S. Redon, and Y.J. Kim, “Continuous Collision Detection for Adaptive Simulation of Articulated Bodies,” The Visual Computer, vol. 24, is. 4, pp. 261-269, Mar. 2008.
[15] S. Redon, Y.J. Kim, M.C. Lin, and D. Manocha, “Fast Continuous Collision Detection for Articulated Models,” in Proceedings of ACM Symposium on Solid Modeling and Applications, pp. 145-156, 2004.
[16] K. Okada, M. Inaba, and H. Inoue, “Real-time and Precise Self Collision Detection System for Humanoid Robots,” in Proceedings of IEEE International Conference on Robotics and Automation, pp. 1060–1065, Apr. 2005.
[17] W. Chen, H. Wan, H. Zhang, H. Bao, and Q. Peng, “Interactive Collision Detection for Complex and Deformable Models Using Programmable Graphics Hardware,” in Proceedings of the ACM Symposium on Virtual Reality Software and Technology, pp. 10–15, 2004.
[18] Y.K. Choi, J.W. Chang, W. Wang, M.S. Kim, and G. Elber, “Continuous Collision Detection for Ellipsoids,” IEEE Transactions on Visualization and Computer Graphics, vol. 15, is. 2, pp. 311-325, Mar.-Apr. 2009.
[19] T. Larsson and T. Akenine-Möller, “A dynamic bounding volume hierarchy for generalized collision detection,” Computers and Graphics, vol. 30, is. 3, pp. 450–459, June 2006.
[20] X. Zhang, S. Redon, M. Lee, and Y.J. Kim, “Continuous Collision Detection for Articulated Models using Taylor Models and Temporal Culling,” ACM Transactions on Graphics, vol. 26, is. 3, July 2007.
[21] C. Mendoza and C. O’Sullivan, “An Interruptible Algorithm for Collision Detection between Deformable Objects,” in Proceedings of the 2nd Workshop on Virtual Reality Interactions and Physical Simulations, pp. 73–80, 2005.
[22] A, Foisy and V. Hayward, “A Safe Swept Volume Method for Collision Detection.” The Sixth International Symposium of Robotics Research, Pittsburgh, pp. 61-68, Oct. 1993.
[23] M. Herman, “Fast, Three-dimensional, Collision-free Motion Planning,” in Proceedings of IEEE International Conference on Robotics and Automation, vol.3, pp. 1056-1063, Apr. 1986.
[24] S. Redon, Y.J. Kim, M.C. Lin, D. Manocha, and J. Templeman, “Interactive and Continuous Collision Detection for Avatars in Virtual Environments,” in Proceedings of IEEE Virtual Reality, pp. 117-283, Mar. 2004.
[25] D. Albocher, U. Sarel, Y.K. Choi, G. Elber, and W. Wang, “Efficient Continuous Collision Detection for Bounding Boxes under Rational Motion,” in Proceedings of IEEE International Conference on Robotics and Automation, pp. 3017-3022, May 2006.
[26] B. Kim and J. Rossignac, “Collision Prediction for Polyhedra under Screw Motions,” in Proceedings of ACM Conference on Solid Modeling and Applications, pp. 4–10, 2003.
[27] M. Tang, S. Yoon, and D. Manocha, “Adjacency-based Culling for Continuous Collision Detection,” The Visual Computer, vol. 24, is. 7, pp. 545–553, July 2008.
[28] Y. Awa and K. Kobayashi, “Kinematics Simulation by Using ODE and MATLAB,” SICE Annual Conference, pp. 3090-3094, Sep. 2007.
[29] V. Bečanović, T. Gunther, and A. Bredenfeld, “Modeling of Neuromorphic Vision Sensors in ODE,” in Proceedings of IEEE International Conference on Robotics and Automation, pp. 2859-2864, Apr. 2005.
[30] D. Manocha. I-COLLIDE. [Online]. Available: http://gamma.cs.unc.edu/I-COLLIDE/. 1995-1996.
[31] geom@cs.unc.edu. V-COLLIDE. [Online]. Available: http://gamma.cs.unc.edu/V-COLLIDE/. Sep. 1, 1998.
[32] Gino J.A. van den Bergen. FreeSOLID. [Online]. Available: http://www.win.tue.nl/~gino/solid/. Jan. 19, 2004.
[33] Mitsubishi Electric Research Laboratories. V-Clip Collision Detection Library. [Online]. Available: http://www.merl.com/projects/vclip/. 2010.
[34] P. Terdiman. OPCODE. [Online]. Available: http://www.codercorner.com/Opcode.htm. June 5, 2003.
[35] Project Group 510.D-COLLIDE. [Online]. Available: http://d-collide.ematia.de/index.html. 2007.
[36] AIST, University of Tokyo, and MSTC.OpenHRP. [Online]. Available: http://www.is.aist.go.jp/humanoid/openhrp/English/indexE.html. , 2005.
[37] OpenHRP Team, Humanoid Research Group, Intelligent Systems Research Institute, and AIST. OpenHRP3 Official Site. [Online]. Available: http://www.openrtp.jp/openhrp3/en/index.html. Sep. 14, 2009.
[38] Cyberbotics Ltd. Overview. [Online]. Available: http://www.cyberbotics.com/products/webots/index.html. Nov. 27, 2009.
[39] J.C. Zagal and J. Ruiz-del-Solar, “UCHILSIM: A Dynamically and Visually Realistic Simulator for the RoboCup Four Legged League,” in Proceedings of RoboCup, vol. 3276, pp. 34–45, 2004.
[40] K. Fawaz, R. Merzoukia, and B. Ould-Bouamamaa, “Model Based Real Time Monitoring for Collision Detection of An Industrial Robot,” Mechatronics, vol. 19, is. 5, pp. 695-704, Aug. 2009.

簡易檢索 / 詳目顯示

相關論文