**Quality Improvement and Boolean-Like Cutting Operations in Hexahedral
Meshes**

Jason F. Shepherd^1^, Yongjie Zhang^2^, Claudio T. Silva^3^

^1^Sandia National Laboratories, Albuquerque, NM 87185, USA

<jfsheph@sandia.gov>

^2^Carnegie Mellon University, Pittsburgh, PA 15213, USA

<jessicaz@andrew.cmu.edu>

^3^University of Utah, Salt Lake City, UT 84112, USA

<csilva@cs.utah.edu>

**Abstract**

In this paper, we propose a solution to improving the quality of
hexahedral meshes derived from volumetric data using insights obtained
from the structure of the dual of a hexahedral mesh. Our solution is to
add a layer of hexes along the boundary, composed of well-shaped
elements. The additional flexibility provided by this layer enables the
optimization of the original poorly-shaped elements that are no longer
on the boundary allowing for creation of a high-quality hexahedral mesh
while maintaining a conformal mesh on both sides of the inserted layer.
An extra benefit of our technique is being able to capture sharp
features using a Boolean-like cutting operation and inserting multiple
layers to maintain the high quality of the hexahedral mesh. Our
experimental results demonstrate the successful removal of all bad
elements (i.e. those elements of the mesh that have a scaled Jacobian
measure of less than 0.2) in a number of complex examples. This
technique is also an efficient way to create boundary layers for CFD
(Computational Fluid Dynamics) applications.

**Introduction**

Mesh generation deals with the problem of decomposing complex geometry
into discrete elements (meshes), which can be used for modeling,
simulation, and visualization. These meshes play a significant role in
computationally-based science and engineering.

Our work in this paper demonstrates quality improvement and feature
capture in hexahedral meshes of complex geometries. We build on the work
of Zhang et al. \[1,2\] for creating topological hexahedral meshes from
volumetric isosurfaces, and the fundamental hexahedral mesh concepts
outlined by Shepherd in \[3\] to improve the quality of the final
hexahedral meshes. To create the final hexahedral mesh, sheet insertion
\[4,5\] and mesh optimization algorithms \[6,7\] available in CUBIT
\[8\] are utilized. A key result of our paper is to demonstrate
high-quality hexahedral mesh generation for complex geometries derived
from volumetric images.

Our specific contributions are:

• A method for quality improvement in hexahedral meshes of an
arbitrarily complicated domain generated from octree-based algorithms.

• We describe the necessary topologic structures needed within a
hexahedral mesh to capture boundary discontinuities (i.e. sharp
features).

• Our technique is an automatic and efficient way for Boolean-like
cutting operation and boundary layer creation in CFD applications.

• Finally, we demonstrate our technique on several models indicating the
realized improvement in the overall quality of the final meshes on these
models over previous algorithms.

**Mesh Acquisition**

The base meshes utilized in this paper were constructed from volumetric
data using the LBIE-Mesher \[1,2\]. The LBIE-Mesher is based on a
surface topology preserving octree-based algorithm coupled with a dual
contouring method to create a uniform hexahedral mesh boundary-fitted to
an isosurface. The uniform mesh is then decomposed into finer hexes
adaptively using predefined templates without introducing any hanging
nodes, and the positions of all boundary vertices are recalculated to
approximate the boundary surface more accurately. A smoothing step is
also performed to improve the final surface mesh \[2\]. The final meshes
demonstrated in this paper were built in CUBIT \[8\] using the original
meshes from the LBIE-Mesher as the starting point. In CUBIT, a
hexahedral layer insertion was performed along with mesh smoothing,
optimization and mesh quality verification. These steps will be
discussed in more detail in later sections.

**Hexahedral Mesh Structures**

A hexahedral mesh can be viewed as a collection of intertwined layers of
hexahedra. A single hexahedron will belong to, at most, three separate
layers of hexahedra. Each layer of hexahedra can be visualized in a dual
representation as a single manifold surface, known as a 'sheet'. We will
utilize the dual representation of a hexahedral mesh as defined by
Mitchell \[9\] in his hexahedral mesh existence proof, but also use some
concepts from Murdoch \[10\]. We also utilize the hexahedral constraints
for maintaining a hexahedral topology and sufficient quality as outlined
in \[3\].

