go to: [part 4 ][home]

Implementing Ray Tracing on GPU
Part 3

Creating the Uniform Grid

To accellerate ray tracing, a spatial data structure is used. The uniform grid is one of the best structures to map to the GPU, since traversal doesn't require a lot of texture access. In a uniform grid the scene is uniformly divided into voxels and those voxels containing triangles or part of a triangle obtain a reference to this triangle.

The uniform grid structure of the scene is created on CPU and stored in textures. To create the uniform grid, this simple approach can be used:
For all triangles T[i] in the scene:
1. Calculate the bounding cells (b1, b2) of Triangle T[i]
2. Test triangle-box intersection: T[i] with every cell C[j] in (b1, b2)
3. If triangle-box intersection returned true, add a reference of T[i] to C[j].

Traversing the Uniform Grid

John Amanatides and Andrew Woo presented a way to traverse the grid fast. With slight modifications, this algorithm can be mapped to the GPU.

Uniform Variables
g1 Start point (in world coordinates) of the grid.
len Vector containing voxel size in x,y, and z direction.
curpos Current position on ray (world coordinates)
raydir Direction of the ray.
voxel Current voxel position


During the initialization the voxel-position of the origin of the ray is calculated, this can be done with the function “world2voxel” which transforms world coordinates (x, y, z) to voxel coordinates (i, j, k).

Function: World coordinate to voxel coordinate
vec3 world2voxel (vec3 world )
   vec3 ijk = ( world − g1 ) / _len; // component−wise division
   ijk = INTEGER (ijk);
   return ijk;

Functions: Voxel coordinates to world coordinates
// transform voxel coordinates to world coordinates
float voxel2worldX( float x) { return x _len.x + g1.x; }
float voxel2worldY( float y) { return y _len.y + g1.y; } float voxel2worldZ( float z) { return z _len.z + g1.z; }

Next step is to calculate the positions at which the ray crosses the voxel boundaries in x-, y-, and z-direction.
The positions are stored in variables tMaxX, tMaxY, and tMaxZ.
if (raydir.x < 0.0) tMax.x=(voxel2worldX(voxel.x) − curpos.x) / raydir.
if (raydir.x > 0.0) tMax.x=(voxel2worldX(( voxel.x+1.0)) − curpos.x) / raydir.x;
if (raydir.y < 0.0) tMax.y=(voxel2worldY(voxel.y) − curpos.y) / raydir.y;
if (raydir.y > 0.0) tMax.y=(voxel2worldY((voxel.y+1.0)) − curpos.y) / raydir.y;
if (raydir.z < 0.0) tMax.z=(voxel2worldZ(voxel.z) − curpos.z) / raydir.z;
if (raydir.z > 0.0) tMax.z=(voxel2worldZ((voxel.z+1.0)) − curpos.z) / raydir.z;


tDeltaX, tDeltaY , tDeltaZ indicate how far along the ray must move to equal the corresponding length (in x,y,z direction) of the voxel (length stored in len).
Another set of variables to calculate are stepX, stepY , stepZ which are either −1 or 1 depending whether the voxel in direction of the ray is incremented or decremented.
To reduce the number of instructions, it is possible to define variables outX, outY , outZ that specifiy the first value that is outside the grid, if negative −1 or if positive _r.

stepX = 1.0; stepY = 1.0; stepZ = 1.0;
outX = _r; outY = _r; outZ = _r;
if (raydir.x < 0.0) {stepX = −1.0; outX = −1.0;}
if (raydir.y < 0.0) {stepY = −1.0; outY = −1.0;}
if (raydir.z < 0.0) {stepZ = −1.0; outZ = −1.0;}

Now the actual traversal can start. It is looped until a voxel with non-empty "Voxel Index" is found or if traversal falls out of the grid.
bool c1 = bool (tMax.x < tMax.y );
bool c2 = bool (tMax.x < tMax.z );
bool c3 = bool (tMax.y < tMax.z );
if (c1 && c2)
voxel.x += stepX;
if (voxel.x==outX ) voxel.w=−30.0; // out of voxel space
tMax.x += tDelta.x;
else if (((c1 && ! c2) | | (! c1 && ! c3 )))
voxel.z += stepZ;
if (voxel.z==outZ) voxel.w=−30.0; // out of voxel space
tMax.z += tDelta.z;
else if (! c1 && c3)
voxel.y += stepY;
if (voxel.y==outY ) voxel.w=−30.0; // out of voxel space
tMax.y += tDelta.y;

//check if (voxel.x, voxel.y, voxel.z) contains data

go to: [part 4 ][home]