Extraction of Intersection Curves from Iso-surfaces on Co-Located 3D grids

Patric Ljung
Scientific Visualization Group, Department of Science and Technology, Linköping University, Sweden

Anders Ynnerman
Scientific Visualization Group, Department of Science and Technology, Linköping University, Sweden

Ladda ner artikelhttp://www.ep.liu.se/ecp_article/index.en.aspx?issue=010;article=006

Ingår i: The Annual SIGRAD Conference. Special Theme - Real-Time Simulations. Conference Proceedings from SIGRAD2003

Linköping Electronic Conference Proceedings 10:6, s. 23-28

Visa mer +

Publicerad: 2003-11-20


ISSN: 1650-3686 (tryckt), 1650-3740 (online)


This paper presents new methods for efficient extraction of intersection curves between iso-surfaces of any pair of co-located 3D scalar fields. The first method is based on the Marching Cubes algorithm which has been enhanced to produce an additional data structure that makes it possible to reduce the complexity of the general surface intersection extraction from O(N2) to O(vN); where N denotes the number of triangles in the arbitrary surfaces. The second method directly extracts the intersection lines based on finding intersection points on the faces of the voxels for two iso-surfaces extracted from a regular grid. A simple classification scheme is used for early termination of testing of voxels that are not intersected by both surfaces.

Also presented is an efficient method for fast curve generation through combination of line segments resulting from the explicit surface intersection method. An indexing structure is used to accelerate access and matching of intersection line segments to be combined into closed or open curves.

The presented methods have been used to identify and visualize nodal lines in 3D quantum and wave chaos data. These data are represented by a volume of complex values and a nodal line is a connected curve where the complex iso-value ziso = 0 + i0. This type of chaos is believed to represent physical phenomena present in; for example; quantum mechanics; microwaves; fibre optics; and acoustics.

CR Categories: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—Boundary representations; Geometric algorithms; I.3.6 [Computer Graphics]: Methodology and Techniques—Graphics data structures.


Intersection curves; Isosurfaces; Surface intersection; Feature Detection; Nodal lines visualization; Complex 3D fields


BERRY; M. V. 1977. Regular and irregular semiclassical wave functions. Journal of Physics A 10; 2083–2091.

KRISHNAN; S.; AND MANOCHA; D. 1997. An efficient surface intersection algorithm based on lower-dimensional formulation. ACM Transactions on Graphics 16; 1 (January); 74–106.

LIVNAT; Y.; SHEN; H.-W.; AND JOHNSON; C. R. 1996. A near optimal isosurface extraction algorithm using the span space. IEEE Transactions on Visualization and Computer Graphics 2; 73–84.

LORENSEN; W. E.; AND CLINE; H. E. 1987. Marching cubes: A high resolution 3D surface construction algorithm. In Proceedings of SIGGRAPH ’87; ACM Press; 163–169.

MONTANI; C.; SCATENI; R.; AND SCOPIGNO; R. 1994. A modified lookup table for implicit disambiguation of marching cubes. Visual Computer 10; 6; 353–355.

PARKER; S.; SHIRLEY; P.; LIVNAT; Y.; HANSEN; C.; AND SLOAN; P.-P. 1998. Interactive ray tracing for isosurface rendering. In Proceedings of IEEE Visualization ’98.

PATRIKALAKIS; N. M. 1993. Surface-to-surface intersections. IEEE Computer Graphics and Applications 13; 1 (January); 89–95.

SABHARWAL; C. L. 1994. A fast implementation of surface/surface intersection algorithm. In Proceedings of the 1994 ACM symposium on Applied computing; ACM Press; 333–337.

STÖCKMANN; H.-J. 1999. Quantum Chaos: An Introduction. Cambridge University Press; Cambridge; UK.

THIRION; J.-P.; AND GOURDON; A. 1996. The 3D Marching Lines algorithm. Graphical Models and Image Processing 58; 6 (November); 503–509.

WILHELMS; J.; AND GELDER; A. V. 1992. Octrees for faster isosurface generation. ACM Transactions on Graphics 11; 201–227.

ZOCKLER; M.; STALLING; D.; AND HEGE; H.-C. 1996. Interactive visualization of 3d-vector fields using illuminated stream lines. In Proceedings of IEEE Visualization ’96; IEEE Computer Society; 107–113;474.

Citeringar i Crossref