Basin Boundary Visualization for 3D Dynamical Systems

Master Thesis Internet-Based Visualization of Basin Boundaries for Three-Dimensional Dynamical Systems Bernd Wallisch

Problem Statement
Surface Extraction
Adaptive Representation
Cutting Plane Preview & Domain Boundary
Web-Based Application
Resulting Images
References
Related Links

A more detailed description of this topic for CESCG 2000 is also available.

The basin visualization system can be tested at the following Applet.

.

Required: Browser (Internet Explorer 5.0 or higher, or Netscape Communicator 6.x), a Java Plugin (JRE 1.3.1 or higher) and Java 3D (1.2 or higher).

Remarks: The Applet takes a lot of memory and calculation time with increasing Level of Detail. Therefore VM parameter "-Xm256m", i.e. 256 MB memory, has to be added to the Java Plugin Control Panel in section "Standard", in order to provide enough memory. This value can be increased and decreased, but it restricts the desired maximum Level of Detail. The used browser has also to be activated in section "Browser". The Applet has approximately 400 kB!

Problem Statement

The long-time behaviour of dynamical systems is described by attractors. Adjacent points, which have the same attractor, build regions or so-called basins of attraction. For the visualization it is necessary to construct the boundaries between these basins of attraction, i.e. boundaries, which separate regions with different long-time behaviour. This approach is restricted to three-dimensional dynamical systems. For the classification of a point, i.e. to which attractor the point belongs to, there be in general no analytical solutions, therefore a point has to be experimentally classified for instance with many iterations. Therefore the classification of a dynamical system is expensive in general and provides no further information, like the distance from a classified point to the boundary. Classifications should be stored for later reuse and the number of subdivisions of a region should be adaptive depending on the local shape, in order to avoid unnecessary refinement, because of expensive classification functions. This approach is not just restricted to dynamical systems. All data sets, which can be continuously described by binary or general classifications, can be visualized with this approach. Basins of the same attractor have the same color.

Surface Extraction

For surface construction of the boundary the Marching Cubes algorithm is used. The Marching Cubes algorithm is originally designed just for binary classified cells, but is also used for generally classified cells. A cell is binary classified, if it contains exactly 2 different classifications on its 8 vertices. A cell is generally classified, if it contains three or more different classifications. Just binary and general cells contain surfaces. For the triangulation of generally classified cells the cells are disassembled into several binary cells. These binary cells are independently triangulated. The triangulation of a general cell is the combination of the triangulations of its binary cells. This approach leads to a not defined region at the junction of more than two different regions, which indicates that it is not more accurate information available about this region. The size of the not defined region decreases with increasing level of detail. The advantage of this surface extraction method is a fast and simple construction and the reuse of the look-up table of original Marching Cubes. The normal vectors and the exact location of a surface point cannot be calculated with the usual method, since only classifications are available at the cell vertices. Therefore the normal vector is calculated from the location of the resulting triangle. The network traffic can be decreased, if the normal vector is calculated at the client. This method is sufficient for the "low-quality" flat shading, which is adequate for the basin boundary visualization. The position of a surface point is always located in the center of an intersected cell edge. This position choice leads to a rather coarse surface, which can be improved with surface smoothing. The principle of surface smoothing is to relocate a surface point depending on the classifications of adjacent cells. A more accurate method to approximate the exact position of a surface point is to check the classifications along a considered edge. This method returns the best results, but is much more expensive. The constructed surface consists of double-sided triangles with different front and back side colors, since the surface displays always the color of the region behind it.

Adaptive Representation

The adaptive representation of data sets is realized with an octree. For compact classification storage there are three leaf node types distinguished depending on the number of different classifications within a cell. Simple leaf nodes store only one classification and contain no surface. Binary leaf nodes store exactly two and general leaf nodes store 8 classifications. The refinement of a cell depends on the type of a leaf node and adjacent cells by estimation of curvature and the fulfilment of consistency criteria. Simple (empty) nodes are just subdivided, if they are intersected by a surface of an adjacent non-empty cell, such a kind of local surface tracking. Rare general nodes are always subdivided, in order to minimize the error of not defined regions. Binary nodes are subdivided, if the curvature respectively angle with adjacent cells is to high or the consistency criteria are not met. The consistency criteria guarantee easy and fast connection between cells with different sizes and compact representation for storage and transmission. The refinement of a cubic cell is performed by a subdivision into 8 equal-sized subcubes. The constructed triangles are stored in a symbolic, compact way, supported by a limited number of positions of surface points (triangle vertices). The progressive refinement is controlled by the current view direction, in order to subdivide regions first, which can be currently seen by the user. After a refinement the changes are just transmitted to the client (user).

Cutting Plane Preview & Domain Boundary

A domain boundary is used, in order to get a better overall view of the basin boundaries, since they are double-sided with different colors. The domain boundary is the surface at the edge respectively face of the octree. For the exploration of dynamical systems it is also necessary to construct cutting planes of the intersection of orthogonal planes with the data set. The construction of a cutting plane with a higher resolution is also expensive and not interactive, because of the expensive classification function. Therefore a fast preview is provided, which reuses the stored classifications in the octree, in order to select a position for calculation of the complete cutting plane. The closest classifications of intersected leaf nodes of the octree are projected onto the cutting plane. The advantage of this approach is the reuse of expensive classifications of the octree and the adaptive representation of homogeneous regions. The preview of a cutting plane is at least 5 to 10 times faster as the complete cutting plane and makes also fast animations of a moving cutting plane possible.

Web-Based Application

The basin visualization was designed to support also the application over networks like the Internet. A surface-oriented approach was used instead of direct volume rendering, so the geometry have to be 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.

Essential References

Agiza, 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.

Cline, 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.

Engel, K., Grosso, R., Ertl, T., "Progressive Iso-surfaces on the Web", Late Breaking Hot Topics, IEEE Visualization, 1998.

Engel, K., Westermann, R., Ertl, T., "Isosurface Extraction Techniques for Web-based Volume Visualization", IEEE Visualization 1999, San Francisco, USA, pp. 139 - 146.

Hege, 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), 1997.

Lorensen, 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.

Müller, H., Stark, M., "Adaptive Generation of Surfaces in Volume Data", The Visual Computer, 9(4), 1993, pp. 182 - 199.

Nielson, G. M., Franke, R., "Computing the Separating Surface for Segmented Data", IEEE Visualization '97, October, 1997, pp. 229 - 233.

Peitgen, H.-O., Jürgens, H., Saupe, D., "Chaos and Fractals: New Frontiers of Science", Springer-Verlag, 1992.

Thürmer, G., Wüthrich, C. A., "Normal Computation for Discrete Surfaces in 3D Space", EUROGRAPHICS '97, Volume 16, Number 3, 1997, C-15 - C-26.

Wallisch, B., "Internet-Based Visualization of Basin Boundaries for Three-Dimensional Dynamical Systems", Master Thesis, Vienna University of Technology, 2000.