algoritmos de colisión AABB vs Ray más eficientes

53

¿Existe un algoritmo conocido 'más eficiente' para la detección de colisión AABB vs Ray?

Recientemente me topé con el algoritmo de colisión AABB vs Esfera de Arvo, y me pregunto si hay un algoritmo similarmente notable para esto.

Una condición que debe tener este algoritmo es que necesito tener la opción de consultar el resultado de la distancia desde el origen del rayo hasta el punto de colisión. Dicho esto, si hay otro algoritmo más rápido que no devuelve la distancia, además de publicar uno que sí lo haga, también sería muy útil publicar ese algoritmo.

Indique también cuál es el argumento de retorno de la función y cómo lo utiliza para devolver la distancia o un caso de "no colisión". Por ejemplo, ¿tiene un parámetro de salida para la distancia y un valor de retorno de bool? ¿O simplemente devuelve un flotador con la distancia, frente a un valor de -1 para ninguna colisión?

(Para aquellos que no saben: AABB = Cuadro delimitador alineado del eje)

Sir Yakalot
fuente
Podría estar equivocado, pero creo que aún obtendrá falsos positivos con este algoritmo. Tiene razón en que si todas las esquinas están en el mismo lado cuando se verifican los 3 ejes, no hay colisión. Pero parece que todavía puede tener la condición de que los 3 ejes tengan puntos en ambos lados y aún no tengan colisión. Por lo general, verifico si las distancias de entrada / salida se superponen en las tres losas para saber con certeza. Es del sitio de herramientas geométricas.
Steve H
¿Por qué debe tener la condición para la consulta de distancia? Si hay un algoritmo aún más rápido para el caso en el que no necesita la distancia, ¿no quiere saberlo también?
sam hocevar
bueno, no, en realidad no. Necesito saber a qué distancia ocurre la colisión.
SirYakalot
en realidad supongo que tienes razón, editaré la pregunta.
SirYakalot
44
Como publiqué en su otro hilo, hay un buen recurso para este tipo de algoritmos aquí: realtimerendering.com/intersections.html
Tetrad

Respuestas:

22

Andrew Woo, quien junto con John Amanatides desarrolló el algoritmo de marcado de rayos (DDA) utilizado de manera ubicua en los trazadores de rayos, escribió "Intersección rápida de la caja de rayos" (fuente alternativa aquí ) que se publicó en Graphics Gems, 1990, pp. 395-396. En lugar de ser construido específicamente para la integración a través de una cuadrícula (por ejemplo, un volumen de vóxel) como DDA es (ver la respuesta de zacharmarz), este algoritmo es específicamente adecuado para mundos que no están subdivididos de manera uniforme, como su mundo de poliedros típico que se encuentra en la mayoría de los 3D juegos.

El enfoque proporciona soporte para 3D y, opcionalmente, realiza el sacrificio de la cara posterior. El algoritmo se deriva de los mismos principios de integración utilizados en los DDA, por lo que es muy rápido. Se pueden encontrar más detalles en el volumen original de Graphics Gems (1990).

Se pueden encontrar muchos otros enfoques específicos para Ray-AABB en realtimerendering.com .

EDITAR: Aquí se puede encontrar un enfoque alternativo sin ramificaciones, que sería deseable tanto en GPU como en CPU .

Ingeniero
fuente
ah! me superaste, acabo de encontrarlo esta mañana. Gran descubrimiento!
SirYakalot
Placer, señor. También sugeriría comparar cualquier algoritmo que encuentre sobre este tipo de base. (Hay más listas oficiales como esta en otros lugares, pero no puedo encontrar ninguna en este momento.)
Ingeniero
El artículo está aquí
bobobobo
1
Aquí se puede encontrar una implementación bien comentada del algoritmo de Woo .
Ingeniero
44
Los dos enlaces que proporciona generan errores "No encontrado" y "Prohibido" respectivamente ...
liggiorgio
46

Lo que he estado usando anteriormente en mi 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;

Si esto devuelve verdadero, se está intersectando, si devuelve falso, no se está intersectando.

