Data Structure Optimizations for Cryosection Images

by Arthur Kantor and Ladd Van Tol


Introduction

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.

Data Organization

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.

Performance Testing

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.

Ray Tracer

Unfortunately, the ray tracer wasn't entirely finished by the end of the project, but the initial results are promising. Currently, the ray tracer has several visual flaws, but is producing somewhat usable results. We haven't been able to make any meaningful performance analysis, but the speed is quite reasonable, and could be improved with additional optimization work.


Questions/Comments:

Arthur Kantor: kantor@cs.wisc.edu

Ladd Van Tol: ladd@beale.com