Hamzah Asyrani Sulaiman1*, Abdullah Bade2

1Universiti Teknikal Malaysia Melaka,
Durian Tunggal, Melaka, Malaysia
2Faculty of Science and Natural Resources,
Universiti Malaysia Sabah,
Jalan UMS, 88400 Kota Kinabalu, Sabah, Malaysia.

ABSTRACT. Computing penetration depth between two or more polygons commonly described by most researchers as one of the high computational cost process. Major implementation required numbers of pre-processing function just to find the minimum penetrating depth between those penetrated objects or polygons. In this paper, we proposed a technique that manipulates the advantages of Dynamic Pivot Point into computing penetration depth between two or more objects. Comparing our proposed technique (DyOP-PD) with the well-known Lin-Canny technique, the conducted experiments proved that our proposed technique has achieved better efficiency. Overall time for DyOP-PD technique to compute penetration depth was significantly faster than the Lin-Canny PD technique (refer Figure 6.9). Our technique was faster than the prominent technique where the computational time significantly reduced, solved a larger fraction of problems, and produced better paths of penetration depth. The lowest results recorded from our simulation was in average at 10.22 milliseconds for DyOP PD and 21.33 milliseconds for Lin-Canny PD technique. The findings proved that DyOP-PD technique is robust to handle efficient, nearly accurate, and fast penetration depth detection compared to Lin-Canny-PD technique.

KEYWORDS. Collision detection, penetration depth, virtual environment



  • Bergen, G. V D. 2001. Proximity Queries and Penetration Depth Computation on 3D Game Objects, in Game Developers Conference.
  • Kim,Y. J., Otaduy, M. A., M. C. Lin & D. Manocha. 2003. Fast Penetration Depth Estimation Using Rasterization Hardware And Hierarchical Refinement. Presented at the Proceedings of The Nineteenth Annual Symposium On Computational Geometry, San Diego, California, USA.
  • Redon, S., Kheddar, A. & Coquillart. S., 2002. Fast Continuous Collision Detection between Rigid Bodies. Computer Graphics Forum, 21: 279-287.
  • Shengzheng, W. & Jie, Y. 2009. Efficient Collision Detection for Soft Tissue Simulation In A Surgical Planning System. Computer-Aided Design and Computer Graphics, 2009. CAD/Graphics ’09. 11th IEEE International Conference on, 49-53.
  • Stephane, R. & Lin, M. C. 2006. A Fast Method for Local Penetration Depth Computation. Journal of Graphics Tools.
  • Sulaiman, H. A., Othman, M. A., Ismail, M. M, Misran, M. H., Said, M. A., B. M., Ramlee, R. A. 2013. Quad Separation Algorithm for Bounding-Volume Hierarchies Construction In Virtual
  • Environment Application. Journal of Next Generation Information Technology, 4: 63-73
  • Zhang, L., Kim Y. J., Varadhan, G. & Manocha, D. 2007. Generalized Penetration Depth Computation. Computer-Aided Design, 39(8): 625-638.
  • Zhang, X., Kim, Y. J. & Manocha, D. 2014. Continuous Penetration Depth. Computer-Aided Design, 46: 3-13

Download Full Paper Here (Right-Click and Save As.. )