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.

Developments in the field of parametrization-based quad mesh generation on surfaces have been impactful over the past decade. In this context, an important advance has been the replacement of error-prone rounding in the generation of integer-grid maps, by robust quantization methods. In parallel, parametrization-based hex mesh generation for volumes has been advanced. In this volumetric context, however, the state-of-the-art still relies on fragile rounding, not rarely producing defective meshes, especially when targeting a coarse mesh resolution. We present a method to robustly quantize volume parametrizations, i.e., to determine guaranteed valid choices of integers for 3D integer-grid maps. Inspired by the 2D case, we base our construction on a non-conforming cell decomposition of the volume, a 3D analogue of a T-mesh. In particular, we leverage the motorcycle complex, a recent generalization of the motorcycle graph, for this purpose. Integer values are expressed in a differential manner on the edges of this complex, enabling the efficient formulation of the conditions required to strictly prevent forcing the map into degeneration. Applying our method in the context of hexahedral meshing, we demonstrate that hexahedral meshes can be generated with significantly improved flexibility.

HexMe consists of 189 tetrahedral meshes with tagged features and a workflow to generate them. The primary purpose of HexMe meshes is to enable consistent and practically meaningful evaluation of hexahedral meshing algorithms and related techniques, specifically regarding the correct meshing of specified feature points, curves, and surfaces. The tetrahedral meshes have been generated with Gmsh, starting from 63 computer-aided design (CAD) models from various databases. To highlight and label the diverse and challenging aspects of hexahedral mesh generation, the CAD models are classified into three categories: simple, nasty, and industrial. For each CAD model, we provide three kinds of tetrahedral meshes (uniform, curvature-adapted, and box-embedded). The mesh generation pipeline is defined with the help of Snakemake, a modern workflow management system, which allows us to specify a fully automated, extensible, and sustainable workflow. It is possible to download the whole dataset or select individual meshes by browsing the online catalog. The HexMe dataset is built with evolution in mind and prepared for future developments. A public GitHub repository hosts the HexMe workflow, where external contributions and future releases are possible and encouraged. We demonstrate the value of HexMe by exploring the robustness limitations of state-of-the-art frame-field-based hexahedral meshing algorithm. Only for 19 of 189 tagged tetrahedral inputs all feature entities are meshed correctly, while the average success rates are 70.9% / 48.5% / 34.6 % for feature points/curves/surfaces.

Non-linear optimization is essential to many areas of geometry processing research. However, when experimenting with different problem formulations or when prototyping new algorithms, a major practical obstacle is the need to figure out derivatives of objective functions, especially when second-order derivatives are required. Deriving and manually implementing gradients and Hessians is both time-consuming and error-prone. Automatic differentiation techniques address this problem, but can introduce a diverse set of obstacles themselves, e.g. limiting the set of supported language features, imposing restrictions on a program’s control flow, incurring a significant run time overhead, or making it hard to exploit sparsity patterns common in geometry processing. We show that for many geometric problems, in particular on meshes, the simplest form of forward-mode automatic differentiation is not only the most flexible, but also actually the most efficient choice. We introduce TinyAD: a lightweight C++ library that automatically computes gradients and Hessians, in particular of sparse problems, by differentiating small (tiny) sub-problems. Its simplicity enables easy integration; no restrictions on, e.g., looping and branching are imposed. TinyAD provides the basic ingredients to quickly implement first and second order Newton-style solvers, allowing for flexible adjustment of both problem formulations and solver details. By showcasing compact implementations of methods from parametrization, deformation, and direction field design, we demonstrate how TinyAD lowers the barrier to exploring non-linear optimization techniques. This enables not only fast prototyping of new research ideas, but also improves replicability of existing algorithms in geometry processing. TinyAD is available to the community as an open source library.

Polycube mapping is an attractive approach for the generation of all-hexahedral meshes with a fully regular interior, i.e. free of internal singular edges or vertices. It is based on determining a low distortion map between the input model and a polycube domain, which then pulls back the regular voxel grid to form a hexahedral mesh for the model. Automatically finding an appropriate polycube domain for a given model, however, is a challenging problem. Existing algorithms are either very sensitive to the embedding and orientation of the input model, restricted to only subclasses of possible domains, or depend crucially on some initialization because they rely on a non-convex optimization formulation. This can easily lead to unsatisfactory and unnecessary corners and edges in the polycube structure. We present a novel approach to the problem of finding high-quality polycube domains. It is based on an entirely intrinsic formulation as a mixed integer optimization problem, which can be tackled by solving a series of simple convex problems, each of which can be solved to the global optimum. Experiments demonstrate that our method avoids many of the undesired corners and surface irregularities common to many previous methods.

Methods from the field of computer graphics are the foundation for the representation of geological structures in the form of geological models. However, as many of these methods have been developed for other types of applications, some of the requirements for the representation of geological features may not be considered, and the capacities and limitations of different algorithms are not always evident. In this work, we therefore review surface-based geological modelling methods from both a geological and computer graphics perspective. Specifically, we investigate the use of NURBS (non-uniform rational B-splines) and subdivision surfaces, as two main parametric surface-based modelling methods, and compare the strengths and weaknesses of the two approaches. Although NURBS surfaces have been used in geological modelling, subdivision surfaces as a standard method in the animation and gaming industries have so far received little attention—even if subdivision surfaces support arbitrary topologies and watertight boundary representation, two aspects that make them an appealing choice for complex geological modelling. It is worth mentioning that watertight models are an important basis for subsequent process simulations. Many complex geological structures require a combination of smooth and sharp edges. Investigating subdivision schemes with semi-sharp creases is therefore an important part of this paper, as semi-sharp creases characterise the resistance of a mesh structure to the subdivision procedure. Moreover, non-manifold topologies, as a challenging concept in complex geological and reservoir modelling, are explored, and the subdivision surface method, which is compatible with non-manifold topology, is described. Finally, solving inverse problems by fitting the smooth surfaces to complex geological structures is investigated with a case study. The fitted surfaces are watertight, controllable with control points, and topologically similar to the main geological structure. Also, the fitted model can reduce the cost of modelling and simulation by using a reduced number of vertices in comparison with the complex geological structure.