Minimum Normal Cone for Continuous Collision Detection

Abstract:

Continuous collision detection (CCD) algorithm is a vital step in virtual reality. This paper describes an efficient self-collision detection algorithm called the minimum normal cone algorithm. The algorithm calculates the parent-normal cone in a new way, which optimizes the two test conditions for the self-collision detection: In the first test condition, we analyze and calculate the relative position between the two child-normal cones, and then a bottom-up technology is used to build the parent-normal cone. Thus the two child normal cones can be surrounded by the parent-normal cone perfectly, and the normal vectors motion range of the parent-triangular mesh can also be closely restricted; In the second test condition, we calculate the normal vectors motion range of the contour projection line, and check whether the projection line is self-colliding or not, to avoid excessive tests between segments. The algorithm has been implemented and tested on two classical models, cloth-ball and N-body model respectively. Experimental results demonstrate that our algorithm can decrease the number of elementary tests by two orders of magnitudes, and significantly improve the performance of the overall CCD algorithm.

• Periodical: Applied Mechanics and Materials (Volumes 397-400)
• Pages: 2477-2482
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.397-400.2477
• Online since: September 2013
• Authors: Yong Shui, Jin Jin Zheng, Hong Jun Zhou
• Keywords: Continuous Collision Detection, Deformable Models, Minimum Normal Cone, Self-Collision

References

[1] PROVOT, X. Collision and self-collision handling in cloth model dedicated to design garment. Graphics Interface, 177–189, (1997).

DOI: 10.1007/978-3-7091-6874-5_13

[2] BRIDSON, R., FEDKIW, R., AND ANDERSON, J. Robust treatment for collisions, contact and friction for cloth animation. Proc. of ACM SIGGRAPH, 594–603, (2002).

DOI: 10.1145/566654.566623

[3] TANG, M., CURTIS, S., YOON, S., AND MANOCHA, D. ICCD: Interactive continuous collision detection between deformable models using connectivity-based culling. IEEE Transactions on Visualization and Computer Graphics 15, 4, 544–557, (2009).

DOI: 10.1109/tvcg.2009.12

[4] CURTIS, S., TAMSTORF, R., AND MANOCHA, D. Fast collision detection for deformable models using representative-triangles. In SI3D '08: Proceedings of the 2008 Symposium on Interactive 3D graphics and games, 61–69, (2008).

DOI: 10.1145/1342250.1342260

[5] HUTTER, M., AND FUHRMANN, A. Optimized continuous collision detection for deformable triangle meshes. Proc. WSCG07, 25–32, (2007).

[6] BARBIˇC, J., AND JAMES, D. L. Subspace self-collision culling. ACM Trans. on Graphics (SIGGRAPH 2010) 29, 3, (2010).

DOI: 10.1145/1833349.1778818

[7] TANG, C., LI, S., AND WANG, G., P. Reduced deforming filter culling for fast continuous collision detection. Proceedings of the 17th ACM Symposium on Virtual Reality Software and Technology, 79-82, (2010).

DOI: 10.1145/1889863.1889876

[8] ZHANG, X., REDON, S., LEE, M., AND KIM, Y. J. Continuous collision detection for articulated models using taylor models and temporal culling. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2007) 26, 3, 15, (2007).

DOI: 10.1145/1275808.1276396

[9] VOLINO, P., AND THALMANN, N., M. Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. Computer Graphics Forum (EuroGraphics Proc. ) 13, 3, 155–166, (1994).

DOI: 10.1111/1467-8659.1330155

[10] GRINSPUN, E., AND SCHRODER, P. Normal bounds for subdivision-surface interference detection. In IEEE Visualization'01, IEEE Computer Society, 333–340, (2001).

DOI: 10.1109/visual.2001.964529

[11] SCHVARTZMAN, S., GASC ´ON, J., AND OTADUY, M. Bounded normal trees for reduced deformations of triangulated surfaces. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, ACM, 75–82, (2009).

DOI: 10.1145/1599470.1599480

[12] SCHVARTZMAN, S., P´EREZ, A., AND OTADUY, M. Star-contours for efficient hierarchical self-collision detection. In ACM Trans. on Graphics (Proc. of ACM SIGGRAPH), vol. 29, (2010).

DOI: 10.1145/1833349.1778817

[13] WONG, W. S. -K., AND BACIU, G. A randomized marking scheme for continuous collision detection in simulation of deformable surfaces. Proc. of ACM VRCIA, 181–188, (2006).

DOI: 10.1145/1128923.1128954

[14] TANG, M., MANOCHA, D., AND TONG, R. Fast continuous collision detection using deforming non-penetration filters. In Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, ACM, 7–13, (2010).

DOI: 10.1145/1730804.1730806