Hex-Mesh Optimization

Contents

1 Introduction ... 1

2 Object Representation ... 2
2.1 Mesh Types ... 2
2.2 Properties in the Context of Simulation ... 3
2.3 Mesh Creation ... 3

3 Hex-Mesh Optimization ... 4
3.1 Related Work ... 4
3.2 Optimization via Edge-Cone Rectification ... 4
3.2.1 Basic Problem Definition ... 6
3.2.2 Cone Shape Optimization ... 6
3.2.3 Additional Constraints ... 8
3.2.4 Optimized Boundary Surface Preservation ... 10
3.2.5 Complete Formulation ... 11

4 Results 12
4.1 Outcome Quality ... 12
4.2 Comparison ... 13

5 Conclusion ... 15

1 Introduction

Computer driven simulations are often used to simulate certain object related effects such as force dis- tribution or surface deformation. In this context, it is crucial to choose an appropriate way of object representation. While various techniques have been developed to fulfill this task, nowadays polyhedral meshes are the discretization of choice in many simulation applications. Thereby, the quality of an object-representing polyhedral mesh has a decisive influence on the outcome of the simulation [P´e+07]. Especially when applying the finite element method in the context of simulation, it is important that the mesh consists of well-shaped elements. Even a single inverted or concave element can lead to undesired effects during simulation and may falsify any computed result [Liv+15]. When using hexahedral meshes, the quality of the mesh increases the less all hexahedra in the mesh deviate from a perfect cube. Since

initially created hexahedral meshes often contain a high amount of inverted or poorly shaped hexahedra, in most cases it is required to apply an optimization method to the generated hex-meshes in order to make them suitable for the desired simulation purpose.

In this context, Chapter 2 will introduce polyhedral meshes and their characteristics. Furthermore, polyhedral mesh related properties in the field of simulation are presented and it is shortly described how a hexahedral mesh can be created. Chapter 3 focuses on hex-mesh optimization. First, some com- monly used optimization approaches are presented followed by a detailed explanation of the optimization approach by Livesu et al. [Liv+15]. Chapter 4 then presents the results of this optimization approach and compares it to the outcome of some of the previously presented approaches. Finally, Chapter 5 will conclude the topic and sums up the most important findings.

2 Object Representation

In the field of computer graphics, object representation is one of the most discussed topics. Depending on the application scenario, different object properties are more important than others and have to be modeled in an efficient way. The most important representation types that have emerged over the years are Polygonal and Polyhedral Meshes,Point Clouds, Constructive Solid Geometry and Voxels, each of them specialized for a certain case of application.

In the area of 3D modeling and simulation, polyhedral meshes have become the most used object represen- tation approach. Because of their simplicity, it is possible to represent highly complex geometric objects which can be processed by flexible and effective algorithms that combine results from approximation theory, numerical analysis and differential geometry [Kob+00].

3 Mesh Types

These images are not included in the preview.

Figure 1: Grid Types - Structured Grid, Unstructured Grid and Hybrid Grid. The 2D representation can easily be adapted to the 3D case. (Image based on [BP00])

A polyhedral mesh is a combination of vertices, edges and faces that form the shape and the interior of a virtual 3D object [Bau75]. There are two common ways of classifying a polyhedral mesh structure:connectivity-based classification and element-based classification.

Considering polyhedral meshes as a whole, connectivity-based classification qualifies the overall struc- ture of such a mesh. In general, meshes can be separated into structured andunstructured grids but there also exist hybrid grids that contain structured and unstructured parts (Figure 1). Structured grids are defined by regular, in an ideal case orthogonal, connectivity which is highly efficient in terms of space complexity because neighboring structures can be determined implicitly based on the regular structure of the grid. In contrast, unstructured grids are characterized by irregular connectivity. Here, the local neighborhood of vertices can be arbitrarily varying which makes an implicit determination of adjacent structures difficult or impossible. On the other hand, unstructured meshes offer more complicated object representations and better mesh adaptability than structured grids. As hybrid meshes can be partially structured and unstructured, they combine the characteristics of both approaches [BP00].

In element-based classification, the basic shapes a mesh consists of are considered. Depending on the allowed dimension, there exist different commonly used element shapes. In case of two dimensions, there are triangles and quadrilaterals. Where triangles are relatively easy to create and are most common in un- structured grids, quadrilaterals are often used to form a structured grid. Typically, quadrilaterals are also excluded from being concave or inverted (see Subsection 2.2). When looking at three-dimensional shapes, the most popular elements are thetetrahedron, quadrilateral pyramid, triangular prism and hexahedron (Figure 2). The usage of these elements highly depends on the application scenario and as the faces of the three-dimensional elements are in fact 2D elements, they have similar properties. For example, the most used 3D elements in structured meshes are hexahedrons as they consist of quadrilaterals, whereas tetrahedrons normally can be found in unstructured meshes.

These images are not included in the preview.

Figure 2: 3D Mesh Types - Tetrahedron, Quadrilateral Pyramid, Triangular Prism and Hexahedron

3.1 Properties in the Context of Simulation

