Between umbra and penumbra

Julien Demouth 1 Olivier Devillers 2 Hazel Everett 1 Marc Glisse 1 Sylvain Lazard 1 Raimund Seidel 3
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Computing shadow boundaries is a difficult problem in the case of non-point light sources. A point is in the umbra if it does not see any part of any light 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 penumbra and the full light is well understood, less is known about the boundary of the umbra. In this paper we prove various bounds on the complexity of the umbra and the penumbra cast by a segment or polygonal light source on a plane in the presence of polygon or polytope obstacles. In particular, we show that a single segment light source may cast on a plane, in the presence of two triangles, four connected components of umbra and that two fat convex obstacles of total complexity n can engender Omega(n) connected components of umbra. In a scene consisting of a segment light source and k disjoint polytopes of total complexity n, we prove an Omega(nk^2+k^4) lower bound on the maximum number of connected components of the umbra and a O(nk^3) upper bound on its complexity. We also prove that, in the presence of k disjoint polytopes of total complexity n, some of which being light sources, the umbra cast on a plane may have Omega(n^2k^3 + nk^5) connected components and has complexity O(n^3k^3). 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 which is bounded by line segments and whose worst-case complexity is in Omega(n alpha(k) +km +k^2) and O(n alpha(k) +km alpha(k) +k^2), where m is the complexity of the polygonal light source.
Type de document :
Communication dans un congrès
23rd Annual Symposium on Computational Geometry - SOCG 2007, Jun 2007, Gyeongju, South Korea. ACM, Session 8A, pp.265-274, 2007, Proceedings of the twenty-third annual symposium on Computational geometry. 〈10.1145/1247069.1247117〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00187253
Contributeur : Olivier Devillers <>
Soumis le : mercredi 14 novembre 2007 - 09:51:06
Dernière modification le : mardi 31 octobre 2017 - 14:22:18
Document(s) archivé(s) le : lundi 24 septembre 2012 - 15:25:35

Fichier

hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Julien Demouth, Olivier Devillers, Hazel Everett, Marc Glisse, Sylvain Lazard, et al.. Between umbra and penumbra. 23rd Annual Symposium on Computational Geometry - SOCG 2007, Jun 2007, Gyeongju, South Korea. ACM, Session 8A, pp.265-274, 2007, Proceedings of the twenty-third annual symposium on Computational geometry. 〈10.1145/1247069.1247117〉. 〈inria-00187253〉

Partager

Métriques

Consultations de la notice

384

Téléchargements de fichiers

480