Data-Driven Space-Filling Curves

Abstract

Abstract-We propose a data-driven space-filling curve method for 2D and 3D visualization. Our flexible curve traverses the data elements in the spatial domain in a way that the resulting linearization better preserves features in space compared to existing methods. We achieve such data coherency by calculating a Hamiltonian path that approximately minimizes an objective function that describes the similarity of data values and location coherency in a neighborhood. Our extended variant even supports multiscale data via quadtrees and octrees. Our method is useful in many areas of visualization including multivariate or comparative visualization ensemble visualization of 2D and 3D data on regular grids or multiscale visual analysis of particle simulations. The effectiveness of our method is evaluated with numerical comparisons to existing techniques and through examples of ensemble and multivariate datasets.

Fig. 1.

Visualizations of an ensemble of volumetric data. The key idea is to employ a mapping from 3D space (as in the volume renderings) to 1D space via space-filling curves, which then allow us to show boxplots of the data distributions. The ensemble is generated by sampling from Gaussian distributions of data values in the nucleon data with varying extents of uncertainty. The boxplots of the ensemble linearized with the Peano-Hilbert curve (bottom) do not preserve the coherency of 3D features—the small torus structure of high intensity cannot be readily identified. In contrast, our data-driven space-filling curve method (top) preserves features from 3D even in the 1D linearized representation as high intensities are more concentrated. This observation is confirmed by brushing-and-linking—the torus could be covered by one brush and its surroundings with two brushes with our method (see the volume rendering on the right and the yellow and purple regions in “Data-driven space-filling curve”), whereas multiple brushes are required by the Peano-Hilbert curve (yellow and purple regions in “Peano-Hilbert curve”).

Fig. 2.

A 2D multiscale graph G = (V, E, L) on a quadtree with a Hamiltonian path P_min.

Fig. 3.

(Left) A 2D graph on a regular grid G = (V, E, 1) with corresponding data values (black = 0, red = 1), and its associated circuit graph G_c (right) of circuits C. Adjacent circuits of C_i are drawn in light blue. The edge weights of data values between circuits C_i and C_j are shown on the right.

Fig. 4.

Intermediate steps of the framework of [5] on 2D regular grids. The dual graph $G_c^{\prime }$. (a) of circuits graph G_c is a directed graph with our new weights (labeled on edges). Then, the minimum spanning tree (b) is found on the dual graph. Next, the Hamiltonian cycle is generated by merging circuits using the minimum spanning tree (c). Finally, (d) the Hamiltonian cycle is converted into a Hamiltonian path by making a cut anywhere on the cycle (shown as X).

Fig. 5.

$G_c^{\prime }$ is partitioned (the blue dash-dot line) into blocks denoted by their centers (e.g., $S_{C_i}$ and $S_{C_j}$) to accommodate the new positional term of the objective function.

Fig. 6.

Comparison of linearization methods applied to a slice of the nucleon dataset (a). Our new data-driven space-filling curve is compared to previous methods: the context-based space-filling curve, the Peano-Hilbert curve, and scanline ordering. The spatial layout of the respective curves is shown in (b), and the linearization of the data values in (c). The spatial layout (b) is colored by the traversal order of curves (the horizontal axis of (c)) with the parula colormap (right of (b) Ours). Autocorrelations of value (d) and radial distance (e) quantify data coherency and locality preservation, respectively. The plots show that our approach provides the best compromise between the two conflicting goals. Note that the autocorrelations of data values of our method and the context-based method are largely overlapping.

Fig. 7.

The effect of different α (left–right: 0, 0.01, 0.03, 0.1, 0.3, and 1.0) on the scan order of our space-filling curves for the nucleon slice data (left). The order is color-coded using the same color map as in Fig. 6.

Fig. 8.

Linearizations (top) of a synthetic volume data of a sphere (left) with our data-driven curve, the Peano-Hilbert curve, and scanline ordering. The scan orders of curves are shown in the bottom row.

Fig. 9.

The value weights of cubes on 3D regular grids (a). The cubes need to be converted into cycles during merging. There exist (b) six cycle configurations of a unit cube, and the cycles are merged with (c) two association rules.

Fig. 10.

Steps to compute a data-driven space-filling curve for multiscale data.

Fig. 11.

Flexible Hamiltonian paths for 2D and 3D grid graphs. Exit sides are on the (a) right and (b) left for these examples of 2D graphs. The example 3D graph has exit faces on the (c) left and at the (d) top.

Fig. 12.

Data-driven space-filling curves for quadtree and octree. The input data are shown in the first column, the linearizations in the second column, and the spatial configurations of the space-filling curves in the third column.

Fig. 13.

Autocorrelations of data value (first column) and radial distance (second column) for our 2D techniques (first row) and our 3D techniques (second row). Note that larger autocorrelation means better coherency.

Fig. 14.

Visualization of an SPH simulation of dam break: (a) rendering of particles with brushed regions, (b) multivariate line charts generated using our octree-based data-driven space-filling curve.

Fig. 15.

Visualization of a brain atlas with our data-driven space-filling curve and a Peano-Hilbert curve (with images padded to size of 256 × 256 with zeros). The median image (bottom) and an outlier image (top) are shown in (a) with brushing-and-linking (purple box) on the space-filling curves (b, center). The 1D layout with the space-filling curve allows for easy interaction, including brushing and zooming on spatial details, and it supports rendering boxplots that separate the brain from its surrounding and show that the outlier has wider low-value regions than the band at the lateral ventricle (red curves in the gray boxes in the zoom-in).

Fig. 16.

Ensemble visualizations of a heart ischemia simulation. The median member is volume-rendered in (a)—with 1D functional boxplots linearized with (b) our data-driven space-filling curve (top) and a Peano-Hilbert curve (bottom). The ischemic region that has potential value greater than 3 eV is selected in the boxplots and highlighted in (c).