“Robust epsilon visibility”

Analytic visibility algorithms, for example methods which compute a subdivided mesh to represent shadows, are notoriously unrobust and hard to use in practice. We present a new method based on a generalized definition of extremal stabbing lines, which are the extremities of shadow boundaries. We treat scenes containing multiple edges or vertices in degenerate configurations, (e.g., collinear or coplanar). We introduce a robust ε method to determine whether each generalized extremal stabbing line is blocked, or is touched by these scene elements, and thus added to the line’s generators. We develop robust blocker predicates for polygons which are smaller than ε. For larger ε values, small shadow features merge and eventually disappear. We can thus robustly connect generalized extremal stabbing lines in degenerate scenes to form shadow boundaries. We show that our approach is consistent, and that shadow boundary connectivity is preserved when features merge. We have implemented our algorithm, and show that we can robustly compute analytic shadow boundaries to the precision of our chosen ε threshold for non-trivial models, containing numerous degeneracies.

1. M. Agrawala, R. Ramamoorthi, A. Heirich, and L. Moll. Efficient image-based methods for rendering soft shadows. In ACM SIGGRAPH 2000, Annual Conference Series, pages 375-384, July 2000. Google Scholar
2. K. Bala, J. Dorsey, and S. Teller. Radiance interpolants for accelerated bounded-error ray tracing. ACM Transactions on Graphics, 18(3):213-256, July 1999. Google Scholar
3. A. T. Campbell, III and D. S. Fussell. Adaptive mesh generation for global diffuse illumination. Computer Graphics (Proc. SIGGRAPH ’90), 24:155-164, August 1990. Google Scholar
4. N. Chin and S. Feiner. Fast object-precision shadow generation for areal light sources using BSP trees. In Computer Graphics (1992 Symposium on Interactive 3D Graphics), volume 25, pages 21-30, March 1992. Google Scholar
5. F. C. Crow. Shadow algorithms for computer graphics. Computer Graphics (Proc. SIGGRAPH 77), 11(2):242-248, July 1977. Google Scholar
6. G. Drettakis and E. Fiume. A fast shadow algorithm for area light sources using back projection. In ACM SIGGRAPH 94, Annual Conference Series, pages 223-230, July 1994. Google Scholar
7. T. Duff. Interval arithmetic and recursive subdivision for implicit functions and constructive solid geometry. Computer Graphics (Proc. SIGGRAPH’92), 26(2):131-138, July 1992. Google Scholar
8. F. Durand. 3D Visibility: analytical study and applications. PhD thesis, Université Joseph Fourier, Grenoble I, July 1999. http://www-imagis.imag.fr.Google Scholar
9. F. Durand, G. Drettakis, and C. Puech. The Visibility Skeleton: A Powerful and Efficient Multi-Purpose Global Visibility Tool. In ACM SIGGRAPH 97 (Los Angeles, CA), Annual Conference Series, August 1997. Google Scholar
10. F. Durand, G. Drettakis, and C. Puech. Fast and accurate hierarchical radiosity using global visibility. ACM Trans. on Graphics, 18(2):128-170, Apr 1999. Google Scholar
11. Z. Gigus and J. Malik. Computing the aspect graph for the line drawings of polyhedral objects. IEEE Trans. Pattern Analysis and Machine Intelligence, 12(2), February 1990. Google Scholar
12. E. A. Haines. Shaft culling for efficient ray-traced radiosity. In Photorealistic Rendering in Comp. Graphics, pages 122-138. Springer Verlag, 1993. Proc. 2nd EG Workshop on Rendering (Barcelona, 1991).Google Scholar
13. P. Heckbert. Discontinuity meshing for radiosity. Proc. Third Eurographics Workshop on Rendering, Bristol, pages 203-226, May 1992.Google Scholar
14. J. J. Koenderink and A. J. van Doorn. The internal representation of solid shape with respect to vision. Biological Cybernetics, 32(4):211-216, 1979.Google Scholar
15. L. Leblanc and P. Poulin. Guaranteed occlusion and visibility in cluster hierarchical radiosity. In Rendering Techniques 2000, (Proc. 11th Eurographics Workshop on Rendering 2000), pages 89-100, June 2000. Google Scholar
16. D. Lischinski, F. Tampieri, and D. P. Greenberg. Discontinuity meshing for accurate radiosity. IEEE CGA, 12(6):25-39, November 1992. Google Scholar
17. nvidia. webpage. http://developer.nvidia.com/view.asp?IO=cedec_stencil.Google Scholar
18. D. Salesin, L. Guibas, and J. Stolfi. Epsilon geometry: Building robust algorithms from imprecise computations. In Annual Symposium on Computational Geometry, 1989. Saarbrucken, West Germany. Google Scholar
19. J. M. Snyder. Interval analysis for computer graphics. Computer Graphics (Proc. SIGGRAPH’92), 26(2):121-130, July 1992. Google Scholar
20. C. Soler and F. X. Sillion. Fast calculation of soft shadow textures using convolution. In ACM SIGGRAPH’98, Annual Conference Series, pages 321-332, Jul 1998. Google Scholar
21. A. J. Stewart and S. Ghali. Fast computation of shadow boundaries using spatial coherence and backprojections. In ACM SIGGRAPH 94, Annual Conference Series, pages 231-238, July 1994. Google Scholar
22. S. Teller. Visibility Computations in Densely Occluded Polyhedral Environments. PhD thesis, UC Berkeley, 1992. Google Scholar
23. S. J. Teller. Computing the antipenumbra of an area light source. Computer Graphics (Proc. SIGGRAPH 92), 26(4):139-148, July 1992. Google Scholar
24. K. Weiler and K. Atherton. Hidden surface removal using polygon area sorting. Computer Graphics (Proc. SIGGRAPH 77), 11(2):214-222, July 1977. Google Scholar
25. L. Williams. Casting curved shadows on curved surfaces. Computer Graphics (Proc. SIGGRAPH 78), 12(3):270-274, August 1978. Google Scholar