“Star-contours for efficient hierarchical self-collision detection” by Schvartzman, Pérez and Otaduy

Collision detection is a problem that has often been addressed efficiently with the use of hierarchical culling data structures. In the subproblem of self-collision detection for triangle meshes, however, such hierarchical data structures lose much of their power, because triangles adjacent to each other cannot be distinguished from actually colliding ones unless individually tested. Shape regularity of surface patches, described in terms of orientation and contour conditions, was proposed long ago as a culling criterion for hierarchical self-collision detection. However, to date, algorithms based on shape regularity had to trade conservativeness for efficiency, because there was no known algorithm for efficiently performing 2D contour self-intersection tests.In this paper, we introduce a star-contour criterion that is amenable to hierarchical computations. Together with a thorough analysis of the tree traversal process in hierarchical self-collision detection, it has led us to novel hierarchical data structures and algorithms for efficient yet conservative self-collision detection. We demonstrate the application of our algorithm to several example animations, and we show that it consistently outperforms other approaches.

1. Arvo, J., and Kirk, D. B. 1987. Fast ray tracing by ray classification. In Computer Graphics (Proceedings of SIGGRAPH 87), 55–64. Google ScholarDigital Library
2. Avis, D., and Toussaint, G. T. 1981. An efficient algorithm for decomposing a polygon into star-shaped polygons. Pattern Recognition 13, 6.Google ScholarCross Ref
3. Baciu, G., and Wong, W. S.-K. 2002. Hardware-assisted self-collision for deformable surfaces. Proc. of the ACM Symposium on Virtual Reality Software and Technology. Google ScholarDigital Library
4. Gottschalk, S. 2000. Collision Queries Using Oriented Bounding Boxes. PhD thesis, The University of North Carolina at Chapel Hill. Google ScholarDigital Library
5. Govindaraju, N., Redon, S., Lin, M., and Manocha, D. 2003. CULLIDE: Interactive collision detection between complex models in large environments using graphics hardware. Proc. of ACM SIGGRAPH/Eurographics Workshop on Graphics Hardware, 25–32. Google ScholarDigital Library
6. Govindaraju, N. K., Knott, D., Jain, N., Kabul, I., Tamstorf, R., Gayle, R., Lin, M. C., and Manocha, D. 2005. Interactive collision detection between deformable models using chromatic decomposition. Proc. of ACM SIGGRAPH. Google ScholarDigital Library
7. Grinspun, E., and Schröder, P. 2001. Normal bounds for subdivision-surface interference detection. Proc. of IEEE Visualization Conference. Google ScholarDigital Library
8. James, D. L., and Pai, D. K. 2004. BD-Tree: Output-sensitive collision detection for reduced deformable models. Proc. of ACM SIGGRAPH. Google ScholarDigital Library
9. Karypis, G., and Kumar, V. 1999. A fast and highly quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing 20, 1. Google ScholarDigital Library
10. Lee, D. T., and Preparata, F. P. 1979. An optimal algorithm for finding the kernel of a polygon. Journal of the ACM 26, 3. Google ScholarDigital Library
11. Mezger, J., Kimmerle, S., and Etzmuß, O. 2003. Hierarchical techniques in collision detection for cloth animation. Proc. of WSCG.Google Scholar
12. Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garment. Proc. of 8th Eurographics Workshop on Computer Animation and Simulation, 177–189.Google ScholarCross Ref
13. Schvartzman, S. C., Gascon, J., and Otaduy, M. A. 2009. Bounded normal trees for reduced deformations of triangulated surfaces. Proc. of ACM SIGGRAPH / Eurographics Symposium on Computer Animation. Google ScholarDigital Library
14. Sud, A., Govindaraju, N. K., Gayle, R., Kabul, I., and Manocha, D. 2006. Fast proximity computation among multiple deformable models using discrete voronoi diagrams. Proc. of ACM SIGGRAPH. Google ScholarDigital Library
15. Tang, M., Curtis, S., Yoon, S.-E., and Manocha, D. 2008. Interactive continuous collision detection between deformable models using connectivity-based culling. Proc. of ACM Symposium on Solid and Physical Modeling. Google ScholarDigital Library
16. Teschner, M., Heidelberger, B., Müeller, M., Pomeranets, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. Proc. of Vision, Modeling and Visualization.Google Scholar
17. Van den Bergen, G. 1997. Efficient collision detection of complex deformable models using AABB trees. J. Graphics Tools 2, 4, 1–14. Google ScholarDigital Library
18. Varadhan, G., and Manocha, D. 2005. Star-shaped roadmaps – a deterministic sampling approach for complete motion planning. Proc. of Robotics: Science and Systems.Google Scholar
19. Volino, P., and Magnenat-Thalmann, N. 1994. Efficient self-collision detection on smoothly discretized surface animations using geometrical shape regularity. Eurographics.Google Scholar