Z zamiarem napisania RayCastera nosiłem się od dobrych kilku miesięcy. Po jednym nieudanym podejściu w końcu dotarłem do końca a teraz moge podzielić się rezultatami. Najważniejsze aby zacząc od tego co to tak naprawde RayCaster?
Wiele lat temu komputery nie byly na tyle silne (czyt. szybkie), aby były w stanie sobie poradzić z obliczaniem skomplikowanej sceny 3D jak ma to miejsce teraz. W tym celu stosowało się pewne triki optymalizacyjne, aby uzyskać chociaż w przybliżeniu żądany efekt. Jednym z takich trików jest właśnie RayCasting – w dosłownym tłumaczeniu rzucanie promieni. Aby jednak wytłumaczyć tę optymalizację wpierw przejdę wpierw do wytłumaczenia jak powstaje scena 3D. Najprościej jest to sobie uzmysłowić rysując na kartce siebie jako obserwatora, przedmiotu stojącego przed nami (trójwymiarowego) oraz ekranu komputera pomiędzy (ten ekran znajduje się w trójwymiarowej przestrzeni, jednak jest ustawiony do nas prostopadle). Następnie rysujemy linie od każdego wierzchołka obiektu obserwowanego do nas. Miejsce przecięcia sie tej linii z ekranem komputera wyznacza dwu wymiarowy punkt na naszym ekranie (czyli dokonujemy przekształcenia z trójwymiarowej przestrzeni w dwuwymiarową reprezentację). Wszystko to robimy po to, że docelowo musimy narysować punkt na naszym dwuwymiarowym ekranie (podając X oraz Y). Mam nadzieje ze lepiej zobrazuje to rysunek:
Teraz powróćmy do RayCastingu. W teorii wygląda to dość prosto, jednak jak przyjrzymy sie aparatowi matematycznemu zrozumiemy, że jednak nie jest to już takie proste. Mamy do wyboru dwie opcje – albo z każdego wierzchołka poprowadzić prostą do obserwatora i następnie przewidzieć jakie płaszczyzny mogą być widoczne, albo od obserwatora starać się wysyłać promienie na każdy punkt obrazu i sprawdzić na co napotkają. Jak łatwo sobie wyobrazić pierwsza metoda może dać tylko zadowalające rezultaty przy małej ilości wierzchołków. W praktyce częściej korzysta się z drugiej opcji – wysyłamy “promienie” od obserwatora w nieznane i patrzymy na co napotykają. Jak łatwo zauważyć, aby stworzyć scenę 320×200 potrzebujemy wysłać tych promieni około 64000 linii na jedną scenę. Komputery kiedyś nie radziły sobie w czasie rzeczywistym z takimi obliczeniami dlatego wprowadzono technike RayCasting głównie w grach komputerowych (pierwsze FPP, Wolfenstein oraz Doom). Polega ona na prostym uproszczeniu, że zamiast liczyć całą scenę złożoną z pojedyńczych punktów, zakładamy że wszystkie obiekty w przestrzeni mają stałą wysokość i patrzymy tylko na przecięcie rzucanych promieni na lini horyzontu. Na podstawie odległości przecięcia tego promienia z najbliższym obiektem możemy określić jego wielkość na ekranie (ponieważ ustaliliśmy stała wysokość). Zwróćcie uwage na film z gry Wolfenstein gdzie wysokość otoczenia jest zawsze ta sama: Wolfenstein.
To uproszenie pozwala zmniejszyć ilość obliczeń z 64000 na jedną scenę (dla obrazu 320×200) do 320. Ta ogromna optymalizacja pozwoliła na wprowadzenie gier takich jak wolfenstein czy doom na starych komputerach.
Kolejnym problemem do rozwiązania jest jak odnależć, czy nasz rzucany promień trafia na jakiś obiekt – np. ściane. Nasze obiekty najprzyjemniej byłoby określać punktami gdzie się zaczynają i kończą – a co jeśli taki promień trafi pomiędzy takie punkty? Kolejne uproszczenie zastosowane w grze Wolfenstein wykorzystamy również przy pisaniu naszego RayCastera. Mianowicie możemy sobie uprościć życie i określić że ściany rozchodzą się tylko prostopadle i są tej samej wielkości. Ułatwia nam to nie tylko aparat matematyczny, ale też i zapis mapy który teraz może być ciągiem wartości:
1111111
1001001
1001001
1100011
1001001
1111111
Które czytamy jako 1 – ściana, 0 – brak ściany. Oczywiście nasze ściany w przestrzeni nie są punktami tylko sześcianami, dlatego z takiej mapy musimy ją w naszej aplikacji przekształcić w klocki (np. 50x50x50). Przy takich uproszczeniach każdy rzucany promień musimy sprawdzać czy sie nie przeciął z jakimś obiektem tylko w kolejnych 50-krotnościach x-ów oraz y-ów. To pokrętne tłumaczenie mam nadzieje, że rozjaśni rysunek:
Kiedy już odnajdziemy przecięcie z najbliższą ścianą, możemy łatwo policzyć odległość pomiędzy punktami. Ta odległość wyznacza nam wysokość ściany, którą chcielibyśmy narysować na ekranie komputera (im dalej tym wysokość naszego “słupka” jest mniejsza). Ostatni problem z tą wartością jest taki, że wprowadza ona pewną sferyczność – tzn. obraz wydaje się jakby opisany na kuli. Ten efekt można łatwo zaobserwować na przykładach dostepnych na stronie mozilli. Aby to zrozumieć musimy znów wrócić do idei rzucania promieni. Jak pamiętamy jest tam obserwator, obiekt oraz ekran naszego komputera – jednak kiedy liczymy tylko odległość od przecięć tak naprawde nie uwzględniamy tego że im kąt rzucania promieni bardziej oddala się od środka ekranu – tym ekran znajduje się troszkę dalej od obserwatora. Ten efekt bardzo łatwo zniwelować jednym Cosinusem zależnym od kąta aktualnie przetwarzanego punktu.
Ostatecznie warto dodać teksturowanie – w zależności od miejsca padania na ścianę – pionowy pasek obrazu tekstury zostanie przeniesiony (po transformacji wielkości) na ekran naszego komputera.
To koniec części wyjaśniającej teoretyczne podstawy. W następnej części zajmiemy się implementacją krok po kroku.
[...] W poprzednim odcinku starałem się przybliżyć technikę RayCastingu, tym razem przejdziemy do implementacji. [...]