| Three-dimensional (3D) linear projection is a procedure that projects the 3D object space onto a 2D plane. A set of parallel rays are defined that pass through the 3D object space. Points along each ray are sampled, and a transformation of the points is computed for each ray. The 3D planar projection is similar, except parallel planes are projected through the 3D data, onto a line. Three-dimensional parallel projection (linear or planar) finds numerous applications in the fields of computer graphics and image processing. For instance, scientific visualization of 3D data is achieved by projecting along rays to obtain a 2D frame for viewing. The reconstruction of 3D images from data collected by various means often involves 3D planar or linear projection.; In this research, we devise new fast linear and planar sampling algorithms for 3D parallel projection. Our new sampling algorithms operate in a recursive manner that is completely different from the conventional methods. They compute a set of linear or planar projections over a range of angles simultaneously, in far less time than required for the independent computation of each projection. In particular, our approximate linear projection algorithms are as much as a factor of {dollar}Theta(N){dollar} faster per projection than computing independently, and our approximate planar projection algorithm has a speedup of {dollar}Theta(Nsp2/log N{dollar}) over independent projections. Furthermore, the recursive sampling algorithms yield very efficient parallel algorithms. High efficiency is achieved by trading off some sampling accuracy--sample points are within {dollar}(sqrt{lcub}2{rcub}/2)log N - 1{dollar} units of the intended line or plane.; We next show how our algorithms can be applied to two computation-intensive problems from 3D imaging--animated volume visualization and 3D image reconstruction. We demonstrate that our sampling algorithms not only greatly speed up the 3D projection process, but also result in images of fairly good quality. The applications are implemented and evaluated on both sequential and parallel processing platforms. |
