Algorithmes génériques pour affichage de primitives 2D.

Version imprimable

01/01/2005, 21h52
Selenite

Algorithmes génériques pour affichage de primitives 2D.

Bonjour,

J'aurais besoins d'implémenter l'affichage de primitives graphiques (lignes, polygones, ellipses, courbe de bézier) et tout ça avec les possibilités suivantes: anti-aliasing on/off, contour on/off, largeur du trait, remplissage on/off.

D'où la quasi necessité de développer des algorithmes génériques pour chacune de ces primitives. Il est or de question de reprogrammer l'AA pour toutes les primitives par ex, idem pour la largeur du trait.

J'ai pas trouvé grand chose comme doc. Je fait donc appel à votre culture et à vos favoris pour me donner quelques mots clefs et liens;

Voilà ;-).
Merci d'avance.
02/01/2005, 03h49
Mac LAK

Pour le tracé de ligne, pas de tergiversations : l'algorithme de Bresenham est (de loin !!) le plus efficace de tous, surtout quand on sait qu'il est possible de directement tracer la droite antialiasée ! :twisted:
Ces URL pourront t'aider :
http://inferno.cs.univ-paris8.fr/~armsoft/CHAOS/triangulation/bresenham.html
http://www.mines.u-nancy.fr/~tombre/Java/Prog10/bresenham.pdf

Déjà, pour les polygones, pas besoin de chercher, il faut et il suffit d'y aller à grand coup de lignes "simples". Tu n'auras pas plus rapide, sauf peut-être pour les polygones réguliers, mais même dans ce cas, j'ai des doutes. Il n'y a vraiment que pour les rectangles qu'il est possible d'améliorer la vitesse de tracé.

A l'époque, j'avais implémenté une variante de Bresenham pour le tracé de cercles, en dessinant 1/8 du cercle et en dessinant le reste par symétries. La vitesse de tracé des cercles (Pascal/DOS/SVGA) était proprement fulgurante, et ça permettait même de dessiner des cercles pleins (disques) avec contour quasiment à la même vitesse que les cercles "vides" !
Une fois l'algo compris, de toutes façons, il est très simple de l'adapter aux cercles, mais un lien est encore plus simple :
http://raphaello.univ-fcomte.fr/IG/Algorithme/ExemplesGLUt/ExempleBresenhamCercle.htm
http://archivesic.ccsd.cnrs.fr/sic_00001174.en.html
http://www.cours.polymtl.ca/inf2700/transparents/Bresenham.pdf (ce PDF regroupe les algos ligne/cercle)

Les ellipses, c'est un peu plus complexe. Je n'ai pas trouvé de méthode plus optimisée qu'un dessin sur 1/4 d'ellipse + 3 symétries, mais un algo incrémental comme Bresenham n'est pas franchement trivial à adapter aux ellipses (il y a 3 cas de position pour le pixel suivant au lieu de 2). Cependant, c'est possible.

Pour les courbes de Bézier, je ne les ai jamais utilisées autrement qu'en maths "pures". Regarde du côté de l'algo de De Casteljau également.
J'ai trouvé ces liens, à toi de voir si quelque chose te convient dedans.
http://www.mactech.com/articles/mactech/Vol.05/05.01/BezierCurve/
http://www.efg2.com/Lab/Graphics/Jean-YvesQueinecBezierCurves.htm
http://www.ece.eps.hw.ac.uk/~dml/cgonline/hyper00/curvesurf/morebez.html
http://freespace.virgin.net/hugo.elias/graphics/x_bezier.htm
http://en.wikipedia.org/wiki/De_Casteljau%27s_algorithm
http://www.tinaja.com/cubic01.asp

Pour le remplissage, si tu entends par là un "FloodFill", il existe de nombreux algos plus ou moins optimisés et parfois, limités à certains types de formes (ex : formes convexes). Les plus courants sont le FloodFill et le remplissage par scanlines.
Lien :
http://www.iro.umontreal.ca/~dift2730/cours/cours_5.pdf (très très complet, inclus l'AA)

Programmer l'AA revient le plus souvent à multiplier artificiellement la résolution par deux (1 pixel d'origine => 2x2 pixels "virtuels"), cette augmentation de résolution permettant alors, lors du retour à la résolution d'origine, d'effectuer l'AA. Pour les algos de type Bresenham, il est très facile d'implémenter ça directement au niveau du tracé. Le lien ci-dessus donne l'explication théorique de cette méthode, ainsi que son application à l'algo de Bresenham. On peut (en partie) effectuer un AA "générique" en surchargeant la méthode d'affichage d'un pixel, mais ça fait un peu sale à l'écran en général. Il vaut mieux, là aussi, ajouter spécifiquement la fonction à chaque primitive.

Les algos de contour et de largeur de trait sont plus complexes, j'avoue ne jamais avoir touché à ces éléments "par moi-même". Je n'ai utilisé les contours que pour les formes simples (rectangles, ellipses, cercles), et les largeurs de traits pour les rectangles seulement.

