Visibility Sorting and Compositing for Image-Based Rendering

We present an efficient algorithm for analyzing synthetic scenes involving a set of moving objects and changing view parameters into a sorted sequence of image layers. The final image is generated by evaluating a 2D image compositing expression on these layers. Unlike previous visibility approaches, we detect and report occlusion cycles rather than splitting to remove them. Such an algorithm has many applications in computer graphics; we demonstrate two: rendering acceleration using image interpolation, and visibility-correct depth of field using image blurring. The algorithm involves an incremental method for identifying mutually occluding sets of objects and computing a visibility sort of these sets. Occlusion queries are accelerated by testing on convex bounding hulls; less conservative tests are also discussed. Kd-trees formed by combinations of directions in object or image space provide an initial cull on potential occluders, and a new incremental algorithmis employed to resolve pairwise occlusions. Mutual occluders are further analyzed to generate an image compositing expression; in the case of nonbinary cycles an expression can always be generated without aggregating the objects into a single layer. Results demonstrate that the algorithm is practical for interactive animation of scenes involving hundreds of objects each comprising hundreds or thousands of polygons.