Résumé:
Nous nous intéressons aux problèmes de visibilité dans le cas d'objets courbes 3D. Nous cherchons à construire le graphe de visibilité d'un ensemble d'objets dans une scène; les noeuds du graphe sont les objets et deux objets sont reliés par une arête s'ils sont mutuellement visibles. La seule manière connue pour calculer ce graphe passe par le calcul des segments libres maximaux tangents aux quadruplets d'objets.
Nous présentons ici un algorithme pour le calcul des tangentes libres à quatre sphères parmi un ensemble de n sphères unitaires. Pour obtenir un algorithme dont la complexité en moyenne est intéressante nous utilisons une discrétisation de R3 ainsi que de l'espace des droites (au voisinage des droites tangentes à deux sphères). L'algorithme calcule les tangentes libre à quatre sphères via le calcul du graphe de visibilité tangentiel (les arêtes représentes les paires de sphères ayant une tangente libre). Nous présentons quelques résultats expérimentaux.
Ce travail est fait en collaboration avec H. Everett et S. Lazard.