Algorytm okręgu środkowego

  Rasteryzacja okręgu o promieniu 23 za pomocą algorytmu okręgu punktu środkowego Bresenhama. W rzeczywistości obliczany jest tylko zielony oktant, jest on po prostu odbijany ośmiokrotnie w celu utworzenia pozostałych siedmiu oktantów.

Okrąg o promieniu 23 narysowany algorytmem Bresenhama

W grafice komputerowej algorytm okręgu punktu środkowego jest algorytmem używanym do określania punktów potrzebnych do rasteryzacji okręgu . Algorytm okręgu Bresenhama wywodzi się z algorytmu okręgu punktu środkowego. Algorytm można uogólnić na przekroje stożkowe .

Algorytm jest powiązany z pracami Pittewaya i Van Akena.

Streszczenie

Algorytm ten rysuje wszystkie osiem oktantów jednocześnie, zaczynając od każdego kierunku kardynalnego (0°, 90°, 180°, 270°) i rozciąga w obie strony, aby osiągnąć najbliższą wielokrotność 45° (45°, 135°, 225°, 315° ). Może określić, gdzie się zatrzymać, ponieważ gdy y = x , osiągnął 45°. Powód użycia tych kątów pokazano na powyższym rysunku: Gdy x rośnie, nie pomija ani nie powtarza żadnej wartości x , aż do osiągnięcia 45°. Tak więc podczas pętli while x zwiększa się o 1 w każdej iteracji, a y od czasu do czasu zmniejsza się o 1, nigdy nie przekraczając 1 w jednej iteracji. Zmienia się to przy kącie 45°, ponieważ jest to punkt, w którym styczna jest wznosząca = biegnąca. Podczas gdy wstań>biegnij przed i wstań<biegnij po.

Druga część problemu, wyznacznik, jest znacznie trudniejsza. To określa, kiedy należy zmniejszyć y . Zwykle pojawia się po narysowaniu pikseli w każdej iteracji, ponieważ nigdy nie schodzi poniżej promienia pierwszego piksela. Ponieważ w funkcji ciągłej funkcja dla sfery jest funkcją dla okręgu o promieniu zależnym od z (lub jakiejkolwiek trzeciej zmiennej), zrozumiałe jest, że algorytm dla sfery dyskretnej (woksela) również polegałby na ten algorytm okręgu punktu środkowego. Ale patrząc na kulę, całkowity promień niektórych sąsiednich okręgów jest taki sam, ale nie oczekuje się, że będzie miał ten sam dokładny okrąg przylegający do siebie na tej samej półkuli. Zamiast tego okrąg o tym samym promieniu potrzebuje innego wyznacznika, aby krzywa mogła zbliżyć się nieco bliżej środka lub rozszerzyć dalej.

• Sto pięćdziesiąt koncentrycznych okręgów narysowanych za pomocą algorytmu okręgu środkowego.
• 

  Po lewej wszystkie okręgi są narysowane na czarno.

• 

  Po prawej, czerwony, czarny i niebieski są używane razem, aby zademonstrować koncentryczność okręgów.

Algorytm

$_$ algorytmu _ w kategoriach laika każdy piksel powinien znajdować się w przybliżeniu w tej samej odległości od środka. Na każdym kroku ścieżka jest wydłużana przez wybór sąsiedniego piksela, który spełnia ${\ Displaystyle x ^ {2} + y ^ {2} \ równoważnik r ^ {2}}$ ale maksymalizuje ${\ Displaystyle x ^ {2} + y ^ {2}}$ . Ponieważ kandydujące piksele sąsiadują ze sobą, arytmetyka obliczania tego ostatniego wyrażenia jest uproszczona i wymaga jedynie przesunięć bitowych i dodawania. Ale można zrobić uproszczenie, aby zrozumieć przesunięcie bitowe. Należy pamiętać, że przesunięcie bitowe liczby binarnej w lewo jest tym samym, co mnożenie przez 2. Ergo, przesunięcie bitowe promienia w lewo daje tylko średnicę zdefiniowaną jako promień razy dwa.

Ten algorytm zaczyna się od równania koła . Dla uproszczenia załóżmy, że środek okręgu znajduje się w punkcie ${\ Displaystyle (0,0)}$ . Rozważ najpierw tylko pierwszy $wskazówek$ i narysuj krzywą, która zaczyna się w punkcie , osiągając kąt 45.

