Mandoline: Robust Cut-Cell Generation for Arbitrary Triangle Meshes

Abstract: Although geometry arising ``in the wild" most often comes in the form of a surface representation, a plethora of geometrical and physical applications require the construction of volumetric embeddings either of the geometry itself or the domain surrounding it. Cartesian cut-cell-based mesh generation provides an attractive solution in which volumetric elements are constructed from the intersection of the input surface geometry with a uniform or adaptive hexahedral grid. This choice, especially common in computational fluid dynamics, has the potential to efficiently generate accurate, surface-conforming cells; unfortunately, current solutions are often slow, fragile, or cannot handle many common topological situations. We therefore propose a novel, robust cut-cell construction technique for triangle surface meshes that explicitly computes the precise geometry of the intersection cells, even on meshes that are open or non-manifold. Its fundamental geometric primitive is the intersection of an arbitrary segment with an axis-aligned plane. Beginning from the set of intersection points between triangle mesh edges and grid planes, our bottom-up approach robustly determines cut-edges, cut-faces, and finally cut-cells, in a manner designed to guarantee topological correctness. We demonstrate its effectiveness and speed on a wide range of input meshes and grid resolutions, and make the code available as open source.

Authors/Presenter(s): Michael Tao, University of Toronto, Canada
Christopher Batty, University of Waterloo, Canada
Eugene Fiume, Simon Fraser University, University of Toronto, Canada
David Levin, University of Toronto, Canada

QuadMixer: Layout Preserving Blending of Quadrilateral Meshes

Abstract: We propose QuadMixer, a novel interactive technique to compose quad mesh components preserving the majority of the original layouts. Quad Layout is a crucial property for many applications since it conveys important information that would otherwise be destroyed by techniques that aim only at preserving shape. Our technique keeps untouched all the quads in the patches which are not involved in the blending. We first perform robust boolean operations on the corresponding triangle meshes. Then we use this result to identify and build new surface patches for small regions neighboring the intersection curves. These blending patches are carefully quadrangulated respecting boundary constraints and stitched back to the untouched parts of the original models. The resulting mesh preserves the designed edge flow that, by construction, is captured and incorporated to the new quads as much as possible. We present our technique in an interactive tool to show its usability and robustness.

Authors/Presenter(s): Stefano Nuvoli, University of Cagliari, Italy
Alex Hernandez, Federal University of Rio de Janeiro, Italia, Brazil
Claudio Esperança, Federal University of Rio de Janeiro, Italia, Brazil
Riccardo Scateni, University of Cagliari, Italia, Italy
Paolo Cignoni, CNR of Italy, Italia, Italy
Nico Pietroni, University of Technology Sydney, Italia, Australia

3D Hodge Decompositions of Edge and Face-based Vector Fields

Abstract: We present a compendium of Hodge decompositions of vector fields on tetrahedral meshes embedded in the 3D Euclidean space. After describing the foundations of the Hodge decomposition in the continuous setting, we describe how to implement a five-component orthogonal decomposition that generically splits, for a variety of boundary conditions, any given discrete vector field expressed as discrete differential forms into two potential fields, as well as three additional harmonic components that arise from the topology or boundary of the domain. The resulting decomposition is proper and mimetic, in the sense that the theoretical dualities on the kernel spaces of vector Laplacians valid in the continuous case (including correspondences to cohomology and homology groups) are exactly preserved in the discrete realm. Such a decomposition only involves simple linear algebra with symmetric matrices, and can thus serve as a basic computational tool for vector field analysis in graphics, electromagnetics, fluid dynamics and elasticity.

Authors/Presenter(s): Rundong Zhao, Michigan State University, United States of America
Mathieu Desbrun, California Institute of Technology, United States of America
Guo-Wei Wei, Michigan State University, United States of America
Yiying Tong, Michigan State University, United States of America

Bounded Distortion Tetrahedral Metric Interpolation

Abstract: We present a method for volumetric shape interpolation with unique shape preserving features. The input to our algorithm are two or more 3-manifolds, immersed into R^3 and discretized as tetrahedral meshes with shared connectivity. The output is a continuum of shapes that naturally blends the input shapes, while striving to preserve the geometric character of the input. The basis of our approach relies on the fact that the space of metrics with bounded isometric and angular distortion is convex [Chien et al. 2016b]. We show that for high dimensional manifolds, the bounded distortion metrics form a positive semidefinite cone product space. Our method can be seen as a generalization of the bounded distortion interpolation technique of [Chen et al. 2013] from planar shapes immersed in R^2 to solids in R^3. The convexity of the space implies that a linear blend of the (squared) edge lengths of the input tetrahedral meshes is a simple yet powerful-and-natural choice. Linearly blending flat metrics results in a new metric which is, in general, not flat, and cannot be immersed into three-dimensional space. Nonetheless, the amount of curvature that is introduced in the process tends to be very low in practical settings. We further design an extremely robust nonconvex optimization procedure that efficiently flattens the metric. The flattening procedure strives to preserve the low distortion exhibited in the blended metric while guaranteeing the validity of the metric, resulting in a locally injective map with bounded distortion. Our method leads to volumetric interpolation with superb quality, demonstrating significant improvement over the state-of-the-art and qualitative properties which were obtained so far only in interpolating manifolds of lower dimensions.

Authors/Presenter(s): Ido Aharon, Bar-Ilan University, Israel
Renjie Chen, Max Planck Institute for Informatics, University of Science and Technology of China, China
Denis Zorin, NYU, United States of America
Ofir Weber, Bar-Ilan University, Israel