An Algorithm of hidden Surface Removal based on Frame-To- Frame Coherence

Abstract

Frame-to-frame coherence capitalizes on the continuity existing between successive frames in order to predict the visibility of the scene at a given instant on the basis of its visibility at the previous instant. It is shown that all the algorithms based on frame-to-frame coherence share a common model and involve similar data structures. This model is used as a framework for a discussion of possible frame-to-frame coherence algorithms. A specific solution based on a partition of the image space into several 2-D regions is then presented. A temporal graph of the depth priority relationship of the objects is first computed in a pre-process along with a temporal BSP tree of each object. In the first frame a total traversal of both data structures is required in order to establish the priority list of the faces of the scenes. In successive frames, the priority list is easily updated with partial traversals and with no geometrical computations. The complexity of the proposed algorithm is discussed. Some examples are presented with comments on the results of their implementation.