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

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

Недавно я наткнулся на алгоритм столкновения AABB против Sphere Arvo, и мне интересно, есть ли для этого аналогичный алгоритм.

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

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

(Для тех, кто не знает: AABB = выровненная по осям рамка)

48 голосов | спросил SirYakalot 12 +04002011-10-12T15:02:27+04:00312011bEurope/MoscowWed, 12 Oct 2011 15:02:27 +0400 2011, 15:02:27

10 ответов


18

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

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

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

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

ответил Arcane Engineer 14 WedEurope/Moscow2011-12-14T00:04:48+04:00Europe/Moscow12bEurope/MoscowWed, 14 Dec 2011 00:04:48 +0400 2011, 00:04:48
38

Что я использовал ранее в своем 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 12 +04002011-10-12T22:22:09+04:00312011bEurope/MoscowWed, 12 Oct 2011 22:22:09 +0400 2011, 22:22:09
11

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

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

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

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

<p> Моя реализация: </p>

<pre><code>bool AABB :: пересекает (const Ray & ray)
{
  //Случай EZ: если луч начинается внутри коробки или заканчивается внутри
  //поле, то он определенно попадает в поле.
  //Я использую этот код для трассировки лучей с октетом,
  //поэтому мне нужны лучи, которые начинаются и заканчиваются внутри
  //octree node для COUNT как хиты.
  //Вы можете изменить этот тест, чтобы (лучи начинались внутри и заканчивались снаружи)
  //квалифицировать как удар, если вы хотите НЕ считать полностью внутренние лучи
  if (containsIn (ray.startPos) || содержитIn (ray.getEndPoint ()))
    return true;

  //алгоритм говорит, найти 3 t,
  Вектор t;

  //LARGEST t - это единственное, что нам нужно проверить, если оно на лице.
  для (int i = 0; i <3; i ++)
  {
    если (ray.direction.e [i]> 0) //CULL BACK FACE
      t.e [i] = (min.e [i] - ray.startPos.e [i]) /ray.direction.e [i];
    еще
      t.e [i] = (max.e [i] - ray.startPos.e [i]) /ray.direction.e [i];
  }

  int mi = t.maxIndex ();
  if (МеждуIn (t.e [mi], 0, ray.length))
  {
    Вектор pt = ray.at (t.e [mi]);

    //проверяем его в поле в других 2 измерениях
    int o1 = (mi + 1)% 3; //i = 0: o1 = 1, o2 = 2, i = 1: o1 = 2, o2 = 0 и т. д.
    int o2 = (mi + 2)% 3;

    return BetweenIn (pt.e [o1], min.e [o1], max.e [o1]) & & &
           МеждуIn (pt.e [o2], min.e [o2], max.e [o2]);
  }

  return false; //луч не попал в коробку.
}
</code></pre></body></html>

ответил bobobobo 14 +04002012-10-14T02:12:12+04:00312012bEurope/MoscowSun, 14 Oct 2012 02:12:12 +0400 2012, 02:12:12
4

Это мое пересечение 3D-лучей /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
}
ответил Jeroen Baert 24 FebruaryEurope/MoscowbFri, 24 Feb 2012 20:17:12 +0400000000pmFri, 24 Feb 2012 20:17:12 +040012 2012, 20:17:12
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];
}
ответил Rama Hoetzlein 10 J000000Friday15 2015, 07:16:52
1

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

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

Подробнее и код:

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

ответил Gavan Woolery 13 TueEurope/Moscow2011-12-13T23:41:11+04:00Europe/Moscow12bEurope/MoscowTue, 13 Dec 2011 23:41:11 +0400 2011, 23:41:11
1

Вот код линии с 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 14 WedEurope/Moscow2011-12-14T02:31:09+04:00Europe/Moscow12bEurope/MoscowWed, 14 Dec 2011 02:31:09 +0400 2011, 02:31:09
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;
ответил 13 +04002011-10-13T00:17:16+04:00312011bEurope/MoscowThu, 13 Oct 2011 00:17:16 +0400 2011, 00:17:16
0

Я удивлен, увидев, что никто не упомянул метод разветвленной плиты Tavian

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-пересечение /

ответил Tyron 27 J000000Thursday17 2017, 10:44:28
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;
ответил Anton 6 12017vEurope/Moscow11bEurope/MoscowMon, 06 Nov 2017 20:21:31 +0300 2017, 20:21:31

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132