наиболее эффективные алгоритмы AABB против Ray

53

Существует ли известный «наиболее эффективный» алгоритм для обнаружения столкновений AABB и Ray?

Недавно я наткнулся на алгоритм коллизии AABB и Sphere от Arvo, и мне интересно, есть ли такой же заслуживающий внимания алгоритм для этого.

Необходимо иметь условие для этого алгоритма, что мне нужно иметь возможность запрашивать результат для расстояния от источника луча до точки столкновения. Сказав это, если есть другой, более быстрый алгоритм, который не возвращает расстояние, то в дополнение к публикации того, который делает, также публикация этого алгоритма была бы очень полезной.

Пожалуйста, также укажите, что является аргументом возврата функции и как вы используете его для возврата расстояния или случая отсутствия столкновения. Например, есть ли у него параметр out для расстояния, а также значение возврата bool? или он просто возвращает float с расстоянием, против значения -1, без столкновений?

(Для тех, кто не знает: AABB = Ограничивающая рамка с выравниванием по оси)

SirYakalot
источник
Я могу ошибаться, но я думаю, что вы все равно получите ложные срабатывания с этим алгоритмом. Вы правы, что если при проверке оси 3 все углы находятся на одной стороне, столкновения нет. Но кажется, что у вас все еще может быть условие, когда все 3 оси имеют точки с обеих сторон и все еще не имеют столкновения. Я обычно проверяю, перекрывают ли расстояния въезда / выезда все три плиты, чтобы знать наверняка. Это с сайта Geometric tools.
Стив Х
Почему должно быть условие для удаленного запроса? Если есть еще более быстрый алгоритм для случая, когда вам не нужно расстояние, вы тоже не хотите об этом знать?
Сэм Хочевар
ну нет, не совсем. Мне нужно знать, на каком расстоянии происходит столкновение.
SirYakalot
на самом деле я полагаю, что вы правы, я отредактирую вопрос.
SirYakalot
4
Как я уже писал в вашей другой ветке, здесь есть хороший ресурс для этих типов алгоритмов: realtimerendering.com/intersections.html
Tetrad

Ответы:

22

Эндрю Ву, который вместе с Джоном Аманатидесом разработал алгоритм лучевой метки (DDA), повсеместно используемый в raytracers, написал «Fast Ray-Box Intersection» (альтернативный источник здесь ), который был опубликован в Graphics Gems, 1990, pp. 395-396. Вместо того, чтобы быть построенным специально для интеграции через сетку (например, объем вокселя), как DDA (см. Ответ zacharmarz), этот алгоритм специально подходит для миров, которые не подразделяются равномерно, таких как ваш типичный мир многогранников, встречающийся в большинстве 3D игры.

Подход обеспечивает поддержку 3D и, при желании, делает выборку задней поверхности. Алгоритм основан на тех же принципах интеграции, которые используются в DDA, поэтому он очень быстрый. Более подробную информацию можно найти в оригинальном томе Graphics Gems (1990).

Многие другие подходы специально для Ray-AABB можно найти на realtimerendering.com .

РЕДАКТИРОВАТЬ: альтернативный подход без ответвлений - что было бы желательно для GPU и CPU - можно найти здесь .

инженер
источник
ах! ты побил меня этим, я только что натолкнулся на это сегодня утром. Отличная находка!
SirYakalot
Удовольствие, сэр. Я бы также предложил сравнить любые алгоритмы, которые вы найдете на такой основе. (Есть другие официальные списки, подобные этому в другом месте, но сейчас не могу их найти.)
Инженер
Статья здесь
bobobobo
1
Хорошо прокомментированная реализация алгоритма Ву может быть найдена здесь .
Инженер
4
Две предоставленные вами ссылки генерируют ошибки «Not found» и «Forbidden» соответственно ...
liggiorgio
46

То, что я использовал ранее в моем raytracer:

// r.dir is unit direction vector of ray
dirfrac.x = 1.0f / r.dir.x;
dirfrac.y = 1.0f / r.dir.y;
dirfrac.z = 1.0f / r.dir.z;
// lb is the corner of AABB with minimal coordinates - left bottom, rt is maximal corner
// r.org is origin of ray
float t1 = (lb.x - r.org.x)*dirfrac.x;
float t2 = (rt.x - r.org.x)*dirfrac.x;
float t3 = (lb.y - r.org.y)*dirfrac.y;
float t4 = (rt.y - r.org.y)*dirfrac.y;
float t5 = (lb.z - r.org.z)*dirfrac.z;
float t6 = (rt.z - r.org.z)*dirfrac.z;

float tmin = max(max(min(t1, t2), min(t3, t4)), min(t5, t6));
float tmax = min(min(max(t1, t2), max(t3, t4)), max(t5, t6));

