近年由於製造技術快速發展，為了提高產能並減少人力，會加入自動化夾具、產品輸送設備及上下料設備。這些設備的機構可能具有高自由度，且相互的運動關係也較複雜，在操作上可能無法直覺的判斷。所以電腦輔助製造(CAM)軟體，提供了在製造生產前的模擬，可避免實際進行加工時產生的意外問題，但無法達到整個加工單元的模擬。而本研究建立了一套系統，具備碰撞偵測功能，提供了加工單元或多機台在加工前的模擬。
本文提出一套程式架構，此程式架構是基於函式庫中的類別。利用樹狀機構鏈的搜尋，建立各自獨立的機構鏈。再將機構鏈簡化，獲得實際需要判斷碰撞的機構鏈。最後利用遞迴關係，將所有機構鏈中需要檢測碰撞的桿件配對。當進行模擬時可由此取出所有的「碰撞對」進行碰撞檢查。此架構提供使用者加入新的物件時，即可快速產生碰撞對，進行加工時的碰撞偵測。本文提出減少碰撞對之方法，可降低程式執行的計算量，提高執行效率。在本文中所使用的函式庫中已具備可建立虛擬加工單元、各物件間的干涉檢查及切削工中的實體切削等功能。
本文在模擬加工的過程中，建立的虛擬物件。包含虛擬機台的部分，還搭配了虛擬控制器。本文以實際加工程式及真實控制器驗證虛擬控制器之加工路徑。最後利用東台精機股份有限公司提供的TMV-510A銑床及SCARA機械手臂等幾何資料導入進行系統整合實作及加工示範。並比較本文提出的資料結構在計算效率上的優勢。

With rapid development of manufacturing techniques recently, the pursuit to increase production and reduce human resources has resulted in the addition of automatic robots, transportation equipment and robotic arm. Mechanisms of that equipment are of high degree of freedoms, and relative motions are much more complex so that it is difficult to be judged by human intuitively. Therefore, computer-aided manufacturing software were usually used to simulate before production, which can avoid accidents while machining real bodies, but can’t simulate the whole machining cell. This research has established a system with function of collision detection. That can providing a simulation of the machining cell or multi-machine before manufacturing.
This thesis proposes a data structure, based on the architecture of the class library. Searching the tree structure, construct the independent chain, and then simplification of the chain, real need to determine the impact in the chain will be obtained. Finally, use of the recursion relations will create mappings of pairs among all rods that need to be examined in the chain during the simulation. This architecture provides the user to add a new object, and can generate the collision pairs quickly. That can detect collision in process simulation. This thesis proposes the method of reducing collision detection pair. While operating programs, it can reduce the calculation time and increase efficiency. Libraries used in this thesis can construct virtual machining cells, detect collision between each object, and simulate real bodies machining.
In this thesis, simulation of the machining process, and the establishment of a number of virtual objects including the virtual machine with a virtual controller have been implemented. This thesis used actual processing program and actual controller to verify the tool path by with controller. Finally, geometrical information of milling machine (TMV-510A) and SCARA robotic arm provided by Tongtai Machine and Tool Company were imported into the developed program to demonstrate machining examples. Advantages of the proposed data structure will be presented and compared to others.

