“Global visibility algorithms for illumination computations” by Teller and Hanrahan

The most expensive geometric operation in image synthesis is
visibility determination. Classically this is solved with hidden
surface removal algorithms that render only the parts of the scene
visible from a point. Global illumination calculations, however,
may require information between any two points in the scene.
This paper describes global visibility algorithms that preprocess
polygon databases in order to accelerate visibility determination
during illumination calculations. These algorithms are sensitive to
the output complexity in visibility space; that is, how many pairs
of objects are mutually visible. Furthermore, the algorithms are
incremental so that they work well with progressive refinement
and hierarchical methods of image synthesis. The algorithms
are conservative, but exact; that is, when they return visibility
predicates they can be proved true. However sometimes they do not
return either totally visible or totally invisible, but partially visible,
even though in the same situation a better algorithm might return
the exact answer. In this paper we describe the algorithms and
their implementation, and show that, in a scene with low average
visual complexity, they can dramatically accelerate conventional
radiosity programs.

1. AIREY, J. M. Increasing Update Rates in the Building Walkthrough System with Automatic Model-Space Subdivision and Potentially Visible Set Calculations. PhD thesis, UNC Chapel Hill, 1990.
2. BAUM, D. R., MANN, S., SMITH, K. P., AND WINGET, J. M. Making Radiosity Usable: Automatic Preprocessing and Meshing Techniques for the Generation of Accurate Radiosity Solutions. Computer Graphics (Proc. SIGGRAPH ’91) 25, 4 (1991), 51-60.
3. CAMPBELL III, A., AND FUSSELL, D. S. An Analytic Approach to Illumination with Area Light Sources. Tech. Rep. TR-91-25, Department of Computer Sciences, UT Austin, 1991.
4. CHIN, N., AND EEINER, S. Fast Object-Precision Shadow Generation for Area Light Sources Using BSP Trees. In Proc. 1992 Symposium on Interactive 3D Graphics (1992), pp. 21-30.
5. COHEN, M. F., CHEN, S. E., WALLACE, J. R., AND GREEN- BERG, D. P. A Progressive Refinement Approach to Fast Radiosity Image Generation. Computer Graphics (Proc. SIGGRAPH ’88) 22,4 (1988),75-84.
6. COHEN, M. F., AND GREENBERG, D. P. The Hemi-Cube: A Radiosity Solution for Complex Environments. Computer Graphics (Proc. SIGGRAPH ’85) 19, 3 (1985), 31-40.
7. FUCHS, H., KEDEM, Z., AND NAYLOR, B. On visible surface generation by a priori tree structures. Computer Graphics (Proc. SIG- GRAPH ’80) 14, 3 (1980), 124-133.
8. EUNKHOUSER, T. A., S~,QUIN, C. H., AND TELLER, S. Management of Large Amounts of Data in Interactive Building Walkthroughs. In Proc. 1992 Workshop on Interactive 3D Graphics (1992), pp. 11 – 20.
9. Q~IGUS, Z., CANNY, J., AND SEIDEL, R. EfficienflyComputing and Representing Aspect Graphs of Polyhedral Objects. IEEE Transactions on Pattern Analysis and Machine Intelligence 13,6 (1991), 542-551.
10. HAINES, E. A., AND WALLACE, J. R. Shaft Culling for Efficient Ray-Traced Radiosity. In Proc. 2~d Eurographics Workshop on Rendering (May 1991).
11. HANRAHAN, P., SALZMAN, D., AND AUPPERLE, L. A Rapid Hierarchical Radiosity Algorithm. Computer Graphics (Proc. SIG- GRAPH ’91) 25, 4 ( 1991 ), 197 – 206.
12. HECKBERT, P. S. Simulating Globallllumination Using Adaptive Meshing. PhD thesis, Computer Sciences Department, UC Berkeley, June 1991.
13. LISCHINSKI, D., TAMPIERI, F., AND GREENBERG, D. P. Discontinuity Meshing for Accurate Radiosity. IEEE Computer Graphics andApplications 12,6 (1992),25-39.
14. LISCHINSKI, D., TAMPIERI, F., AND GREENBERG, D. P. Combining Hierarchical Radiosity and Discontinuity Meshing. Computer Graphics (Proc. SIGGRAPH ’93) 27 (1993).
15. MEGIDDO, N. Linear programming in linear time when the dimension is fixed. Journalofthe ACM 31 (1984), 114-127.
16. NISHITA, T., AND NAKAMAE, E. Half-Tone Representation of 3-D Objects Illuminated by Area Sources or Polyhedron Sources. In Proc. IEEE COMPSAC, 1983 (1983), pp. 237-242.
17. PLANTINGA, H. An algorithm for finding the weakly visible faces from a polygon in 3D. Tech. Rep. 92 – 11, U of Pittsburgh, 1992.
18. PLANTINGA, W., AND DYER, C. An algorithm for constructing the aspect graph. In Proc. 27th Annual IEEE Symposium on Foundations of Computer Science (1986), pp. 123-131.
19. SEIDEL, R. Small-dimensional linear programming and convex hulls made easy. Discrete and Computational Geometry (1991), 423 -434.
20. SOMMERVILLE, D. Analytical Geometry of Three Dimensions. Cambridge University Press, 1959.
21. TELLER, S. Computing the Antipenumbra Cast by an Area Light Source. Computer Graphics (Proc. SIGGRAPH ’92) 26, 2 (1992), 139-148.
22. TELLER, S. Visibility Computations in Densely Occluded Polyhedral Environments. PhD thesis, CS Dept., UC Berkeley, 1992.
23. TELLER, S., AND HOHMEYER, M. E. Computing the Lines Piercing Four Lines. Tech. Rep. UCB/CSD 91/665, Computer Science Department, UC Berkeley, 1991.
24. TELLER, S., AND SEQUIN, C. H. Visibility Preprocessing for Interactive Walkthroughs. Computer Graphics (Proc. SIGGRAPH ’91) 25, 4 (1991), 61-69.
25. ZHAO, J., AND DOBKIN, D. Personal communication, 1992.