“Subspace self-collision culling” by Barbic and James

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