Śledzenie promieni

Śledzenie promieni, wsteczne śledzenie promieni (ang. ray tracing, backward raytracing) – technika generowania fotorealistycznych obrazów scen trójwymiarowych opierająca się na analizowaniu tylko tych promieni światła, które trafiają bezpośrednio do obserwatora. W rekursywnym śledzeniu promieni bada się dodatkowo promienie odbite, zwierciadlane oraz załamane. Ponadto umożliwia łatwą realizację CSG, a także wizualizację idealnych, opisywanych formułami matematycznymi obiektów. Odwrotne podejście do techniki śledzenia promieni realizuje metoda prostego śledzenie promieni (ang. forward raytracing).

Metoda mimo uproszczonego modelu interakcji światła z otoczeniem daje bardzo dobre rezultaty, jednak ze względu na koszty obliczeniowe przez wiele lat jej wykorzystanie limitowała moc obliczeniowa komputerów, które były dostępne tylko dla dużych firm, głównie z branży filmowej. Współczesne komputery osobiste są w stanie bez problemu generować obrazy tą metodą i dostępne są komercyjne oraz darmowe programy (POV-Ray, Blender, 3ds Max, Maya, LightWave 3D, PYTHA).

Algorytm

Zobacz też: algorytm.

Sposób określania barwy piksela w śledzeniu promieni

Algorytm śledzenia promieni wygląda następująco:

Z punktu w którym znajduje się obserwator wyprowadzany jest promień pierwotny, który przecina rzutnię.
Wyszukiwany jest najbliższy punkt przecięcia z obiektami znajdującymi się na scenie.
Następnie dla każdego źródła światła zdefiniowanego na scenie wyznaczana jest jasność w tym punkcie, zgodnie z określonym modelem oświetlenia (np. Lamberta czy Phonga).
Najczęściej także określa się cienie – w tym celu jest testowana widoczność źródła światła z danego punktu, tj. czy światło nie jest przesłaniane przez jakiś obiekt i jeśli nie – dopiero wtedy oblicza się jasność punktu dla tego źródła.

W algorytmie rekurencyjnym dodaje się jeszcze jeden warunek:

Jeśli punkt przecięcia należy do obiektu odbijającego światło lub przezroczystego, wysyłane są z tego punktu promienie wtórne – odpowiednio, promień odbity lub promień załamany – i algorytm rekursywnie powtarza się od drugiego kroku (w większości programów można ograniczyć liczbę zejść rekurencyjnych). Kolor punktu wyznaczany jest dopiero, gdy znane są wyniki przetwarzania promieni wtórnych; zwykle projektant podaje procentowo wpływ kolorów z promieni wtórnych, tj. określa jak bardzo obiekt odbija/załamuje światło.

Algorytm śledzenia promieni stosuje się dla wszystkich pikseli obrazu; aby uniknąć aliasingu przez jeden piksel przeprowadza się więcej niż jeden promień.

Bardzo dużą zaletą tej metody jest łatwość przeprowadzenia obliczeń równoległych, gdyż każdy promień pierwotny może być przetwarzany niezależnie od innych; podobnie promienie wtórne są od siebie niezależne.

Obecnie śledzenie promieni implementuje się również w procesorach graficznych uzyskując obrazy w czasie rzeczywistym (kilkanaście-kilkadziesiąt klatek na sekundę).

Przykład

Obserwator (kamera) znajduje się w punkcie O, na scenie umieszczone zostały dwa światła L1 i L2 oraz trzy obiekty:

a (elipsa): nieprzezroczysty, nie odbija światła,
b (koło): przezroczysty, odbija światło,
c (prostokąt): tylko odbija światło.

Z punktu O wyprowadzany jest promień pierwotny (zielony), który trafia w obiekt b – ponieważ odbija i załamuje światło, toteż z punktu przecięcia wypuszczane są dwa promienie wtórne: odbity (czerwony) i załamany (niebieski). Promień odbity trafia z kolei w obiekt a – tutaj już nie są generowane żadne promienie wtórne. Z kolei promień załamany znów trafia w obiekt b i ponownie ulega załamaniu (tak naprawdę powinien tutaj być jeszcze promień odbity, ale ze względu na przejrzystość rysunku został pominięty). Ten promień trafia w obiekt c, który odbija światło, toteż generowany jest tylko jeden promień wtórny (odbity), który jednak nie przecina się z żadnym obiektem na scenie i na tym kończy się analiza.

Kreskami przerywanymi zaznaczono dodatkowe promienie, służące określeniu widoczności świateł w punktach przecięcia (dla punktów obiektu b te promienie nie zostały narysowane) – jak widać zarówno inne obiekty (b) jak i sam obiekt (a) może blokować światło.

Wyznaczanie promieni dla prostokątnej rzutni

Na wejściu dane mamy (punkty oznaczamy dużymi literami, wektory i skalary małymi):

$E\in \mathbb {R^{3}}$ pozycja oka
$T\in \mathbb {R^{3}}$ pozycja celu
$\theta \in [0,\pi )$ pole widzenia - dla człowieka można przyjąć $\approx \pi /2{\text{ rad}}=90^{\circ }$
$m,k\in \mathbb {N}$ liczba kwadratowych pikseli odpowiednio na wysokości i szerokości rzutni
$i,j\in \mathbb {N} ,1\leq i\leq k\land 1\leq j\leq m$ numery/współrzędne aktualnego piksela
${\vec {w}}\in \mathbb {R^{3}}$ wektor pionu, wyznaczający gdzie jest góra a gdzie dół, zwykle $w=[0,1,0]$ (nie pokazano na rysunku)

