algoritmos de colisão AABB vs Ray mais eficientes

53

Existe um algoritmo conhecido 'mais eficiente' para a detecção de colisões AABB vs Ray?

Recentemente, deparei com o algoritmo de colisão AABB vs Sphere do Arvo, e estou me perguntando se existe um algoritmo igualmente digno de nota para isso.

É preciso ter condição para esse algoritmo: eu preciso ter a opção de consultar o resultado para a distância da origem do raio até o ponto de colisão. Dito isto, se houver outro algoritmo mais rápido que não retorne distância, além de postar um que o faça, postar esse algoritmo também seria muito útil.

Indique também qual é o argumento de retorno da função e como você o usa para retornar a distância ou um caso de 'sem colisão'. Por exemplo, ele possui um parâmetro out para a distância e também um valor de retorno bool? ou simplesmente retorna um float com a distância, vs um valor de -1 para nenhuma colisão?

(Para quem não sabe: AABB = Caixa delimitadora alinhada ao eixo)

SirYakalot
fonte
Posso estar errado, mas acho que você ainda obterá falsos positivos com esse algoritmo. Você está certo que, se todos os cantos estiverem do mesmo lado ao verificar o eixo 3, não haverá colisão. Mas parece que você ainda pode ter a condição em que todos os 3 eixos têm pontos em ambos os lados e ainda não têm colisão. Geralmente, verifico se as distâncias de entrada / saída se sobrepõem nas três lajes para ter certeza. É do site de ferramentas geométricas.
211111 Steve
Por que o deve ter condição para consulta à distância? Se houver um algoritmo ainda mais rápido para o caso em que você não precisa da distância, não quer saber também?
Sam Hocevar
bem, não, na verdade não. Preciso saber a que distância a colisão acontece.
perfil completo de SirYakalot
na verdade, suponho que você esteja certo, vou editar a pergunta.
precisa saber é o seguinte
4
Como eu publiquei em seu outro tópico, há um bom recurso para esses tipos de algoritmos aqui: realtimerendering.com/intersections.html
Tetrad

Respostas:

22

Andrew Woo, que, juntamente com John Amanatides, desenvolveu o algoritmo raymarching (DDA) usado onipresente em rastreadores de raios, escreveu "Fast Ray-Box Intersection" (fonte alternativa aqui ), que foi publicado em Graphics Gems, 1990, pp. 395-396. Em vez de ser construído especificamente para a integração por meio de uma grade (por exemplo, um volume voxel) como é o DDA (consulte a resposta de zacharmarz), esse algoritmo é adequado especificamente para mundos que não são subdivididos de maneira uniforme, como o mundo típico dos poliedros encontrado na maioria dos 3D jogos

A abordagem fornece suporte para 3D e, opcionalmente, faz a seleção da face posterior. O algoritmo é derivado dos mesmos princípios de integração usados ​​nos DDAs, por isso é muito rápido. Mais detalhes podem ser encontrados no volume original Graphics Gems (1990).

Muitas outras abordagens especificamente para o Ray-AABB podem ser encontradas em realtimerendering.com .

EDIT: Uma abordagem alternativa, sem ramificação - que seria desejável na GPU e na CPU - pode ser encontrada aqui .

Engenheiro
fonte
ah! você me venceu, acabei de encontrar esta manhã. Ótima descoberta!
perfil completo de SirYakalot
Prazer, senhor. Eu também sugeriria comparar todos os algoritmos encontrados nesse tipo de base. (Existem mais listas oficiais como essa em outros lugares, mas não conseguimos encontrar nenhuma no momento.) #
Engenharia
O artigo está aqui
bobobobo 13/10/12
11
Uma implementação bem comentada do algoritmo de Woo pode ser encontrada aqui .
Engineer
4
Os dois links que você fornecer gerar "Not Found" e "proibido" erros respectivamente ...
liggiorgio
46

O que eu tenho usado anteriormente no meu 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;

Se isso retorna verdadeiro, ele está se cruzando, se ele retorna falso, não está se cruzando.

