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.
@article{Sacht:2015:NC,
author = {Leonardo Sacht and Etienne Vouga and Alec Jacobson},
title = {Nested Cages},
journal = {ACM Transactions on Graphics (TOG)},
volume = {34},
number = {6},
year = {2015},
}We thank: Derek Bradley, Keenan Crane, Eitan Grinspun, and Daniele Panozzo, for illuminating discussions; Eric Price, for brainstorming the NP completeness proof; Henrique Maia, Papoj Thamjaroenporn, and Sarah Abraham, for proofreading; and Peter Schroeder, Richard Kenyon, Alexander I. Bobenko, Helmut Pottmann, and Johannes Wallner for organizing the DDG Oberwolfach and Seggau Geometry workshops. The Columbia Computer Graphics Group is supported by the NSF, Intel, The Walt Disney Company, and Autodesk. Funded in part by NSF grant DMS-1304211. We thank the Visgraf Lab and IMPA, for the technical support and software resources, CNPq, for the first author’s PhD fellowship, and CAPES and FAPESC, for supporting the presentation of this work at SIGGRAPH Asia 2015.