電腦輔助六種幾何形狀之三階段干涉偵測

Computer-Aided Hierarchy Three Levels Interference Detection of six geometric objects

陳德穎(De-Ying Chen)

指導教授 ： 黃以文

國立中正大學/工學院/機械工程學系/碩士(2014年)

摘要

本研究的主要目的是建立一套可適用於多方面干涉偵測的電腦模擬方法以及提供使用者易操作之介面。本文中使用一般設計上常見的幾何形狀，包含有長方體、三角柱、三角錐、球體、圓柱和通孔圓柱等六種幾何物件。
幾何形狀的干涉偵測過程分為三個步驟，首先利用均勻網格進行空間劃分，僅對空間中存在於相同網格內的物件組合進行測試。接著利用邊界球包覆所有物件，經過粗略計算後邊界球間互相接觸的物件配對才進行最後的細估步驟。最後細估計算分為分離軸測試及與通孔相關測試，先以分離軸定理判斷所有物件配對的干涉情況，再用通孔相關測試方法進行通孔圓柱與幾何物件的干涉判斷。
經過空間劃分和粗估的步驟快速剔除測試配對，使最後階段的測試次數降低，藉此三階段的分層偵測方法，增加程式整體的模擬效率。本程式是使用Visual Basic 6.0，套用OpenGL 函式庫撰寫。

關鍵字

三階段式 ； 分離軸定理 ； 干涉偵測 ； 通孔圓柱

並列摘要

The purpose of this research is to establish a wide-ranging interference detection of computer simulation method and provide a user-friendly interface. There are six kinds of geometric objects which are commonly used on design, including cuboid, triangular prism, triangular pyramid, sphere, cylinder and holey cylinder, in this research.

The interference detection process of geometric objects is divided into three levels. First, it will be tested that pairs of objects are in the same grid after the space was partitioned with uniform grid. Next, envelope all objects with bounding spheres. Only pairs of objects that bounding sphere is collided each other through rough estimation will proceed the final level-exact estimation. Finally, the exactly estimating process is divided into the separating axis theorem and the test about holey cylinder. The first stage of the final level is to determine the interference case between all of pairs of objects with separating axis theorem, and then the next stage is that execute the test about holey cylinder to determine the interference between holey cylinder and other geometric objects.

Some testing pairs are excluded by spatial partitioning and rough estimation quickly.-Through spatial partitioning and rough estimation, they decrease the number of final level test. The efficient of system is improved by the interference detection method of three hierarchical levels. This program is encoded with Visual Basic 6.0 programming language and using OpenGL library.

並列關鍵字

Hierarchy Three Levels ； Separating Axis Theorem ； Interference Detection ； Holey Cylinder

參考文獻

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

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

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

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

【7】 J. Ritter, “An Efficient Bounding Sphere,” In Graphics Gems, A. Glassner, Ed. Academic Press,301-303,1990