“Visibility sorting and compositing without splitting for image layer decompositions” by Snyder and Lengyel

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.

1. Appel A., “The Notion of Quantitative Invisibility and the Machine Rendering of Solids,” In P1vceedings of the ACMNational Conference, pp. 387-393, 1967.
2. Baraff, David, “Curved Surfaces and Coherence for Non-Penetrating Rigid Body Simulation,” Siggraph ’90, August 1990, pp. 19-28.
3. Bentley, J.L., “Multidimensional Binary Search Trees Used for Associative Searching,” Communications of the ACM, 18(1975), pp. 509-517.
4. Chen, Han-Ming, and Wen-Teng Wang, “The Feudal Priority Algorithm on Hidden-Surface Removal,” Siggraph ’96, August 1996, pp. 55-64.
5. Chung, Kelvin, and Wenping Wang, “Quick Collision Detection of Polytopes in Virtual Environments,” ACM Symposium on Virtual Reality Software and Technology 1996, July 1996, pp. 1-4.
6. Chung, Tat Leung (Kelvin), “An Efficient Collision Detection Algorithm for Polytopes in Virtual Environments,” M. Phil Thesis at the University of Hong Kong, 1996 {www.cs.hku.hk/tlchung/collision_library.html}.
7. Cohen, D.J., M.C. Lin, D. Manocha, and M. Ponamgi, “I-Collide: An Interactive and Exact Collision Detection System for Large-Scale Environments,” P1vceedings of the Symposium on Interactive 3D Graphics,, 1995, pp. 189-196.
8. Cook, Robert, “Distributed Ray Tracing,” Siggraph ’84, July 1984, pp. 137-145.
9. Durand, Fredo, George Drettakis, and Claude Puech, “The Visibility Skeleton: A Powerful and Efficient Multi-Purpose Global Visibility Tool,” Siggraph ’97, August 1997, pp. 89-100.
10. Fuchs, H., Z.M. Kedem, and B.F. Naylor, “On Visible Surface Generation by A Priori Tree Structures,” Siggraph ’80, July 1980, pp. 124-133.
11. Funkhouser, T.A., C.H. Sequin, and S.J. Teller, “Management of Large Amounts of Data in Interactive Building Walkthroughs,” Proceedings of 1992 Symposium on Interactive 3D Graphics, July 1991, pp. 11-20.
12. Gilbert, Elmer G., Daniel W. Johnson, and S. Sathiya A. Keerthi, “A Fast Procedure for Computing the Distance Between Complex Objects in Three- Dimensional Space,” IEEE Journal of Robotics and Automation, 4(2), April 1988, pp. 193-203.
13. Greene, N., M. Kass, and G. Miller, “Hierarchical Z-buffer Visibility,” Siggraph ’93, August 1993, pp. 231-238.
14. Haeberli, Paul, and Kurt Akeley, “The Accumulation Buffer: Hardware Support for High-Quality Rendering,” Siggraph ’90, August 1990, pp. 309-318.
15. Kay, Tim, and J. Kajiya, “Ray Tracing Complex Scenes,” Siggraph ’86, August 1986, pp. 269-278.
16. Lengyel, Jed, and John Snyder, “Rendering with Coherent Layers,” Siggraph ’97, August 1997, pp. 233-242.
17. Maciel, Paolo W.C. and Peter Shirley, “Visual Navigation of Large Environments Using Textured Clusters,” Proceedings 1995 Symposium on Interactive 3D Graphics, April 1995, pp. 95-102.
18. Mark, William R., Leonard McMillan, and Gary Bishop, “Post-Rendering 3D Warping,” Proceedings 1997 Symposium on Interactive 3D Graphics, April 1997, pp. 7-16.
19. Markosian, Lee, M.A. Kowalski, S.J. Trychin, L.D. Bourdev, D. Goodstein, and J.F. Hughes, “Real-Time Nonphotorealistic Rendering,” Siggraph ’97, August 1997, pp. 415-420.
20. Max, Nelson, and Douglas Lerner, “A Two-and-a-Half-D Motion-Blur Algorithm,” Siggraph ’85, July 1985, pp. 85-93.
21. McKenna, M., “Worst-Case Optimal Hidden Surface Removal,” ACM Transactions on Graphics, 1987, 6, pp. 19-28.
22. Ming-Chieh Lee, Wei-ge Chen, Chih-lung Bruce Lin, Chunag Gu, Tomislav Markoc, Steven I. Zabinsky, and Richard Szeliski, “A Layered Video Object Coding System Using Sprite and Affine Motion Model,” IEEE Transactions on Circuits and Systems for Video Technology, 7(1), February 1997, pp. 130-145.
23. Molnar, Steve, John Eyles, and John Poulton, “PixelFlow: High-Speed Rendering Using Image Compositing,” Siggraph ’92, August 1992, pp. 231-140.
24. Mulmuley, K., “An Efficient Algorithm for Hidden Surface Removal,” Siggraph ’89, July 1989, pp. 379-388.
25. Naylor, B.F., “Partitioning Tree Image Representation and Generation from 3D Geometric Models,” P1vceedings of Graphics Intelface ’92, May 1992, pp. 201-212.
26. Newell, M. E., R. G. Newell, and T. L. Sancha, “A Solution to the Hidden Surface Problem,” P1vc. ACM National Conf., 1972.
27. Ponamgi, Madhav K., Dinesh Manocha, and Ming C. Lin, “Incremental Algorithms for Collision Detection between Polygonal Models,” IEEE Transactions on Visualization and Computer Graphics, 3(1), March 1997, pp 51-64.
28. Porter, Thomas, and Tom Duff, “Compositing Digital Images,” Siggraph ’84, July 1984, pp. 253-258.
29. Potmesil, Michael, and Indranil Chakravarty, “A Lens and Aperture Camera Model for Synthetic Image Generation,” Siggraph ’81, August 1981, pp. 389-399.
30. Potmesil, Michael, and Indranil Chakravarty, “Modeling Motion Blur in Computer-Generated Images,” Siggraph ’83, July 1983, pp. 389-399.
31. Regan, Matthew, and Ronald Pose, “Priority Rendering with a Virtual Address Recalculation Pipeline,” Siggraph ’94, August 1994, pp. 155-162.
32. Rokita, Przemyslaw, “Fast Generation of Depth of Field Effects in Computer Graphics,” Computers and Graphics, 17(5), 1993, pp. 593-595.
33. Schaufler, Gernot, and Wolfgang Stfirzlinger, “A Three Dimensional Image Cache for Virtual Reality,” P~vceedings of Emvgraphics ’96, August 1996, pp. 227-235.
34. Schaufler, Gernot, “Nailboards: A Rendering Primitive for Image Caching in Dynamic Scenes,” in P~vceedings of the 8th Emvgraphics Workshop on Rendering ’97, St. Etienne, France, June 16-18, 1997, pp. 151-162.
35. Schumacker, R.A., B. Brand, M. Gilliland, and W. Sharp, “Study for Applying Computer-Generated Images to Visual Simulation,” AFHRL-TR- 69-14, U.S. Air Force Human Resources Laboratory, Sept. 1969.
36. Sedgewick, Robert, Algorithms, Addison-Wesley, Reading, MA, 1983.
37. Shade, Jonathan, Dani Lischinski, David H. Salesin, Tony DeRose, and John Snyder, “Hierarchical Image Caching for Accelerated Walkthroughs of Complex Environments,” Siggraph ’96, August 1996, pp. 75-82.
38. Sillion, Francois, George Drettakis, and Benoit Bodelet, “Efficient Impostor Manipulation for Real-Time Visualization of Urban Scenery,” P~vceedings of Emvgraphics ’97, Sept 1997, pp. 207-218.
39. Snyder, John, and Jed Lengyel, “Visibility Sorting and Compositing for Image-Based Rendering,” Microsoft Technical Report, MSR-TR-97-11, April 1997.
40. Snyder, John, Jed Lengyel, and Jim Blinn, “Resolving Non-Binary Cyclic Occlusions with Image Compositing,” Microsoft Technical Report, MSR- TR-98-05, March 1998.
41. Sudarsky, Oded, and Craig Gotsman, “Output-Sensitive Visibility Algorithms for Dynamic Scenes with Applications to Virtual Reality,” Computer Graphics Forum, 15(3), P1vceedings of Emvgraphics ’96, pp. 249-258.
42. Sutherland, Ivan E., Robert F. Sproull, and Robert A. Schumacker, “A Characterization of Ten Hidden-Surthce Algorithms,” Computing Surveys, 6(1), March 1974, pp. 293-347.
43. Teller, Seth, and C.H. Sequin, “Visibility Preprocessing for Interactive Walkthroughs,” Siggraph ‘ 91, July 1991, pp. 61 – 19.
44. Teller, Seth, and R Hanrahan, “Global Visibility Algorithms for Illumination Computations,” Siggraph ’93, August 1993, pp. 239-246.
45. Torborg, Jay, and James T. Kajiya, “Talisman: Commodity Realtime 3D Graphics for the PC,” Siggraph ’96, August 1996, pp. 353-364.
46. Torres, E., “Optimization of the Binary Space Partition Algorithm (BSP) for the Visualization of Dynamic Scenes,” Proceedings of Eurographics ’90, Sept. 1990, pp. 507-518.
47. Wang, J.Y.A., and E.H. Adelson, “Representing Moving Images with Layers,” IEEE Trans. Image Processing, vol. 3, September 1994, pp. 625-638.
48. Zhang, Hansong, Dinesh Manocha, Thomas Hudson, and Kenneth Hoff III, “Visibility Culling Using Hierarchical Occlusion Maps,” Siggraph ’97, August 1997, pp. 77-88.