레이/AABB 교차로 잘못된 내가 C 번호에 <a href="http://tog.acm.org/resources/GraphicsGems/gems/RayBox.c" rel="nofollow">Fast Graphics Gems Ray/AABB Intersection Method</a> 다시 구현하기 위해 노력했습니다

Question

: 그것은 일종의 작동하지만, 내가 단위 테스트의 다음 부분에 잘못된 결과를 얻고있다, 그러나

// 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)을 반환합니다.

---

계산 된 포인트가 광선에 있는지 최종 확인을 추가하는 경우입니까? 또는 (그리고 이것이 내가 의심하는 바입니다) 코드를 옮겨 적을 때 오류가 있었습니까? 이중 및 삼중 검사를했는데 아무 것도 볼 수 없었습니다 ...

Answer 1

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 길이가 반드시 단위 길이가 아닙니다. 당신은 당신이 Orientation을 정상화 할 몇 가지 다른 길이에 대해 maxDistance을 확인하려는 경우이

   thisDimensionDist = (candidatePlanes[i] - StartPoint[i])/Orientation[i]; 

길이의 단위가되도록 (이 차원 만들기) 원래의 알고리즘에 문제가 있지만하지 않을 수 있습니다.

또한, 기존에 나는 다음과 같은 잘못된 생각이 코드를 가정

이

if(inside) { 
    coord = origin; 
    return (TRUE); 
} 

C가 아니라 C++입니다, 이것은 단순히 origin 포인터와 동일한 기준을 가지고하여 coord 포인터를 설정하는 발신자에게 아무런 영향을 미치지 않습니다. 그러나이 문제는 귀하의 버전에는 적용되지 않습니다.

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

:

또한,이보고하는 과정에서, 내가 여기 알고리즘을보다 문자 C#을 전사했다