Between umbra and penumbra

ABSTRACT

Computing shadow boundaries is a difficult problem in the case of non-pointlight sources. A point is in the umbra if it does not see any part of anylight source; it is in full light if it sees entirely all the light sources;otherwise, it is in the penumbra. While the common boundary of the penumbraand the full light is well understood, less is known about the boundary of theumbra. In this paper we prove various bounds on the complexity of the umbra andthe penumbra cast by a segment or polygonal light source on a plane in the presence ofpolygon or polytope obstacles. In particular, we show that a single segment light source may cast on a plane, in thepresence of two triangles, four connected components of umbra and that two fatconvex obstacles of total complexity n can engender Ω(n) connectedcomponents of umbra. In a scene consisting of a segment light source and kdisjoint polytopes of total complexity n, we prove an Ω(nk²+k⁴)lower bound on the maximum number of connected components of the umbra and a O(nk³) upper bound on its complexity. We also prove that, in the presence of kdisjoint polytopes of total complexity n, some of which being light sources,the umbra cast on a plane may have Ω(n²k³ +nk⁵) connected components and has complexity O(n³k³).These are the first bounds on the size of the umbra in terms of both k and n. These results prove that the umbra, which is bounded by arcs of conics,is intrinsically much more intricate than the full light/penumbra boundary whichis bounded by linesegments and whose worst-case complexity is in Ω(nα(k) +km +k²) and O(nα(k) + kmα(k) +k²), where m is the complexity of the polygonallight source.

REFERENCES

• 1: Boris Aronov , Micha Sharir, The common exterior of convex polygons in the plane, Computational Geometry: Theory and Applications, v.8 n.3, p.139-149, Aug. 1997 [doi>10.1016/S0925-7721(96)00004-1 ]
• 2: H. Brönnimann, O. Devillers, V. Dujmović, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na, and S. Whitesides. On the number of maximal free line segments tangent to arbitrary three-dimensional convex polyhedra. Research Report n ^° 5671, INRIA, Sept. 2005. 28 pages.
• 3: H. Brönnimann, O. Devillers, V. Dujmović, H. Everett, M. Glisse, X. Goaoc, S. Lazard, H.-S. Na, and S. Whitesides. Lines and free line segments tangent to arbitrary three-dimensional convex polyhedra. SIAM Journal on Computing, 2006. To appear.
• 4: H. Brönnimann , H. Everett , S. Lazard , F. Sottile , S. Whitesides, Transversals to Line Segments in Three-Dimensional Space, Discrete & Computational Geometry, v.34 n.3, p.381-390, September 2005 [doi>10.1007/s00454-005-1183-1]
• 5: 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]
• 6: F. Durand. A multidisciplinary survey of visibility, 2000. ACM SIGGRAPH course notes, Visibility, Problems, Techniques, and Applications.
• 7: 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]
• 8: Frédo Durand , George Drettakis , Claude Puech, Fast and accurate hierarchical radiosity using global visibility, ACM Transactions on Graphics (TOG), v.18 n.2, p.128-170, April 1999 [doi>10.1145/318009.318012]
• 9: Frédo Durand , George Drettakis , Claude Puech, The 3D visibility complex, ACM Transactions on Graphics (TOG), v.21 n.2, p.176-206, April 2002 [doi>10.1145/508357.508362]
• 10: J-M. Hasenfratz, MLapierre, NHolzschuch, and FSillion. A survey of real-time soft shadows algorithms. In Eurographics, 2003.
• 11: P.S. Heckbert. Discontinuity meshing for radiosity. In Proceedings of the Third Eurographics Workshop on Rendering, pages 203--215, May 1992.
• 12: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 13: P. Mamassian, D.C. Knill, and D. Kersten. The perception of cast shadows. Trends in Cognitive Sciences, 2(8):288--295, 1998.
• 14: T. Nishita and E. Nakamae. Half-tone representation of 3D objects illuminated by area sources or polyhedron sources. In IEEE Computer Society's 7th International Computer Software and Applications Conference (COMPSAC '83), pages 237--242, 1983.
• 15: G. Salmon. Analytic Geometry of Three Dimensions. Cambridge, 1978.
• 16: 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]
• 17: 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
• 18: L. Wanger. The effect of shadow quality on the perception of spatial relationships in computer generated images. Computer Graphics, 25(2):39--42, 1992.
• 19: Ady Wiernik , Micha Sharir, Planar realizations of nonlinear Davenport-Schinzel sequences by segments, Discrete & Computational Geometry, v.3 n.1, p.15-47, Jan., 1988 [doi>10.1007/BF02187894]
• 20: Andrew Woo , Pierre Poulin , Alain Fournier, A Survey of Shadow Algorithms, IEEE Computer Graphics and Applications, v.10 n.6, p.13-32, November 1990 [doi>10.1109/38.62693 ]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture

General Terms:
Algorithms, Theory

Keywords:
complexity, discontinuity mesh, penumbra, shadows, umbra