An application of surface-oriented methods for volume visualization is the visualization of surfaces separating distinct regions of the volume. This technique is mostly based on binary classification of data samples in an inside and outside part by an iso-value, i.e. the separation of data sets by a surface into two different regions depending on a classification. But there are also applications where the classification into more than two different regions (general classification) is required. Nielson et al. [16] mention the segmentation of different tissues or organ classes for medical applications or materials classified by properties like solid, liquid or gas for physical simulation. A visualization of more than two different regions is also required for the exploration of boundaries between basins within dynamical systems, for example the system discussed by Agiza et al. [1]. This application is the main motivation for the presented project, but the surface extraction technique can also be applied to other data sets with a binary or general classification. The basin boundaries of a dynamical system can be considered as surfaces, which separate regions with different long-time behaviour [17]. The problem with dynamical systems in this context is an expensive classification function (iteration of a trajectory) and that these classifications do not support further information about the position of the boundary.

The surface construction has to be fast both for binary and generally classified regions. The construction should only have local influence to support progressive refinement, since new points are gradually inserted.
 

Because of expensive classifications we have to use a representation with as few as possible classified points, i.e. we use more points for regions with a higher level of detail and fewer points for regions with a small level of detail. Further we have to store and reuse classified points. The classification and the surface model have to be stored in a compact way, because of the expected high amounts of data.
 

We have to provide the possibility of selection criteria for progressive refinement and a high number of intermediate representations. For the selective refinement the user is able to choose a region of interest by the actual view direction. The selected region is first considered for refinement and is visualized with a higher level of detail than its surrounding. Other regions are considered, if the refinement of the selected region to the currently highest level of detail is finished.
 

 

There are only few approaches for the visualization of generally classified data sets. These approaches are not adequate for our application because of a subdivision of generally classified cells in many sub cells for a generalized Marching Cubes [11] or the use of tetrahedra for the surface construction in [4, 16]. Therefore a modified Marching Cubes algorithm [6, 12] is used. The progressive refinement is realized by a subdivision of a cube into 8 equally sized sub cubes. Different levels of detail are extracted depending on the local curvature by different subdivision depths.

The visualization of generally classified regions requires also double-sided triangles with different front and back side colors. Double-sided triangles can be implemented with Java 3D using two triangles with opposite normal vectors, opposite vertex order, activated backface culling and different colors.
 

The original Marching Cubes algorithm classifies the eight vertices of a cell depending on their data value and an iso-value as inside (0) and outside (1). Every differently classified edge of a cell contains an intersection point. The intersection points are points of the surface, which have to be connected for triangulation. Exploiting symmetry 15 basic cases can be identified out of 256 possible classifications of the 8 cell vertices. The 15 cases can be stored in a fast look-up table. The exact position of a point on an intersected edge is calculated by linear interpolation between the two vertices using iso-value. The normal vector on a surface point is calculated using central differences. The Marching Cubes algorithm is reused for binary cells (exactly two different classifications within a cell) with some modifications. For the classification of a vertex the classification function is used, which returns which basin a point belongs to. As only classification information is available, we can also not calculate the position of the surface point and the normal vector with the original methods. The position of a point is always located in the middle of an edge, since we have no information about the exact position from the surrounding classifications. This leads to coarse surfaces, which can be improved with surface smoothing. A more accurate position of a surface point can be estimated by checking the classifications along an edge, but it is more costly. The normal vector of a point is calculated from the location of the corresponding triangle, resulting in a single normal vector per triangle. This is sufficient information for flat shading, which is also sufficient for the basin boundary visualization.
 

For the triangulation of generally classified cells (more than two different classifications within a cell) the cell is disassembled into several binary classified cells. These binary cells contain only vertices with identical and adjacent classifications from the general cell, the remaining vertices are assigned to a so-called not defined region. These binary cells are independently triangulated with the modified Marching Cubes algorithm. The triangulation of a general cell is the combination of the triangulations of its binary dissection. This triangulation approach for generally classified cells raises the problem of not defined regions and duplicate triangles. Not defined regions are visible at lower resolutions, but are nearly invisible at higher resolutions. On the other hand their appearance informs the user, that more detailed information on the junction of several regions is not available. The duplicate triangles are caused by opposite but similar Marching Cubes cases at the boundary. The duplicate triangle has to be removed and the colors of the opposite triangle have to be updated. The advantages of this method are a fast surface construction because of the reuse of the Marching Cubes look-up table and its simplicity. Figure 1 shows an example for the surface construction of a generally classified cell with the modified Marching Cubes. The example leads also to a duplicate triangle.
 

