# JVRB - Journal of Virtual Reality and Broadcasting

##### Sections
Home / Adaptive Cube Tessellation for Topologically Correct Isosurfaces

# Adaptive Cube Tessellation for Topologically Correct Isosurfaces

1. Francisco Velasco University of Granada
2. Juan Carlos Torres University of Granada
3. Alejandro Léon University of Granada
4. Francisco Soler University of Granada

## Abstract

Three dimensional datasets representing scalar fields are frequently rendered using isosurfaces. For datasets arranged as a cubic lattice, the marching cubes algorithm is the most used isosurface extraction method. However, the marching cubes algorithm produces some ambiguities which have been solved using different approaches that normally imply a more complex process. One of them is to tessellate the cubes into tetrahedra, and by using a similar method (marching tetrahedra), to build the isosurface. The main drawback of other tessellations is that they do not produce the same isosurface topologies as those generated by improved marching cubes algorithms. We propose an adaptive tessellation that, being independent of the isovalue, preserves the topology. Moreover the tessellationallows the isosurface to evolve continuously when the isovalue is changed continuously.

1. published: 2008-03-20

## 1.  Introduction

A popular representation of digitized volumes is a regular lattice of points which represent the digitized samples. This set of samples can be used directly or can be previously filtered to obtain a reduced dataset. The most used lattice for some fields is a grid of cubic cells. This representation is easily obtained from a computerized axial tomography (CAT scan) or by magnetic resonance imaging (MRI). In both cases several 2D images are obtained and can be easily represented by a 3D grid in which every vertex represents a point sample.

Thus, a volume can be represented by the equation:

({(x,y,z,γ)}, F(x,y,z) : ³ → Γ)   (1)

where{(x,y,z,γ)} is the set of samples in the property domain Γ, and F(x,y,z) : ³ → Γ is the function that approximates values between samples.

There are several methods to visualize a volume represented by a grid: by slices, direct visualization [], or by means of isosurface extraction. By this later method, the focus of this paper, a threshold valueγ0 is set and an isosurface F(x,y,z) = γ0 is built and rendered as a volume visualization. Usually γ0 is also called isovalue. Several parts of the volume can be rendered by modifying γ0 . In this method F(x,y,z) must be extended outside the samples, usually as an interpolation function. The classical algorithm in this category is the marching cubes method []. This method builds the isosurface cube by cube, marching through all the cubes within the grid of cubic cells and extends F as the linear interpolation along the edges of every cube.

Every cell is classified, by comparing its eight vertex values with the threshold γ0 , as belonging to one of the fifteen possible equivalence classes. Every class (or case) has an isosurface represented as a triangle mesh. The entire isosurface to be rendered is obtained by joining the pieces of isosurface generated for every cube. Figure 1 shows the fifteen cases with their interior triangle meshes.

However, this method is ambiguous in some topologycal aspects. The ambiguity has been well studied in []. For instance, figure 2-a shows that a crack arises on the isosurface between the two cells; figure 2-b shows the triangle mesh proposed by marching cubes for the Case 4 however, the one in figure 2-c may also be possible. To find out which one is correct we need information about the interior of the cell.

Lopes, Brodlie and Nielson in [] solve the ambiguity studying the interior of the faces and the interior of the cell using the trilinear interpolation equation to define the property variation. As a consequence, the number of different equivalence classes is increased to 31 and 57 cases respectively. In this paper we will refer to these method as extended marching cubes(EMC).

Other authors [] solve the ambiguity using a tessellation of the cell into tetrahedra and building the isosurface by marching tetrahedra []. This method is similar to marching cubes but based on a tetrahedron instead of a cube, with the added advantage that, in this method, there are no ambiguities as it is well known and only has 3 equivalence classes.

However, for many classes of EMC [], the topology of the isosurface which is built by these methods is not the same as the topology of the isosurface built by marching tetrahedra from tessellations in other published works.

In this paper we propose a tessellation of cells into tetrahedra which produces the same isosurface topology as the one that would be extracted by the extended marching cubes methods.

The next section analyses the sources of ambiguity in a cube. Section three presents some tessellations used to obtain tetrahedra from cubes. In section four we put forth our proposal of tessellation. The paper ends with a section presenting the results and the conclusions.

## 2.  Correct Isosurfaces

In order to determine the correct topology for an isosurface we have to study the interpolation function F, which is a trilinear interpolation function. For a more exhaustive study the paper by Nielson [] may be consulted.

