s'authentifier
version française rss feed

inria-00186262, version 2

On the Complexity of Umbra and Penumbra

Julien Demouth () a1, Olivier Devillers () 2, Hazel Everett () a1, Marc Glisse () 1, Sylvain Lazard () 1, Raimund Seidel () b3

N° RR-6347 (2007)

Résumé : 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.

  • Domaine : Informatique/Géométrie algorithmique
    Informatique/Synthèse d'image et réalité virtuelle
  • Mots-clés : Computational geometry – visibility – graphics – shadow computation
  • Référence interne : RR-6347
  • Versions disponibles :  v1 (08-11-2007) v2 (08-11-2007)
 
  • inria-00186262, version 2
  • oai:hal.inria.fr:inria-00186262
  • Contributeur : 
  • Soumis le : Jeudi 8 Novembre 2007, 15:58:11
  • Dernière modification le : Jeudi 16 Octobre 2008, 16:02:05
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...