PARALLEL DISPLAY OF OBJECTS REPRESENTED BY LINEAR OCTREES

The storage, display, and manipulation of three dimensional volumetriq ue information requires a large amounts of computing resources, both i n terms of memory, and processing power. Most existing serial algorith ms that display 3-D objects on a 2-D screen are found to be too slow t o process the large amounts of volume data in a reasonable time. Hence , one way to increase the performance of the display algorithm is to p rocess individual volume elements (voxels) in parallel. The first part of this paper presents a brief overview of the linear octree [6] data structure which represents 3-D objects by an eight-way branching tree , while the second part focusses on the parallel display of such objec ts. We have shown that, for an object represented by a linear octree a nd enclosed in a 2(n) x 2(n) X 2(n) universe, the maximum number of vo xels that can be processed in parallel is 3(n), and the maximum number of time steps required to display such an object is 4(n). This paper presents a set of formulae which identify the processing element (PE) as well as the time step in which a given linear octree node is proces sed. Similarly, a procedure which determines the locational code of a linear octree node which must be processed by a given PE, at some spec ific time step, is presented, along with a strategy for determining wh ether a PE is active or idle.