Algorytm linii Bresenhama - Bresenham's line algorithm

Algorytm bresenhama to rysunek linii algorytm , który określa punkty w n -wymiarowej rastra , które powinny być wybrane w celu utworzenia bliskiego zbliżenia do linii prostej pomiędzy dwoma punktami . Jest powszechnie używany do rysowania prymitywów liniowych w obrazie bitmapowym (np. na ekranie komputera ), ponieważ wykorzystuje tylko dodawanie, odejmowanie i przesuwanie bitów liczb całkowitych , z których wszystkie są bardzo tanimi operacjami w standardowych architekturach komputerowych . Jest to przyrostowy algorytm błędu . Jest to jeden z najwcześniejszych algorytmów opracowanych w dziedzinie grafiki komputerowej . Do rysowania okręgów można użyć rozszerzenia oryginalnego algorytmu .

Chociaż algorytmy takie jak algorytm Wu są również często używane we współczesnej grafice komputerowej, ponieważ mogą obsługiwać antyaliasing , szybkość i prostota algorytmu liniowego Bresenhama oznacza, że ​​jest on nadal ważny. Algorytm jest wykorzystywany w sprzęcie takim jak plotery oraz w układach graficznych nowoczesnych kart graficznych . Można go również znaleźć w wielu bibliotekach graficznych oprogramowania . Ponieważ algorytm jest bardzo prosty, często jest implementowany zarówno w oprogramowaniu układowym, jak i sprzęcie graficznym nowoczesnych kart graficznych .

Etykieta „Bresenham” jest dziś używana dla rodziny algorytmów rozszerzających lub modyfikujących oryginalny algorytm Bresenhama.

Historia

Algorytm liniowy Bresenhama nosi imię Jacka Eltona Bresenhama, który opracował go w 1962 roku w IBM . W 2001 roku Bresenham napisał:

Pracowałem w laboratorium obliczeniowym w laboratorium programistycznym IBM w San Jose. Calcomp ploter został dołączony do IBM 1401 za pośrednictwem konsoli 1407 maszynie. [Algorytm] był w produkcji do lata 1962, prawdopodobnie miesiąc wcześniej. Programy w tamtych czasach były swobodnie wymieniane między korporacjami, więc Calcomp (Jim Newland i Calvin Hefte) miał kopie. Kiedy wróciłem do Stanford jesienią 1962 roku, umieściłem kopię w bibliotece centrum komputerowego Stanford. Opis procedury rysowania linii został przyjęty do prezentacji na krajowej konwencji ACM w 1963 r. w Denver w stanie Kolorado. Był to rok, w którym nie opublikowano żadnych materiałów, a jedynie agendę prelegentów i tematy w numerze Komunikatów ACM. Po mojej prezentacji osoba z IBM Systems Journal zapytała mnie, czy mogą opublikować artykuł. Chętnie się zgodziłem i wydrukowali go w 1965 roku.

Algorytm Bresenhama został rozszerzony o koła, elipsy, sześcienne i kwadratowe krzywe Beziera, a także ich natywne wersje z antyaliasingiem.

metoda

Ilustracja wyniku algorytmu linii Bresenhama. (0,0) znajduje się w lewym górnym rogu siatki, (1,1) znajduje się w lewym górnym końcu linii, a (11, 5) jest w prawym dolnym końcu linii.

Stosowane będą następujące konwencje:

• górny lewy jest (0,0) taki, że współrzędne piksela rosną w prawo iw dół (np. piksel w (7,4) znajduje się bezpośrednio nad pikselem w (7,5)), oraz
• centra pikseli mają współrzędne całkowite.

Punktami końcowymi linii są piksele w miejscu i , gdzie pierwsza współrzędna pary to kolumna, a druga to wiersz. ${\displaystyle (x_{0},y_{0})}$${\styl wyświetlania (x_{1},y_{1})}$

