Interactive Computation and Visualization of Level-Set Surfaces: A Streaming Narrow Band Algorithm

Deformable isosurfaces, implemented with level-set methods, have demonstrated a great potential in visualization and computer graphics for applications such as segmentation, surface processing, and surface reconstruction. Their usefulness has been limited, however, by two problems. First, three-dimensional level sets are relatively slow to compute. Second, their formulation usually entails free parameters that can be difficult to tune correctly for specific applications. The second problem is compounded by the first. This thesis presents a solution to these challenges by describing graphics processor unit (GPU) based algorithms for solving and visualizing level-set solutions at interactive rates for volumes as large as 256 x 256 x 256. Level-set techniques deform isosurfaces by solving partial differential equations (PDEs) on a voxel grid. Efficient solvers for the equations compute a solution only at those voxels on or near the isosurface. The active elements in this narrow-band of computation change as the level-set solution evolves. This thesis demonstrates that such dynamic sparse-grid computations can be efficiently solved using a streaming architecture platform--a modern graphics processor. The solution uses a multidimensional virtual memory mapping to pack the active, three-dimensional voxel data into two-dimensional texture memory on the GPU. A novel GPU-to-CPU message passing scheme quickly updates this sparse data structure as the isosurface moves. The integration of the level-set solver with a real-time volume renderer allows a user to visualize and steer the deformable level-set surface as it evolves. The resulting isosurface can also serve as a region-of-interest specifier for the volume renderer. This thesis demonstrates the capabilities of this technology for interactive volume segmentation and visualization. This thesis also presents an evaluation of the method with a brain tumor segmentation user study