Maillage et traitement des nuages de points

Une fois obtenus des nuages de points (par scan laser ou par photogrammétrie), il faut nettoyer les nuages de leurs points aberrants et erreurs. Par exemple, nettoyer le bruit d’un nuage, dus au bruit des photographies, en calculant pour chaque point sa densité de voisinage.

nettoyage
nettoyage du bruit sur un bas-relief de Goujon (sous MeshLab)

D’une manière générale, pour chaque nuage, on l’entoure de ses voisins (ceux qui possèdent des points en communs avec lui), et on supprime les éléments imparfaits et/ou inutiles. On ouvre tous les nuages ensemble (réduits ou non, selon la capacité de la machine), on effectue les dernières rectifications, et on assemble tous les nuages pour n’en former qu’un.

Par la suite, nous avons réduit la densité des nuages par échantillonnage de Poisson. Réduire le nuage à environ 1M de points permet à une machine de capacité standard de calculer les normales de ses points, et même de le trianguler selon Poisson (Kahzdan 2006). Par la suite on peut facilement réattribuer au modèle polygonal les couleurs et attributs du nuage de points haute résolution. Il arrive que la triangulation forme quelques erreurs sur les modèles, modifiables à la main, en fonction des détails du modèle auxquels on tient. Ces erreurs sont souvent dues à des problèmes d’orientations de quelques groupes de normales.

CGAL de l’INRIA

L’Inria développe actuellement un logiciel CGAL permettant de trianguler un nuage de point par méthode du Ball-Pivoting.

L’algorithme Ball-Pivoting a été développé par Bernardini, Taubin et al. dans les laboratoires IBM[1]. Il procède par propagation : les triangles d’un maillage sont construits progressivement de proche en proche. Le maillage est créé tel que, pour tout triangle, une boule de rayon ρ qui passe par ses trois sommets ne contient aucun autre point ; le rayon ρ est défini par l’utilisateur en fonction de la résolution souhaitée pour le maillage. Si l’on détaille la construction :

  • Initialement, trois points A, B et C du nuage sont choisis pour former un triangle souche ;
  • Une boule de rayon ρ est positionnée sur ce triangle ABC
  • Celle-ci pivote autour de l’arête AB, jusqu’à ce qu’elle touche un autre point C’. En ce cas, on crée un triangle ABC’ et on le rajoute à la liste des triangles à traiter. Si aucun point n’est atteint par la boule quand elle pivote autour de AB, alors cette arête sera une frontière de la surface.
  • La boule fait de même avec les arêtes BC et AC, pour éventuellement créer deux nouveaux triangles A’BC et AB’C. Le triangle ABC est considéré comme « traité »
  • S’il reste des triangles à traiter, l’algorithme traite le triangle en tête de liste (ordre de création).
  • Si, à la fin, il reste des points non inclus dans le maillage, l’algorithme en réélit trois pour sélectionner un nouveau triangle souche parmi les points encore libres.

Cette méthode a l’avantage d’être applicable à des nuages contenant plusieurs millions de points. La quantité réduite de RAM exigée par cette méthode, son rapidité d’exécution sont les avantages notables de cette méthode. Malheureusement, le maillage créé peut contenir des trous si le rayon ρ est choisi trop petit, et surtout, si les points sont bruités. Il faut alors rajouter des étapes intermédiaires, coûteuses en temps de calcul.

[1] F. Bernardini and J. Mittlelman and H. Rushmeir and C. Silva, The ball-pivoting algorithm for surface reconstruction ,IEEE Trans. Visual. Comput. Graphics , vol. 5, n. 8, pp. 349-359, (1999)