C#中线段与轴对齐的盒子的交点

Question

我希望您能提供一个算法，用于确定线段和轴对齐框之间的近点和远点交点。

这是我的方法定义：

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

如果线段不与盒子相交，该方法应返回一个空的Point3D数组。

到目前为止，我已经找到了一些高度优化的算法研究论文，但它们似乎都是用C++编写的，并且需要将多个长类文件转换为C#。对于我的目的，我更喜欢一些相对高效、易于理解的算法，适合那些懂得点积和叉积的人，并且简单/简洁。

- devuxer

---

我不知道算法，但我认为返回“null”有点不寻常。一个空数组更好，它清楚地表明没有相交的点（长度=0），并且您不需要在使用代码中执行空检查。 - RichK

只是挑剔一下，光线没有终点-它在一个方向上是无限的。有起点和终点的线段才叫直线。 - Incredulous Monk

好的，@RichK，我已经纠正了我的问题。 - devuxer

好的观点，@Incredulous Monk，我修改了我的问题。 - devuxer

http://www.geometrictools.com/LibMathematics/Intersection/Intersection.html 是寻找这类东西的好地方 :) - Mark Simpson

Answer 1

这是我最终使用的代码：

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

- devuxer

---

至少在这里有一点解释：http://www.garagegames.com/community/blogs/view/309。该算法计算了从起点到交点所需走过的线段的比例。它通过将每个轴视为一维问题来实现此目的，其中它找到需要添加到起点的线段的比例以达到交点。 - mike

这段代码可以通过先检查边界框来进行优化：if (begin>max || end < min) return intersections; // 没有交集 - mike

Answer 2

对于一个轴对齐的盒子来说，它非常简单：你需要找到你的光线与6个平面（由盒子的面定义）的交点，然后检查你找到的点是否在盒子顶点坐标限制范围内。

- Archie

Answer 3

优化版的答案。没有理由进行分配或查找。

public struct Ray3
{
  public Vec3 origin, direction;

        public bool IntersectRayBox(Box3 box, out Vec3 point1, out Vec3 point2)
        {
            var min = (box.center - (box.size / 2)) - origin;
            var max = (box.center + (box.size / 2)) - origin;
            float near = float.MinValue;
            float far = float.MaxValue;

            // X
            float t1 = min.x / direction.x;
            float t2 = max.x / direction.x;
            float tMin = Math.Min(t1, t2);
            float tMax = Math.Max(t1, t2);
            if (tMin > near) near = tMin;
            if (tMax < far) far = tMax;
            if (near > far || far < 0)
            {
                point1 = Vec3.zero;
                point2 = Vec3.zero;
                return false;
            }

            // Y
            t1 = min.y / direction.y;
            t2 = max.y / direction.y;
            tMin = Math.Min(t1, t2);
            tMax = Math.Max(t1, t2);
            if (tMin > near) near = tMin;
            if (tMax < far) far = tMax;
            if (near > far || far < 0)
            {
                point1 = Vec3.zero;
                point2 = Vec3.zero;
                return false;
            }

            // Z
            t1 = min.z / direction.z;
            t2 = max.z / direction.z;
            tMin = Math.Min(t1, t2);
            tMax = Math.Max(t1, t2);
            if (tMin > near) near = tMin;
            if (tMax < far) far = tMax;
            if (near > far || far < 0)
            {
                point1 = Vec3.zero;
                point2 = Vec3.zero;
                return false;
            }

            point1 = origin + direction * near;
            point2 = origin + direction * far;
            return true;
        }
}

- zezba9000