Piszę raytracera 3D jako osobisty projekt edukacyjny (Enlight) i natknąłem się na interesujący problem związany z wykonaniem testów przecięć między promieniem a sceną obiektów.Struktura danych/podejście do efektywnego raytracingu
Sytuacja jest:
- Mam szereg prymitywów, że promienie mogą się przecinać z (kulki, pudełka, samoloty, etc.) i ich grup. Łącznie nazywam te obiekty sceny.
- Chcę być w stanie prymitywów obiektów sceny z dowolnymi transformacjami afinicznymi, owijając je w obiekt
Transform(co ważne, umożliwi to użycie wielu wystąpień tego samego prymitywu w różnych położeniach w scenie, ponieważ prymitywy są niezmienne) - obiekty Scene mogą być przechowywane w drzewo bvh (tj robię podział przestrzenny)
- moich testów przecięcia pracować z
Rayobiektów, które reprezentują segment ray częściowe (start wektor, znormalizowany wektor kierunku, start dystans , odległość końcowa)
Problem polega na tym, że kiedy promień uderza w ramkę ograniczającą obiektu Transform, wygląda na to, że jedynym sposobem na wykonanie testu przecięcia z transformowanymi prymitywami zawartymi w nim jest przekształcenie Ray w przekształconą współrzędną. Jest to dość łatwe, ale jeśli promień nie trafi żadnych przekształconych obiektów, muszę wrócić do oryginalnego Ray, aby kontynuować śledzenie. Ponieważ transformacje mogą być zagnieżdżone, oznacza to, że muszę utrzymywać cały stos Ray s dla każdego śledzonego przecięcia.
Jest to oczywiście wewnętrzna pętla całej aplikacji i główne wąskie gardło wydajności. Będzie się to nazywać miliony razy na sekundę, więc chcę zminimalizować złożoność/uniknąć niepotrzebnego przydzielania pamięci.
Czy istnieje sprytny sposób na uniknięcie konieczności przydzielania nowego Ray s/utrzymania stosu Ray?
Czy jest na to jeszcze bardziej sprytny sposób?
Nie jestem pewien, czy byłby szybszy niż alokacja pamięci, ale można spróbować wymyślić skuteczny algorytm odwrócenia transformacji, a następnie pomnożyć bieżący promień z transformacją odwrotną, gdy wycofa się z bieżącego obiektu. –
@Ivan - ciekawy pomysł. Wydaje mi się, że może to być nieznacznie szybsze, chociaż martwiłbym się wtedy o kompilację liczbowych problemów precyzji ..... – mikera
Można wstępnie obliczać i buforować transformację i odwrotną transformację (tj. Obiekt macierzowy) dla każdego obiektu (jak również obiekty w grupie), które zostaną przekształcone w ramkę globalną i z niej. W ten sposób nie potrzebujesz zagnieżdżonej hierarchii, ponieważ możesz wykonać test trafień bezpośrednio na każdym obiekcie. To znaczy. przekształć promień w ramę obiektu, a następnie przekształć go, aby uzyskać punkt trafienia w globalnej ramce. Robię to w moim znaczniku: http://github.com/danieljfarrell/pvtrace –