我尝试在 C# 中重新实现 Fast Graphics Gems Ray/AABB 交集方法：
// Based on "Fast Ray-Box Intersection" algorithm by Andrew Woo, "Graphics Gems", Academic Press, 1990
public unsafe Vector? IntersectionWith(Cuboid other) {
const int NUM_DIMENSIONS = 3;
Assure.Equal(NUM_DIMENSIONS, 3); // If that value is ever changed, this algorithm will need some maintenance
const byte QUADRANT_MIN = 0;
const byte QUADRANT_MAX = 1;
const byte QUADRANT_BETWEEN = 2;
// Step 1: Work out which direction from the start point to test for intersection for all 3 dimensions, and the distance
byte* quadrants = stackalloc byte[NUM_DIMENSIONS];
float* candidatePlanes = stackalloc float[NUM_DIMENSIONS];
float* cuboidMinPoints = stackalloc float[NUM_DIMENSIONS];
float* cuboidMaxPoints = stackalloc float[NUM_DIMENSIONS];
float maxDistance = Single.NegativeInfinity;
byte maxDistanceDimension = 0;
bool startPointIsInsideCuboid = true;
cuboidMinPoints[0] = other.X;
cuboidMinPoints[1] = other.Y;
cuboidMinPoints[2] = other.Z;
cuboidMaxPoints[0] = other.X + other.Width;
cuboidMaxPoints[1] = other.Y + other.Height;
cuboidMaxPoints[2] = other.Z + other.Depth;
for (byte i = 0; i < NUM_DIMENSIONS; ++i) {
if (StartPoint[i] < cuboidMinPoints[i]) {
quadrants[i] = QUADRANT_MIN;
candidatePlanes[i] = cuboidMinPoints[i];
startPointIsInsideCuboid = false;
}
else if (StartPoint[i] > cuboidMaxPoints[i]) {
quadrants[i] = QUADRANT_MAX;
candidatePlanes[i] = cuboidMaxPoints[i];
startPointIsInsideCuboid = false;
}
else {
quadrants[i] = QUADRANT_BETWEEN;
}
}
if (startPointIsInsideCuboid) return StartPoint;
// Step 2: Find farthest dimension from cuboid
for (byte i = 0; i < NUM_DIMENSIONS; ++i) {
// ReSharper disable once CompareOfFloatsByEqualityOperator Exact check is desired here: Anything other than 0f is usable
if (quadrants[i] != QUADRANT_BETWEEN && Orientation[i] != 0f) {
float thisDimensionDist = (candidatePlanes[i] - StartPoint[i]) / Orientation[i];
if (thisDimensionDist > maxDistance) {
maxDistance = thisDimensionDist;
maxDistanceDimension = i;
}
}
}
if (maxDistance < 0f) return null;
if (maxDistance - Length > MathUtils.FlopsErrorMargin) return null;
float* intersectionPoint = stackalloc float[NUM_DIMENSIONS];
for (byte i = 0; i < NUM_DIMENSIONS; ++i) {
if (maxDistanceDimension == i) {
intersectionPoint[i] = StartPoint[i] + maxDistance * Orientation[i];
if (cuboidMinPoints[i] - intersectionPoint[i] > MathUtils.FlopsErrorMargin || intersectionPoint[i] - cuboidMaxPoints[i] > MathUtils.FlopsErrorMargin) return null;
}
else intersectionPoint[i] = candidatePlanes[i];
}
Vector result = new Vector(intersectionPoint[0], intersectionPoint[1], intersectionPoint[2]);
if (!IsInfiniteLength && Vector.DistanceSquared(StartPoint, result) > Length * Length) return null;
else return result;
}
但是，尽管它有点工作，但我在单元测试的以下部分得到了不正确的结果：
Cuboid cuboid = new Cuboid(frontBottomLeft: new Vector(0f, 7.1f, 0f), width: 0f, height: 5f, depth: 0f);
Ray testRayC = new Ray(startPoint: new Vector(30f, 30f, 30f), orientation: new Vector(-1f, -1f, -1f));
Assert.AreEqual(
null,
testRayC.IntersectionWith(cuboid)
);
我期待从对testRayC.IntersectionWith(cuboid)的调用中得到null，但它返回一个Vector(0, 12.1, 0)，这根本不是射线上的一个点。
那么，这只是添加最终检查计算点在射线上的情况吗？或者(这就是我怀疑的(，我在转录代码时是否犯了错误？我进行了双重和三重检查，但没有看到任何明显的东西......
代码中的问题是当您执行if (maxDistanceDimension == i) { . 原始代码检查if (whichPlane != i) { . 我没有您的数据结构，但修复程序应如下所示：
for (byte i = 0; i < NUM_DIMENSIONS; ++i)
{
if (maxDistanceDimension != i)
{
intersectionPoint[i] = StartPoint[i] + maxDistance * Orientation[i];
if (intersectionPoint[i] < cuboidMinPoints[i] - MathUtils.FlopsErrorMargin || intersectionPoint[i] > cuboidMaxPoints[i] + MathUtils.FlopsErrorMargin)
return null;
}
else
{
intersectionPoint[i] = candidatePlanes[i];
}
}
接下来，以下内容不在原始代码中。 这是干什么用的？
if (maxDistance - Length > MathUtils.FlopsErrorMargin)
return null;
如果您尝试检查命中是否在射线范围内，这可能是一个错误。 鉴于您的Orientation似乎没有规范化，maxDistance不一定以长度为单位。 这在原始算法中可能无关紧要，但是如果您要根据其他长度检查maxDistance，则需要对Orientation进行规范化(使其无量纲(，以便
thisDimensionDist = (candidatePlanes[i] - StartPoint[i]) / Orientation[i];
将具有长度单位。
顺便说一句，在原著中我认为以下内容是错误的：
if(inside) {
coord = origin;
return (TRUE);
}
假设此代码是 c 而不是 c++，则只需将 coord 指针设置为与 origin 指针具有相同的引用，这对调用方没有影响。 但是，此问题不适用于您的版本。
另外，在查看此内容的过程中，我在此处对算法进行了更字面的 c# 转录：
public static class RayXCuboid
{
enum HitQuadrant
{
Right = 0,
Left = 1,
Middle = 2,
}
const int Dimension = 3;
[Conditional("DEBUG")]
static void AssertValidArguments<TDoubleList>(params TDoubleList[] args) where TDoubleList : IList<double>
{
Debug.Assert(Dimension == 3);
foreach (var list in args)
Debug.Assert(list != null && list.Count == Dimension);
}
public static bool HitBoundingBox<TDoubleList>(TDoubleList minB, TDoubleList maxB, TDoubleList origin, TDoubleList dir, TDoubleList coord) where TDoubleList : IList<double>
{
AssertValidArguments(minB, maxB, origin, dir, coord);
HitQuadrant[] quadrant = new HitQuadrant[Dimension];
double[] maxT = new double[Dimension];
double[] candidatePlane = new double[Dimension];
/* Find candidate planes; this loop can be avoided if
rays cast all from the eye(assume perpsective view) */
bool inside = true;
for (int i = 0; i < Dimension; i++)
if (origin[i] < minB[i])
{
quadrant[i] = HitQuadrant.Left;
candidatePlane[i] = minB[i];
inside = false;
}
else if (origin[i] > maxB[i])
{
quadrant[i] = HitQuadrant.Right;
candidatePlane[i] = maxB[i];
inside = false;
}
else
{
quadrant[i] = HitQuadrant.Middle;
}
/* Ray origin inside bounding box */
if (inside)
{
CopyTo(origin, coord);
return true;
}
/* Calculate T distances to candidate planes */
for (int i = 0; i < Dimension; i++)
if (quadrant[i] != HitQuadrant.Middle && dir[i] != 0.0)
maxT[i] = (candidatePlane[i] - origin[i]) / dir[i];
else
maxT[i] = -1.0;
/* Get largest of the maxT's for final choice of intersection */
int whichPlane = 0;
for (int i = 1; i < Dimension; i++)
if (maxT[whichPlane] < maxT[i])
whichPlane = i;
/* Check final candidate actually inside box */
if (maxT[whichPlane] < 0.0)
{
FillWithDefault(coord);
return false;
}
for (int i = 0; i < Dimension; i++)
if (whichPlane != i)
{
coord[i] = origin[i] + maxT[whichPlane] * dir[i];
if (coord[i] < minB[i] || coord[i] > maxB[i])
{
FillWithDefault(coord);
return false;
}
}
else
{
coord[i] = candidatePlane[i];
}
return true; /* ray hits box */
}
static void FillWithDefault<T>(IList<T> list)
{
for (int i = 0; i < list.Count; i++)
list[i] = default(T);
}
static void CopyTo<T>(IList<T> from, IList<T> to)
{
int arrayIndex = 0;
foreach (var item in from)
to[arrayIndex++] = item;
}
}