The specified requirements like adaptive representation and progressive refinement are supported by an octree as a hierarchical data structure. An intermediate node with 8 child nodes represents every subdivision. The root node represents the whole data set as a cube. Therefore we have to transform the data set, since it has usually not the same extent in all dimensions. The data set, which has to be continuously defined in the domain, is transformed by scaling and translation into a cubic domain with the range 0 to 2^n. This domain makes both an easier subdivision and a fast calculation with just integer arithmetic instead of floating point possible. The cubic domain is used for the whole work within the octree like subdivision, surface construction, surface smoothing and so on. The domain is transformed into a domain with the original size relations for rendering. For efficiency the octree is replaced by an octree forest to achieve a minimum starting subdivision and in order to avoid the traversal of these first levels. The octree forest is a three-dimensional array (currently 8x8x8) with references to the corresponding root nodes of shorter octrees.

The classifications of the vertices have to be stored for reuse, because of expensive classification functions. The storage in an array is inefficient, because of the adaptive representation. Therefore the classifications are stored within the cell in a compact way. For efficiency several types of leaf nodes are distinguished. There are simple and complex leaf nodes. A simple leaf node has the same classification at all vertices and contains therefore no surface. Most of the leaf nodes are simple leaf nodes and can be stored with only one classification. A complex leaf node contains at least two different classifications and therefore a part of the surface. A complex node can be further subdivided into binary and general leaf nodes. A binary (leaf) node contains exactly two different classifications, so we can store them with just two classifications and the corresponding Marching Cubes case index. All classifications have to be stored just for the general node with at least three different classifications. A complex node stores also a surface index to the triangles constructed within the cell for later replacement during progressive refinement. The distinction between different leaf node types results in big savings, since usually at least 90% of the leaf nodes are simple or binary leaf nodes.

Simple nodes are not further refined, since this would usually only result in more simple nodes. This method leads to savings because of fewer subdivisions and less memory consumption, but also to missed surface parts. Missed parts of a continuous surface can be found by surface tracking. For surface tracking all simple neighbours of a newly subdivided cell are checked. If a considered cell has an intersected edge, which is adjacent to the checked simple cell, also the simple cell must contain this intersection point and a surface part. Therefore such simple cells are subdivided until they have the same size as the considered cell. This method is restricted to surface parts, which are connected to surface parts already found, which is in most cases sufficient.

A drawback of an octree is a difficult or expensive access to neighbour cells of the current processed region. Therefore the leaf nodes of an intermediate node of the octree are stored in a three-dimensional array, which works like a cache for leaf nodes in a part of the octree. Every entry of the array refers to the corresponding leaf node. The number of entries for a leaf node depends on its size, therefore larger cells are represented by more entries than smaller ones. Further for every cell the reference point within an octree, the cell size respectively octree depth, the parent node and the child index are stored. This information is implicitly stored in the octree and can only be determined by an expensive traversal. The selection of the size of this array is essential for the efficiency, since only a part of the octree can be held in this cache. Therefore the array size is chosen to correspond to a progressive unit, an entity used by this approach for progressive refinement.
 

A more exact calculation of the curvature is expensive, because we have to calculate the angles between normal vectors of triangles of the investigated and adjacent cells. The curvature of the cell is related to the angle between own and adjacent triangles. This principle is reused, but every cell has only one representative normal vector. The curvature is now estimated by the minimum angle between the representative normal vectors of the considered and the adjacent cells. The representative normal vector of a cell is the average or normalized sum of the normal vectors of the vertices. The normal vector of a vertex is calculated by the technique for discrete surfaces from Thürmer et al. [21]. Vertices belong to the same surface, if they have the same classification and are not separated by other classifications.

The depth difference between the cell and a non-empty edge neighbour is larger than 1.

The cell cannot be triangulated neither with the Marching Cubes algorithm nor as an adaptive cell.

The faces of the cell contain more than two different classifications.

 

A cell is valid for Marching Cubes triangulation, if all faces

contain no intersection point at an inner edge.

contain at most one intersection point at each border edge.

At most 4 faces of 6 have intersection points.

Every inner or border edge contain at most one intersection.

Every face contains either 2 or no intersections at border edges.

Every sub face contains either 2 or no intersections.

 

The task of the adaptive triangulation is to connect the surfaces of adjacent cells, if the Marching Cubes algorithm cannot be applied. The closest intersection points on the faces of such a cell are connected in order to obtain a contour. The consistency criteria guarantee a closed contour, so the contour can be easily triangulated for surface construction. Figure 4 shows an example of an adaptive triangulation of a cell with smaller neighbours.

 