Se você usar o mesmo raio várias vezes, poderá pré-calcular dirfrac(apenas divisão no teste de interseção inteiro). E então é muito rápido. E você também tem comprimento de raio até a interseção (armazenada em t).

zacharmarz
fonte
seria possível fornecer uma chave para o que seus nomes de variável significam?
SirYakalot
11
Eu tentei adicionar alguma explicação nos comentários. Então: "r" é raio, "r.dir" é o vetor de direção da unidade, "r.org" é a origem da qual você dispara o raio, "dirfrac" é apenas otimização, porque você pode usá-lo sempre para o mesmo raio (você não precisa fazer divisão) e isso significa 1 / r.dir. Então "lb" é o canto do AABB com as três coordenadas mínimas e "rb" é o oposto - o canto com o máximo de coordenadas. O parâmetro "t" de saída é o comprimento do vetor da origem à interseção.
Zacharmarz 14/10
como é a definição de função? É possível descobrir a distância que a colisão ocorreu no raio?
perfil completo de SirYakalot
11
então, o que seu algoritmo significa quando retorna uma interseção, mas essa interseção tem um número negativo? Às vezes, tmin é retornado como um número negativo.
SirYakalot
11
ah, é quando a origem está dentro da caixa
SirYakalot 14/12/11
14

Ninguém descreveu o algoritmo aqui, mas o algoritmo Graphics Gems é simplesmente:

  1. Usando o vetor de direção do raio, determine quais dos três aviões candidatos seriam atingidos primeiro . Se o seu vetor de direção do raio (não normalizado) for (-1, 1, -1), os três planos que podem ser atingidos são + x, -y e + z.

  2. Dos 3 planos candidatos, encontre o valor t para a interseção de cada um. Aceite o plano que obtiver o maior valor de t como sendo o avião atingido e verifique se o hit está dentro da caixa . O diagrama no texto deixa isso claro:

insira a descrição da imagem aqui

Minha implementação:

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
fonte
+1 para realmente explicá-lo (que também com uma imagem :)
legends2k
4

Esta é a minha interseção de raio 3D / AABox que estou 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
fonte
O que são tneare tfar?
7115
A interseção é entre [tnear, tfar].
Jeroen Baert
3

Aqui está uma versão otimizada do que eu uso acima 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
fonte
convertida este para uso unidade, e foi mais rápido do que builtin bounds.IntersectRay gist.github.com/unitycoder/8d1c2905f2e9be693c78db7d9d03a102
mgear
Como posso interpretar o valor retornado? É algo como a distância euclidiana entre origem e ponto de interseção?
Ferdinand Mütsch
Qual o valor da distância da caixa?
jjxtra 12/08
1

Uma coisa que você pode querer investigar é rasterizar a frente e o verso da sua caixa delimitadora em dois buffers separados. Renderize os valores x, y, z como rgb (isso funciona melhor para uma caixa delimitadora com um canto em (0,0,0) e o oposto em (1,1,1).

Obviamente, isso tem uso limitado, mas achei ótimo para renderizar volumes simples.

Para mais detalhes e código:

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

Gavan Woolery
fonte
1

Aqui está o código Line vs AABB que eu tenho usado:

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;
}
caosTechnician
fonte
0

Isso parece semelhante ao código postado por zacharmarz.
Eu obtive esse código do livro 'Real-Time Collision Detection', de Christer Ericson, na seção '5.3.3 Interseção de raio ou segmento contra caixa'

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

fonte
isso é 2d, sim?
perfil completo de SirYakalot
Isso é apenas 2D, sim. Além disso, o código não é tão bem pensado quanto o de zacharmarz, que cuida de reduzir o número de divisões e testes.
Sam Hocevar
0

Estou surpreso ao ver que ninguém mencionou o método de laje sem galhos 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;
}

Explicação completa: https://tavianator.com/fast-branchless-raybounding-box-intersections/

Tyron
fonte
0

Adicionei à resposta @zacharmarz para lidar com quando a origem do raio está dentro da AABB. Nesse caso, tmin será negativo e atrás do raio, então tmax é a primeira interseção entre o raio e o 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
fonte