Algorytm zostanie wstępnie przedstawiony tylko dla oktantu, w którym odcinek opada w prawo ( i ), a jego rzut poziomy jest dłuższy niż rzut pionowy (linia ma dodatnie nachylenie mniejsze niż 1). W tym oktancie, dla każdej kolumny x pomiędzy i , istnieje dokładnie jeden wiersz y (obliczony przez algorytm) zawierający piksel linii, podczas gdy każdy wiersz pomiędzy i może zawierać wiele zrastrowanych pikseli. ${\displaystyle x_{0}\leq x_{1}}$${\displaystyle y_{0}\leq y_{1}}$${\displaystyle x_{1}-x_{0}}$${\displaystyle y_{1}-y_{0}}$${\displaystyle x_{0}}$${\displaystyle x_{1}}$${\displaystyle y_{0}}$${\displaystyle Y_{1}}$

Algorytm Bresenhama wybiera liczbę całkowitą y odpowiadającą centrum piksela, która jest najbliżej idealnego (ułamkowego) y dla tego samego x ; na kolejnych kolumnach y może pozostać bez zmian lub zwiększyć się o 1. Ogólne równanie prostej przechodzącej przez punkty końcowe jest dane wzorem:

${\displaystyle {\frac {y-y_{0}}{y_{1}-y_{0}}}={\frac {x-x_{0}}{x_{1}-x_{0}}} }$.

Ponieważ znamy kolumnę x , rząd piksela y , otrzymujemy zaokrąglając tę ​​wielkość do najbliższej liczby całkowitej:

${\ Displaystyle y = {\ Frac {y_ {1}-y_ {0}} {x_ {1}-x_ {0}}} (x-x_ {0}) + Y_ {0}}$.

Nachylenie zależy tylko od współrzędnych punktu końcowego i można je wstępnie obliczyć , a idealne y dla kolejnych wartości całkowitych x można obliczyć, zaczynając od i wielokrotnie dodając nachylenie. ${\displaystyle (y_{1}-y_{0})/(x_{1}-x_{0})}$${\displaystyle y_{0}}$

W praktyce algorytm nie śledzi współrzędnej y, która rośnie o m = ∆y/∆x za każdym razem, gdy x wzrasta o jeden; utrzymuje błąd ograniczony na każdym etapie, który reprezentuje ujemną odległość od (a) punktu, w którym linia wychodzi z piksela do (b) górnej krawędzi piksela. Ta wartość jest najpierw ustawiana na (ze względu na użycie współrzędnych środka piksela) i jest zwiększana o m za każdym razem, gdy współrzędna x jest zwiększana o jeden. Jeśli błąd staje się większy niż 0.5 , wiemy, że linia przesunęła się w górę o jeden piksel i że musimy zwiększyć naszą współrzędną y i ponownie dostosować błąd, aby reprezentował odległość od wierzchołka nowego piksela – co jest wykonywane przez odjęcie jednego od błąd. ${\ Displaystyle y_{0}-0,5}$

Pochodzenie

Aby wyprowadzić algorytm Bresenhama, należy podjąć dwa kroki. Pierwszym krokiem jest przekształcenie równania prostej z typowej postaci przecięcia nachylenia w coś innego; a następnie za pomocą tego nowego równania narysować linię opartą na idei akumulacji błędu.

Równanie liniowe

y=f(x)=0,5x+1 lub f(x,y)=x-2y+2

Półpłaszczyzny dodatnie i ujemne

Postać przecięcia nachylenia linii jest zapisana jako

${\ Displaystyle y = f (x) = mx + b}$

gdzie m to nachylenie, a b to punkt przecięcia z osią Y. Jest to funkcja tylko od x i przydałoby się zapisać to równanie jako funkcję zarówno x, jak i y. Korzystanie z manipulacji algebraicznych i rozpoznanie, że nachylenie to „nachylenie nad przebiegiem” lub wtedy ${\ Displaystyle \ Delta y/\ Delta x}$

${\ Displaystyle {\ zacząć {wyrównany} y& = mx + b \ \ y& = {\ Frac {(\ delta y)} {(\ delta x)}} x + b \ \ (\ delta x) y = (\ Delta y)x+(\Delta x)b\\0&=(\Delta y)x-(\Delta x)y+(\Delta x)b\end{wyrównany}}}$

