An Advanced Evenly-Spaced Streamline Placement Algorithm
(IEEE Transactions on Visualization and Computer Graphics, Vol. 12, No. 5 --- Special Issue on IEEE Vis'06, 2006, pp. 965-972)
Zhanping Liu
Robert J. Moorhead II
Joe Groner
rjm AT hpc DOT msstate DOT edu
bjg AT hpc DOT msstate DOT edu

Abstract: This paper presents an advanced evenly-spaced streamline placement algorithm for fast, high-quality, and robust layout of flow lines. A fourth-order Runge-Kutta integrator with adaptive step size and error control is employed for rapid accurate streamline advection. Cubic Hermite polynomial interpolation with large sample-spacing is adopted to create fewer evenly-spaced samples along each streamline to reduce the amount of distance checking. We propose two methods to enhance placement quality. Double queues are used to prioritize topological seeding and to favor long streamlines to minimize discontinuities. Adaptive distance control based on the local flow variance is explored to reduce cavities. Furthermore, we propose a universal, effective, fast, and robust loop detection strategy to address closed and spiraling streamlines. Our algorithm is an order-of-magnitude faster than Jobard and Lefer's algorithm with better placement quality and over 5 times faster than Mebarki et al.'s algorithm with comparable placement quality, but with a more robust solution to loop detection.

Index Terms: Flow visualization, evenly-spaced streamlines, streamline placement, seeding strategy, closed streamlines.

One problem with the use of streamlines is that an incomplete view (Fig. 1) or a cluttered display (Fig. 2) of the flow tends to be obtained unless an effective placement mechanism is adopted. A layout of evenly spaced (or uniform) streamlines may provide a visually pleasing as well as informative pattern to facilitate mental reconstruction of the flow. Our ADVESS (ADVanced Evenly Spaced Streamline placement) algorithm allows for fast high-quality evenly spaced streamline placement (Fig. 3 and Fig. 4).
Figure 1. An incomplete view where some saddles
Figure 2. A heavily cluttered image where a
Figure 3. Evenly spaced streamlines constituting an
Figure 4. Evenly spaced streamlines with a dense
are underrepresented while spirals cause cluttering.
saddle is still missing in the middle-right part.
elegant pattern to allow for inter-line interpolation.
background intended to enhance "interpolation".
Robust Loop Detection for Interactively Placing Evenly Spaced Streamlines
(IEEE Computing in Science and Engineering, Vol. 9, No. 4, 2007, pp. 86~91)
Zhanping Liu
Robert J. Moorhead II
zhanpingliu AT hotmail DOT com
rjm AT hpc DOT msstate DOT edu
Without an effective loop detection strategy, a placement of evenly spaced streamlines may be cluttered (Fig. 5) by closed or open but tightly spiraling streamlines, both loosely defined as loops herein. As opposed to some static, global, and computationally expensive loop detectors [1] [2], an ideal one for sample-based evenly spaced streamline placement needs to work in a dynamic, local, and interactive manner. In addition, it should be powerful enough to avoid loop-genic cluttering and artifacts while retaining important flow features such as closed streamlines and spiraling structures. Such a rapid robust loop detector (Fig. 6) is an integral component of our ADVESS algorithm.
Figure 5. The cluttering problem caused by some
Figure 6. The evenly spaced streamline placement
closed and open but tightly spiraling streamlines.
created by ADVESS with a robust loop detector.
ADVESS is so far the fastest algorithm for interactive (on a nowadays low-end laptop like HP-Compaq Presario / Intel Celeron 1.6GHz / 512MB SDRAM / Windows XP Home) high-quality placement of high-density (1% for 400 x 400 flow fields) evenly spaced streamlines coupled with robust loop detection (Fig. 7).
0.188 seconds for 319 streamlines
0.203 seconds for 388 streamlines
0.234 seconds for 378 streamlines
0.187 seconds for 327 streamlines
0.219 seconds for 387 streamlines
0.190 seconds for 335 streamlines
Figure 7. One-percent density evenly spaced streamline placements generated by using ADVESS with robust loop detection.

The application of evenly spaced streamlines to 3D exploration of volume flows, curved surface flows, and even planar flows in a perspective-view setting poses at least three challenges. The first problem is how to create a placement of streamlines such that they are indeed evenly spaced in 2D view space (the output image) because streamlines evenly spaced in 3D physical space (the flow field) may not visually retain the uniformity when projected to view space through a foreshortening transform. Thus view-dependency issues need to be considered to address incompleteness, cluttering, occlusion, and non-uniformity in the resulting image. The second challenge is how to maintain a smooth transition between two consecutive frames of evenly spaced streamlines for coherent flow exploration. This concern is critical for dynamic level-of-detail flow investigation as features may be missing in a static low-density placement or indiscernible in a static high-density layout due to the foreshortening effect. The third issue is how to find a fast universal mechanism, regardless of the data size or the grid type, to enable interactive placement of visually evenly-spaced streamlines for high-performance visualization of large flows defined on complex grids. To tackle the aforementioned problems, we presented IVDESS, an Interactive View-Driven Evenly Spaced Streamline placement algorithm, for coherent explorative flow visualization.

[1] T. Wischgoll and G. Scheuermann, "Detection and Visualization of Closed Streamlines in Planar Flows," IEEE Transactions on Visualization and Computer Graphics, Vol. 7, No. 2, 2001. pp. 165~172.
[2] H. Theisel, T. Weinkauf, H.-C. Hege, and H.-P. Seidel., "Grid-Independent Detection of Closed Streamlines in 2D Vector Fields," Proceedings of the 9th International Fall Workshop on Vision, Modeling, and Visualization (VMV'04), 2004. pp. 421~428.
Flow Visualization
Home Page