Aliyu, M. D. S., “A Vertex Algorithm for Collision Detection,” European Journal of Operational Research , Vol. 120, pp.174-180, 2000.
Chan, C. K., & Tan, S. T., “Determination of the Minimum Bounding Box of an Arbitrary Solid--an Iterative Approach,” Computers and Structures, Vol. 79, pp. 1433-1449, 2001.
Chou, W.H., “Collision Detection for Curved Solids”, Master Thesis, Institute of Mechanical Engineering, National Chung Hsing University, 2001.
Chou C. P., “Computer-aided Design and Interference Detection of Bending Pipes”, Master Thesis, Institute of Mechanical Engineering, National Chung Cheng University, 2004.
Ding, S., Mannan, M. A., & Poo, A. N., “Oriented Bounding Box and Octree Based Global Interference Detection in 5-axis Machining of Free-Form Surfaces,” Computer-Aided Design, Vol. 36, pp. 1281-1294, 2004.
Hubbard, P. M., “Approximatting Polyhedra with Spheres for Time-Critical Collision Detection,” ACM Transactions on Graphics, Vol. 15, No.3, 1996.
Hsu P. S., “Study on Kinematic Movements for Multi-axis Machine Tool by Virtual Reality”, Master Thesis, Institute of Mechanical Engineering, National Cheng Kung University, 2001.
Hsu W. C., “Study on Cutting Motion of Multi-axis Machine Tool by Virtual Reality＂, Master Thesis, Institute of Mechanical Engineering, National Cheng Kung University, 2002.
Huang H. C., “A Study of the Technology of Five-Axis Virtual Machine Tool System” , Master Thesis, Institute of Mechanical Engineering, National Chung Cheng University, 2007
Hsieh E. P., “An Octree Method for Milling Force Prediction in Five-Axis Virtual Machine Tool”, Master Thesis, Institute of Mechanical Engineering, National Cheng Kung University, 2013.
Iqbal, M. & Hashmi, M. S. J., “Application of virtual reality for the training of engineering personnel”, Proceedings of the International Conference on Advances in Materials and Processing Technologies, AMPT’99 and 16th Annual Conference of the Irish Manufacturing Committee, Vol.3, pp.1959-1966, 1999.
Kim H. S., Kim H. O., & Shin S. Y., “Collision Detection Algorithm of a Continuous Type Using Spherical Extreme Vertex Diagrams,” Computers and Mathematics with Applications, Vol. 47, pp. 1363-1378, 2004.
Lin, M., Manocha, D., Cohen, J. & Gottschalk, S., “Collision Detection: Algorithms and Applications,” Proceedings of Algorithms for Robotics Motion and Manipulation, pp. 129-142, 1996.
Liu T. L., “Study on Simulation of Cutting Motion in Multi-axis Machine Tool by Interpolation Algorithm”, Master Thesis, Institute of Mechanical Engineering, National Cheng Kung University, 2003.
Liu, Y. C., “Collision Detection of CGT Machine Tool”, Master Thesis, Institute of Mechanical Engineering, National Chung Cheng University, 2005.
Lee, R. S., & Mei, K. J., "Development of parallel cutting simulation with adaptive octree model in virtual machine tool", pp. 654-658, 2012.
Mei, K. J., “Studies on Virtual Multi-Axis Milling Machine Construction and Postprocessor Program Integration”, Master Thesis, Institute of Mechanical Engineering, National Cheng Kung University, 2009.
Nakayasu, H., Nakagawa, M., Ishikawa, K., E. Nakamachi, Nakamura, Y.& Katayama, T. “Design of die geometry for metal sheet forming in virtual manufacturing”, Int. J. Ind. Eng.: Theory Appl. Prac., Vol.6. pp. 271-281, 1999.
Ong, S. K., Jiang, L. & Nee, A. Y. C. “An Internet-Based Virtual CNC Milling System”, Advanced Manufacturing Technology, pp. 20-30, 2002.
Perez, A. P., & Martinez, B., “A Practical Approach to Collision Detection Between General Objects,” Proceedings of IEEE International Conference on Robotics and Automation, Vol. 1, pp. 779-784, April 1996.
Saha, S. K., “Organizational visions of virtual manufacturing: sociotechnical aspects of adopting technology computer-aided design based manufacturing process”, Proceddings of Engineering and Technology Management, pp. 570-575, 1996.
Shukla, C., M. Vazquez, & Chen, F. F. “Virtual manufacturing：an Overview”,Journal of Future Generation Computer System, Vol. 31, No1-2, pp. 79-82, 1996.
Su, C. J., Lin, F.& Ye, L. “A new collision detection method for CSG-represented objects in virtual manufacturing”, Computers In Industry, Vol. 40, pp. 1-13, 1999.
Yu C. C., “A Study on the Virtual Technology for the Five-Axis CGT Machine Tool System”, Master Thesis, Institute of Mechanical Engineering, National Chung Cheng University, 2006.
Zhang, Yu, Xu, Xun, & Liu, Yongxian, "Numerical control machining simulation: a comprehensive survey", International Journal of Computer Integrated Manufacturing, Vol. 24, No. 7, pp. 593-609, 2011.