Isosurface Generation
16.july.1997
GFX
by Hin Jang
An isosurface is defined by a set of points that satisfy the following equation
S(x, y, z) - C = 0where S is a spatial function and C is a constant. The surface is usually displayed as set of triangles, all of which are formed by local intersections between cells and the surface. Cells that do not intersect the surface are not part of the volume. Ito and Koyamada developed an efficient algorithm that visits only intersecting cells and cells that are included in cell lists [2].
Isosurface generation consists of a preprocess and a main process.
main()
{
/* -------------------------------- Pre-process */
ExtractExtrema()
GenerateGraph()
GenerateBoundList()
/* -------------------------------- Main process */
while(1) {
C = SpecifyScalarValue()
GenerateSurface(C)
}
}Determining the extrema points requires a comparison of the scalar values of all points for each cell.
ExtractExtrema()
{
for (each cell) {
if (point_is_not_maximum)
mark point as not_maximum
if (point_is_not_minimum)
mark point as not_minimum
}
for (each point) {
if (point is not either 'not maximum' or 'not minimum')
insert point into extrema list
}
}An extrema graph is a group of arcs that connects two extrema points a and b, the start and goal points, respectively. The cost of the graph, (ie. the number of cells inserted into the cell list), is minimal when closer extrema points are chosen. Starting from the cell that contains the start point, adjacent cells that share the face whose distance is minimum are visited in order. The minimum and maximum values of the start and goal points are updated by the scalar values of the points visited herein. This process is repeated until the traversal reaches the cell containing the goal point. If reaching the goal point results in leaving the volume, the traversal is terminated and a similar traversal begins when the next-closest extrema is declared the goal point.
GenerateGraph()
{
for (each extrema i)
extrm[i].flag = extrm[i].gID
for (each extrema n) {
for (each other extrema i) {
if (extrm[n].flag != extrm[i].flag)
if (extrm[i] is not too far)
Enqueue(extrm[i])
}
while (path_is_not_connected) {
Dequeue(extrm[m])
if (Make_Graph1(extrm[n], extrem[m]) == SUCCESS)
break
if (Queue_Is_Empty() == TRUE) {
Make_Graph2(extrm[n], extrm[m])
break
}
}
for (each extrema i)
if (extrm[i].flag == extrm[m].flag)
extrm[i].flag = extrm[n].flag
}
}
MakeGraph1(extrmA, extrmB)
{
visit_cell = A cell that contains extrmA
while (1) {
arc.cID[arc.numC++] = cell
arc.value[0] += arc.eID[0]
arc.value[1] -= arc.eID[1]
if (visit_cell includes extrmB)
return SUCCESS
visit_cell = adjacent cell that intersects arc
if (visit_cell == NULL)
return FAILURE
}
}
MakeGraph2(extrmA, extrmB)
{
visit_cell = A cell that contains extrmA
while (1) {
arc.cID[arc.numC++] = cell
arc.value[0] += arc.eID[0]
arc.value[1] -= arc.eID[1]
if (visit_cell includes extrmB)
return SUCCESS
visit_cell = adjacent cell that shares the nearest arc
}
}A boundary cell list is a group of cells that have faces not connected to an adjacent cell.
GenerateBoundList()
{
for (each boundary cell cID[i]) {
cID[i].max = FindMaximum()
cID[i].min = FindMinimim()
}
Generate_Sorted_Maximum_Based_List()
Generate_Sorted_Minimum_Based_List()
}Isosurfaces propagate themselves from seed cells. The minimum-based boundary cell list is traversed until the minimum value becomes higher than the given value. If the maximum value of the visited cell is higher, the cell is denoted as the seed cell. The maximum-based boundary cell list can also be used to select a cell from which propagation occurs. Seed cells are then searched for by traversing the arcs of the extrema graphs. If the specified scalar value lies between the minimum and maximum values of the arc, all the cells in the list are visited in order. An isosurface is generated when an extracted seed cell is unmarked.
GenerateSurface(float C)
{
for (each cell bcell[i] in the boundary cell list)
if (bcell[i].min < C
&& bcell[i].max > C
&& bcell[i] is not marked)
PropagateSurface(bcell[i], C);
for (each arc in the extrema graph)
if (arc.value[1] < C && arc.value[0] > C)
for (each unmarked cell in the arc) {
if (cell.cID[i] is intersected)
PropagateSurface(cID[i], C)
}
}
PropagateSurface(int cellID, float C)
{
Enqueue(cellID)
while (Queue_Is_Empty == FALSE) {
Dequeue(cellID)
Draw_Triangle(cellID);
Enqueue(cellIDs of all unmarked adjacent, intersected cells)
Mark_Cells_in_Queue();
}
}[1] Grimm, C.M., and J.F. Hughes, "Smooth Isosurface Approximation," Eurographics Conference on Implicit Surfaces, April 1995
[2] Itoh, T., and K. Koyamada, "Isosurface Generation by Using Extrema Graphs," 1994 IEEE Visualisation Conference, 77-83
[3] Lorensen, W.E., and H.E. Cline, "Marching Cubes: A High Resolution 3D Surface Construction Algorithm," Computer Graphics, SIGGRAPH 1987 Proceedings, 21(4):163-169
[4] Matveyev, S.V., "Approximation of Isosurface in the Marching Cube: Ambiguity Problem," 1994 IEEE Visualisation Conference, 288-292
[5] Montani, C., R. Scateni, and R. Scopigno, "Discretised Marching Cubes," 1994 IEEE Visualisation Conference, 281-287
