Discussion :

[Laurent Gomila]

Bonjour

Je dois effectuer une triangulation (triangulation de l'espace paramètrique, pas de l'espace 3D) de carreaux de Bézier à l'aide de l'algorithme de Delaunay.

Pour un carreau plein aucun souci, l'algorithme fonctionne à merveille.

Par contre je dois maintenant gérer des carreaux "troués", à savoir contenant des contours intérieurs définis par des courbes B-Splines. Et là je n'arrive pas à adapter l'algorithme, toutes les idées de modif qui me viennent à l'esprit posent à un moment où l'autre problème.

Je n'ai pas non plus pu trouver de documentation concernant un tel algorithme sur internet.

Quelqu'un aurait déjà rencontré ce cas de figure, ou aurait une idée ?

[Nemerle]

Non, mais si tu as le temps d'exposer la problématique complête de façon rigoureuse, on pourrait t'aider...

[Laurent Gomila]

Ok je vais essayer de décrire plus précisément mon problème.

Mon but :

Le but est de trianguler un carreau de Bézier donné sous sa forme habituelle (paramètrique). Celui-ci peut contenir des trous, donnés sous forme de courbes B-Splines. Pour effectuer la triangulation à l'aide de l'algorithme de Delaunay, je prends un nuage de points quelconques aléatoirement sur le carreau, plus un échantillonnage des contours intérieurs.
Tout (les points et contours intérieurs) est donné dans l'espace paramètrique, c'est à dire dans le domaine 2D [0, 1] x [0, 1].

Précision supplémentaire, qui ne devrait pas jouer mais sait-on jamais : je ne dois pas me contenter de générer un résultat sous forme de triangles, mais je dois contruire un B-Rep (graphe faces - arêtes - sommets).

Mon problème :

L'algorithme de Delaunay traite habituellement un nuage de points, mais sans distinction entre parties "vides" et parties "pleines". En clair, je ne sais pas comment adapter l'algorithme pour qu'il ne me génère pas de triangle dans les trous.

Ce qui ne marche pas :

J'avais pensé éliminer ces triangles au fur et à mesure des itérations de l'algorithme (ie. ne pas créer ceux qui auraient une arête dans un trou) ; ça pose problème car rien qu'à la première itération aucun triangle ne serait créé, donc impossible de continuer l'algorithme.

J'avais aussi pensé les éliminer à la fin, une fois l'algorithme executé. Mais là aussi ça pose problème ; par exemple rien ne me certifie que l'algorithme ne va pas me créer des triangles intersectant les trous.

Illustration du résultat souhaité :



J'espère que c'est plus clair.

[2Eurocents]

Il y a très longtemps que je n'ai pas traité ce genre de sujet, mais voici quelques pistes ...

Plutôt que d'éliminer les points situés dans les trous, pourquoi ne pas les projeter sur la frontière ? Voire ... les projeter sur la frontière lorsqu'il s'agit d'un 3e point d'un triangle dont les 2 autres points sont dans une zone valide ... et le supprimer si les 2 autres points sont déjà à la frontière.

En outre, il faut que l'algorithme de raffinement de maillage perçoive la contrainte imposée par le bord du trou, afin d'augmenter le nombre d'arêtes dans les zones de forte courbure ... (ce qui n'est pas patent dans ton exemple, dont je suppose qu'il a été fait à la main, non ?)

Bon courage.

[Laurent Gomila]

Plutôt que d'éliminer les points situés dans les trous, pourquoi ne pas les projeter sur la frontière ? Voire ... les projeter sur la frontière lorsqu'il s'agit d'un 3e point d'un triangle dont les 2 autres points sont dans une zone valide ... et le supprimer si les 2 autres points sont déjà à la frontière

Je n'avais pas envisagé cette solution, ça a l'air intéressant. Par contre... Comment effectuer une projection sur une B-Spline ? Ou alors sur un polygone (la B-Spline après échantillonage -- ce sera peut-être plus simple) ?

En outre, il faut que l'algorithme de raffinement de maillage perçoive la contrainte imposée par le bord du trou, afin d'augmenter le nombre d'arêtes dans les zones de forte courbure

L'échantillonage des contours se fait avant de lancer l'algorithme, donc je peux facilement contrôler la précision de celui-ci en fonction de la courbure. L'algorithme lui ne traite qu'une liste de points.

ce qui n'est pas patent dans ton exemple, dont je suppose qu'il a été fait à la main, non ?

Oui, totalement à l'arrache

[Laurent Gomila]

Je viens de m'apercevoir d'un problème avec cette solution : cela ne marchera pas dans le cas de plusieurs contours intérieurs imbriqués. Je ne l'avais pas précisé, mais le cas peut se présenter (ie. on peut avoir des bouts de carreau isolés).

