Efficient visualization of large datasets using parallel processing and visibility computation

Large graphic datasets, with hundreds of megabytes of data or hundreds of thousands of polygons, are gradually becoming a norm in today's applications. Due to the complexity of datasets, real-time or interactive rendering in such applications presents a very challenging problem. In this dissertation we presented two algorithms to tackle such a problem. Our first contribution lies in the development of a parallel rendering algorithm which combines the rendering efficiency of an image-order approach (such as early ray termination and adaptive sampling), with the deterministic communication order of an object-order approach. A front-to-back object-space order is used to achieve great cache efficiency (no cache conflicts or thrashing) and a high degree of latency hiding with only a small amount (several hundred kilobytes) of cache memory. Our new parallel algorithm is efficient, capable of rendering 21 frames per second for 2563 voxels and one frames per second for 512 3 voxels on 128 processors, and scalable, reaching 80% of parallel efficiency for a volume of 5123 voxels on 128 processors. The algorithm can also be extended to take advantage of the frame-to-frame cache coherence across multiple image frames to further improve its performance.; The second algorithm presented in the dissertation is a new visibility computation algorithm for accelerating rendering of large architectural models. We use a 2D floor plan to represent the partitioning structure (e.g. rooms) of a 3D architectural model, and apply a space subdivision to the 2D plan. Visibility information is computed based on subdivided regions by using walls as major occluders. The result is an efficient object-space visibility determination algorithm, which can efficiently cull away most invisible objects (more than 90% of a complex architectural model) with respect to a view point. Our algorithm is designed to be used as a preprocessing step to compute and save the visibility information before the rendering stage. To reduce the storage requirement for saving the preprocessed information, a difference list scheme is developed, which employs a mechanism to save only the differential visibility information between neighboring regions, and provides a quick restoration to the complete visibility during run-time. With the difference list scheme, visibility information can be stored at only a small percentage (about 11% to 15%) of the full set's memory cost, allowing a space subdivision of higher resolutions to be used in the visibility computation (and thus more accurate visibility information).