Framework for Interactive Massive Volume Visualization
From Anita Borg Institute Wiki
Commodity hardware clusters offer a cost-effective solution to visualization of massive data sets. Many challenges must be overcome in adapting existing visualization techniques and managing data for distributed parallel rendering. In this dissertation, we present a framework and algorithms for this purpose.
Region growing is a segmentation algorithm that expands on a user supplied seed voxel to find a region of interest. However, this algorithm is limited to small data sets, so we introduce out-of-core region growing, which processes a slab of consecutive data slices at a time. We also introduce the slab-projection slice to encrypt empty space information so that data slices are not needed in main memory for further preprocessing steps. These are used in our kd-tree partitioning, bricking and moving walls algorithms.
Parallel ray casting is accomplished by independently rendering portions of a scene and compositing the images together. Load balanced network distribution (LBND) is the NP-complete optimization problem of partitioning volumetric data for distribution across a cluster to achieve good load balancing for parallel ray casting. We introduce two dynamic programming (DP) solutions to the LBND problem. One, brick grouping DP, finds a view-dependent partition from a directed acyclic graph of bricks. The other, moving walls DP, finds a view-independent partition of cells which contain a combination of empty space and cropped subvolumes.
Ray tracing is used to enhance rendering realism with global illumination. It is similar to ray casting, except that additional rays are spawned at ray-object intersection points to approximate reflected, refracted and shadow rays. A ray segment is the intersection of a ray with a scene cell, and the set of these defines a tree of ray-cell dependencies. The order in which ray segments are processed impacts rendering time. We introduce the cell-tree, a concise representation of ray-traversal dependencies, and cell-tree peeling, a dependency graph ray task scheduling algorithm for ray tracing that runs in parallel with ray tracing process cycles. Our algorithms have been designed to be independent of any specific system configuration and have been verified with several large high resolution volumetric data sets on the Stony Brook Computing Cluster.
