Volume rendering algorithms and architectures

Volumetric ray casting of large static and time-varying data sets with capabilities of arbitrary viewing directions and complex ray casting functionalities is a challenge that must be met by the use of not only fast sequential algorithms but also by parallel algorithms and VLSI technology. A typical 512{dollar}sp3{dollar} image of x-ray computed tomography with 24 bits per voxel element needs 384 Mbytes of storage. The enormous size of the data set which needs to be repeatedly manipulated/rendered at least 30 frames per second for real-time visualization, has given rise to very computationally intensive tasks. In this dissertation, we present several new algorithms and special purpose architectures for the volumetric ray casting problem. Specifically, we make the following contributions:; We have designed and implemented a new, fast sequential algorithm which casts rays only through the non-empty space defined by non-empty and non-overlapping blocks while raster scanning the volume data. We also propose an efficient and fast block decomposition algorithm for the volume data set and show that for any orthographic viewing direction, we need to pre-sort the blocks in only four distinct ways. This algorithm takes only half of the pre-processing time and uses about one fifth of the memory compared to those in existing algorithms. We then extend this algorithm for fast rendering of time varying data sets. For this, we develop a compact storage scheme whose representation is further reduced by the block decomposition technique. This compact data structure is then directly rendered using an extended fast sequential algorithm.; In the area of parallel volumetric ray casting algorithms, we present an optimal parallel algorithm for volume rendering. This algorithm uses a very simple scheme for distributing the volume data among processors connected in hypercube fashion. The time complexity of the presented algorithm is {dollar}O({lcub}rm log{rcub}sp3n{dollar}) using {dollar}O(nsp3/{lcub}rm log{rcub}sp3n){dollar} processors for a {dollar}nsp3{dollar} data set. We have implemented this algorithm on parallel machines such as Maspar MP1200 and Cray-T3D. We are able to generate a 256{dollar}sp2{dollar} image for a 128{dollar}sp3{dollar} data set on a Cray-T3D, in about 3.0 seconds using only 64 processors.; The performance of a parallel algorithm on an existing parallel machine depends on the machine architecture. Therefore, it is imperative to design special purpose architecture for volumetric ray casting in order to generate high quality images at an interactive rate. We present a new highly parallel and pipelined architecture for 3D volumetric ray casting. In this architecture, each processor is assigned a portion of volume data. To facilitate conflict free access of the voxel's values, a new memory organization scheme is proposed. This architecture uses {dollar}O(n{lcub}rm log{rcub} n{dollar}) processing units to protect a data set of size {dollar}nsp3{dollar} in {dollar}O(nsp2/{lcub}rm log{rcub} n{dollar}) time. We have simulated the proposed ray casting architecture for a 16{dollar}sp3{dollar} system using VHDL for the nearest opaque voxel computations, which suggests the presented architecture can generate 25-30 images per second for a 512{dollar}sp3{dollar} volume data set.