Rzucanie promieni… No prawie

Dzisiaj nietypowo, bo opis tylko jednej nowej rzeczy, która pojawiła się ostatnio w frameworku, ale skoro sam ją zaimplementowałem (o dziwo), to czuję się zobowiązany co nieco o tym napisać. Tym razem postanowiłem zająć się prototypem (bo pełnoprawnym odzwierciedleniem mechanizmu tego nie nazwę) techniki określanej z angielska ray casting, a bardziej swojsko – rzucaniem promieni. Sam pomysł został całkiem nieźle napisany na Wikipedii, ale promień, który napisałem nie ma pierwotnie za zadanie odpowiadać za generowanie scen 3D (chociaż nie wiadomo, co mi później palnie w głowę).

Generalnie, idea wykorzystania promienia do rzucania go po scenie i patrzenia, czy w coś trafi bezpośrednio wiąże się z moimi poprzednimi próbami stworzenia systemu kolizji. Jeśli ktoś to czytał (będę z tej notki też tutaj troszkę korzystał), napotkałem ogromne trudności z rozwiązaniem problemu kolizji w bardziej ludzki sposób, więc chwytałem się dość dziwnych, choć pokrewnych, metod. Wtedy jeszcze nie bardzo znałem określenia promienia w grafice, gdyż pewnie implementacja byłaby trwalsza i mniej błędogenna niż jest teraz. Ciekawe jednak, iż wtedy próbowałem podobnych metod – czegoś jednak zabrakło, aby to wszystko działało jak należy (prawdopodobnie cierpliwości na debugowanie). Wróćmy jednak na właściwe tory.

Promień w założeniu ma być wykorzystywany do testowania, czy znajdujemy się blisko jakieś ściany czy obiektu (aczkolwiek algorytm troszkę faworyzuje ściany i obiekty będące czworokątami. Właściwie, to nawet nie tylko troszkę) i czy trafiamy w niego na przykład kursorem, co może powodować rozmaite reakcje programu (przykładowo ściana z sufitem się zawalą. Gra również). Cała idea bazuje na pobraniu punktu początkowego promienia, okreslenia kierunku, w którym będzie on rzucany i zasięgu trafienia, jaki nas interesuje (gdyż zwykle twórca gry nie będzie chciał, aby gracze otwierali skrzynię z drugiego końca pokoju. Zwłaszcza, jak umieścił w niej pułapkę. Śmiertelną). Potrzebne też są oczywiście współrzędne wierzchołków ściany, którą testujemy w zestawieniu z promieniem – przyznaję, iż nie jest to profesjonalne rozwiązanie, ale jakąś tam funkcjonalność zapewnia.

Posiadamy zatem takie oto dane:

• L(r) – zasięg trafiania promienia
• P1 = (x1, y1, z1) – punkt, z którego rzucamy promień
• P2 = (x2, y2, z2) – punkt, który aktualnie wskazujemy
• V1, V2, V3, V4 – wektory wskazujące współrzędne [x, y, z]wierzchołków badanego quada, poczynając od lewego dolnego i kierując się przeciwnie do wskazówek zegara
• OB, hemoglobina i takie tam

Dużo łatwiej będzie przedstawić algorytm w punktach. Będę też czasami używał pseudokodu, a czasami boskich i nadobnych screenów z Worda. Zastosuję też coś, co anglojęzyczni nazywają swizzling (chyba), czyli notację taką, że odwołanie się do współrzędne y wektora v oznaczę jako v.y. Zostaliście ostrzeżeni.

1. Na początku musimy sobie zdać sprawę, czego tak naprawdę potrzebujemy – równania prostej przechodzącej przez punkty P1 i P2, równania płaszczyzny na której leży quad, a następnie współrzędnych punktu przecięcia prostej z płaszczyzną. Całą teorię zaczęrpnąłem z krótkiego opracowania Znane równania prostej na płaszczyźnie i w przestrzeni autorstwa Elżbiety Szumińskiej oraz książki Geometria analityczna w zadaniach autorstwa Edwarda Kąckiego, Danuty Sadowskiej i Lucjana Siewierskiego.