Une chose est sûre : la largeur de trait est à répercuter sur toutes les primitives ! On ne trace pas une ligne horizontale de 3 pixels d'épaisseur de la même manière que le contour d'un cercle de 3 pixesl d'épaisseur lui aussi.

Je pense n'avoir rien oublié. J'espère que ça pourra t'aider.
02/01/2005, 19h19
Selenite

Merci beaucoup :D

Pour l'algo de Bresenham, je l'avais vu. C'est celui que j'ai actuellement implémenter pour les lignes. Mais pour les lignes de différentes largeurs, j'ai pas trouver grand chose. J'ai trouvé ça, mais c'est assez illisible, mal expliqué, etc. S'il le faut, je vais creuser, mais bon... on verra ;-). http://homepages.enterprise.net/murphy/thickline/

Pour le remplissage (j'entend par là, le coloriage de la figure tracée), je devrais m'en sortir. Pour les cercles/ellipses aussi.

L'AA découlant de l'algo de Bresenham ne m'a pas paru très performant au niveau de la qualité (à approfandir) et surtout, il n'est pas compatible avec les largeurs de traits.

Je pense que je vais me rabbatre sur la méthode naïve: on fait tout le dessin à haute résolution, et on reduit au dernier moment. Après faut voir les performances.

Encore merci. J'ai pas encore tout regardé, mais ça ne saurait tarder.
02/01/2005, 20h20
Mac LAK

Citation:

Envoyé par Selenite

Merci beaucoup :D

De rien.

Citation:

Envoyé par Selenite

Pour l'algo de Bresenham, je l'avais vu. C'est celui que j'ai actuellement implémenter pour les lignes. Mais pour les lignes de différentes largeurs, j'ai pas trouver grand chose. J'ai trouvé ça, mais c'est assez illisible, mal expliqué, etc. S'il le faut, je vais creuser, mais bon... on verra ;-). http://homepages.enterprise.net/murphy/thickline/

Je ne vois pas ce qui te bloque : d'accord, l'algo est chaud, mais il est correctement décrit, tu as tous les organigrammes et même un programme d'exemple avec ses sources Delphi !

Citation:

Envoyé par Selenite

Pour le remplissage (j'entend par là, le coloriage de la figure tracée), je devrais m'en sortir. Pour les cercles/ellipses aussi.

Parfait.

Citation:

Envoyé par Selenite

L'AA découlant de l'algo de Bresenham ne m'a pas paru très performant au niveau de la qualité (à approfandir) et surtout, il n'est pas compatible avec les largeurs de traits.

Pourtant, elle l'est, j'ai déjà eu l'occasion de vérifier ce point : ça donne un très bon rendu, tout dépend en fait du niveau de partitionnage des pixels. Utiliser du 2x2 n'est pas terrible (mais c'est rapide), mais du 3x3 donne d'excellents résultats (c'est plus lent, bien sûr).

Pour le problème de largeur de trait, je pense que tu fais une erreur monumentale : il ne faut pas mélanger les primitives ! Si tu traces toutes tes lignes, y compris celles d'un pixel de large avec un algo "générique", tu vas obtenir des performances minables.
La bonne méthode, à mon sens, et de faire un CaseOf dans la fonction de tracé de ligne, et d'appeler (en fonction du paramétrage) les primitives plus "basses" les plus optimisées.
Dans mon unité SVGA, par exemple, je différenciais les lignes horizontales des autres types de lignes, car elles pouvaient être dessinées par des méthodes bien plus rapides que Bresenham.
Dans ton cas, il faudra différencier les lignes d'un pixel de large ou pas, puis éventuellement au sein des sous-primitives distinguer le cas AA des autres, différencier les lignes horizontales, etc...

Citation:

Envoyé par Selenite

Je pense que je vais me rabbatre sur la méthode naïve: on fait tout le dessin à haute résolution, et on reduit au dernier moment. Après faut voir les performances.

Cette méthode d'AA est certes très performante sur le plan visuel. Par contre, sans accélération hardware, les performances de vitesse sont minables.

De plus, il y a un inconvénient que tu n'as pas pris en compte : avec ça, tu fais un AA sur l'image complète, ce qui n'est pas forcément souhaitable (ça produit un effet de flou).
Alors qu'implémenter l'AA pour chaque primitive te permet de choisir les éléments qui subiront un AA (ex : lignes, texte, cercles) et ceux qui ne doivent surtout pas le subir (floodfill, rectangles), donnant une image antialiasée mais restant "nette" à l'oeil.

Citation:

Envoyé par Selenite

Encore merci. J'ai pas encore tout regardé, mais ça ne saurait tarder.

J'avoue, je t'ai mis quelques heures de lecture si tu lis tous ces liens... :mrgreen:
Sérieusement, tous les liens que je t'ai mis ont leur intérêt, n'en oublie pas : dans le pire des cas, tu auras au moins la confirmation que la méthode que tu as prise est la bonne, ce n'est quand même pas négligeable.

Bonne chance !