Je travaille sur les problèmes de visibilité. Je cherche à développer des algorithmes et structures de données permettant des requêtes efficaces de visibilité comme "quel objet est visible de ce point ?", "Quels objets sont mutuellement visibles ?", etc. Le but est bien sûr d'exploiter la cohérence spatiale et la cohérence temporelle.
L'idée est d'effectuer un précalcul pour construire une structure de donnée qui permettra des requêtes efficaces.
A partir des travaux en 2D de Michel Pocchiola et Gert Vegter sur le complexe de visibilité, je développe une structure similaire en 3D. Ce complexe de visibilité 3D servira (j'espère !) en simulation de l'éclairage (Pour la méthode de radiosité et le calcul des facteurs de forme), en vision (elle est liée aux graphes d'aspect) et peut-être aussi pour la planification de trajectoire (le déplacement d'un robot est en fait similaire à la propagation de rayons lumineux).
Auparavant, en DEA, j'avais travaillé sur le complexe de visibilité 2D, j'ai réalisé un système de visualisation de cette structure de donnée complexe, et j'ai proposé des solutions pour une approche hiérarchique multi-échelle du complexe de visibilité 2D, concepts qui je l'espère pourront être réutilisé en 3D.
Le complexe de visibilité 2D
L'idéé est de regrouper tous les rayons lumineux qui "voient" le même objet.
Les changements de visibilité interviennent quand on considère des rayons tangent à un objet (les arêtes du complexe) ou à deux objets (les sommets du complexe).
Pour une meilleure introduction.
Rachel Orti a montré l'intérêt de cette structure de donnée pour les calculs de radiosité.
Voir à ce sujet la version html de notre vidéo.
Aller voir aussi la biblio de Michel Pocchiola et la page de Stéphane Rivière.
Le complexe de visibilité 3D
Soit une scène dans l'espace 3D composée d'objets qui seront des obstacles à la propagation de la lumière (ou d'un robot...). On appelle segment libre maximal, un segment dont les deux extrémités sont sur des objets mais qui ne coupe l'intérieur d'aucun objet.L'ensemble des segments libres maximaux est de variété 4 (même s'il est plongé dans un espace 5D...)
Le complexe de visibilité est la partition des segments libres maximaux selon leurs extrémités. L'idée est de regrouper les rayons lumineux qui voient les mêmes objets.
Une face du complexe est de variété 4, il s'agit d'un ensemble de segments qui voient les deux mêmes objets.
Elles sont délimitées par des ensemble de dimension inférieures qui correspondent à des segments tangent à 1, 2, 3 ou 4 objets. Cela correspond à des changements de visibilité.
Je suis en train de développer un algorithme de balayage (un triple balayage en fait) pour construire le complexe d'une scène polygonale.
Ensuite je compte utiliser les faces du complexe pour calculer les facteurs de formes entre deux objets (cad l'échange d'énergie entre ces deux objets) qui sont fondamentaux en radiosité. J'aurai aussi accès, grâces aux frontières des faces du complexes, aux limites entre ombre et pénombre, ce qui est également très utile pour la simulation de l'éclairage.
Je pense aussi utiliser le complexe pour des calculs de "walkthrough". Cela consiste à maintenir, lors d'un déplacement à l'intérieur de la scène, l'intersection entre l'ensemble des segments qui passent par le point de vue avec le complexe de visibilité.
J'espère aussi m'intérresser aux liens entre le complexe de visibilité et les graphes d'aspect.