Si usa el mismo rayo muchas veces, puede calcular previamente dirfrac(solo división en la prueba de intersección completa). Y luego es realmente rápido. Y también tiene una longitud de rayo hasta la intersección (almacenada en t).

zacharmarz
fuente
¿Sería posible proporcionar una clave para lo que significan sus nombres de variables?
SirYakalot
1
Traté de agregar alguna explicación en los comentarios. Entonces: "r" es rayo, "r.dir" es el vector de dirección de la unidad, "r.org" es el origen, del cual disparas el rayo, "dirfrac" es solo optimización, porque puedes usarlo siempre para el mismo rayo (no tiene que hacer división) y significa 1 / r.dir. Entonces "lb" es la esquina de AABB con las 3 coordenadas mínimas y "rb" es la esquina opuesta - esquina con coordenadas máximas. El parámetro de salida "t" es la longitud del vector desde el origen hasta la intersección.
zacharmarz
¿Cómo se ve la definición de la función? ¿Es posible averiguar la distancia que ocurrió la colisión en el rayo?
SirYakalot
1
Entonces, ¿qué significa su algoritmo cuando devuelve una intersección pero esa intersección tiene un número negativo? tmin a veces se devuelve como un número negativo.
SirYakalot
1
ah, es cuando el origen está dentro de la caja
SirYakalot
14

Nadie describió el algoritmo aquí, pero el algoritmo Graphics Gems es simplemente:

  1. Usando el vector de dirección de tu rayo, determina qué 3 de los 6 planos candidatos serían golpeados primero . Si su vector de dirección de rayos (no normalizado) es (-1, 1, -1), entonces los 3 planos que se pueden golpear son + x, -y y + z.

  2. De los 3 planos candidatos, encuentre el valor t para la intersección de cada uno. Acepte el plano que obtiene el valor t más grande como el plano que recibió el impacto, y verifique que el impacto esté dentro de la casilla . El diagrama en el texto deja esto claro:

ingrese la descripción de la imagen aquí

Mi implementacion:

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
fuente
+1 por explicarlo (eso también con una foto :)
legends2k
4

Esta es mi intersección de rayos 3D / AABox que he estado usando:

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
fuente
¿Qué son tneary tfar?
tekknolagi
La intersección es entre [tnear, tfar].
Jeroen Baert
3

Aquí hay una versión optimizada de lo anterior que utilizo para 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
fuente
convertido a esta unidad para su uso, y fue más rápido que el orden interna bounds.IntersectRay gist.github.com/unitycoder/8d1c2905f2e9be693c78db7d9d03a102
mgear
¿Cómo puedo interpretar el valor devuelto? ¿Es algo así como la distancia euclidiana entre el origen y el punto de intersección?
Ferdinand Mütsch
¿Qué valor tiene la distancia a la caja?
jjxtra
1

Una cosa que es posible que desee investigar es rasterizar las caras frontal y posterior de su cuadro delimitador en dos búferes separados. Representa los valores x, y, z como rgb (esto funciona mejor para un cuadro delimitador con una esquina en (0,0,0) y el opuesto en (1,1,1).

Obviamente, esto tiene un uso limitado, pero me pareció genial para renderizar volúmenes simples.

Para más detalles y código:

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

Gavan Woolery
fuente
1

Aquí está el código Line vs AABB que he estado usando:

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;
}
técnico del caos
fuente
0

Esto parece similar al código publicado por zacharmarz.
Obtuve este código del libro 'Detección de colisión en tiempo real' de Christer Ericson en la sección '5.3.3 Rayo o segmento de intersección contra la caja'

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

fuente
esto es 2d, si?
SirYakalot
Esto es solo 2D, sí. Además, el código no está tan bien pensado como el de zacharmarz, que se encarga de reducir el número de divisiones y pruebas.
sam hocevar
0

Me sorprende ver que nadie ha mencionado el método de losa sin ramas de 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;
}

Explicación completa: https://tavianator.com/fast-branchless-raybounding-box-intersections/

Tyron
fuente
0

He agregado a @zacharmarz la respuesta para manejar cuando el origen del rayo está dentro del AABB. En este caso, tmin será negativo y detrás del rayo, por lo que tmax es la primera intersección entre el rayo y 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
fuente