Adaptive Grid for Polyhedral Visibility in Object Space: an Implementation
W. Randolph Franklin · The Computer Journal · 1988
This paper presents an implementation of Franklin's object space hidden surface algorithm for polyhedral scenes.4 It is known that if the faces are independently and identically distributed this algorithm performs in time linear in the number of faces, and in particular is not affected by the depth complexity. The algorithm overlays a grid on the scene with fineness depending on the statistics of the edges and the faces. It then preprocesses the edges and the faces in a grid data structure so that distant edges and faces will not be compared. The implementation of the algorithm on a Prime 750 using Ratfor shows that it is indeed very fast for random and structured scenes alike.