Let us begin analyzing a cube face. Taking into account that every face vertex can be positive (its value is greater than the isovalue) or negative and that a face has four vertices, there are 24 = 16 possible configurations of a face, however by rotation or by complementation (positive/negative), there are only 4 equivalence classes (see figure 3).

Assuming a linear variation along the edges, it is easy to prove that Case 0 does not have an isocurve and Cases 1 and 2 have the two isocurve topologies shown in figure 4. However, Case 3 has two possible isocurve topologies as is shown in figure 4 depending on which vertices can be connected by a line without intersecting the isocurves, the negative ones (case 3-a) or the positive ones (case 3-b).

To discover which one is the correct topology we have to compute the face saddle point, the point where one topology changes into another. This point is computed by using the function that interpolates the interior of the face, which is the bilinear interpolation:

Fface(x,y) = axy + bx + cy + d   (2)

The face saddle point is calculated by making the partial derivates, with respect to x and y, equal to zero:

(3)

and its value is computed using the equation 2.

So, we have a 5th point which can be positive or negative and allows us to choose the correct topology of the isocurve as it is shown in figure 5. The face saddle point becomes the inflection point between the two configurations; it is a contact point when the isovalue is equal to the face saddle point value (central image in figure 5).

The face saddle point (FSP), whenever it exists and is inside the face, can be used to tessellate it into 4 triangles. So the correct topology is directly obtained by processing the triangles instead of the square (see figure 6).

If the face saddle point is not present or is outside the face, it can be shown that the face will be always classified as belonging to Cases 0, 1 or 2 (figure 3), which are not ambiguous.

For the interior of the cube the process is similar: the body saddle points need to be computed.

The function that interpolates the interior of the cube is the trilinear interpolation:

F(x,y,z) = axyz + bxy + cyz + dzx + ex + fy + gz + h   (4)

The body saddle point (BSP) is also obtained by making 0 the three partial derivates:

(5)

The result of this equation system gives two possible body saddle points which are used to solve the ambiguities and choose the correct topology for the isosurface. The body saddle points are inflection points between the different configurations for an ambiguous cell. In this way, we can use the body saddle points, when they are present and they are inside the cell, to tessellate the cube into tetrahedra. The correct topology of the isosurface can be obtained by marching tetrahedra as will be shown in sections 4 and 5.

All the possible topologies, numbered following Lopes' methodology in [], are shown in figure 7. The first number defines the case taking into account the configuration of positive and negative vertices, the second number defines different solutions for ambiguous faces, and the third one defines different solutions for the ambiguous body. The case 0, without isosurface, is not shown. Nielson presents more cases in [], this is due to the use of a different equivalence relationship, but many of the cases are equivalents according to the Lopes' equivalence relationship.

These topologies can be easily obtained by marching tetrahedra with the adequate tessellation. The next section shows related works on tessellations and section 4 puts forth our proposal for the tessellation.

## 3.  Previous Tesselations

The marching tetrahedra method [] for isosurface building is similar to the marching cubes method []:

This method is non ambiguous by assuming a linear interpolation along the edges. Thus, by tessellating a cell into tetrahedra (figure 8 shows the most used tessellations) the ambiguity problem could be solved as can be seen in [].

However, these studies do not take into account that the property variation along a diagonal of a cube face is not linear, but quadratic, so that diagonal which is taken as a tetrahedron edge could have two intersections with the isosurface and not only one. Zhou et al. [] study this question and define a new way to build isosurfaces inside tetrahedra taking into account the quadratic variation of properties along diagonal edges, but there are 59 different cases! And moreover the method does not produce topologies like that of 4.1.2 in figure 7.

Chan and Purisima [] define a different tessellation (see figure 9) by defining tetraedra between adjacent cells, but the method does not produce topologies like that of 13.5.1 in figure 7.

Later studies have improved this method. Treece et al. [] reduce the number or triangles by clustering tetrahedra vertices which preserves the topology. The generated triangles are more regular, so the Gouraud shading is improved. Gerstner et al. [] achieve a multiresolution tessellation by a recursive bisection of some tetrahedron in two. They take into account several critical points to preserve or not the topology in accordance with certain criteria. Both studies start from a tessellation that does not produce all the topologies of figure 7.

Chiang et al. [] propose a progressive simplification of tetrahedral meshes by using a contour tree, a data structure that represents the relations between connected components of the isosurfaces embedded in a volume dataset. Since the structure used includes critical points, the simplification preserves the topology. The authors focus on an irregular grid, however their method can be also applied to regular grids.

