Cette thèse présente principalement des résultats sur la combinatoire des droites et segments qui apparaissent naturellement dans l'étude des problèmes de visibilité en trois dimensions. Nous exposons en premier lieu des résultats sur la taille de la silhouette d'un objet vu d'un point, c'est à dire sur la complexite de l'ensemble des droites ou segments tangents à l'objet et passant par le point. Nous présentons en particulier les premières bornes théoriques non triviales pour des polyèdres non-convexes, à savoir que, sous des hypothèses raisonnables, la complexité moyenne de la silhouette est au plus la racine carrée de la complexité du polyèdre, phénomène largement observé en infographie. Nous présentons aussi des bornes, en moyenne et dans le cas le pire, sur le nombre de droites et segments tangents à quatre objets dans une scène composée d'objets polyédriques ou sphériques. Ces bornes donnent en particulier l'espoir que la complexité des structures de données globales comme le complexe de visibilité ne soit pas nécessairement prohibitive. Les bornes sur les polytopes sont également les premières à tirer parti des propriétés structurelles des scènes composées de triangles organisés en polytopes de facon réaliste, c'est à dire non nécessairement disjoints. Ces bornes induisent enfin les premières bornes non triviales sur la complexité des ombres induites par des sources lumineuses non ponctuelles. Les résultats presentés dans cette thèse améliorent significativement l'état de l'art sur les propriétés combinatoires des structures de visibilité en trois dimensions et devraient favoriser les développements algorithmiques futurs pour ces problèmes.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00192337 |
| Date | 29 October 2007 |
| Creators | Glisse, Marc |
| Publisher | Université Nancy II |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0024 seconds