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 my research, I have developed 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 I have introduced out-of-core region growing, which processes a slab of consecutive data slices at a time. I have also developed 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 for kd-tree partitioning, bricking, and the 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. I have introduced 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. I have created 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. Algorithms in this research 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.