Our proposal produces a tessellation that preserves all the topologies of figure 7 and can be used as an initial tessellation for the method of Chiang.

## 4.  Our Proposal

We propose to carry out an adaptive tessellation of every cell into tetrahedra in such a way that:

1. The tessellation must be isovalue independent in order to compute it just once, avoiding extra computations every time that the isovalue is changed.

2. The isosurface built inside the cell by joining the pieces of isosurfaces built from every tetrahedron of the tessellation has to be topologically equivalent to the isosurface built by using the extended marching cubes already commented in section 2 and in figure 7.

3. The isosurface has to move continuously when the isovalue changes continuously.

It will be done by taking into account the face and body saddle points.

We will use a basic tessellation which is valid for all non ambiguous cell configurations, that is to say, it is valid for those cells without face saddle points nor body saddle points. Then, this basic tessellation will be modified when face or body saddle points exist. These special points will be tetrahedra vertices and will be located at their exact position to improve the isosurface accuracy.

Basic case: 0 ambiguous faces and 0 body saddle points (Case 0-0)

The basic case corresponds to cells without ambiguous faces and without body saddle points. This kind of cell is tessellated as shown on figure 8-a. This tessellation produces 6 tetrahedra. Note that it is possible to build a tessellation which produces just 5 tetrahedra (see figure 8-b) but it is less homogeneous than the one proposed, because it implies the use of 2 possible symmetric tessellations depending on the position of the cell as can be deduced in figure 8-b. Another advantage is that this tesselation is similar to the others that will be shown in the paper. In figure 10 you can see an example of this case where the isovalue is continuously changed.

Case 0-1

This case corresponds to cells without ambiguous faces and just 1 body saddle point. This kind of cell is tessellated as is shown in figure 11-a where the body saddle point is the central point. In order to see it clearly, one must look at figure 11-b where the tessellation which corresponds to a face is shown. The other 5 faces are tessellated in a similar way. The cube is tesselated into 6 pyramids and each pyramid is tesselated into 2 tetrahedra. As such, this tessellation produces 12 tetrahedra. For clarity, in the figure 11-a the body saddle point is drawn in the center of the cell, but it will always be positioned in its exact position. All the tetrahedra share the body saddle point, so the topology around this point is preserved.

Cases n-1 (1 ≤ n ≤ 6)

These cases corresponds to cells with just 1 body saddle point and several ambiguous faces with one face saddle point associated with each ambiguous face. These cases are tesselated in a similar way to the case 0-1, the cube is tesselated into 6 pyramids, one pyramid for each face. The pyramids for the non-ambiguous faces are tesselated into 2 tetrahedra, as we have shown for the case 0-1 (figure 11-b). The pyramids for the ambiguous faces are tesselated into 4 tetrahedra by using the face saddle point in the base of the pyramid; as you can see in the figure 12-b. The figure 12-a shows the cube tesselated for the case 1-1 with the ambiguous face in the bottom face of the cube. All the saddle points will be positioned in their exact positions. This tessellation produces 12 + 2n tetrahedra. In these cases the topology is preserved around the face and body saddle points as can be easily observed by the fact that all the tetrahedra of an ambiguous face share the face saddle point and all the tetrahedra from the tessellation share the body saddle point.

In the figure 13 you can see an example for the case 1-1. The isovalue changes continuously and so, the isosurface is moved continuously from one topology to another.

Cases n-0 (1 ≤ n ≤ 6)

The cases n-0 are transformed into cases n-1 by adding a fictitious body saddle point in the center of the cube. We proceed this way to have tesselations analogous to the others. The figures 14, 15, and 16 show several examples with different configurations.

Case 0-2

This represents a cell with no ambiguous faces and 2 body saddle points. These two body saddle points form an edge . Using this edge and the 6 edges of the cuboid formed by the vertices V1, V5, V4, V6, V2, V3 (see figure 17-a), 6 tetrahedra are built (see figure 17-b). The back, left and bottom faces (which share V0) are tessellated as it was shown in figure 11-b but using B1 as the pyramid vertex (the body saddle point nearest to the cell origin). The front, right and top faces (which share V7) are tessellated in the same way but using B2 as the pyramid vertex, the other body saddle point. This tessellation produces 18 tetrahedra.

Cases n-2 (1 ≤ n ≤ 6)

The tessellation according to this case is carried out as the one shown for the case 0-2 but the ambiguous faces are tessellated as it was shown in figure 12-b instead of the tessellation shown in figure 11-b. This tessellation produces 18 + 2n tetrahedra. The topology is also preserved in theese cases as can be seen in figure 18.

