Search

In this article, we provide a detailed survey of techniques for hexahedral mesh generation. We cover the whole spectrum of alternative approaches to mesh generation, as well as post processing algorithms for connectivity editing and mesh optimization. For each technique, we highlight capabilities and limitations, also pointing out the associated unsolved challenges. Recent relaxed approaches, aiming to generate not pure-hex but hex-dominant meshes, are also discussed. The required background, pertaining to geometrical as well as combinatorial aspects, is introduced along the way.

The so-called motorcycle graph has been employed in recent years for various purposes in the context of structured and aligned block decomposition of 2D shapes and 2-manifold surfaces. Applications are in the fields of surface parametrization, spline space construction, semi-structured quad mesh generation, or geometry data compression. We describe a generalization of this motorcycle graph concept to the three-dimensional volumetric setting. Through careful extensions aware of topological intricacies of this higher-dimensional setting, we are able to guarantee important block decomposition properties also in this case. We describe algorithms for the construction of this 3D motorcycle complex on the basis of either hexahedral meshes or seamless volumetric parametrizations. Its utility is illustrated on examples in hexahedral mesh generation and volumetric T-spline construction.

We describe an efficient algorithm to compute a conformally equivalent metric for a discrete surface, possibly with boundary, exhibiting prescribed Gaussian curvature at all interior vertices and prescribed geodesic curvature along the boundary. Our construction is based on the theory developed in [Gu et al. 2018; Springborn 2020], and in particular relies on results on hyperbolic Delaunay triangulations. Generality is achieved by considering the surface's intrinsic triangulation as a degree of freedom, and particular attention is paid to the proper treatment of surface boundaries. While via a double cover approach the boundary case can be reduced to the closed case quite naturally, the implied symmetry of the setting causes additional challenges related to stable Delaunay-critical configurations that we address explicitly in this work.

Seamless global parametrization of surfaces is a key operation in geometry processing, e.g. for high-quality quad mesh generation. A common approach is to prescribe the parametric domain structure, in particular the locations of parametrization singularities (cones), and solve a non-convex optimization problem minimizing a distortion measure, with local injectivity imposed through either constraints or barrier terms. In both cases, an initial valid parametrization is essential to serve as feasible starting point for obtaining an optimized solution. While convexified versions of the constraints eliminate this initialization requirement, they narrow the range of solutions, causing some problem instances that actually do have a solution to become infeasible. We demonstrate that for arbitrary given sets of topologically admissible parametric cones with prescribed curvature, a global seamless parametrization always exists (with the exception of one well-known case). Importantly, our proof is constructive and directly leads to a general algorithm for computing such parametrizations. Most distinctively, this algorithm is bootstrapped with a convex optimization problem (solving for a conformal map), in tandem with a simple linear equation system (determining a seamless modification of this map). This initial map can then serve as valid starting point and be optimized with respect to application specific distortion measures using existing injectivity preserving methods., Comment: 17 pages, 21 figures

The question of representation of 3D geometry is of vital importance when it comes to leveraging the recent advances in the field of machine learning for geometry processing tasks. For common unstructured surface meshes state-of-the-art methods rely on patch-based or mapping-based techniques that introduce resampling operations in order to encode neighborhood information in a structured and regular manner. We investigate whether such resampling can be avoided, and propose a simple and direct encoding approach. It does not only increase processing efficiency due to its simplicity - its direct nature also avoids any loss in data fidelity. To evaluate the proposed method, we perform a number of experiments in the challenging domain of intrinsic, non-rigid shape correspondence estimation. In comparisons to current methods we observe that our approach is able to achieve highly competitive results., Comment: Presented at the ECCV workshop on Geometry meets Deep Learning

An algorithm for the computation of global discrete conformal parametrizations with prescribed global holonomy signatures for triangle meshes was recently described in [Campen and Zorin 2017]. In this paper we provide a detailed analysis of convergence and correctness of this algorithm. We generalize and extend ideas of [Springborn et al. 2008] to show a connection of the algorithm to Newton's algorithm applied to solving the system of constraints on angles in the parametric domain, and demonstrate that this system can be obtained as a gradient of a convex energy.