Multiple Scientific Applications
of Front Tracking Method

Multi-Component

The Marching Cube algorithm is an efficient way to construct complex geometric structures by mapping all possible grid cell conformations into some isomorphically distinct patterns. Here, we extended the Marching Cube algorithm to the construction of 3-D grid cells containing three different materials on their vertices.

There are two main methods used in the Matching Cube algorithm to establish the mapping. For example, for a 3-D two-component problem, the conformational mapping can be established by:

• use a look-up table of all 2⁸=256 conformations, which counts all potential combinations of status on eight vertices and then maps them into 14 basic patterns(e.g. Bourke, 1994).
• use a look-up table of 14 pre-defined patterns and let the computer programs do the rotations and complementations.

Terminologies

Some geometric terminologies frequently used in constructing 3-D grid cells with FronTier are shown in the figure below.

The orientation of the surfaces follows the right-hand rule, and the following figure link shows the definition of the orientations for both the surfaces and the intersection bond in a grid cell.

For example, the positive direction is from comp-0 to comp-1 for surface-0, from comp-1 to comp-2 for surface-1, and from comp-2 to comp-0 for surface-2(see the following table). By this way, the positive direction of the bond keeps coherent from P1 to P2.

Surface number	Positive component	Negative component
0	comp-0	comp-1
1	comp-1	comp-2
2	comp-2	comp-0

Note: the orientation of the intersecting bond is unique and must be specified deliberately in order to cope with the surface orientations.

Because of the structure symmetry of the cube, any potential conformation of the n-cube(n-dimensional grid cell) can be mapped into some typical patterns by geometric transformations. The rotation group of the n-cube guarantees the happening of the mapping.

Curve Crossing Assumptions

To define a surface representation within a grid cell which contains exact three different components, we assume two functions z = f(x, y) and z = g(x, y) which divide a grid cell into three parts, and each part belongs to an unique component. The intersection of the above two functions defines a bond that forms the final intersecting curve of the three different surfaces.

Based on each grid-face(see figure below Left), the intersection point of two functions z = f(x, y) and z = g(x, y) is called a curve crossing. Different from a grid-line crossing which is a point located on the grid line and separating between two distinct materials, a curve crossing is a point in the grid-face at which three different materials meet together.

Since the curve crossings may occur in any position of a grid-face, and given a grid-face conformation, there can exist a single curve crossing, no curve crossing, or multiple curve crossing.

If we consider all these potential conformations and there are 6 grid-faces in a single grid cell, the number of the typical patterns by the Marching Cube algorithm will be added up to at least 3 X 6 = 18 times of the number in the original look-up patterns.

To simplfy our problem, we made some assumptions on the curve crossing. In a grid cell, a curve crossing is uniquely determined if and only if the following assumptions are satisfied:

• Exactly three distinct components are found.
• Two components at the diagonal positions must be different.

57 Pattern Constructions

The following movie link shows a typical interface construction based on a grid cell.

• For every grid-line with two distinct components at each end, one and only one grid-line crossing must exist.
• For each grid face, one and only one crossing must exist if it satisfies two assumptions mentioned in the above section.
• Triangular patches are built by connecting all grid-line crossings binding to the same surface and any possible related curve crossings.
• One or more bonds are formed by connecting on-site curve crossings.

By stitching the triangular patches from the neighboring grid cells, the surface representations can then be made up, and the intersecting curve of three components is made by connecting all adjacent bonds into a continuous object.

[Back] [Top]

Computational Results

To examine the feasibility of our assumptions in constructing the three-component grid cells, we conducted several numerical experiments on some geometric problems where three-phase intersecting curves exist.

Case Constructions

Table below shows some captured grid conformations computed by our algorithm.

case01	case02	case03	case04	case05	case06	case07	case08
case09	case10	case11	case12	case13	case14	case15	case16
case17	case18	case19	case20	case21	case22	case23	case24
case25	case26	case27	case28	case29	case30	case31	case32
case33	case34	case35	case36	case37	case38	case39	case40
case41	case42	case43	case44	case45	case46	case47	case48
case49	case50	case51	case52	case53	case54	case55	case56
case57

An Ellipsoid Collides with a Plane

the following movie link shows an ellipsoid drip into a horizontal free-boundary plane. Three components are the component inside the ellipsoid, the component outside the ellipsoid but above the horizontal plane and the component outside the ellipsoid but below the horizontal plane.

Two Ellipsoids Intersect

the following movie shows the collision of two ellipsoids. The smaller ellipsoid has been cut open to check the intersection curve from the inside. Some glitches could be found on the intersection curve, which are possibly from the assumptions of defining the curve crossings or the pre-defined triangulation method on the 57 grid cell patterns.

[Prev] [Back]