How do I find the intersection of a line and a cube

[mirhagk]

I have a 3d line defined as a point and a direction (actually its a ray), and a cube defined as a 3d point and a size (cubes have same dimensions for all 3 sides so only one value is needed).

How would I determine whether, and more importantly where the line intersects with the cube. Any help at all is appreciated, but some good pseudocode will be very helpful (don't bother with actual code, because I'm writing this in assembly... so even if you could demonstrate, it wouldnt be much help)

I will offer lots of bits or w/e if someone makes a tutorial on this, or even just a really good explanation. Thank you so much for anyone who responds.

[bbi5291]

I don't see how one point and a side length can unambiguously specify a cube. Unless, for example, the cube is axis-aligned and you've specified the vertex with lowest x-coordinate, y-coordinate, and z-coordinate or something like that. But anyway, this is just a math problem, and the math is not difficult, but the case-bash is very annoying. The cube has six faces. We can determine separately whether the ray intersects each face. To do so, we consider each face in turn. The face is a square located in some plane, whose equation can be easily found. The ray is also half of some line, whose equation can also be easily found. Find the intersection of the line and plane by solving their equations simultaneously. There are three possibilities:

1. Solving the equations succeeds because no division by zero is indicated during any step. A unique point is obtained as the intersection. All you have to do is check whether it lies on the appropriate face (as opposed to elsewhere on the plane) and on the right side of the line (that is, not on the wrong side of the endpoint of the ray).

2. Solving the equations fails because a nonzero number must be divided by zero. In this case the line and plane are parallel and don't intersect at all.

3. Solving the equations fails because one of the coordinates ends up being 0/0. In this case the line lies in the plane of the face. So either the line lies along the face, or it misses the face completely. To determine which is the case, you have to determine whether the line intersects any of the edges surrounding that face. (You must treat the edge as a line segment, not a line.) If not, there is no intersection with the face. If so, it's easy to see that the line must usually intersect the face at exactly two points, and are three cases to consider:

3a. Both intersection points are on the correct side of the ray's endpoint. Then the intersection of the ray with the face is a line segment between two points on the face's perimeter.

3b. One intersection point is on the correct side of the ray's endpoint. The endpoint is inside the face, so the intersection is a line segment between the endpoint and a point on the face's perimeter.

3c. Neither intersection point is on the correct side of the ray's endpoint. There is no intersection.

However, there is a special case in which the line exactly passes through one of the vertices. This is handled in essentially the same way, though.

Happy coding

[mirhagk]

yes I forgot to mention that the cube is axis aligned, and I figured I could do some retardly complex plane math (making it even more difficult because I need to find the intersection, then ensure that the intersection actually happens within that face and not at some arbitrary point) but I was hoping there was some special case math for an axis aligned cube, I dunno just seemed like there should be.

Anyways correct me if I'm wrong,

Turing:

SolveTwoEquations if (worked) then     if (pointIsOnRay) then          %we have the point, we're done     end if elsif (failedDivNumByZero) then     %no intersection elsif (failedDivZeroByZero) then      if (lineIntersectsEdges) then           if (BothPointsOnRay) then                 %get closest           elsif (OnePointOnRay) then                 %use that one, done           else                 %no intersection           end if      end if end if

However I don't get what you mean by the line passing through the vertices, like wouldn't that show up in the face analysis (like it would detect the intersection while I'm detecting if it intersects any faces)

[bbi5291]

For your first case, where you check if pointIsOnRay, you also have to check if it's on the face. Other than that it looks good.

[mirhagk]

http://www.permadi.com/tutorial/raycast/index.html

This article kinda confuses me a little, and isn't DIRECTLY what I want, but it seems to have the way to do this without super complex planar math, and even better, without even having to unproject rays from a matrix (since a projection matrix is really unnecassary in a game that only draws using rays).

The part with the floors is the part I'm interested in, after all voxel rendering only differs from old school ray casting by the size of the shapes right?

Anyways, I'll try to make sense of this article, cuz it seems like the better way

[CodeMonkey2000]

That applies if you assume that the world is a 2d matrix made up of NxN squares. Think of something like a grid paper.

[mirhagk]

but since every cube is axis aligned, couldn't I think of a voxel world as 3d grid paper and use the same type of concept?

[Homer_simpson]

not sure if this article is what ur looking for. http://www.student.kuleuven.be/~m0216922/CG/raycasting.html

[mirhagk]

actually that is kinda a much simpler version of the one I posted, which is awesome, thank you very, very much. I can reapply this to a 3D map once I'm doing working through it, should work the same I think.