Niech to ostatnie równanie będzie funkcją od x i y, to można je zapisać jako

${\ Displaystyle f (x, y) = 0 = Ax + przez + C}$

gdzie są stałe

• ${\ Displaystyle A = \ Delta y}$
• ${\displaystyle B=-\delta x}$
• ${\ Displaystyle C = (\ Delta x) b}$

Linia jest następnie definiowana dla pewnych stałych A, B i C w dowolnym miejscu . Dla każdego, kto nie jest na linii . Wszystko w tej formie zawiera tylko liczby całkowite, jeśli x i y są liczbami całkowitymi, ponieważ stałe są koniecznie liczbami całkowitymi. ${\ Displaystyle f (x, y) = 0}$${\displaystyle (x,y)}$${\displaystyle f(x,y)\neq 0}$

Jako przykład, linia to może być zapisana jako . Punkt (2,2) jest na linii ${\ Displaystyle y = {\ Frac {1} {2}} x + 1}$${\displaystyle f(x,y)=x-2y+2}$

${\ Displaystyle f (2, 2) = x-2y +2 = (2) -2 (2) +2 = 2-4 +2 = 0}$

a punkt (2,3) nie leży na linii

${\ Displaystyle f (2,3) = (2)-2 (3) + 2 = 2-6 + 2 = -2}$

i nie chodzi o (2,1)

${\ Displaystyle f (2, 1) = (2)-2 (1) + 2 = 2-2 + 2 = 2}$

Zauważ, że punkty (2,1) i (2,3) znajdują się po przeciwnych stronach linii, a f(x,y) daje wynik dodatni lub ujemny. Linia dzieli płaszczyznę na połowy i półpłaszczyzna, która ma ujemną f(x,y) można nazwać ujemną półpłaszczyzną, a drugą połowę można nazwać dodatnią półpłaszczyzną. Ta obserwacja jest bardzo ważna w pozostałej części wyprowadzenia.

Algorytm

Najwyraźniej punkt wyjścia znajduje się na linii

${\ Displaystyle f (x_ {0}, y_ {0}) = 0}$

tylko dlatego, że linia jest zdefiniowana tak, aby zaczynała się i kończyła na współrzędnych całkowitych (chociaż całkiem rozsądne jest rysowanie linii z niecałkowitymi punktami końcowymi).

Punkt kandydujący (2,2) na niebiesko i dwa punkty kandydujące na zielono (3,2) i (3,3)

Mając na uwadze, że nachylenie jest mniejsze lub równe jedności, pojawia się teraz problem, czy następny punkt powinien znajdować się na lub . Być może intuicyjnie, punkt należy wybrać na podstawie tego, który jest bliżej linii w . Jeśli jest bliższy temu pierwszemu, uwzględnij na linii pierwszy punkt, jeśli ten drugi, to drugi. Aby odpowiedzieć na to pytanie, oceń funkcję linii w punkcie środkowym między tymi dwoma punktami: ${\displaystyle (x_{0}+1,y_{0})}$${\displaystyle (x_{0}+1,y_{0}+1)}$${\displaystyle x_{0}+1}$

${\displaystyle f(x_{0}+1,y_{0}+{\tfrac {1}{2}})}$

Jeśli wartość tego jest dodatnia, to idealna linia znajduje się poniżej punktu środkowego i bliżej punktu kandydującego ; w efekcie współrzędna y przesunęła się do przodu. W przeciwnym razie idealna linia przechodzi przez lub powyżej punktu środkowego, a współrzędna y nie przesunęła się; w tym przypadku wybierz punkt . Ta obserwacja jest kluczowa do zrozumienia! Wartość funkcji linii w tym punkcie środkowym jest jedynym wyznacznikiem tego, który punkt należy wybrać. ${\displaystyle (x_{0}+1,y_{0}+1)}$${\displaystyle (x_{0}+1,y_{0})}$

