Bonjour,  
 
j'aimerai trouver les coordonnées des pixels qui se trouvent sur une droite que je trace sur une image.
J'explique, j'ai une image qui a bien évidemment des pixels qui se trouvent aux coordonnées (x,y).  
Je connais le point d'arrivée et le point de départ de ma droite, j'aimerai connaitre tous les pixels (coordonnées) qui se trouvent sur ma droite (aux erreurs de précisions près bien sur).  
Comment puis-je faire ?  
 
Une méthode consiste à calculer l'équation de la droite, pour chaque point vérifier si ses coordonnées vérifient l'équation (ou à peu près). Mais bon, cette méthode est très peu pratique car faut tester tous les pixels.  
J'aimerai faire une méthode par incrémentation mais j'ai du mal à trouver la formule.
 
Avez vous une idée ? merci !

vec(A,M) = k vec(A,B)
Donc si je ne me trompe pas
x = k (xB - xA) + xA
y = k (yB - yA) + yA
avec k variant de -l'infini à + l'infini.
Garanti comme peut l'être une formule donnée après les agapes de Noël  

ok merci, je vérifierai ça demain, car la hop au dodo.  
 
Si quelqu'un à d'autres solutions je suis preneur !  
 
bonne fin de soirée !

http://fr.wikipedia.org/wiki/Algor [...] _Bresenham

J'utilisais un algo similaire (enfin comme tout le monde je crois, c'est le seul que j'avais trouvé) mais il me semble que le code était bien plus court.
Au lieu de faire tous les cas ils ne pourraient pas inverser ?

c'est l'algo le plus rapide connu pour l'affichage de segments. il est possible de ne coder qu'un seul octant, mais pour des raisons simples de perfs coder les 4 octants est bien meilleur (c'est rapide en fait: 3 copié/collé, 2 relectures, 4 tests).
Un algo dérivé consiste à traiter les pixels par lot (de pixels horizontaux/verticaux), mais celà n'apporte véritablement de gains de perfs que pour l'affichage direct en mémoire/buffer vidéo et optims en assembleur.

C'est pas d'inverser deux coordonnées ou de les remettre en négatif qui prendra tant de temps.
Enfin ça dépend surtout de l'optimisation nécessaire.

Mettre des 'if's à l'intérieur de la boucle au lieu d'à l'extérieur, ajoute un délai proportionnel au nombre de pixels du segment, au lieu du délai constant correspondant à une instruction 'if' par segment.
Si tu n'as qu'un petit nombre de segments, d'un point de vue algorithmique, tu peux zapper cette optim.

Bresenham c'est pas le plus rapide façe a une bête interpolation, et surtout pour paramétrer d'autres grandeurs, ça doit poser des problèmes.

la 'bête interpolation' est 3 à 10 fois plus lente à cause des calculs flotants vs entiers et de la multiplication vs addition.

tu connais le concept de virgule fixe ?

Oui, et alors? Tu m'expliques comment faire une interpolation sans multiplication?
 
En plus la virgule fixe n'arrange pas les choses: celà ajoute au moins un shift de bit (voire une division qui est encore plus lente qu'une multiplication) pour pouvoir multiplier deux virgules fixes ensembles. Enfin, la virgule fixe nécessite que tu connaisse par avance un ordre de grandeur pour la résolution de l'image sans quoi le résultat n'est soit qu'approché, ou soit exact mais la précision interne y est surestimée.
 
pseudo code avec interpolation:

 
pseudo code style bresenham:

 
La différence est dans le corps de la boucle pour:

• 1 multiplication + 1 addition
• 1 condition + 2 additions au pire (la division en octants permet en plus aux microprocesseurs de raccourcir le temps d'exécution de la condition car le 'then' est exécuté plus de fois (ici) et plus rapidement (en général) que le 'else')

Or la multiplication est environ 3 (calculs entiers), 5 (calculs fixes), voire 7 fois (flottants) plus lente qu'une addition (avec le même mode de calcul) sur la plupart des PCs (AMD est jusqu'à 2 fois plus rapide en flottant mais chauffe plus).
 
Bon, c ptet plus de l'algorithmique pratique que théorique... mais il n'y a pas à ma connaissance de processeur (ou peut être très spécifique?) qui multiplie plus vite qu'il n'additionne.

+1 avec Nargy, hors de bresenham point de salut.

la virgule fixe a des contraintes et des limites, mais qui cite brensenham (a juste titre), sans avoir expérimenté de la virgule fixe, bah bof.  
 
pseudo-code mélangé avec du C en virgule fixe:
 
