Algorytm Bresenhama
Z Wikipedii
Więcej informacji co należy poprawić, być może znajdziesz na odpowiedniej stronie. W pracy nad artykułem należy korzystać z zaleceń edycyjnych. Po naprawieniu wszystkich błędów można usunąć tę wiadomość.
Możesz także przejrzeć pełną listę stron wymagających dopracowania.
Algorytm Bresenhama służy do rasteryzacji krzywych 2D, czyli do jak najlepszego przybliżenia matematycznych krzywych na siatce pikseli.
[edytuj] Algorytm konwencji odcinka
1.1 Założenia
Kąt pomiędzy styczną a osią OX, nie może przekraczać 45 stopni,
a)Jeśli krzywa może zostać opisana funkcją y=f(x) to musi zostać spełniony warunek 
Krzywa musi być nierosnąca albo niemalejąca
1.2 Algorytm i jego działanie
Załóżmy że krzywa w przedziale [xi, xk] spełnia w/w założenia
Pierwszy piksel stawiamy w punkcie P(xi, yi). Drugi natomiast ogranicza się jedynie do dwóch możliwości: Si+1 = (xi+1, yi) lub Ti+1(xi+1, yi+1). Przyrost w kierunku osi OX (osi wiodącej) jest stały - jeden piksel. Korzystając z równania kierunkowego prostej y = dy dx (x−x0)+y0 policzymy w jakiej odległości znajdują się powyższe piksele od punktu przecięcia łączącego je odcinka z prostą przebiegającą w rzeczywistym układzie współrzędnych
di = dx(s − t) = 2dy(xi − xo) − 2dx(yi − yo) + 2dy − dx
Ponieważ dx > 0 di określa, która z odległości s i t jest większa. Jeżeli di > 0, to s > t za punkt Pi+1 przyjmujemy piksel Ti+1, jeżeli di < 0, wybieramy piksel Si+1. Wartość di = 0 oznacza, że oba piksele leżą w tej samej odległości i arbitralnie przyjmujemy, ze następny piksel to Ti+1. Policzmy jeszcze wartość di+1
di+1 = 2dy(xi+1 − x0) − 2dx(yi+1 − y0) + 2dy − dx
oraz różnice di+1 − di
di+1 − di = 2dy(xi+1 − xi) − 2dx(yi+1 − yi)
czyli
di+1 = di + 2dy − 2dx(yi+1 − yi)
gdyż xi+1 = xi + 1. Jeżeli di 0, to yi+1 = yi + 1 (wybieramy piksel Ti+1), co pozwala na uproszczenie obliczeń di+1
di+1 = di + 2(dy − dx)
Analogicznie, gdy di < 0 mamy yi+1 = yi (wybieramy piksel Si+1), i wzór na di+1 ma postać
di+1 = di + 2dy
Z uwagi na rekurencyjną postać wzoru na obliczanie współczynnika di, nazywanego także zmienna decyzyjna, należy jeszcze policzyć wartość początkową d0. Podstawiając xi = x0 oraz yi = y0 do równania
di = 2dy(xi − x0) − 2dx(yi − y0) + 2dy − dx
otrzymujemy wzór na d0
d0 = 2dy − dx
Implementacja algorytmu Bresenhama musi oczywiście uwzględniać inne możliwe położenia odcinka względem osi OX. Jednak w każdej sytuacji można zastosować opisany wyżej schemat, w razie potrzeby traktując oś OY jako oś wiodącą
Rysowanie odcinka algorytmem Bresenhama
// x1 , y1 − współrzędne początku odcinka
// x2 , y2 − współrzędne konca odcinka
void BresenhamLine( const int x1 , const int y1 , const int x2 , const int y2 )
{
// zmienne pomocnicze
int d , dx , dy , ai , bi , xi , yi ;
int x = x1 , y = y1 ;
// ustalenie kierunku rysowania
if ( x1 < x2 )
{
xi = 1 ;
dx = x2 - x1 ;
}
else
{
xi = -1;
dx = x1 - x2 ;
}
// ustalenie kierunku rysowania
if ( y1 < y2 )
{
yi = 1 ;
dy = y2 - y1 ;
}
else
{
yi = -1;
dy = y1 - y2 ;
}
// pierwszy piksel
glVertex2i ( x , y ) ;
// oś wiodąca OX
if ( dx > dy )
{
ai = ( dy - dx ) * 2 ;
bi = dy * 2 ;
d = bi - dx ;
// pętla po kolejnych x
while ( x != x2 )
{
// test współczynnika
if ( d > 0)
{
y += yi ;
d += ai ;
}
else
{
d += bi ;
x += xi ;
glVertex2i ( x , y ) ;
}
}
}
// oś wiodąca OY
else
{
ai = ( dx - dy ) * 2 ;
bi = dx * 2 ;
d = bi - dy ;
// pętla po kolejnych y
while ( y != y2 )
{
// test współczynnika
if ( d > 0)
{
x += xi ;
d += ai ;
}
else
{
d += bi ;
y += yi ;
glVertex2i ( x , y ) ;
}
}
}
}
Rysowanie linii (odcinaka) przechodząca przez dwa punkty o współrzędnych P1(x1,y1) i P2(x2,y2) procedura w języku Pascal
Procedure Linia(x1,y1,x2,y2,Kolor : integer);
var c,i : integer;
sx,sy,y,x : real;
begin
{ if x2<x1 then {ten warunek nie pozwala rysowac linii 'wygladajacej jak funkcja rosnaca'!!!}
begin
c:=x1;
x1:=x2;
x2:=c;
end;
if y2<y1 then
begin
c:=y2;
y2:=y1;
y1:=c;
end; }
if (x2-x1)>(y2-y1) then
begin
sy:=(y2-y1)/(x2-x1);
y:=y1;
for i:=x1 to x2 do
begin
putpixel(i,round(y),Kolor);
y:=y+sy;
end;
end else
begin
sx:=(x2-x1)/(y2-y1);
x:=x1;
for i:=y1 to y2 do
begin
putpixel(round(x),i,Kolor);
x:=x+sx;
end;
end;
end;
[edytuj] Algorytm Bresenhama dla okręgu
2.1 Założenia
Rozważamy elipsę w I ćwiartce układu współrzednych,
Rysowanie elipsy zaczynamy od punktu (0, b),
W każdym kroku stawiamy symetrycznie 4 punkty elipsy,
Poczatkową osią wiodacą jest os OX,
W punkcie zmiany osi wiodącej, współczynnik nachylenia stycznej do elipsy wynosi −1 (tg 135°)
2.2 Algorytm i jego działanie
O wyborze piksela decydować będzie wartość funkcji F(x, y) w punkcie środkowym M położonym pomiędzy alternatywnymi pikselami. Gdy osią wiodąca jest OX obliczamy
F (M) = F(xi + 1, yi −1/2)
Jeżeli F (M) > 0, to punkt M leży na zewnątrz elipsy i wybieramy piksel Pi+1 = SE. Natomiast, gdy F (M)<= 0, to punkt M leży wewnątrz elipsy lub na jej brzegu i wybieramy piksel Pi+1 = E. Gdy osią wiodąca jest OY obliczamy
F(M) = F(xi +1/2, yi − 1)
Jeżeli F (M) > 0, to punkt M leży poza elipsa i wybieramy piksel Pi+1 = S. Natomiast, gdy F (M) <= 0, to punkt M leży wewnątrz elipsy lub na jej brzegu i wybieramy piksel Pi+1 = SE.
Zgodnie z przyjętymi założeniami elipsę zaczynamy rysować w punkcie (0, b). Ponieważ osią wiodącą jest wówczas OX policzymy wartość zmiennej decyzyjnej d dla piksela startowego P0 = (x0, y0) = (0, b)
d0 = F(1, b −1/2)= b²+ a² (−b +1/4)
Jeżeli następnym pikselem jest Pi+1 = E (xi+1 = xi + 1, yi+1 = yi), to wartość zmiennej decyzyjnej wynosi:
di+1=F (xi+1+1,yi+1−1/2)= b²(xi+1+1)²+a²(yi+1−1/2)²−a²b²= b²(xi+1+1²+a²(yi−1/2)²-a²b²= F(xi+1,yi−1/2)+2b*2b(xi+1)+b²= di+2b²xi+1+b²
Jeżeli następnym pikselem jest Pi+1 = SE (xi+1 = xi+1, yi+1 = yi−1), to wartość zmiennej decyzyjnej wynosi:
di+1=F(xi+1+1,yi+1−1/2)= b²(xi+1+1)²+a²(yi+1−1/2)²− a²b² = b²(xi+1+1)²+a²(yi −1−1/2)−a²b² = F(xi+1,yi−1/2)+2b²(xi + 1)+b²−2a²(yi −1/2)+a² = di+2b²xi+1−2a²yi+1+b²
Przy zmianie osi wiodącej na OY należy także zmienić wartość zmiennej decyzyjnej. Różnica miedzy „nowa” i „stara” zmienna wynosi:
F(xi+1/2,yi−1)−F(xi+1,yi−1/2)= b²(xi+1/2)²+a²(yi − 1)²−a²b²−b²(xi + 1)²−a²(yi −1/2)²+a²b²= b²(x²i+xi+1/4)+a²(y²i−2yi+1)−b²(x2i+2xi+1)−a²)(y²i−yi+1/4)= b²(xi−2xi+1/4−1)+a²(−2yi+yi+1−1/4)= b2(−xi−3/4)+a²(−yi+3/4)
Teraz wyliczymy rekurencyjne równania opisujące zmienna decyzyjna, gdy osią wiodąca jest OY . Jeżeli następny piksel jest Pi+1 = SE (xi+1 = xi + 1, yi+1 = yi − 1), to wartość zmiennej decyzyjnej wynosi
di+1=F(xi+1+1/2,yi+1−1)= b²(xi+1+2)+a²(yi+1−1)²+a²b²= b²(xi+1+1/2)²+a²(yi−1−1)²+a²b² = F(xi+1/2,yi−1)+2b²(xi+1)−2a²(yi−1)+a²= di + 2b²xi+1 −2a²yi+1+a²
Przy wyborze następnego piksela Pi+1 = S (xi+1 = xi, yi+1 = yi−1) wartość zmiennej decyzyjnej wynosi:
di+1=F(xx+1+1/2,yi+1−1)= b²(xi+1+1/2)²+a²(yi+1−1)²+a²b²= b²(xi+2)+a²(yi−1−1)+a²b²= F(xi+1/2,yi−1)−2a2(yi−1)+a²= di−2a²yi+1+a²
