effizientesten Kollisionsalgorithmen von AABB gegen Ray

53

Gibt es einen bekannten, 'effizientesten' Algorithmus für die Erkennung von AABB-Ray-Kollisionen?

Kürzlich bin ich über den Kollisionsalgorithmus AABB vs Sphere von Arvo gestolpert, und ich frage mich, ob es dafür einen ähnlich bemerkenswerten Algorithmus gibt.

Eine Bedingung für diesen Algorithmus muss sein, dass ich die Option haben muss, das Ergebnis für die Entfernung vom Ursprung des Strahls zum Kollisionspunkt abzufragen. Wenn es jedoch einen anderen, schnelleren Algorithmus gibt, der keine Distanz zurückgibt, dann wäre es in der Tat sehr hilfreich, zusätzlich zu einem, der dies tut, auch diesen Algorithmus zu veröffentlichen.

Bitte geben Sie auch an, was das Rückgabeargument der Funktion ist und wie Sie es verwenden, um die Distanz oder einen Fall ohne Kollision zurückzugeben. Hat es beispielsweise einen out-Parameter für die Entfernung sowie einen bool-Rückgabewert? oder gibt es einfach einen float mit der entfernung gegen einen wert von -1 für keine kollision zurück?

(Für diejenigen, die nicht wissen: AABB = Axis Aligned Bounding Box)

SirYakalot
quelle
Ich könnte mich irren, aber ich denke, Sie werden mit diesem Algorithmus immer noch falsch-positive Ergebnisse erzielen. Sie haben Recht, dass es keine Kollision gibt, wenn sich alle Ecken bei der Überprüfung der 3-Achsen auf derselben Seite befinden. Aber es scheint, als ob Sie immer noch die Bedingung haben können, dass alle 3 Achsen auf beiden Seiten Punkte haben und immer noch keine Kollision haben. Ich überprüfe im Allgemeinen, ob sich die Ein- und Ausstiegsentfernungen auf allen drei Platten überschneiden, um sicherzugehen. Es ist von der Geometric-Tools-Site.
Steve H
Warum muss die Bedingung für die Distanzabfrage vorliegen? Wenn es einen noch schnelleren Algorithmus für den Fall gibt, dass Sie die Entfernung nicht benötigen, möchten Sie auch nichts darüber wissen?
Sam Hocevar
nun, nein, nicht wirklich. Ich muss wissen, in welcher Entfernung die Kollision stattfindet.
SirYakalot
Eigentlich nehme ich an, du hast recht, ich bearbeite die Frage.
SirYakalot
4
Wie ich in Ihrem anderen Thread geschrieben habe, gibt es hier eine gute Ressource für diese Art von Algorithmen: realtimerendering.com/intersections.html
Tetrad

Antworten:

22

