Piszę sobie software'ową rasteryzację trójkąta z wykorzystaniem techniki polegającej na podążaniu wzdłuż osi Y z góry na dół, wykrywaniu kolejnych pikseli wschodzących w skład boków trójkąta i łączenie ich poziomą linią (scan line).
Możliwie najprostszym rozwiązaniem jest tutaj algorytm DDA, który jednak z uwagi na wykorzystanie dzielenia liczb zmiennoprzecinkowych i zaokrągleń, nie jest zbyt wydajny. Jego rozwinięciem jest słynny algorytm Bresenhama, który działa podobnie, ale operuje tylko na liczbach całkowitych (a więc jest szybszy), a do tego zapewnia większą dokładność (bo nie wymusza zaokrągleń).
Są też inne algorytmy (np Wu Line czy EFLA), które zapewniają nawet większą wydajność, ale póki co, głównie z uwagi na prostotę, stawiam na Bresenhama. Niestety jego adaptacja do moich potrzeb mnie przerosła...
Pewnie każdy koder o tym algorytmie słyszał, ale raczej nie każdy zagłębiał się w jego działanie, więc pokrótce wyjaśnię.
Mamy 2 punkty w przestrzeni 2D, które chcemy połączyć linią. Weźmy np.
P1 = [1, 1]
P2 = [12, 6]
- Liczymy wektor pomiędzy nimi [X2 - X1, Y2 - Y1], czyli [12 - 1, 6 - 1], a więc wektor = [11, 5].
- Wyznaczamy oś wiodącą oraz oś uboczną (po co się to robi, wyjaśni się dalej). Osią główną jest zawsze ta dłuższa, uboczną krótsza. U nas wiodącą osią będzie X (bo = 11), uboczną Y( bo = 5).
- Wyznaczamy kierunek ruchu na obu osiach, który może przyjąć jedną z 3 wartości: +1, -1 lub 0. U nas obie osie są dodatnie, więc kierunek ruchu na obu osiach również będzie dodatni, czyli X = +1, Y = +1 (ruch będzie się więc odbywać z lewej na prawo i z góry na dół).
- Liczymy 3 wartości: Pozytywny (P), Negatywny (N) oraz Czynnik Decyzyjny (D)
- Pozytywny (P) liczymy ze wzoru: P = 2 x (Wektor Osi Ubocznej - Wektor Osi Wiodącej), a więc 2 x (5 - 11), czyli -12 (Pozytywny zawsze powinien mieć wartość ujemną, co stanie się zrozumiałe później).
- Negatywny (N) to N = 2 x Wektor Osi Ubocznej, czyli N = 2 x 5 = 10 (ten zawsze powinien być dodatni)
- Czynnik Decyzyjny (D) liczymy jako Negatywny (N) - Wektor Osi Wiodącej, a więc D = 10 - 11 = -1*
- Wyznaczamy wartość początkową X i Y, które zawsze są równe odpowiednio P1.X i P1.Y.
- Po zakończeniu tych przygotowań możemy przejść do właściwej pętli wyznaczającej kolejne współrzędne pikseli wchodzących w skład linii. Pętla powinna mieć długość równą długości osi wiodącej. U nas będzie to więc od 0 do 10 (albo jak kto woli, od 1 do 11).
Co robimy w pętli?
A). Ruch na osi wiodącej wykonujemy ZAWSZE. U nas jest to X, więc przy każdym powtórzeniu X = X + KierunekRuchuX, czyli X = X + 1.
B). Ruch na osi ubocznej wykonujemy tylko wtedy, gdy wartość czynnika decyzyjnego (D) jest większa niż 0 (D > 0). Jeżeli tak, wykonujemy 2 czynności:
- Y = Y + KierunekRuchuY, czyli Y = Y + 1.
- Modyfikujemy wartość czynnika decyzyjnego (D) przy pomocy obliczonej wcześniej wartości Pozytywny (P), czyli D = D + P. Czynnik decyzyjny (D) jest pozytywny, więc dodajemy do niego Pozytywny modyfikator (teraz to ma sens, prawda? ;s).*
C). Jeżeli natomiast czynnik decyzyjny jest ujemny lub równy 0 (D <= 0), wtedy wykonujemy tylko jedną czynność, dodajemy do niego Negatywny modyfikator (N), a więc D = D + N.
Ot i cały algorytm, prześledźmy może kawałek na naszym przykładzie:
V = [11, 5]
P = -12
N = 10
D = -1
X = 1 (wiodąca)
Y = 1 (uboczna)
Krok 1:
X = X + 1 = 2 (bo zwiększamy zawsze)
Y = 1 (D < 0, więc nie zwiększamy)
D = D + N = 9 (modyfikujemy czynnik decyzyjny)
Krok 2:
X = 3
Y = 2 (bo D > 0)
D = D + P = -3
Krok 3:
X = 4
Y = 2
D = 7
itd.
Teraz mój właściwy problem. Jak pisałem we wstępie, chcę wykorzystać ten algorytm do wyznaczania boków trójkąta. Rzecz w tym, że przy rysowaniu poprzez scan line, muszę oś Y traktować zawsze jako wiodącą, bo pętla przy każdym powtórzeniu MUSI przeskakiwać o jedną linię do dołu (Y = Y + 1). Generalna zasada jest taka, że na każdy ruch na dłuższej osi przypada jakaś szczątkowa część ruchu na osi krótszej (a więc jeżeli X = X + 1, to Y = np. Y + 0.2). Tyle, że rasteryzacja musi być wykonywana do pełnych pikseli, więc te szczątkowe ruchy, mniejsze niż 0.5, się pomija (przez zaokrąglenie jak w DDA, albo przez kumulowanie tych szczątków w czynniku decyzyjnym, jak u Bresenhama). Jeżeli więc każdy ruch szczątkowy zwielokrotnię jakąś tam ilość razy (by dojść do wartości umożliwiającej wykonanie jednego pełnego ruchu), to taką samą operację muszę wykonać na drugiej osi, czyli X.
Powiedzmy, że ruch szczątkowy na Y wynosi 0.2, na X oczywiście pełne +1. Krok pierwszy, X zwiększamy o 1, Y wynosi 0.2 więc zostawiamy w spokoju. Krok drugi, X znowu zwiększamy o 1, Y to 0.4, więc nadal nie robimy z nim nic. Krok trzeci, X rośnie o 1, Y to już 0.6, więc zwiększamy o 1. Czyli widać wyraźnie, że na każdy 1 ruch na Y, wykonać trzeba 3 ruchy na X. Rozumiejąc tę zależność, jestem w stanie wyliczyć o ile powinno przeskoczyć X, przy każdym ruchu wynoszącym Y + 1.
Niby logiczne, ale nie mam pojęcia jak to zrobić bez dzielenia i wykorzystania pętli while lub repeat. Próbowałem to zrobić z nimi, ale wtedy szybkość spada na tyle, że algorytm zrównuje się z DDA (czyli najbardziej prymitywną i wolną implementacją). Ktoś ma pomysł jak to zrobić inaczej?
Przepraszam za długi post, ale wolałem nie ryzykować, że ktoś potencjalnie pomocny się zniechęci nie znając działania algorytmu Bresenhama.