Zainteresowanie ray tracingiem pojawilo sie wiele lat temu, kiedy poznalem program do ray tracingu
o nazwie POV-Ray. Dlugo jednak nie mialem odpowiedniej wiedzy, aby taki program napisac.
Na szczescie sytuacja sie zmienila i pomyslalem, ze ciekawie bedzie napisac ray-tracer w funkcyjnym jezyku.
Czym jest ray tracing mozna sie z grubsza dowiedziec tutaj: http://pl.wikipedia.org/wiki/Ray_Tracing
O programie, na którym bede sie wzorowal mozna poczytac tutaj: http://pl.wikipedia.org/wiki/POV-Ray
A oto, co mozna stworzyc przy pomocy metody sledzenia promieni: http://hof.povray.org/
Postep projektu:
21 listopada 2006
Zdefiniowalem typy dla elementów sceny, czyli: promien, zródlo swiatla, material powierzchni,
ksztalty (narazie tylko proste bryly typu sfera, walec, stozek, etc. gdyz latwo jest wyznaczyc
wektor normalny do powierzchni w punkcie oraz przeciecie z promieniem, ale w planach mam tez platy
Beziera i powierzchnie B-sklejane). Jest tez funkcja rozstrzygajaca przeciecie promienia ze
sfera. Obecnie pracuje nad jezykiem opisu sceny i jego parserem.
23 listopada 2006
Ulozylem wstepna wersje jezyka opisu sceny, ktorego skladnia jest nastepujaca:
camera <loc[x, y, z], l_at[x, y, z]>
light <loc[x, y, z], clr[r, g, b]>
object <’shape_def’, mtr[r, g, b, s]>
// 'shape_def' is either of:
// sphere <ctr[x, y, z], rd[v]>
// tours <ctr[x, y, z], rd1[v], rd2[v]>
// con <ctr[x, y, z], rd[v], nd[v]>
#
legenda:
loc - location
l_at - look_at
ctr - center
rd - radius
nd - node
mtr - material
clr - color
r - red
g - green
b - blue
s - shininess
// - komentarz
# - znacznik konca kodu
Tych kilka prostych konstrukcji skladniowych wystarczy, aby zdefiniowac polozenie kamery wraz
z kierunkiem obserwacji, zrodel swiatla wraz z kolorem oraz kilku prostych obiektow geometrycznych,
w ktorych material jest zdefiniowany jako kolor + polysk.
Pozostaje napisac lekser + parser. Ostatnim razem gdy pisalem lekser, napisalem go (w C#) jako
obiekt, który podczas wywolania metody NextToken() tworzyl na zadanie parsera token przetwarzajac
kolejny fragment pliku, po czym zatrzymywal sie, az do nastepnego wywolania NextToken(). Tym razem
jednak postanowilem reprezentowac lekser jako strumien w postaci:
type token_stream = EOS | TStream of token * (unit → token_stream) ;;
A wiec jako pare (aktualny_token, ogon_strumienia). Pomyslalem ze specyfikacja bedzie przez to czytelniejsza, a samo korzystanie z leksera w parserze
wygodniejsze.
26 grudnia 2006
Powstal interpreter jezyka opisu sceny, ktory zwraca liste obiektow sceny oraz wspolrzedne
bryly szesciennej zawierajacej wszystkie obiekty. Jest tez funkcja tworzaca kd-drzewo
czyli osemkowy podzial przestrzeni, zawartej w powyzszej bryle szesciennej. Bazowa bryla
dzielona jest na 8 bryl, ktore rekurencyjnie takze dzielone sa na 8 bryl. Glebokosc rekursji
ustalana jest na podstawie ilosci obiektow i ich rozproszenia. Zmiejszy to znacznie koszt obliczen,
gdyz dla danego promienia sprawdza sie wtedy przez ktore bryly przelatuje, a nastepnie szuka sie zdarzen
(odbicia, zalamania itd.) tylko z obiektami znajdujacymi sie w brylach do ktorych promien wlatuje.
Plaszczyzny podzialu bryl sa usrednianymi plaszczyznami sasiadujacymi (byc moze da sie to zrobic lepiej :) ).
Jest tez funkcja, ktora jako argument pobiera promien (reprezentowany w postaci punktu bedacego jego zrodlem,
oraz wektora wyznaczajacego kierunek ruchu) oraz kd-drzewo i zwraca liste zdarzen.
W ogolnym przypadku rozstrzyganie przeciec bryl czy zawierania nie jest takie trywialne,
wiec ogranicze sie do kuli, trojkata, kola, prostokata, tym bardziej ze planuje zrobic
elementy CSG (constructive solid geometry) czyli tworzenie ksztaltow na bazie prymitwow geometrycznych
przy pomocy operacji boolowskich.
Teraz trwaja prace nad strumieniem promieni i implementacja modelu Phonga (modelowanie odbicia swiatla),
czyli to co potrzebne, aby moc cokolwiek zobaczyc ;-)
Sczegoly techniczne - reprezentacja kd-drzewa:
type bounding_box = {
near : float;
far : float;
left : float;
right : float;
bottom : float;
top : float;
}
type kd_tree =
KD_Empty
| KD_Leaf of shape list * bounding_box
| KD_Branch of kd_tree * kd_tree * kd_tree * kd_tree * kd_tree * kd_tree * kd_tree * kd_tree * bounding_box
(* t1 t2 t3 t4 b1 b2 b3 b4 *)
;;