Idea polega na znalezieniu pozycji środka każdego piksela na rzutni $P_{ij}$ co łatwo dalej pozwoli znaleźć prostą przechodzącą przezeń i punkt $E$ i w konsekwencji sam promień opisany jako para $E$ i znormalizowany wektor ${\vec {r}}_{ij}$ . Aby to zrobić wystarczy że znajdziemy położenie lewego dolnego piksela $P_{1m}$ a kolejne piksele poprzez odpowiednie przesunięcia (o wielokrotność wielkości piksela) wzdłuż kierunków prostopadłych do rzutni (wektory ${\vec {b}}$ i ${\vec {v}}$ ). Poniżej wyprowadzimy zależności uwzględniając odległość $d$ oka od rzutni, jednak ta wartość skróci się podczas normalizacji wynikowego wektora ${\vec {r}}_{ij}$ (więc równie dobrze można przyjąć że $d=1$ i usunąć z obliczeń). Obliczenia wstępne: obliczymy znormalizowane wektory $v_{n},b_{n}$ (patrz rysunek powyżej) prostopadłe do rzutni

t=T-E,\qquad b=w\times t

t_{n}={\frac {t}{||t||}},\qquad b_{n}={\frac {b}{||b||}},\qquad v_{n}=t_{n}\times b_{n}

zauważmy że: $C=E+t_{n}d$ , następnie obliczamy wielkości rzutni $h_{x},h_{y}$ podzielone przez 2 z uwzględnieniem stosunku tych dwóch wielkości ${\frac {m}{k}}$ :

g_{x}={\frac {h_{x}}{2}}=d\tan {\frac {\theta }{2}},\qquad g_{y}={\frac {h_{y}}{2}}=g_{x}{\frac {m}{k}}

a następnie obliczymy wektory przesunięcia $q_{x},q_{y}$ wzdłuż kierunków prostopadłych do rzutni ( ${\vec {b}},{\vec {v}}$ )

q_{x}={\frac {2g_{x}}{k-1}}b_{n},\qquad q_{y}={\frac {2g_{y}}{m-1}}v_{n},\qquad p_{1m}=t_{n}d-g_{x}b_{n}-g_{y}v_{n}

Obliczenia właściwe: zauważmy że $P_{ij}=E+p_{ij}$ oraz że promień $R_{ij}=P_{ij}-E=p_{ij}$ zatem

p_{ij}=p_{1m}+q_{x}(i-1)+q_{y}(j-1)

r_{ij}={\frac {p_{ij}}{||p_{ij}||}}

Powyższa formuła została przetestowana w tym projekcie javascript (działa w przeglądarce).

Złożoność obliczeniowa

Zobacz też: złożoność obliczeniowa.

Śledzenie promieni jest metodą kosztowną obliczeniowo – liczba obliczeń jest proporcjonalna do rozdzielczości obrazu, zależy również od stopnia skomplikowania sceny, tj. od liczby świateł (wyznaczenie cieni), liczby obiektów oraz ich charakterystyki: jeśli bowiem zawiera dużą liczbę obiektów odbijających lub załamujących światło należy przeprowadzać analizę także dla promieni wtórnych.

Zasadniczym czynnikiem wpływającym na szybkość obliczeń jest procedura znajdowania najbliższego przecięcia promienia z obiektami geometrycznymi. Np. wyznaczenie przecięcia z kulą wymaga rozwiązania równania kwadratowego, a przecięcia z płaszczyzną rozwiązania równania liniowego (ale już dla wycinków płaszczyzny, np. wielokątów, wymaga dodatkowych testów). Z kolei dla obiektów bardziej skomplikowanych, jak torusy, bryły obrotowe, płaty Béziera, czy NURBS potrzebne są złożone obliczenia.

Nie mniej ważnym problemem jest wytypowanie tych obiektów ze sceny, które mogą się z danym promieniem przeciąć – aby procedury przeprowadzające dokładne obliczenia wywoływać tylko wtedy, gdy jest to niezbędne; mówiąc obrazowo: jeśli scena zawiera milion obiektów, by za każdym razem nie testować milion razy, czy promień przecina każdy z nich. Jednym ze sposobów na minimalizację obliczeń jest podział przestrzenny sceny (regularną siatką, drzewami ósemkowymi, kd, czy BSP), powszechnie wykorzystuje się także bryły otaczające (pozwalające szybciej określić czy promień może mieć punkt wspólny z obiektem, bądź że na pewno go nie ma).

Wady

Śledzenie promieni, mimo swoich zalet, nie jest idealnym sposobem tworzenia fotorealistycznych obrazów. Przede wszystkim w ogóle nie uwzględnia światła rozproszonego, ponadto ponieważ operuje na pojedynczych promieniach, nie może prawidłowo modelować dyfrakcji, rozszczepienia światła np. na pryzmacie, interferencji fal świetlnych i innych zjawisk falowych.

Stworzono wiele technik, które stosowane samodzielnie bądź w połączeniu ze śledzeniem promieni umożliwiają pokonanie tych niedogodności; są to m.in. metoda energetyczna, śledzenie ścieżek, metoda map fotonowych i tzw. forward raytracing.

Zobacz też