On the Complexity of 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
INRIA Futurs, 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. 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 polygonal or polytopal obstacles. In particular, we show that a 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 complexity $n$ can give rise to $\Omega(n)$ connected components. 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 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 are 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 bounds, the first ones in terms of both $k$ and $n$, prove that the umbra is much more intricate than the full light boundary whose worst-case complexity is, as we show, in $\Omega(nk +k^4)$ and $O(nk\alpha(k^2) +k^4)$. We also improve these last bounds when the number of light sources is bounded.
Type de document :
Rapport
[Research Report] RR-6347, INRIA. 2007, pp.28
Liste complète des métadonnées

https://hal.inria.fr/inria-00186262
Contributeur : Rapport de Recherche Inria <>
Soumis le : jeudi 8 novembre 2007 - 15:58:11
Dernière modification le : jeudi 11 janvier 2018 - 16:41:48
Document(s) archivé(s) le : mardi 21 septembre 2010 - 15:10:49

Fichiers

RR-6347.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00186262, version 2

Citation

Julien Demouth, Olivier Devillers, Hazel Everett, Marc Glisse, Sylvain Lazard, et al.. On the Complexity of Umbra and Penumbra. [Research Report] RR-6347, INRIA. 2007, pp.28. 〈inria-00186262v2〉

Partager

Métriques

Consultations de la notice

401

Téléchargements de fichiers

276