*Surface Capture*

The boundary of any hexahedral mesh is a quadrilateral mesh. As shown in
Figure 1, the quadrilaterals on the boundary will belong to one or more
layers of hexahedra. For a smooth and continuous boundary, a hexahedral
mesh consisting of a single layer of hexahedra reduces skew and improves
element orthogonality at the boundary, and offers the highest level of
topologic regularity in the mesh. Therefore, if we assume no
discontinuities in the boundary surface description, meshes which
utilize a single layer to capture all of the boundary quadrilaterals
will invariably admit elements whose potential quality is higher than
meshes which utilize multiple layers to capture the boundary surface.

![](media/image1.wmf){width="5.035416666666666in" height="1.16875in"}

**Figure 1: When multiple layers of hexahedra capture boundaries, the
quality and regularity of the mesh is affected. Image A shows elements
from a single layer capturing the upper boundary of the solid. Image B
and C use multiple layers of hexahedra to capture the upper boundary of
the solid. In image B and C, note how the regularity of the mesh is
affected and the resulting skew in the transition element as the
hexahedral layer curves away from the boundary.**

*Curve Capture*

Where discontinuities exist in the geometry, it is often desirable to
place a simply connected set of mesh edges that align themselves with
the discontinuity. These discontinuities are often called sharp
features, and in solid models are often the trimmed boundaries of pairs
of surfaces within the solid model (and known as *curves).*

The intersection of two layers of hexahedral elements results in a
column of hexahedra. In the dual representation of a hexahedral mesh,
this column of hexahedra is also known as a chord (see Figure 2). For
each chord, there are four sets of simply connected edges running along
the length of the column of hexahedra. For each sharp discontinuity in
the geometry, a conformal hexahedral mesh of that discontinuity will
have one or more columns of hexahedra running along the length of the
discontinuity. (However, these columns may be disjointed, similar to the
layers of hexahedra shown in Figure 1.)

**Methods**

In octree-based hexahedral meshes, the quadrilaterals on the boundary of
the mesh often belong to multiple, disjointed layers of hexahedra. This
structure results in diminished element quality near the boundary. In
this section we will outline an algorithm for improving the quality of
hexahedral meshes near the boundary by inserting a new layer of
hexahedra. This new layer effectively aligns the boundary hexahedra with
the boundary surface and of provides extra degrees of freedom for
subsequent mesh optimization.

*Mesh Quality Improvement using Boundary Sheets*

In order to add a new layer of hexahedra near the boundary of the
geometry, we use a modified version of a pillowing algorithm as
described by Mitchell \[9\].

![](media/image2.wmf){width="2.7506944444444446in" height="2.39375in"}

**Figure 2: The intersection of two layers of hexahedra results in a
column of hexahedra, and a string of simply connected mesh edges
sufficient to capture a sharp geometric discontinuity.**

The basic layer insertion algorithm is as follows (also refer to Figure
3):

1\. *Define a shrink set* - For our purposes, this step involves
dividing the existing mesh into two sets of elements: one set for each
of the half-spaces defined by the new layer to be inserted. One of these
two sets of hexahedral elements comprises the shrink set.

2\. *Shrink the shrink set* - Create a gap region between the two
previous element sets.

3\. *Connect with a new layer of elements* -- Because there is a
one-to-one mapping between the nodes on the boundaries of the two sets,
a new layer of hexes can be created by creating an edge between each
node separated during the shrinking operation and generating the
connectivity of the new hexahedra in the layer using the quadrilaterals
on the boundary of the two sets of hexahedra.

When inserting a single layer next to the boundary, we define our shrink
set as all of the elements within the solid. We desire the original
surface mesh to be undisturbed by any of our modification operations, so
a copy of the surface mesh is made prior to shrinking the layer of
elements near the boundary. For each face on the boundary, one new
hexahedral element is created. Our layer insertion algorithm guarantees
that for each quadrilateral on the boundary, there is at most one
incident hexahedra interior to the volume, which results in a lot of
freedom for further mesh quality improvement. Figure 4 demonstrates a
mesh with a newly inserted layer.

