Algoritmul lui Bresenham

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 30 mai 2019; verificările necesită 13 modificări .

Algoritmul lui Bresenham este un algoritm care determină ce puncte dintr-un raster bidimensional trebuie să fie umbrite pentru a obține o aproximare apropiată a unei linii drepte între două puncte date . Acesta este unul dintre cei mai vechi algoritmi din grafica computerizată - a fost dezvoltat de Jack Elton Bresenham la IBM în 1962 . Algoritmul este utilizat pe scară largă, în special, pentru trasarea liniilor pe ecranul unui computer. Există o generalizare a algoritmului lui Bresenham pentru construirea curbelor de ordinul 2.

Algoritm

Segmentul este desenat între două puncte - și , unde aceste perechi indică o coloană și, respectiv, un rând, ale căror numere cresc la dreapta și în jos. În primul rând, vom presupune că linia noastră merge spre dreapta și în jos, iar distanța orizontală o depășește pe cea verticală , adică panta liniei față de orizontală este mai mică de 45 °. Scopul nostru este ca fiecare coloană x între și să determinăm care rând y este cel mai aproape de linie și să desenăm un punct . $(x_0, y_0)$ $(x_{1},y_{1})$ $x_{1}-x_{0}$ $y_{1}-y_{0}$ $x_{0}$ $x_{1}$ $(X y)$

Formula generală pentru o dreaptă între două puncte este:

y-y_{0}={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0}).

Deoarece cunoaștem coloana , rândul se obține prin rotunjirea următoarei valori la un număr întreg: $X$ $y$

y={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}}(x-x_{0})+y_{0}.

Cu toate acestea, nu este necesar să se calculeze valoarea exactă a acestei expresii. Este suficient să rețineți că scade de la și pentru fiecare pas adăugăm la unul și adăugăm la valoarea pantei (în cazul nostru, valoarea pantei va fi un număr negativ): $y$ $y_0$ $X$ $y$

s={\frac {y_{1}-y_{0}}{x_{1}-x_{0}}},

care poate fi calculat în avans. Mai mult, la fiecare pas facem unul din două lucruri: fie păstrăm același y , fie îl micșorăm cu 1.

Pe care dintre cele două să alegeți se poate decide ținând evidența valorii de eroare , ceea ce înseamnă distanța verticală dintre valoarea curentă y și valoarea exactă y pentru curentul x . Ori de câte ori creștem x , creștem valoarea erorii cu valoarea pantei s dată mai sus. Dacă eroarea este mai mare de 1,0, linia se apropie de următorul y , așa că creștem y cu 1,0 în timp ce scade valoarea erorii cu 1,0. În implementarea algoritmului de mai jos, plot(x,y)desenează un punct și absreturnează valoarea absolută a numărului:

function line( int x0, int x1, int y0, int y1) int deltax := abs(x1 - x0) int deltay := abs(y1 - y0) real error := 0 real deltaerr := (deltay + 1) / (deltax + 1) int y := y0 int diry := y1 - y0 dacă diry > 0 murdar := 1 dacă murdar < 0 murdar := -1 pentru x de la x0 la x1 plot(x,y) eroare := eroare + deltaerr dacă eroare >= 1.0 y := y + diry eroare := eroare - 1.0

Problema cu această abordare este că, cu valori reale, cum ar fi errorși deltaerr, computerele sunt relativ lente. În plus, în calculele cu virgulă mobilă, din cauza limitărilor asociate cu reprezentarea numerelor reale, este imposibil să se obțină valori exacte la împărțire. Acest lucru duce la faptul că în procesul de calcul există o acumulare de erori și poate duce la rezultate nedorite. Din aceste motive, este mai bine să lucrați numai cu numere întregi. Acest lucru se poate face prin înmulțirea tuturor valorilor reale utilizate cu ( deltax + 1). Obținem următorul cod:

function line( int x0, int x1, int y0, int y1) int deltax := abs(x1 - x0) int deltay := abs(y1 - y0) int eroare := 0 int deltaerr := (deltay + 1) int y := y0 int diry := y1 - y0 dacă diry > 0 murdar := 1 dacă murdar < 0 murdar := -1 pentru x de la x0 la x1 plot(x,y) eroare := eroare + deltaerr dacă eroare >= (deltax + 1) y := y + diry eroare := eroare - (deltax + 1)

Necesitatea de a adăuga unul la deltax și deltay se datorează faptului că funcția trebuie să tragă o linie de la punctul (x0, y0) până la punctul (x1, y1) inclusiv! Acum putem desena rapid linii dreapta-jos cu o pantă mai mică de 1. Rămâne să extindem algoritmul la desen în toate direcțiile. Acest lucru se realizează prin reflexii în oglindă, adică prin schimbarea semnului (un pas de 1 este înlocuit cu −1), prin schimbul de variabile x și y și prin schimbul coordonatele începutului segmentului cu coordonatele sfârșitului .

Desenând cercuri

Există și algoritmul lui Bresenham pentru desenarea cercurilor. Metoda de construcție este similară cu trasarea unei linii. În acest algoritm, se construiește un arc de cerc pentru primul cadran, iar coordonatele punctelor cercului pentru cadranele rămase sunt obținute simetric. La fiecare pas al algoritmului, se iau în considerare trei pixeli, iar cel mai potrivit este selectat dintre aceștia comparând distanțele de la centru la pixelul selectat cu raza cercului.

// R - raza, X1, Y1 - coordonatele centrului int x := 0 int y := R int delta := 1 - 2 * R int eroare := 0 while (y >= x) pixeli desen (X1 + x, Y1 + y) pixeli desen (X1 + x, Y1 - y) pixeli desenați (X1 - x, Y1 + y) pixeli trasă (X1 - x, Y1 - y) pixeli desen (X1 + y, Y1 + x) pixeli desen (X1 + y, Y1 - x) pixeli desen (X1 - y, Y1 + x) pixeli trasă (X1 - y, Y1 - x) eroare:= 2 * (delta + y) - 1 dacă ((delta < 0) && (eroare <= 0)) delta += 2 * ++x + 1 continua dacă ((delta > 0) && (eroare > 0)) delta -= 2 * --y + 1 continua delta += 2 * (++x - --y)

Literatură

Rogers D. Fundamentele algoritmice ale graficii computerizate . - M . : Mir, 1989. - S. 54 -63. — ISBN 5-03-000476-9 .
Schildt G. „C” pentru programatori profesioniști. - M. , 1989.

Algoritmul lui Bresenham

Algoritm

Desenând cercuri

Literatură

Vezi și