The main advantage of this method is that tessellations, being independent of isovalue, produce the same isosurface topologies as the ones obtained by the recents improvements of marching cubes [] but with less computations because, with our method, an isovalue change does not produce a new tessellation, but rather marching tetrahedra has to be run again; whereas with Lopes and Nielson's methods, an isovalue change needs to compute a new configuration.

## 5.  Results And Conclusions

The proposed method has been tested by using a cell with configurations for all the cases of improved marching cubes. In this section we show the most representative ones. Every example is shown using different isovalues on the basis of the same cell, where you can see how the isosurface changes continuously when the isovalue is slightly changed.

Example 1 (figure 10): A configuration with 1 component on the basis of the simpliest tessellation.

Example 2 (figure 13): By modifying the isovalue from 26 to 23 we can see how an isosurface of 2 components changes to an isosurface of 1 component (with a tunnel between them) around the body saddle point which is inside this ambiguous cell.

Example 3 (figure 14): By changing the isovalue from 40 to 26 we can see how the isosurface changes continuously from 2 components to 1 component through the face saddle point on the bottom face.

Example 4 (figure 15): By modifying the isovalue from 36 to 50 the isosurface of 2 components on two opposite ambiguous faces changes continuously to an isosurface of 1 component and again, to an isosurface of 2 components.

Example 5 (figure 16): This example shows a cell with all its faces ambiguous but without body saddle points. The isovalue changes from 43 to 63.

Example 6 (figure 18): This example shows a cell with 2 body saddle points, by changing the isovalue from 42 to 58 we can see how the isosurface forms a tunnel around each body saddle point depending on the particular isovalue.

The vertex values, in addition to the number of tetrahedra, of every example, are shown in table 1.

Table 1.  Example's vertex values and number of tetrahedra (last row).

 V. Ex.1 Ex.2 Ex.3 Ex.4 Ex.5 Ex.6 V0 0 35 50 100 78 33 V1 10 12 14 71 33 100 V2 20 0 14 14 33 100 V3 30 38 14 14 100 0 V4 40 100 0 14 0 100 V5 50 15 14 0 78 0 V6 60 15 100 71 78 0 V7 100 15 14 71 33 67 6 14 14 16 24 30

In general the method produces all Lopes' topologies correctly; in fact, all the topologies in figure 7 have been achieved using our method. As the EMC method by Lopes produces topollogicaly correct isosurfaces, our method also produces topollogicaly correct isosurfaces.

The method has also been tested with real data. Figure 19-a shows a model of some teeth rendered using our method. It is possible to see that there are no holes on he surface. Figures 19-b and 19-c show a zoom of the image generated with our method and marching cubes respectively.

Our method produces similar results to Lopes []. However, every time the isovalue changes, Lopes' method has to compute the new cell configuration (from a total of 31 distinct configurations), the new possible bishoulder points, and the new possible tangent points, and then the triangle configuration is formed and rendered.

Using Lopes method, some infomation can be precomputed just once, but other information depends on the isovalue, so this kind of information needs to be computed every time the isovalue changes. As can be seen in his work, the computation of bishoulder points needs to compute a minimum of 2 face shoulder points (or more if a more accurate approximation is needed) so several square roots need to be computed. The computation of tangent points also needs to compute square roots because three quadratic equations have to be solved even though they have the same discriminant. So, every time the isovalue changes, several costly computations have to be performed. That is, it is a time expensive method for interaction.

Our method also needs to compute square roots (just one per cell) to determine which tessellation must be carried out, however, the particular tessellation is computed just once for every cell because our tessellation is isovalue independent. As the tessellation does not depend on the classification of the vertices, once the tessellation has been carried out, the volume is represented by a set of tetrahedra and it is visualized by the well known and fast marching tetrahedra. No new tessellation needs to be computed, unless some value is changed. In this case, only the cells that share that point will be tessellated again. An isovalue change does not require any new tessellation.

Both methods are topologically valid but our method needs less computations when the isovalue changes as it is isovalue independent. So, it is faster with, allowing interactive visualization.

Moreover, our method also produces continuous changes in the isosurface when the isovalue changes continuously. It is so, because the saddle points, which are points where one topology changes into another one, are vertices of the tetrahedra. So, when the isovalue is changed, the isosurface is moved towards or from saddle points where its topology is changed

Hence, our three goals of section 4 are achieved:

1. The tessellation only depends on the cell vertex' values. It is independent of the isovalue.

