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

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