The commonly chosen object representations in computer based simulation applications are hexahedral meshes. As their quality strongly influences the outcome of a simulation, hex-mesh optimization is an important aspect of creating a suitable input mesh for such simulations.

Practical hex-mesh optimization via edge-cone rectification is an optimization approach that converts the direct hexahedra optimization problem to an easier to solve scenario. Comparisons have shown that this approach is able to successfully generate high-quality hex-meshes in cases where other approaches fail.

## 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** *and*unstructured** *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 the*tetrahedron*, *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.