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).
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].
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).
Related Publications
[1] |
A Robust Procedure to Eliminate Degenerate Faces from Triangle Meshes
Vision, Modeling & Visualization 2001, pp. 283-289.
|
|
[2] |
Resampling Feature and Blend Regions in Polygonal Meshes for Surface Anti-Aliasing
Computer Graphics Forum 20(3), Proc. Eurographics 2001, pp. 402-410.
|
|
[3] |
Feature Sensitive Surface Extraction from Volume Data
ACM SIGGRAPH 2001, pp. 57-66.
|
|
[4] |
A Remeshing Approach to Multiresolution Modeling
Eurographics Symp. on Geometry Processing 2004, pp. 189-196.
|
|
[5] |
Optimizing Voronoi Diagrams for Polygonal Finite Element Computations
Proceedings of the 19th International Meshing Roundtable, 2010, pp. 335-350.
|
|
[6] |
Adaptive Remeshing for Real-Time Mesh Deformation
Proceedings of Eurographics Short Papers, 2013
|