Fermeture de trous 3d

Un algorithme de fermeture de trous 3D

Personnes impliquées : Zouina Aktouf, Gilles Bertrand, Laurent Perroton.

Un trou dans un objet en 3D n'est pas une région de l'espace, comme on peut s'en convaincre en considérant un tore plein, qui est un objet comportant un unique trou (voir aussi les exemples de la Fig. ). Intuitivement, la présence d'un trou dans un objet peut être caractérisée par l'existence d'un chemin fermé inclus dans l'objet, et ne pouvant être transformé de façon continue en un point unique, tout en restant dans l'objet.

Fermer des trous dans des objets 3D n'est donc pas un problème trivial, en particulier il n'est pas possible d'utiliser, comme en 2D, des algorithmes de recherche de composantes connexes.

En se basant sur les études que nous avons faites sur la topologie de Z³, nous proposons une méthode pour fermer des trous dans un objet 3D. Cette méthode permet de plus de contrôler par un paramètre la ``taille'' des trous à fermer (Fig. ). Elle peut être implantée en un temps linéaire. A notre connaissance, il s'agit de la première méthode pour résoudre ce problème [ABP96].

L'idée de base de la méthode consiste à plonger l'objet X dont on veut fermer les trous, dans un autre objet Y connexe et sans trou, tel qu'un cube par exemple. On amincit itérativement Y en enlevant des points n'appartenant pas à l'objet X, et en s'assurant que l'enlèvement du point ne crée pas de trou. Ce test est effectué à l'aide des nombres topologiques (voir ci-dessus). Afin d'obtenir un résultat bien ``centré'' sur l'objet X, on guide le processus d'amincissement par une transformation de distance. Cette information de distance nous permet par ailleurs de fermer sélectivement des trous suivant un critère de "taille" (voir Figure 8 et Figure 8b).

Figure 8: Illustration d'un algorithme de fermeture de trous dans des objets 3D.
Figure 8b: Visualisation (animation) du processus de fermeture de trous.