Visualization: CMPT 767 (Fall 2008)

Instructor: Dr. Torsten Möller

(a) An analytic function	(b) The uncbrain dataset	(c) The carp fish dataset
Images rendered using the software developed in this course

This was my first course at SFU and hence I was a bit shaky and naive with my methods and implementations. Nonetheless, it was this course that got me interested in Body Centric Cubic (BCC) lattice and paved my way into research in this area. Accurate normal computation plays a very important role in volume visualization as it is used for shading iso-surfaces. BCC lattice (see Video 1) have been shown to yield a more accurate and faster reconstruction of scalar data which also means more accurate iso-surfaces (read this paper for details). However, if the shading of these accurate iso-surfaces are not complemented with accurate normals then the visual perception of fine details remain rather unclear. This is analogous to a finely reconstructed geometric surface painted with a slightly wrong brush.

Video 1: BCC Lattice	Video 2: Support of Quintic Box Spline

Therefore, for the final project I picked the open problem of computing accurate gradients on BCC lattice. Initially, I was interested only in computing gradients at the grid points but later I also wanted to use interpolation filter to compute gradient in the continuous domain. This whole work was largely motivated by Möller et al.

In the first phase of the project I developed a command-line software ray-tracer in C/C++ from ground up. It had an OpenGL previewer that let me see the progress of the rendering in a separate window. I designed the code in such a way that it could be easily extended for any lattice type and various discrete and continuous interpolation filters. A screenshot of my renderer in action is shown in Figure 1.

In the second phase I implemented codes for BCC grids with the corresponding interpolation filter, Quintic Box Spline (read this paper). While debugging my code I used a single impulse in a BCC grid and rendered it with a transfer function that sets full opacity for any scalar value epsilon (usually a very small number) away from zero. For a correct code this should display the support of the interpolation filter and in case of Quintic Box Spline the support should be a Rhombic Dodechedron. Later I produced this interesting video (Video 2) using my code that shows the support of the Quintic Box Spline.

At this point I started working mostly with Maple to develop a novel discrete stencil to compute the first derivative along each axis for the BCC grid. Intially my approach was a little bit naive and hence I got myself into dealing with very long equations of multi-dimensional Taylor series expansion that would fry my brain for a bit. Though, later I managed to develop one filter before the deadline that would use all the nearest neighbours ( 8 for BCC lattice ) to compute the first derivative which was second-order in terms of asymptotic error behavior. Since the filter had eight weights forming the eight corners of a box I named it Box-Central Differencing (BCD). With this new filter I noticed some remarkable numerical and visual improvement over the commonly used axis-aligned central differencing, which I named SOCD, that would take only the axis-aligned neighbours which were not the closest in a BCC grid. Figure 2 shows the visual and numerical differences this new BCD filter has over the older SOCD in BCC grid. Note that in Figure 2 all the iso-surfaces were computed from the actual analytic function, whereas only the normals were computed from the sampled data. This way I ruled out the possibilities of any artifacts due to scalar interpolation.

(a) SOCD, ( 68.9° / 3.78 )	(b) Truth	(c) BCD ( 39.2° / 2.88 )
Figure 2: Marschner-Lobb data sampled at 32x32x64 (which has roughly the same number of samples for 41x41x41 on Cartesian Cubic grid). Normals are computed with different filters while the iso-surfaces for all three images were computed from the actual analytic function to make sure no artifact was introduced due to scalar interpolation. The number pair underneath each image shows the RMS angular error in degrees followed by the RMS magnitude error. Quintic Box Spline was used to interpolate the gradients. (a) Normals computed using the older method of aix-aligned central differencing (b) The ground truth (c) Normals computed using the new BCD filter.

Final Report

You can access the final report for this course here. Please note that the images in the final report are buggy as I had mistakently normalized the gradients prior to interpolation and this had effects only in the final renderings. However, the numerical results are all correct.

Further Work

The above results instigated a full blown research on gradient estimation on BCC grid right after the course was over. I realized that I could extend the work of my supervisor, also the instructor of this course, Dr. Torsten Möller (see this paper), to develop a general framework for, not only gradient, but any derivates on regular lattices using very compactly supported discrete filters.

While we were working on developing a generic Taylor series based framework, Usman Raza Alim recognized that this problem of gradient estimation can also be tackled using a relatively new concept in signal processing called Orthogonal Projection (see this paper). In this method gradients can be computed with much higher accuracy but with some decent storage overhead. We extended both these Taylor Series and Orthogonal Projection based frameworks for arbitrary dimension and derivatives on regular lattices together with allowing users to specify the order of accuracy. Later we put both these methods together and published a journal article in IEEE Transaction on Visualization and Computer Graphics (TVCG). For more details, please refer to our article on my publication page. For all the experiments performed in the journal paper I extended and used the same Ray-Tracer code that I had written for this course. These days however, the Ray-Tracer is getting extended mostly by Usman Raza Alim for his continuing research on gradient estimation.