Na sąsiednim obrazie pokazano niebieski punkt (2,2) wybrany na linię z dwoma kandydackimi punktami w kolorze zielonym (3,2) i (3,3). Czarny punkt (3, 2,5) jest punktem środkowym między dwoma punktami kandydującymi.

Algorytm arytmetyki liczb całkowitych

Alternatywnie można użyć różnicy między punktami zamiast oceniać f(x,y) w punktach środkowych. Ta alternatywna metoda umożliwia arytmetykę wyłącznie na liczbach całkowitych, która jest zazwyczaj szybsza niż arytmetyka zmiennoprzecinkowa. Aby wyprowadzić alternatywną metodę, zdefiniuj różnicę w następujący sposób:

${\ Displaystyle D = f (x_ {0}+1, y_ {0}+ {\ tfrac {1} {2}})-f (x_ {0}, y_ {0})}$

W przypadku pierwszej decyzji to sformułowanie jest równoważne metodzie punktu środkowego, ponieważ w punkcie wyjścia. Uproszczenie tego wyrażenia daje: ${\ Displaystyle f (x_ {0}, y_ {0}) = 0}$

${\ Displaystyle {\ zacząć {tablica} {rclcl} D & = i \ lewo [A (x_ {0}+1) + B \ lewo (y_ {0}+ {\ Frac {1} {2}} \ po prawej) +C\right]&-&\left[Ax_{0}+B_{0}+C\right]\\&=&\left[Ax_{0}+B_{0}+C+A+{\frac { 1}{2}}B\right]&-&\left[Ax_{0}+By_{0}+C\right]\\&=&A+{\frac {1}{2}}B\end{array }}}$

Podobnie jak w przypadku metody punktu środkowego, jeśli D jest dodatnie, wybierz , w przeciwnym razie wybierz . ${\displaystyle (x_{0}+1,y_{0}+1)}$${\displaystyle (x_{0}+1,y_{0})}$

Jeśli zostanie wybrany, zmiana w D będzie: ${\displaystyle (x_{0}+1,y_{0})}$

${\ Displaystyle {\ zacząć {tablica} {lclcl} \ Delta D & = & F (x_ {0}+2, Y_ {0}+ {\ tfrac {1}{2}})-f (x_ {0}+1 ,y_{0}+{\tfrac {1}{2}})&=&A&=&\Delta y\\\end{array}}}$

Jeśli zostanie wybrana zmiana w D będzie: ${\displaystyle (x_{0}+1,y_{0}+1)}$

${\ Displaystyle {\ zacząć {tablica} {lclcl} \ Delta D & = & f (x_ {0}+2, y_ {0}+ {\ tfrac {3}{2}})-f (x_ {0}+1 ,y_{0}+{\tfrac {1}{2}})&=&A+B&=&\Delta y-\Delta x\end{array}}}$

Jeśli nowe D jest dodatnie, wybiera się, w przeciwnym razie . Decyzję tę można uogólnić, akumulując błąd w każdym kolejnym punkcie. ${\displaystyle (x_{0}+2,y_{0}+1)}$${\displaystyle (x_{0}+2,y_{0})}$

Wykreślanie linii od (0,1) do (6,4) pokazującej wykres linii siatki i pikseli

Całe wyprowadzenie algorytmu jest wykonane. Jednym z problemów z wydajnością jest czynnik 1/2 początkowej wartości D. Ponieważ wszystko to dotyczy znaku skumulowanej różnicy, wszystko można pomnożyć przez 2 bez żadnych konsekwencji.

Daje to algorytm, który używa tylko arytmetyki liczb całkowitych.

plotLine(x0, y0, x1, y1)
    dx = x1 - x0
    dy = y1 - y0
    D = 2*dy - dx
    y = y0

    for x from x0 to x1
        plot(x,y)
        if D > 0
            y = y + 1
            D = D - 2*dx
        end if
        D = D + 2*dy

Uruchomienie tego algorytmu dla od (0,1) do (6,4) daje następujące różnice przy dx=6 i dy=3: ${\displaystyle f(x,y)=x-2y+2}$

