A visibility algorithm for hybrid geometry- and image-based modeling and rendering

Hybrid geometry- and image-based modeling and rendering systems use photogr aphs taken of a real-world environment and mapped onto the surfaces of a 3D model to achieve photorealism and visual complexity in synthetic images re ndered from arbitrary viewpoints. A primary challenge in these systems is t o develop algorithms that map the pixels of each photograph efficiently ont o the appropriate surfaces of a 3D model, a classical visible surface deter mination problem. This paper describes an object-space algorithm for comput ing a visibility map for a set of polygons for a given camera viewpoint. Th e algorithm traces pyramidal beams from each camera viewpoint through a spa tial data structure representing a polyhedral convex decomposition of space containing cell, face, edge and vertex adjacencies. Beam intersections are computed only for the polygonal faces on the boundary of each. traversed c ell, and thus the algorithm is output-sensitive. The algorithm also support s efficient determination of silhouette edges, which, allows an image-based modeling and rendering system to avoid mapping pixels along edges whose co lors are the result of averaging over several disjoint surfaces. Results re ported for several 3D models indicate the method is well suited for large, densely occluded virtual environments, such as building interiors. (C) 1999 Published by Elsevier Science Ltd. All rights reserved.