Fast query for closest point between line and AABB in 3D

Question

How can I efficiently find the closest points between an infinite line and an AABB in 3D space?

I have a naive solution that involves finding the closest points to all 12 edges of the AABB to the line and picking the closest pair, which works, but is not very performant. I need something faster for my use case.

In my search, I've found plenty of literature on finding collisions between lines and AABBs, and several implementations of the naive algorithm. But is there anything better?

Answer 1

Your line will be something like cv + p, where v is the direction vector and p a point it passes through.

The direction to the closest point on your box from the line will be perpendicular to the line, so get a pair of normals to v, say n and m.

The actual closest point will be a linear combination of n and m with a point on the line. (You start from a point on the line, and follow some perpendicular to the line off to your destination point, every perpendicular to the line is a linear combination of the normals through that point.)

So solve an + bm + cv + p = s, where s is each corner of your box.

Without loss of generality, we can assume v does not have zero in either of its first two components. (If it has one, permute the indices to make it the third. If it has two, this becomes a much simpler problem, which we can solve separately.)

That means we can take n = (1, 0, N) and m = (0, 1, M).

Since n * v = 0 and m * v = 0, we can find N = -v1/v3 and M = -v2/v3. We are not going to do all this substitution, it is enough to just know those are numbers, not variables.

Now we want to solve an + bm + cv = s - p. Which we can do with normal algebra. We get

c = (s3 - p3 - N(s1 - p1)- M(s2 - p2))/(v3 - N v1 - M v2)

and cv + p is then the nearest point on your line to that corner.

Meanwhile we also have:

b = s2 - p2 - v2 c
a = s1 - p1 - v1 c

And the distance of the line from your corner is |an + bm| so the distance squared is

D^2 = (an + bm) * (an + bm) = (a^2 + b^2 + (aM + bM)^2)

As you look at corners, you can consider the fact you have a box. Choose a corner and go to an neighbor, then to the neighbor that puts you diagonally from that corner. If one of those three values is farther away than both of the other two in the same direction, the nearest point will not be on edges going to it. That removes all the edges involving it. Since the line might go right through your box, it is possible for this not to happen. But it is highly unlikely.

For each pair of corners (that are not ruled out) that constitute an edge, we have a range of c values x c0 + (1-x) c1 for x in [0,1] which represent a range of closest points on the line to the closest points on the edge.

The corresponding a and b values are

a = s1-p1-v2(x c0 + (1-x)c1) = s1-p1-v2-(c0-c1)v2 x
b = s2-p2-v1(x c0 + (1-x)c1) = s2-p2-v1-(c0-c1)v1 x

Again, it only matters that the constants are known, so let's just write these as:

a = A0 + A1x
b = B0 + B1x

Now, from above

D^2 = (a^2 + b^2 + (aN + bM)^2)

so we can get the squared distance in terms of x.

D^2 = (A0 + A1 x)^2 + (B0 + B1 x)^2 + 
      (A0 N + A1 Nx)^2 + (B0 M + B1 MX)^2

Multiplying this all out, the x term is going to be the middle term of each square and the x^2 term is going to be the square term of each square.

And clearly the minimum for a parabola k + rx + qx^2 is where r + 2qx = 0 at 'x = -1/2 r/q, by differentiation.

So the minimum will be for

x = -(A0 A1 + B0 B2 + (NA0 A1 + MB0 B1))/
     (A1^2 + B1^2 + (A1 N + B1 M)^2)

When x is between zero and 1, you have a minimum or maximum. By comparing the outcomes between these, you should be able to discard the maximums.

If the minimum would be on a face, not an edge, you will have too many qualifying values. In that case clearly the answer is zero -- the line hits the box.

Answer 2

First thing off my mind, you don't need to check for all 12 edges. For e.g. let's say you want to find the closest point to line A. With some simple math, you can find a perpendicular line A' passing through the center of AABB. You can find the intersection of A and A', let's call that point P. So point P is basically the projection of the center of the AABB on line A, there's mathematical formulae to calculate that. I'll add it if you could tell us how your infinite line is defined (Is it defined by two points, or is it defined by a point and a direction vector?).
Now you can look at the coordinates of P to check which octant it lies in with respect to the center of the AABB, i.e. subtract the coordinates of the center from coordinates of P, this will result in a basic translation of the center to orgin (origin shift). The closest vertex of the cube will be the one in the same octant.

Now, the closest edge to the line will be one of the 3 edges that this vertex belongs to.

This will work in 1/4th the time of your algo.

Answer 3

My (also fairly naïve) solution would be to choose the point on the line closest to the centre of the AABB and work outward from that point following the example from here: https://math.stackexchange.com/questions/2133217/minimal-distance-to-a-cube-in-2d-and-3d-from-a-point-lying-outside

Then iterate along the line until the distance was no longer decreasing (has to sweep outwards in each direction.)

This would have the benefit of being very fast in the cases where the line is parallel to a face or an edge but I don't know if it would be faster than your naïve solution on lines that have no parallel aspects to the AABB.

(Of course the solution from the maths stack exchange would take a bit of adapting from pseudo-code to the language of your choice and you would have to calculate the co-ordinates of the vector to get your points after you had found the shortest path.)