Adaptive Grid for Polyhedral Visibility in Object Space: An Implementation

摘要

The paper presents an implementation of Franklin's object space hidden surface algorithm for polyhedral scenes (ACM Computer Graphics 14(3), 117-123, 1980). 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.