“Nested cages”
Conference:
Type(s):
Title:
- Nested cages
Session/Category Title: Geometry Processing
Presenter(s)/Author(s):
Abstract:
Many tasks in geometry processing and physical simulation benefit from multiresolution hierarchies. One important characteristic across a variety of applications is that coarser layers strictly encage finer layers, nesting one another. Existing techniques such as surface mesh decimation, voxelization, or contouring distance level sets do not provide sufficient control over the quality of the output surfaces while maintaining strict nesting. We propose a solution that enables use of application-specific decimation and quality metrics. The method constructs each next-coarsest level of the hierarchy, using a sequence of decimation, flow, and contact-aware optimization steps. From coarse to fine, each layer then fully encages the next while retaining a snug fit. The method is applicable to a wide variety of shapes of complex geometry and topology. We demonstrate the effectiveness of our nested cages not only for multigrid solvers, but also for conservative collision detection, domain discretization for elastic simulation, and cage-based geometric modeling.
References:
1. Adams, M., and Demmel, J. W. 1999. Parallel multigrid solver for 3d unstructured finite element problems. In Proceedings of the 1999 ACM/IEEE Conference on Supercomputing.
2. Ainsley, S., Vouga, E., Grinspun, E., and Tamstorf, R. 2012. Speculative parallel asynchronous contact mechanics. ACM Trans. Graph. 31, 6.
3. Aksoylu, B., Khodakovsky, A., and Schröder, P. 2005. Multilevel Solvers for Unstructured Surface Meshes. SIAM Journal on Scientific Computing 26, 4, 1146.
4. Attene, M. 2010. A lightweight approach to repairing digitized polygon meshes. The Visual Computer 26, 11, 1393–1406.
5. Au, O. K.-C., Tai, C.-L., Chu, H.-K., Cohen-Or, D., and Lee, T.-Y. 2008. Skeleton extraction by mesh contraction. ACM Trans. Graph. 27, 3.
6. Baerentzen, J. A., and Aanaes, H. 2005. Signed distance computation using the angle weighted pseudonormal. Trans. Vis. & Comp. Graphics 11, 3 (May).
7. Baraff, D., Witkin, A., and Kass, M. 2003. Untangling cloth. ACM Trans. Graph. 22.
8. Ben-Chen, M., Weber, O., and Gotsman, C. 2009. Spatial deformation transfer. In Proc. SCA, 67–74.
9. Ben-Chen, M., Weber, O., and Gotsman, C. 2009. Variational harmonic maps for space deformation. ACM Trans. Graph. 28, 3.
10. Botsch, M., Steinberg, S., Bischoff, S., and Kobbelt, L. 2002. OpenMesh — a generic and efficient polygon mesh data structure. In OpenSG Symposium.
11. Brochu, T., and Bridson, R. 2009. Robust topological operations for dynamic explicit surfaces. SIAM Sci. Comp. 31, 4.
12. Brochu, T., Edwards, E., and Bridson, R. 2012. Efficient geometrically exact continuous collision detection. ACM Trans. Graph. 31, 4.
13. Brune, P. R., Knepley, M. G., and Scott, L. R. 2011. Unstructured geometric multigrid in two and three dimensions on complex and graded meshes. CoRR abs/1104.0261.
14. Campen, M., and Kobbelt, L. 2010. Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes. Comput. Graph. Forum 29, 5, 1613–1622.
15. Cgal, Computational Geometry Algorithms Library. http://www.cgal.org.
16. Chan, T. F., and Wan, W. 2000. Robust multigrid methods for nonsmooth coefficient elliptic linear systems. J. Comput. Appl. Math. 123, 1–2.
17. Chan, T. F., and Zou, J. 1996. A convergence theory of multilevel additive schwarz methods on unstructured meshes. Numerical Algorithms 13, 2, 365–398.
18. Chan, T. F., Smith, B., and Zou, J. 1996. Overlapping schwarz methods on unstructured meshes using non-matching coarse grids. Numer. Math 73, 149–167.
19. Chan, T. F., Go, S., and Zou, J. 1999. Boundary treatments for multilevel methods on unstructured meshes. SIAM Journal on Scientific Computing 21, 1, 46–66.
20. Chang, W., Li, H., Mitra, N. J., Pauly, M., and Wand, M. 2010. Geometric registration for deformable shapes. In Eurographics 2010: Tutorial Notes.
21. Chao, I., Pinkall, U., Sanan, P., and Schröder, P. 2010. A simple geometric model for elastic deformations. ACM Trans. Graph. 29, 4.
22. Chuang, M., Luo, L., Brown, B. J., Rusinkiewicz, S., and Kazhdan, M. 2009. Estimating the laplace-beltrami operator by restricting 3d functions. In Proc. SGP, 1475–1484.
23. Crane, K., Pinkall, U., and Schröder, P. 2013. Robust fairing via conformal curvature flow. ACM Trans. Graph. 32, 4.
24. Debunne, G., Desbrun, M., Cani, M.-P., and Barr, A. H. 2001. Dynamic real-time deformations using space & time adaptive sampling. Proceedings of SIGGRAPH 2001, 31–36.
25. Demmel, J., 2004. Multigrid overview. http://www.cs.berkeley.edu/~demmel.
26. Deng, Z.-J., Luo, X.-N., and Miao, X.-P. 2011. Automatic cage building with quadric error metrics. Comp. Sci. & Tech. 26, 3.
27. Desbrun, M., Meyer, M., Schröder, P., and Barr, A. H. 1999. Implicit fairing of irregular meshes using diffusion and curvature flow. In Proccedings of ACM SIGGRAPH, 317–324.
28. Dick, C., Georgii, J., and Westermann, R. 2011. A hexahedral multigrid approach for simulating cuts in deformable objects. Trans. Vis. & Comp. Graphics 17, 11.
29. Dickopf, T. 2010. Multilevel methods based on non-nested meshes. PhD thesis, Universität Bonn.
30. Eppstein, D., 2015. When is it possible to “shrink” a polyhedron? MathOverflow. http://mathoverflow.net/q/206750 (version: 2015-05-16).
31. Falgout, R. 2006. An introduction to algebraic multigrid computing. Computing in Science Engineering (Nov).
32. Feng, Y., Perić, D., and Owen, D. 1997. A non-nested galerkin multi-grid method for solving linear and nonlinear solid mechanics problems. Comp. methods in applied mech. & eng. 144, 3.
33. Ferstl, F., Westermann, R., and Dick, C. 2014. Large-scale liquid simulation on adaptive hexahedral grids. Trans. Vis. & Comp. Graphics 20, 10.
34. Fish, J., Pandheeradi, M., and Belsky, V. 1995. An efficient multilevel solution scheme for large scale non-linear systems. Int. Journal for Numerical Methods in Eng. 38, 10, 1597–1610.
35. Garland, M., and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. In Proc. SIGGRAPH.
36. Guillard, H. 1993. Node-nested multi-grid method with Delaunay coarsening. Research Report RR-1898.
37. Gumhold, S., Borodin, P., and Klein, R. 2003. Intersection free simplification. IJSM, 155–176.
38. Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous contact mechanics. ACM Trans. Graph. 28, 3.
39. Harmon, D., Panozzo, D., Sorkine, O., and Zorin, D. 2011. Interference aware geometric modeling. ACM Trans. Graph. 30, 6.
40. Hoppe, H. 1996. Progressive meshes. In Proc. SIGGRAPH.
41. Jacobson, A., Kavan, L., and Sorkine-Hornung, O. 2013. Robust inside-outside segmentation using generalized winding numbers. ACM Trans. Graph. 32, 4.
42. Joshi, P., Meyer, M., DeRose, T., Green, B., and Sanocki, T. 2007. Harmonic coordinates for character articulation. ACM Trans. Graph. 26, 3, 71.
43. Kazhdan, M., Bolitho, M., and Hoppe, H. 2006. Poisson surface reconstruction. In Proc. SGP, 61–70.
44. Kazhdan, M., Solomon, J., and Ben-Chen, M. 2012. Can mean-curvature flow be modified to be non-singular? Comput. Graph. Forum 31, 5.
45. Krishnan, D., Fattal, R., and Szeliski, R. 2013. Efficient preconditioning of laplacian matrices for computer graphics. ACM Trans. Graph. 32, 4.
46. 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 (Aug.), 37:1–37:12.
47. Mehra, R., Zhou, Q., Long, J., Sheffer, A., Gooch, A., and Mitra, N. J. 2009. Abstraction of man-made shapes. ACM Trans. Graph. 28, 5.
48. Melax, S. 1998. A simple, fast, and effective polygon reduction algorithm. Game Developer Magazine, 44–49.
49. Mueller, M., Chentanez, N., Kim, T.-Y., and Macklin, M. 2015. Air meshes for robust collision handling. ACM Trans. Graph. 34, 4.
50. 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.
51. Otaduy, M. A., and Lin, M. C. 2003. CLODs: Dual hierarchies for multiresolution collision detection. In Proc. SGP.
52. Otaduy, M. A., and Lin, M. C. 2003. Sensation preserving simplification for haptic rendering. ACM Trans. Graph. 22.
53. Peng, J., Kristjansson, D., and Zorin, D. 2004. Interactive modeling of topologically complex geometric detail. ACM Trans. Graph. 23, 3, 635–643.
54. Peterhans, C. 2012. Interactive Surface Reconstruction. Master’s thesis, ETH Zurich.
55. Platis, N., and Theoharis, T. 2003. Progressive hulls for intersection applications. Comput. Graph. Forum 22, 2.
56. Poranne, R., Ovreiu, E., and Gotsman, C. 2013. Interactive planarization and optimization of 3d meshes. In Comput. Graph. Forum, vol. 32, 152–163.
57. Ruge, J., and Stüben, K. 1987. Algebraic multigrid. Multigrid methods 3.
58. Sacht, L., Jacobson, A., Panozzo, D., Schüller, C., and Sorkine-Hornung, O. 2013. Consistent volumetric discretizations inside self-intersecting surfaces. In Proc. SGP.
59. Sander, P. V., Gu, X., Gortler, S. J., Hoppe, H., and Snyder, J. 2000. Silhouette clipping. In Proc. SIGGRAPH.
60. Shen, C., O’Brien, J. F., and Shewchuk, J. R. 2004. Interpolating and approximating implicit surfaces from polygon soup. ACM Trans. Graph. 23, 3, 896–904.
61. Si, H., 2003. TetGen: A 3D delaunay tetrahedral mesh generator. http://tetgen.berlios.de.
62. Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proc. SGP, 109–116.
63. Sýkora, D., Dingliana, J., and Collins, S. 2009. As-rigid-as-possible image registration for hand-drawn cartoon animations. In Proc. NPAR.
64. Tagliasacchi, A., Alhashim, I., Olson, M., and Zhang, H. 2012. Mean curvature skeletons. Comput. Graph. Forum 31, 5.
65. Takayama, K., Panozzo, D., Sorkine-Hornung, A., and Sorkine-Hornung, O. 2013. Sketch-based generation and editing of quad meshes. ACM Trans. Graph. 32, 4.
66. Taubin, G. 1995. A signal processing approach to fair surface design. In Proceedings of ACM SIGGRAPH, 351–358.
67. 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. Trans. Vis. & Comp. Graphics 11, 3.
68. Volino, P., and Magnenat-Thalmann, N. 2006. Resolving surface collisions through intersection contour minimization. ACM Trans. Graph. 25, 3.
69. Vouga, E., Sacht, L., and Jacobson, A. 2015. Polyhedral nesting is NP-complete. Tech. rep., in supplementary materials.
70. Wang, Y.-S., and Lee, T.-Y. 2008. Curve-skeleton extraction using iterative least squares optimization. Trans. Vis. & Comp. Graphics 14, 4.
71. Wang, H., Sidorov, K. A., Sandilands, P., and Komura, T. 2013. Harmonic parameterization by electrostatics. ACM Trans. Graph. 32, 5.
72. Wang, H. 2014. Defending continuous collision detection against errors. ACM Trans. Graph. 33, 4.
73. Wicker, M., Lanker, H., and Gross, M. 2006. Untangling cloth with boundaries. In Proc. VMV.
74. Xian, C., Lin, H., and Gao, S. 2009. Automatic generation of coarse bounding cages from dense meshes. In Proc. SMA.
75. Xian, C., Lin, H., and Gao, S. 2012. Automatic cage generation by improved OBBs for mesh deformation. The Visual Computer.
76. Xian, C., Zhang, T., and Gao, S. 2013. Semantic cage generation for fe mesh editing. In CADG.
77. Xian, C., Li, G., and Xiong, Y. 2015. Efficient and effective cage generation by region decomposition. Computer Animation and Virtual Worlds 26, 2, 173–184.
78. Xu, H., and Barbič, J. 2014. Signed distance fields for polygon soup meshes. Graphics Interface 2014.
79. Ye, J., and Zhao, J. 2012. The intersection contour minimization method for untangling oriented deformable surfaces. In Proc. SCA.