*Cutting Operations*

![](media/image3.png){width="4.995138888888889in"
height="1.9395833333333334in"}

**Figure 3: A basic pillowing operation starts with an initial mesh (A).
A shrink set is defined and separated by 'shrinking' from the original
mesh (B). A new layer of elements (i.e. a sheet) is inserted (C) to fill
the void left by the shrinking process.**

![](media/image4.png){width="2.498611111111111in"
height="2.498611111111111in"}![](media/image5.png){width="2.498611111111111in"
height="2.498611111111111in"}

**Figure 4: A hexahedral mesh of a sphere with a human head embedded in
the center. The mesh on the left is an octree-based mesh that has been
refined and oriented capture the geometry of the embedded head. The
hexahedral mesh on the right is the same mesh with two additional layers
of hexahedra at the interior and exterior boundary. The mesh on the
right has a higher quality and flexibility due to the improved mesh
topology capturing the geometric boundary.**

By inserting multiple layers of hexahedra, we can obtain a simply
connected set of mesh edges wherever new or existing layers intersect.
Capitalizing on this concept, we can strategically insert layers of
hexahedra to perform Boolean-like CG operations in the hexahedral mesh
while still maintaining mesh conformity with all of the split-off pieces
\[5\]. At the intersection of the layers, edges can be aligned with any
sharp discontinuities in the geometry. In Figure 5 we demonstrate
several successive spherical cuts from a single hexahedral mesh of a
cubical geometry. Where two layers intersect, a simply-connected string
of mesh edges exists and can be aligned with the cut enabling the sharp
features in the resulting model to be recognized.

![](media/image6.wmf){width="5.013194444444444in"
height="1.4131944444444444in"}

**Figure 5: By inserting spherical sheets into the geometry, we can
perform Boolean-like cutting operations in the mesh, while maintaining
the integrity of the hexahedral mesh.**

*Boundary Layer Insertion*

Viscous flow phenomena, such as laminar flow and turbulent flow has
strong gradient directionality near the boundary. To capture the
characteristics of these flows with a manageable number of elements,
anisotropic meshes are often utilized in boundary layers and free shear
layers. Therefore, it is very critical to create high-quality boundary
layer meshes in CFD simulations. A popular strategy for generating
boundary layer meshes is the advancing layers method (also called
advancing normals method) \[15-20\]. However, care needs to be taken to
prevent crossover of the normal directions or self-intersection.

In addition to the cutting operations described earlier, strategic sheet
insertion can be utilized to automatically and efficiently insert layers
of hexahedra adequate for use near the boundary in fluid-based
simulations. Compared to the advancing layers method, one significant
advantage of our sheet insertion algorithm is that no self-intersection
situations are introduced. This is accomplished using the same method
described earlier for cutting the meshes, by defining a manifold set of
quadrilaterals in the mesh where the boundary layers are desired. The
manifold set of quadrilaterals within the original hexahedral mesh
separate the hexes into two sides. Either side of hexes can be
designated as the pillowing shrink set and a single sheet can be
inserted. With the initial boundary layer sheet in place, a sheet-dicing
algorithm \[11,12\] can be applied to produce multiple parallel layers
of hexahedra suitable for boundary layer simulation. The placement of
these layers must be controlled to enable geometric growth in the
thickness of the hexahedral layers. This process is shown using the mesh
from Figure 4. The initial mesh after the cutting operation is utilized
for the boundary layer and a sheet dicing algorithm is applied to
produce the multiple parallel boundary layer effect shown in Figure 6.

In Figure 7, a planar layer of hexes is added behind the face of the
head model. This layer coupled with the layer of hexahedral added
previously for the head results in a string of edges that can be used to
capture the sharp discontinuity, thereby enabling the cutting operation.

![](media/image7.png){width="2.3180555555555555in"
height="2.1756944444444444in"}
![](media/image8.png){width="2.316666666666667in"
height="2.1972222222222224in"}

**Figure 6: After insertion of a sheet near the boundary of a manifold
set of quadrilaterals, sheet dicing can be used to insert boundary
layers into the hexahedral mesh. The box in the image on the left
indicates the location of the close-up view shown on the right.**

