Jump to content

  • Log In with Google      Sign In   
  • Create Account


Like
21Likes
Dislike

Intersection Math & Algorithms - Learn to Derive

By Vilem Otte | Published Apr 17 2013 09:24 AM in Math and Physics
Peer Reviewed by (Toothpix, Josh Vega, Michael Tanczos)

algorithms point ray linear algebra vector plane normal aabb bounding box intersection sphere

One of the most important group of algorithms inside game engines are intersection algorithms. Even though there are plenty of sites showing code for intersection algorithms, there are only a few describing the math backround behind this, and algorithm derivation. To understand this article you need to know just a bit about linear algebra.

Primitive description


Let's start with a mathematical description of primitives we're going to intersect. For this article I've used just ray (line), plane, sphere, axis-aligned bounding box and triangle ... these should be enough for a basic game engine.

Ray


This is the simplest (and very useful) primitive you can think about. Let us define it with two 4-component numbers, point (further referred as origin) and direction. Mathematically the definition is:

eq.latex?%20%5Cboldsymbol%7Bx%7D=%5Cbold

Where:
  • x represents any point on a line
  • o represents some exact specified point on line (e.g. origin)
  • d represents direction vector of line
  • t is parameter within some specified range
The range specifies whether our line is infinite in both directions (+d and -d), whether it's just in a single direction, or whether it's finite.

Writing a ray object in some programming language is straight-forward of course, you should end up with something like this:

class Ray
{
public:
    float4 origin;
    float4 direction;
	
    <<constructor>>
	
    <<methods>>
};

Constructor and methods are straight-forward (and should be also inline for performance reasons).

Plane


Another basic primitive. There are more ways to define a plane, but we will derive one that is well known and used. What is a plane? It's a point set that contains every such point in space, that when we create vector from that point to our known point on a plane, that vector has to be perpendicular to plane normal. And we know that perpendicular vectors are those whose dot product is equal to zero. So:

eq.latex?%20%5Cvec%7B%5Cboldsymbol%7Bn%7

Where:
  • n is unit vector in the plane normal direction
  • x is every point on the plane
  • p is our specified point on the plane
Expanding this yields:

