The program presents the user with two windows-- the smaller window has zoom and translation controls, and the larger window serves as both the output window and allows the user to easily and interactively rotate the block of data. I use an interactive rotation input system similar to the Volrend system's [Standish, 1995] virtual trackball. An actual screen image from the program is below.

The images have rulers which display millimeter distances, matched to the zoom factor. If the user drags the mouse inside the image window (labeled "Slice 3D") the block of data rotates beneath the mouse. If the user clicks the mouse in the image window, the program computes the 3D coordinates (in millimeters) of the clicked point on the slicing plane, and writes them to standard output. These coordinates could then be captured to a file and passed to another program for further analysis (e.g., for MRI geometric calibration, estimating the volume of a lesion, or planning a minimally harmful path for radiation treatment).

The importance of an intuitive and convenient user interface should not be overlooked-- a fast, elegant program which requires its input data to be submitted in batch form in base-13 Latin is useless to all but the most dedicated; while an easy-to-use, interactive program can be understood by a child.

Computational Results

The computational performance of the algorithm surprised even the authors. The problem consists of mapping nearly a million 3D data points onto several hundred thousand screen points using a complex interpolation scheme. The Java language has a reputation for being quite slow. Nonetheless, the program's performance was excellent, performing quickly enough for interaction even on slower machines. We attribute much of this speed to the use of time-honed computational techniques such as fixed-point integer math (see Appendix B) and a heavily optimized inner loop.

The performance of graphical programs is nearly linearly dependant on the area of the region being manipulated-- the performance theoretically scales as O(n²), where n is the length of one side of a square region. For this reason our performance figures are quoted for various window sizes. The program correctly handles any window or data size-- these window sizes should not be taken as exclusive. Under Windows NT 4.0 and in Netscape 4.0, using trilinear interpolation, slicing a 128x128x50 pixel data block generated the following the number of slices, or frames, per second (fps).
 

System	200x200 Size	400x400 Size	800x800 Size
Pentium 133	12 fps	4 fps	1 fps
Pentium II 200	50 fps	10 fps	3 fps

Note that for most people, frame rates above 20 fps are indistinguishable from continuous motion. A frame rate adequate for interactive response for our purposes is two or three frames per secondóbelow this rate, motion becomes unacceptably choppy. Hence, on all but the largest images on the slowest computers, the program is fast enough to use interactively.

As a rough estimate of the computations involved, note that at a window size of 800x800 pixels, there are 640,000 pixels to trilinearly interpolate. Since interpolating each screen pixel requires fetching eight surrounding data points and performing at least nine 32-bit integer multiplications (two to index into the data array, four to interpolate along the x direction, two along the y direction, and another along the z direction), there are at least 5.76 million multiplications and 5.12 million data accesses per frame, totaling (on the Pentium II system) more than 15 million data accesses as well as 15 million full-size multiplications per second. It seems that Java's reputation for being slow is undeserved.

Using larger or smaller 3D data blocks did not significantly affect the speed. Using nearest-neighbor interpolation does not significantly improve the speed, and since this method looks very poor, trilinear interpolation is the default.

Interpolation Results

To test the interpolation routines for aliasing artifacts, we generated a test data set containing a linear FM signal emanating from the origin. The final frequency present is twice the Nyquist frequency. Aliasing is quite prevalent in the nearest neighbor linear FM signal, and present to a lesser extent in the trilinearly interpolated data.

Nearest Neighbor InterpolationÝÝ	Trilinear InterpolationÝÝ
Nearest Neighbor Interpolation	Ý  Trilinear Interpolation

There are several features of the above images to note-- first, trilinear interpolation makes the line of the neck smooth and continuous, but with nearest neighbor interpolation there are several discontinuities in the sliced data (these discontinuities are especially obvious in an animated image). Some blurring is present in the trilinear version, but this effect is slight.

I think trilinear interpolation is quite passable here, especially considering how fast it is.

Return to the Table Of Contents

References