Given a bounding box and a line (two points), determine if the line intersects the box

Question

Given a bounding box, with definitions like bounds.min.(x/y/z), bounds.max.(x/y/z), and two points in 3D space (expressed as Vector3 objects), how can I determine if the line made by the two points intersects the bounding box?

Pneumo

Answer 1

There is an implementation in C++ available online here: Line Box Intersection (http://www.3dkingdoms.com/weekly/weekly.php?a=3)

Another link, with references (and code) for a lot of intersection tests: http://www.realtimerendering.com/intersections.html

If you want to learn more about intersection tests, this one is the bible: Real-Time Collision Detection (Amazon)

EDIT: the algorithm in this paper ("An Efficient and Robust Ray-Box Intersection Algorithm", Amy Williams and Steve Barrus and R. Keith Morley and Peter Shirley; journal of graphics, gpu, and game tools, Vol. 10(1), 49-54, 2005) looks especially concise and comes with (C++) source code, too.

Juliennejuliet

After converting the code in the first link to non-hideous C++, it seems to be working for the most part. I'll post the code here for anyone else who needs it, so they don't have to convert it, too. – Pneumo

Answer 2

Here's one way to do it if you want to do the math yourself: Intersect the line with each of the 6 planes created by the bounding box.

The vector representation of the line is X = B + t*D, where B is a Tuple (x,y,z) of the base point (say, your first point) and D is the direction of the line, again expressed as a Tuple (dx, dy, dz). You get the direction by subtracting one of the points from the other, so if you have points P1 (x1, y1, z1) and P2(x2, y2, z2), then D = P2 - P1 and B = P1, meaning D = (x2 - x1, y2 - y1, z2 - z1). We'll call the elements of this vector dx, dy and dz.

The parametric representation of the plane is x + y + z = c. So, convert your bounding box to this represenation and then use the parametric representation of your line, e.g. the three equations x = x1 + tdx, y = y1 + tdy, z = z1 + t*dz, to substitute x,y and z in your plane equation. Solve for t. Since each of your 6 planes is going to be parallel to the plane created by 2 of the axis, your problem becomes easier; for example for the plane that is parallel to the plane created by the x and y axis, your plane equation simply becomes z = c, whereas c is the z-coordinate of one of your bounding box points, and so on.

Now use t to calculate the intersection point of the line with your plane. (If t is < 0 or > 1, then your line intersects OUTSIDE of P1-P2, if t >= 0 and t <= 1, then your line intersects the plane somewhere between P1 and P2)

Now you're not done yet. The plane equation gives you a plane, not a rectangle, so the point of intersection with the plane might actually be OUTSIDE your rectangle, but since you now have the coordinates of your intersection (x = x1 + t * dx and so on), you can easily see if that point is inside the rectangle your bounding box. Your problem is now reduced to check whether a point in 2D space is inside a bounding box rectangle, which is trivial to check.

Of course, the first thing you should do if you actually use this solution is check whether the line is also aligned along one axis because in that case, your intersection code becomes trivial and it will also take care of the problem of the line not intersecting some planes, e.g. huge or tiny numbers of t, maybe even over- or underflows.

I bet there are faster ways to do this, but it will work.

Base

If there are faster ways of doing this I need to know about them, because this code is going to run anywhere up to 100 times per second, and every computation I add slows down the game. – Pneumo

Hmmm, actually I think that the algorithm you posted is SLOWER than what I proposed because it seems to work with vectors, e.g. doing lots of additions and four multiplications for each call to GetIntersection because it does not optimize on the fact that your bounding box is aligned with the coordinate system, which means you can throw out two of the three parametric equations for each plane intersection. I think you can get away with a single multiplication per intersection. – Base

Ooops, no, sorry. discard that. You need the three multiplications to calculate the coordinates of the hit. Darn. – Base

Answer 3

Here is the code which seems to be working, converted from Greg S's answer into C#:

bool CheckLineBox(Vector3 B1, Vector3 B2, Vector3 L1, Vector3 L2, ref Vector3 Hit)
{
    if (L2.x < B1.x && L1.x < B1.x) return false;
    if (L2.x > B2.x && L1.x > B2.x) return false;
    if (L2.y < B1.y && L1.y < B1.y) return false;
    if (L2.y > B2.y && L1.y > B2.y) return false;
    if (L2.z < B1.z && L1.z < B1.z) return false;
    if (L2.z > B2.z && L1.z > B2.z) return false;
    if (L1.x > B1.x && L1.x < B2.x &&
        L1.y > B1.y && L1.y < B2.y &&
        L1.z > B1.z && L1.z < B2.z)
    {
        Hit = L1;
        return true;
    }
    if ((GetIntersection(L1.x - B1.x, L2.x - B1.x, L1, L2, ref Hit) && InBox(Hit, B1, B2, 1))
      || (GetIntersection(L1.y - B1.y, L2.y - B1.y, L1, L2, ref Hit) && InBox(Hit, B1, B2, 2))
      || (GetIntersection(L1.z - B1.z, L2.z - B1.z, L1, L2, ref Hit) && InBox(Hit, B1, B2, 3))
      || (GetIntersection(L1.x - B2.x, L2.x - B2.x, L1, L2, ref Hit) && InBox(Hit, B1, B2, 1))
      || (GetIntersection(L1.y - B2.y, L2.y - B2.y, L1, L2, ref Hit) && InBox(Hit, B1, B2, 2))
      || (GetIntersection(L1.z - B2.z, L2.z - B2.z, L1, L2, ref Hit) && InBox(Hit, B1, B2, 3)))
        return true;

    return false;
}

bool GetIntersection(float fDst1, float fDst2, Vector3 P1, Vector3 P2, ref Vector3 Hit)
{
    if ((fDst1 * fDst2) >= 0.0f) return false;
    if (fDst1 == fDst2) return false;
    Hit = P1 + (P2 - P1) * (-fDst1 / (fDst2 - fDst1));
    return true;
}

bool InBox(Vector3 Hit, Vector3 B1, Vector3 B2, int Axis)
{
    if (Axis == 1 && Hit.z > B1.z && Hit.z < B2.z && Hit.y > B1.y && Hit.y < B2.y) return true;
    if (Axis == 2 && Hit.z > B1.z && Hit.z < B2.z && Hit.x > B1.x && Hit.x < B2.x) return true;
    if (Axis == 3 && Hit.x > B1.x && Hit.x < B2.x && Hit.y > B1.y && Hit.y < B2.y) return true;
    return false;
}

Pneumo

12 years later I'm wondering: In GetIntersection, if first condition doesn't match, how could the second condition match? – Correia

@Correia I copied the C++ code more or less verbatim, if I recall (just translating it to C#). I'm sure those if statements could be combined or re-ordered to maybe gain a few ticks of efficiency, but it didn't affect the performance of the game I was making at the time either. – Pneumo

Answer 4

JavaScript version, based on SpikeX answer and glMatrix:

// all args are Vec3, Hit will be filled by this algo
function checkLineBox( B1, B2, L1, L2, Hit)
{
    if (L2[0] < B1[0] && L1[0] < B1[0]) return false;
    if (L2[0] > B2[0] && L1[0] > B2[0]) return false;
    if (L2[1] < B1[1] && L1[1] < B1[1]) return false;
    if (L2[1] > B2[1] && L1[1] > B2[1]) return false;
    if (L2[2] < B1[2] && L1[2] < B1[2]) return false;
    if (L2[2] > B2[2] && L1[2] > B2[2]) return false;
    if (L1[0] > B1[0] && L1[0] < B2[0] &&
        L1[1] > B1[1] && L1[1] < B2[1] &&
        L1[2] > B1[2] && L1[2] < B2[2])
    {
        vec3.set( L1, Hit);
        return true;
    }

    if ((getIntersection(L1[0] - B1[0], L2[0] - B1[0], L1, L2, Hit) && inBox(Hit, B1, B2, 1))
      || (getIntersection(L1[1] - B1[1], L2[1] - B1[1], L1, L2, Hit) && inBox(Hit, B1, B2, 2))
      || (getIntersection(L1[2] - B1[2], L2[2] - B1[2], L1, L2, Hit) && inBox(Hit, B1, B2, 3))
      || (getIntersection(L1[0] - B2[0], L2[0] - B2[0], L1, L2, Hit) && inBox(Hit, B1, B2, 1))
      || (getIntersection(L1[1] - B2[1], L2[1] - B2[1], L1, L2, Hit) && inBox(Hit, B1, B2, 2))
      || (getIntersection(L1[2] - B2[2], L2[2] - B2[2], L1, L2, Hit) && inBox(Hit, B1, B2, 3)))
        return true;

    return false;
}

var temp = vec3.create();
function getIntersection( fDst1, fDst2, P1, P2, Hit)
{
    if ((fDst1 * fDst2) >= 0) return false;
    if (fDst1 == fDst2) return false;

    vec3.subtract(P2, P1, temp);
    vec3.scale( temp, (-fDst1 / (fDst2 - fDst1)));
    vec3.add( temp, P1, Hit);

    return true;
}

function inBox(Hit, B1, B2, Axis)
{
    if (Axis == 1 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[1] > B1[1] && Hit[1] < B2[1]) return true;
    if (Axis == 2 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[0] > B1[0] && Hit[0] < B2[0]) return true;
    if (Axis == 3 && Hit[0] > B1[0] && Hit[0] < B2[0] && Hit[1] > B1[1] && Hit[1] < B2[1]) return true;
    return false;
}

Autopsy

Answer 5

You can represent you bounding box as 12 triangles (2 for each of 6 faces). Then you can check intersection of your line with each of them. I have a line-triangle intersection function, but it was written for my own software rendering engine, not for D3D. I can try to convert it, if you need the code.

Withoutdoors

I could do this, but I don't know how performant it would be... this runs every "Update", so many times per second, and I'm not sure how it would fare, but it's certainly worth a try. If you post the code for line/triangle intersection, and I can get that working (and it isn't slow), I'll give it to you. – Pneumo

Answer 6

Adding a Python implementation. Please do not rely on it without an extensive testing!

from __future__ import annotations  # allow using Vec3 within Vec3
from dataclasses import dataclass


# based on https://gist.github.com/davidnuon/3816736
@dataclass
class Vec3:
    # default of 'inf' means 'unset'
    x: float = float('inf')
    y: float = float('inf')
    z: float = float('inf')

    # String represntation
    def __str__(self):
        return '<%s, %s, %s>' % (self.x, self.y, self.z)

    # Produce a copy of itself
    def __copy(self):
        return Vec3(self.x, self.y, self.z)

    # Signing
    def __neg__(self):
        return Vec3(-self.x, -self.y, -self.z)

    # Scalar Multiplication
    def __mul__(self, number):
        return Vec3(self.x * number, self.y * number, self.z * number)

    # Arithmetic Operations
    def __add__(self, operand):
        return Vec3(self.x + operand.x, self.y + operand.y, self.z + operand.z)

    def __sub__(self, operand):
        return self.__copy() + -operand

    def assign_from(self, another: Vec3):
        self.x = another.x
        self.y = another.y
        self.z = another.z


class Geometry:
    # based on https://mcmap.net/q/897839/-given-a-bounding-box-and-a-line-two-points-determine-if-the-line-intersects-the-box
    @staticmethod
    def CheckLineBox(B1: Vec3, B2: Vec3, L1: Vec3, L2: Vec3, Hit: Vec3) -> bool:

        def GetIntersection(fDst1: float, fDst2: float, P1: Vec3, P2: Vec3) -> bool:
            if (fDst1 * fDst2) >= 0.0:  # both line values are at same side relative to box side
                return False
            if fDst1 == fDst2:  # can't happen!
                return False
            Hit.assign_from(P1 + (P2 - P1) * (-fDst1 / (fDst2 - fDst1)))
            return True

        def InBox(Axis: int):
            if Axis == 1 and B1.z < Hit.z < B2.z and B1.y < Hit.y < B2.y:
                return True
            if Axis == 2 and B1.z < Hit.z < B2.z and B1.x < Hit.x < B2.x:
                return True
            if Axis == 3 and B1.x < Hit.x < B2.x and B1.y < Hit.y < B2.y:
                return True
            return False

        def VerifyBox():
            # box must be specified correctly with nearest and farthest corners
            ok = B1.x < B2.x and B1.y < B2.y and B1.z < B2.z
            if not ok:
                print('bad box data')
            return ok

        print(f'Box: ({B1}:{B2}), Line: {L1}:{L2}')
        if not VerifyBox():
            return False
        # if at any axis, the line values are before/after the box, return False:
        if ((L2.x < B1.x and L1.x < B1.x) or
                (L2.x > B2.x and L1.x > B2.x) or
                (L2.y < B1.y and L1.y < B1.y) or
                (L2.y > B2.y and L1.y > B2.y) or
                (L2.z < B1.z and L1.z < B1.z) or
                (L2.z > B2.z and L1.z > B2.z)):
            return False
        # if L1 is within the box, return it
        if B1.x < L1.x < B2.x and B1.y < L1.y < B2.y and B1.z < L1.z < B2.z:
            Hit.assign_from(L1)
            return True
        if ((GetIntersection(L1.x - B1.x, L2.x - B1.x, L1, L2) and InBox(1))
                or (GetIntersection(L1.y - B1.y, L2.y - B1.y, L1, L2) and InBox(2))
                or (GetIntersection(L1.z - B1.z, L2.z - B1.z, L1, L2) and InBox(3))
                or (GetIntersection(L1.x - B2.x, L2.x - B2.x, L1, L2) and InBox(1))
                or (GetIntersection(L1.y - B2.y, L2.y - B2.y, L1, L2) and InBox(2))
                or (GetIntersection(L1.z - B2.z, L2.z - B2.z, L1, L2) and InBox(3))):
            return True

        return False


g = Geometry()
hit = Vec3()
rc = g.CheckLineBox(Vec3(0, 0, 0), Vec3(3, 3, 3), Vec3(-1, -1, -1), Vec3(0.1, 0, 0), hit)
print(f'rc={rc}, hit={hit}')

Correia