# Ray casting through a 3D grid

This topic is 2774 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello.

I'm working on a 3D voxel-like world similar to the Minecraft one, but with much more advanced blocks. I need to implement some kind of ray casting through this world for bullet collision, visibility testing e.t.c. I do have a working implementation a 2D grid ray caster, but it is eye cancer in its purest form and only returns a boolean result. I am having something of a mental breakdown just thinking about a 3D version, so I'll just throw away all my pride and ask this:

Does anyone have a working raycasting function in any language that returns the closest intersected cube in a 3D grid? Alternatively, can anyone think of a solution that does not require 3 ifs per dimension (dx < 0, dx > 0, dx = 0)? We're talking a maximum of 10 rays per frame, most likely somewhat short.

Again, I apologize for my rudeness and ignorance, but I was literally having nightmares about my 2D ray-caster...

EDIT:
This is my "problem": http://pastebin.com/myAqNDev

##### Share on other sites
Hidden
This is the code for Axis-Aligned Bounding Box Intersection:

const float IntersectRayTriangle(const vec3 &v1, const vec3 &v2, const vec3 &v3, const vec3 &origin, const vec3 &dir)
{
float r_dist = 0.0f;
float u = 0;
float v = 0;
const vec3 edge1 = v2 - v1;
const vec3 edge2 = v3 - v1;
const vec3 pvec = Cross(dir, edge2);
const float det = Dot(edge1, pvec);

if (det > -0.00001f)
return 0.0f;

const float inv_det = 1.0f / det;
const vec3 tvec = Sub(origin, v1);

u = Dot(tvec, pvec) * inv_det;
if (u < -0.00001f || u > 1.00001f)
return 0.0f; //Miss

const vec3 qvec = Cross(tvec, edge1);
v = Dot(dir, qvec) * inv_det;
if (v < -0.00001f || (u + v) > 1.00001f)
return 0.0f; //Miss

r_dist = Dot(edge2, qvec) * inv_det;
if (r_dist <= 0.0f)
return 0.0f; //Inside
return r_dist;
}

Hope it helps ;)

This is the code for Axis-Aligned Bounding Box in my projects:

const float IntersectRayAABox(const vec3 &min, const vec3 &max, const vec3 &origin, const vec3 &dir)
{
float tmin = 0.0f;
float dist = 1000000.0f;
float t0 = 0.0f;
float t1 = 0.0f;
for(int axis=0; axis<3; ++axis)
{
t1 = 1.0f / dir.cell[axis];
t0 = (min.cell[axis] - origin.cell[axis]) * t1;
t1 = (max.cell[axis] - origin.cell[axis]) * t1;
tmin = MAX(MIN(t0, t1), tmin);
dist = MIN(MAX(t0, t1), dist);
}
if( tmin > dist )
return 0.0f; //miss
if( tmin > 0.0f )
return dist; //hit
return 0.0f; //inside
}

Just to be clear:
vec3::cell[0] is x
vec3::cell[1] is y
vec3::cell[2] is z

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 11
• 23
• 36
• 16
• 75