// if tmax < 0, ray (line) is intersecting AABB, but the whole AABB is behind us
if (tmax < 0)
{
    t = tmax;
    return false;
}

// if tmin > tmax, ray doesn't intersect AABB
if (tmin > tmax)
{
    t = tmax;
    return false;
}

t = tmin;
return true;

Если это возвращает true, это пересекается, если это возвращает false, это не пересекается.

Если вы используете один и тот же луч много раз, вы можете выполнить предварительные вычисления dirfrac(только деление во всем тесте пересечения). И тогда это действительно быстро. И у вас есть также длина луча до пересечения (хранится в t).

zacharmarz
источник
Можно ли предоставить ключ для того, что означают имена ваших переменных?
SirYakalot
1
Я попытался добавить некоторые пояснения в комментариях. Итак: «r» - это луч, «r.dir» - это его единичный вектор направления, «r.org» - это источник, из которого вы снимаете луч, «dirfrac» - это просто оптимизация, потому что вы всегда можете использовать его для одного и того же луча. (вам не нужно делать деление) и это означает 1 / r.dir. Тогда «lb» - это угол AABB со всеми тремя минимальными координатами, а «rb» - противоположный - угол с максимальными координатами. Выходной параметр "t" - длина вектора от начала координат до пересечения.
zacharmarz
как выглядит определение функции? Можно ли узнать расстояние, на которое произошло столкновение на луче?
SirYakalot
1
Итак, что означает ваш алгоритм, когда он возвращает пересечение, но у этого пересечения отрицательное число? tmin иногда возвращается как отрицательное число.
SirYakalot
1
ах, это когда происхождение находится внутри коробки
SirYakalot
14

Никто не описал алгоритм здесь, но алгоритм Graphics Gems просто:

  1. Используя вектор направления вашего луча, определите, какие 3 из 6 возможных самолетов будут поражены первыми . Если ваш (ненормализованный) вектор направления луча равен (-1, 1, -1), то можно нанести удар по 3 плоскостям: + x, -y и + z.

  2. Из 3 возможных плоскостей найдите t-значение для пересечения для каждого. Примите плоскость, которая получает наибольшее значение t, как самолет, который получил удар, и проверьте, что попадание находится внутри коробки . Диаграмма в тексте проясняет это:

введите описание изображения здесь

Моя реализация:

