本篇論文主要是開發一種新的碰撞偵測演算法，以模擬物體在手術模擬環境中的碰撞狀況。演算法的新構想是結合圓柱座標系統和點陣圖來儲存立體點資料，這和一般使用特殊資料結構儲存點資料的方法不一樣，而所需的點陣圖的數目只有兩張，遠少於多層次影像法所需要的圖像數目。

　　研究中所使用的物體每個有49802 個點和99600 個三角網格，當點資料被對應到點陣圖上的位置時，該點的深度值儲存在被對應到的像素顏色值，當物體被移動後，程式會檢查物體的碰撞情形。

　　本程式使用Visual C++語言，並且不需要複雜的資料結構來儲存點資料。在檢測碰撞情況時，只需要比較點陣圖上像素的顏色數值即可。將來，本研究可應用到偵測手術模擬中凹凸不平之物件的碰撞情形與多個物件之間的碰撞情形，而效能可以最佳化到適用於即時性的模擬環境。

　The approach of this research is to develop an algorithm to detect the three-dimensional objects collision in simulation environment. The new idea of this paper is to use cylindrical coordinates and bitmap images to save the particles of objects. It is different from some conventional methods that use bounding volume hierarchies to save the particles. It is also different from the method of layered depth images. However, the particles of objects are mapped onto two of bitmap images, collision detection bitmap image and global cylindrical coordinates bitmap image. Through examining the color bit of the two images, the program can detect collision between objects.

　I use two objects each of that has 49802 particles, and 99600 triangular meshes to simulate collision detection. The coordinates of particles are changed to the positions of the pixels and the depths of particles are saved in the color bits of bitmap images; and then the program detects collision on the bitmap images when the objects are moved.

　The algorithm is successfully implemented and does not require an involved setup or the implementation of a sophisticated spatial data structure by using Visual C++. I provide a new method for collision detection that takes use of cylindrical coordinates bitmap image and uses comparing instead of counting. The algorithm can be further improved to concave objects in surgical simulation.

