Aby stworzyć 3D-engine musimy się nauczyć rysować na ekranie trójwymiarowe bryły. Każda taka bryła, niezależnie od kształtu składać się będzie z płaskich ścian. Każda ściana jest wielokątem. Każdy wielokąt można podzielić na trójkąty. Dlatego bardzo ważne jest, aby mieć gotową procedurę potrafiącą wypełnić trójkąt. W tym artykule dowiesz się jedynie jak wypełnić go jednym kolorem - ale jego zrozumienie jest potrzebne do zrozumienia dalszych lekcji na temat cieniowania, teksturowania, etc...

Jak zapewne wiecie, każdy trójkąt ma dokładnie trzy wierzchołki:




Do naszych celów wierzchołki powinne być posortowane. Ten najwyższy powinien być pierwszy, a najniższy - trzeci. Lepiej od razu podam jak posortować wierzchołki, żeby ktoś do tego quicksorta nie zaciągał ;) a także dlatego, że już w kilku miejscach widziałem sortowanie nieoptymalne (np. w pliku fatmap.txt).



(zwróć uwagę na wcięcia, ostatni warunek sprawdzamy tylko wtedy, gdy warunek drugi jest prawdziwy)

Po posortowaniu wierzchołków sytuacja wygląda tak:



Trójkąt rysować będziemy liniami poziomymi. Zaczynamy od góry i posuwamy się w dół. Rysowanie składa się z dwóch części - najpierw linie od wierzchołka 1 do 2 (zielone pole), potem linie od wierzchołka 2 do 3 (żółte pole).



Narysowanie każdej linii polega na pokolorowaniu pixeli od pewnego punktu położonego na lewej krawędzi, do punktu położonego na prawej krawędzi. Dla każdego Y będziemy mieli wyliczone XL (lewy X) i XR (prawy X). Niektórzy wyliczają je na początku, jeszcze przed rysowaniem, nie ma to jednak sensu. Ja ustalam wartości XL i XR na początku i zmieniam je w każdej linii po narysowaniu poprzedniej.



Linię więc narysujemy tak:

dla każdego x od XL do XR 

    pokoloruj_pixel(x,y)

W typowym trójkącie (nie w każdym! jest jeden wyjątek o którym trzeba pamiętać) pierwsza linia ma długość zero, ponieważ zarówno XL jak i XR są równe współrzędnej poziomej najwyższego wierzchołka - czyli X1. Potem w każdej linii lewy i prawy X zmieniają się o pewną wartość. Nazwijmy te wartości - delta_xl dla lewego X i delta_xr dla prawego X.



Te wzory trzeba zrozumieć. Delta_lx mówi nam o ile zmienia się lewy x w każdej linii. Oblicza się więc ją dzieląc różnicę X na obu końcach lewej krawędzi przez ilość linii do narysowania.

Zwróć uwagę, że powyższe wzory prawdziwe są tylko wtedy, gdy drugi wierzchołek trójkąta znajduje się po lewej stronie. Trzeba to sprawdzić i jeżeli okaże się, że jest po prawej - delty zamieniają się miejscami.

Po narysowaniu y2-y1 linii (czyli pierwszej części trójkąta), jedna z delt się zmieni. W tym przypadku będzie to lewa delta.



Jeżeli wierzchołek numer 2 był po prawej stronie - zmieni się prawa delta.

Po narysowaniu drugiej części nie zostaje już nic - bo cały trójkąt jest narysowany :-) Cały algorytm wygląda więc w przybliżeniu tak:
posortuj_wierzchołki_według_y



Napisanie dobrze całego algorytmu nie jest takie proste. Mi zajmowało zawsze cały wieczór (pisałem w czystym assemblerze). Trzeba bowiem pamiętać o wielu przypadkach, które trzeba uwzględnić. Co będzie np. gdy nie będzie dolnej lub górnej części. Wtedy np. y2-y1 będzie równe 0. I jeżeli tego nie sprawdzisz - dostaniesz dzielenie przez 0.

Najlepszy sposób na sprawdzenie czy algorytm działa w każdym przypadku, to napisanie obracającego się trójkącika. Bierzesz trzy punkty na ekranie i co klatkę obracasz je wokół środka ekranu, a następnie rysujesz trójkąt, którego są wierzchołkami.

No cóż... zostaje życzyć ci powodzenia :-) Jeżeli uda ci się napisać dobrze wypełnianie trójkąta - możesz zaczynać swoją przygodę w trójwymiarowym świecie. Już nie długo będziesz mógł tworzyć w nim naprawdę fascynujące rzeczy... powyższy materiał - bez tego może być trudniej w dalszych lekcjach.