[plegat]

Salut,

Tu peux aussi, lors de la définition de ton nuage de points "aléatoires", rajouter des points qui seront localisés sur le bord de ton trou (en gros, tu mailles ton trou avec des segments). Tu gardes de côté la définition des segments, ça servira ultérieurement.

Tu fais ta triangulation de delaunay comme d'hab.

L'étape d'après consiste à réorganiser les triangles qui seront à cheval avec la frontière de ton trou (du style inversion de diagonale: triangles ABC et BCD qui se transforment en ABD et ADC)

Une fois que tout est organisé comme il faut, il suffit de supprimer les triangles à l'intérieur de ton trou, en faisant un parcours des triangles bord à bord. Les triangles sur les côtés du carreau étant à l'intérieur, dès que tu passes un bord qui est sur le bord de ton trou (c'est à dire qui fait partie de la liste des segments constituant la frontière du trou), tu sais que tu viens de passer à l'intérieur du trou. Donc tu supprimes le triangle et ainsi de suite...

J'avais trouvé une doc sur le site de l'INRIA pour ce problème en 3D à une époque... essaye de voir si tu n'y trouverais pas ton bonheur! http://www.inria.fr/publications/centredoc.fr.html

[Laurent Gomila]

L'étape d'après consiste à réorganiser les triangles qui seront à cheval avec la frontière de ton trou (du style inversion de diagonale: triangles ABC et BCD qui se transforment en ABD et ADC)

Justement je ne sais pas si cette étape est triviale. A priori les cas de figure peuvent être plus complexes qu'une simple inversion de diagonale (surtout lorsqu'on a des contours imbriqués et très proches).

J'ai rapidement jeté un oeil du côté de l'INRIA, les liens intéressants que j'ai trouvé pour le moment étaient tous morts ; je vais continuer à regarder.

[plegat]

[
Justement je ne sais pas si cette étape est triviale. A priori les cas de figure peuvent être plus complexes qu'une simple inversion de diagonale (surtout lorsqu'on a des contours imbriqués et très proches).

Triviale, non... d'ailleurs j'en suis resté à ce niveau pour mon mailleur 3D! (manque de temps, changement de langage et un autre projet en cours...)

La méthode, en gros, est la suivante.
Pour chaque segment qui borde le trou, il faut rechercher tous les triangles qui ont un côté qui intersecte (intersectionne?) le segment en question.
Au mieux, il n'y en a que deux, auquel cas on est sur le cas simple d'inversion de diagonale.
Sinon, ce n'est guère plus compliqué... on prend tous les triangles, on les ordonne comme il faut (à la suite les uns des autres suivant le parcours du segment). Tu prends les deux derniers, tu fais une inversion de diagonale sur ces deux-là. Résultat, tu te retrouves avec un des triangles qui ne coupe plus le segment! (pour la justification, voir avec des matheux... mais ça marche!). Tu enlèves donc ce triangle qui n'est plus à prendre en compte, et tu prends celui qui reste, auquel tu rajoutes le triangle suivant, et tu continues jusqu'à ce que tu aies parcouru tous les triangles concernés.

Attention, cette méthode ne marche correctement que si l'ensemble des triangles constitue un polygone "étoilé" (=on peut joindre les sommets deux à deux par une droite qui ne passe pas à l'extérieur du polygone) (si je me souviens bien, c'est ainsi que ça s'appelle cette bête )

J'essaye de retrouver la référence de la doc de l'Inria... elle ne doit pas être bien loin...

[edit]
Eventuellement, demande à l'Inria de t'envoyer une copie du document RR 835, "Tetraedrisation automatique et respect de la frontière", Paul-Louis GEORGE, Frédéric HECHT, Eric SALTEL, Avril 1988 (il n'y a pas de version postscript ou pdf, c'est trop vieux!)
Il y a un exemple en 2D de la méthode que j'essaie d'expliquer.

Sinon ça marche aussi pour les polygones non-étoilés. Il faut juste vérifier, lorsque l'on travaille sur deux triangles, que les deux "diagonales" s'intersectent. Sinon, on utilise le triangle suivant et on garde le triangle adjacent parmi les deux triangles qui posent problème. On réutilise le triangle mis de côté ensuite, dès que la condition d'intersection des diagonales est vérifiée.

Je ne sais pas si c'est hyper clair tout ça... fais-toi un test sur papier, ça va venir de suite.

[Re-Edit]
Allez zou, finalement je l'ai trouvé!
ftp://ftp.inria.fr/INRIA/publication.../RR-0835.ps.gz
Page 8
J'ai une conversion en pdf si le postscript pose problème...