Mesh Generation & Optimization

Engineering applications and numerical simulations require a faithful approximation of the involved geometric models. In the case of technical data sets, sharp or highly curved edges and corners, so-called geometric features, carry crucial shape information and therefore have to be represented accurately. In order to minimize geometric aliasing the mesh tessellation needs to be aligned to the feature lines, i.e., to the principal curvature directions of the underlying geometry. To this end, we extend the well known Marching Cubes algorithm in order to detect and reconstruct sharp edges or corners when extracting an isosurface from a volumetric data set [3]. Figures 1 compares the standard and the extended Marching Cubes for a milling simulation, implemented by constructive solid geometry (CSG). In [2] a resampling strategy for anisotropically curved feature and blend regions is derived, with the goal to minimize geometric aliasing artifacts (Figure 2).

**Figure 1:** A milling simulation is performed on a volumetric representation by Boolean substraction of the milling tool's envelope, followed by an isosurface extraction to get the resulting object's surface. The left image shows the surface extracted by the standard Marching Cubes algorithm, the right image shows our extended Marching Cubes. The sharp ridges are better reconstructed due to the clearly reduced geometric aliasing.

**Figure 2:** Feature-sensitive anisotropic resampling applied to a high resolution car model, which is to be used for CFD simulation. The geometric aliasing in the vicinity of the feature regions of the input model (top left) can cause numerical instabilities. In the remeshed feature regions around the driver window the aliasing is almost completely removed (center, top right).

The robustness of numerical simulations strongly depends on the shape of triangles or tetrahedra in the surface or volume tessellation. While equilateral triangles allow for robust simulations, the extremely small and large angles in degenerate triangles prevent stable computations of areas or gradients. One can either try to remove degenerate triangles only (Figure 3) [1], or apply isotropic remeshing [4,6] for globally optimizing the tessellation using numerically robust equilateral triangles (Figures 4, 5). The latter method is fast enough for real-time remeshing in interactive modeling applications [6].

**Figure 3:** Degeneracy removal for a typical mesh generated by a CAD tesselation unit.

**Figure 4:** Isotropic remeshing preserves the surface geometry while optimizing the tessellation perferring close-to-equilateral triangles. Adaptive remeshing furthermore adjusts the vertex density to the curvature of the underlying surface geometry, thereby spending more triangles in regions of geometric details.

**Figure 5:** Using univariate curve resampling for sharp features lines and adjusting the local remeshing rules accordingly allows geometric features in technical data sets to be preserved faithfully.

Classical simulation methods typically discretize the simulation domain into triangular or quadrilateral elements. In contrast, polygonal finite element methods allow for arbitrary polygonal elements. A widespread approach to mesh generation for polygonal finite elements are centroidal Voronoi tessellations (CVTs). While CVTs contain mostly well-shaped elements, they may also contain a number of ill-conditioned elements with short edges. These short edges are a major reason for numerical instabilities. In [5] we present a method to effectively remove short edges from the Voronoi diagram by minimizing a carefully chosen energy functional (Figure 6).

**Figure 6:** Minimizing a carefully chosen energy functional eliminates short edges from the Voronoi diagram. Elements incident to a short edge are shown in red.

[1]	A Robust Procedure to Eliminate Degenerate Faces from Triangle Meshes Mario Botsch, Leif Kobbelt Vision, Modeling & Visualization 2001, pp. 283-289. Paper
[2]	Resampling Feature and Blend Regions in Polygonal Meshes for Surface Anti-Aliasing Mario Botsch, Leif Kobbelt Computer Graphics Forum 20(3), Proc. Eurographics 2001, pp. 402-410. Paper
[3]	Feature Sensitive Surface Extraction from Volume Data Leif Kobbelt, Mario Botsch, Ulrich Schwanecke, Hans-Peter Seidel SIGGRAPH 2001, pp. 57-66. Paper Code
[4]	A Remeshing Approach to Multiresolution Modeling Mario Botsch, Leif Kobbelt Eurographics Symp. on Geometry Processing 2004, pp. 189-196. Paper Presentation
[5]	Optimizing Voronoi Diagrams for Polygonal Finite Element Computations Daniel Sieger, Pierre Alliez, Mario Botsch Proceedings of the 19th International Meshing Roundtable, 2010, pp. 335-350. Paper
[6]	Adaptive Remeshing for Real-Time Mesh Deformation Marion Dunyach, David Vanderhaeghe, Loïc Barthe, Mario Botsch Proceedings of Eurographics Short Papers, 2013 Paper Video

Mesh Generation & Optimization

Related Publications