# Traces in voxel space

My current project required a method to trace a ray though a voxel space. This is a problem I figured would be pretty much solved and could just copy paste a solution into my codebase and carry on with other issues. Unfortunately not. While there are some source programs that purport to trace a voxel space they are set up for the nuances of that type of voxel and so weren’t immediately amenable to my problem. Furthermore they didn’t really have much of a description of how they were working. So I sat down and worked out how to do it! I’m writing it down here for three reasons: 1) It’s an excuse to blog :) 2) So people smarter than me can point out if anything is wrong (I hope nothing is) 3) So others can use and learn from it

I’m going to explain most of this in a 2D space, but the extension to 3D is trivial and I’ll show it at the end.
Problem:
Given two spaces, a world space (which I’ll measure in millimetres “mm”) and a grid/voxel space (1 voxel = 100 mm) we want to trace a line between two points in world space and get back which voxels are intersected by this line. That is a function (point start, point end) -> list

Step one is to find which voxel our end points are currently in.

If your space can be negative you need to make sure you do the correct division here! -50 / 100 should be -1 not 0. See Euclidean division

Next is to calculate a direction vector between the start and end points

This can be understood as a velocity vector, it’s units are mm/t where t is our arbitrary time unit. This means we travel from start to end in 1t.

Given the direction we call sign (returns -1,0 or 1) on the two direction components. This will be used to step our voxel indices later.

Now we calculate the delta in time space per voxel. That’s a bit of a mouth full so lets take it step by step. First we know that dir is mm/t and that 100mm equals 1 voxel, so if dv=dir/100 then dv is measured in voxel/t. That is how many voxels we move in 1 time unit. If then take the reciprocal of that (dt=1/dv) then dt is measured in t/voxel, or in other words how many time units it takes to move 1 voxel. Bit of rearrangement gives:

While dir could be an integer vector if you world points were integers the calculation here needs to be done with floats.

Moving on we calculate the extents of the starting voxel in world space. This is simply multiplying its index by 100 for the minimum extent and then adding 100 to that for the maximum extent.

Now given this box and the direction we’re tracing (remember dx/dy) we find the distance in each axis from the start point to the next axis plane between voxels. So if start.x is at 570mm and we are moving positively then the distance to the next plane is 600mm - 570mm or 40mm. Same for y.

If moving positively (or not all, doesn’t really matter in that case), the return the distance between start and the max extents else return the distance between start and the min extents.

Those distances are in mm we need them in voxels so a quick division by hundred later.

Again note we need floats here.

Finally the last step of initialisation. Given the distance in voxels to the next voxel in each axis and the time units per voxel again in each axis we work out how far away we are in time space from the next voxel!

tx and ty tell us at what time we cross over into the next voxel in that direction. Given all this information we can loop until we get to the end.

On each iteration of the loop we yield the current voxel (so we will always yield the start voxel). We then check if tx is less than ty, if it is we know we’ve hit the x axis boundary between two voxels. If it’s the last voxel we break out the loop otherwise we add dtx (which tells us how far in t till the next x axis boundary) to tx and add dx (+/-1) to our current voxel. Likewise if ty is less than tx we do the same but in the y axis.

Hopefully that’s a good enough description. If you spot anything wrong please point it out. I’ll leave you with two final things, first the above algorithm for 3D, and second a program for SlimDX.Direct2D to experiment tracing grids.

Green is the start point, red the end point. They are set by left and right click respectively. The blue squares indicate which grid points are hit by the ray getting smaller as they progress.