Abstract
There are numerous instances in which it is necessary to reconstruct
or track the boundary surfaces (or "interfaces")
between multiple materials that commonly result from simulations.
Multi-fluid Eulerian hydrodynamics calculations require geometric
approximations of fluid interfaces to form the equations of motion
to advance these interfaces correctly over time. This project
presents a new algorithm for material boundary interface reconstruction
from data sets containing volume fractions.
To solve this problem, we transform the reconstruction problem
to a problem that analyzes the dual data set, where each vertex
in the dual mesh has an associated barycentric coordinate tuple
that represents the fraction of each material present. After
constructing a dual tetrahedral mesh from the original mesh,
we construct material boundaries by mapping a tetrahedron into
barycentric space and calculating the intersections with Voronoi
cells in barycentric space. These intersections are mapped back
to the original physical space and triangulated to form the boundary
surface approximation. This algorithm can be applied to any grid
structure and can treat any number of materials per element/vertex.
In typical simulations, the grid cells contain fractional
volumetric information for each of the materials. Each cell C
of a grid S has an associated tuple (a_1,
a_2, ..., a_m)
that represents the portions of each of m materials
in the cell, i.e., a_i
represents the fractional part of material i. We assume
that a_1 + a_2
+ ... + a_m = 1. The problem
is to find a (crack-free) piecewise two-manifold separating surface
approximating the boundary surfaces between the various materials.
To solve this problem, we consider the dual data set constructed
from the given data set. In the dual grid, each cell is represented
by a point (typically the center of the cell), and each point
is associated with a tuple (a_1,
a_2, ..., a_m),
where m is thenumber of materials present in the data set and
a_1 + a_2
+ ... +a_m = 1. Thus, the
boundary surface reconstruction problem reduces to constructing
the material interfaces for a grid where each vertex has an associated
barycentric coordinate representing the fractional parts of each
material at the vertex.We use this ``barycentric coordinate field''
to approximate thematerial boundary surfaces.
If we have a data set containing m materials, we process each
tetrahedral cell of the grid and map our tetrahedral elements
into an m simplex representing m-dimensional barycentric
space. Next, we calculate intersections with the edges of Voronoi
cells in the m-simplex. These Voronoi cells represent regions,
where one material ``dominates'' the other materials locally.
We map these intersections back to the original space and triangulate
the resulting points to obtain the boundary.
The figure on the
left shows a three-dimensional projection of a 4-simplex in barycentric
space, whose vertices are: (1,0,0,0), (0,1,0,0), (0,0,1,0), and
(0,0,0,1), and its associated Voroinoi partitions. We have mapped
a tetrahedron from physical space into the 4-simplex in Barycentric
space.
The following picture illustrates the material interfaces
fora data set consisting of three materials. The boundary of
the region containing material 1 has a spherical shape, and the
other two material regions are formed as concentric layers around
material 1 -- forming two material interfaces. The original grid
is rectilinear-hexahedral consisting of 64x64x64 cells.
The following illustration shows the material interfaces for
a three-material data set of a simulation of a ball striking
a plate consisting of two materials. The original data set is
rectilinear-hexahedral and has a resolution of 53x23x23 cells.
The following illustrataion shows the material interfaces
for a human brain data set. The original grid is rectilinear-hexahedral
containing 256x256x124 cells. Each cell contains a probability
tuple giving the probability that each material is present at
the point. The resulting dual data set contains over eight million
tetrahedra. We have clipped the resulting set of polygons to
illustrate the boundaries in the interior of the brain.
Publications
Contact
Ken Joy, Bernd Hamann
Download
A PDF version of the paper can be found here. 