pour l'itération en y:
 
sx = x0 << 16
dx = (x1-x0)<<16 / dy
pour chaque coordoonnée y:
       tracer( y, sx >> 16 )
       sx += dx
 
variante texturée/ombrée linéairement:
 
sx = x0 << 16
su = u0 << 16
sv = v0 << 16  
sm = m0 << 16
 
dx = (x1-x0)<<16 / dy
du = (u1-u0)<<16 / dy
dv = (v1-v0)<<16 / dy
dm = (m1-m0)<<16 / dy
pour chaque coordoonnée y:
       tracer( y, sx >> 16,  su>>16, sv>>16, sm>>16 )
       sx += dx
       su += du
       sv += dv
       sm += dm
       
 
quand on a un branchement par pixel, on évite de se palucher sur le reste hein.
 
avec brensenham, montre moi du pseudo code sur comment tu ferais évoluer d'autres gradients. (ça m'interresse, vu que j'ai jamais cherché à le faire en asm)
   

Je pige pas ta question... Pour faire de l'anticrénelage: la ligne se situe exactement là où reste==0. La valeur abs(reste)/dy est la transparence entre 0 = opaque et 1= transparent. C'est le même principe que celui décrit dans l'algo de bresenham pour transformer cette division en algo incrémental.
 
La version anglaise de cette page:
http://fr.wikipedia.org/wiki/Algor [...] _Bresenham
donne aussi l'algo de tracé de cercle (x²+y²=r²).
 
Le cartes graphiques affichent des textures 2D/3D par projection avec perspective avec un algo qu'on pourrait qualifier de double-bresenham: d'un côté la texture est balayée hyperboliquement (perspective) suivant un plan 3D, de l'autre les pixels de l'écran sont balayés horizontalement et verticalement pour afficher un polygone texturé de gauche à droite et de haut en bas.

justement, comment tu les détermines tes gradients à l'intérieur de boucle de bresenham ?
 
---
 
l'approche par virgule fixe, a été utilisée dans tous les renderers 3d logiciels de l'époque pré-gpu.
 
sinon pour le rendu gpu y'a pas de double balyage (dans le sens boucle), y'a une n gradients interpolés en virgule flottante le long des bords de triangles et à l'intérieur des scanlines (groupés par bloc de pixels carrés) (enfin là est ptet d'accord).
 
bref, c'est pas pour dire que bresenham c'est mal, loin du contraire, mais y'a d'autres approches valables, et à connaitre, dans le domaine de traçage de formes.  
 
en l'occurence le traçage de ligne (pour en revenir à nos moutons), je suis vraiment pas sûr que bresenham soit plus rapide que de la virugle fixe. après c'est suivant l'architecture (qui rends déjà la virgule fixe faisable ou pas).

Si on prend comme référence le temps pris par une opération + - SHIFT ROT, et que le 'if < 0' prends T unités de temps. Le 'else' (vu la division en quadrans) est exécuté 1 fois quand le 'then' est exécuté 2 fois, en moyenne. Un incrément (y++), borné par le temps pris par une addition, est donc exécuté durant 0.33 unités de temps par tour de boucle.
 
Bresenham reste plus rapide que la virgule fixe, dans le cas moyen, tant que: Temps_du_if < 2/3 Temps_d_une_addition. C'est généralement le cas pour le test "if x<0" sur la plupart des architectures (test d'un seul bit en fait). Sur les PC cette valeur avoisine les 0.5, me semble-t-il.

c'est pas le test le problème c'est si il y a un branchement vidant le pipeline derrière.

heu.. je dirais que le pipeline rentre très peu en compte, en tout cas dans le sens calculatoire et données, par contre c'est vrai que le 'else' vide le cache de code. Ça se traduit concrètement par une rapidité accrue du 'then' par rapport au 'else', comme sans pipeline d'ailleurs, et j'en tiens compte en prenant une valeur moyenne T.
 
En fait, en y repensant, il y a bien un cas particulier pour lequel la virgule fixe est plus rapide: dans le cas où on dispose d'un registre à décalage. Un registre à décalage permet d'effectuer un shift de bits sans passer par l'unité de calcul, rendant cette opération aussi courte que possible: idéalement 1 cycle.
 
J'étudie plus haut le cas seulement où les registres sont généraux, c'est le cas le plus courant pour les CPUs, mais ce n'est pas forcément le cas pour les périphériques, dont le matériel utilise souvent les registres à décalage pour éviter l'emploi d'unités de calculs supplémentaires.

oulà