D=2*3-6=0
Loop from 0 to 6
 * x=0: plot(0, 1), D≤0: D=0+6=6
 * x=1: plot(1, 1), D>0: D=6-12=-6, y=1+1=2, D=-6+6=0
 * x=2: plot(2, 2), D≤0: D=0+6=6
 * x=3: plot(3, 2), D>0: D=6-12=-6, y=2+1=3, D=-6+6=0
 * x=4: plot(4, 3), D≤0: D=0+6=6
 * x=5: plot(5, 3), D>0: D=6-12=-6, y=3+1=4, D=-6+6=0
 * x=6: plot(6, 4), D≤0: D=0+6=6

Wynik tego wykresu jest pokazany po prawej stronie. Wykres można oglądać, kreśląc na przecięciu linii (niebieskie kółka) lub wypełniając pola pikseli (żółte kwadraty). Niezależnie od tego fabuła jest taka sama.

Wszystkie przypadki

Jednak, jak wspomniano powyżej, dotyczy to tylko oktantu zero, to znaczy linii zaczynających się od początku z gradientem od 0 do 1, gdzie x wzrasta dokładnie o 1 na iterację, a y wzrasta o 0 lub 1.

Algorytm można rozszerzyć, aby obejmował gradienty od 0 do -1, sprawdzając, czy y musi się zwiększyć, czy zmniejszyć (tzn. dy < 0)

plotLineLow(x0, y0, x1, y1)
    dx = x1 - x0
    dy = y1 - y0
    yi = 1
    if dy < 0
        yi = -1
        dy = -dy
    end if
    D = (2 * dy) - dx
    y = y0

    for x from x0 to x1
        plot(x, y)
        if D > 0
            y = y + yi
            D = D + (2 * (dy - dx))
        else
            D = D + 2*dy
        end if

Przełączając osie x i y implementację dla dodatnich lub ujemnych stromych gradientów można zapisać jako

plotLineHigh(x0, y0, x1, y1)
    dx = x1 - x0
    dy = y1 - y0
    xi = 1
    if dx < 0
        xi = -1
        dx = -dx
    end if
    D = (2 * dx) - dy
    x = x0

    for y from y0 to y1
        plot(x, y)
        if D > 0
            x = x + xi
            D = D + (2 * (dx - dy))
        else
            D = D + 2*dx
        end if

Kompletne rozwiązanie wymagałoby wykrycia, czy x1 > x0 czy y1 > y0 i odwrócenia współrzędnych wejściowych przed rysowaniem, a zatem

plotLine(x0, y0, x1, y1)
    if abs(y1 - y0) < abs(x1 - x0)
        if x0 > x1
            plotLineLow(x1, y1, x0, y0)
        else
            plotLineLow(x0, y0, x1, y1)
        end if
    else
        if y0 > y1
            plotLineHigh(x1, y1, x0, y0)
        else
            plotLineHigh(x0, y0, x1, y1)
        end if
    end if

W implementacjach niskiego poziomu, które uzyskują bezpośredni dostęp do pamięci wideo, typowe byłoby, aby szczególne przypadki linii pionowych i poziomych były obsługiwane oddzielnie, ponieważ mogą być wysoce zoptymalizowane.

Niektóre wersje wykorzystują zasady Bresenhama dotyczące całkowitego błędu przyrostowego, aby wykonać wszystkie rysowania linii oktantowych, równoważąc błąd dodatni i ujemny między współrzędnymi x i y. Zwróć uwagę, że zamówienie niekoniecznie jest gwarantowane; innymi słowy, linia może być poprowadzona od (x0, y0) do (x1, y1) lub od (x1, y1) do (x0, y0).

