Ray casting through a 3D grid

This topic is 2464 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

1. 1
2. 2
3. 3
Rutin
23
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 12
• Forum Statistics

• Total Topics
633653
• Total Posts
3013166
×