Visibility Sorting and Compositing without Splitting for Image Layer Decompositions

We present an efficient algorithm for visibility sorting a set of moving geometric objects into a sequence of image layers which are composited to produce the final image. Instead of splitting the geometry as in previous visibility approaches, we detect mutual occluders and resolve them using an appropriate image compositing expression or merge them into a single layer. 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. We propose a new, incremental method for identifying mutually occluding sets of objects and computing a visibility sort among 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 incremental collision detection algorithms are adapted to resolve pairwise occlusions, when necessary. Mutual occluders are further analyzed to generate an image compositing expression; in the case of non-binary occlusion cycles, an expression can always be generated without merging the objects into a single layer. Results demonstrate that the algorithm is practical for real-time animation of scenes involving hundreds of objects each comprising hundreds or thousands of polygons.