Discussion :

[Le Furet]

Je cherche un algorithme simple et rapide pour tracer des disques pleins (pas juste la circonférence, mais aussi l'intérieur) dans un bitmap tout simple.

Pour le cercle, j'ai trouvé un algo du type Bresenham, mais pour le disque, j'ai pas vu.

[ceugniet]

Je cherche un algorithme simple et rapide pour tracer des disques pleins (pas juste la circonférence, mais aussi l'intérieur) dans un bitmap tout simple.

Pour le cercle, j'ai trouvé un algo du type Bresenham, mais pour le disque, j'ai pas vu.

Pour une circonférence, avec une épaisseur, c'est vrai que ce n'est pas évident. Mais pour un disque plein d'équation (x-xc)^2+(y-yc)^2<=r^2, je ne vois aucune difficulté :

Pour y de yc-r à yc+r, calculer h=racine_carree(r^2-(y-yc)^2) et tracer un trait de xc-h à xc+h.

Mais peut-être n'ai-je pas bien compris la question...

[j.p.mignot]

en borland delphi ou C++ il existe des fonctions toutes faites du type

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
// Canvas de Image1 type TImage par exemple
Canvas.Brush.Color := clRed;   // ou autre
Canvas.Brush.Style := bsSolid;   //bsSolid bsCross  bsClear bsDiagCross
                                       //  bsBDiagonal		bsHorizontal  bsFDiagonal		bsVertical
Canvas.Ellipse(X1,Y1,X2,Y2); // trace une ellipse dans le rectangle x1,y1 : x2,y2
//  donc un cercle si dx = dy. avec Style = bsSolid, on à un disque.

Un algorithme me parait assez simple mais si on veut eviter de 'rater' certains pixels, on doit scanner une surface incluant le cercle ( comme 1 carré de centre xc,yc et coté 2R) pixel par pixel, tester la distance au centre.
Un tracé de droites comme proposé peut aussi se faire mais il faut estimer correctement le pas en angle ( si droites issues du centre ) ou pas en x (resp. y ) si verticales ( resp. horiz) pour atteindre tous les pixels.

[ceugniet]

en borland delphi ou C++ il existe des fonctions toutes faites du type

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
// Canvas de Image1 type TImage par exemple
Canvas.Brush.Color := clRed;   // ou autre
Canvas.Brush.Style := bsSolid;   //bsSolid bsCross  bsClear bsDiagCross
                                       //  bsBDiagonal		bsHorizontal  bsFDiagonal		bsVertical
Canvas.Ellipse(X1,Y1,X2,Y2); // trace une ellipse dans le rectangle x1,y1 : x2,y2
//  donc un cercle si dx = dy. avec Style = bsSolid, on à un disque.

Oui ! Mais si l'on est pinailleur, ce qui est mon cas, et si les cercles sont petits, on peut être gêné du fait que les cercles ne sont pas parfaits (pas symétriques)...On n'est jamais si bien servi que par soi-même...

[j.p.mignot]

en effet pour de petits cercles il y a des déformations qui sont avant tout du à la quatification, la taille des pixels devenant grande devant la taille du cercle. Pour cela à part augmenter la résolution de la carte graphique il n'y a pas grand chose à faire. Je n'ai pas regardé en détails si la routine "ellipse" étatit parfaite du point de vue 'touver le meilleur arrondi' mais je serais surpris que borland ai livré un outil trop grossier. Par contre je sais d'expérience qu'il était parfois nécessaire d'applique un "AspectRatio" afin de ne pas dessiner une ellipse en lieu et pace d'un cercle ( c'était le cas entre les modes EGA et VGA sous DOS ), la densité de pixels n'étant pas la même sur l'axe x et y. Dans ce cas le tracé 'personnel' de cecles doit tenir compte de ce ratio alors qu'en général les outils 'intégrés' en tiennent comptent en interne ( voir leurs docs respectives).

[ceugniet]

en effet pour de petits cercles il y a des déformations qui sont avant tout du à la quatification, la taille des pixels devenant grande devant la taille du cercle. Pour cela à part augmenter la résolution de la carte graphique il n'y a pas grand chose à faire. Je n'ai pas regardé en détails si la routine "ellipse" étatit parfaite du point de vue 'touver le meilleur arrondi' mais je serais surpris que borland ai livré un outil trop grossier.

Ce n'est pas ce que j'ai voulu dire. D'une part, je ne connais pas Delphi, mais sur C++, il faut deviner (car la doc en ligne ne le précise pas) que Ellipse(X1,Y1,X2,Y2) donnera une elllipse inscrite dans le rectangle (X1,Y1,X2,Y2) - pas dur - c'est à dire inscrite dans le rectangle remplissant les pixels X1 à X2-1 horizontalement et Y1 à Y2-1 verticalement, - moins évident mais pas trop dur non plus -. Mais surtout, je ne parle pas de la beauté de l'arrondi, je voudrais bien que mon cercle ait deux axes de symétrie et ce n'est pas le cas - au moins pour certains petits cercles.

[j.p.mignot]

Je crois que l'on ne s'est pas tout à fait compris!. Qand je parle du "meilleur arrondi", je ne parle pas de la beauté de la chose mais de l'arrondi entre real et integer. C'est à dire que le cercle passe au travers de pixels. un pixel qui est à la fois In et Out doit-il être "allumé" ou "eteint"? C'est un problème tout à fait analogue à celui de la déformation d'un signal avec trop peu de bits pour le digitaliser. Un cercle de centre x,y qui n'est pas au centre d'un pixel et de rayon R de quelques pixels mais non entier en terme de nombre de pixels ( par exemples 3.6 pixels) risque de se dessiner sans repecter les symétries. Maintenant, en tout cas chez borland ( C++ ou delphi ) , je n'ai jamais vérifié comment ils tracaient les pixels à cheval In/Out. Les rare fois ou j'ai eu à tracer avec 1 peu de précision des cercles on été sur des bitmap et des prints. Dans le 1er cas j'ai mis suffisement de pixels dans le bitmaop pour réduire les erreurs de quantifications, dans le second j'ai écris directement dans le canvas du printer ou la aussi la résolution est suffisante pour assurer la qualité requise ( du moins pour les besoins du moment)

[ceugniet]

Je crois que l'on ne s'est pas tout à fait compris!. Qand je parle du "meilleur arrondi", je ne parle pas de la beauté de la chose mais de l'arrondi entre real et integer.

Voui, bien sûr ! J'étais à côté de la plaque.

Reprenons alors,...

Un cercle de centre x,y qui n'est pas au centre d'un pixel et de rayon R de quelques pixels mais non entier en terme de nombre de pixels ( par exemples 3.6 pixels) risque de se dessiner sans repecter les symétries.

Cela va de soi : si les coordonnées du centre ne sont ni des nombres entiers ni des nombre entiers de fois des demis, il n'y a pas lieu de chercher des symétries, puisqu'il n'y en a pas ! Mais C++ impose d'avoir des entiers en entrée (void __fastcall Ellipse(int X1, int Y1, int X2, int Y2)). Il s'ensuit que le résultat devrait nécessairement avoir deux symétries axiales, et ceci quelles que soient les parités de X2-X1 et Y2-Y1.

Je suis d'accord sur le fait que ce n'est pas d'une importance capitale, mais, comme je l'ai dit, sur de petits cercles, ça se voit. Et puis, on ne refait pas ! Quand on est pinailleur...
Quand je veux faire un dessin parfait, je le fais "à la main", mais j'apprécie aussi souvent de pouvoir utiliser la fonction "ellipse"...

[Le Furet]

Excusez-moi, mais à part la première réponse, les autres ne répondent pas à la question posée (en l'occurence, le langage utilisé est le C, et je ne veux pas utiliser de bibliothèque externe).

Quant à la première réponse, bien sûr c'est comme ça que je fais pour l'instant, mais il y a calcul d'une racine carrée, d'où forcément perte de temps. Je sais que pour tracer un cercle, on peut le faire sans racine carrée (avec un algo de type Bresenham), je voulais juste savoir s'il y avait plus rapide.

En y réflechissant, l'adaptation de l'algo en question est immédiate. Il était tard hier

[Mac LAK]

J'ai fait un algo de ce type en ASM, à l'époque, sur une variante de Bresenham.

Principe : tracé d'un arc de cercle de 45° (de 0 à Pi/4), calcul des 8 points totaux par symétrie, et tracé de lignes horizontales entre deux points en face à face (=4 lignes horizontales à chaque itération). Le calcul de la "déviance" du tracé est faite sans calcul de norme euclidienne, en calculant la "différence" entre deux distances successives (pose les équations, ça se fait tout seul). Du coup, pas de calculs "lourds" pendant le tracé, tout bénèf ! :-)

Résultat 100% parfait à l'affichage (aucun trou), vitesse fulgurante (le tracé de ligne horizontal étant fait par une opération de type "memset", qui est souvent optimisée à mort).