Multiresolution volume processing and visualization on graphics hardware

PhD ceremony: Mr. W.J. van der Laan, 16.15 uur, Academiegebouw, Broerstraat 5, Groningen

Title: Multiresolution volume processing and visualization on graphics hardware

Promotor(s): prof. J.B.T.M. Roerdink

Faculty: Mathematics and Natural Sciences

In this thesis we investigated several advanced techniques in visualization of large data sets, multidimensional signal processing, deformable models, and data reduction. As we aimed to develop fast algorithms, all of these can be used in an interactive pipeline.

In chapter 2 we have investigated a number of algorithms based on morphological pyramids for multiresolution MIP volume rendering on graphics hardware. We found that our highly- optimized streaming MIP GPU-method outperforms both its software implementation as well as existing ray-casting and 3-D texture-based methods.

In chapter 3 we presented a novel, fast wavelet lifting implementation on graphics hardware using CUDA, which extends to any number of dimensions. We compared our method to an op- timized CPU implementation of the lifting scheme, to another (non-CUDA based) GPU wavelet lifting method, and also to an implementation of the wavelet transform in CUDA via convolu- tion. We implemented our method both for 2D and 3D data. The method is scalable and was shown to be the fastest GPU implementation among the methods considered. Our theoretical performance estimates turned out to be in fairly close agreement with the experimental observations. The complexity analysis revealed that our CUDA kernels are cost- and work-efficient. Our proposed GPU algorithm can be applied in all cases were the Discrete Wavelet Transform is part of a pipeline for processing large amounts of data. Examples are the encoding of static images, such as the wavelet-based successor to JPEG, JPEG2000 [124], or video coding schemes [9].

In chapter 4, we showed how to accelerate the Dirac Video Codec by our fast wavelet lift- ing implementation on graphics hardware using CUDA. We also accelerated the motion com- pensation and frame arithmetic stages of this codec. The experiments on high definition video sequences have demonstrated that one can achieve a speedup factor of more than 7 for the en- tire decoding process including the CPU steps, and a factor of 15 for just the GPU part. In our benchmark we could play back a 1080p resolution Dirac video sequence at roughly 50 frames per second on basic consumer hardware.

In chapter 5 we presented a new method for rendering fluids in real-time directly from particle based representations without the need for intermediate triangulation, but which still produces a high-quality fluid surface. We also introduced new ideas to add thickness-based shading and small-scale surface detail to fluids.

In chapter 6 we proposed an efficient data structure, the Sorted Tile List, with associated operations for the level set representation, and compared the resulting method with the current method of choice, the DT-Grid method. With regard to performance, given the same numerical simulation code, our method turned out to be faster by a significant factor. After fine-grain parallelization using SIMD instructions our method was shown to be roughly 8 times faster.

In chapter 7 we adapted our highly-efficient, sparse, tile-based level set method to leverage highly parallel architectures such as GPUs We compared our method to other state-of-the-art, sparse approaches, and showed that our method is about 20 times faster than the optimized CPU version of the Sorted Tile List method, and two orders of magnitude faster than the DT- Grid method. Many level-set applications can benefit from our level-set GPU infrastructure. To demonstrate its efficiency, we discussed two graphics applications: surface reconstruction from point clouds and level-set surface editing. Our novel multi-resolution method for surface re- construction compares favorably with recent, existing techniques and parallel implementations. Finally, our free-form surface editing tool runs at interactive frame rates on large volumetric grids of 1024^3 voxels.