2. The isosurfaces that are obtained are topollogically equivalents to the isosurfaces that are obtained by Lopes' method, so they are topollogically corrects.

3. The movement of the isosurface is continuous when the isovalue is moved continuously.

The drawback of our method is the number of tetrahedra that is produced, however acording to several test, the most frequent case is the case 0-0, which appears more than a 52%. The case 1-1 (which includes the case 1-0) appears a 27%, the case 2-1 (plus the case 2-0) appears a 13% and so on until the worst cases (cases n-2) which, by taking into account all together, appear less than 1%. The tests have been carried out building cells within random values. Table 2 shows the results.

Table 2.  Frecuency of cases

 Case Frequency Case 0-0 52.77% Cases 1-0 and 1-1 27.22% Cases 2-0 and 2-1 13.23% Cases 3-0 and 3-1 3,39% Cases 4-0 and 4-1 1.98% Cases 5-0 and 5-1 0.00% Cases 6-0 and 6-1 0.98% Cases 0-2, 1-2, 2-2 and 3-2 0.00% Case 4-2 0 000011% Case 5-2 0.00% Case 6-2 0.43%

As future work, we want to analyse the possibility of grouping the tetrahedra in order to reduce their global amount and to allow a multiresolution representation of the volume.

## 6.  Acknowledgement

This work has been funded by the Spanish Government and by ERDF funds under project TIN2004-06326-C03-02. It has also been unded by Andalusian Government under excellence project TIC-401.

## Bibliography

[CGMS00] Reconstruction of topologically correct and adaptive trilineal surfaces Computer and Graphics,  24 (2000)no. 3399—418issn 0097-8493.

[Che95] Marching cubes 33: Construccion of Topologically Correct IsosurfacesTechnical Report CN/95-17CERN1995http://wwwinfo.cern.ch/asdoc/psdir/mc.ps.gz, Last visited March 20th, 2008.

[CL03] Progressive simplification of tetrahedral meshes preserving all isosurface topologies Computer Graphics Forum,  22 (2003)no. 3493—504issn 0167-7055.

[CP98] A new tetrahedral tesselation scheme for isosurface generation Computers & Graphics,  22 (1998)no. 183—90issn 0097-8493.

[GH95] Exploiting triangulated surface extraction using tetrahedral decomposition IEEE Transactions on Visualization and Computer Graphics,  1 (1995)no. 4328—342issn 1077-2626.

[GP00] Topology preserving and controlled topology simplifying multiresolution isosurface extraction Proceedings of the IEEE Conference on Visualization'00,  2000259—266Salt Lake City, Utah, USAisbn 1-58113-309-X.

[LB03] Improving the robustness and accuracy of the marching cubes algorithm for isosurfacing IEEE Transaction on Visualization and Computer Graphics,  9 (2003)no. 116—29issn 1077-2626.

[LC87] Marching cubes: A high resolution 3d surface construction algorithm ACM Computer Graphics,  21 (1987)no. 4163—169issn 0097-8930.

[Lev90] Efficient ray tracing of volume data ACM Transactions on Graphics,  9 (1990)no. 3245—261issn 0730-0301.

[Lop99] Accuracy in Scientific VisualizationPhd ThesisUniversity of Leeds, United Kingdom1999.

[MSS94] A modified look-up table for implicit disambiguation of marching cubes The Visual Computer,  10 (1994)no. 6353—355issn 0178-2789.

[NH91] The asymptotic decider: resolving the ambiguity in marching cubes Proceedings of the IEEE Conference on Visualization'91,  pp. 83—911991San Diego, California, USAisbn 0-8186-2245-8.

[Nie03] On marching cubes IEEE Transactions on visualization and computer graphics,  9 (2003)no. 3283—297issn 1077-2626.

[NY06] A survey of the marching cubes algorithm Computers & Graphics,  30 (2006)no. 5854—879issn 0097-8493.

[PT90] Surface mapping brain function on 3d models IEEE Computer Graphics & Applications,  10 (1990)no. 533—41issn 0272-1716.

[TPG98] Regularised marching tetrahedra: Improved iso-surface extraction Computers & Graphics,  23 (1999)no. 4583—598issn 0097-8493.

[WG90] Topological considerations in isosurface generation. extended abstract ACM Computer Graphics,  24 (1990)no. 579—86issn 0097-8930.

[ZCT95] An elaborate ambiguity detection method for constructing isosurfaces within tetrahedral meshes Computers & Graphics,  19 (1995)no. 3355—364issn 0097-8493.