kanevsky@heathcliff.columbia.edu (Paul Kanevsky) (02/06/88)
Distribution: A question (actually a plea for help): I am trying to implement real time 3-D display on an IBM-AT class machine. The display consists of a plane with a bunch of solid blocks stacked on the plane. The objective is to be able to rotate and translate the entire thing in real time. The question is: what is the most efficient hidden plane removal algorithm for this? The program currently uses a variant of a depth priority algorithm which fails in some cases, but is reasonably fast. It requires a sort (n*log(n) time) and computation of distances for each face of each block. I think it is possible to come up with an algorithm that will require linear time (in number of blocks) to determine the drawing order of visible block sides. Does anyone know of such an algorithm (it only needs to work in the domain of rectangular blocks)? The main limitation is the speed of the machine - computation is slow, while graphics primitives (EGA) are relatively fast. Although I am aware of some of the more widely known algorithms, they all seem to be too computation intensive for my purposes... Any help, source code, or pointers you can provide will be greatly appreciated. Please respond directly to me; if there is enough interest I'll summarize to the net. kanevsky@heathcliff.columbia.edu (Paul Kanevsky)