Pour les besoins du boulot et a des fins d'edification personnelle je dois ecrire des routine de tracage de forme (ligne / poly / courbes ...) avec anti aliasing. Si le tracage de forme en lui meme n'est pas un problème (souvenirs inside), l'anti alias me laisse plus perplexe. J'ai farfouillé le net dans tous les sens, mais je n'ai pas trouvé de fin algorithme pour ce genre de sport (supersampling mis de coté), excepté pour les lignes. Pour ces dernières j'utilise l'algorithme de Wu. Ca marche bien mais souffre de defaut au niveau de jointure entre certains lignes (nomémment entre ligne oblique et ligne horizontale, vu que dans le cas de l'oblique on aura une ligne de 2 pixels de large tandis que l'horizontale n'en fera qu'une).
 
QQun s'y connait un peu ? Une page ? Un nom d'algo ?

18 vues quand meme

ben chaipa, c'est vachement specifique quand meme  
 
a premiere vue, je vois trois solutions pas trop compliquees:
- solution bateau: tu prends chaque pixel et tu reevalue sa couleur en fonction de ses voisins, mais ton image risque de "baver" d'un peu partout
- solution moins bateau: tu recherches les parties anguleuses de ton image (tu peux analyser l'image via une transformee de fourrier et chercher les pics de frequences par exemple) et tu mets du flou avec la solution bateau aux endroits anguleux.
- pseudo-solution: tu augmentes la resolution de l'image en interpolant et tu diminue la resolution a nouveau (ca revient un peu a faire la solution bateau remarque)
 
mais j'y connais pas grand chose en traitement d'image, des avis de specialistes seraient surement les bienvenus, ca m'interesse aussi moi !
 

T'as regardé les algos en incrémental comme Bresenham ?
L'erreur peut servir à faire un anti-alias.
J'avais fait des droites, des cercles et des ellipses à une époque, avec des algos du meme style, mais pour les courbes quelconques, je sais pas trop... elles sont définies comment, tes courbes ?
 
Pour ton problème de jointure de lignes, c'est normal : ta ligne oblique arrive entre 2 pixels, et ta ligne horizontale part sur 1 pixel, ça colle pas.
Je vois 3 possibilités :
- tu décale ta ligne horizontale verticalement d'une fraction de pixel, pour qu'elle se retrouve au meme niveau que la ligne oblique. (pas beau)
- tu oblige ta ligne oblique à se terminer sur 1 seul pixel en ajustant légèrement sa pente. (beau !)
- tu rabote l'angle en faisant un arrondi. (bon courage!)

je reponds facon tir groupé
 
 

 
bah c du blur, ca, pas de l'AA
 
 

 
Non seulement mes maths me laissent en retrait pour ce genre de truc, mais en plus je crains que ca ne soit bpc trop gourmand pour la cible (200Mhz)
 
 

 
Tout a fait, c'est d'ailleurs l'idée de l'algo de Wu (cf http://freespace.virgin.net/hugo.elias) Le pb c'est que ca marche bien pour les lignes, pas pour les contours de polygones remplis (+ les pb de taille de ligne evoqués plus haut)
 
 

 
Courbe de bezier, donc a priori une brochette de points de controles
 
 

 
tout le probleme c'est que ces deux lignes me seront peut etre fournie sans indication de liens entre elle (je ne sais pas que la ligne 1 va rejoindre la ligne 34). J'ai regarder Paint shop pro 5 et meme pour les lignes droites / verticales il fait une sorte d'AA (il epaissit la ligne, en fait)
Me demande si il fait pas du supersample....
 
 
enfin bref, merci de vos reponses !

 
euh...tu sais quand tu sauvegarde une image au format JPEG, tu fais de la transformee de fourier discrete, a priori, un pentium 200 fait ca sans probleme, a moins que t'ai une image en 10000 par 10000 auquel effectivement c'est limite. M'enfin c'est clair que c'est pas la solution a retenir... c'est vraiment si tu es desespere et que ca fait deux mois que tu planches... c'est la solution bien bourrin quoi

 
 
Indépendamment de ce problème, tu peux quand meme te débrouiller pour que toutes tes formes (lignes et courbes) débutent et se terminent pile sur un pixel. D'ailleurs, c'est peut-etre deja comme ça dans ton cahier des charges.
A moins que les coordonnées de tes formes soient en float... ?

le blur est une methode d'anti aliasing comme une autre.
 
LeGreg

C'est d'ailleurs comme ca que tu fais le edge antialiasing
(je verrai bien ça dans ton cas)
tu mémorises les lignes que tu traces et tu passe un filtre flou centré sur tes lignes et tes bords de polygones.
 
LeGreg

bon me revoila
 
Pour ceux que ca interesse, pour le tracage courbes de bezier, y'a un algo bien bourrin qui existe, cf les documents d'un certains A.E Fabris qui a l'air d'etre l'expert en bezier, au vu du nombre de documents qu'il a ecrit dessus (recherche sur "High quality rendering of two dimensional continous curves" par ex Notez que l'algo presenté peut etre étendu au lignes (logique) et ptet meme aussi au poly, fo voir). Par contre je vois pas trop comment utiliser cet algo pour faire autre chose que des lignes remplies uniformément, c bien dommage. (pointille out, mais j'imagine que c ce que l'auteur voulait dire avec son "continous" ). Evidemment pour ce genre de sport on peut subdiviser la courbe de bezier en troncon decrivant nos pointillés...
 
Sinon, legreg (avec 3 ans de retard) je ne pense pas que memoriser les edges + faire un flou par dessus soit une bonne idee (imagine un petit poly recouvert par un gros, tu va faire du flou en plein milieu du gros, ca peut etre un peu laid...)
 
voila je continue a bricoler

A mon avis, tu obtiendras plus un effet de flou qu'autre chose !

La transformée de Fourier, c'est pas si gourmand que ça hein !
Un 200 Mhz devrait suffire je pense.

Bon, comme d'hab, multigrilled de partout !
Je pars
 

 
han, et moi qui esperais trop une reponse passionnante et precise quand g vu ton nom

Je serais enclin à te proposer la solution n°2 de souk : la transformée de Fourier pour rechercher les endroits anguleux, et un flou sur ces endroits. La Transformée de Fourier est au traitement de signal ce que le produit scalaire est à la programmation 3D : un véritable marteau pilon !
Si ce qui t'effraie est la transformée de Fourier, c'est un faux problème : tu as des librairies qui s'en occupent très bien. A ce titre, je te conseille la librairie FFTW qui dispose de perfs hallucinantes, est portable et possède un truc génial : elle s'adapte automatiquement à des tailles non puissances de 2 ! Quant à la puissance nécessaire, ou est le problème ? Tu ne fais la transformée qu'une fois, donc rien ne t'empeche de temporiser en attendant. Mais tu verras, la FFTW est proprement hallucinante en terme de perfs ! Je l'ai utilisée une fois sur une image pour simuler un trait au fusain, et j'ai pleuré devant sa rapidité !
 
Une fois les bords localisés avec la Transformée, tu appliques une bonne vieille moyenne des pixels des familles sur les bords, et roulez jeunesse !
 
A mon avis, c'est la solution possédant le meilleur rapport temps/perfs.

Le coup de la FFT me semble un peu limite
 
Pour quoi ne pas reprendre un principe de l'anti-aliasing en 3D, en gros basé sur les pourcentages de surfaces occupées ?

Pour de la 2D, ça me semble suffisant

 
C'est quand même un peu limite de résoudre un problème de géométrie (des pourcentages de surfaces rectangulaires à répartir dans des carrés) par du traitement du signal.  
 
Edit : Disons que c'est mon point de vue "philosophique", mais si ça marche....

 
et a quoi il sert mon buffer de profondeur ?
pour des prunes ou quoi ?
 
LeGreg

 
ben je vois pas ou t'en a fais mention, et si je pourrais eviter d'accumuler les buffers de ci de la je ne serais pas specialement malheureux

 
edge antialiasing => quelques cartes 3d le faisaient
donc le buffer de profondeur vient gratos.
 
LeGreg

 
Ah mon dieu, si j'avais une carte 3d a dispo, j'utiliserais le FSAA, les fonctions de ladite carte et au diable tout ca

 
des cartes 3d ? j'en vends ..
..enfin bientot..
 
LeGreg

 
tu te met a la vente de carte 3d a la criée  ?

 
eheh..
 
Il parait que le marche du middleware n'etait pas si porteur
que ca alors une reorientation de carriere s'impose..
 
LeGreg

je me permet de remonter ce topic pour signaler a ceux que ca interesse qu'il y a un fort interessant article a ce sujet dans Graphics Gem I page 76 (sur l'AA de poly) et les resultats obtenus sont tout a fait satisfaisant, voir meme plus. (Si y'en a que ca interesse et qui ont pas le bouquin je veux bien developper)

 
 
EDIT: oué ca m'intéresse

ok
je ferais mon petit cours ce soir