Geometry and raytracing: a cookbook

From Create52 Cookbook

1 Warning
2 Note on dimensions
3 Reminder of some basics
- 3.1 Dot product
- 3.2 Cross product
4 Component and perpendicular component
5 Rotating a vector towards another vector
6 Reflection
7 Refraction
- 7.1 Calculating refracted ray
8 Intersection of a line with various primitives
- 8.1 Plane
- 8.2 Sphere
9 Related equations
- 9.1 Shortest distance from point to a line
10 Possibly unrelated

Warning

This page will cause you to eat your own head.

Note on dimensions

Unless otherwise mentioned, the details below apply to any amount of dimensions. For example, the equation for rotating a vector towards another vector works just as well in 2, 3, and 57 dimensions.

Reminder of some basics

Dot product

The dot product of two vectors is calculated as the sum of the products of the two vector's corresponding components:

$\underline{a} . \underline{b} = \sum_{i=1}^n a_i b_i$

So, for example, for a three dimensional dot product we have:

$(a_1, a_2, a_3) . (b_1, b_2, b_3) = a_1 b_1 + a_2 b_2 + a_3 b_3 \;$

The following useful identity holds for the dot product:

$\underline{a} . \underline{b} = \left | \underline{a} \right | \left | \underline{b} \right | \cos \theta$

where $θ$ is the angle between $\underline{a}$ and $\underline{b}$ .

Cross product

The cross product of two three-dimensional vectors is calculated as the following determinant:

$\underline{a} \times \underline{b} = \det \begin{bmatrix} \underline{i} & \underline{j} & \underline{k} \\ a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3 \end{bmatrix}$

which expands as:

$\underline{a} \times \underline{b} = (a_2 b_3 - a_3 b_2, \; a_1 b_3 - a_3 b_1, \; a_1 b_2 - a_2 b_1)$

The cross product is a vector which is at right angles to both $\underline{a}$ and $\underline{b}$ , and which has magnitude:

$\left | \underline{a} \times \underline{b} \right | = \left | \underline{a} \right | \left | \underline{b} \right | \sin \theta$

Component and perpendicular component

Component of $\underline{a}$ in direction of $\underline{b}$ (i.e. projection of $\underline{a}$ onto $\underline{b}$ ) is a vector defined as:

$\underline{a} \nmid \underline{b} = \frac{ \underline{b} }{ \left | \underline{b} \right | ^2} \; \underline{a} . \underline{b}$

(Derivation: draw a picture, and consider the dot product equation containing $cosθ$ .)

Note that if there is more than 90 degrees between $\underline{a}$ and $\underline{b}$ , the $\underline{a} \nmid \underline{b}$ function gives a vector in the direction of $\underline{a}$ , not $\underline{b}$ .

The perpendicuar component of $\underline{a}$ in direction of $\underline{b}$ (i.e. projection of $\underline{a}$ onto plane with normal $\underline{b}$ ) is a vector defined as:

$\underline{a} \perp \underline{b} = \underline{a} - \underline{a} \nmid \underline{b}$

Note that $\underline{a} \nmid \underline{b}$ and $\underline{a} \perp \underline{b}$ are at right angles to each other, and together they compose $\underline{a}$ , i.e. $\underline{a} = \underline{a} \nmid \underline{b} + \underline{a} \perp \underline{b}$ .

Rotating a vector towards another vector

This is accomplished by finding the component and perpendicular components and then using the 2D equation for rotation.

If vector being rotated towards is $\underline{r}$ (reference vector), and the vector being rotated is $\underline{v}$ , and the angle of rotation is $θ$ , then let:

$\underline{y} = \underline{v} \nmid \underline{r}$

$\underline{x} = \underline{v} \perp \underline{r}$

then find the rotated vector as:

$\underline{v}^\prime = (\cos \theta + \sin \theta) \underline{x} + (\cos \theta - \sin \theta) \underline{y}$

Reflection

If $\underline{i}$ is the incident (incoming) ray and $\underline{n}$ the surface normal (which is pointing in the direction the incident ray is coming from!), the reflected ray is given by

$\underline{r} = 2 (\underline{i} \nmid \underline{n}) - \underline{i}$

Refraction

$Image:refract1.png$

Snell's law of refraction:

$\frac{\sin \theta_1}{\sin \theta_2} = \frac{n_2}{n_1}$

(The refractive index, n, is a measure of the optical density of a material - i.e. it is inversely proportional to the velocity of light in the material.)

When $n 1 > n 2$ , total internal reflection happens at angles greater than the critical angle, given by:

$\theta_c = \arcsin \frac{n_2}{n_1}$

Calculating refracted ray

$Image:refract2.png$

Firstly calculate $\underline{r}_p$ (due to Snell):

$\underline{r}_p = - \frac{n_1}{n_2} \; \underline{i} \perp \underline{n}$

Note that if $| \underline{r}_p | > | \underline{i} |$ , total internal reflection (T.I.R.) has occurred and you can forget about refraction. Ooh yeah.

If T.I.R. has not occurred, calculate refracted ray as:

$\underline{r} = \underline{r}_p - \underline{\hat{i}}_n \sqrt{| \underline{i} | ^2 - | \underline{p} | ^2}$

Intersection of a line with various primitives

In the following text, we are adopting the parametric equation of a line: a line is defined by a position vector of a point on the line, $\underline{s}$ , and a direction vector, $\underline{d}$ , such that any point on the line is expressible as $\underline{p}_{\lambda}$ whereby:

$\underline{p}_{\lambda} = \underline{s} + \lambda \underline{d} \quad (\lambda \in \mathbb{R})$

The following sections show how to find $λ i$ for the point(s) of intersection of a line with various primitives. Note that traps are listed - these are conditions where no solution can be found. The geometrical intrepretation of the trap is also given.

Plane

Plane normal is $\underline{n}$ , and $\underline{t}$ is a point on the plane.

$\lambda_i = \frac{\underline{n}.(\underline{t}-\underline{s})}{\underline{n}.\underline{d}}$

Trap: $\underline{n}.\underline{d}=0$ , which corresponds to the line direction being at right angles to the plane normal. (In this situation, the line intersects the plane in either zero or infinitely many places.)

Scope: eqn applies to any line and plane in N dimensions.

Derivation: A point $\underline{p}$ lies on the plane when the vector from $\underline{p}$ to $\underline{t}$ is at right angles to the plane normal $\underline{n}$ , hence we can write $(\underline{t} - \underline{p}).\underline{n} = 0$ . Then substitute in $\underline{s} + \lambda \underline{d}$ for $\underline{p}$ and solve for $λ$ .

Sphere

Sphere has radius $r$ and is centered at the origin. There can be 0, 1 or 2 intersections. The intersections are found as the real solution(s) to the following quadratic:

$0 = (\left | \underline{d} \right | ^2)\lambda^2 + (2 \left | \underline{s} \right | \left | \underline{d} \right |) \lambda + (\left | \underline{s} \right | ^2 - r^2)$

Reminder: solutions to a quadratic are found by:

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

with $a$ , $b$ and $c$ being the $λ 2$ , $λ$ and constant terms respectively of aforementioned quadratic.

The amount of real solutions are dictated by the value of the discriminant, $Δ = b 2 - 4 a c$ , as follows:

$\begin{cases} 0 & \mbox{if } \Delta < 0 \mbox{ (lines misses sphere)}\\ 1 & \mbox{if } \Delta = 0 \mbox{ (lines intersects sphere once at tangent)}\\ 2 & \mbox{if } \Delta > 0 \mbox{ (lines intersects sphere twice)} \end{cases}$

Trap: see comments about about the discriminant $Δ$ .

Derivation: solve the following sphere equation for $λ$ :

$\left | \underline{s} + \lambda \underline{d} \right | = r$

Related equations

Shortest distance from point to a line

For a point $\underline{p}$ , this is given by

$d_{min} = (\underline{p} - \underline{s}) . \underline{\hat{d}}$

Derivation 1: use dot product equation to find size of component of $(\underline{p} - \underline{s})$ perpendicular to $\underline{d}$ .

Derivation 2: Translate $\underline{p}$ such that $\underline{s}$ is at the origin, then rotate things so that $\underline{d}$ runs horizontally. Then the distance is the y coordinate of $\underline{p}$ in this system of coordinates.

Possibly unrelated

For a (hyper)sphere of any dimension, radius $r$ , and two points on its surface $\underline{a}$ and $\underline{b}$ , the shortest distance between the points on the surface of the (hyper)sphere is:

$d = 2r \arcsin \left ( \frac{\left | \underline{b} - \underline{a} \right |}{2r} \right )$