algorithmes de collision AABB vs Ray les plus efficaces

53

Existe-t-il un algorithme «le plus efficace» pour la détection de collision AABB vs Ray?

Je suis récemment tombé sur l'algorithme de collision Arvo AABB vs Sphere d'Arvo, et je me demande s'il existe un algorithme similaire à cet effet.

Une condition préalable à cet algorithme est que je dois avoir la possibilité d’interroger le résultat sur la distance entre l’origine du rayon et le point de collision. Cela dit, s’il existe un autre algorithme plus rapide qui ne renvoie pas la distance, alors en plus d’en afficher un qui le fait, il serait également très utile d’afficher cet algorithme.

Indiquez également quel est l'argument de retour de la fonction et comment vous l'utilisez pour renvoyer une distance ou un cas «sans collision». Par exemple, existe-t-il un paramètre de sortie pour la distance ainsi qu’une valeur de retour booléenne? ou retourne-t-il simplement un float avec la distance, vs une valeur de -1 pour aucune collision?

(Pour ceux qui ne connaissent pas: AABB = Axis Bounding Box Alignement)

SirYakalot
la source
Je peux me tromper mais je pense que vous obtiendrez quand même des faux positifs avec cet algorithme. Vous avez raison de dire que si tous les angles sont du même côté lors de la vérification de l’axe 3, il n’y aura pas de collision. Mais il semble que vous pouvez toujours avoir la condition où les 3 axes ont des points des deux côtés et n'ont toujours pas de collision. Je vérifie généralement si les distances d’entrée / de sortie se chevauchent sur les trois dalles pour en être sûr. Cela provient du site des outils géométriques.
Steve H
Pourquoi la condition indispensable pour l'interrogation de distance? S'il existe un algorithme encore plus rapide pour le cas où vous n'avez pas besoin de la distance, ne voulez-vous pas en savoir plus?
Sam Hocevar
non, pas vraiment. J'ai besoin de savoir à quelle distance se produit la collision.
SirYakalot
En fait, je suppose que vous avez raison, je vais modifier la question.
SirYakalot
4
Comme je l'ai écrit dans votre autre sujet, il existe une bonne ressource pour ce type d'algorithme ici: realtimerendering.com/intersections.html
Tetrad

Réponses:

22

Andrew Woo, qui, avec John Amanatides, a développé l'algorithme de Raymarching (DDA) utilisé de manière omniprésente dans les traceurs de rayons, a écrit "Fast Ray-Box Intersection" (source alternative ici ), publié dans Graphics Gems, 1990, p. 395-396. Plutôt que d'être construit spécifiquement pour l'intégration via une grille (par exemple, un volume de voxel) comme DDA (voir la réponse de zacharmarz), cet algorithme est spécifiquement adapté aux mondes qui ne sont pas répartis de manière uniforme, tels que votre monde de polyhèdres typique trouvé dans la plupart des environnements 3D. Jeux.

L'approche prend en charge la 3D et effectue éventuellement le retrait de la face arrière. L'algorithme est dérivé des mêmes principes d'intégration que ceux utilisés dans les DDA, il est donc très rapide. Plus de détails peuvent être trouvés dans le volume original Graphics Gems (1990).

De nombreuses autres approches spécifiques à Ray-AABB sont disponibles sur realtimerendering.com .

EDIT: Une approche alternative, sans branche - qui serait souhaitable à la fois sur le processeur graphique et le processeur - peut être trouvée ici .

Ingénieur
la source
ah! vous m'avez battu, je viens de le trouver ce matin. Super trouvaille!
SirYakalot
Plaisir, Monsieur. Je suggérerais également de comparer tous les algorithmes que vous trouverez sur ce type de base. (Il y a d'autres listes officielles comme celle-ci ailleurs, mais je n'en trouve pas pour le moment.)
Ingénieur
L'article est ici
bobobobo
1
Une implémentation bien commentée de l'algorithme de Woo peut être trouvée ici .
Ingénieur
4
Les deux liens que vous fournissez génèrent respectivement les erreurs "
Introuvable
46

Ce que j'ai utilisé précédemment dans mon 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 cela retourne vrai, c'est intersectant. S'il renvoie faux, ce n'est pas intersection.

Si vous utilisez plusieurs fois le même rayon, vous pouvez pré-calculer dirfrac(division uniquement dans le test d'intersection complet). Et puis c'est vraiment rapide. Et vous avez également la longueur du rayon jusqu'à l'intersection (stockée dans t).

zacharmarz
la source
serait-il possible de fournir une clé pour ce que vos noms de variable signifient?
SirYakalot
1
J'ai essayé d'ajouter une explication dans les commentaires. Donc: "r" est un rayon, "r.dir" est son vecteur de direction unitaire, "r.org" est son origine, d'où vous tirez un rayon, "dirfrac" est simplement une optimisation, car vous pouvez l'utiliser toujours pour le même rayon. (vous n’êtes pas obligé de diviser) et cela signifie 1 / r.dir. Alors "lb" est le coin de l’AABB avec les 3 coordonnées minimales et "rb" est le coin opposé - coin avec les coordonnées maximales. Le paramètre de sortie "t" est la longueur du vecteur de l'origine à l'intersection.
Zacharmarz
à quoi ressemble la définition de la fonction? Est-il possible de connaître la distance parcourue par la collision sur le rayon?
SirYakalot
1
alors que signifie votre algorithme quand il retourne une intersection mais que cette intersection a un nombre négatif? tmin est parfois retourné sous forme de nombre négatif.
SirYakalot
1
ah, c'est quand l'origine est à l'intérieur de la boîte
SirYakalot
14

Personne n'a décrit l'algorithme ici, mais l' algorithme Graphics Gems est simplement:

  1. En utilisant le vecteur de direction de votre rayon, déterminez quels 3 des 6 avions candidats seraient touchés en premier . Si votre vecteur de direction de rayon (non normalisé) est (-1, 1, -1), les 3 plans pouvant être touchés sont + x, -y et + z.

  2. Trouvez la valeur t de l'intersection pour chacun des 3 plans candidats. Acceptez l'avion qui obtient la plus grande valeur t comme l'avion touché et vérifiez qu'il est dans la case . Le diagramme dans le texte montre clairement ceci:

entrez la description de l'image ici

Ma mise en oeuvre:

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
la source
+1 pour l'expliquer réellement (cela aussi avec une image :)
legends2k
4

Voici mon intersection 3D rayon / AABox que j'utilise:

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
la source
Que sont tnearet tfar?
tekknolagi
L'intersection est entre [tnear, tfar].
Jeroen Baert
3

Voici une version optimisée de ce qui précède que j'utilise pour le 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
la source
converti ce pour l' unité, et il était plus rapide que builtin bounds.IntersectRay gist.github.com/unitycoder/8d1c2905f2e9be693c78db7d9d03a102
Mgear
Comment puis-je interpréter la valeur renvoyée? Cela ressemble-t-il à la distance euclidienne entre l'origine et le point d'intersection?
Ferdinand Mütsch le
Quelle est la valeur de la distance à la boîte?
jjxtra
1

Une des choses que vous voudrez peut-être étudier est de rastériser le recto et le verso de votre cadre de sélection dans deux mémoires tampons séparées. Rendez les valeurs x, y, z en tant que rgb (cela fonctionne mieux pour un cadre de sélection avec un coin à (0,0,0) et le contraire à (1,1,1).

Évidemment, son utilisation est limitée, mais je l’ai trouvé génial pour le rendu de volumes simples.

Pour plus de détails et code:

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

Gavan Woolery
la source
1

Voici le code de ligne vs AABB que j'utilise:

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;
}
technicien chaos
la source
0

Cela semble similaire au code publié par zacharmarz.
J'ai obtenu ce code dans le livre "Détection de collision en temps réel" de Christer Ericson dans la section "5.3.3 Rayons ou segments se croisant contre la boîte".

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

la source
c'est 2d, oui?
SirYakalot
Ce n'est que 2D, oui. En outre, le code n'est pas aussi bien pensé que celui de zacharmarz, qui prend en charge la réduction du nombre de divisions et de tests.
Sam Hocevar
0

Je suis surpris de voir que personne n'a mentionné la méthode des dalles sans branches 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;
}

Explication complète: https://tavianator.com/fast-branchless-raybounding-box-intersections/

Tyron
la source
0

J'ai ajouté à @zacharmarz answer pour traiter lorsque l'origine du rayon est à l'intérieur de l'AABB. Dans ce cas, tmin sera négatif et derrière le rayon de sorte que tmax est la première intersection entre le rayon et 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
la source