[Aga02] P. Agarwal, M. De Berg, J. Gudmunds-Son, M. Hammar , H. Haverkort. Box-trees and r-trees with near-optimal query time. Discrete and Computational Geometry 28, 3 (2002), 291–312. 121
[Bac02] G. Baciu, W. S-K. Wong. Hardware-assisted self-sollision for deformable surfaces. VRST, 2002, 129-136.
[Bac99] G. Baciu, W. Sai-Keung Wong, and H. Sun. RECODE : an image–based collision detection algorithm. The Journal of Visualization and Computer Animation, vol. 10(4), pp. 181–192, 1999.
[Bac98] G. Baciu, W. Sai-Keung Wong, H. Sun. Hardware-assisted virtual collisions. VRST 1998: 145-151.
[Ber97] Van Den Bergen G.. Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools 2, 4 (1997), 1–14. 121, 122
[Bra02] G. Bradshaw, C. O’Sullivan. Sphere-tree construction using medial-axis approximation. Proc. of ACM Symposium on Computer Animation SCA ’02, pp. 33-40, 2002.
[Cor02] F. Cordier, N. Magnenat-Thalmann. Real-time animation of dressed virtual humans. EUROGRAPHICS 2002, Volume 21, Number 3.
[Cug99] Umberto Cugini 1 and Caterina Rizzi 2. 3D design and simulation of men garment. 1999
[Doc04] V. Dochev, T. Vassilev, B. Spanlang. Image-space Based Collision Detection in Cloth Simulation on Walking Humans, Proc. of CompSysTech'2004, Ruse, 17-18 June, 2004.
[Ehm01] S. A. Ehmann, M. C. Lin. Accurate and fast proximity queries between polyhedra using convex surface ecomposition. In Computer Graphics Forum (2001), vol. 20, pp. 500–510. ISSN 1067-7055. 121
[Fan03] Z. Fan, H. Wan, S. Gao. A Fast Collision Detection Algorithm Based On Image Space Using OBB. Proc. of Visualization and Computer Animation Volume 14, Issue 4 , pp. 169 – 181, 2003.
[Gon01] D.X. Gong, B.K. Hinds and J. McCartney. Progress towards effective garment CAD. Journal of ClothingScience and Technology,Vol. 13 No. 1, 2001, pp. 12-22.
[Got96] S. Gottschalk, M. Lin, D. Manocha. OBB-Tree: A hierarchical structure for rapid interference detection. Proc. of SIGGRAPH 96 Conference Proceedings (Aug. 1996), Rushmeier H., (Ed.), ACMSIGGRAPH, Addison Wesley, pp. 171–180. 121
[Gov03] N.Govindaraju, S.Redon, M.Lin, D.Manocha. CULLIDE : Interactive collision detection between complex models in large environments using graphics hardware. Proc. of ACM Graphics Hardware 2003.
[Hei04] B. Heidelberger, M. Teschner, M. Gross. Detection of Collisions and Self-collisions Using Image-space Techniques. Proc. of Computer Graphics, Visualization and Computer Vision WSCG'04, Plzen, Czech Republic, pp. 145-152, February 2-6, 2004.
[Hei03] B. Heidelberger, M. Teschner, M. Gross. Realtime volumetric intersections of deforming objects. Proc. of Vision, Modeling, Visualization VMV’ 03, pp. 461–468, 2003.
[Hof00] K. E. Hoff III, A. Zaferakis, M. C. Lin, and D. Manocha. Fast and simple 2D geometric proximity queries using graphics hardware. Proc. of 2001 ACM Symposium on Interactive 3D Graphics, pp. 145–148, Mar. 2000.
[Hub96] P. M. Hubbard. Approximating polyhedra with spheres for time-critical collision detection. Proc. of ACM Transactions on Graphics 15, 3 (July 1996), 179–210. 121
[Kim02] Y. J. Kim, M. A. Otaduy, M. C. Lin, and D. Manocha. Fast penetration depth computation for physically-based animation. Proc. of 2002 ACM SIGGRAPH Symposium on Computer Animation, pp. 23–31,187, July 2002.
[Klo98] J. T. Klosowski, M. Held, J. S. B. Mitchell, H. Sowrizal, K. Zikan. Efficient collision detection using bounding volume hierarchies of k-DOPs. Proc. of IEEE Transactions on Visualization and Computer Graphics 4, 1 (Jan. 1998), pp. 21–36. 121
[Kno03] D. Knott, D. Pai. CinDeR. Collision and interference detection in real–time using graphics hardware. Proc. of Graphics Interface ’03, to appear, 2003.
[Kri98] S. Krishnan, M. Gopi, M. Lin, D. Manocha, A. Pattekar. Rapid and accurate contact determination between spline models using ShellTrees. Proc. of Computer Graphics Forum 17, 3 (Sept. 1998). 121
[Lar03] T. Larsson, T. Akenine-Moller. Efficient collision detection for models deformed by morphing. The Visual Computer 19, 2(May 2003), 164–174. 122
[Lar01] T. Larsson, T. Akenine-Moller. Collision detection for continuously deforming bodies. In Eurographics (2001), pp. 325–333. short presentation. 121, 122, 123
[Lga02] Takeo Igarashi, John F. Hughes. Clothing Manipulation. Proc. of ACM 1-58113-488-6/02 ,2002
[Lom99] J. Lombardo, M.-P. Cani, F. Neyret. Real-time collision detection for virtual surgery. Proc. of Computer Animation 99’, pp. 33-39, 1999.
[Mys95] K. Myszkowski, O. Okunev, T. Kunii. Fast collision detection between complex solids using rasterizing graphics hardware. The Visual Computer, vol. 11:9, pp. 497-512, 1995.
[Pal95] I. J. Palmer, R. L. Grimsdale. Collision detection for animation using sphere-trees. Proc. of Computer Graphics Forum 14, 2 (June 1995), 105– 116. 121
[Ros92] J. Rossignac, A. Megahed, and B. -O. Schneider. Interactive inspection of solids: Cross-sections and interferences. In Computer Graphics (Proc. of SIGGRAPH 92), volume 26, pp. 353–360, July 1992.
[Shi91] M. Shinya, M. Forgue. Interference detection through rasterization. Journal of Visualization and Computer Animation vol.2, pp.132 –134, 1991.
[Tes04] M. Teschner, S. Kimmerle, B. Heidelberger, G. Zachmann, L. Raghupathi, A. Fuhrmann, M.-P. Cani, F. Faure, N. Magnenat-Thalmann, W. Strasser, P.Volino. Collision Detection for Deformable Objects. Proc. of Eurographics EG'04, State of the Art Report, Grenoble, France, pp. 119-139, August 30 - September 3, 2004.
[Unb98] M. Unbescheiden and A. Trembilski. Cloud simulation in virtual environments. Proc. of IEEE Virtual Reality Annual International symposium (VRAIS), Atlanta,1998
[Vas00] T. Vassilev, B. Spanlang. Efficient Cloth Model for Dressing Animated Virtual People. Proc. of Learning to Behave Workshop, Enschede the Netherlands, pp. 89-100, October 2000.
[Vas01] T. Vassilev, B. Spanlang, Y. Chrysanthou. Fast cloth animation on walking avatars. Proc. of Eurographics ’01, pp. 260-267, 2001.
[Zac03] G. Zachmann, E. Langetepe. Geomentric data structures for computer graphics. Proc. of ACM SIGGRAPH. ACM Transactions of Graphics, pp. 27-31, July 2003. 121
[Zac02] G. Zachmann. Minimal hierarchical collision detection. Proc. of ACM Sympo-sium on Virtual Reality Software and Technology (VRST) (Hong Kong, China, Nov.11–13, 2002), pp. 121–128. 121, 122
[Zac98]G. Zachmann. Rapid collision detection by dynamically aligned DOP-trees. Proc. of IEEE Virtual Reality Annual International Symposium; VRAIS ’ 98 (Atlanta, Georgia, Mar. 1998), pp. 90–97. 121
[Zha01] Dongliang Zhang,Matthew M.F. Yuen. Cloth simulation using multilevel meshes. 2001 Elasevier Science Ltd.
[丁 瑜04] 丁瑜, 方晶晶. 服飾設計自動化-自動版型的產生. 國立成功大學機械工程研究所, 2004.
[朱百晟03] 朱百晟, 謝孟達. 腹腔鏡手術模擬系統 - 以2D取代3D之手術模擬系統. 國立成功大學工業設計研究所, 2003.
[陳冠宏02] 陳冠宏, 蔡明俊. 3D人體點資料的特徵萃取與電腦人模建立. 國立成功大學機械工程研究所, 2002.
[陳建誠03] 陳建誠, 方晶晶. 服飾設計自動化-三維服裝設計與剪裁. 國立成功大學機械工程研究所, 2003.
[廖振凱02] 廖振凱, 方晶晶. 服飾設計自動化-三維服裝設計與編修. 國立成功大學機械工程研究所, 2002.