Fast out-of-core isosurface visualization of volume data sets

Efficient visualization of volume data is critical to many scientific, engineering and medical applications. One of the most pervasive and useful volume visualization techniques is isosurface rendering. The process of locating voxels that are needed to create the isosurface is a specific instance of the general class of stabbing point query problems. Algorithms that accelerate stabbing point queries significantly increase RAM requirements, making these algorithms only suitable for small data sets. To cope with larger data sets, researchers have devised out-of-core isosurface rendering techniques that keep the search-optimized data set on secondary storage and perform voxel extraction directly on the secondary storage-resident data. Existing out-of-core techniques have had limited success because they have failed to address system issues such as data caching at various levels, disk head seeking and limitations within the operating system/user interfaces. As a result, the performance of these techniques do not scale well with the raw data size.; A system-oriented out-of-core isosurface extraction algorithm based on the use of interval trees is presented. Interval tree data structures are well-suited for stabbing point queries. Furthermore, the data on the disk is organized to minimize head seeking delays and prefetching with multithreading is used to almost eliminate the impact of disk accessing delays. The resulting out-of-core technique matches or exceeds the performance of in-core acceleration techniques that have sufficient RAM for holding the search-optimized data structures. More importantly, as data set sizes increase further, this out-of-core interval tree based isosurface extraction technique performs orders of magnitude faster than in-core algorithms and scales well with the data size.; The performance of the interval tree based out-of-core technique is improved upon with the introduction of a new data structure called span-space buckets, optimized for stabbing point queries and requiring about half as much storage as the interval tree based structures. Further improvements in scalability are achieved by using an out-of-core chessboarding scheme that achieves another four-fold reduction in the size of the transformed data without sacrificing performance. Lastly, both out-of-core techniques are speeded up through their parallelization on symmetric multiprocessors. Even though these techniques are effective on high-end machines, their small memory footprints make them ideal for commodity PCs; bringing inexpensive large volume data visualization to the masses.