bool AABB::intersects( const Ray& ray )
{
  // EZ cases: if the ray starts inside the box, or ends inside
  // the box, then it definitely hits the box.
  // I'm using this code for ray tracing with an octree,
  // so I needed rays that start and end within an
  // octree node to COUNT as hits.
  // You could modify this test to (ray starts inside and ends outside)
  // to qualify as a hit if you wanted to NOT count totally internal rays
  if( containsIn( ray.startPos ) || containsIn( ray.getEndPoint() ) )
    return true ; 

  // the algorithm says, find 3 t's,
  Vector t ;

  // LARGEST t is the only one we need to test if it's on the face.
  for( int i = 0 ; i < 3 ; i++ )
  {
    if( ray.direction.e[i] > 0 ) // CULL BACK FACE
      t.e[i] = ( min.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;
    else
      t.e[i] = ( max.e[i] - ray.startPos.e[i] ) / ray.direction.e[i] ;
  }

  int mi = t.maxIndex() ;
  if( BetweenIn( t.e[mi], 0, ray.length ) )
  {
    Vector pt = ray.at( t.e[mi] ) ;

    // check it's in the box in other 2 dimensions
    int o1 = ( mi + 1 ) % 3 ; // i=0: o1=1, o2=2, i=1: o1=2,o2=0 etc.
    int o2 = ( mi + 2 ) % 3 ;

    return BetweenIn( pt.e[o1], min.e[o1], max.e[o1] ) &&
           BetweenIn( pt.e[o2], min.e[o2], max.e[o2] ) ;
  }

  return false ; // the ray did not hit the box.
}
bobobobo
источник
+1 за фактическое объяснение этого (это тоже с картиной :)
legends2k
4

Это мое пересечение 3D ray / AABox, которое я использовал:

bool intersectRayAABox2(const Ray &ray, const Box &box, int& tnear, int& tfar)
{
    Vector3d T_1, T_2; // vectors to hold the T-values for every direction
    double t_near = -DBL_MAX; // maximums defined in float.h
    double t_far = DBL_MAX;

    for (int i = 0; i < 3; i++){ //we test slabs in every direction
        if (ray.direction[i] == 0){ // ray parallel to planes in this direction
            if ((ray.origin[i] < box.min[i]) || (ray.origin[i] > box.max[i])) {
                return false; // parallel AND outside box : no intersection possible
            }
        } else { // ray not parallel to planes in this direction
            T_1[i] = (box.min[i] - ray.origin[i]) / ray.direction[i];
            T_2[i] = (box.max[i] - ray.origin[i]) / ray.direction[i];

            if(T_1[i] > T_2[i]){ // we want T_1 to hold values for intersection with near plane
                swap(T_1,T_2);
            }
            if (T_1[i] > t_near){
                t_near = T_1[i];
            }
            if (T_2[i] < t_far){
                t_far = T_2[i];
            }
            if( (t_near > t_far) || (t_far < 0) ){
                return false;
            }
        }
    }
    tnear = t_near; tfar = t_far; // put return values in place
    return true; // if we made it here, there was an intersection - YAY
}
Йерун Баерт
источник
Какие есть tnearи tfar?
Текнолаги
Пересечение между [tnear, tfar].
Jeroen Baert
3

Вот оптимизированная версия выше, которую я использую для GPU:

__device__ float rayBoxIntersect ( float3 rpos, float3 rdir, float3 vmin, float3 vmax )
{
   float t[10];
   t[1] = (vmin.x - rpos.x)/rdir.x;
   t[2] = (vmax.x - rpos.x)/rdir.x;
   t[3] = (vmin.y - rpos.y)/rdir.y;
   t[4] = (vmax.y - rpos.y)/rdir.y;
   t[5] = (vmin.z - rpos.z)/rdir.z;
   t[6] = (vmax.z - rpos.z)/rdir.z;
   t[7] = fmax(fmax(fmin(t[1], t[2]), fmin(t[3], t[4])), fmin(t[5], t[6]));
   t[8] = fmin(fmin(fmax(t[1], t[2]), fmax(t[3], t[4])), fmax(t[5], t[6]));
   t[9] = (t[8] < 0 || t[7] > t[8]) ? NOHIT : t[7];
   return t[9];
}
Рама Хетцляйн
источник
преобразовал это для использования единства, и это было быстрее, чем встроенные границы. IntersectRay gist.github.com/unitycoder/8d1c2905f2e9be693c78db7d9d03a102
mgear
Как я могу интерпретировать возвращаемое значение? Это что-то вроде евклидова расстояния между началом и точкой пересечения?
Фердинанд Мюч
Какое значение расстояние до коробки?
jjxtra
1

Одна вещь, которую вы, возможно, захотите исследовать, это растеризация передней и задней сторон вашей ограничительной рамки в двух отдельных буферах. Отобразите значения x, y, z как rgb (это лучше всего подходит для ограничительной рамки с одним углом в (0,0,0) и противоположным в (1,1,1).

Очевидно, что это ограниченное использование, но я нашел его отличным для рендеринга простых томов.

Для более подробной информации и кода:

http://www.daimi.au.dk/~trier/?page_id=98

Гаван Вулери
источник
1

Вот код Line против AABB, который я использовал:

namespace {
    //Helper function for Line/AABB test.  Tests collision on a single dimension
    //Param:    Start of line, Direction/length of line,
    //          Min value of AABB on plane, Max value of AABB on plane
    //          Enter and Exit "timestamps" of intersection (OUT)
    //Return:   True if there is overlap between Line and AABB, False otherwise
    //Note:     Enter and Exit are used for calculations and are only updated in case of intersection
    bool Line_AABB_1d(float start, float dir, float min, float max, float& enter, float& exit)
    {
        //If the line segment is more of a point, just check if it's within the segment
        if(fabs(dir) < 1.0E-8)
            return (start >= min && start <= max);

        //Find if the lines overlap
        float   ooDir = 1.0f / dir;
        float   t0 = (min - start) * ooDir;
        float   t1 = (max - start) * ooDir;

        //Make sure t0 is the "first" of the intersections
        if(t0 > t1)
            Math::Swap(t0, t1);

        //Check if intervals are disjoint
        if(t0 > exit || t1 < enter)
            return false;

        //Reduce interval based on intersection
        if(t0 > enter)
            enter = t0;
        if(t1 < exit)
            exit = t1;

        return true;
    }
}

//Check collision between a line segment and an AABB
//Param:    Start point of line segement, End point of line segment,
//          One corner of AABB, opposite corner of AABB,
//          Location where line hits the AABB (OUT)
//Return:   True if a collision occurs, False otherwise
//Note:     If no collision occurs, OUT param is not reassigned and is not considered useable
bool CollisionDetection::Line_AABB(const Vector3D& s, const Vector3D& e, const Vector3D& min, const Vector3D& max, Vector3D& hitPoint)
{
    float       enter = 0.0f;
    float       exit = 1.0f;
    Vector3D    dir = e - s;

    //Check each dimension of Line/AABB for intersection
    if(!Line_AABB_1d(s.x, dir.x, min.x, max.x, enter, exit))
        return false;
    if(!Line_AABB_1d(s.y, dir.y, min.y, max.y, enter, exit))
        return false;
    if(!Line_AABB_1d(s.z, dir.z, min.z, max.z, enter, exit))
        return false;

    //If there is intersection on all dimensions, report that point
    hitPoint = s + dir * enter;
    return true;
}
chaosTechnician
источник
0

Это похоже на код, размещенный zacharmarz.
Я получил этот код из книги Кристера Эриксона «Обнаружение столкновений в реальном времени» в разделе «5.3.3. Пересекающийся луч или сегмент против прямоугольника».

// Where your AABB is defined by left, right, top, bottom

// The direction of the ray
var dx:Number = point2.x - point1.x;
var dy:Number = point2.y - point1.y;

var min:Number = 0;
var max:Number = 1;

var t0:Number;
var t1:Number;

// Left and right sides.
// - If the line is parallel to the y axis.
if(dx == 0){
    if(point1.x < left || point1.x > right) return false;
}
// - Make sure t0 holds the smaller value by checking the direction of the line.
else{
    if(dx > 0){
        t0 = (left - point1.x)/dx;
        t1 = (right - point1.x)/dx;
    }
    else{
        t1 = (left - point1.x)/dx;
        t0 = (right - point1.x)/dx;
    }

    if(t0 > min) min = t0;
    if(t1 < max) max = t1;
    if(min > max || max < 0) return false;
}

// The top and bottom side.
// - If the line is parallel to the x axis.
if(dy == 0){
    if(point1.y < top || point1.y > bottom) return false;
}
// - Make sure t0 holds the smaller value by checking the direction of the line.
else{
    if(dy > 0){
        t0 = (top - point1.y)/dy;
        t1 = (bottom - point1.y)/dy;
    }
    else{
        t1 = (top - point1.y)/dy;
        t0 = (bottom - point1.y)/dy;
    }

    if(t0 > min) min = t0;
    if(t1 < max) max = t1;
    if(min > max || max < 0) return false;
}

// The point of intersection
ix = point1.x + dx * min;
iy = point1.y + dy * min;
return true;

источник
это 2d, да?
SirYakalot
Это только 2D, да. Кроме того, код не так хорошо продуман, как у zacharmarz, который заботится о сокращении количества делений и тестов.
Сэм Хоцевар
0

Я удивлен, увидев, что никто не упомянул метод Тавиана без ветвей

bool intersection(box b, ray r) {
    double tx1 = (b.min.x - r.x0.x)*r.n_inv.x;
    double tx2 = (b.max.x - r.x0.x)*r.n_inv.x;

    double tmin = min(tx1, tx2);
    double tmax = max(tx1, tx2);

    double ty1 = (b.min.y - r.x0.y)*r.n_inv.y;
    double ty2 = (b.max.y - r.x0.y)*r.n_inv.y;

    tmin = max(tmin, min(ty1, ty2));
    tmax = min(tmax, max(ty1, ty2));

    return tmax >= tmin;
}

Полное объяснение: https://tavianator.com/fast-branchless-raybounding-box-intersections/

Тайрон
источник
0

Я добавил к @zacharmarz ответ для обработки, когда источник луча находится внутри AABB. В этом случае tmin будет отрицательным и позади луча, поэтому tmax является первым пересечением между лучом и AABB.

// r.dir is unit direction vector of ray
dirfrac.x = 1.0f / r.dir.x;
dirfrac.y = 1.0f / r.dir.y;
dirfrac.z = 1.0f / r.dir.z;
// lb is the corner of AABB with minimal coordinates - left bottom, rt is maximal corner
// r.org is origin of ray
float t1 = (lb.x - r.org.x)*dirfrac.x;
float t2 = (rt.x - r.org.x)*dirfrac.x;
float t3 = (lb.y - r.org.y)*dirfrac.y;
float t4 = (rt.y - r.org.y)*dirfrac.y;
float t5 = (lb.z - r.org.z)*dirfrac.z;
float t6 = (rt.z - r.org.z)*dirfrac.z;

float tmin = max(max(min(t1, t2), min(t3, t4)), min(t5, t6));
float tmax = min(min(max(t1, t2), max(t3, t4)), max(t5, t6));

// if tmax < 0, ray (line) is intersecting AABB, but the whole AABB is behind us
if (tmax < 0)
{
    t = tmax;
    return false;
}

// if tmin > tmax, ray doesn't intersect AABB
if (tmin > tmax)
{
    t = tmax;
    return false;
}

// if tmin < 0 then the ray origin is inside of the AABB and tmin is behind the start of the ray so tmax is the first intersection
if(tmin < 0) {
  t = tmax;
} else {
  t = tmin;
}
return true;
Антон
источник