Discussion :

[mister3957]

Bonjour à tous,

J'ai une série de zones en 2D à afficher (cela peut-être des polygones, ou des zones un peu plus complexes, comme une espèce de lune ou un tracé linéaire avec des courbes et épaisseurs différentes selon les endroits).

Tout ce que j'ai au départ, c'est une série de points traçant le contour, dans le même ordre que ce que l'on donne à un LineStrip.

Pour être plus concrêt, je suis en train de faire une cartographie, les zones peuvent être des bois, des rivières, des zones commerciales / industrielles etc.

Le soucis, c'est que je dois remplir cette zone, donc avec des triangles et non des lignes, enfin je pense, et je ne sais pas comment m'y prendre pour que cela soit performant. J'imagine qu'il y a des formules mathématiques pour ordonner les vertex afin d'ensuite faire du TriangleList ou TriangleStrip ?

Je travail en 2D, avec DirectX9 et OpenGL sous C++, peut-être que ces API donnent des outils pour faire ça ?

En fait c'est comme dans Paint, où on trace une forme indéterminée, fermée, puis on sélectionne le pot de peinture pour cliquer dans la zone afin de la colorer. Ca me paraît courrant comme problématique.

Si vous avez des tutoriels, des noms d'algorithme ou des librairies pour faire ça, ça m'aiderai pas mal.

Merci beaucoup par avance,

A bientôt

[comtois]

Pour remplir une forme quelconque j'utilise cet algo

[mister3957]

Merci pour ta réponse.

Si j'ai bien compris, il crée une structure de données de la ligne brisée permettant ensuite de savoir ensuite si tel coordonnée est dans le polygone ou pas, et ensuite, il colorie pixel par pixel. Est-ce bien ça ?

Mais je pense que ça ne conviendra pas, ça ne sera pas performant à l'affichage. Pour agir sur une image ça peut le faire, mais là c'est pour envoyer à la carte graphique... si je lui envoie des millions de points qu'elle devra afficher des dizaines de fois par secondes...

Je dois trouver un algo de triangularisation, ça doit bien exister.

Merci

[comtois]

Dans mon message précédent je te proposais de regarder aussi du côté de la triangulation de Delaunay mais comme je ne maitrise pas le sujet, je n'étais pas convaincu que ça puisse répondre à ton besoin du coup je l'ai supprimé de mon message, mais tu peux toujours y jeter un oeil.

y'a aussi la triangulation d'un polygone c'est sûrement ce que tu recherches ?

De mémoire il y a un tut sur DVP qui traite du sujet.

[mister3957]

Oui j'ai regardé, mais apparemment c'est pour triangulariser un ensemble de points et non un polygone.

Dans le tutoriel, c'est pour générer un terrain. Il génère les points, et ensuite utilise l'algo de Delaunay pour trianguler.

Je pense que ça ne convient pas car moi j'ai juste un polygone et son contour, sans points à l'intérieur.

Sinon j'ai trouvé ceci : http://mustapha.bismi.free.fr/dess/etude.html qui compare deux algo.

Le premier, la méthode des oreilles, semble pas super performante. Si j'avais juste des zones industrielles / commerciales, ça conviendrai, mais pour un cours d'eau par exemple, ça sera pas assez performant.

Le second, la méthode de seidel semble plus approprié, mais il va falloir que je gère des cas particuliers je pense.

[plegat]

Oui j'ai regardé, mais apparemment c'est pour triangulariser un ensemble de points et non un polygone.

Ca revient au même... un polygone peut se voir comme une suite de segments, ou comme une suite de points.

Dans le tutoriel, c'est pour générer un terrain. Il génère les points, et ensuite utilise l'algo de Delaunay pour trianguler.

Je pense que ça ne convient pas car moi j'ai juste un polygone et son contour, sans points à l'intérieur.

L'algorithme de delaunay fonctionne très bien même sans points intérieurs. D'ailleurs il ne fait pas la distinction entre points intérieurs et extérieurs, il triangule en injectant les points un par un. Le résultat ne respecte que rarement le contour du polygone, c'est pour quoi il est nécessaire de faire une passe ensuite pour recréer le contour (en recombinant les triangle, en faisant de la découpe, etc etc).

A mon avis, quelque soit l'algo que tu vas utiliser, tu n'auras pas ton résultat brut de décoffrage, il y aura toujours un peu de pre/post-traitement pour avoir ce que tu veux.

[mister3957]

Je crois que j'ai trouvé mon bonheur ici :
http://www.cgal.org/Manual/last/doc_...pter_main.html

Je testerai ça cette semaine sûrement.