A Frequency-Sensitive Point Hierarchy

Tomihisa Welsh Klaus Mueller

(a) Orig. 2,608,070 pts (9 sec) (b) 951,291 pts (3 sec) (c) 195,854 pts (0.5 sec) (d) 79,007 pts, (0.2 sec)
Figure 1. The engine dataset (256^3), rendered semitransparent without occlusion culling at various error thresholds with our algorithm.


This project introduces a method for converting an image or volume sampled on a regular grid into a space-efficient irregular point hierarchy. The conversion process retains the original frequency characteristics of the dataset by matching the spatial distribution of sample points with the required frequency. To achieve good blending, the spherical points commonly used in volume rendering are generalized to ellipsoidal point primitives. Our approach uses a family of multiresolution, oriented Gabor wavelets to provide the frequency-space analysis of the dataset. The outcome of this frequency analysis is the reduced set of points, in which the sampling rate is decreased in originally oversampled areas. During rendering, the traversal of the hierarchy can be controlled by any suitable error metric or quality criteria. The local level of refinement is also sensitive to the transfer function. Areas with density ranges mapped to high transfer function variability are rendered at higher point resolution than others. Our decomposition is flexible and can be used for iso-surface rendering, alpha compositing and X-ray rendering of volumes. We demonstrate our technique by implementing an interactive volume renderer using a splatting algorithm, in which the traversal of the point hierarchy for rendering is modulated to maintain a user-specified frame rate.



For images, we use 2D elliptical Gaussians as the point primitive oriented in four quantized directions and scaled to any size. We do not compare our results to standard image compression algorithms such as JPEG, since the main goal of our system is to create a point hierarchy system and not image compression. However, images are a good way of demonstrating how the data is decomposed using frequency analysis.

(a) Orig. Lena Image (262,144 pts) (b) 85530 pts (c) 45616 pts (d) Ellipses used as primitives
Figure 2. The Lena image (512^2). The main effect of compression is blurring. (d) Note, these are at a higher threshold than the images for demonstration purposes


(a) Orig. volume (1,779,610 pts) (b) 877318 pts
Figure 3. A head volume rendered with half as many points but an unnoticable difference in quality.

(a) Orig. volume (1,779,610 pts) (b) 551950 pts (c) 219997 pts
Figure 4. A head volume rendered with an X-Ray algorithm.


We have implemented a rendering system which permits time-critical volume rendering and progressive refinement of the image. Based on a history of previous frame-rates, the system adjusts the error threshold to achieve a specified frame rate to maintain a user-selected frame rate. When there is no motion, the system progressively refines the image by lowering the error threshold and consequently increasing the number of points in the representation.

IEEE Visualization 2003 Paper (3.0 Mb)
Video (6.73 Mb) (Requires DivX codec)