Odlewanie promieni - Ray casting
Odlewanie promieni jest podstawą metodologiczną trójwymiarowego modelowania bryłowego CAD/CAM i renderowania obrazu. Zasadniczo jest to to samo, co śledzenie promieni w grafice komputerowej, w którym wirtualne promienie światła są „rzucane” lub „śledzone” na swojej drodze od ogniska kamery przez każdy piksel w czujniku kamery, aby określić, co jest widoczne wzdłuż promienia w Scena 3D. Termin „Ray Casting” został wprowadzony przez Scotta Rotha podczas pracy w General Motors Research Labs w latach 1978-1980. Jego artykuł „Ray Casting for Modeling Solids” opisuje modelowane obiekty bryłowe przez łączenie prymitywnych brył, takich jak bloki i walce, przy użyciu sumy operatorów mnogości (+), przecięcia (&) i różnicy (-). Ogólna idea wykorzystania tych operatorów binarnych do modelowania bryłowego jest w dużej mierze zasługą grupy modelowania geometrycznego Voelckera i Requicha na Uniwersytecie Rochester. Zobacz Modelowanie bryłowe, aby zapoznać się z szerokim przeglądem metod modelowania bryłowego. Ten rysunek po prawej pokazuje połączenie w kształcie litery U wymodelowane z cylindrów i bloków w drzewie binarnym przy użyciu systemu ray casting Roth, około 1979 roku.
Przed rzutowaniem promieni (i śledzeniem promieni) algorytmy grafiki komputerowej rzutowały powierzchnie lub krawędzie (np. linie) ze świata trójwymiarowego na płaszczyznę obrazu, gdzie trzeba było zastosować logikę widoczności. Rzutowanie płaszczyzny świata na obraz jest trójwymiarową transformacją jednorodnego układu współrzędnych (inaczej: projekcja 3D , transformacja afiniczna lub transformacja rzutowa ( Homografia )). Renderowanie obrazu w ten sposób jest trudne do osiągnięcia przy usuwaniu ukrytych powierzchni/krawędzi. Ponadto sylwetki zakrzywionych powierzchni muszą być wyraźnie rozwiązane, podczas gdy jest to niejawny produkt uboczny rzutowania promieni, więc nie ma potrzeby jawnego rozwiązywania tego za każdym razem, gdy zmienia się widok.
Rzutowanie promieni znacznie uprościło renderowanie obrazów obiektów i scen trójwymiarowych, ponieważ linia przekształca się w linię. Tak więc, zamiast rzutować zakrzywione krawędzie i powierzchnie w scenie 3D na płaszczyznę obrazu 2D, przekształcone linie (promienie) są przecinane z obiektami w scenie. Jednorodna transformacja współrzędnych jest reprezentowana przez macierz 4x4. Technika matematyczna jest wspólna dla grafiki komputerowej i modelowania geometrycznego. Transformacja obejmuje obroty wokół trzech osi, niezależne skalowanie wzdłuż osi, translacje w 3D, a nawet pochylenie. Przekształcenia można łatwo łączyć za pomocą arytmetyki macierzowej. W przypadku użycia z macierzą 4x4, punkt jest reprezentowany przez [X, Y, Z, 1], a wektor kierunku jest reprezentowany przez [D x , D y , D z , 0]. (Czwarty termin dotyczy translacji i nie dotyczy wektorów kierunkowych).
Chociaż upraszczając matematykę, algorytm rzutowania promieni jest bardzo intensywny w przetwarzaniu komputerowym. Pixar ma duże farmy renderujące, budynki z tysiącami procesorów, aby tworzyć swoje animacje przy użyciu ray tracingu [inaczej „ray casting”] jako podstawowej techniki.
Pojęcie
Rzutowanie promieni jest najbardziej podstawowym z wielu algorytmów renderowania grafiki komputerowej , które wykorzystują geometryczny algorytm ray tracingu . Algorytmy renderowania oparte na ray tracingu działają w kolejności obrazu, aby renderować sceny trójwymiarowe do obrazów dwuwymiarowych. Promienie geometryczne są śledzone z oka obserwatora, aby pobrać próbkę światła ( promieniowania ) podróżującego w kierunku obserwatora z kierunku promienia. Szybkość i prostota rzucania promieni wynika z obliczania koloru światła bez rekursywnego śledzenia dodatkowych promieni, które próbkują promieniowanie padające na punkt, w który pada promień. Eliminuje to możliwość dokładnego renderowania odbić , załamań lub naturalnego zanikania cieni ; jednak wszystkie te elementy można do pewnego stopnia sfałszować, twórczo wykorzystując mapy tekstur lub inne metody. Wysoka prędkość obliczeń sprawiła, że ray casting stał się przydatną metodą renderowania we wczesnych grach wideo 3D w czasie rzeczywistym .
Ideą rzucania promieni jest śledzenie promieni z oka, jeden na piksel, i znalezienie najbliższego obiektu blokującego ścieżkę tego promienia – pomyśl o obrazie jako o drzwiach ekranowych, gdzie każdy kwadrat na ekranie jest pikselem. To jest obiekt, który oko widzi przez ten piksel. Wykorzystując właściwości materiału i efekt świateł w scenie, algorytm ten może określić zacienienie tego obiektu. Przyjmuje się upraszczające założenie, że jeśli powierzchnia jest skierowana w stronę światła, światło dotrze do tej powierzchni i nie zostanie zablokowane ani zacienione. Zacienienie powierzchni jest obliczane przy użyciu tradycyjnych modeli cieniowania grafiki komputerowej 3D. Jedną z ważnych zalet technologii Ray Casting w porównaniu ze starszymi algorytmami linii skanowania była jego zdolność do łatwego radzenia sobie z nieplanarnymi powierzchniami i bryłami, takimi jak stożki i kule . Jeśli powierzchnia matematyczna może być przecięta przez promień, może być renderowana za pomocą rzutowania promieni. Rozbudowane obiekty można tworzyć za pomocą technik modelowania bryłowego i łatwo renderować.
Z streszczenia do artykułu „Ray Casting for Modeling Solids”: Aby zwizualizować i przeanalizować modelowane bryły kompozytowe, wirtualne promienie światła są rzucane jako sondy. Dzięki swojej prostocie, ray casting jest niezawodny i rozszerzalny. Najtrudniejszym problemem matematycznym jest znalezienie punktów przecięcia linia-powierzchnia. Tak więc powierzchnie takie jak płaszczyzny, kwadryki, torusy, a prawdopodobnie nawet parametryczne łaty powierzchni mogą wiązać prymitywne bryły. Poruszono tutaj kwestie adekwatności i wydajności odlewania promieniowego. Największym wyzwaniem jest możliwość szybkiego generowania obrazów do interaktywnego modelowania.
Promienie świetlne i geometria kamery stanowią tutaj podstawę wszelkich rozumowań geometrycznych. Ten rysunek przedstawia model kamery otworkowej dla efektu perspektywy w przetwarzaniu obrazu oraz model kamery równoległej do analizy masy. Prosty model kamery otworkowej składa się z ogniska (lub punktu ocznego) i kwadratowej matrycy pikseli (lub ekranu). Proste promienie światła przechodzą przez macierz pikseli, aby połączyć ognisko ze sceną, jeden promień na piksel. Aby zacienić obrazy, mierzy się intensywność promieni i przechowuje je jako piksele. Powierzchnia odbijająca odpowiedzialna za wartość piksela przecina promień piksela.
Gdy ogniskowa, odległość między ogniskiem a ekranem, jest nieskończona, widok nazywany jest „równoległym”, ponieważ wszystkie promienie światła są równoległe do siebie, prostopadłe do ekranu. Chociaż widok perspektywiczny jest naturalny do robienia zdjęć, niektóre aplikacje wymagają promieni, które mogą być równomiernie rozłożone w przestrzeni.
Dla wygody modelowania typowy standardowy układ współrzędnych dla kamery ma ekran w płaszczyźnie XY, scenę w półprzestrzeni +Z i ognisko na osi -Z.
Promień to po prostu prosta linia w trójwymiarowej przestrzeni modelu kamery. Najlepiej zdefiniować go jako wektor kierunkowy w sparametryzowanej postaci jako punkt (X 0 , Y 0 , Z 0 ) i wektor kierunkowy (D x , D y , D z ). W tej formie punkty na linii są uporządkowane i dostępne za pomocą jednego parametru t. Dla każdej wartości t zdefiniowany jest odpowiedni punkt (X, Y, Z) na linii:
X = X0 + t · Dx Y = Y0 + t · Dy Z = Z0 + t · Dz
Jeżeli wektor jest znormalizowany, to parametr t jest odległością wzdłuż linii. Wektor można łatwo znormalizować za pomocą następujących obliczeń:
Dist = √(Dx2 + Dy2 + Dz2) Dx = Dx / Dist Dy = Dy / Dist Dz = Dz / Dist
Biorąc pod uwagę geometryczne definicje obiektów, z których każdy jest ograniczony jedną lub większą liczbą powierzchni, wynik obliczenia przecięcia jednego promienia ze wszystkimi ograniczonymi powierzchniami na ekranie jest zdefiniowany przez dwie tablice,
Ray parameters: t[1], t[2], ..., t[n] Surface pointers: S[1], S[2], ..., S[n]
gdzie n to liczba przecięć powierzchni promienia. Uporządkowana lista parametrów promienia t [i] oznacza punkty wejścia-wyjścia. Promień wchodzi do bryły w punkcie t [1], wychodzi w punkcie t [2], wchodzi do bryły w punkcie t [3] itd. Punkt t [1] jest najbliżej kamery, a t [n] jest najdalszy. W połączeniu z parametrami promienia, wskaźniki powierzchni zawierają unikalny adres dla informacji o przecinanej powierzchni. Powierzchnia może mieć różne właściwości, takie jak kolor, odbicia, przezroczystość z/bez załamania, przezierność itp. Ciało stałe związane z powierzchnią może mieć własne właściwości fizyczne, takie jak gęstość. Może to być przydatne, na przykład, gdy obiekt składa się z zestawu różnych materiałów, a przedmiotem zainteresowania jest ogólny środek masy i momenty bezwładności.
Stosowanie informacji
Trzy algorytmy wykorzystujące rzutowanie promieni to tworzenie rysunków liniowych, cieniowanych obrazów oraz obliczanie objętości i innych właściwości fizycznych. Każdy algorytm, biorąc pod uwagę model kamery, rzuca jeden promień na piksel na ekranie. W przypadku obliczania objętości rozdzielczość ekranu pikselowego do użycia zależy od pożądanej dokładności rozwiązania. W przypadku rysunków liniowych i cieniowania obrazu rozdzielczość określa jakość obrazu.
RYSUNKI LINII . Aby narysować widoczne krawędzie bryły, wygeneruj jeden promień na piksel, przesuwając się z góry na dół, od lewej do prawej na ekranie. Oceń każdy promień w celu zidentyfikowania widocznej powierzchni S[1], pierwszego wskaźnika powierzchni na posortowanej liście przecięć promień-powierzchnia. Jeśli widoczna powierzchnia w lokalizacji piksela (X, Y) jest inna niż widoczna powierzchnia w pikselu (X-1, Y), wyświetl pionową linię o długości jednego piksela wyśrodkowaną w (X-½, Y). Podobnie, jeśli widoczna powierzchnia w (X, Y) jest inna niż widoczna powierzchnia w pikselu (X, Y-1), wówczas wyświetl linię poziomą o długości jednego piksela wyśrodkowaną w (X, Y-½). Wynikowy rysunek będzie składał się tylko z krawędzi poziomych i pionowych, wyglądających na postrzępione w rozdzielczościach kursu.
System ray casting Rotha generował obrazy obiektów stałych po prawej stronie. Do optymalizacji wykorzystano obudowy pudełkowe, dynamiczne ograniczenia i spójność. Dla każdego obrazu próbkowano ekran z gęstością około 100x100 (np. 10 000) promieni, a nowe krawędzie lokalizowano za pomocą wyszukiwania binarnego. Następnie po wszystkich krawędziach rzucano dodatkowe promienie w odstępach co jeden piksel po obu stronach krawędzi. Każde zdjęcie zostało narysowane na tubie Tektronix w rozdzielczości 780x780.
CIENIOWANE OBRAZY . Aby zrobić zacieniony obraz, ponownie rzucaj jeden promień na piksel na ekranie. Tym razem jednak użyj wskaźnika widocznej powierzchni S[1] na każdym pikselu, aby uzyskać dostęp do opisu powierzchni. Z tego oblicz normalną powierzchni w widocznym punkcie t [1]. Wartość piksela, możliwe do wyświetlenia natężenie światła, jest proporcjonalne do cosinusa kąta utworzonego przez normalną powierzchni i wektor źródła światła do powierzchni. Przetwarzanie w ten sposób wszystkich pikseli daje rastrowy obraz sceny.
Obliczanie objętości i momentów bezwładności . Objętość (i podobne właściwości) bryły ograniczonej zakrzywionymi powierzchniami można łatwo obliczyć metodą całkowania „aproksymujących sum”, przybliżając bryłę zestawem prostokątnych równoległościanów. Osiąga się to poprzez wykonanie „dogłębnego” zdjęcia bryły w widoku równoległym. Rzucanie promieni przez ekran na bryłę dzieli bryłę na elementy objętości. Dwa wymiary równoległościanów są stałe, określone przez dwuwymiarowy odstęp promieni na ekranie. Trzeci wymiar jest zmienny, zdefiniowany przez obliczony punkt wejścia-wyjścia. W szczególności, jeśli odległość pozioma i pionowa między promieniami na ekranie wynosi S, to objętość „wykrywana” przez każdy promień wynosi
S × S × (t[2]-t[1] + t[4]-t[3] + ∙∙∙ + t[n]-t[n-1]) / L
gdzie L jest zdefiniowane jako długość wektora kierunku. (Jeżeli jest już znormalizowany, to jest równe 1.)
L = √(Dx2 + Dy2 + Dz2)
Każdy ( t [ i ]- t [ i -1])/L jest długością segmentu promienia znajdującego się wewnątrz bryły.
Ten rysunek przedstawia równoległościany dla modelowanej bryły za pomocą odlewania promieniowego. Jest to zastosowanie modelu kamery z projekcją równoległą.
Klasyfikacja promienia wejścia-wyjścia
Ten rysunek przedstawia przykład operatorów binarnych w drzewie kompozycji przy użyciu + i –, gdzie oceniany jest pojedynczy promień.
Procedura rzutowania promieni rozpoczyna się na szczycie drzewa kompozycji brył, rekursywnie schodzi w dół, klasyfikuje promień względem brył pierwotnych, a następnie powraca w górę drzewa, łącząc klasyfikacje lewego i prawego poddrzewa.
Ten rysunek ilustruje połączenie klasyfikacji lewej i prawej dla wszystkich trzech operatorów binarnych.
Realistyczne cieniowane zdjęcia
Ray Casting to naturalne narzędzie do modelowania służące do tworzenia cieniowanych obrazów. System rzutowania promieni w skali szarości opracowany przez Scotta Rotha i Daniela Bassa w GM Research Labs wyprodukował obrazy na kolorowym wyświetlaczu rastrowym Ramtek około 1979 roku. Aby komponować obrazy, system zapewnił użytkownikowi następujące elementy sterujące:
View
• Viewing direction and position
• Focal length: width-angle perspective to parallel
• Zoom factor
Illumination
• Number of light sources
• Locations and intensities of lights
• Optionally shadow
• Intensities of ambient light and background
Surface Reflectance
• % reflected diffusely
• % reflected specularly
• % transmitted
Ten rysunek przedstawia scenę stołu z cieniami z dwóch punktowych źródeł światła.
Algorytmy cieniowania, które implementują wszystkie realistyczne efekty, są kosztowne obliczeniowo, ale stosunkowo proste. Na przykład poniższy rysunek przedstawia dodatkowe promienie, które można rzucić dla pojedynczego źródła światła.
Aby wyrenderować pojedynczy piksel w obrazie, algorytm rzuca promień rozpoczynający się w ognisku i określa, że przecina on półprzezroczysty prostokąt i błyszczące koło. Następnie należy rzucić dodatkowy promień, zaczynając od tego punktu w kierunku symetrycznie przeciwnym do normalnej powierzchni w punkcie przecięcia powierzchni promienia, aby określić, co jest widoczne w odbiciu lustrzanym. Ten promień przecina trójkąt, który jest nieprzezroczysty. Na koniec każdy punkt przecięcia powierzchni promienia jest testowany w celu określenia, czy znajduje się w cieniu. Promień „czujnika cienia” jest rzucany z punktu przecięcia powierzchni promienia do źródła światła, aby określić, czy jakakolwiek inna powierzchnia blokuje tę ścieżkę.
Turner Whitted nazywa promienie drugorzędne i dodatkowe „Recursive Ray Tracing”. [Wyrenderowanie pomieszczenia z lustrami byłoby kosztowne, więc ograniczenie liczby rekurencji jest rozsądne.] Odcień modelowane załamanie dla przezroczystości poprzez wygenerowanie promienia wtórnego z punktu widocznej powierzchni pod kątem określonym przez współczynnik załamania bryły. Promień wtórny jest następnie przetwarzany jako promień zwierciadlany. Aby zapoznać się ze wzorem załamania i przykładami obrazkowymi, zobacz artykuł Whitteda.
Obudowy i wydajność
Rzucanie promieni kwalifikuje się jako metoda brutalnej siły do rozwiązywania problemów. Minimalny algorytm jest prosty, szczególnie biorąc pod uwagę jego liczne zastosowania i łatwość użycia, ale aplikacje zazwyczaj rzucają wiele promieni. Aby wyrenderować pojedynczą klatkę filmu animowanego, można rzucić miliony promieni. Czas przetwarzania komputerowego wzrasta wraz z rozdzielczością ekranu i liczbą prymitywnych brył/powierzchni w kompozycji.
Dzięki zastosowaniu minimalnych ramek ograniczających wokół brył w drzewie kompozycji wyczerpujące wyszukiwanie przecięcia promień-bryła przypomina wydajne wyszukiwanie binarne. Algorytm brute force przeprowadza wyczerpujące poszukiwania, ponieważ zawsze odwiedza wszystkie węzły w drzewie — przekształca promień w lokalne układy współrzędnych prymitywów, testuje przecięcia powierzchni promieńa i łączy klasyfikację — nawet jeśli promień wyraźnie omija bryłę. W celu wykrycia „wyraźnego chybienia” szybszy algorytm wykorzystuje binarne drzewo kompozycji jako hierarchiczną reprezentację przestrzeni zajmowanej przez kompozycję bryłową. Ale wszystkie informacje o położeniu, kształcie i rozmiarze są przechowywane w liściach drzewa, gdzie znajdują się prymitywne bryły. Górne i pośrednie węzły w drzewie określają tylko operatory łączenia.
Charakteryzowanie z obudowami przestrzeni, którą wypełniają wszystkie bryły, daje wszystkim węzłom w drzewie abstrakcyjne podsumowanie informacji o pozycji i rozmiarze. Następnie szybkie testy „promień przecina obudowę” kierują wyszukiwaniem w hierarchii. Gdy test zakończy się niepowodzeniem w węźle pośrednim w drzewie, promień ma gwarancję, że zostanie zaklasyfikowany jako poza złożonym, więc ponowne przechodzenie w dół jego poddrzew w celu dalszego zbadania nie jest konieczne.
Dokładne oszacowanie oszczędności kosztów stosowania obudów jest trudne, ponieważ zależy to od przestrzennego rozmieszczenia prymitywów (rozkład złożoności) oraz od organizacji drzewa kompozycji. Optymalne warunki to:
- Żadne prymitywne obudowy nie zachodzą na siebie w przestrzeni
- Drzewo kompozycji jest wyważone i zorganizowane tak, że bryły znajdujące się w pobliżu przestrzeni znajdują się również w pobliżu drzewa
Natomiast najgorszy stan to:
- Wszystkie prymitywne obudowy wzajemnie się pokrywają
Poniżej przedstawiono różne ulepszenia wydajności wprowadzone w artykule Rotha na temat odlewania promieni, ale nastąpiły znaczne ulepszenia wprowadzone później przez innych.
- Wczesne wyjścia . Jeśli operator w węźle złożonym w drzewie to – lub &, a promień zaklasyfikuje jako spoza lewej podbryły kompozytu, to promień zostanie sklasyfikowany jako spoza kompozytu niezależnie od klasyfikacji promienia w odniesieniu do prawej podbryły. solidny. Tak więc klasyfikacja promienia względem właściwej sub-bryła jest niepotrzebna i należy jej unikać w celu zwiększenia wydajności.
- Transformacje . Dzięki początkowemu połączeniu transformacji ekran-scena z transformacją sceny do lokalnej prymitywu i zapisaniu wynikowych transformacji ekran-do-lokacji w strukturach danych prymitywu, jedna transformacja promienia na każde przecięcie powierzchni promienia zostaje wyeliminowana.
- Rekurencja . Biorąc pod uwagę głębokie drzewo kompozycji, rekurencja może być kosztowna w połączeniu z przydzielaniem i zwalnianiem pamięci. Rekurencję można symulować za pomocą tablic statycznych jako stosów.
- Ograniczanie dynamiczne . Jeśli mają być wyświetlane tylko widoczne krawędzie bryły, algorytm rzutowania promienia może dynamicznie powiązać promień, aby odciąć wyszukiwanie. Oznacza to, że po stwierdzeniu, że promień przecina podbryłę, algorytm może użyć punktu przecięcia najbliżej ekranu, aby zawęzić granicę głębokości dla testu „pudełka przecięcia promieni”. Działa to tylko dla części drzewa +, zaczynając od góry. Z – i &, pobliskie „w” części promienia mogą później stać się „na zewnątrz”.
- Spójność . Zasada spójności polega na tym, że powierzchnie widoczne na dwóch sąsiednich pikselach z większym prawdopodobieństwem będą takie same niż różne. Twórcy grafiki komputerowej i systemów wizyjnych zastosowali tę empiryczną prawdę dla wydajności i wydajności. W przypadku rysunków liniowych obszar obrazu zawierający krawędzie jest zwykle znacznie mniejszy niż całkowity obszar obrazu, dlatego rzucanie promieni powinno być skoncentrowane wokół krawędzi, a nie w obszarach otwartych. Można to skutecznie wdrożyć, rzadko próbkując ekran za pomocą promieni, a następnie lokalizując krawędzie, gdy sąsiednie promienie identyfikują różne widoczne powierzchnie, za pomocą wyszukiwania binarnego.
Wygładzanie krawędzi
Postrzępione krawędzie spowodowane aliasingiem są niepożądanym efektem technik próbkowania punktowego i są klasycznym problemem algorytmów wyświetlania rastrowego. Liniowe lub gładko zakrzywione krawędzie będą wyglądały na postrzępione i są szczególnie nieprzyjemne w animacjach, ponieważ ruch obrazu sprawia, że krawędzie wydają się rozmyte lub wyglądają jak małe ruchome schody ruchome. Ponadto mogą zostać utracone szczegóły sceny mniejsze niż odstępy między promieniami. Postrzępione krawędzie na rysunku liniowym można wygładzić przez śledzenie krawędzi. Celem takiego algorytmu jest zminimalizowanie liczby linii potrzebnych do narysowania obrazu z dokładnością do jednego piksela. Efekt gładkich krawędzi. Powyższe rysunki liniowe zostały narysowane w ten sposób.
Aby wygładzić postrzępione krawędzie w cieniowanym obrazie z dokładnością do subpikseli, należy rzucić dodatkowe promienie w celu uzyskania informacji o krawędziach. (Patrz Supersampling, aby zapoznać się z ogólnym podejściem.) Krawędzie są tworzone przez przecięcie powierzchni lub przez profil zakrzywionej powierzchni. Stosując "koherencję" jak opisano powyżej za pomocą wyszukiwania binarnego, jeśli widoczna powierzchnia na pikselu (X,Y) jest inna niż widoczna powierzchnia na pikselu (X+1,Y), wtedy promień może zostać wygenerowany w połowie ich na (X+ ½,Y) i tam widoczna powierzchnia. Odległość między punktami próbkowania może być dalej dzielona, ale poszukiwanie nie musi być głębokie. Podstawowa głębokość wyszukiwania w celu wygładzenia postrzępionych krawędzi jest funkcją gradientu intensywności wzdłuż krawędzi. Ponieważ (1) obszar obrazu, który zawiera krawędzie, jest zwykle niewielkim procentem całkowitego obszaru i (2) dodatkowe promienie rzucane w wyszukiwaniach binarnych mogą być ograniczone do głębokości — widocznych prymitywów tworzących krawędzie — koszt wygładzanie postrzępionych krawędzi jest niedrogie.
Historia rzucania promieni
Aby zapoznać się z historią odlewania promieni, zobacz ray tracing (grafika), ponieważ oba są w zasadzie tym samym. Scott Roth wynalazł termin „promieniowanie”, zanim usłyszał o „śledzeniu promieni”. Rozwój ray castingu Scotta Rotha w GM Research Labs odbywał się równocześnie z pracą Turnera Whitteda w Bell Labs w zakresie ray tracingu.
Ray casting we wczesnych grach komputerowych
We wczesnych grach pierwszoosobowych, raycasting był używany do wydajnego renderowania świata 3D z pola gry 2D za pomocą prostego jednowymiarowego skanowania na poziomej szerokości ekranu. Wczesne strzelanki pierwszoosobowe wykorzystywały rzucanie promieni jako technikę tworzenia efektu 3D ze świata 2D. Podczas gdy świat wydaje się trójwymiarowy, gracz nie może patrzeć w górę lub w dół lub tylko pod ograniczonymi kątami z dystorsją ścinającą, ponieważ pozwala to na szybsze renderowanie pola gry 2D.
Wolfenstein 3D
Znana na całym świecie gra wideo Wolfenstein 3D została zbudowana z kwadratowej siatki ścian o jednolitej wysokości, która łączy się z podłogami i sufitami w jednolitych kolorach. Aby narysować świat, na każdą kolumnę pikseli ekranu śledzono pojedynczy promień, a pionowy fragment tekstury ściany został wybrany i przeskalowany w zależności od tego, gdzie na świecie promień uderza w ścianę i jak daleko pokonuje, zanim to zrobi.
Cel poziomów opartych na siatce był dwojaki — kolizje ze ścianą promieni można znaleźć szybciej, ponieważ potencjalne trafienia stają się bardziej przewidywalne, a obciążenie pamięci jest mniejsze. Jednak kodowanie szeroko otwartych obszarów zajmuje dodatkowe miejsce.
ShadowCaster
Raven Software gra ShadowCaster wykorzystuje ulepszony silnik Wolfenstein opartego z dodatkiem podłogi i sufity teksturowania i zmiennych wysokościach ściennych.
Seria Comanche
Silnik Voxel Space opracowany przez NovaLogic dla gier Comanche śledził promień przechodzący przez każdą kolumnę pikseli ekranu i testował każdy promień z punktami na mapie wysokości . Następnie przekształcił każdy element mapy wysokości w kolumnę pikseli, które określiły, które są widoczne (tzn. nie zostały przesłonięte przez piksele narysowane z przodu) i narysował je odpowiednim kolorem z mapy tekstury.
Poza raycastingiem
Późniejsze gry DOS, takie jak DOOM firmy id Software, zachowały wiele ograniczeń dotyczących szybkości raycastu 2.5D, ale przeszły na alternatywne techniki renderowania (takie jak BSP ), co sprawiło, że nie były już silnikami raycastingu.
Ustawienie geometrii obliczeniowej
W geometrii obliczeniowej problem rzucania promieni jest również znany jako problem ze strzelaniem promieni i może być określony jako następujący problem z zapytaniem: mając zestaw obiektów w przestrzeni d- wymiarowej, przetwórz je wstępnie w strukturę danych, tak aby dla każdego promienia zapytania, początkowy obiekt trafiony przez promień można szybko znaleźć. Problem został zbadany dla różnych ustawień: wymiar przestrzeni, typy obiektów, ograniczenia promieni zapytań itp. Jedną z technik jest użycie rzadkiego oktreu woksela .
