Conservative volumetric visibility with occluder fusion

ABSTRACT

Visibility determination is a key requirement in a wide range of graphics algorithms. This paper introduces a new approach to the computation of volume visibility, the detection of occluded portions of space as seen from a given region. The method is conservative and classifies regions as occluded only when they are guaranteed to be invisible. It operates on a discrete representation of space and uses the opaque interior of objects as occluders. This choice of occluders facilitates their extension into adjacent opaque regions of space, in essence maximizing their size and impact. Our method efficiently detects and represents the regions of space hidden by such occluders. It is the first one to use the property that occluders can also be extended into empty space provided this space is itself occluded from the viewing volume. This proves extremely effective for computing the occlusion by a set of occluders, effectively realizing occluder fusion. An auxiliary data structure represents occlusion in the scene and can then be queried to answer volume visibility questions. We demonstrate the applicability to visibility preprocessing for real-time walkthroughs and to shadow-ray acceleration for extended light sources in ray tracing, with significant acceleration in both cases.

REFERENCES

• 1: John M. Airey , John H. Rohlf , Frederick P. Brooks, Jr., Towards image realism with interactive update rates in complex virtual building environments, Proceedings of the 1990 symposium on Interactive 3D graphics, p.41-50, February 1990, Snowbird, Utah, United States
• 2: Catmull, Edwin, E., Computer Display of Curved Surface, IEEE Conference on Computer Graphics, Pattern Recognition and Data Structures, May 1975, pp 11-17.
• 3: Norman Chin , Steven Feiner, Fast object-precision shadow generation for area light sources using BSP trees, Proceedings of the 1992 symposium on Interactive 3D graphics, p.21-30, June 1992, Cambridge, Massachusetts, United States [doi>10.1145/147156.147159]
• 4: Satyan Coorg , Seth Teller, Temporally coherent conservative visibility (extended abstract), Proceedings of the twelfth annual symposium on Computational geometry, p.78-87, May 24-26, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237218.237242]
• 5: Cohen-Or, Daniel and Amit Shaked, Visibility and Dead- Zones in Digital Terrain Maps, EUROGRAPHICS '95 14 3 (1995) pp 171-180.
• 6: Cohen-Or, D., G. Fibich, D. Halperin and E. Zadicario, Conservative Visibility and Strong Occlusion for Viewspace Partitioning of Densely Occluded Scenes, Computer Graphics Forum, 17 (3) 1998, pp 243-253.
• 7: Y. Chrysanthou , D. Cohen-Or , D. Lischinski, Fast Approximate Quantitative Visibility for Complex Scenes, Proceedings of the Computer Graphics International 1998, p.220, June 22-26, 1998
• 8: George Drettakis , Eugene Fiume, A fast shadow algorithm for area light sources using backprojection, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.223-230, July 1994 [doi>10.1145/192161.192207]
• 9: Frédo Durand , George Drettakis , Claude Puech, The visibility skeleton: a powerful and efficient multi-purpose global visibility tool, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.89-100, August 1997 [doi>10.1145/258734.258785]
• 10: Durand, Fredo, 3D Visibility: Analytical Study and Applications, PhD Dissertation, Universite Joseph Fournier, Grenoble, France.
• 11: Frédo Durand , George Drettakis , Joëlle Thollot , Claude Puech, Conservative visibility preprocessing using extended projections, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.239-248, July 2000 [doi>10.1145/344779.344891]
• 12: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 13: N Greene, Applications of world projections, Proceedings on Graphics Interface '86/Vision Interface '86, p.108-114, August 1986, Vancouver, British Columbia, Canada
• 14: Ned Greene , Michael Kass , Gavin Miller, Hierarchical Z-buffer visibility, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.231-238, September 1993 [doi>10.1145/166117.166147]
• 15: Haines, A. Eric and Donald P. Greenberg, The Light Buffer: A Ray Tracer Shadow Testing Accelerator, IEEE Computer Graphics and Applications, 6 9, 1986, pp 6-16.
• 16: Haines, A. Eric and John R. Wallace, Shaft Culling for Efficient Ray Cast Radiosity, Photorealistic Rendering in Computer Graphics (Proceedings of the Second Eurographics Workshop on Rendering), Springer-Verlag, New York, 1994, pp 122-138.
• 17: David Hart , Philip Dutré , Donald P. Greenberg, Direct illumination with lazy visibility evaluation, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.147-154, July 1999 [doi>10.1145/311535.311551]
• 18: T. Hudson , D. Manocha , J. Cohen , M. Lin , K. Hoff , H. Zhang, Accelerated occlusion culling using shadow frusta, Proceedings of the thirteenth annual symposium on Computational geometry, p.1-10, June 04-06, 1997, Nice, France [doi>10.1145/262839.262847]
• 19: T. M. Murali , Thomas A. Funkhouser, Consistent solid and boundary representations from arbitrary polygonal data, Proceedings of the 1997 symposium on Interactive 3D graphics, p.155-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253326]
• 20: Harry Plantinga , Charles R. Dyer, Visibility, occlusion, and the aspect graph, International Journal of Computer Vision, v.5 n.2, p.137-160, Nov. 1990 [doi>10.1007/BF00054919]
• 21: Saona-Vazquez, Carlos, Isabel Navazo and Pere Brunet, The Visibility Octree. A Data Structure for 3D Navigation, TR LSI-99-22-R, Universitat Politecnica de Catalunya, Spain.
• 22: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 23: A. James Stewart , Sherif Ghali, Fast computation of shadow boundaries using spatial coherence and backprojections, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.231-238, July 1994 [doi>10.1145/192161.192210]
• 24: A. James Stewart, Hierarchical Visibility in Terrains, Proceedings of the Eurographics Workshop on Rendering Techniques '97, p.217-228, June 16-18, 1997
• 25: Tanaka, Toshimitsu, and Tokiichiro Takahashi, Fast Analytic Shading and Shadowing for Area Light Sources, Computer Graphics Forum, Vol. 16, 3, 1997, pp 231-240.
• 26: Seth J. Teller , Carlo H. Séquin, Visibility preprocessing for interactive walkthroughs, Proceedings of the 18th annual conference on Computer graphics and interactive techniques, p.61-70, July 1991
• 27: Seth J. Teller, Computing the antipenumbra of an area light source, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.139-148, July 1992
• 28: Seth Teller , Celeste Fowler , Thomas Funkhouser , Pat Hanrahan, Partitioning and ordering large radiosity computations, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.443-450, July 1994 [doi>10.1145/192161.192279]
• 29: Ward, Gregory J. and Paul Heckbert, Irradiance Gradients, Third Eurographics Workshop on Rendering, May 1992, pp 85-98.
• 30: A. Woo , J. Amanatides, Voxel occlusion testing: a shadow determination accelerator for ray tracing, Proceedings on Graphics interface '90, p.213-220, June 1990, Halifax, Nova Scotia
• 31: Yagel, Roni, and William Ray, Visibility Computation for Efficient Walkthrough of Complex Environments, PRESENCE, Vol.5, No. 1, Winter 1996, pp 1-16.
• 32: Hansong Zhang , Dinesh Manocha , Tom Hudson , Kenneth E. Hoff, III, Visibility culling using hierarchical occlusion maps, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.77-88, August 1997 [doi>10.1145/258734.258781]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.6 Methodology and Techniques
          Subjects: Graphics data structures and data types
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

General Terms:
Algorithms, Design, Measurement, Performance, Theory