# Podstawy Raycastingu

## Raycasting w skrócie

Rysunek przedstawia działanie Camera Obscura:

![Camera obscura](static/2-camera_obscura.jpg)

Aparaty zamiast używać małego otworu, robią coś podobnego przy pomocy soczewek.
Napisany przez nas raytracer będzie też działał na podobnej zasadzie.
Nie będziemy jednak generować obrazu na tylnej scianie, tylko przed otworem, dzięki czemu nie będzie odwórcony:

1. Przed punktem skupienia promieni "umieścimy" prostokątną siatkę w kratkę, którą podzielimy na piksele.
2. Dla każdego piksela będziemy osobno ustalali jego kolor sprawdzając, w który obiekt na scenie uderza promień przechodzący do ogniska przez ten piksel.

W zarysie:

```python
def render_image(scene, camera, out_image):
    for x in range(camera.width):
        for y in range(camera.height):
            pix_center_position = camera.pixel_center(x, y)
            hit_object = check_first_hit(ray_from_to(camera.focus, pix_center_position), scene)
            out_image[x, y] = hit_object.color if hit_object else COLOR_BLACK
```

Kolejność pracy będzie odwrotna:

1. Zaczniemy od sprawdzania, czy pojedynczy promień przecina obiekt sceny.
2. Napiszemy funkcję, która dla danego promienia wybiera pierwszy przecięty obiekt.
3. Złożymy to do kupy w obraz, wykonując powyższe sprawdzenia dla każdego piksela.

Co będzie na kolejnych zajęciach:

1. Dzisiaj jedynymi obiektami na scenie będą sfery; jutro dowiemy się, jak w praktyce opisuje się bardziej złożone kształty.
2. W piątek zajmiemy śię oświetleniem - dzisiejsza technika pomija fakt, że obiekty nie mają koloru same w sobie, tylko wynika on ze sposobu, w jaki odbijają padające na nie światło.

## Wektory

![Ilustracje operacji na wektorach](static/2-all_the_vectors.png)

Wektory:

- "Strzałki między punktami":
    - konkretny wektor oznacza konkretne przesunięcie w układzie współrzędnych,
    - nie ważne, gdzie jest zaczepiony,
    - $v = (5, 4)$ oznacza, że wektor $v$ przesuwa o 5 wzdłuż OX i o 4 wzdłuż OY.
- Dodawanie wektorów:
    - dodajemy współrzędne: $(x_1, y_1) + (x_2, y_2) = (x_1 + x_2, y_1 + y_2)$,
    - graficznie wygląda seria marszów na azymut.
- Wektory można mnożyć przez liczbę:
    - mnożymy poszczególne współrzędne: gdy $v = (x, y)$ to $av = (ax, ay)$

Wektory mają sens też w 3D, mają wtedy trzy współrzędne:
- współrzędna $x$ od lewej do prawej,
- współrzędna $y$ z dołu do góry,
- współrzędna współrzędna $z$ z tyłu do przodu.

Widać to jak na dłoni; konkretnie trzech palcach lewej dłoni!

![Right hand rule](static/2-right_hand_coordinates.png)

Kod startowy na dzisiejsze zajęcia zawiera implementację wektorów w 3D w Pythonie:

```py
from starting_code.w2_simple_raytracer import Vec3
# Tworzenie wektora:
u = Vec3(1, 2, 3)
v = Vec3(4, 5, 6)
# Pobieranie współrzędnych
print("Współrzędne u to:", u.x, u.y, u.z)
# Dodawanie i odejmowanie:
print(u + v)
print(u - v)
# Mnożenie:
print(2 * u)
```

```{attention}
"Na kartce" do poszczególnych współrzędnych punktu/wektora będziemy się odwoływać przez $v_x, v_y, v_z$, co odpowiada pythonowemu `v.x`, `v.y` i `v.z`.
```

Dwa wektory są sobie równe wtedy i tylko wtedy, kiedy ich kolejne współrzędne są sobie równe.

To pozwala nam rozpisywać równania na wektorach, na przykład: jeżeli $u, v, w$ to wektory, a $a, b, c \in \mathbb{R}$, to równanie:

```{math}
au + bv + cw = (1, 2, 3)
```

Oznacza to samo, co układ równań:

```{math}
\begin{cases}
a u_x + b v_x + c w_x = 1 \\
a u_y + b v_y + c w_y = 2 \\
a u_z + b v_z + c w_z = 3 \\
\end{cases}
```

Opis wektora jest identyczny z opisem punktu - punkt również składa się z trzech liczb oznaczających jego współrzędne.
Dlatego w Pythonie również punkty będziemy opisywać za pomocą typu `Vec3`.
Różnica generalnie jest w tym, co chcemy powiedzieć: punkty to konkretne miejsca w układzie współrzędnych, a wektory mogą być "położone gdziekolwiek" i opisują przesunięcie z jednego miejsca w inne.

Zróbmy krótkie ćwiczenia, żeby oswoić się z używaniem wektorów w Pythonie. Napisz funkcję, która dla danego wektora $v$ i listy wektorów $u_1, \dots, u_k$ zwróci ten wektor $u_i$, który jest najbliższy $v$ (w sensie odległości między punktami).

```python
from starting_code.w2_simple_raytracer import Vec3

def find_closest(v, us):
    ...

# Sprawdzenie, czy działa
assert find_closest(Vec3(0, 0, 0), [Vec3(1, 0, 0), Vec3(0, 0, 0)]) == Vec3(0, 0, 0)
assert find_closest(Vec3(0, 0, 0), [Vec3(1, 0, 0), Vec3(0, 0.1, 0), Vec3(1, 2, 3)]) == Vec3(0, 0.1, 0)
```

## Przecięcie promienia ze sferą

Pierwszymi obiektami, jakie pojawią się na naszej scenie, będą sfery.
Dlatego zaczniemy od napisania kodu, który będzie wyznaczał punkt przecięcia promienia ze sferą.

Do opisania promienia będziemy używać dwóch wartości:

- `ray.orign`: punkt, z którego wychodzi promień,
- `ray.direction`: wektor określający, w którym kierunku biegnie promień.

Zbiór punktów składających się na promień możemy wtedy opisać jako:

```{math}
\{ p\colon p = \texttt{ray.origin} + t \cdot \texttt{ray.direction}, \text{ gdzie $t>0$} \}
```

Z kolei sfera o środku $C$ i promieniu $r$ to zbiór punktów równoodległych od jej środka:

```{math}
\{ p\colon (p_x - C_x)^2 + (p_y - C_y)^2 + (p_z - C_z)^2 = r^2
```

Wobec tego zróbmy teraz takie zadanie: *jak sprawdzić, czy promień z punktu $O$ (`ray.origin`) w kierunku wektora $d$ (`ray.direction`) przecina sferę o środku $C$ i promieniu $r$, a jeżeli tak, to w jakiej odległości od początku promienia znajduje się to przecięcie?*

```{toggle}
Trzeba rozwiazać równanie kwadratowe ze zmienną $t$: $(O_x + td_x - C_x)^2 + (O_y + td_y - C_y)^2 + (O_z + td_z - C_z)^2 = r^2$. 
```

Obliczmy rozwiązanie tego równania. Następnie użyjmy go do napisania klasy opisującej sferę na scenie:

```python
class Sphere:
    def __init__(self, color, center, radius):
        self.color = color
        self.center = center
        self.radius = radius

    def check_hit(self, ray):
        # Funkcja powinna zwrócić odległość do pierwszego punktu przecięcia promienia ze sferą,
        # jeżeli promień ją przecina, a w przeciwnym wypadku specjalną wartość None
        ...


# Sprawdzenie, czy działa
sphere = Sphere(COLOR_BLACK, Vec3(0, 0, 0), 1)
assert 0.999 <= sphere.check_hit(Ray(Vec3(0, 2, 0), Vec3(0, -1, 0))) <= 1.001
assert sphere.check_hit(Ray(Vec3(0, 2, 0), Vec3(0, -1, 44))) is None
```

## Znajdowanie właściwej sfery

Jeżeli na scenie może być kilka sfer, to nie wystarczy umieć jedynie odpowiedzieć na pytanie, czy promień trafia w jedną z nich.

![Test głębokości](static/2-depth-test.png)

Musimy być w stanie wybrać tę, w którą promień trafia jako pierwszą, czyli tę o punkcie przecięcia najbliższym początkowi promienia.
Wszystkie pozostałe są w tym punkcie przez nią zasłonięte.

Kolejnym krokiem będzie napisanie takiej funkcji, która dla danego promienia i mając do dyspozycji opis sceny wyznaczy ten obiekt, w który faktycznie trafia promień.
Jeżeli promień nie trafia w żaden obiekt, powinna zwrócić `None`.

```python
scene = [
    Sphere(COLOR_RED, Vec3(0, 0, 0), 2),
    Sphere(COLOR_BLUE, Vec3(1, 0, 0), 1.1),
]

def compute_hit_object(ray):
    ...

# Sprawdzenie, czy działa
assert compute_hit_object(Ray(Vec3(3, 0, 0), Vec3(-2, 0, 0))) is scene[1]
assert compute_hit_object(Ray(Vec3(3, 0, 0), Vec3(-2, 1, 0))) is scene[0]
assert compute_hit_object(Ray(Vec3(3, 0, 0), Vec3(-2, -1.9, 0))) is scene[0]
assert compute_hit_object(Ray(Vec3(3, 0, 0), Vec3(-2, 4, 0))) is None
```

## Tworzenie obrazu

Żeby wygenerować obraz, raytracer potrzebuje dla każdego piksela ekranu sprawdzić, w który obiekt uderza promień z ogniska kamery w kierunku tego piksela - jak na obrazku:

![Rzutnia raytracera](static/2-projection.png)
Źródło prawej części: https://commons.wikimedia.org/wiki/File:Ray_trace_diagram.svg

Danymi wejściowymi na tym etapie są informacje na temat "aparatu", który robi zdjęcie naszej sceny ("camera" po angielsku brzmi lepiej):

- Rozdzielczość danego obrazu, czyli dwie liczby całkowite: `output.width` i `output.height`,
- Współrzędne punktu ogniskowego: `camera.focus: Vec3`,
- Współrzędne rogów ekranu: `camera.top_left: Vec3`, `camera.top_right`, `camera.bottom_right: Vec3`.

Na podstawie tych danych musimy wyliczyć współrzędne środków wszystkich pikseli ekranu - przez nie do ogniska dochodzą promienie światła.

Chcemy napisać następującą funkcję:

```python
def render(camera, output):
    # Dodatkowe obliczenia...
    for img_x in range(output.width):
        for img_y in range(output.heght):
            # Ustawianie koloru piksela output[img_x, img_y]
            # na podstawie wyniku compute_hit_object()
            ...
```

## Wyświetlanie obrazu

Korzystając z wiedzy z poprzednich zajęć możemy wyświetlić obraz:

```python
def main():
    S_WIDTH = 300
    S_HEIGHT = 300

    pg.init()
    pg.display.init()
    screen = pg.display.set_mode((S_WIDTH, S_HEIGHT), 0, vsync=True)
    pixels = pg.PixelArray(screen)

    # TODO: utworzyć kamerę na podstawie proporcji ekranu i sceny
    camera = Camera(
        bottom_left=...,
        top_left=...,
        bottom_right=...,
        focus=...
    )
    
    render(camera, pixels)

    del pixels
    pg.display.flip()
    running = True
    while running:
        events = pg.event.get()
        for event in events:
            if event.type in [pg.QUIT]:
                running = False
    pg.quit()

    
# TODO: porozmieszczać sfery na scenie
scene = []
main()
```

![4 sfery](static/2-finale.png)