2. Zanim jednak do tego podejdziemy, proponuję najpierw z wektorów wierzchołkowych wyciągnąć minimalne i maksymalne wartości dla x, y oraz z. Na tym etapie jeszcze to nie jest konieczne, ale będzie znacznie bardziej czytelne, jeśli zrobimy to teraz, a nie będziemy potem się już zastanawiali “których wektorów użyć i do czego” (a na dodatek “jak ja się do cholery nazywam”).

   1: xmin = min(v1.x, v2.x, v3.x, v4.x)

   2: xmax = max(v1.x, v2.x, v3.x, v4.x)

   3:  

   4: ymin = min(v1.y, v2.y, v3.y, v4.y)

   5: ymax = max(v1.y, v2.y, v3.y, v4.y)

   6:  

   7: zmin = min(v1.z, v2.z, v3.z, v4.z)

   8: zmax = max(v1.z, v2.z, v3.z, v4.z)

Te wartości tworzą taką “bryłkę” okresloną granicami, którymi właśnie są współrzędne minimalne i maksymalne.

3. Kolejna rzecz, którą wypada zrobić, to sprawdzić, czy w ogóle nam się opłaca wykonywać algorytm. Innymi słowy – czy ściana w ogóle jest w zasięgu promienia. Tutaj można przyjąć dowolne warunki, które musi spełnić quad. Ja przyjąłem, że wystarczy, gdy którykolwiek wierzchołek znajduje się w zasięgu. Uzasadnienie tego jest takie, że dla gigantycznych quadów łatwiej spełnić taki warunek, aniżeli dla wyliczenia środka czworokąta i długości P1 do środka. Gigantyczne quady się cieszą, my również, więc policzmy te długości. W tym celu tworzymy tymczasowe wektory prowadzące od punktu P1 do wierzchołków V1, V2, V3 i V4.

   1: vec_1 = [v1.x - p1.x, v1.y - p1.y, v1.z - p1.z]

   2: vec_2 = [v2.x - p1.x, v2.y - p1.y, v2.z - p1.z]

   3: vec_3 = [v3.x - p1.x, v3.y - p1.y, v3.z - p1.z]

   4: vec_4 = [v4.x - p1.x, v4.y - p1.y, v4.z - p1.z]

Jak powszechnie wiadomo, długość wektora wynika z następującego wzoru.

Czyli po prostu jest to pierwiastek z sumy kwadratów współrzędnych wektora. Zatem należy sprawdzić, czy którykolwiek wektor ma długość mniejszą od promienia promienia. Jeśli żaden, to algorytm mówi “asta la (Windows) vista” i kończy swoje działanie z wartością fałszu.

   1: Jeżeli (L(v1) > L(r) i

   2:         L(v2) > L(r) i

   3:         L(v3) > L(r) i

   4:         L(v4) > L(r))

   5:  

   6: to kończ algorytm

   7:              

4. Jakimś cudem okazało się jednak, że promień znajduje się w zasięgu ściany. Po przeklnięciu pod nosem, iż musimy dalej pisać, musimy utworzyć płaszczyznę, na której znajduje się quad, a następnie wyliczyć jej równanie. Właśnie o tym zagadnieniu pisałem przy okazji systemu kolizji, a nie chcę się powtarzać (w skrócie, chodzi o stworzenie wektorów V1V2 oraz V1V4, obliczenie ich iloczynu wektorowego, co daje nam wektor normalny, a współrzędne tegoż to współczynniki A, B i C płaszczyzny, natomiast D obliczamy podstawiając jakikolwiek punkt należący do płaszczyzny). Płaszczyznę oznaczymy sobie jako S.

   1: // utworzenie wektorów

   2: v1v2 = [v2.x - v1.x, v2.y - v1.y, v2.z - v1.z]

   3: v1v4 = [v4.x - v1.x, v4.y - v1.y, v4.z - v1.z]

   4:  

   5: // ich iloczyn wektorowy daje wektor normalny

   6: n.x = v1v2.y * v1v4.z - v1v2.z * v1v4.y

   7: n.y = v1v2.z * v1v4.x - v1v2.x * v1v4.z

   8: n.z = v1v2.x * v1v4.y - v1v2.y * v1v4.x

   9:  

  10: // współczynniki równania płaszczyzny (Ax+By+Cz+D=0)

  11: s.a = n.x

  12: s.b = n.y

  13: s.c = n.z

  14: s.d = -(s.a * v1.x + s.b * v1.y + s.c * v1.z)

