Untangling of 2D meshes in ALE simulations.
A procedure is presented to untangle unstructured 2D meshes containing inverted elements by node repositioning. The inverted elements may result from node movement in Arbitrary Lagrangian Eulerian (ALE) simulations of continuum mechanics problems with large shear deformation such as fluid flow and metal forming. Meshes with inverted elements may also be created due to the limitations of mesh generation algorithms particularly for nonsimplicial mesh generation. The untangling procedure uses a combination of direct node placement based on geometric computation of the feasible set, and node repositioning driven by numerical optimization of an objective function that achieves its minimum on a valid mesh. It is shown that a combination of the feasible set, based method and the optimization method achieves the best results in untangling complex 2D meshes. Preliminary results are also presented for untangling of 3D unstructured meshes by the same approach.
Introduction
Arbitrary Lagrangian-Eulerian or ALE methods are a popular class of methods
for simulating continuum mechanics problems with large shear deformation
such as
uid
ow and metal forming [1,2]. ALE methods consist of a
Lagrangian step in which the mesh nodes move according to the
ow of the
material, a rezone step in which the mesh is modied to improve its quality
and the remapping step in which the solution is transferred from the old mesh
to the new, improved mesh. In [3{5], methods were described to improve the
quality of the mesh while keeping it close to the original mesh. However, in
order to improve the meshes by the methods described in [3{5], all elements of
the starting mesh must be valid or non-inverted. Therefore, if the Lagrangian
step of an ALE simulation causes the mesh to become tangled (i.e., it has
some elements that become inverted), the mesh must be untangled before the
mesh improvement procedures are applied to it.
The need for untangling meshes also exists when a mesh generation procedure
is unable to create all valid elements in a mesh. This situation may be encountered
in the generation of all hexahedral meshes and general polyhedral
meshes where there is no guaranteed method of directly generating a valid
mesh [6]. It may also be encountered in advancing front based mesh generation
of tetrahedral and hexahedral meshes [7{9] where it is possible to generate
small cavities that cannot be lled with all positive volume elements. In these
cases, it is very useful to have a tool that can untangle the mesh after the initial
generation assuming that the right mesh connectivity has been generated.
Several researchers have recently begun focusing on the problem of untangling
unstructured meshes by node repositioning [10{13]. Freitag and Plassmann
[11,14] untangle meshes by optimization of a local function based on maximizing
the minimum element area at each mesh vertex. Knupp [12] performs
a global optimization of the dierence between the absolute and signed values
of element volumes in order to untangle the mesh. Kovalev et.al. [13] visit
each vertex connected to at least one invalid element and reposition the vertex
directly to a point in its feasible set (or \kernel") to make all connected
elements valid. They dene the feasible set of a vertex to be the set of all
locations of the vertex for which all elements connected to the vertex will be
valid. The new location of the vertex in the feasible set is found by a clever use
of the simplex method to nd three corners of the feasible set and taking their
mean. Most of these procedures are capable of successfully untangling many
tangled mesh congurations. However, there are conditions under which they
may fail to untangle the mesh or they may not be able to produce elements
with su-cient positive volume so as to provide a good starting point for mesh
improvement procedures.
In this paper, a method is presented for untangling unstructured 2D meshes
containing triangles and quadrilaterals. The method uses a multi-step approach
based on a combination of relocating vertices to positions in their
respective feasible sets and on minimizing a function to untangle the mesh
elements. The untangling procedures only reposition nodes to untangle the
mesh and do not perform any topological modications since solution transfer
between meshes with dierent connectivity is complex and expensive. Also in
the interest of accurate solution transfer, the procedures endeavor to keep the
mesh as close as possible to the original mesh.
The methods described here focus only on ensuring that all elements of the
mesh meet at least bare minimum validity criteria as dened by the simulation
procedures that will use them. However, the methods can easily be combined
with separate procedures for improving the quality of the untangled mesh like
the ones described in [4,5].
The rest of the paper is organized as follows. The next section discusses the
denition of element validity and the denition of the feasible set for a vertex.
Section 3 describes the untangling of a mesh by the feasible set method and
untangling by optimization of an objective function is discussed in Section 4.
Section 5 describes the multi-step untangling procedure that has achieved a
greater success in untangling meshes than each of the two untangling methods
by themselves. Finally, several simple and complex examples of mesh untangling
and mesh optimization [4,5] are presented in Section 6 followed by
conclusions.
Denitions
In this study, an element is considered valid if each corner of the element is
considered valid. An element corner is valid if the Jacobian determinant of its
mapping to a right angle corner with unit sides is positive. This requirement
is more conservative than that required by some numerical methods [15] in
which the element or its \subcells" must only have a decomposition into any
one set of simplices (triangles and tetrahedra) with all positive volumes (See

Figure

1). However, it does not explicitly account for the requirements of
other methods such as having positive Jacobian determinants everywhere or
at quadrature points.
Given the denition of element validity, the feasible set for a vertex can
be dened as the set of all positions of the vertex for which each connected
element is valid at the corners aected by the position of the vertex. In other
words, if a vertex is in its feasible set, then each connected element is valid at
the vertex and at the adjacent (edge-connected) neighbors of the vertex.
(b)
(a)
(d)
A
(c) (e)
A
O
F
G
A
O
F
G
A
A
A
Fig. 1. Valid and Invalid Quadrilateral Elements: (a),(b) Valid quads with positive
Jacobian everywhere (c) Quad with valid decomposition into positive area triangles
ABC and ACD but negative Jacobian at reentrant corner, C (d) Quad with no
valid decomposition into positive area triangles (e) Quad decomposition into valid
subcells AEOH, BFOE, FCGO, GDHO but negative Jacobian at C (f) Quad with
invalid subcells
The feasible set for a vertex connected to a single triangle is a half-space as
shown in the 2D example in Figure 2a assuming a ccw ordering of vertices
of the triangle. For a vertex connected to a single quadrilateral or general
polygonal element, the feasible set of a vertex is dened by the intersection
of three half-spaces as illustrated in Figure 2b. This is because the position of
the vertex in
uences the Jacobian at the vertex V 1 and its two edge connected
neighbors, V 2 and V 3 in the element. In the gure, if vertex past line
AA' in the opposite direction of the arrows, the Jacobian at V 1 and the area
of triangle become negative. If it moves past line BB', the Jacobian
at V 2 and the area of triangle negative and if it moves past
line CC', the Jacobian at V 3 and area of triangle
Figure 2c shows the feasible set for a vertex interior to a patch of elements.
From the denition of the feasible set, it is clear that the feasible set is a convex
polygon in 2D while it is a convex polyhedron in 3D. Note that the feasible
set for a vertex can be empty depending on the geometry and conguration of
the elements connected to the vertex. This implies that given the positions of
the boundary vertices of the patch, there is no location for the vertex which
will simultaneously make all the elements valid. Such an example is shown in

Figure

3 along with congurations where the feasible set is a line and a point.
Feasible Set
Element
Vertex
Half-plane
boundary
Direction of
half-plane
(a) (b)
(c)
A
A'
A
A'
C'
Fig. 2. Illustration of Feasible Sets (a) Feasible set for vertex connected to single
element (b) Feasible set for vertex connected to a pentagon (c) Polygonal feasible
set for vertex connected to patch of triangular and quadrilateral elements.
3 Untangling by Finding the Feasible Set
The denition of a feasible set given above leads to a natural method of untangling
meshes in which the feasible set of a vertex is determined and the
vertex is positioned inside it. This is referred to here as the feasible set method.
In this approach each vertex of the mesh is visited and its connected elements
examined to see if any of them are invalid. If an invalid element exists among
Feasible set
(line)
Feasible set
Fig. 3. Degenerate and Null Feasible Sets: (a) Feasible set is a line (b) Feasible set
is a point (c) Null or empty feasible set.
the elements connected to the vertex, the feasible set of the vertex is computed
and the vertex is placed in center of the feasible set. The method loops over
the mesh until all elements are valid or no invalid element can be xed.
The feasible set of a vertex can be found by computing the intersection of
half-spaces representing the feasible region of the vertex with respect to each
element. In 2D, this is accomplished by the intersection of pairs of lines demarcating
the feasibility half-planes. In this work, the feasible set is found by
the chasing algorithm described by O'Rourke [16] and has been found to work
well on a number of test cases. In Figure 4, an example of mesh untangling by
the intersection based feasible set method is illustrated step by step. In the
gure, the invalid quadrilaterals are shown shaded and nodes connected to at
least one invalid quadrilateral are shown in black.
While the intersection based computation of the feasible set works well in
2D, nding the feasible set polyhedron by intersection of half-spaces is impractically
complex in 3D. Therefore, an alternate method for positioning the
vertex inside the feasible set is implemented based on the simplex method
as described in [13]. In [13] the idea is proposed that the boundary lines of
the half-planes forming the feasible set in 2D can be interpreted as inequality
constraints on the minimization of an arbitrary function. If the function is a
linear function then its minimum must occur at the intersection of two of these
inequality constraints or in other words the corner of the feasible set polygon.
Therefore, the corners of the feasible set polygon can be found by minimizing
dierent linear functions along with the appropriate inequality constraints
using the simplex method [17,18].
This idea is further simplied by recognizing that for untangling, it is su-cient
(c) (d)
Fig. 4. Untangling of mesh by feasible set method with node placement at the center
of the feasible set (a) Initial mesh (b),(c) Intermediate meshes (d) Final mesh. The
shaded quadrilaterals indicate invalid elements and vertices represented in black are
connected to at least one invalid quadrilateral.
to nd any one position for the vertex inside its feasible set to make all connected
elements valid. This implies that it is unnecessary to nd all corners of
the feasible set polygon. Therefore, for untangling a patch of elements in 2D,
it can be inferred that it is su-cient to nd three distinct corners of the feasible
set polygon and reposition the vertex to the center of the triangle formed
by these corners. Therefore, the procedure minimizes simple linear functions
y to nd three distinct corners of the feasible set polygon.
The vertex is then repositioned to the center of the triangle formed by these
corners. If only two distinct corners can be found, then the feasible set is a
line connecting the two and the vertex is repositioned to the mid-point of the
line. If only one distinct corner can be found, the feasible set is a point and
the vertex is repositioned to this point. Note that in the case when the feasible
set is a line or a point, one or more elements connected to the vertex will be
of zero area.
The feasible set approach to untangling is very useful because it is a direct way
of xing inverted elements aecting only those nodes connected to invalid ele-
ments. This characteristic can be useful for accurate solution transfer in ALE
methods from the old mesh to the new, untangled mesh. Also, if the feasible
set is not degenerate, xing the mesh by this method results in elements that
have substantial volume rather than near zero volume. However, the short-coming
of this approach is that some elements cannot be xed because the
feasible set associated with each of their vertices is empty.
Optimization Approach to Untangling
Several researchers have proposed the use of numerical optimization for untangling
meshes. In this approach an appropriate objective function is minimized
so as to make all the invalid elements valid. Freitag and Plassmann [11] attempt
to untangle meshes by minimizing a local function at each mesh vertex.
The local function at each vertex is taken to be the minimum volume of all
connected elements. Knupp [12] proposed optimization of a global objective
function based on the dierence between signed volumes of elements and their
corresponding absolute values. Thus, the objective function has a contribution
from an element only if it has a negative area. If the area of the i'th element
in a mesh is  i , then the function to be minimized is
(j
Minimization of this function can only bring elements to a zero area (volume)
state which is still considered unusable in numerical simulations. Therefore,
Knupp suggested the addition of a user controlled parameter  to the function,
modifying it to be
(j  i
The role of  is to force the function to reach a minimum when the elements
have a small positive volume instead of zero volume. However, as discussed
later, the proper selection of  can be tricky. The behavior of the objective
(a) (b) (c)
Fig. 5. Objective function behavior with respect to area/volume  of one element
(a) Linear function without  (b) Linear function with  (c) Quadratic function
with
function for one element without and with  is shown in Figures 5a and b
respectively.
The objective function in Eq. 2 is non-smooth due to the presence of an absolute
value term in a linear form and minimization of such functions requires
special and expensive methods of non-linear optimization. If a gradient based
method is used, it must be modied to account for the fact that the gradient
of the objective function is discontinuous. This can be done by interrupting
a line search if valid elements become invalid or vice versa thereby causing a
jump in the gradient. At this point the gradient can be reevaluated and the
optimization continued.
To overcome the above optimization issues, the objective function proposed
by Knupp in [12] has been modied in this work so that it is quadratic and
smooth as shown for one element in Figure 5c. Since the objective function
for one element is smooth and convex, it is expected that the global objective
function formed by combining such functions for all elements of the mesh
(shown in Eq. 3) is also smooth and convex.
(j  i
This smooth function can then be minimized using a standard numerical optimization
method for smooth functions such as the conjugate gradient method
[17,18]. It has been found in practice that minimization of the quadratic form
of the objective function untangles the mesh more reliably than the linear
form.
To illustrate the untangling of meshes by numerical optimization, some 1D
cases of mesh untangling are discussed. In the rst example consider a 1D
Fig. 6. (a) Tangled 1D mesh (b) One possible untangled mesh conguration
mesh with 4 points, x 1 , x 2 , x 3 and x 4 , of which x 1 and x 4 are xed boundary
points, and x 2 and x 3 are interior points as shown in Figure 6. To make
visualization of the mesh tangling easier, valid elements are shown with their
nodes on a single line or level while an invalid element is shown with one
of its nodes on the next higher level. Going from left to right, element 1 is
valid are shown on the same level.
Element 2 is invalid and therefore, it is displayed as going from x 2 to x 3 at
the next upper level. Element 3 is valid and so its vertices x 3 and x 4 are at
the upper level. Note that the mesh shown in the gure cannot be xed by
the feasible set approach described earlier, since x 3 < x 1 making the feasible
set of x 2 empty and the x 2 > x 4 making the feasible set of x 3 empty.
The objective function formed from this mesh is a function of two variables
and can be readily visualized. Figures 7a and b show the linear and quadratic
objective functions respectively for this mesh. The interior of the central triangle
represents the portion of the x space in which the mesh is valid, i.e.,
for all 4. The paths taken by the optimization from dierent
starting points on the gure (i.e. dierent tangled mesh congurations) are
also shown in the gures. The mesh conguration shown in Figure 6 is indicated
as point P 1 in Figures 7a,b. The optimization is performed with a nite
but small value for . It can be seen that the nal valid conguration of the
mesh depends on the starting invalid conguration of the mesh since the solution
is non-unique. Also, the optimization procedure gets stuck while using
the linear objective function (Eq. 2) due to the presence of discontinuities but
successfully untangles the mesh using the quadratic function (see point P 2).
The second example illustrates the possible non-local eect of the optimization
approach on the mesh. The example chosen is a 1D example with 11 points
out of which one point outside the domain as shown in Figure 8b.
The placement of this point makes the element between x 6 and x 7 invalid.
The locations of the mesh vertices and the various congurations of the mesh
as the optimization procedure untangles the mesh are shown in Figure 8a,b.
Fig. 7. Contour plots of objective functions for mesh untangling on which paths
followed by the mesh points x 2 and x 3 from various starting congurations have
been superimposed (a) Linear objective function
objective function
The optimization uses a  of 0.2 for the untangling. It can be seen that the
optimization procedure moves nodes x 6 , x 7 , x 8 , x 9 and x 10 around to make
the mesh untangled. In the process, several elements rst become invalid and
then return to a valid state. In contrast, the feasible set approach could have
xed this mesh by simply placing x 6 in between x 5 and x 7 in the initial mesh.
In practice, it is uncommon to encounter meshes entangled in such extreme
ways and therefore, the optimization procedure usually only aects a small
number of nodes in the local neighborhood. Still, the approach adopted here
is to x as much of the mesh as possible with the feasible set approach before
using optimization to untangle meshes so that fewer nodes are perturbed in
the process.
The optimization procedure for untangling 2D meshes is similar to the 1D
meshes. For e-ciency, the optimization procedure for 2D meshes is performed
as a series of local iterations over the mesh vertices that minimize the global
objective function instead of a simultaneous movement of all mesh nodes. It
is important to note that at each local iteration at a vertex, all terms of the
global function which are aected by the movement of the vertex are grouped
into a local objective function which is minimized. For simplex elements, this
just means that the area/volume of the elements connected to the vertex
are involved in the local function. For more complex element types the local
function includes the cross product (triple product in 3D) of the edge vectors
in each connected element computed at the vertex itself and its edge connected
neighbors. Computing the local objective function this way ensures that global
objective function is still minimized at each local iteration.
Iteration
No.
Node position
(a)
(b)
Fig. 8. Optimization based untangling of 1D mesh with one node outside the domain.
(a) Path followed by the mesh nodes as the optimization progresses (from bottom
to top) (b) Mesh conguration at key stages in the optimization.
The optimization of the global function at interior vertices is preceded by a
loop over the boundary vertices of the mesh with the purpose of untangling
any invalid elements connected to the boundary. The objective function at
any boundary vertex is evaluated as it is for an interior vertex. However, the
optimization itself is performed with respect to a local parametrization of
the mesh vertex with respect to the boundary mesh edges it is connected to
[5]. This ensures that boundary mesh vertex remains on the original discrete
boundary during its movement.

Figure

9 shows example of the mesh shown in Figure 4, untangled by the optimization
procedure. Figure 9a shows the mesh optimized using the quadratic
objective function without the use of  or  = 0. The procedure untangles the
mesh but because  is zero, some of the valid elements are barely valid. The
barely valid elements and the interior vertices connected to these elements are
shaded in the gure. Figure 9b shows the same optimization but with a nite
, which is calculated as 10% of the problem size (diagonal of the bounding
box) normalized by the number of elements in either the x or y directions and
has the value of 0.106. As seen from the gure, the mesh is better in this case
since all the elements are positively valid.
(a) (b)
Fig. 9. Invalid mesh of Figure 4 optimized using optimization with quadratic objective
function (a) Without  (barely valid elements shown shaded) (b) With
of bounding box diagonal normalized by number of elements in x or y
directions
In using the optimization procedure for untangling meshes, the choice of
must be made carefully. Without  (i.e., 0:0), the optimization procedure
can only make all the elements valid in the sense that the volume of every
element is positive or at least zero. However, zero volume elements are unacceptable
for many numerical procedures and improvement of meshes with
zero volume elements can be di-cult or impossible. Therefore, to force the
untangled mesh to have all positive volume elements, the optimization procedure
must use  > 0 in the objective function. On the other hand, increasing
indiscriminately can also be quite detrimental, since the objective function
minimum can become non-zero and end up outside the feasible region for the
patch. This lack of a solution implies that for the given boundary congura-
tion it is not possible for all elements to achieve a volume equal to or greater
than . This undesirable eect of increasing  is illustrated in Figure 11 using
the mesh patch shown in Figure 10. Therefore, the approach adopted here
is to set  to the minimum acceptable area or volume of the elements with
respect to the mesh optimization procedures that will subsequently improve
Fig. 10. Mesh patch used to illustrate the eect of increasing  on untangling by
optimization. Dotted triangle shows feasible region for vertex V.
Fig. 11. Eect of increasing  on the minimum of the function
for a particular mesh patch. The solid triangle in the interior indicates the feasible
set and the dotted region indicates the minimum of the function which can be
outside the feasible set for a large .
the mesh.
5 Three-step Procedure for Mesh Untangling
In the previous sections, it was seen that the feasible set approach had a local
eect on the mesh but could not always x the mesh. On the other hand, the
optimization approach, usually xed the mesh by making all elements non-negative
but could aect a larger number of nodes and resulted in barely valid
elements. Therefore, the procedures have been combined here into a 3-step
procedure for maximizing the possibility of untangling the mesh with minimal
impact on the mesh.
The rst step of the procedure performs untangling by the feasible set method
so as to x as many elements as possible with minimal impact to the valid
part of the mesh.
The second step of the procedure performs a minimization of the quadratic
objective function described earlier in order to x any remaining invalid ele-
ments. The optimization procedure rst performs a local or vertex-by-vertex
optimization loop over the boundary vertices in order to try and x as many
elements as possible by their movement. The movement of the boundary vertices
is constrained to the original discrete boundary by a local parameterization
technique [5]. This is followed by local optimization loop over all interior
vertices connected to invalid elements.
The third step of the procedure performs another round of untangling on
barely valid elements by the feasible set approach to increase their volume.
This step requires redenition of the feasible set boundaries to account for
the desired element volumes. Once this is done, the mesh is usually suitable
for use as input to a mesh quality improvement procedure such as the one
described in [4,5].
The eect of the 3-step procedure is illustrated rst with a 1D example as
shown in Figure 12. In the rst step, the feasible set approach is able to x
element x 4 x 5 by moving x 5 to the middle of x 4 and x 6 . However, it cannot
x element x 8 x 9 because the feasible set for both x 8 and x 9 is empty. In the
second step, the optimization method xes all the elements but nodes x 8 ,x 9
are too close to each other. In the third step, the feasible set method
achieves a better distribution of the nodes by placing nodes connected to the
barely valid elements, x 8 x 9 and x 9 x 10 in the middle of their respective feasible
sets.
6 Results
The rst example shown in Figure 13 illustrates the untangling of a mesh
arising from a Rayleigh-Taylor simulation. The mesh is made invalid during
the Lagrangian step of an ALE simulation of the problem and must be xed
before the simulation can proceed. Figure 13a shows a part of the overall domain

Figure

13b shows the tangled portion of the mesh (with squares marking
nodes connected to invalid elements). Figure 13c shows the untangled mesh
corresponding to the tangled meshes shown in Figures 13a,b. The stages of
Feasible Set
Method
Feasible Set
Method
Optimization
Fig. 12. Three step procedure involving feasible set method and optimization for
xing 1D mesh
untangling of this mesh are illustrated further in Figure 14. Figure 14a shows a
zoom-in of the tangled portion of the original mesh. Figure 14b shows the mesh
after the rst untangling step by the feasible set method which is unable to x
all the elements. Figure 14c shows the mesh after untangling by optimization
during which all elements were made at least barely valid. Figure 14d shows the
mesh after the second round of untangling by the feasible set method during
which all elements were brought to a positive volume state. Finally, Figure 14e
shows the mesh after improvement by the Reference Jacobian Matrix based
optimization procedure [4,5]. This type of mesh optimization procedure, developed
for ALE simulations, improves mesh quality while keeping the mesh
close to the original conguration as can be seen by comparing Figures 14d,e.
The next example shows the untangling of a structured mesh, called the
\horseshoe" mesh shown in Figure 15b obtained by simple Laplacian smoothing
of the mesh shown in Figure 15a [19]. The untangled mesh after the 3-stage
untangling procedure is shown in Figure 15c. Finally, Figure 15d shows the
untangled mesh improved by the condition number based optimization procedure
[4,5] which improves the condition numbers of all the elements as much
as possible.

Figure

presents the example of untangling a mesh of the state of Texas
[20]. An originally valid mesh shown in Figure 16a was tangled by a random
perturbation of a subset of the interior vertices to result in the mesh shown
in

Figure

16b. The maximum perturbation was 20% of the domain size. This
mesh was then successfully untangled using the 3-step procedure to give the
(a) (b) (c)0.350.450.550.650 0.04 0.08 0.12 0.160.460.50.1 0.11 0.12 0.13 0.140.460.50.1 0.11 0.12 0.13 0.14
Fig. 13. Untangling of Lagrangian mesh from Rayleigh-Taylor Simulation (a) Part
of original tangled mesh (b) Zoom-in of tangled mesh (nodes shown by a square are
connected to at least one invalid element) (c) Zoom-in of untangled mesh
mesh shown in Figure 16c. For this example, the feasible set method alone left
behind 17 patches with negative area triangles and the optimization method
alone left behind 6 zero area triangles. The value of  was zero for the optimization
step. The result of condition number based mesh optimization on
the untangled mesh is presented in Figure 16d to illustrate that good quality
meshes can be obtained when the untangling procedure is combined with
mesh improvement procedures.
Finally, a untangling of a tetrahedral mesh is presented in Figure 17 to illustrate
that the principles presented in this paper can be extended easily to 3D.
The original 3D mesh is shown in Figure 17a. The tangled 3D mesh obtained
by perturbing the interior nodes is shown in Figure 17b and the untangled
mesh is shown in Figure 17c. The minimum and maximum element volumes
before untangling were -0.194 and 0.475. The minimum and maximum volumes
after the mesh was untangled were 1.39E-07 and 0.242. Therefore, the
untangled mesh is suitable for input to a mesh optimization procedure for
improving mesh quality.
Conclusions
A multi-step method for successful untangling of unstructured 2D meshes has
been presented in this paper. The method uses a combination of the feasible
set method and optimization method to achieve the greatest degree of success
in untangling the mesh while keeping the mesh close to the original mesh as
(a) (b)
(d)
Fig. 14. Steps of untangling Rayleigh-Taylor simulation mesh (a) Zoom-in of original
mesh (nodes connected to invalid elements shown as squares) (b) Mesh after feasible
set approach, some elements remain with less than a minimum volume (c) Mesh after
optimization, some elements remain with zero volume (d) Mesh after second pass of
the feasible set approach, all elements have volume greater than required minimum
improved with Reference Jacobian Matrix based optimization procedure
[4,5] which seeks to improve the mesh but keep it close to the original mesh
required for remapping in ALE simulations. The methods have shown a high
degree of success in untangling complex 2D meshes. The formulation of the
procedures allows easy extension to 3D problems and preliminary results are
promising. Work is in progress to apply the untangling procedure for general
polygonal meshes.
(d)
(c)
(b)
Fig. 15. (a) Valid mesh of horseshoe (b) Mesh tangled by simple Laplacian smoothing
(c) Mesh untangled by 3-step untangling procedure (d) Mesh after improvement by
condition number based optimization [4,5] which improves the condition numbers
of all elements as much as possible

Acknowledgments

The work of the authors was performed at Los Alamos National Laboratory
operated by the University of California for the US Department of Energy
under contract W-7405-ENG-36. Los Alamos National Laboratory strongly
supports academic freedom and a researcher's right to publish; as an institu-
tion, however, the Laboratory does not endorse the viewpoint of a publication
or guarantee its technical correctness.
The work of P. Vachal was also supported in part by the Czech Grant Agency
grant 201/00/0586.
The authors wish to thank Dr. Richard Liska (Czech Technical University
in Prague, Czech Republic) and Dr. Markus Berndt (Los Alamos National
Laboratory, Los Alamos, NM, USA) for implementation of the feasible set
computation by geometric intersections. The authors also thank Dr. Patrick
Knupp (Sandia National Laboratories) for valuable input during the development
of these procedures.



--R

An Arbitrary Lagrangian-Eulerian computing method for all ow speeds
Computational methods in Lagrangian and Eulerian hydrocodes.
Reference Jacobian optimization-based rezone strategies for Arbitrary Lagrangian Eulerian methods

--TR
Computational methods in Lagrangian and Eulerian hydrocodes
Computational geometry in C
An arbitrary Lagrangian-Eulerian computing method for all flow speeds
The construction of compatible hydrodynamics algorithms utilizing conservation of total energy
Smoothing by optimisation for a quadrilateral mesh with invalid elements
Reference Jacobian optimization-based rezone strategies for arbitrary Lagrangian Eulerian methods

--CTR
G. Irving , J. Teran , R. Fedkiw, Tetrahedral and hexahedral invertible finite elements, Graphical Models, v.68 n.2, p.66-89, March 2006
Raphal Loubre , Mikhail J. Shashkov, A subcell remapping method on staggered polygonal grids for arbitrary-Lagrangian-Eulerian methods, Journal of Computational Physics, v.209 n.1, p.105-138, 10 October 2005
G. Irving , J. Teran , R. Fedkiw, Invertible finite elements for robust simulation of large deformation, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France
element validity;arbitrary Lagrangian-Eulerian ALE simulations;mesh untangling;rayleigh taylor simulation;triangles;quadrilaterals