Beside simple object representation, polyhedral meshes and its design are a crucial component in scien- tific simulation, especially when using finite element approaches. The finite element method (FEM) is a numerical approach to solve partial differential equations and is most commonly used to simulate force distribution within an object or deformations of rigid bodies. In order to restrict the amount of calcula- tions that are necessary to simulate a certain effect, the whole problem gets subdivided into finite, simple parts, thereby limiting the number of differential equations that have to be solved [BZ02]. One way of breaking down a simulation problem is to represent objects that have to be simulated by a finite number of elements for example by using polyhedral meshes. Thereby, the outcome of a finite element simulation strongly depends on the mesh quality. One aspect that influences the accuracy of the simulation is the size of the single mesh elements. The smaller the mesh elements are and the more elements a mesh consists of, the more precise a simulation can be. However, this leads to more complex calculations. Another and by far more important aspect is the quality of the single mesh elements. Research [BA76][WGS90] has shown that simulation errors occur if the interior angle between two edges of a mesh element is very sharp or reflex. Livesu et al. [Liv+15] even state that only a single concave or inverted mesh element makes a mesh unusable for simulations. Because of that, interior angles are often restricted to lie between 30 and 120 [Che89]. These criteria are also influenced by the overall symmetry and aspect ratio of a single element and hence also affect the simulation quality [Ell14]. Another method, especially when using hexahedral meshes, computes the minimal or average scaled Jacobian and its determinant [Knu00]. The purpose of this is to detect inverted or concave elements and to estimate the degree to which a hexahedron differs from a canonical cube. Typically, the value of the Minimal Scaled Jacobian (MSJ) is negative if a mesh element is inverted and therefore not usable for simulations. Positive values can be measured for suitable mesh elements with an optimal element resulting into a value of one. Although there are a lot of efficient algorithms to automatically create tetrahedral meshes out of a given geometry [She98][Che89], tetrahedral meshes come along with the disadvantages of unstructured grids and often show sharp angles. That is why hexahedral meshes are the structure of choice in many FEM simulations.

3.2 Mesh Creation

As stated in the previous section, the quality of a given mesh structure has a high impact on the reli- ability of a finite element simulation. Therefore, it is important to carefully create polyhedral meshes

for the objects that have to be simulated. Typically, suitable hexahedral meshes (short: hex-meshes) are generated in two steps. First, an initial mesh is designed with focus on representing the shape of the corresponding object. After that, the vertex positions get modified to optimize the shape of every single element in the mesh, thus increasing the overall quality of the hex-mesh [Owe98]. Various approaches have been developed to generate an initial hex-mesh. One method is to create or use a given tetrahedral mesh and split every tetrahedron into four hexahedra. As this method only generates hexahedral ele- ments but does not deal with the overall connectivity and symmetry in the mesh, this approach is mostly used for theoretical applications. It is also possible to refine parts of a mixed mesh into a hex-mesh by merging pyramid and prism elements [Bau+14]. However, this approach most of the time only results into hex-dominant meshes with small hybrid parts left in the mesh. Kremer et al. [Kre+13] presented a method of hex-mesh creation for given concave quad surface object representations. Other approaches use octrees as a base for initial hex-mesh generation [ISS09] or base on polycubes [GSZ11]. All in all, there are a lot of methods to create an initial mesh but all approaches have in common that they do not result into perfect, high quality hex-meshes. One problem is that they do not always generate convex, structured grids. They often also do not fulfill the requirements necessary for reliable FEM simulations by showing inverse or concave elements with skewed edges or small, sharp angles. Therefore, a given or generated hex-mesh is often optimized before it is used for simulation purpose.

4 Hex-Mesh Optimization

Hex-mesh optimization uses an initial hex-mesh as input and tries to optimize its overall quality. This chapter will roughly introduce current optimization approaches followed by a detailed description of the hex-mesh optimization approach by Livesu et al. [Liv+15].

4.1 Related Work

Typically, the goal of an optimization method is to improve the quality of all elements a mesh consists of while preserving their connectivity and the boundary surface of the input mesh. Often, this is performed by first detecting and correcting inverted elements and after that optimizing the average quality of all mesh elements. As tetrahedral meshes are easier to handle, there exist various methods in refining such meshes. However, these methods can not be applied to hex-meshes as is. The approach by Aigerman et al. [AL13] provides an inversion-free tetrahedral mesh given an input mesh with several inverted elements. One attempt to map this approach to hex-meshes is to represent a hexahedron by 8 overlapping tetrahedra and to apply the optimization afterwards. Nevertheless there are cases in which the outcome is not perfect. Other approaches only work for specialized input types like hybrid meshes [VH14], grid-based meshes [SZM12] or inversion-free but unoptimized meshes [Knu03] and therefore are not suitable for general application scenarios. Approaches that work directly on hex-meshes often make use of the Gauss-Seidel method to iteratively untangle a given mesh and correct as many inverted elements as possible [Bre+03] [RG+14]. The method of Marechal [Mar09] also works directly on hex-meshes and computes the closest optimal hex cube for each hex element. Afterwards, the vertices of every element are moved to relatively approximate all optimal cubes throughout the whole mesh. The drawback of this approach is that the surface of the mesh gets strongly deformed depending on the approximation accuracy. To sum up, all approaches can provide high quality results but most of them only work great for certain input types or in very specialized application scenarios. In the following, the approach of Livesu et al. [Liv+15] will be presented in more detail. It provides outputs with better average and worst element quality than other approaches while closely preserving the input surface geometry. It is also able to generate an inversion free outcome when other methods fail to do so.