“Computing exact shadow irradiance using splines” by Stark, Cohen, Lyche and Riesenfeld

We present a solution to the general problem of characterizing shadows in scenes involving a uniform polygonal area emitter and a polygonal occluder in arbitrary position by manifesting shadow irradiance as a spline function. Studying generalized prism-like constructions generated by the emitter and the occluder in a four-dimensional (shadow) space reveals a simpler intrinsic structure of the shadow as compared to the more complicated 2D projection onto a receiver. A closed form expression for the spline shadow irradiance function is derived by twice applying Stokes’ theorem to reduce an evaluation over a 4D domain to an explicit formula involving only 2D faces on the receiver, derived from the scene geometry. This leads to a straightforward computational algorithm and an interactive implementation. Moreover, this approach can be extended to scenes involving multiple emitters and occluders, as well as curved emitters, occluders, and receivers. Spline functions are constructed from these prism-like objects. We call them generalized polyhedral splines because they extend the classical polyhedral splines to include curved boundaries and a density function. The approach can be applied to more general problems such as some of those occurring in radiosity, and other related topics.

1. James Arvo. The irradiance Jacobian for Partially Occluded Polyhedral Sources. In Andrew Glassner, editor, SIGGRAPH 94 Conference P~vceedings, Annual Conference Series, pages 343-350. ACM SIGGRAPH, ACM Press, July 1994. ISBN 0-89791-667-0.
2. James Arvo. Analytic Methods for Simultated Light Transport. PhD thesis, Yale University, 1995.
3. Daniel R. Baum, Holly E. Rushmeier, and James M. Winget. Improving Radiosity Solutions Through the Use of Analytically Determined Form-Factors. In Jeffrey Lane, editor, Computer Graphics (SIGGRAPH 89 Conference P1vceedings), volume 23, pages 325-334, July 1989. ISBN 0-89791-746-4.
4. C. de Boor and K. HNlig. Recurrence Relations for Multivariate B-Splines. P~vc. Ame1: Math. Soc., pages 397-400, 1982.
5. C. de Boor, K. HNlig, and S. Riemenschneider. Box Splines. Springer-Verlag, 1993.
6. Ame BrOndsted. An Int~vduction to Convex Polytopes. Springer-Verlag, New York, 1983.
7. A.T. Campbell, III and Donald S. Fussell. Adaptive Mesh Generation for Global Diffuse Illumination. In Forest Baskett, editor, Computer Graphics (SIGGRAPH 90 Conference Proceedings), volume 24, pages 155-164, August 1990. ISBN 0-89791-344-2.
8. Elaine Cohen, Tom Lyche, and Richard Riesenfeld. Discrete Box Splines and Refinement Algorithms. Computer Aided Geometric Design, 1(2):131-148, 1984.
9. Michael F. Cohen and Donald P. Greenberg. The Hemi-Cube: A Radiosity Solution for Complex Environments. In B. A. Barsky, editor, Computer Graphics (SIGGRAPH 85 Conference Proceedings), volume 19, pages 31-40, August 1985.
10. Michael F. Cohen and John R. Wallace. Radiosity and Realistic Image Synthesis. Academic Press Professional, San Diego, CA, 1993.
11. Robert L. Cook, Thomas Porter, and Loren Carpenter. Distributed Ray Tracing. In Hank Christiansen, editor, Computer Graphics (SIGGRAPH 84 Conference Proceedings), volume 18, pages 137-45, July 1984.
12. H. S. M. Coxeter. Regular Complex Polytopes, Second Edition. Cambridge University Press, New York, 1991.
13. Franklin C. Crow. Summed-area Tables for Texture Mapping. In Hank Christiansen, editor, Computer Graphics (SIGGRAPH 84 Conference Proceedings), volume 18, pages 207-212, July 1984.
14. H.B. Curry and I. J. Schoenberg. On P61ya frequency functions IV: the fundamental spline functions and their limits. J. Analyse Math., 17:71-107, 1966.
15. M. Da~hlen and T. Lyche. Box Splines and Applications. Geometric Modelling, Methods and Applications, pages 35-93, 1991.
16. W. Dahmen and C. A. Micchelli. Recent Progress in Multivariate Splines. In C. Chui, L. Schumaker, and J. Ward, editors, Approximation Theory IV, pages 27-121. Academic Press, New York, 1983.
17. George Drettakis. Structured Sampling and Reconstruction of Illumination for Image Synthisis. PhD thesis, University of Toronto, 1994.
18. George Drettakis and Eugene Fiume. A Fast Shadow Algorithm for Area Light Sources Using Backprojection. In Andrew Glassner, editor, SIGGRAPH 94 Conference Proceedings, Annual Conference Series, pages 223-230. ACM SIG- GRAPH, ACM Press, July 1994. ISBN 0-89791-667-0.
19. P. Fong and Hans-Peter Seidel. Modeling with multivariate B-spline surfaces over arbitrary triangulations. In M. Silbermann and H. Tagare, editors, Curves and Smfaces in Computer Vision and Graphics II, pages 97-108. SPIE, 1992.
20. Philip Fong and Hans-Peter Seidel. An implementation of multivariate B-spline surfaces over arbitrary triangulations. In Proceedings of Graphics Interface ’92, pages 1-10, May 1992.
21. Cindy M. Goral, Kenneth E. Torrance, Donald P. Greenberg, and Bennett Battaile. Modelling the Interaction of Light Between Diffuse Surfaces. In Hank Christiansen, editor, Computer Graphics (SIGGRAPH 84 Conference Proceedings), volume 18, pages 212-22, July 1984.
22. Steven J. Gortler, Peter Schroder, Michael F. Cohen, and Pat Hanrahan. Wavelet Radiosity. In Computer Graphics Proceedings, Annual Conference Series, 1993, pages 221-230, 1993.
23. Branko Gr~nbaum. Convex Polytopes. John Wiley & Sons, 1967.
24. Pat Hanrahan, David Salzman, and Larry Aupperle. A Rapid Hierarchical Radiosity Algorithm. In Thomas W. Sederberg, editor, Computer Graphics (SIG- GRAPH 91 Conference Proceedings), volume 25, pages 197-206, July 1991. ISBN 0-89791-436-8.
25. Paul Heckbert. Discontinuity Meshing for Radiosity. Third Eurographics Workshop on Rendering, pages 203-226, May 1992.
26. Paul Heckbert. Radiosity in Flatland. Computer Graphics Forum (Eurographics ’92), 11(3):181-192, September 1992.
27. G. Heflin and G. Elber. Shadow Volume Generation from Free Form Surfaces. In Communicating with Virtual Worlds, Proceedings of CGI’ 93 (Lausanne, Switzerland), pages 115-126. Springer-Verlag, June 1993.
28. J. R. Howell. A Catalog of Radiation Configuration Factors. McGraw Hill, 1982.
29. Marc Levoy and Pat Hanrahan. Light Field Rendering. In Holly Rushmeier, editor, SIGGRAPH 96 Conference Proceedings, Annual Conference Series, pages 31-42. ACM SIGGRAPH, Addison Wesley, August 1996. ISBN 0-89791-746-4.
30. Daniel Lischinski, Filippo Tampieri, and Donald P. Greenberg. Discontinuity Meshing for Accurate Radiosity. IEEE Computer Graphics and Applications, 12(6):25-39, November 1992.
31. Michael D. McCool. Analytic Antialiasing With Prism Splines. In Robert Cook, editor, SIGGRAPH 95 Conference Proceedings, Annual Conference Seties, pages 429-436. ACM SIGGRAPH, Addison Wesley, August 1995. ISBN 0-89791-701-4.
32. Michael D. McCool. Analytic Signal P1vcessing for Computer Graphics using Multivariate Polyhedral Splines. PhD thesis, University of Toronto, 1995.
33. Tomoyuki Nishita and Eihachiro Nakamae. Continuous Tone Representation of Three-Dimensional Objects Taking Account of Shadows and Interreflection. In B. A. Barsky, editor, Computer Graphics (SIGGRAPH 85 Conference Proceedings), volume 19, pages 23-30, July 1985.
34. William T. Reeves, David H. Salesin, and Robert L. Cook. Rendering Antialiased Shadows with Depth Maps. In Maureen C. Stone, editor, Computer Graphics (SIGGRAPH 87 Conference Proceedings), volume 21, pages 283-291, July 1987. ISBN 0-89791-227-6.
35. Peter Schr~Sder and Pat Hanrahan. On the Form Factor Between Two Polygons. In James T. Kajiya, editor, SIGGRAPH 93 Conference Proceedings, Annual Conterence Series, pages 163-164,1993. ISBN 0-89791-601-8.
36. Peter Shirley, Chang Yaw Wang, and Kurt Zimmerman. Monte Carlo Techniques for Direct Lighting Calculations. ACM Transactions on Graphics, 15(1):1-36, January 1996. ISSN 0730-0301.
37. Franqois Sillion and Claude Puech. Radiosity and Global Illumination. Morgan Kaufmann, San Francisco, 1994.
38. Cyril Soler and Franqois X. Sillion. Fast Calculation of Soft Shadow Textures Using Convolution. In Michael Cohen, editor, SIGGRAPH 98 Conference P1vceedings, Annual Conference Series, pages 321-332. ACM SIGGRAPH, Addison Wesley, July 1998. ISBN 0-89791-999-8.
39. Seth J. Teller. Computing the Antipenumbra of an Area Light Source. UCB/CSD 91 6, Computer Science Division, University of California, Berkeley, 1991.
40. John R. Wallace, Kells A. Elmquist, and Eric A. Haines. A Ray Tracing Algorithm for Progressive Radiosity. In Jeffrey Lane, editor, Computer Graphics (SIGGRAPH 89 Conference Proceedings), volume 23, pages 315-324, July 1989.
41. Gregory J. Ward and Paul Heckbert. Irradiance Gradients. Third Eurographics Workshop on Rendering, pages 85-98, May 1992.
42. Turner Whitted. An Improved Illumination Model for Shaded Display. Communications of the ACM, 23(6):343-349, July 1980.
43. Lance Williams. Casting Curved Shadows on Curved Surfaces. In Computer Graphics (SIGGRAPH 78 Conference Proceedings), volume 12, pages 270-274, Aug 1978.
44. Andrew Woo, Pierre Poulin, and Alain Fournier. A Survey of Shadow Algorithms. IEEE Computer Graphics and Applications, 10(6):13-32, November 1990.