Andrew Woo, der zusammen mit John Amanatides den in Raytracern allgegenwärtig verwendeten Raymarching-Algorithmus (DDA) entwickelte, schrieb "Fast Ray-Box Intersection" (alternative Quelle hier ), der in Graphics Gems, 1990, S. 395-396 veröffentlicht wurde. Dieser Algorithmus ist nicht speziell für die Integration durch ein Gitter (z. B. ein Voxelvolumen) wie DDA (siehe zacharmarz 'Antwort) entwickelt worden, sondern eignet sich speziell für Welten, die nicht gleichmäßig unterteilt sind, wie z. B. Ihre typische Polyederwelt in den meisten 3D-Umgebungen Spiele.

Der Ansatz bietet Unterstützung für 3D und führt optional das Backface-Culling durch. Der Algorithmus basiert auf den gleichen Integrationsprinzipien wie in DDAs und ist daher sehr schnell. Weitere Details finden Sie im Original Graphics Gems Band (1990).

Viele andere Ansätze speziell für Ray-AABB finden Sie auf realtimerendering.com .

BEARBEITEN: Ein alternativer, verzweigungsloser Ansatz - der sowohl für die GPU als auch für die CPU wünschenswert wäre - kann hier gefunden werden .

Techniker
quelle
Ah! du hast mich verprügelt, ich bin heute morgen darauf gestoßen. Toller Fund!
SirYakalot
Vergnügen, Sir. Ich würde auch vorschlagen, alle Algorithmen zu vergleichen, die Sie auf dieser Basis finden. (Es gibt weitere offizielle Listen wie diese an anderer Stelle, aber
Ingenieur
Der Artikel ist hier
Bobobobo
1
Eine gut kommentierte Implementierung des Woo-Algorithmus finden Sie hier .
Ingenieur
4
Die beiden von Ihnen
bereitgestellten
46

Was ich früher in meinem Raytracer verwendet habe:

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

Wenn dies wahr ist, schneidet es sich, wenn es falsch ist, schneidet es sich nicht.

Wenn Sie denselben Strahl mehrmals verwenden, können Sie vorberechnen dirfrac(nur Teilung im gesamten Schnittpunkttest). Und dann geht es richtig schnell. Und Sie haben auch Länge des Strahls bis zur Kreuzung (gespeichert in t).

Zacharmarz
quelle
Wäre es möglich, einen Schlüssel für die Bedeutung Ihrer Variablennamen anzugeben?
SirYakalot
1
Ich habe versucht, einige Erklärungen in die Kommentare aufzunehmen. Also: "r" ist ray, "r.dir" ist der Einheitsrichtungsvektor, "r.org" ist der Ursprung, von dem aus Sie ray schießen, "dirfrac" ist nur eine Optimierung, da Sie es immer für denselben ray verwenden können (Sie müssen keine Division durchführen) und es bedeutet 1 / r.dir. Dann ist "lb" die Ecke von AABB mit allen 3 Koordinaten minimal und "rb" ist die gegenüberliegende Ecke mit den maximalen Koordinaten. Der Ausgabeparameter "t" ist die Länge des Vektors vom Ursprung bis zum Schnittpunkt.
Zacharmarz
Wie sieht die Funktionsdefinition aus? Ist es möglich, die Entfernung herauszufinden, aus der die Kollision auf dem Strahl aufgetreten ist?
SirYakalot
1
Was bedeutet Ihr Algorithmus, wenn er eine Kreuzung zurückgibt, diese aber eine negative Zahl hat? tmin wird manchmal als negative Zahl zurückgegeben.
SirYakalot
1
Ah, es ist, wenn der Ursprung in der Box ist
SirYakalot
14

Niemand hat den Algorithmus hier beschrieben, aber der Graphics Gems-Algorithmus ist einfach:

  1. Bestimmen Sie anhand des Richtungsvektors Ihres Strahls, welche 3 der 6 möglichen Flugzeuge zuerst getroffen werden . Wenn Ihr (nicht normalisierter) Strahlrichtungsvektor (-1, 1, -1) ist, sind die 3 Ebenen, die getroffen werden können, + x, -y und + z.

  2. Finden Sie von den 3 Kandidatenebenen für jede den t-Wert für den Schnittpunkt. Akzeptieren Sie die Ebene, die den größten t- Wert erhält , als die Ebene, die getroffen wurde, und überprüfen Sie, ob der Treffer innerhalb des Felds liegt . Das Diagramm im Text macht dies deutlich:

Bildbeschreibung hier eingeben

Meine Implementierung:

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
quelle
+1 für die tatsächliche Erklärung (das auch mit einem Bild :)
legends2k
4

Dies ist meine 3D-Ray / AABox-Kreuzung, die ich verwendet habe:

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
quelle
Was sind tnearund tfar?
Tekknolagi
Der Schnittpunkt liegt zwischen [tnear, tfar].
Jeroen Baert
3

Hier ist eine optimierte Version der oben genannten, die ich für die GPU verwende:

__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
quelle
dies für die Einheit Nutzung umgewandelt, und es war schneller als builtin bounds.IntersectRay gist.github.com/unitycoder/8d1c2905f2e9be693c78db7d9d03a102
Mgear
Wie kann ich den zurückgegebenen Wert interpretieren? Ist es so etwas wie der euklidische Abstand zwischen Ursprung und Schnittpunkt?
Ferdinand Mütsch
Welchen Wert hat der Abstand zur Box?
12.
1

Möglicherweise möchten Sie die Vorder- und Rückseite Ihres Begrenzungsrahmens in zwei separaten Puffern rastern. Rendern Sie die x, y, z-Werte als rgb (dies funktioniert am besten für einen Begrenzungsrahmen mit einer Ecke bei (0,0,0) und der gegenüberliegenden bei (1,1,1).

Natürlich hat dies nur eine begrenzte Verwendung, aber ich fand es großartig, um einfache Volumes zu rendern.

Für mehr Details und Code:

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

Gavan Woolery
quelle
1

Hier ist der Code von Line vs AABB, den ich verwendet habe:

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
quelle
0

Dies scheint dem von zacharmarz geposteten Code zu ähneln.
Ich habe diesen Code aus dem Buch 'Real-Time Collision Detection' von Christer Ericson im Abschnitt '5.3.3 Ray oder Segment gegen Box schneiden' erhalten.

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

quelle
das ist 2d, ja?
SirYakalot
Das ist nur 2D, ja. Außerdem ist der Code nicht so gut durchdacht wie der von Zacharmarz, der sich darum kümmert, die Anzahl der Unterteilungen und Tests zu verringern.
Sam Hocevar
0

Ich bin überrascht zu sehen, dass niemand die astlose Plattenmethode von Tavian erwähnt hat

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

Vollständige Erklärung: https://tavianator.com/fast-branchless-raybounding-box-intersections/

Tyron
quelle
0

Ich habe @zacharmarz Antwort hinzugefügt, um zu behandeln, wann der Strahlursprung innerhalb des AABB ist. In diesem Fall ist tmin negativ und liegt hinter dem Strahl, sodass tmax der erste Schnittpunkt zwischen dem Strahl und AABB ist.

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