Intersection of line segment with axis-aligned box

问题:

I'm looking for an algorithm that determines the near and far intersection points between a line segment and an axis-aligned box.

Here is my method definition:

public static Point3D[] IntersectionOfLineSegmentWithAxisAlignedBox(
    Point3D rayBegin, Point3D rayEnd, Point3D boxCenter, Size3D boxSize)

If the line segment doesn't intersect the box, the method should return an empty Point3D array.

From my research so far, I've come across some research papers with highly optimized algorithms, but they all seem to be written in C++ and would require multiple long class files to be converted to C#. For my purposes, something that is reasonably efficient, easy to understand by someone who gets dot products and cross products, and simple/short would be preferred.

回答1:

Here's what I ended up using:

public static List<Point3D> IntersectionOfLineSegmentWithAxisAlignedBox(
    Point3D segmentBegin, Point3D segmentEnd, Point3D boxCenter, Size3D boxSize)
{
    var beginToEnd = segmentEnd - segmentBegin;
    var minToMax = new Vector3D(boxSize.X, boxSize.Y, boxSize.Z);
    var min = boxCenter - minToMax / 2;
    var max = boxCenter + minToMax / 2;
    var beginToMin = min - segmentBegin;
    var beginToMax = max - segmentBegin;
    var tNear = double.MinValue;
    var tFar = double.MaxValue;
    var intersections = new List<Point3D>();
    foreach (Axis axis in Enum.GetValues(typeof(Axis)))
    {
        if (beginToEnd.GetCoordinate(axis) == 0) // parallel
        {
            if (beginToMin.GetCoordinate(axis) > 0 || beginToMax.GetCoordinate(axis) < 0)
                return intersections; // segment is not between planes
        }
        else
        {
            var t1 = beginToMin.GetCoordinate(axis) / beginToEnd.GetCoordinate(axis);
            var t2 = beginToMax.GetCoordinate(axis) / beginToEnd.GetCoordinate(axis);
            var tMin = Math.Min(t1, t2);
            var tMax = Math.Max(t1, t2);
            if (tMin > tNear) tNear = tMin;
            if (tMax < tFar) tFar = tMax;
            if (tNear > tFar || tFar < 0) return intersections;

        }
    }
    if (tNear >= 0 && tNear <= 1) intersections.Add(segmentBegin + beginToEnd * tNear);
    if (tFar >= 0 && tFar <= 1) intersections.Add(segmentBegin + beginToEnd * tFar);
    return intersections;
}

---

public enum Axis
{
    X,
    Y,
    Z
}

---

public static double GetCoordinate(this Point3D point, Axis axis)
{
    switch (axis)
    {
        case Axis.X:
            return point.X;
        case Axis.Y:
            return point.Y;
        case Axis.Z:
            return point.Z;
        default:
            throw new ArgumentException();
    }
}

public static double GetCoordinate(this Vector3D vector, Axis axis)
{
    switch (axis)
    {
        case Axis.X:
            return vector.X;
        case Axis.Y:
            return vector.Y;
        case Axis.Z:
            return vector.Z;
        default:
            throw new ArgumentException();
    }
}

回答2:

Well, for an axis-aligned box it's pretty simple: you have to find intersection of your ray with 6 planes (defined by the box faces) and then check the points you found against the box vertices coordinates limits.