To get the most out of this article you’ll need to be familiar with the basics of matrix and vector mathematics. If you’re not, try going over this post that introduces the basics.
Today I’m going to write about one of the coolest little tricks I’ve come across in raytracing. Until I found this trick I thought the maths behind intersection tests was completely crazy. I couldn’t imagine how anyone would be able to code these tests from first principles.
The reason intersection tests get hard is because you’re trying to find the intersection between any ray that can exist, and an object which is at any position and orientation. Even worse, these primitives might also be scaled, so the intersection code can get really deeply unpleasant.
If only we could limit scenes so that we only ever had to raytrace an arbitrary ray against the unit primitive fixed at the origin. The code for standard object intersections at the origin is usually a lot smaller and faster to run, the problem is our scenes are going to lack variation. So here comes the little trick that makes life so much easier… move all objects back to the origin when ray tracing them, and move the ray instead.
To go through this in detail we need to start with a ray definition and the return value from an intersection test. Remember that a ray has both a position P and a direction D, a ray intersection will return a collision point C and a normal N. These locations also exist after we’ve moved everything so that we’re raytracing against an object at the origin. These points will be described as P’, D’, C’ and N’.
First of all lets look at how a translation works using this new method. We’re raytracing an object centred at (2,2,2) from the position P. This is equivalent to raytracing a sphere at (0,0,0) from the position (Px-2, Py-2, Pz-2). The direction D is unchanged because all we’ve done is move the ray position.
P' = T-1 P
D' = D
Once we’ve found a collision we calculate the collision point C’, and the normal to the surface N’. Because we moved the ray by (-2,-2,-2) our collision point won’t be in the right place. Instead, we’ll need to add (2,2,2) to work out the collision as if we’d never used the translation trick. The normal N’ is unaffected.
C = T C'
N = N'
So that’s the easy one, let’s move on to rotation
If you’re raytracing a cube and it’s been rotated by a rotation matrix R, then you can actually raytrace a cube that isn’t rotated by transforming the ray by the opposite rotation matrix R-1. Calculating the inverse of a rotation matrix is relatively easy using a standard matrix inversion function. I’d suggest you go and copy and paste an implementation because they’re extremely tedious to write from first principles.
This time the rotation matrix will be inverted and applied to both the position and the direction.
P' = R-1 P
D' = R-1 D
Similarly once we’ve got a collision point C’ and a normal N’ they both need to be rotated to get them back into the normal positions.
C = R C'
N = R N'
This trick is particularly nice when you’re doing intersection tests against a cube. The reason being that intersection tests against axis aligned planes are very quick. Intersection tests against arbitrary planes take quite a bit more calculation. A Cube is effectively 6 planes with boundaries, so any performance improvements you can make by testing against axis aligned planes will make quite a difference.
And now we’re onto the final type of translation we can do, the scaling transformation, shorthand S. One thing to note here is that the scaling transformation can be different for each axis, i.e. we may want to stretch an object on a single axis to make an elongated primitive. Once again we can do this by scaling the ray itself.
P' = S-1 P
D' = S-1 D
This will now give us a collision point C’ and a normal N’. Getting the collision point back into normal space is done by scaling the point using the scaling matrix.
C = S C'
Far more difficult though is the normal. Something very odd happens here because the normals don’t just need scaling back into normal space, instead we need to apply the inverse scale again!
N = S-1 N'
I’m not going to go into the details of this because it’s pretty mindbending, but my old lecturer neil dodgson has a great explanation that you can find on his website here.
All transformations simultaneously
Now we’ve done all three transformations separately lets put them all back together. We’ll apply the different transformations in this order. Scale, Rotate, Translate.
P' = T-1 R-1 S-1 P
D' = R-1 S-1 D
And then after the transform…
C = S R T C'
N = S-1 R N'
A final optimisation is also possible here by multiplying each separate matrix together so that we can translate each vector using a single matrix multiplication.
Once this code is all written we can now raytrace any simple primitive at an arbitrary position, scale or rotation. This makes it a lot quicker to add additional primitives because the code is straightforwards. There’s also a major testing benefit because the intersection tests themselves become far simpler, and hence easier to test.
Hopefully you found this useful and if anything was unclear or (god-forbid) wrong, please let me know!