CODEWITHSUNDEEP
c#3d
devuxer
devuxer

Reputation: 42354

Intersection of line segment with axis-aligned box in C#

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.

Upvotes: 7

Views: 7888

Answers (3)

zezba9000
zezba9000

Reputation: 3383

Optimized version of the answer. There is no reason to do allocations or lookups.

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

Upvotes: 2

devuxer
devuxer

Reputation: 42354

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

Upvotes: 8

Archie
Archie

Reputation: 2672

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.

Upvotes: 3

Related Questions