![](media/image9.wmf){width="5.064583333333333in"
height="3.1666666666666665in"}

**Figure 7: A layer of hexahedra elements is inserted behind the face in
the head model enabling the face to be cut cleanly from the rest of the
head.**

**Results**

In this section we display results detailing the quality differences
after inserting a layer of hexahedra at the boundary for several
examples. The scaled Jacobian metric \[12\], as implemented in VERDICT
\[13\], is used as the definitive measure for hexahedral quality. We
will assume that any elements with scaled Jacobian less than zero are
unsuitable for analysis and any element with scaled Jacobian less than
0.2 is questionable for use in an analysis.

Because correct and optimal placement of the new layer can be difficult,
we also perform a mesh optimization step on both meshes using the TSTT
Mesh Quality and Improvement Toolkit (MESQUITE) \[7\] library of
smoothing algorithms as implemented in Cubit \[8\]. In particular, we
have utilized a mean ratio smoother \[6\], which incorporates an
*L*^2^-norm template with guarantees that (1) the mesh will remain
untangled if the initial mesh is untangled, and (2) the average value of
the mean ratio will either stay the same, or be decreased.

There are four examples given: a human head (Figures 8 and 9), a meshed
sphere around the human head (Figure 4), a human knee model (Figure 10),
and a model of a mAChE biomolecule (Figures 13 and 14). Element quality
results are given for each of the meshes before and after layer
insertion (see Figures 11 and 12). The introduction of the boundary
sheet enables the removal of all negative scaled Jacobian values from
the displayed meshes.

![](media/image10.png){width="1.4819444444444445in"
height="2.1013888888888888in"}![](media/image11.png){width="1.7791666666666666in"
height="2.032638888888889in"}![](media/image12.png){width="1.6805555555555556in"
height="2.0125in"}

**Figure 8: Human head model. The original mesh contains 6,583 total
hexes (cut-away view in center). An additional layer of hexahedra was
added to the boundary to improve quality resulting in a new mesh (right)
with 9,487 total elements. The boxes indicate the location of the
close-up view shown in Figure 9.**

![](media/image13.png){width="2.3618055555555557in"
height="2.1256944444444446in"}
![](media/image14.png){width="2.5006944444444446in"
height="2.157638888888889in"}

**Figure 9: Close-up view showing the changes to the mesh quality before
and after the sheet insertion in the human head model.**

![](media/image15.png){width="1.5in" height="2.626388888888889in"}
![](media/image16.png){width="1.6506944444444445in"
height="2.6618055555555555in"}![](media/image17.png){width="1.6506944444444445in"
height="2.65625in"}

**Figure 10: Human knee model. The original mesh contains 1,338 total
hexahedra (cut-away in center). An additional layer of elements was
added to the boundary to improve quality resulting in a new mesh (right)
with 2,682 total elements.**

![](media/image18.jpeg){width="2.502083333333333in"
height="2.1069444444444443in"}![](media/image19.jpeg){width="2.4493055555555556in"
height="2.134027777777778in"}

**Figure 11: Distribution of scaled Jacobian measure for the knee and
the head meshes. The original mesh (hatched, dark) of the knee contains
367 elements of questionable or unacceptable quality, while the new mesh
(solid, white) has all elements with scaled Jacobian greater than 0.2.
The original mesh (dark, hatched) of the head contains 1025 questionable
or unacceptable elements, and the new mesh (solid, white) has one
element of questionable quality (related to a poor quality boundary
quadrilateral).**

![](media/image20.jpeg){width="2.4993055555555554in"
height="2.2083333333333335in"}![](media/image21.jpeg){width="2.4972222222222222in"
height="2.1944444444444446in"}

**Figure 12: Distribution of scaled Jacobian measures for the head
sphere mesh and the mAChE mesh. The original mesh (dark, hatched) of the
head sphere contains 2,485 elements of questionable or unacceptable
quality, while the new mesh (solid, white) has all elements with scaled
Jacobian greater than 0.2. The original mesh (dark, hatched) of the
mAChE has 7,298 problematic elements, while the new mesh (solid, white)
has only 111 elements of questionable quality (due to poor quality
boundary quadrilaterals).**

![](media/image22.png){width="3.1326388888888888in" height="2.50625in"}

![](media/image23.png){width="2.441666666666667in"
height="2.3833333333333333in"}
![](media/image24.png){width="2.441666666666667in"
height="2.3493055555555555in"}

**Figure 13: Biomolecule mAChE model. The original mesh contains 70,913
hexahedra (cut-away view in center). An additional layer of elements was
added to the boundary to improve quality giving a new mesh (right) with
90,937 elements. The boxes indicate the location of the close-up views
shown in Figure 14.**

![](media/image25.png){width="2.247916666666667in"
height="2.6347222222222224in"}
![](media/image26.png){width="2.247916666666667in"
height="2.645138888888889in"}

**Figure 14: Close-up view showing the changes to the mesh quality
before and after the sheet insertion in the mAChE model.**

**Discussion**

The meshes generated for this paper were initially created using the
algorithm detailed by Zhang, et al., in \[1\]. Subsequent sheet
insertions, mesh smoothing and optimization, and mesh quality
calculations were completed in CUBIT \[8\]. Each of these later steps
are user-driven and have not been fully automated; however, they are not
very time-consuming, and each mesh was generated in less than two hours
of wall-clock time for a knowledgeable user. All of these steps could be
automated and subsequent work by both Shepherd \[3\] and Zhang \[21\]
have continued to expand, generalize, and automate these methods for
more complex geometries.

It is also important to note that the sheet insertion process is mesh
enriching. That is, when a new sheet is added below the boundary of an
existing mesh, there are an equal number of new hexahedra added to the
mesh as there are quadrilaterals on the boundary. For large meshes, the
addition of this many new hexahedra is typically insignificant, however
for smaller meshes the number of new hexahedra added could be a
significant percentage of the original mesh. Subsequent mesh adaptation
algorithms, including sheet extraction \[22\], can be utilized to reduce
the number of elements in the final mesh.

**Conclusion**

In this paper, we have outlined a method utilizing a simple hexahedral
layer insertion process to improve the quality of the elements generated
using an octree-based algorithm with methodologies similar to the dual
contouring approach that captures isosurfaces within volumetric data. We
demonstrate how by strategically inserting hexahedral layers into the
octree-produced hexahedral meshes, we can significantly improve the
overall mesh quality without changing the boundary mesh. We also show
how insertion of multiple sheets can be utilized to capture
discontinuities or sharp features in the meshes, and create boundary
layer meshes for CFD applications. We have demonstrated the quality
improvement on several models. We ensure that the quality comparisons
are accurate by utilizing the MESQUITE mesh optimization algorithms on
the meshes both before and after the sheet insertion. The VERDICT
library is also used to verify and report the final mesh quality.

**Acknowledgments**

C. Silva is funded by the National Science Foundation (grants
CCF-0401498, EIA-0323604, OISE-0405402, IIS-0513692, CCF-0528201), the
Department of Energy, Sandia National Laboratories, Lawrence Livermore
National Laboratory, and an IBM Faculty Award.

Sandia is a multiprogram laboratory operated by Sandia Corporation, a
Lockheed Martin Company, for the United States Department of Energy's
National Nuclear Security Administration under contract
DE-AC04-94AL85000.

**References**

\[1\] Y. Zhang and C. Bajaj. Adaptive and quality
quadrilateral/hexahedral meshing from volumetric data. Computer Methods
in Applied Mechanics and Engineering (CMAME), 195(9-12):942--960, 2006.

\[2\] Y. Zhang, C. Bajaj, and G. Xu. Surface smoothing and quality
improvement of quadrilateral/hexahedral meshes with geometric flow. In
Proceedings, 14th International Meshing Roundtable, pages 449--468.
Sandia National Laboratories, September 2005.

\[3\] J. F. Shepherd. Topologic and Geometric Constraint-Based
Hexahedral Mesh Generation. Published Doctoral Dissertation, University
of Utah, May 2007.

\[4\] S. A. Mitchell and T. J. Tautges. Pillowing doublets: Refining a
mesh to ensure that faces share at most one edge. In Proceedings, 4th
International Meshing Roundtable, pages 231-- 240. Sandia National
Laboratories, October 1995.

\[5\] M. J. Borden, J. F. Shepherd, and S. E. Benzley. Mesh cutting:
Fitting simple all-hexahedral meshes to complex geometries. In
Proceedings, 8th International Society of Grid Generation Conference,
2002.

\[6\] P. M. Knupp. Hexahedral and tetrahedral mesh shape optimization.
International Journal for Numerical Methods in Engineering,
58(1):319--332, 2003.

\[7\] MESQUITE: The Mesh Quality Improvement Toolkit, Terascale
Simulation Tools and Technology Center (TSTT),
http://www.tstt-scidac.org/research/mesquite.html, 2005.

\[8\] The CUBIT Geometry and Mesh Generation Toolkit, Sandia National
Laboratories,

http://cubit.sandia.gov/, 2005.

\[9\] S. A. Mitchell. A characterization of the quadrilateral meshes of
a surface which admit a compatible hexahedral mesh of the enclosed
volumes. In 13th Annual Symposium on Theoretical Aspects of Computer
Science, volume Lecture Notes in Computer Science: 1046, pages 465--476,
1996.

\[10\] P. J. Murdoch. The Spatial Twist Continuum: A Dual Representation
of the All Hexahedral Finite Element Mesh. Published Doctoral
Dissertation, Brigham Young University, December 1995.

\[11\] D. J. Melander, T. J. Tautges, and S. E. Benzley. Generation of
multi-million element meshes for solid model-based geometries: The dicer
algorithm. AMD - Trends in Unstructured Mesh Generation, 220:131--135,
July 1997.

\[12\] K. Merkley, C. D. Ernst, J.F. Shepherd, M.J. Borden, "Methods and
Applications of Generalized Sheet Insertion for Hexahedral Meshing,"
Proceedings, 16^th^ International Meshing Roundtable, October 2007.

\[13\] P. M. Knupp. Algebraic mesh quality metrics. SIAM J. Sci.
Comput., 23(1):193--218, 2001.

\[14\] P. P. Pebay, D. C. Thompson, J.F. Shepherd, P. Knupp, "New
Applications of the Verdict Library for Standardized Mesh Verification:
Pre, Post, and End-to-End Processing," Proceedings, 16th International
Meshing Roundtable, October 2007.

\[15\] S. D. Connell, M. E. Braaten, "Semistructured mesh generation for
three dimensional navier-stokes calculations," AIAA Journal, 33(6),
1995.

\[16\] Y. Kallinderis, S. Ward, "Hybrid prismatic tetrahedral grid
generation for complex 3-d geometries," In AIAA-93-0669, 1995.

\[17\] Y. Kallinderis, A. Khawaja, H. McMorris,\_"Hybrid
prismatic_tetrahedral grid generation for complex 3-d geometries," In
AIAA-95-0211, 1995.

\[18\] R. Lohner, "Matching semi-structured and unstructured grids for
Navier-Stokes calculations," In AIAA-93-3348 CP, 1995.

\[19\] S. Pirzadeh,"Viscous unstructured three-dimension grids by the
advancing layers method," Proceedings of the 32nd Aerospace Sciences
Meeting & Exhibit, number AIAA-94-0417, Reno, NV, Jan. 1994.

\[20\] R. V. Garimella, M. S. Shephard, "Boundary layer meshing for
viscous flows in complex domains," 7th International Meshing Roundtable,
107-118, 1998.

\[21\] Y. Zhang, T. J.R. Hughes, C. Bajaj. "Automatic 3D Meshing for A
Domain with Multiple Materials," Proceedings of 16th International
Meshing Roundtable, pp. 367-386. Seattle, Washington. Oct. 14-17, 2007.

\[22\] M. J. Borden, S. E. Benzley, and J. F. Shepherd. Coarsening and
sheet extraction for all-hexahedral meshes. In Proceedings, 11th
International Meshing Roundtable, pages 147--152. Sandia National
Laboratories, September 2002.