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
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.