plotLine(int x0, int y0, int x1, int y1)
    dx =  abs(x1-x0);
    sx = x0<x1 ? 1 : -1;
    dy = -abs(y1-y0);
    sy = y0<y1 ? 1 : -1;
    err = dx+dy;  /* error value e_xy */
    while (true)   /* loop */
        plot(x0, y0);
        if (x0 == x1 && y0 == y1) break;
        e2 = 2*err;
        if (e2 >= dy) /* e_xy+e_x > 0 */
            err += dy;
            x0 += sx;
        end if
        if (e2 <= dx) /* e_xy+e_y < 0 */
            err += dx;
            y0 += sy;
        end if
    end while

Podobne algorytmy

Algorytm Bresenhama może być interpretowany jako nieznacznie zmodyfikowany cyfrowy analizator różnicowy (używając 0,5 jako progu błędu zamiast 0, co jest wymagane w przypadku rasteryzacji wielokątów nienakładających się).

Zasada stosowania błędu przyrostowego w miejsce operacji dzielenia ma inne zastosowania w grafice. Możliwe jest użycie tej techniki do obliczenia współrzędnych U, V podczas skanowania rastrowego wielokątów z mapami tekstur. W woksel heightmap silniki software rendering widziane w niektórych grach komputerowych stosowane również tę zasadę.

Bresenham opublikował również algorytm obliczeniowy Run-Slice (w przeciwieństwie do Run-Length). Ta metoda została przedstawiona w wielu patentach amerykańskich:

Rozszerzenie algorytmu obsługującego grube linie zostało stworzone przez Alana Murphy'ego w IBM.

Zobacz też

• Cyfrowy analizator różnicowy (algorytm graficzny) , prosta i ogólna metoda rasteryzacji linii i trójkątów
• Algorytm linii Xiaolin Wu , podobnie szybka metoda rysowania linii z antyaliasingiem
• Algorytm okręgu środkowego , podobny algorytm do rysowania okręgów

Uwagi

Bibliografia

• Bresenham, JE (1965). „Algorytm komputerowego sterowania ploterem cyfrowym” (PDF) . Dziennik systemów IBM . 4 (1): 25–30. doi : 10.1147/sj.41.0025 . Zarchiwizowane z oryginału (PDF) w dniu 28 maja 2008 r.
• „Algorytm rysowania linii Bresenham” , Colin Flanagan
• Abrash, Michael (1997). Czarna księga programowania graficznego Michaela Abrasha . Albany, NY: Coriolis. s.  654–678 . Numer ISBN 978-1-57610-174-2. Bardzo zoptymalizowana wersja algorytmu w języku C i asemblacji do użytku w grach wideo z pełnymi szczegółami jego wewnętrznego działania
• Zingl, Alois (2012). „Algorytm rasteryzacji do rysowania krzywych” (PDF) ., Piękno algorytmów Bresenhama

Dalsza lektura

• Teza Patricka-Gillesa Maillota jest rozszerzeniem algorytmu rysowania linii Bresenham do usuwania ukrytych linii 3D; opublikowany również w postępowaniu MICAD '87 dotyczącym CAD/CAM i Grafiki Komputerowej, strona 591 - ISBN  2-86601-084-1 .
• Zagęszczanie linii przez modyfikację algorytmu Bresenhama , AS Murphy, IBM Technical Disclosure Bulletin, tom. 20, nr 12, maj 1978.

zamiast [który] do rozszerzenia okręgu użyj: Raport techniczny 1964 27 stycznia -11- Circle Algorithm TR-02-286 IBM San Jose Lab lub A Linear Algorithm for Incremental Digital Display of Circular Arcs Luty 1977 Komunikacja ACM 20(2 ):100-106 DOI:10,1145/359423,359432

Zewnętrzne linki

• Michael Abrash's Graphics Programming Black Book Wydanie specjalne: Rozdział 35: Bresenham jest szybki, a szybki jest dobry
• Algorytm rysowania linii Bresenham autorstwa Colina Flanagana
• Strona Narodowego Instytutu Standardów i Technologii na algorytmie Bresenhama
• Informacje o ploterze przyrostowym Calcomp 563
• Algorytm Bresenhama w kilku językach programowania
• Piękno algorytmu Bresenham – prosta implementacja do kreślenia linii, okręgów, elips i krzywych Béziera