Internet-Based Visualization of Basin Boundaries
for Three-Dimensional Dynamical Systems
Institute of Computer Graphics
Vienna University of Technology
Vienna / Austria
2. Surface Extraction
2.3 Surface Smoothing
3. Adaptive Surface
Heuristic Curvature Estimation
Efficient Geometry Representation for Storage and Transmission
Surface Construction Algorithm
Boundary & Cutting Plane Preview
5. Web-Based Application
One application of surface-oriented visualization of volume data is
the construction of surfaces between two different regions of the volume
(e.g. iso-surfaces). For some applications, a binary subdivision of the
volume is not sufficient, for instance for the representation of basin
boundaries in the phase space of dynamical systems. Basins describe regions
with the same long-time behaviour. An extension of the known Marching Cubes
algorithm is introduced, which works both with binary and generally classified
(at least three different classifications within a cell) data sets. For
faster surface construction the original look-up table of the Marching
Cubes algorithm is used. The algorithm supports both progressive refinement
of surfaces by binary subdivision of data cells and smooth transitions
between models, which are differently refined. The adaptive subdivision
depends on the local properties of the surface. Binary subdivision for
refinement of regions leads to a coarse representation of the surface,
therefore the vertices of the triangles are relocated after the surface
construction depending on the classifications of adjacent cells, in
order to smooth the surface.
Keywords: dynamical systems, non-binary
classification, adaptive representation
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.  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. . 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 . 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.
Following requirements for basin boundary visualization can be listed:
• Fast surface construction for generally
classified regions [4, 11, 16]
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.
• Adaptive and efficient model representation
[3, 10, 13, 15, 18, 24]
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.
• Selective and smooth progressive refinement
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.
• Web-based interactive application [7,
8, 9, 14]
The use of the Internet
is also connected with a limited bandwidth for data transmission, so we
have to reduce the data required to describe a model as far as possible.
Therefore a compact data representation for the transmission is necessary
and only the changes between different models with increasing level of
detail are transmitted.
The basin visualization
is implemented in the platform-independent programming language Java (JDK
1.2) with its 3D-extension Java 3D (Java 3D 1.1.1 Beta 1 for Direct X)
which can be used for providing 3D-graphics over the Internet .
2. Surface Extraction
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 
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.
2.1 Binary Classified
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.
2.2 Generally Classified
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.
Figure 1 Example of general triangulation with duplicate
2.3 Surface Smoothing
results of the modified surface extraction are coarse, since the vertices
are always located in the center of an intersected edge. The shape of the
surface around a vertex is influenced by the positions of other vertices.
Therefore a vertex can be relocated depending on the surrounding classifications.
A vertex on an intersected edge is influenced by the vertices in cells
sharing this common edge. Parallel edges have only a small influence, because
they do not attract connected triangles (Figure 2a). Orthogonal edges attract
triangles in their direction and cause higher curvature at the considered
vertex (Figure 2b). This attraction has to be compensated in order to get
a smoother transition. Therefore the vertex is shifted in the direction
of an intersected edge. Two intersections in different directions neutralize
each other, since every intersection is connected with relocation in its
direction (Figure 2c). Each edge is connected with 4 cells and is influenced
by 8 edges, 4 in positive and 4 in negative direction. The shift for an
edge is relative to the sum of the intersections with a sign depending
on their direction. The shift for an edge can also be scaled by a user-definable
factor in order to adjust the influence. This approach is a fast and simple
method to smooth the surface influenced by the surrounding classifications.
Figure 2 Principle of Surface Smoothing
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
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.
3.1 Adaptivity Criteria
The goal of the adaptive
representation is to represent sections with a level of detail, which depends
on the local shape (curvature) of the surface. Therefore fast heuristic
curvature estimation is used as well as consistency criteria, which guarantee
a simple and fast triangulation and connection between adjacent cells with
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. . Vertices belong to the same surface, if they have the same
classification and are not separated by other classifications.
3.1.2 Consistency Criteria
consistency criteria guarantee a simple and fast connection between cells
with different sizes and a compact representation, since this is a common
problem for all adaptive approaches. The criteria do not have to be considered
for cells, which have only direct neighbours with the same size, since
a valid triangulation is possible with the Marching Cubes algorithm. For
the check of the consistency criteria the 6 faces of a cell are considered.
The different parts of a cell face with smaller neighbours are shown in
Figure 3 Face part designation of a cell face with smaller
A non-empty cell has to be
subdivided, if any of the following rules is met.
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.
A cell is valid for adaptive
triangulation, if all following rules are met.
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.
Figure 4 Example of an adaptive triangulated cell
3.2 Progressive Refinement
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.
Efficient Geometry Representation for Storage and Transmission
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 following pseudo
code describes the principle of the surface construction and all its connected
techniques. Details about the techniques are described in the previous
or following sections. The desired level of detail is controlled by a maximum
number of subdivisions.
IF (all progressive units refined)
IF (desired level of detail) stop refinement;
ELSE restart refinement;
ELSE select progressive unit depending on view direction;
FOR (all leaf nodes within progressive unit) /* Refinement */
IF ((leaf node is general node) OR
((leaf node is binary node) AND
(curvature(leaf node) >= maximum curvature))
subdivide leaf node;
surface tracking in non-empty children of subdivided leaf node;
check consistency with neighbours;
FOR (all leaf nodes within progressive unit) /* Surface extraction */
surface construction within leaf node;
surface smoothing within leaf node;
if (leaf node is on the edge of the domain)
construct domain boundary part from leaf node;
transmit the symbolic surface representation of changed cells;
Domain Boundary & Cutting Plane Preview
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 Results of the surface extraction for dynamical system
Game3D with different parameters
Image 1 shows the presented surface extraction applied on the dynamical
system Game3D . 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 2 Artificial data set without and with surface smoothing
Image 3 shows the second
dynamical system of Image 1 with a smaller function domain and a transparent
and an opaque domain boundary.
Image 3 Transparent and opaque domain boundary for dynamical system
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.
Image 4 Preview and original cutting plane of dynamical system
For boundary visualization of generally classified regions a modified Marching
Cubes algorithm as surface extraction technique was introduced. For triangulation
generally classified cells are subdivided into several binary cells. The
surface construction is fast, because of reusing the original Marching
Cubes look-up table. A surface smoothing method is used to smooth the coarse
Marching Cubes surface, which is caused by the selection of triangle vertices
in the center of an edge of a cell. An octree is used for adaptive representation
of homogeneous sections of the data sets. Classifications evaluated at
cell vertices by an expensive classification function are stored in the
octree in a compact way. For a better overall view of the visualization
the boundary at the border of the octree is constructed. The octree is
also used to construct a fast preview of an intersection of an arbitrary
orthogonal cutting plane with the data set in order to select interesting
locations for a cutting plane. Further information about the basin visualization
project is available at http://www.cg.tuwien.ac.at/~wallisch/da/.
Lukas Mroz, Helwig Hauser, Robert. F. Tobler, “Master” Eduard Gröller.
This work was supported by the BandViz project .
H. N., Bischi, G. I., Kopel, M., "Multistability in a Dynamic Cournot Game
with Three Oligopolists", Mathematics and Computers in Simulation 51, 1999,
pp. 63 - 90.
J., "Polygonization of Implicit Surfaces", Computer Aided Geometric Design,
Volume 5, 1988, pp. 341 - 355.
J., Ferguson, K., "Polygonization of Non-Manifold Implicit Surfaces", Proceedings
of SIGGRAPH '95, Computer Graphics Annual Conference Series, 1995, ACM
SIGGRAPH, pp. 309 - 316.
M. M., "Optimized Geometry Compression for Real-time Rendering", IEEE Visualization
'97, 1997, pp. 347 - 354.
H. E., Lorensen, W. E., Ludke, S., Crawford, C. R., Teeter, B. C., "Two
algorithms for the three-dimensional reconstruction of tomograms", Medical
Physics, Volume 15, Number 3, June 1988, pp. 320 - 327.
T. T., Jain, R., "Web-based Volumetric Data Retrieval", 1995 Symposium
on the Virtual Reality Modeling Language (VRML '95), ACM Press, 1996, pp.
7 - 12.
K., Grosso, R., Ertl, T., "Progressive Iso-surfaces on the Web", Late Breaking
Hot Topics, IEEE Visualization, 1998.
K., Westermann, R., Ertl, T., "Isosurface Extraction Techniques for Web-based
Volume Visualization", IEEE Visualization 1999, San Francisco, USA, pp.
139 - 146.
R., Greiner, G., "Hierarchical Meshes for Volume Data", Proceedings Computer
Graphics International '98, 1998, Hannover, Germany, pp. 761 - 769.
H.-C., Seebaß, M., Stalling, D., Zöckler, M., "A Generalized
Marching Cubes Algorithm Based On Non-Binary Classifications", Technical
Report SC-97-05, Konrad-Zuse-Zentrum für Informationstechnik (ZIB),
W. E., Cline, H. E., "Marching Cubes: A High Resolution 3D Surface Construction
Algorithm", ACM Computer Graphics, Volume 21, Number 4, July 1987, pp.
163 - 169.
C., Ertl, T., "Adaptive Iso-surface Generation", 3D Image Analysis and
Synthesis '96, Graduiertenkolleg 3D Bildanalyse und Synthese, 1996, pp.
183 - 190.
L., Löffelmann, H., Gröller, E., “Bringing Your Visualization
Application to the Internet”, Technical Report TR-186-2-98-14, Institute
of Computer Graphics, Vienna University of Technology, April 1998.
H., Stark, M., "Adaptive Generation of Surfaces in Volume Data", The Visual
Computer, 9(4), 1993, pp. 182 - 199.
G. M., Franke, R., "Computing the Separating Surface for Segmented Data",
IEEE Visualization '97, October, 1997, pp. 229 - 233.
H.-O., Jürgens, H., Saupe, D., "Chaos and Fractals: New Frontiers
of Science", Springer-Verlag, 1992.
R., Fayyad, E., Yagel, R., Cornhill, J., "Octree-Based Decimation of Marching
Cubes Surfaces", Visualization '96, 1996, pp. 335 - 342.
G., Wüthrich, C. A., "Normal Computation for Discrete Surfaces in
3D Space", EUROGRAPHICS '97, Volume 16, Number 3, 1997, C-15 - C-26.
C., Gotsman, C., "Triangle Mesh Compression", Proceedings Graphics Interface
'98, 1998, pp. 26 - 34.
B., “Internet-Based Visualization of Basin Boundaries for Three-Dimensional
Dynamical Systems”, Master Thesis, Vienna University of Technology, 2000.
R., Kobbelt, L., Ertl, T., "Real-Time Exploration of Regular Volume Data
by Adaptive Reconstruction of Iso-Surfaces", The Visual Computer, 15(2),
1999, pp. 100 - 111.