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

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?

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.

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.

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;
}

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;
}

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.

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://stackoverflow.com/a/3235596/913347
    @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}')