“Subspace self-collision culling” by Barbic and James

  • ©Jernej Barbic and Doug L. James




    Subspace self-collision culling



    We show how to greatly accelerate self-collision detection (SCD) for reduced deformable models. Given a triangle mesh and a set of deformation modes, our method precomputes Subspace Self-Collision Culling (SSCC) certificates which, if satisfied, prove the absence of self-collisions for large parts of the model. At runtime, bounding volume hierarchies augmented with our certificates can aggressively cull overlap tests and reduce hierarchy updates. Our method supports both discrete and continuous SCD, can handle complex geometry, and makes no assumptions about geometric smoothness or normal bounds. It is particularly effective for simulations with modest subspace deformations, where it can often verify the absence of self-collisions in constant time. Our certificates enable low amortized costs, in time and across many objects in multi-body dynamics simulations. Finally, SSCC is effective enough to support self-collision tests at audio rates, which we demonstrate by producing the first sound simulations of clattering objects.


    1. Alexa, M., and Müller, W. 2000. Representing Animations by Principal Components. Comp. Graphics Forum 19, 3, 411–418.Google ScholarCross Ref
    2. Barbič, J., and James, D. L. 2005. Real-time subspace integration for St. Venant-Kirchhoff deformable models. ACM Trans. on Graphics 24, 3, 982–990. Google ScholarDigital Library
    3. Boyd, S., and Vandenberghe, L. 2004. Convex Optimization. Cambridge University Press. Google ScholarDigital Library
    4. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust Treatment of Collisions, Contact, and Friction for Cloth Animation. ACM Trans. on Graphics 21, 3, 594–603. Google ScholarDigital Library
    5. Capell, S., Burkhart, M., Curless, B., Duchamp, T., and Popović, Z. 2007. Physically based rigging for deformable characters. Graphical Models 69, 1, 71–87. Google ScholarDigital Library
    6. Chadwick, J. N., An, S. S., and James, D. L. 2009. Harmonic Shells: A practical nonlinear sound model for near-rigid thin shells. ACM Transactions on Graphics 28, 5, 1–10. Google ScholarDigital Library
    7. 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
    8. Faloutsos, P., van de Panne, M., and Terzopoulos, D. 1997. Dynamic Free-Form Deformations for Animation Synthesis. IEEE Trans. on Vis. and Comp. Graphics 3, 3, 201–214. Google ScholarDigital Library
    9. 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
    10. Golub, G. H., and Loan, C. F. V. 1996. Matrix Computations, 3rd ed. Johns Hopkins University Press. Google ScholarDigital Library
    11. Gottschalk, S., Lin, M. C., and Manocha, D. 1996. OBB-Tree: A Hierarchical Structure for Rapid Interference Detection. In Proc. of ACM SIGGRAPH 96, 171–180. Google ScholarDigital Library
    12. 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 Trans. on Graphics 24, 3, 991–999. Google ScholarDigital Library
    13. 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
    14. Grinspun, E., and Schröder, P. 2001. Normal bounds for subdivision-surface interference detection. In IEEE Visualization 2001, 333–340. Google ScholarDigital Library
    15. Guibas, L., Nguyen, A., Russel, D., and Zhang, L. 2002. Collision Detection for Deforming Necklaces. In Proc. of the ACM Symp. on Computational Geometry, 33–42. Google ScholarDigital Library
    16. Guibas, L. 2004. Kinetic Data Structures. In Handbook of Data Structures and Applications. Chapman and Hall/CRC.Google Scholar
    17. Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous Contact Mechanics. ACM Transactions on Graphics 28, 3, 87:1–87:12. Google ScholarDigital Library
    18. 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
    19. Hirota, G., Fisher, S., and Lin, M. C. 2000. Simulation of Non-penetrating Elastic Bodies Using Distance Fields. Tech. rep., University of North Carolina at Chapel Hill. Google ScholarDigital Library
    20. Huang, Q., Wicke, M., Adams, B., and Guibas, L. 2009. Shape decomposition using modal analysis. Computer Graphics Forum 28, 2, 407–416.Google ScholarCross Ref
    21. Hubbard, P. M. 1995. Collision Detection for Interactive Graphics Applications. PhD thesis, Department of Comp. Science, Brown University. Google ScholarDigital Library
    22. Hughes, M., DiMattia, C., Lin, M., and Manocha, D. 1996. Efficient and accurate interference detection for polynomial deformation. In Proc. Computer Animation’96, 155–166. Google ScholarDigital Library
    23. James, D. L., and Pai, D. K. 2004. BD-Tree: Output-Sensitive Collision Detection for Reduced Deformable Models. ACM Trans. on Graphics 23, 3, 393–398. Google ScholarDigital Library
    24. Kaufman, D. M., Sueda, S., James, D. L., and Pai, D. K. 2008. Staggered Projections for Frictional Contact in Multibody Systems. ACM Transactions on Graphics 27, 5, 164:1–164:11. Google ScholarDigital Library
    25. 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
    26. Larsson, T., and Akenine-Möller, T. 2001. Collision detection for continuously deforming bodies. Eurographics 2001, 325–333.Google Scholar
    27. Larsson, T., and Akenine-Möller, T. 2003. Efficient collision detection for models deformed by morphing. The Visual Computer 19, 2, 164–174.Google ScholarCross Ref
    28. Lin, M., and Canny, J. 1991. A fast algorithm for incremental distance calculation. In IEEE ICRA, vol. 2, 1008–1014.Google Scholar
    29. Meyer, M., and Anderson, J. 2007. Key Point Subspace Acceleration and Soft Caching. ACM Trans. on Graphics 26, 3, 74:1–74:8. Google ScholarDigital Library
    30. Mirtich, B. 1998. V-Clip: Fast and Robust Polyhedral Collision Detection. ACM Trans. on Graphics 17, 3, 177–208. Google ScholarDigital Library
    31. Otaduy, M. A., Germann, D., Redon, S., and Gross, M. 2007. Adaptive Deformations with Fast Tight Bounds. In Symp. on Computer Animation (SCA), 181–190. Google ScholarDigital Library
    32. Pentland, A., and Williams, J. 1989. Good vibrations: Modal dynamics for graphics and animation. Computer Graphics (Proc. of ACM SIGGRAPH 89) 23, 3, 215–222. Google ScholarDigital Library
    33. Provot, X. 1997. Collision and Self-Collision Handling in Cloth Model Dedicated to Design Garments. In Graphics Interface, 177–189.Google Scholar
    34. 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
    35. Sud, A., Govindaraju, N., Gayle, R., Kabul, I., and Manocha, D. 2006. Fast Proximity Computation Among Deformable Models using Discrete Voronoi Diagrams. ACM Trans. on Graphics 25, 3, 1144–1153. Google ScholarDigital Library
    36. 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
    37. Teschner, M., Heidelberger, B., Möller, M., Pomeranets, D., and Gross, M. 2003. Optimized spatial hashing for collision detection of deformable objects. In Proc. Vision, Modeling, and Visualization Conference, 47–54.Google Scholar
    38. Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M., Faure, F., Magnenat-Thalmann, N., Strasser, W., and Volino, P. 2005. Collision Detection for Deformable Objects. Computer Graphics Forum 24, 1, 61–81.Google ScholarCross Ref
    39. van den Bergen, G. 1997. Efficient Collision Detection of Complex Deformable Models using AABB Trees. J. of Graphics Tools 2, 4, 1–14. Google ScholarDigital Library
    40. Volino, P., and Magnenat-Thalmann, N. 1994. Efficient Self-Collision Detection on Smoothly Discretized Surface Animations using Geometrical Shape Regularity. Comp. Graphics Forum 13, 3, 155–166.Google ScholarCross Ref
    41. Witkin, A., and Welch, W. 1990. Fast Animation and Control of Nonrigid Structures. Computer Graphics (Proc. of ACM SIGGRAPH 90) 24, 4, 243–252. Google ScholarDigital Library

ACM Digital Library Publication: