# All entries for February 2008

## February 11, 2008

### Raytracing: Intersection with a sphere

Follow-up to Raytracing: Intersection with a plane from Nick's blog

Last time I went through intersection of a ray with a plane. Plane’s are all well and good, but you can’t have a ray tracer without spheres everywhere :-)

This article’s another maths-heavy one I’m afraid – more vectors and dot products, this time with a quadratic equation thrown in at the end. Enjoy.

Equation for our ray:

$P = O + Dt$

(P is the position, O is the origin of the ray, D is the direction of the ray, t is the parametric variable)

Equation for a sphere:

$(x - C_x)^2 + (y - C_y)^2 + (z - C_z)^2 = r^2$

(x, y and z represent points around the surface of the sphere, C is the centre of the sphere, r is the radius of the sphere)

As with the plane intersection in the previous article, we solve the equations simultaneously, setting P = (x,y,z).

First we’ll rewrite the sphere equation in vector form. Summing the squares of the x, y and z components is the same as the dot product.

$(P - C) \cdot (P - C) = r^2$

Now substitute in the equation for our ray:

$(O + Dt - C) \cdot (O + Dt - C) = r^2$

We’re trying to solve for t, so let’s break up the above equation using the distributivity of the dot product:

$(O + Dt - C) \cdot O + (O + Dt - C) \cdot Dt + (O + Dt - C) \cdot (-C)= r^2$

Now extract the Dt terms:

$(O - C) \cdot O + (O - C) \cdot Dt + (O - C) \cdot (-C) + (Dt) \cdot O + (Dt) \cdot (Dt) + (Dt) \cdot(-C) = r^2$

Collect like terms:

$(O - C) \cdot O + 2(O - C) \cdot Dt + (O - C) \cdot (-C) + (Dt) \cdot (Dt) = r^2$

Now if we take the scalar t outside of the dot products, and move the r squared to the left hand side we get:

$(O - C) \cdot O + (O - C) \cdot (-C) + t(2(O - C) \cdot D) + t^2(D \cdot D) - r^2 = 0$

Which we can solve using the quadratic formula

Where
$a = D \cdot D = 1 \\ b = 2(O - C) \cdot D \\ c = (O-C) \cdot O + (O-C) \cdot (-C) - r^2 = (O-C) \cdot (O-C) - r^2$

This is where I notice that I’ve reused “C” as a variable name – don’t get confused between “C” for centre” and the “c” in the quadratic formula.

Here I’ve also simplified A and C. A is always 1 in this case, as the direction of our ray “D” is normalised. I’ve also combined C into a single dot product.

Here’s the quadratic formula, which we can simplify by removing the “a” multiplicand.

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

The rest is just a case of plugging in your values.

In order to solve this, you should check the value of the determinant (the bit inside the square root). If it’s < 0 then we have no real solutions, and therefore no intersections.

If the determinant is >= 0, then you need to check both solutions to the equation(-b + ... and -b – ...). We want the closest (lowest value) positive solution. A -ve value means the intersection is behind the ray. Also, if you have one +ve and one -ve solution, then your ray has been cast from inside the sphere.

One final thing worth noting is that there are special methods used to compute quadratic solutions which help to reduce the effect of rounding errors.

Ok, well hope that makes sense. Let me know if you have any questions or comments. Next post will probably cover lighting, so you can actually get planes and spheres in colour!

## February 01, 2008

### Raytracing: Intersection with a plane

Follow-up to Raytracing: A (Very) Brief Introduction from Nick's blog

Last time I mentioned that rays are cast from the eye point. This isn’t much good of course unless you can tell what the ray collides with. So here’s an idea of how to check for the intersection of a ray and a flat plane.

### Representing our objects

Here’s the mathsy bit. If you’ve covered vectors before, then I think it should be reasonably easy to follow. Let me know if you have any questions or spot any mistakes.

#### The Ray

We can represent our ray with an origin, and a direction. Both of these are 3-dimensional vectors. It will come in handy later if our direction is normalised (has a length of 1).

We can then represent the path the ray takes as a parametric equation in t.

$P%7E%3D%7EO%7E%2B%7EDt$

(P is the position, O is the origin, and D is the direction).

Because our direction vector is normalised, t is also the distance the ray has traveled from the origin.

#### The Plane

Representing a plane is a little less intuitive, but we can do it using a (3D) vector to represent the normal to the plane, as well as a value to represent the distance to the origin (in the direction of the normal). Note: this is the distance to the origin at (0,0,0) rather than the origin of the ray mentioned above.

e.g. if we look down the Z-axis from 0 in the positive direction, we could represent a wall 10 units away with a plane with a normal of (0,0,-1) and a distance of 10.

The general equation for a plane is:

$ax%7E%2B%7Eby%7E%2B%7Ecz%7E%2B%7Ed%7E%3D%7E0$

Where a, b and c are the x, y and z components of the normal, and d is the distance to the origin. To make the later equations more concise, we’ll rewrite the plane equation in vector form as:

$P%7E%5Ccdot%7EN%7E%3D%7E-d$

(P is the position, N is the normal, and d is the distance from the origin. Also the dot is the dot product)

#### The Maths

As we’ve already established, t is the distance the ray has travelled from the origin. What we want to do now is find out how far the ray has travelled if/when it intersects our plane. We can do this by solving the ray and plane equations simultaneously.

Starting with the plane equation:
$P%7E%5Ccdot%7EN%7E%3D%7E-d$

Substitute in the ray equation:

$%28O%2BDt%29%7E%5Ccdot%7EN%7E%3D%7E-d$

The dot product is distributive, so we can do this:

$O%7E%5Ccdot%7EN%7E%2B%7E%28Dt%29%7E%5Ccdot%7EN%7E%3D%7E-d$

The dot product also lets us take multiplied scalar arguments outside the brackets like so:

$O%7E%5Ccdot%7EN%7E%2B%7Et%28D%7E%5Ccdot%7EN%29%7E%3D%7E-d$

Now shuffle it around a bit…

$t%28D%7E%5Ccdot%7EN%29%7E%3D%7E-d%7E-%7EO%7E%5Ccdot%7EN$

A bit more…

$t%7E%3D%7E%5Cfrac%7B-d%7E-%7EO%7E%5Ccdot%7EN%7D%7BD%7E%5Ccdot%7EN%7D$

Super! Now we have the distance the ray has travelled when it hits the plane. We can plug this value back into the ray equation to get the intersection point in 3D coordinates too.

If the ray doesn’t hit the plane then both the numerator and denominator of the above equation are 0.

If you’d implemented what I’ve said so far, you would probably have a screen with half white (for the intersection hits) and half black (for the misses). So what we need now is some colour, or a slightly more interesting primitive to draw.

So, next time I’ll probably cover intersection with a sphere or how to colour your object with some simple lighting equations. Any preferences? I’ll probably do them both anyway.

## February 2008

Mo Tu We Th Fr Sa Su
Jan |  Today  | Mar
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29