Our project examines the performance impact on volumetric rendering, and other applications of the cadaver data of various data organizations of cryosection images from the Visible Human Project, with a focus on improving ray tracing performance.
One of the first options considered was to simply break the entire data set into a collection of fixed size cubes. This was rejected, as certain directions of data access through the cube would be slower than others.
The second option considered was the idea of octtrees, a three-dimensional extension of the quadtree. The octtree successively splits cubic areas of space, until the entire spatial volume is represented. In data structure terms, this can be stored as a tree, with each node having 8 children, representing the cube's 8 subcubes. This approach offers several notable benefits -- first and most importantly, flattened representations of octtrees keep spatially adjacent areas physically adjacent on the disk. Additionally we have a large amount of black space surrounding the cadaver. The black space, as well as any other contiguous cubes of solid color, can be compactly represented in an octtree data structure.
After considerable analysis various options of octtree organization, we finally decided on a hybrid tree structure approach that would represent the top layers of the tree in a linked structure, while placing the bottom layers in "branch files" -- a flattened representation of an octtree branch.
Once we had completed a lengthy stint of debugging, and sanity checking of the octree data, we were able to test our results, by writing a small program to pull arbitrary slices out of the octtree dataset. After a great deal of optimization work, we managed to get the octtree slicer to run consistently 20% faster than the original dataset slicer. On off-axis slices, the octtree slicer performed even better, running in less than one tenth of the time.
Arthur Kantor: email@example.com
Ladd Van Tol: firstname.lastname@example.org