chiver dans la mémoire de l’ordinateur, de
procéder aisément à des calculs, voire de modifier l’objet ou d’en télécommander l’usinage
d’une copie. Bref, une fois que la forme d’un
objet réel est numériquement enregistrée, et
ce avec suffisamment de précision, on dispose
de maintes possibilités d’action et de calcul.
Les enjeux économique et industriel du
problème de la reconstruction de surfaces, son
caractère fondamental du point de vue scientifique, ont conduit à de nombreux travaux
depuis une vingtaine d’années. Mais ce n’est
que très récemment que les spécialistes ont
formalisé en termes mathématiques le problème, ce qui leur a permis de concevoir des
algorithmes efficaces et fournissant une
reconstruction fidèle. Le transfert vers l’industrie de certains de ces résultats de géométrie dite algorithmique s’est alors opéré de
manière très rapide au travers de la création
de jeunes pousses (comme Raindrop Geomagic
aux États-Unis) ou le lancement de nouveaux
produits par les leaders de la conception assistée par ordinateur ou de l’imagerie médicale
(Dassault Systèmes, Siemens Medical).
Diagrammes de Voronoï et
triangulation de Delaunay, deux
outils géométriques indispensables
Pour reconstruire une surface à partir d’un
nuage de points qui l’échantillonnent, la
grande majorité des algorithmes utilisent un
outil central en géométrie algorithmique : la
triangulation de Delaunay, nommée d’après
Boris Delone (1890-1980), mathématicien russe
dont le nom a été francisé en Delaunay. La triangulation de Delaunay se définit naturellement à partir de ce qu’on appelle le diagramme
de Voronoï, du nom du mathématicien russe
Georgi Voronoï (1868-1908). Considérons un
ensemble fini de points dans l’espace, et appelons-le E. Le diagramme de Voronoï de E est
une division de l’espace en cellules convexes
(en bleu sur la Figure 2), où chaque cellule est
constituée des points de l’espace plus proches
d’un point de E que des autres points de E.
Les cellules — ce sont des polyèdres convexes
— sont ainsi définies de manière univoque.
Maintenant, relions par des segments de
droite les points de E dont les cellules de
Voronoï sont adjacentes. L’ensemble de ces
segments constitue la triangulation de
Delaunay (en vert sur la Figure 2) associée à
E. Ces structures se définissent dans des
espaces de dimension quelconque ; c’est le cas
de la dimension trois — l’espace usuel — qui
est le plus intéressant pour la reconstruction
de surfaces. Les diagrammes de Voronoï
(Figures 2 et 3) figurent parmi les principaux
Reconstruire des surfaces pour l’imagerie
89
Figure 2. Le diagramme de Voronoï (en bleu) et la triangulation de
Delaunay (en vert) d’un ensemble de points (marqués en rouge). Le
diagramme de Voronoï et la triangulation de Delaunay sont des outils
fondamentaux en géométrie algorithmique.
procéder aisément à des calculs, voire de modifier l’objet ou d’en télécommander l’usinage
d’une copie. Bref, une fois que la forme d’un
objet réel est numériquement enregistrée, et
ce avec suffisamment de précision, on dispose
de maintes possibilités d’action et de calcul.
Les enjeux économique et industriel du
problème de la reconstruction de surfaces, son
caractère fondamental du point de vue scientifique, ont conduit à de nombreux travaux
depuis une vingtaine d’années. Mais ce n’est
que très récemment que les spécialistes ont
formalisé en termes mathématiques le problème, ce qui leur a permis de concevoir des
algorithmes efficaces et fournissant une
reconstruction fidèle. Le transfert vers l’industrie de certains de ces résultats de géométrie dite algorithmique s’est alors opéré de
manière très rapide au travers de la création
de jeunes pousses (comme Raindrop Geomagic
aux États-Unis) ou le lancement de nouveaux
produits par les leaders de la conception assistée par ordinateur ou de l’imagerie médicale
(Dassault Systèmes, Siemens Medical).
Diagrammes de Voronoï et
triangulation de Delaunay, deux
outils géométriques indispensables
Pour reconstruire une surface à partir d’un
nuage de points qui l’échantillonnent, la
grande majorité des algorithmes utilisent un
outil central en géométrie algorithmique : la
triangulation de Delaunay, nommée d’après
Boris Delone (1890-1980), mathématicien russe
dont le nom a été francisé en Delaunay. La triangulation de Delaunay se définit naturellement à partir de ce qu’on appelle le diagramme
de Voronoï, du nom du mathématicien russe
Georgi Voronoï (1868-1908). Considérons un
ensemble fini de points dans l’espace, et appelons-le E. Le diagramme de Voronoï de E est
une division de l’espace en cellules convexes
(en bleu sur la Figure 2), où chaque cellule est
constituée des points de l’espace plus proches
d’un point de E que des autres points de E.
Les cellules — ce sont des polyèdres convexes
— sont ainsi définies de manière univoque.
Maintenant, relions par des segments de
droite les points de E dont les cellules de
Voronoï sont adjacentes. L’ensemble de ces
segments constitue la triangulation de
Delaunay (en vert sur la Figure 2) associée à
E. Ces structures se définissent dans des
espaces de dimension quelconque ; c’est le cas
de la dimension trois — l’espace usuel — qui
est le plus intéressant pour la reconstruction
de surfaces. Les diagrammes de Voronoï
(Figures 2 et 3) figurent parmi les principaux
Reconstruire des surfaces pour l’imagerie
89
Figure 2. Le diagramme de Voronoï (en bleu) et la triangulation de
Delaunay (en vert) d’un ensemble de points (marqués en rouge). Le
diagramme de Voronoï et la triangulation de Delaunay sont des outils
fondamentaux en géométrie algorithmique.