The intersection of a line segment with an axis-aligned field in C #

Question

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

Here is my method definition:

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

If the line segment does not cross the field, the method should return an empty Point3D array.

From my research so far, I have come across some research papers with highly optimized algorithms, but they all seem to be written in C ++ and will require several large class files to be converted to C #. For my purposes, it is preferable that it is reasonably effective, it is easy to understand someone who receives point products and cross products, and simple / short.

Answer 1

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

Answer 2

Well, for a field aligned on the axis it is quite simple: you need to find the intersection of the ray with 6 planes (given by the box borders), and then check the points you found at the coordinates of the window vertices.