eq.latex?%20n_%7Bx%7D%5Ccdot(x-p_%7Bx%7D
eq.latex?%20n_%7Bx%7D%5Ccdot%20x%20+%20n

Substitute:

eq.latex?%20-(n_%7Bx%7D%5Ccdot%20p_%7Bx%
eq.latex?%20n_%7Bx%7D=a
eq.latex?%20n_%7By%7D=b
eq.latex?%20n_%7Bz%7D=c

And we get something very familiar:

eq.latex?%20a%20%5Ccdot%20x%20+%20b%20%5

Which is a plane equation (so we proved that the definition we use is actually a plane). Definition in programming language could be like this:

class Plane
{
public:
    float4 point;
    float4 normal;

    <<constructor>>
	
    <<methods>>
};

A very simple definition. Let's jump ahead.

Sphere


Yet another basic primitive, that is widely used. The definition is surface containing all points in distance from sphere's center less-or-equal to sphere's radius. We will define it using an analytic equation:

eq.latex?%20(x%20-%20p_%7Bx%7D)%5E2%20+%

Where:
  • x, y and z are coordinates of point in sphere
  • p represents sphere's center
  • r represents sphere's radius
A sphere class is again very trivial:

class Sphere
{
public:
    float4 center;
    float radius;
    
    <<constructor>>
    
    <<methods>>
};

So much for sphere; simple, yet very useful primitive.

Axis-aligned Box


From here on I'll call this one just AABB (which stands for Axis-Aligned Bounding Box). Definition is very simple, as we work in Cartesian coordinate system, we have perpendicular axes X, Y and Z - AABB is defined as volume between minimum and maximum point in this system, the sides are made by planes orthogonal to planes formed by all 3 combinations of 2 base axis (XY, XZ and YZ). Mathematically we can define it as:

eq.latex?%20%5Cbold%7Bmin_%7Bp%7D%7D%20%

Where:
  • min_p stands for AABB minimum point
  • max_p stands for AABB maximum point
  • x represents points inside AABB
In programming language it can look like:

class AABB
{
public:
    float4 min_p;
    float4 max_p;
    
    <<constructor>>
    
    <<methods>>
};

Let's jump ahead to last object we're going to use.

Triangle


The first and only primitive in this article that is going to be defined by more than 2 values, yet very important. Most of the game worlds are described by triangles, most of the simulation use objects described as triangles, and every more (or less) complex 3D object can be decomposed into triangles. They're awesome; as opposed to other boring N-gons, triangles are never concave!

Let's define triangle with 3 points, then any point on triangle can be described as:

eq.latex?%20%5Cbold%7Bx%7D%20=%20%5Cbold

With conditions:

eq.latex?%20%5Calpha+%5Cbeta+%5Cgamma=1,

Where:
  • x is every point in triangle
  • A, B, C are points defining triangle
  • a, ß, ? are so called barycentric coordinates (e.g. parameters in the equation above)
A triangle inside of a program could be defined as:

class Triangle
{
public:
    float4 p[3];
    
    <<constructor>>
        
    <<methods>>
};

Intersections


So now that we have defined some of the basic primitives, it's time to derive intersection equation and also intersection algorithms between the primitives. As I want to keep the article short (and I don't want to storm you with zillion of equations and exhausting equation solving), I will just show you 4 derivations - Ray-Plane (analytic derivation), Ray-Sphere (geometric derivation), Ray-AABB (tricky derivation) and Ray-Triangle (more complex analytic derivation). You should get an idea of how the intersection equation can be derived and in the end you should be able to derive the rest of them on your own.

Ray-Plane intersection


I will derive Ray-Plane intersection analytically, as this is one of the most simple approaches to the derivation. When we want to derive some intersection algorithm analytically, we should write equations of those 2 objects right away, so (I intentionally used commonly known plane equation, instead of our definition):

eq.latex?%20%5Cboldsymbol%7Bx%7D=%5Cbold
eq.latex?%20a%20%5Ccdot%20x%20+%20b%20%5

Now we're looking for a point that lies on both, the ray and the plane - so we're looking for x. So we first write the first equation in scalar form:

eq.latex?%20x=o_%7Bx%7D+t%5Ccdot%20d_%7B
eq.latex?%20y=o_%7By%7D+t%5Ccdot%20d_%7B
eq.latex?%20z=o_%7Bz%7D+t%5Ccdot%20d_%7B

Let's substitute these 3 to plane equation:

eq.latex?%20a%20%5Ccdot%20(o_%7Bx%7D+t%5
eq.latex?%20a%20%5Ccdot%20o_%7Bx%7D+%20a
eq.latex?%20a%20%5Ccdot%20t%20%5Ccdot%20
eq.latex?%20t%20%5Ccdot%20(a%20%5Ccdot%2
eq.latex?%20t%20=%20-%7Ba%20%5Ccdot%20o_

It's time to reverse substitution we did when "deriving" plane equation, e.g.:

eq.latex?%20-(n_%7Bx%7D%5Ccdot%20p_%7Bx%
eq.latex?%20n_%7Bx%7D=a
eq.latex?%20n_%7By%7D=b
eq.latex?%20n_%7Bz%7D=c

eq.latex?%20t%20=%20-%7B%7Bn_%7Bx%7D%20%

And transformed to vector form we get:

eq.latex?%20t%20=%20%7B-%7B%7B%5Cvec%7B%

But we can optimize this a little bit:

eq.latex?%20t%20=%20%7B-%7B%7B%5Cvec%7B%

Voila, that's what we have been looking for! So basically we need just subtraction, 2 dot products and 1 division. In program this can look like (assuming we want to intersect planes in front of ray origin in direction of ray):

bool IntrRayPlane(const Ray* r, const Plane* p, float* t)
{
    float denom = dot(p->normal, r->direction);
    
    // Test whether ray and plane aren't parallel
    if(fabsf(dotND) < EPSILON)
        return false;
    
    *t = -(dot(p->normal, r->origin - p->point) / denom);
    return ((*t) > 0.0f);
}

Almost as simple as the equation. Let's jump ahead, time for spheres!

Ray-Sphere intersection


I could perform analytic derivation like in the Ray-Plane intersection derivation, although Ray-Sphere intersection is just one of the cases that can be easily derived using geometry. Let's start with an image:

gallery_102163_282_11168.jpg

We're now looking for 2 distances:

eq.latex?%20t_%7B0%7D%20=%20%7C%5Cbold%7
eq.latex?%20t_%7B1%7D%20=%20%7C%5Cbold%7

Finding C-O is quite straightforward, it's just simple:

eq.latex?%20%5Cbold%7BL%7D=%5Cbold%7Bp%7

Another thing we need to find is distance along the ray to point X, but as we know ray direction, it's just simple projection of L.

eq.latex?%20t_x%20=%20%5Cbold%7BL%7D%5Cc

Right now we should look again at the image, we can see 3 important right angle triangle, one formed by {d, OX and OC}, another one {d, r, PX} and last one {d, r, P'X}. We need to know distance PX (respectively P'X, they're equal). So let's use Pythagorean theorem twice:

eq.latex?%20d%5E2%20=%20%5Cbold%7BL%7D%5
eq.latex?%20t_%7BPX%7D=%5Csqrt%7Br%5E2-d

And our 2 hit distances are:

eq.latex?%20t_%7B0%7D%20=%20t_%7Bx%7D%20
eq.latex?%20t_%7B1%7D%20=%20t_%7Bx%7D%20

Time for the code (searching just nearest hit):

bool IntrRaySphere(const Ray* r, const Sphere* s, float* t)
{
    float rad2 = s->radius * s->radius;
    float4 L = s->center - r->origin;
    
    float tPX = dot(L, r->direction);
    if(tPX < 0.0)
        return false;
    
    float dsq = dot(L, L) - tPX * tPX;
    if(dsq > rad2)
        return false;
    
    float thit = sqrt(rad2 - dsq);
    *t = tPX - thit;
    if(*t < 0.0f)
        *t = tPX + thit;
    
    return ((*t) < 0.0f);
}    

Just a side note. Analytic derivation in this case is also very trivial, you will end up with quadratic equation, where determinant is negative in case of no hit, zero in case of single point hit (e.g. tangent line), and positive in case of secant.

Let's jump ahead to boxes!

Ray-AABB intersection


Another important one, although a bit tricky. Let's start with an image again:

gallery_102163_282_5470.png

You can see, that box in 2D is formed by 2 slabs, horizontal and vertical. 3D is analogous to this, but of course it's formed by 3 slabs. For each slab we want to find minimum distance and maximum distance, e.g.:

eq.latex?%20%5Cbold%7Bt_%7Bmin%7D%7D%20=
eq.latex?%20%5Cbold%7Bt_%7Bmin%7D%7D%20=

Where a and b represents minimum (respectively maximum) point of our AABB. What we get is the minimum and maximum distance to each slab. Now we have to correctly order the distances along the ray direction, this is quite simple:

eq.latex?%20%5Cbold%7Bt_%7Bnear%7D%7D%20
eq.latex?%20%5Cbold%7Bt_%7Bfar%7D%7D%20=

Where min/max is defined as:

eq.latex?%20min%28%5Cbold%7Ba%7D,%20%5Cb
eq.latex?%20max%28%5Cbold%7Ba%7D,%20%5Cb

Entry/exit point is then defined as maximum of near distances (see the image), thus:

eq.latex?%20enter%20=%20hmax%28%5Cbold%7
eq.latex?%20enter%20=%20hmin%28%5Cbold%7

Where hmax/hmin function is horizontal minimum/maximum, defined as:

eq.latex?%20hmin%28%5Cbold%7Ba%7D%29%20=
eq.latex?%20hmax%28%5Cbold%7Ba%7D%29%20=

Of course a hit only occurs when the exit point is larger than zero, and the exit point is further than the entry point (if it isn't, we missed the AABB). Time to code:

bool IntrRayAABB(const Ray* r, const AABB* b, float* enter, float* exit)
{
    float4 tmin = (b->minimum - r->origin) / r->direction;
    float4 tmax = (b->maximum - r->origin) / r->direction;
    
    float4 tnear = f4min(tmin, tmax);
    float4 tfar = f4min(tmin, tmax);
    
    *enter = max(max(tnear.x, 0.0f), max(tnear.y, tnear.z));
    *exit = min(tfar.x, min(tfar.y, tfar.z));
    
    return (*exit > 0.0f && *enter < *exit);
}

It can be a little more optimized, although I'll leave that to reader as an exercise.

Ray-Triangle intersection


I'd like to say, there is like a dozen of ways to intersect a ray with a triangle. Lots of them don't even use a triangle defined by 3 points, and re-define it in better suited way. I'll show you how to derive plain good old Barycentric test with one huge advantage, you don't have to precompute a triangle in any way, just use the standard definition with 3 points.

Let's start with equations we already have:

eq.latex?%20%5Cboldsymbol%7Bx%7D=%5Cbold
eq.latex?%20%5Cbold%7Bx%7D%20=%20%5Cbold

The triangle equation actually is equal to this:

eq.latex?%20%5Cbold%7Bx%7D%20=%20%5Cbold

And let's arrange it like this:

eq.latex?%20%5Cbold%7Bx%7D%20=%20%5Cbold

Substituting line equation for x yields:

eq.latex?%20%5Cbold%7Bo%7D%20+%20t%20%5C
eq.latex?%20-t%20%5Ccdot%20%5Cvec%7B%5Cb

Those are 3 equations with 3 unknown variables. Instead of thinking about some more clever way, let's solve it in brute force manner with Cramer's rule. First let's re-arrange it to better form:

eq.latex?%20%5Cbegin%7Bpmatrix%7D-%7B%5C

For clarity let's substitute e1 for B-A, e2 for C-A and p for o-A.

eq.latex?%20%5Cbegin%7Bpmatrix%7D-%7B%5C

Now it's time to apply Cramer's rule, e.g.:

eq.latex?%20%5Cbegin%7Bpmatrix%7Dt%5C%5C

But matrix determinant can be written as scalar triple product, so:

eq.latex?%20%5Cbegin%7Bpmatrix%7Dt%5C%5C

I know this might look scary right now, but it really is simple. For those that understand code easier than math I also add code:

bool IntrRayTriangle( const Ray* r, const Triangle* t, float* thit, float* u, float* v)
{
    float4 e1 = t->v[1] - t->v[0];
    float4 e2 = t->v[2] - t->v[0];
    
    float4 pvec = cross(r->direction, e2);
    
    float det = dot(e1, pvec);
    if(det > -EPSILON && det < EPSILON)
        return false;
    
    float inv_det = 1.0f / det;
    
    float4 tvec = r->origin - t->v[0];
    *u = dot(tvec, pvec) * inv_det;
    if(*u < 0.0f || *u > 1.0f)
        return false;
    
    float4 qvec = cross(tvec, e1);
    *v = dot(r->direction, qvec) * inv_det;
    if(*v < 0.0f || *u + *v > 1.0f)
        return false;
    
    *thit = dot(e2, qvec) * inv_det;
    
    return (*thit > 0.0f);
}

Conclusion


Intersection algorithms, as I've said, are core algorithms for practically every game engine! And not just game engines, ray-tracers, physics simulators, collision detection libraries, even some AI simulations use them, etc. If you made it here, then I have to say thanks for reading my article, and I hope you've learned something new.

9 Apr 2013: Initial release



License


GDOL (Gamedev.net Open License)




Comments

I did some grammar clean up but didn't mess around too much with the various definitions. Anyone with a better understanding of the terms can help the author clean those up if they feel it necessary.

Is float4 defined as a record of two floats? If it is, it would be good if you explained it, even if it is obvious.

It is not clear in the article why 4-dimensional vectors are used to represents 3D points and vectors. Even if it is quite common in the game and computer graphics industry, it is not very common in other fields. Since this article is about computing intersections between very simple mathematical objects, I wouldn't assume the reader is familiar with that convention.

Moreover, I would fix the notation to make it more consistent. For example, points are represented using uppercase letters in some equations and using lowercase letters in others. Vectors do sometimes have an arrow above the letter and sometimes not... 

Ad float4 - using float4 to represent 3D points and vectors is quite common, there are 2 main reasons why I've chosen float4 representation of 3D points and vectors (and why you should always prefer it).

 

1st - performance (computation) reasons, I bet most of you know that there is SSE in CPUs today (since Pentium III - thats 1999, 14 years), using float4 (even defined as only struct of 4 floats) with few compiler flags (-mfpmath=see for gcc for example) will vectorize the code, resulting in better performance.

 

2nd - basically this code can also be used on GPU (and it's quite common to do ray tracing on GPU these days). GPU is huge SIMD machine and works mostly with 4-byte, 16-byte or 64-byte primitives (e.g. float, float4, float16). Now what if you want to transfer a ton of rays defined with float3 origin & direction, you either do it through new struct containing float[3]'s and experience a lot of cache misses (e.g. low performance), or use float4 in the first place. You could convert it before sending too, but that can waste even more time than cache misses on GPU.

 

Anyway you're right that this should be added into article.

 

Ad points, vectors notation - it's common in central Europe countries to represent points as bold symbols (either uppercase or lowercase), vectors as bold symbol with an arrow. I though don't know what exactly are other conventions (but I know they differ (even ISO standard for this allows for several different ways), and some differ a lot) - but I know this might be confusing.

 

F.e. according to ISO 80000 you can express point with any of these:

latex.php?latex=%5Cbold%7Bx%7D~~~%5Cbold

And you can express vector with any of these:

latex.php?latex=%5Cvec%7Bv%7D~~~%5Cbold%

 

So in this case I don't get idea, why it was *standardized* (because this standard actually doesn't standardize anything).

 

Anyway, if there is some reference for notations here on gamedev (or even another article just using some math notations), please post a link there and I'll update the notations to match.

 

Ad grammar - Thanks for clean up. I'm still working on my English.

I know why you have decided to use 4D vectors to represents both points and vectors. I was simply suggesting to include this motivation in the article.

 

You can represents points and vectors in several different ways. It isn't very important which one you decide to use. But you should be consistent. If you decide that a point is represented using an uppercase bold letter, all points should use this notation. 

Then may I make a suggestion?

 

Since this article is about algorithms, why not drop all the performance related aspects in your code (e.g. float4), and the language specific constructs (e.g. class, public), and present the algorithms in a more generic language (some sort of pseudo code)?

 

Again, it is just a suggestion. But I think the article can be understood by more people if it is more generic.

I think your plane representation can be made simpler by directly using the four dimensional vector n = (a, b, c, d) (it is actually a point in a 3-dimensional projective space). It is more compact and less ambiguous (it is unique up to scaling). Moreover, if you represent your 3D points using 4D vectors in the form (x, y, z, 1) and 3D vectors in the form (x, y, z, 0) as it is common in affine (and projective) geometry, the plane equation simply becomes dot(n, P) = 0 where P = (x, y, z, 1). dot is clearly the 4D dot product.

 

By substituting the ray equation in this new equation you then obtain

 

dot(n, O + t*d) = dot(n, O) + t*dot(n, d) = 0

 

and finally

 

t = - dot(n, O)/dot(n, d).

BTW, in AABB - Ray algorithm.. Should't it be:

 

float4 tnear = f4min(tmin, tmax);
float4 tfar = f4max(tmin, tmax);

 

??


Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS