Material Boundary Surfaces

Kathleen S. Bonnell, Mark A. Duchaineau, Daniel A. Schikore, Bernd Hamann, and Ken Joy



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.



Ken Joy, Bernd Hamann


A PDF version of the paper can be found here.