Given a bounding box and a line (two points), dete

问题:

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?

回答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.

回答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 = y1+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.

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

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

回答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.