Szybki kierunek tutaj ( wektor bazowy o większym wzroście wartości) to kierunek $\ displaystyle y}$ { . Algorytm zawsze robi krok w kierunku dodatnim $($$robi$ krok w wolnym kierunku ( ujemny ).

$2$ równania otrzymuje ${2}}$$r$ jest obliczane tylko raz podczas inicjalizacji.

Niech punkty na okręgu będą ciągiem współrzędnych wektora do punktu (w zwykłej bazie). Punkty są numerowane zgodnie z kolejnością, w jakiej zostały wylosowane, z $displaystyle$ do pierwszego punktu $(r, 0$ .

Dla każdego punktu obowiązuje:

${\ Displaystyle {\ rozpocząć {wyrównane} x_ {n} ^ {2} + y_ {n} ^ {2} = r ^ {2} \ koniec {wyrównane}}}$

Można to przeorganizować w ten sposób:

${\ Displaystyle {\ rozpocząć {wyrównane} x_ {n} ^ {2} = r ^ {2} -y_ {n} ^ {2} \ koniec {wyrównane}}}$

I podobnie w kolejnym punkcie:

${\ Displaystyle {\ rozpocząć {wyrównane} x_ {n + 1} ^ {2} = r ^ {2} -y_ {n + 1} ^ {2} \end{wyrównane}}}$

Ponieważ dla pierwszej oktanty następny punkt będzie zawsze co najmniej o 1 piksel wyższy niż ostatni (ale także co najwyżej o 1 piksel wyższy, aby zachować ciągłość), prawdą jest, że:

${\ Displaystyle {\ rozpocząć {wyrównane} y_ {n + 1} ^ {2} i = (y_ {n} + 1)^{2}\\&=y_{n}^{2}+2y_{n}+1\end{wyrównane}}}$

${\ Displaystyle {\ rozpocząć {wyrównane} x_ {n + 1} ^ {2} = r ^ {2} -y_ {n} ^ {2} -2y_ {n} -1 \ koniec {wyrównane}}}$

Przerób więc równanie następnego punktu na rekurencyjne, podstawiając ${\ Displaystyle x_ {n} ^ {2} = r ^ {2} -y_ {n} ^ {2 }}$ :

${\ Displaystyle {\ rozpocząć {wyrównane} x_ {n + 1} ^ {2} = x_ {n} ^ {2} -2y_ {n} -1 \end{wyrównane}}}$

Ze względu na ciągłość koła i ponieważ maksima wzdłuż obu osi są takie same, oczywiście nie będzie pomijać x punktów w miarę postępu w sekwencji. Zwykle pozostaje na tej samej x , a czasem przesuwa się o jeden.

Wynikowa współrzędna jest następnie tłumaczona przez dodanie współrzędnych punktu środkowego. Te częste dodawania liczb całkowitych nie ograniczają wydajności , ponieważ te obliczenia kwadratowe (pierwiastkowe) można z kolei oszczędzić w pętli wewnętrznej. Ponownie zero w przekształconym równaniu koła jest zastępowane przez składnik błędu.

Inicjalizacja składnika błędu pochodzi z przesunięcia o ½ piksela na początku. Aż do przecięcia z linią prostopadłą prowadzi to do skumulowanej wartości $składniku$ błędu, tak że ta wartość jest używana do inicjalizacji

Częstych obliczeń kwadratów w równaniu koła, wyrażeniach trygonometrycznych i pierwiastkach kwadratowych można ponownie uniknąć, rozkładając wszystko na pojedyncze kroki i stosując rekurencyjne obliczanie wyrazów kwadratowych z poprzednich iteracji.

Wariant z arytmetyką opartą na liczbach całkowitych

Podobnie jak w przypadku algorytmu liniowego Bresenhama , algorytm ten można zoptymalizować pod kątem matematyki opartej na liczbach całkowitych. Ze względu na symetrię, jeśli można znaleźć algorytm, który oblicza piksele tylko dla jednego oktanta, piksele można odbić, aby uzyskać całe koło.

Zaczynamy od zdefiniowania błędu promienia jako różnicy między dokładną reprezentacją okręgu a punktem środkowym każdego piksela (lub dowolnego innego dowolnego matematycznego punktu na pikselu, o ile jest on spójny we wszystkich pikselach). Dla dowolnego piksela ze środkiem w punkcie błąd promienia jest definiowany jako: ${\ Displaystyle (x_ {i}, y_ {i})}$

${\ Displaystyle RE (x_ {i}, y_ {i}) = \ lewo \ vert x_ {i} ^ {2} + y_ {i} ^ {2} -r ^ {2} \ prawo \ vert}$

Dla jasności ten wzór na okrąg pochodzi z początku, ale algorytm można zmodyfikować dla dowolnej lokalizacji. Warto zacząć $punktu$ X. Ponieważ promień będzie całkowitą liczbą pikseli, błąd promienia będzie oczywiście równy zeru:

${\ Displaystyle RE (x_ {i}, y_ {i}) = \ lewo \ vert x_ {i} ^ {2} + 0 ^ {2} -r ^ {2} \ prawo \ vert = 0}$

Ponieważ zaczyna się w pierwszej oktancie dodatniej w kierunku przeciwnym do ruchu wskazówek zegara, wykona krok w kierunku o największym ruchu , w kierunku Y, więc jasne jest, że ${\ Displaystyle y_ {i + 1} =y_{i}+1}$ . Ponadto, ponieważ dotyczy to tylko tego oktanta, X mają tylko 2 opcje: pozostać takie same jak w poprzedniej iteracji lub zmniejszyć o 1. Można utworzyć zmienną decyzyjną, która określa, czy poniższe stwierdzenie jest prawdziwe:

${\ Displaystyle RE (x_ {i} -1, y_ {i} + 1) <RE (x_ {i} },y_{i}+1)}$

Jeśli ta nierówność zachodzi, to wykreśl ${\ Displaystyle (x_ {i} -1, y_ {i} + 1)}$ ; jeśli nie, to wykres ${\ Displaystyle (x_ {i}, y_ {i} + 1)}$ . Jak więc ustalić, czy ta nierówność zachodzi? Zacznij od definicji błędu promienia:

${\ Displaystyle {\ rozpocząć {wyrównane} RE (x_ {i} -1, y_ {i} + 1) & < RE (x_ {i}, y_ {i} + 1) \\\ lewo \ vert (x_ { i}-1)^{2}+(y_{i}+1)^{2}-r^{2}\right\vert &<\left\vert x_{i}^{2}+(y_{ i}+1)^{2}-r^{2}\right\vert \\\left\vert (x_{i}^{2}-2x_{i}+1)+(y_{i}^{ 2}+2y_{i}+1)-r^{2}\right\vert &<\left\vert x_{i}^{2}+(y_{i}^{2}+2y_{i}+ 1)-r^{2}\right\vert \\\end{wyrównane}}}$

Funkcja wartości bezwzględnej nie pomaga, więc podnieś obie strony do kwadratu, ponieważ kwadrat jest zawsze dodatni:

${\ Displaystyle {\ rozpocząć {wyrównane} \ lewo [(x_ {i} ^ {2} -2x_ {i} +1) + (y_ {i} ^ {2} + 2y_ {i} +1) -r ^ {2}\right]^{2}&<\left[x_{i}^{2}+(y_{i}^{2}+2y_{i}+1)-r^{2}\right] ^{2}\\\lewo[(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i}) \right]^{2}&<\left[x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^{2}\ \\left(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right)^{2}+2(1-2x_{i} )(x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<\lewo [x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1\right]^{2}\\2(1-2x_{i})( x_{i}^{2}+y_{i}^{2}-r^{2}+2y_{i}+1)+(1-2x_{i})^{2}&<0\\\ koniec {wyrównany}}}$

Ponieważ x > 0, termin ${\ Displaystyle (1-2x_ {i}) <0}$ , więc dzielenie daje:

${\ Displaystyle {\ rozpocząć {wyrównane} 2 \ lewo [(x_ {i} ^ {2} + y_ {i} ^ {2} -r ^ {2}) + (2y_ {i} + 1) \ prawo] +(1-2x_{i})&>0\\2\left[RE(x_{i},y_{i})+Y_{\text{Zmiana}}\right]+X_{\text{Zmiana} }&>0\\\koniec{wyrównany}}}$

W ten sposób kryterium decyzyjne zmienia się z operacji zmiennoprzecinkowych na proste dodawanie, odejmowanie i przesuwanie liczb całkowitych (dla operacji mnożenia przez 2). Jeśli ${\ Displaystyle 2 (RE + Y _ {\ tekst {Zmiana}}) + X _ {\ tekst {Zmiana}}> 0}$ , a następnie zmniejsz wartość x . Jeśli ${\ Displaystyle 2 (RE + Y _ {\ text {Zmiana}}) + X _ {\ text {Zmiana}} \ równoważnik 0}, a$ następnie zachowaj tę samą wartość x . Ponownie, odbijając te punkty we wszystkich oktantach, powstaje pełne koło.

Możemy zredukować obliczenia, obliczając jedynie deltę między wartościami tej formuły decyzyjnej od jej wartości w poprzednim kroku. Zaczynamy od przypisania $displaystyle$ 3 $3-2r}$ , która jest początkową wartością wzoru w $r, 0)}$${\ displaystyle (x_ {0}, y_ {0}) =$$aktualizujemy$ to jak powyżej na każdym kroku, jeśli to jako ${\ Displaystyle E = E + 2 (5-2x + 2y)}$ (i zmniejszać X ), w przeciwnym razie ${\ Displaystyle E=E+2(3+2y)}$ stąd przyrost Y jak zwykle.

Rysowanie niekompletnych oktantów

Powyższe implementacje zawsze rysują tylko pełne oktanty lub okręgi. $,$ narysować tylko określony łuk od kąta do $kąta$ algorytm musi najpierw obliczyć współrzędne tych i $displaystyle$$y$ punkty końcowe, w przypadku których konieczne jest skorzystanie z obliczeń trygonometrycznych lub pierwiastków kwadratowych (patrz Metody obliczania pierwiastków kwadratowych ). Następnie algorytm Bresenham jest uruchamiany na całym oktancie lub okręgu i ustawia piksele tylko wtedy, gdy mieszczą się one w żądanym przedziale. Po zakończeniu tego łuku algorytm można zakończyć przedwcześnie.

Jeśli kąty są podane jako nachylenia , to $pierwiastki$ kwadratowe nie są potrzebne: po prostu sprawdź, czy się pomiędzy żądanymi nachyleniami

Uogólnienia

Możliwe jest również użycie tej samej koncepcji do rasteryzacji paraboli , elipsy lub dowolnej innej krzywej dwuwymiarowej .

Linki zewnętrzne

• Rysowanie kół - artykuł o rysowaniu kół, który przechodzi od prostego schematu do wydajnego
• Midpoint Circle Algorithm w kilku językach programowania