# Raytracing

Written by @laian and @SaveMePlz

P.S. This guide is very abstract and only serves to give a general understanding on raytracing concepts.

Raytracing is a way to make pretty realistic computer generated images. It uses math to mimic how light affects its surroundings in real life.

---

## The end goal?
goal: to determine the colour (r, g, b values) for all pixels on a screen

solution: cast a ray for each pixel on the screen

###### the true goal is to make pretty images while burning up the cpu

---

## What is a ray?

a ray is basically a 3d equation for a line in vector form:

<center>

$l = p + d(t)$\
$p = position\;vector$\
$d = direction\;vector$

</center>

think of a ray like a line whose only purpose is to see if it intersects with anything else. (objects, light, nothing)

rays mimic a light ray in real life

in raytracing a ray has 1 objective, to test for intersections

based on the intersection of different things we can calculate what the colour of the origin of the ray (a pixel on the screen) is supposed to look like

---

## the raytracing algorithm

### Forward Tracing (real life)

<center>


</center>

1. light source cast a ray to the object
2. object then reflects the ray to viewer eyes

Pros:
1. Its literally how real life works

Cons:
1. Slow - have to cast way too many rays from the light, some might not even intersect with viewer
2. Inefficient - again, wasting too many resources on rays that will not intersect with viewer (or just goes to nothingness)

Solution: Have the ray casted by the viewer instead

### Backward Tracing

<center>


</center>

1. The viewer cast a ray to the nearest intersecting object
2. The object then cast a ray to all non-blocking light source

Pros:
1. Faster than Forward Tracing
- Less rays casted compared to Forward Tracing

Cons:
1. Still slow
- Need to check every single object in the scene to determine the closest object
- Also need to check every light source to calculate the effect of the light source on the object's color

...at least its faster now

---

## Coordinate Systems

to calculate intersections correctly all entities (rays, objects, the camera) have to be in the same coordinate system.

there are 3 primary coordinate systems that are used in raytracing:
- object space
- world space
- camera / view space

### object space

object space is where the origin is centered around the object. The origin is at the center of the object.

object space is not very useful since every object has its own (and different) object space,
intersections cannot be calculated using it

however, object space can be used to apply transformations to an object (translation, rotation, scaling, etc.)

### world space

the default space used for all objects. The origin is centered around a singular point defined in the space, (0,0,0). Intersections can be calculated in this coordinate system, however this is useful only if the camera is at a fixed point in space and does not move.

### view space

view space is where the origin (0,0,0) is centered around the camera. this makes it very easy to calculate intersections because everything is relative to the camera's position.

### how to transform between coordinate systems?

converting a point from one space to another is just a matter of translating and rotating it.

problem: we need to convert coordinates from one space to another space

solution: use matrices

4x4 matrices can be used to represent the translation and rotation in 3d space.

if we apply the 4x4 matrix onto each coordinate we can get the tranformed coordinate.

*note: applying a matrix -> matrix multiplication

matrix multiplication can only be done if the number of columns in the first matrix is equal to the number of rows in the second matrix

therefore, 3d coordinates originally expressed in a vec3 format:

$${\large{\begin {bmatrix} x \\ y \\ z \end {bmatrix}}}$$

will have to be expressed in 4d using vec4:

$${\large{\begin {bmatrix} x \\ y \\ z \\ w \end {bmatrix}}}$$

however, $w = 0$ for all cases, so:

$${\large{\begin {bmatrix} x \\ y \\ z \\ 0 \end {bmatrix}}}$$

#### forming the 4x4 world-to-view matrix

this matrix is used to convert from world space to view space (to allow for camera movement)

the matrix is made up of two parts, rotation and translation, that are combined together.

#### rotation:

we start with an identity matrix and then start filling values in

$${\large{\bar v = \begin {bmatrix}
r_x & u_x &-f_x & 0\\
r_y & u_y &-f_y & 0\\
r_z & u_z &-f_z & 0\\
0 & 0 & 0 & 1 \end
{bmatrix}}}$$

-- you know i never get how this worked

$$r = right\;vector$$
$$u = true\;up\;vector$$
$$f = forward\;vector$$

Here is a diagram representing the vectors:


note that the Z axis is perpendicular to the screen, and that $Z^+$ is pointing towards the viewer. (right handed coordinate system)

therefore, the forward vector is pointing towards us from the position of the camera

#### translation:

similar as rotation,

$${\large{\bar v = \begin {bmatrix}
1 & 0 & 0 & p_x\\
0 & 1 & 0 & p_y\\
0 & 0 & 1 & p_z\\
0 & 0 & 0 & 1 \end
{bmatrix}}}$$

$$p = position\;vector$$

position is just camera position in world view

---

## Object Intersections & Normals

First, we need to define some terms (just one)

### Normal

A Normal is just a vector that is pointing straight up perpendicular from a surface

We use normals for lighting

Different object has different methods of calculating it's normal

<center>
<img src="https://hackmd.io/_uploads/Hk_45qr0h.png" alt="normal" width="200"/>
</center>

### Sphere
###### ballers :baseball: :8ball: :basketball:

sphere is SIGNIFICANTLY easier than the rest

What is given for a sphere - location, radius

#### Formula

Let

Center of sphere = $(0,0,0)$

Ray Equation: $l = p + d(t)$\
can be rewritten as:\
$(x_l,y_l,z_l)=(x_p, y_p, z_p)+(t)(x_d, y_d, z_d)$

<center>


</center>

$|OP|^2 = r^2$

$OP \cdot OP = r^2$

sub line equation

$(p + d(t)) \cdot (p+d(t))=r^2$

###### do you know you can expand a dot prod? i hella dont, dot product obey the commutative, scalar multiplication and distributive property, we used distributive property here

$(p\cdot p)+2(p \cdot d(t))+(d(t) \cdot d(t))=r^2$

$(p\cdot p)+2\cdot t\cdot (p\cdot d)+t^2\cdot(d\cdot d)=r^2$

##### Optimization time

Optimization 1

d magnitude is always 1\
$\therefore (d \cdot d) = 1$

$(p\cdot p)+2\cdot t\cdot (p\cdot d)+t^2=r^2$

Order by degree of t

$t^2+t\cdot2\cdot(p\cdot d)+(p\cdot p)-r^2=0$

if you subtitute all the constants, you will realize that\
$t^2(A) + t(B)+(C) = 0$\
...this is just a quadratic equation, where\
$A = 1$\
$B = 2\cdot(p\cdot d)$\
$C = (|p|)^2-r^2$

###### note that $(p \cdot p) = |p|^2$

Now remember the quadratic formula ↴

$x = \frac{-b\pm\sqrt{b^2-4ac}}{2a}$

before we talk about how to remove the 2, lets talk about determinant

$b^2-4ac$ is within a square root, and since
- $\sqrt{<0}$ = no real numbers (we ARE NOT DEALING WITH COMPLEX NUMBERS)
- $\sqrt{0} = 0$
- $\sqrt{> 0} = \pm{(>0)}$

Therefore
- $b^2-4ac<0$ = k isnt a real number, k has no solution => does not intersect
- $b^2-4ac=0$ = k only has one value => one intersection
- $b^2-4ac>0$ = k has two intersection

The issue with k having two intersection is ↴

<center>


</center>

So, for k having two values, we need to
1. Determine the smallest value (the smallest value is the one closest to the viewer)
2. Check if the smallest value is < 0, if it is, choose the other one
3. If both k values are < 0, it does not intersect at all

##### More optimizations on Formula

Optimization 1\
if we sub B into the equation

$B = 2\cdot(p\cdot d)$

$\large x = \frac{-b\pm\sqrt{b^2-4ac}}{2a}$

we will find out that...

$\large x = \frac{-(2\cdot(p\cdot d))\pm\sqrt{(2\cdot(p\cdot d))^2-4ac}}{2a}$

$\large x = \frac{-(2\cdot(p\cdot d))\pm\sqrt{4\cdot(p\cdot d)^2-4ac}}{2a}$

$\large x = \frac{-(2\cdot(p\cdot d))\pm\:2\cdot\sqrt{(p\cdot d)^2-ac}}{2a}$

$\large x = \frac{2(-(p\cdot d)\pm\sqrt{(p\cdot d)^2-ac})}{2a}$

$\large x = \frac{-(p\cdot d)\pm\sqrt{(p\cdot d)^2-ac}}{a}$\
...B can just be $(p\cdot d)$, removing the need to multiply then divide 2

Optimization 2

$A$'s value is always 1\
...

The updated (and final) Equation would be

$x = -B\pm\sqrt{B^2-C}$\
$B = (p\cdot d)$\
$C = (|p|)^2-r^2$

#### Normal Formula

A normal formula of a circle would be the vector that is pointing perpendicular to the point

<center>
<img src = "https://hackmd.io/_uploads/ryAjRcrA2.png" width="100">
</center>

###### p.s. may not be accurate

if you think about it hard enough, the vector from the center to the intersection point is the normal to the circle

###### i actually do not know how to explain this, just like, imagine the center shooting an arrow to the intersection point, would the arrow shoot anywhere else? no, will it shoot perpendicularly to the point? probably? i mean it works so yeah.
<center>


</center>

so

$CN = CO + OP$\
$CN = OP - OC$

### Plane
###### haha pettan-ko

What is given: A point on the plane, the normal of plane

#### Formula

Let

Point on the plane = $(0,0,0)$

Ray Equation: $l = p + d(t)$\
can be rewritten as:\
$(x_l,y_l,z_l)=(x_p, y_p, z_p)+(t)(x_d, y_d, z_d)$

The fact that the normal is given is pretty poggers\
See, the normal of the plane = the vector perpendicular to the surface\
And since a plane is a very big surface

Remember Dot Product between Two Vectors\
$a\cdot b = |a||b|\;cos\theta$\
where theta = angle between the 2 vectors

if $\theta$ is $90^o$, that means the angle between a and b is $90^o$, which means it is perpendicular to one another.

$\therefore a\cdot b = |a||b|cos (90)$\
$a\cdot b = 0$

Now, Remember the dot product between two vectors ↴

$(x_1 i + y_1j + z_1k)\cdot (x_2 i + y_2j + z_2k) = (x_1x_2+y_1y_2+z_1z_2)$

$\therefore a\cdot b = (x_ax_b+y_ay_b+z_az_b) = 0$

$\therefore (xx_N+yy_N+zz_N) = 0$ if $(x,y,z)$ is a point on the plane

Once again, finding k in the line vector would find us the intersection point

so sub line vector into the formula

$(x_lx_N+y_ly_N+z_lz_N) = 0$\
$(x_p+ t\cdot x_d)\cdot x_N+(y_p+ t\cdot y_d)\cdot y_N+ (z_p+ t\cdot z_d)\cdot z_N = 0$

Rearranging Formulas\
$(x_p\cdot x_N+ t\cdot x_d\cdot x_N) +(y_p \cdot y_N+ t\cdot y_d \cdot y_N) + (z_p \cdot z_N+ t\cdot z_d \cdot z_N) = 0$
$t\cdot (x_d\cdot x_N + y_d \cdot y_N + z_d \cdot z_N) + x_p\cdot x_N + y_p\cdot y_N + z_p\cdot z_N = 0$

Some Substitution\
$x_d\cdot x_N + y_d \cdot y_N + z_d \cdot z_N = (d \cdot N)$\
$x_p\cdot x_N + y_p\cdot y_N + z_p\cdot z_N = (p\cdot N)$

Continue Rewritting and Rearranging\
$t\cdot (d \cdot N) + (p \cdot N) = 0$\

Final Equation\
$t = -\frac{(p\cdot N)}{(d \cdot N)}$

if t value is < 0, it does not intersect with the plane

#### Normal Formula

The normal of a plane is a must to be specified since it tells you how the plane is oriented

### Cylinder
###### you spin me right round baby right round

its complicated due to it having an extra axis vector

For a cylinder, the center of cylinder, height, radius and orientation axis of the cylinder is given

#### Formula

Let
Center of the Cylinder = $(0,0,0)$

Ray Equation: $l = p + d(t)$\
can be rewritten as:\
$(x_l,y_l,z_l)=(x_p, y_p, z_p)+(t)(x_d, y_d, z_d)$

orientation vector = $ON$


$|OP|^2 = |ON'|^2 + |N'P|^2$

$|N'P|$ = radius, r

$|ON'| = ON \cdot OP$

$\therefore, |OP|^2=(ON\cdot OP)^2+r^2$\
$|OP|^2-(ON\cdot OP)^2=r^2$

sub inside line equation

$|p+d(t)|^2 - (ON \cdot (p+d(t))^2 = r^2$\
Length of the squared of a vector is equal to the dot product of the vector by itself\
$((p+d(t))\cdot (p+d(t))) - ((ON \cdot p) + (ON\cdot d(t)))^2=r^2$

$(p\cdot p) + 2 \cdot p \cdot d(t) + t^2(d\cdot d)-(ON\cdot p)^2-2(ON\cdot p)\cdot(ON \cdot d(t)) - t^2\cdot(ON\cdot d)^2=r^2$

group by coefficients

$t^2 \cdot ((d \cdot d) - (ON \cdot d)^2) + t\cdot 2\cdot (p\cdot d - (ON\cdot p) \cdot (ON \cdot d))+(-(ON\cdot p)^2 + (p\cdot p)-r^2)=0$

the equation above is just a quadratic formula, which we can solve for t

$\large t = \frac{-B\pm\sqrt{(B^2-4AC)}}{2A}$

$A = (d \cdot d) - (ON \cdot d)^2$\
$B = 2\cdot (p\cdot d - (ON\cdot p) \cdot (ON \cdot d))$\
$C = (p\cdot p)-(ON\cdot p)^2 -r^2$

#### Cool Optimizations again..

Optimization one

magnitude of d is 1, so $(d\cdot d) = 1$

$A = 1 - (ON \cdot d)^2$

Optimization two

Similar to Sphere's the 2 in the quadratic equation can be removed

$B = 2\cdot (p\cdot d - (ON\cdot p) \cdot (ON \cdot d))$\
$b = p\cdot d - (ON\cdot p) \cdot (ON \cdot d)$
$b = B/2$

$\large t = \frac{-B\pm\sqrt{(B^2-4AC)}}{2A}$

$\large t = \frac{-B\pm\sqrt{4(\frac{B^2}{4}-AC)}}{2A}$

$\large t = \frac{-B\pm\;2\;\cdot \sqrt{((\frac{B}{2})^2-AC)}}{2A}$

$\large t = \frac{2 (-\frac{B}{2}\pm \sqrt{((\frac{B}{2})^2-AC)})}{2A}$

$\large t = \frac{(-\frac{B}{2}\pm \sqrt{((\frac{B}{2})^2-AC)})}{A}$

$\large t = \frac{(-b\pm \sqrt{(b^2-AC)})}{A}$

Final Equation would be

$\large t = \frac{(-b\pm \sqrt{(b^2-ac)})}{a}$

$a = 1 - (ON \cdot d)^2$\
$b = p\cdot d - (ON\cdot p) \cdot (ON \cdot d)$\
$c = (p\cdot p)-(ON\cdot p)^2 -r^2$

After this we still have to test if the ray intersects the top / bottom of the cylinder

<center>


</center>

Find k:

$k = ((p + d(t)) - O) \cdot ON$\
$k = OP \cdot ON$

if $k >= 0\;or\;k <= cylinder\;height$, it means that the ray has intersected the curved surface of the cylinder and not the top / bottom (therefore, we can show the colour).

Reference:
http://www.illusioncatalyst.com/notes_files/mathematics/line_cylinder_intersection.php

#### Normal Formula

### Cone
###### like cylinder, but one end is pinched

#### Formula

Bro forgot the formula
###### fr fr on god

Reference:

http://www.illusioncatalyst.com/notes_files/mathematics/line_cone_intersection.php

#### Normal Formula

---

## Lighting, Phong's Reflection Model and Shadows

### Phong's Reflection Model

a guy named (Phing) Phong makes some rules to describe the way a surface reflects light, as a combination of ambient, diffuse and specular components.

### Ambient
###### im blue badabeebadaba

ambient lighting is present everywhere.

i.e: every pixel's colour is originally the colour of ambient lighting, diffuse and specular lighting are just added on top of it to form the final colour of the pixel.

Note - there are also some definitions of ambient lighting is "the percentage of lighting that will be illuminated", so a $(125,125,125)$ lighting would only have $(50\%,50\%,50\%)$ of the light actually illuminated. so a $(120, 40, 50)$ light, after ambient lighting, would be $(60, 20, 25)$

i am not sure if this definition is correct, but it does look pretty tho so :P

### Diffuse

###### how many light is in this liGht?

formula:

$$Diffuse =k_dC_{light}\cos\theta$$
$k_d = diffuse\;intensity$\
$C_{light} = colour\;of\;reflected\;light\;ray$\
$\theta = angle\;between\;normal\;and\;light\;vector$

#### Determining colour of reflected light

First, we have to know how colours work in real life

When light hits an object, some of the light is absorbed and some of the light is reflected back into the viewer's eyes.

The colour of the reflected light determines the colour of the object.

Lets talk about this:

<center>
<img src="https://hackmd.io/_uploads/SyRj39B02.png" alt="normal" width="200"/>
</center>

The colour of this apple is red. $(255, 0, 0)$

This means that the colour of reflected light is red (that's why we see the colour red)
- in real life, the other colors are absorbed by the object, only red is reflected

This also means that all other colours are absorbed by the object (eg. green, blue components) $(0, 255, 255)$

Therefore:

Colour of reflected light = Original colour of light - absorbed colour of light

*Note: the absorbed light colour is the inverse of the reflected light colour.

In a nutshell, the steps to get the colour of reflected light are:

1. Get the colour of the object
2. Invert the colour of the object to get the absorbed colour
3. $C_{light}$ is the difference between the original colour of light ray and the absorbed colour (a.k.a reflected colour)
- you may imagine this as the object "absorbing" intensities of light
- damn i love physics

#### Why Cos?

you may notice the formula has a $cos(\theta)$ and wonder, why cos?

<center>
<img src="https://hackmd.io/_uploads/r1FEt2B03.png">
</center>

The illuminated area determines how "bright" a surface is.

See: Lambert’s Cosine Law

Reference:

<center>


</center>

### Specular

###### ooo shiny

specular reflection of light is the mirror like reflection from a surface

makes objects look smooth / rough

example:

<center>


</center>

left is shinier than the right, therefore left ball looks like it is glossy (or smooth) while the right ball looks rougher

formula:

$$Specular = (V \cdot R)^n \times K_s$$

$V = view\; direction\;(-ray\;direction)$\
$R = reflected\;ray\;direction$\
$n = specular\;coefficient$\
$K_s = specular\;highlight\;intensity$

specular coefficient, $n$ = how big is the specular highlight
specular highlight intensity, $K_s$ = how bright the specular highlight is

note: $n$ and $K_s$ have no general formula and need to be determined by the programmer based on their taste.

in this case, we let the user decide on $n$, and
the formula for $K_s$ was defined as:

ks = 0.24 * log(0.14 * n) + 0.6;

or
$$K_s = 0.24 \times \log(0.14 \times n) + 0.6$$

#### calculating reflected ray

<center>


</center>

$$R = 2(N \cdot L)N - L$$

$$N = normal\;vector$$
$$L = Light\;to\;point\;vector$$

The dot product between 2 vectors returns the projection of the vector onto another vector

### Shadows

if the path of a ray from the object to the light is obstructed, it doesnt do anything because the default ray colour is black $(0, 0, 0)$.
###### yes, ray colors are black when first launched, deal with it, its the side effect of doing backward tracing

in the case where there is another light source, the diffuse and specular colours of that light source will be added to the default ray colour.