The principle of the progressive refinement is to generate intermediate models with increasing level of detail for viewing during the creation of more accurate data. The progressive refinement is supported by a successive subdivision and an adaptive representation. There are two combined types of progressive refinement, smooth and selective refinement. Smooth refinement generates many different models with different levels of detail in order to make smooth transitions between the models possible. The selective refinement chooses a new region in the octree for the next refinement depending on the current view direction. All changes in this section, the so-called progressive unit, and in adjacent cells are transmitted in one update. The progressive unit is a cube, which corresponds to an intermediate node of the octree.
 

The task of the geometry compression is a compact representation of the geometry. Geometry compression is usually lossy like in [5, 19, 22]. The discrete positions in the octree and the limited number of positions of intersection points within a cell make a lossless and compact representation for efficient storage and transmission possible. A vertex within a Marching Cubes cell can be stored in a compact way using the edge identifier, because there are only 12 edges within a cell (4 Bits). There are also 5 Bits necessary to store the shift (32 positions) of a vertex on the edge. The triangulation of a Marching Cubes cell can be stored with 7 Bytes (51 Bits) for the cell information and 5 Bytes (35 Bits) per triangle. The cell information consists of the cell position, the size respectively octree depth and the front and back side color. If we represent the triangles by its vertex positions then we need 38 Bytes per triangle for coordinates stored as floating point numbers or 20 Bytes per triangle for short (2 Bytes) numbers.

The compression can be further improved if we distinguish the compression of binary (2 different classifications) and general cells (more than 2 different classifications). For binary cells just one front and back side color has to be stored per cell. For general cells one front and back side color has to be stored per triangle. Similar savings can be achieved with adaptive triangulated cells. There are no normal vectors compressed or transmitted, since we calculate them from the location of the corresponding triangle at the client.
 

The domain boundary visualizes the basins on the surface between the inside and the outside of the specified data domain. The domain boundary can be considered as the cutting planes at the 6 faces of the cube represented by the root node of the octree. For the construction of the domain boundary the cell faces of leaf nodes at the border of the octree are used. A quadtree is used in order to combine smaller homogeneous faces for an adaptive representation also of heterogeneous cells. The domain boundary provides a better overall view of basins, since it shows also the first region corresponding to the current viewing direction, which cannot be recognized because of double-sided surfaces.

The exploration of data sets makes it also necessary to generate two-dimensional intersections with cutting planes. The creation of cutting planes is expensive, therefore a fast cutting plane preview is supported for the selection of desired intersection locations. The preview for orthogonal cutting planes is constructed from the classifications in the octree. The advantages are a reuse of expensive classifications and an adaptive representation of homogeneous regions. For the construction leaf nodes are used which are intersected by the cutting plane. The classifications of the closest vertices are projected onto the cutting plane. The influence of a classification on the cutting plane depends on the corresponding cell size. A classification has more influence in larger cells than in smaller ones.

The basin visualization is designed to support also the application over networks like the Internet. A surface-oriented approach is used instead of direct volume rendering, so the geometry have to be only once constructed and transmitted for a data set. Since the approach is view-independent no further information have to be transmitted over the network, if the view point changes. The progressive refinement of the approach makes also an early, low-resolution preview of the results possible. During progressive refinement only parts of the geometry have to be changed, so only these changes have to be transmitted. The normal vectors of triangles do not have to be transmitted, since they can be calculated from the position of the triangles. The normal vectors have to be calculated at the client, which is a drawback at slow clients. The network traffic can also be reduced by the compact, symbolic representation of the geometry. It has the same drawback as the savings from the normal vector calculation, since the calculation of the necessary geometry representation has to be performed at the client.
 

 
Image 1 shows the presented surface extraction applied on the dynamical system Game3D [1]. The smaller basins are opaque and the larger surrounding basins are transparent displayed.
 

Image 2 shows the surface extraction without and with activated surface smoothing for an artificial data set. The resulting smoothed image is not completely correct, but it is a fast approximation.

 

Image 3 shows the second dynamical system of Image 1 with a smaller function domain and a transparent and an opaque domain boundary.

 

Image 4 shows a preview of a cutting plane through the dynamical system Quad3D, which is from the authors of Game3D. The preview is much faster than a calculation of the cutting plane with the same resolution.
 

 
Lukas Mroz, Helwig Hauser, Robert. F. Tobler, “Master” Eduard Gröller. This work was supported by the BandViz project [2].