“Energy-based self-collision culling for arbitrary mesh deformations” by Zheng and James

  • ©Changxi Zheng and Doug L. James




    Energy-based self-collision culling for arbitrary mesh deformations



    In this paper, we accelerate self-collision detection (SCD) for a deforming triangle mesh by exploiting the idea that a mesh cannot self collide unless it deforms enough. Unlike prior work on subspace self-collision culling which is restricted to low-rank deformation subspaces, our energy-based approach supports arbitrary mesh deformations while still being fast. Given a bounding volume hierarchy (BVH) for a triangle mesh, we precompute Energy-based Self-Collision Culling (ESCC) certificates on bounding-volume-related sub-meshes which indicate the amount of deformation energy required for it to self collide. After updating energy values at runtime, many bounding-volume self-collision queries can be culled using the ESCC certificates. We propose an affine-frame Laplacian-based energy definition which sports a highly optimized certificate pre-process, and fast runtime energy evaluation. The latter is performed hierarchically to amortize Laplacian energy and affine-frame estimation computations. ESCC supports both discrete and continuous SCD with detailed and nonsmooth geometry. We observe significant culling on many examples, with SCD speed-ups up to 26X.


    1. Barbić, J., and James, D. L. 2010. Subspace Self-Collision Culling. ACM Transactions on Graphics 29, 4 (July), 81:1–81:9. Google ScholarDigital Library
    2. Briceño, H. M., Sander, P. V., McMillan, L., Gortler, S., and Hoppe, H. 2003. Geometry videos: a new representation for 3D animations. In Symposium on Computer Animation, 136–146. Google ScholarDigital Library
    3. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust Treatment of Collisions, Contact, and Friction for Cloth Animation. ACM Transactions on Graphics 21, 3, 594–603. Google ScholarDigital Library
    4. Burges, C. 1998. A tutorial on support vector machines for pattern recognition. Data mining and knowledge discovery 2, 2, 121–167. Google ScholarDigital Library
    5. Cohen-Steiner, D., Alliez, P., and Desbrun, M. 2004. Variational shape approximation. ACM Transactions on Graphics 23, 3 (Aug.), 905–914. Google ScholarDigital Library
    6. Curtis, S., Tamstorf, R., and Manocha, D. 2008. Fast collision detection for deformable models using representative-triangles. In Proc. ACM Symp. Interactive 3D Graphics and Games, 61–69. Google ScholarDigital Library
    7. Demmel, J. 1997. Applied numerical linear algebra. SIAM, Philadelphia, PA. Google ScholarDigital Library
    8. Gao, J., Guibas, L., and Nguyen, A. 2006. Deformable spanners and applications. Computational Geometry: Theory and Appl. 35, 1-2, 2–19. Google ScholarDigital Library
    9. Goldsmith, J., and Salmon, J. 1987. Automatic creation of object hierarchies for ray tracing. IEEE Computer Graphics and Applications 7, 5, 14–20. Google ScholarDigital Library
    10. Gottschalk, S., Lin, M., and Manocha, D. 1996. OBB-Tree: A Hierarchical Structure for Rapid Interference Detection. In Proceedings of SIGGRAPH 96, Computer Graphics Proceedings, Annual Conference Series, 171–180. Google ScholarDigital Library
    11. Govindaraju, N., Knott, D., Jain, N., Kabul, I., Tamstorf, R., Gayle, R., Lin, M., and Manocha, D. 2005. Interactive collision detection between deformable models using chromatic decomposition. ACM Transactions on Graphics 24, 3, 991–999. Google ScholarDigital Library
    12. Govindaraju, N., Lin, M., and Manocha, D. 2005. Quick-CULLIDE: Fast inter-and intra-object collision culling using graphics hardware. In Proc. IEEE Virtual Reality, 59–66. Google ScholarDigital Library
    13. Grinspun, E., and Schröder, P. 2001. Normal bounds for subdivision-surface interference detection. In IEEE Visualization 2001, 333–340. Google ScholarDigital Library
    14. Guibas, L., Nguyen, A., Russel, D., and Zhang, L. 2002. Collision Detection for Deforming Necklaces. In Proc. of the ACM Symposium on Computational Geometry, 33–42. Google ScholarDigital Library
    15. Guibas, L. 2004. Kinetic Data Structures. In Handbook of Data Structures and Applications. Chapman and Hall/CRC.Google Scholar
    16. Heidelberger, B., Teschner, M., and Gross, M. 2004. Detection of collisions and self-collisions using image-space techniques. Journal of WSCG 12, 3, 145–152.Google Scholar
    17. Hubbard, P. M. 1995. Collision Detection for Interactive Graphics Applications. PhD thesis, Department of Computer Science, Brown University. Google ScholarDigital Library
    18. James, D. L., and Pai, D. K. 2004. BD-Tree: Output-sensitive collision detection for reduced deformable models. ACM Transactions on Graphics 23, 3 (Aug.), 393–398. Google ScholarDigital Library
    19. James, D. L., and Twigg, C. D. 2005. Skinning mesh animations. ACM Transactions on Graphics 24, 3 (Aug.), 399–407. Google ScholarDigital Library
    20. Klosowski, J. T., Held, M., Mitchell, J. S. B., Sowizral, H., and Zikan, K. 1998. Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs. IEEE Trans. Vis. & Comp. Graphics 4, 1, 21–36. Google ScholarDigital Library
    21. Meyer, M., Desbrun, M., Schröeder, P., and Barr, A. H. 2002. Discrete differential geometry operators for triangulated 2-manifolds. In Proceedings of VisMath.Google Scholar
    22. Müller, M., and Chentanez, N. 2011. Solid simulation with oriented particles. ACM Transactions on Graphics 30 (Aug.), 92:1–92:10. Google ScholarDigital Library
    23. Müller, M., Heidelberger, B., Teschner, M., and Gross, M. 2005. Meshless deformations based on shape matching. ACM Trans. on Graphics 24, 3, 471–478. Google ScholarDigital Library
    24. Nickalls, R. 1993. A new approach to solving the cubic: Cardan’s solution revealed. The Mathematical Gazette 77, 480, 354–359.Google Scholar
    25. Provot, X. 1997. Collision and Self-Collision Handling in Cloth Model Dedicated to Design Garments. In Graphics Interface, 177–189.Google Scholar
    26. Rivers, A. R., and James, D. L. 2007. FastLSM: Fast Lattice Shape Matching for Robust Real-Time Deformation. ACM Transactions on Graphics 26, 3, 82:1–82:6. Google ScholarDigital Library
    27. Schenk, O., and Gärtner, K. 2004. Solving unsymmetric sparse systems of linear equations with PARDISO. Future Generation Computer Systems 20, 3, 475–487. Google ScholarDigital Library
    28. Schvartzman, S. C., Gascón, J., and Otaduy, M. A. 2009. Bounded normal trees for reduced deformations of triangulated surfaces. In Symp. on Computer Animation (SCA), 75–82. Google ScholarDigital Library
    29. Schvartzman, S. C., lvaro G. Pérez, and Otaduy, M. A. 2010. Star-contours for efficient hierarchical self-collision detection. ACM Transactions on Graphics 29, 4 (July), 80:1–80:8. Google ScholarDigital Library
    30. Steinemann, D., Otaduy, M. A., and Gross, M. 2008. Fast adaptive shape matching deformations. In Symposium on Computer Animation, 87–94. Google ScholarDigital Library
    31. Sud, A., Govindaraju, N., Gayle, R., Kabul, I., and Manocha, D. 2006. Fast Proximity Computation Among Deformable Models using Discrete Voronoi Diagrams. ACM Transactions on Graphics 25, 3, 1144–1153. Google ScholarDigital Library
    32. Tang, M., Curtis, S., Yoon, S.-E., and Manocha, D. 2009. Interactive continuous collision detection between deformable models using connectivity-based culling. IEEE Trans. on Visualization and Computer Graphics 15, 544–557. Google ScholarDigital Library
    33. Teschner, M., et al. 2005. Collision Detection for Deformable Objects. Computer Graphics Forum 24, 1, 61–81.Google ScholarCross Ref
    34. van den Bergen, G. 1997. Efficient Collision Detection of Complex Deformable Models using AABB Trees. Journal of Graphics Tools 2, 4, 1–14. Google ScholarDigital Library
    35. Volino, P., and Magnenat-Thalmann, N. 1994. Efficient Self-Collision Detection on Smoothly Discretized Surface Animations using Geometrical Shape Regularity. Computer Graphics Forum 13, 3, 155–166.Google ScholarCross Ref

ACM Digital Library Publication: