Non-manifold level sets: a multivalued implicit surface representation with applications to self-collision processing

Abstract

Level sets have been established as highly versatile implicit surface representations, with widespread use in graphics applications including modeling and dynamic simulation. Nevertheless, level sets are often presumed to be limited, compared to explicit meshes, in their ability to represent domains with thin topological features (e.g. narrow slits and gaps) or, even worse, material overlap. Geometries with such features may arise from modeling tools that tolerate occasional self-intersections, fracture modeling algorithms that create narrow or zero-width cuts by design, or as transient states in collision processing pipelines for deformable objects. Converting such models to level sets can alter their topology if thin features are not resolved by the grid size. We argue that this ostensible limitation is not an inherent defect of the implicit surface concept, but a collateral consequence of the standard Cartesian lattice used to store the level set values. We propose storing signed distance values on a regular hexahedral mesh which can have multiple collocated cubic elements and non-manifold bifurcation to accommodate non-trivial topology. We show how such non-manifold level sets can be systematically generated from convenient alternative geometric representations. Finally we demonstrate how this representation can facilitate fast and robust treatment of self-collision in simulations of volumetric elastic deformable bodies.

References

1. Adalsteinsson, D., and Sethian, J. A. 1994. A fast level set method for propagating interfaces. JCP 118, 269--277.
2. Baraff, D., Witkin, A., and Kass, M. 2003. Untangling cloth. ACM Trans. Graph. 22, 3, 862--870.
3. Bloomenthal, J., and Ferguson, K. 1995. Polygonization of non-manifold implicit surfaces. SIGGRAPH '95, 309--316.
4. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treatment of collisions, contact and friction for cloth animation. ACM Trans. Graph. 21, 3, 594--603.
5. Bridson, R., Marino, S., and Fedkiw, R. 2003. Simulation of clothing with folds and wrinkles. SCA '03, 28--36.
6. Chentanez, N., and Müller, M. 2011. Real-time eulerian water simulation using a restricted tall cell grid. SIGGRAPH '11, 82:1--82:10.
7. Da, F., Batty, C., and Grinspun, E. 2014. Multimaterial mesh-based surface tracking. ACM TOG 33, 4, 112:1--112:11.
8. Enright, D., Marschner, S., and Fedkiw, R. 2002. Animation and rendering of complex water surfaces. ACM Trans. Graph. 21, 3, 736--744.
9. Faure, F., Barbier, S., Allard, J., and Falipou, F. 2008. Image-based collision detection and response between arbitrary volume objects. SCA '08, 155--162.
10. Gascuel, M.-P. 1993. An implicit formulation for precise contact modeling between flexible solids. In SIGGRAPH '93, 313--320.
11. Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Nonconvex rigid bodies with stacking. ACM TOG 22, 3, 871--878.
12. Hellrung, J., Selle, A., Shek, A., Sifakis, E., and Teran, J. 2009. Geometric fracture modeling in bolt. In SIGGRAPH 2009: Talks, SIGGRAPH '09, 7:1--7:1.
13. Houston, B., Nielsen, M. B., Batty, C., Nilsson, O., and Museth, K. 2006. Hierarchical RLE level set: A compact and versatile deformable surface representation. ACM Trans. Graph. 25, 1, 151--175.
14. Irving, G., Guendelman, E., Losasso, F., and Fedkiw, R. 2006. Efficient simulation of large bodies of water by coupling two and three dimensional techniques. SIGGRAPH, 805--811.
15. Kaufmann, P., Martin, S., Botsch, M., Grinspun, E., and Gross, M. 2009. Enrichment textures for detailed cutting of shells. ACM Trans. Graph. 28, 3, 50:1--50:10.
16. Kobbelt, L. P., Botsch, M., Schwanecke, U., and Seidel, H.-P. 2001. Feature sensitive surface extraction from volume data. SIGGRAPH '01, 57--66.
17. Labelle, F., and Shewchuk, J. 2007. Isosurface stuffing: Fast tetrahedral meshes with good dihedral angles. ACM TOG 26, 3.
18. Losasso, F., Gibou, F., and Fedkiw, R. 2004. Simulating water and smoke with an octree data structure. SIGGRAPH '04, 457--462.
19. Losasso, F., Shinar, T., Selle, A., and Fedkiw, R. 2006. Multiple interacting liquids. ACM TOG 25, 3, 812--819.
20. McAdams, A., Zhu, Y., Selle, A., Empey, M., Tamstorf, R., Teran, J., and Sifakis, E. 2011. Efficient elasticity for character skinning with contact and collisions. ACM Trans. Graph. 30, 4, 37:1--37:12.
21. Moës, N., Dolbow, J., and Belytschko, T. 1999. A finite element method for crack growth without remeshing. IJNME 46, 131--150.
22. Molino, N., Bao, Z., and Fedkiw, R. 2004. A virtual node algorithm for changing mesh topology during simulation. ACM Trans. Graph. 23, 3, 385--392.
23. Muller, M., Teschner, M., and Gross, M. 2004. Physically-based simulation of objects represented by surface meshes. CGI '04, 26--33.
24. Museth, K., Breen, D., Whitaker, R., and Barr, A. 2002. Level set surface editing operators. In ACM TOG, 330--338.
25. Museth, K. 2011. DB+Grid: A novel dynamic blocked grid for sparse high-resolution volumes and level sets. SIGGRAPH '11.
26. Museth, K. 2013. VDB: High-resolution sparse volumes with dynamic topology. ACM Trans. Graph. 32, 3 (July), 27:1--27:22.
27. Nesme, M., Kry, P. G., Jeřábková, L., and Faure, F. 2009. Preserving topology and elasticity for embedded deformable models. ACM Trans. Graph. 28, 3, 52:1--52:9.
28. Nielsen, M. B., and Museth, K. 2006. Dynamic tubular grid: An efficient data structure and algorithms for high resolution level sets. J. Sci. Comput. 26, 3 (Mar.), 261--299.
29. Osher, S., and Fedkiw, R. 2002. Level Set Methods and Dynamic Implicit Surfaces. Springer.
30. Osher, S., and Sethian, J. 1988. Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. J. Comput. Phys. 79, 12--49.
31. Rivers, A., and James, D. 2007. FastLSM: Fast lattice shape matching for robust real-time deformation. ACM TOG 26, 3.
32. Sacht, L., Jacobson, A., Panozzo, D., Schüller, C., and Sorkine-Hornung, O. 2013. Consistent volumetric discretizations inside self-intersecting surfaces. Computer Graphics Forum 32, 5, 147--156.
33. Setaluri, R., Aanjaneya, M., Bauer, S., and Sifakis, E. 2014. SPGrid: A sparse paged grid structure applied to adaptive smoke simulation. ACM Trans. Graph. 33, 6, 205:1--205:12.
34. Sethian, J. A. 1998. Fast marching methods. SIAM Review 41, 199--235.
35. Sifakis, E., and Barbic, J. 2012. Fem simulation of 3d deformable solids: A practitioner's guide to theory, discretization and model reduction. In ACM SIGGRAPH 2012 Courses, SIGGRAPH '12.
36. Sifakis, E., Der, K. G., and Fedkiw, R. 2007. Arbitrary cutting of deformable tetrahedralized objects. SCA '07, 73--80.
37. Teran, J., Sifakis, E., Blemker, S. S., Ng-Thow-Hing, V., Lau, C., and Fedkiw, R. 2005. Creating and simulating skeletal muscle from the visible human data set. IEEE Transactions on Visualization and Computer Graphics 11, 3, 317--328.
38. Teran, J., Sifakis, E., Irving, G., and Fedkiw, R. 2005. Robust quasistatic finite elements and flesh simulation. SCA '05, 181--190.
39. Vaillant, R., Barthe, L., Guennebaud, G., Cani, M.-P., Rohmer, D., Wyvill, B., Gourmel, O., and Paulin, M. 2013. Implicit skinning: Real-time skin deformation with contact modeling. ACM Trans. Graph. 32, 4, 125:1--125:12.
40. Vaillant, R., Guennebaud, G., Barthe, L., Wyvill, B., and Cani, M.-P. 2014. Robust iso-surface tracking for interactive character skinning. ACM TOG 33, 6, 189:1--189:11.
41. Wang, B., Faure, F., and Pai, D. K. 2012. Adaptive image-based intersection volume. ACM Trans. Graph. 31, 4, 97:1--97:9.
42. Yuan, Z., Yu, Y., and Wang, W. 2012. Object-space multi-phase implicit functions. ACM TOG 31, 4, 114:1--114:10.
43. Zhao, H.-K., Osher, S., and Fedkiw, R. 2001. Fast surface reconstruction using the level set method. VLSM '01, 194--202.
44. Zheng, W., Yong, J.-H., and Paul, J.-C. 2006. Simulation of bubbles. SCA '06, 325--333.

Index Terms

• Computing methodologies

  • Computer graphics

    • Animation

      • Physical simulation

    • Shape modeling

• Mathematics of computing

  • Continuous mathematics

    • Topology

      • Geometric topology