5. Kolejnych krokiem jest obliczenie współrzędnych wektora kierunkowego promienia. Praktycznie rzecz biorąc, ten etap moglibyśmy pominąć, ale przechodzimy go z jednego prozaicznego powodu – czytelniejszy zapis w późniejszych etapach. Jedną z form równania prostej w przestrzeni przechodzącej przez dwa punty jest taki wzór (dla punktów P1 i P2).

Dlaczego zatem mamy ciągle przepisywać różnice z mianowników, jak można to przedstawić w formie wektora (ale namieszałem).

   1: dir = [p2.x - p1.x, p2.y - p1.y, p2.z - p1.z]

6. Nastąpi teraz preludium do kulminacyjnego momentu – obliczenie współrzędnych punktu będącego przecięciem prostej i płaszczyzny (werble). Załóżmy, że będzie to punkt A = (x, y, z). Zależność pomiędzy tymi współrzędnymi a równaniem płaszczyzny można zapisać parametrycznie za pomocą zmiennej t.

Nic zatem nie stoi na przeszkodzie, aby x, y oraz z podstawić do równania płaszczyzny S w celu obliczenia parametru t. Po przekształceniach uzyskujemy taki wzór.

Nie pytajcie mnie, dlaczego lubię wyprowadzać takie wzory. Tak czy inaczej, z łatwością możemy teraz podstawić t do poprzednich równań i wyliczyć współrzędne punktu A. Tadaam – udało nam się znaleźć punkt przecięcia prostej i płaszczyzny.

7. Pozostaje teraz sprawdzenie, czy punkt A leży nie dość, iż na płaszczyźnie, to jeszcze w konkretnych granicach naszej ściany. Właśnie tutaj użyjemy minimalnych i maksymalnych współrzędnych, które obliczyliśmy onegdaj w drugim punkcie. Sprawdzenie tego jest już dosyć proste – badamy po kolei każdą współrzędną i jeśli choć jedna nie spełnia warunku bycia w przedziale <min, max>, to od razu algorytm zwraca fałsz. Jeśli jednak współrzędne punktu A przejdą wszystkie trzy testy – zwracamy prawdę i programujemy określone zdarzenie (czyli powracamy do śmiertelnej pułapki w skrzyni).

   1: Jeżeli (x < xmin lub x > xmax) zwracamy fałsz

   2: Jeżeli (y < ymin lub y > ymax) zwracamy fałsz

   3: Jeżeli (z < zmin lub z > zmax) zwracamy fałsz

   4:  

   5: Jeżeli dotarliśmy tutaj - zwracamy prawdę

Tak to się mniej więcej przedstawia. Nie wiem, czy ten algorytm zasługuje na miano bycia pełnoprawnym raycasterem, ale w moim frameworku na razie wystarczy. Tak naprawdę, matematyka tutaj użyta nie jest specjalnie trudna. Rozumiem jednak ludzi (sam jestem taką osobą), którzy mają problemy z tym, czego nie mieli w szkole czy na studiach i muszą szperać po książkach samodzielnie – a o ile mi wiadomo, geometrii analitycznej w trójwymiarze nie ma w programie edukacji (nie wiem jeszcze jak na studiach – w liceum jest tylko dwuwymiar).

Jeśli komuś pomogłem tą notką – jestem niezmiernie ukontentowany. Zapraszam do komentowania i zgłaszania swoich ewentualnych wątpliwości.

Pozdrawiam i dziękuję – SceNtriC.