Gegeben eine bounding-box und eine Linie (zwei Punkte) bestimmen Sie, wenn die Linie schneidet die box

Gegeben, eine bounding-box, mit Definitionen wie bounds.min.(x/y/z), bounds.max.(x/y/z) und zwei Punkte im 3D-Raum (ausgedrückt als Vector3 Objekte), wie kann ich bestimmen, ob die Linie durch die beiden Punkte schneidet die bounding box?

InformationsquelleAutor qJake | 2010-07-13

c#c#-2.0 math vector

11

Let me google das für Sie: Line-Box Intersection (http://www.3dkingdoms.com/weekly/weekly.php?a=3)

Einen anderen link, mit Referenzen (und code) für eine Vielzahl von Schnittpunkt-tests: http://www.realtimerendering.com/intersections.html

Wenn du mehr erfahren möchtest über die Kreuzung tests, das ist eine Bibel: Real-Time Collision Detection (Amazon)

EDIT: der Algorithmus in diesem Papier ("Eine Effiziente und Robust Ray-Box Intersection Algorithm", Amy Williams und Steve Barrus und R. Keith Morley und Peter Shirley; journal of graphics, gpu -, und game tools, Vol. 10(1), 49-54, 2005) sieht besonders prägnant und kommt mit (C++) source code zu.

Nach dem konvertieren Sie den code in das erste Glied zu nicht-hässlichen C++, es scheint zu funktionieren für die meisten Teil. Ich poste den code hier für alle anderen, die es braucht, so dass Sie nicht haben, um Sie zu konvertieren, zu.
Ich sammle einige persönliche Unterhaltung aus der Tatsache, dass ich habe zu dieser Antwort, weil ich es gegoogelt...

InformationsquelleAutor Greg S
5

Hier ist ein Weg, es zu tun, wenn Sie wollen, um die Mathematik zu tun Sie sich selbst: Schneiden Sie die Zeile, die mit jeder der 6 Ebenen erstellt, die von der bounding-box.

Die Vektor-Darstellung der Zeile ist X = B + t*D, wobei B ist ein Tupel (x,y,z) des Basis-Punkt (sagen wir, dein Erster Punkt) und D ist die Richtung der Linie, wiederum ausgedrückt als ein Tupel (dx, dy, dz). Erhalten Sie die Richtung, indem einer der Punkte, die von den anderen, also, wenn Sie die Punkte P1 (x1, y1, z1) und P2(x2, y2, z2), dann ist D = P2 - P1 und B = P1, d.h. D = (x2 - x1, y2-y1, z2-z1). Wir nennen die Elemente dieses Vektors dx, dy und dz.

Die parametrische Darstellung der Ebene ist x + y + z = c. So konvertieren Sie Ihre bounding-box, um diese represenation und dann verwenden Sie die parametrische Darstellung der Linie, z.B. die drei Gleichungen x = x1 + tdx, y = y1 + tdy, z = y1+t*dz, ersetzen Sie x,y und z, die in Ihrem Flugzeug Gleichung. Lösen nach t auf. Da jeder der 6 Ebenen wird parallel zu der Ebene, erzeugt durch 2 von der Achse, Ihr problem wird einfacher; zum Beispiel für die Ebene, die parallel zu der Ebene erzeugt, indem die x-und y-Achse, Ihre Flugzeug-Gleichung wird damit zu z = c, wobei c ist die z-Koordinate eines Ihrer bounding-box-Punkte, und so weiter.

Verwenden jetzt t berechnen Sie den Schnittpunkt der Linie mit der Ebene. (Wenn t < 0 > 1, dann wird Ihre Linie schneidet, die AUßERHALB von P1-P2, wenn t >= 0 und t <= 1, dann wird Ihre Linie schneidet die Ebene irgendwo zwischen P1 und P2)

Nun Sie sind noch nicht fertig. Die Flugzeug-Gleichung liefert Sie ein Flugzeug, nicht ein Rechteck, also der Schnittpunkt mit der Ebene könnte tatsächlich AUßERHALB Ihres Rechteck, aber da haben Sie nun die Koordinaten des Schnittpunktes (x = x1 + t * dx und so weiter), können Sie leicht sehen, ob dieser Punkt innerhalb des Rechtecks Ihre bounding-box. Dein problem ist nun reduziert, um zu überprüfen, ob ein Punkt im 2D-Raum befindet sich innerhalb eines Begrenzungsrahmens, das ist trivial zu überprüfen.

Natürlich die erste Sache, die Sie tun sollten, wenn Sie tatsächlich nutzen diese Lösung ist zu überprüfen, ob die Zeile ist auch ausgerichtet auf eine Achse, weil in diesem Fall, Ihr Schnittpunkt code banal und es wird auch kümmern uns um das problem der Linie, nicht schneidende einige Flächen, z.B. große oder kleine zahlen von t, vielleicht sogar über - oder unter -.

Ich Wette, es gibt schnellere Wege, dies zu tun, aber es wird funktionieren.

Wenn es gibt schnellere Wege, dies zu tun ich muss wissen, über Sie, weil dieser code ausgeführt wird, überall bis zu 100-mal pro Sekunde, und jede Berechnung, die ich hinzufügen, verlangsamt das Spiel.
Hmmm, eigentlich denke ich, dass der Algorithmus Sie geschrieben ist LANGSAMER als das, was ich vorgeschlagen, weil es scheint, arbeiten mit Vektoren, z.B. viele der Additionen und vier Multiplikationen für jeden Aufruf GetIntersection, weil es nicht optimiert auf die Tatsache, dass Ihre bounding-box ausgerichtet wird das Koordinatensystem, das heißt, Sie werfen zwei der drei parametrischen Gleichungen für jedes Flugzeug Kreuzung. Ich denke, Sie können sich mit einer einzigen Multiplikation pro Kreuzung.
Ooops, Nein, tut mir Leid. verwerfen die. Sie müssen die drei Multiplikationen zur Berechnung der Koordinaten der hit. Verdammt.

InformationsquelleAutor JeSuisse

Hier ist der code scheint zu funktionieren, Umgerechnet aus Greg ' S die Antwort in C#:

bool CheckLineBox(Vector3 B1, Vector3 B2, Vector3 L1, Vector3 L2, ref Vector3 Hit)
{
    if (L2.x < B1.x && L1.x < B1.x) return false;
    if (L2.x > B2.x && L1.x > B2.x) return false;
    if (L2.y < B1.y && L1.y < B1.y) return false;
    if (L2.y > B2.y && L1.y > B2.y) return false;
    if (L2.z < B1.z && L1.z < B1.z) return false;
    if (L2.z > B2.z && L1.z > B2.z) return false;
    if (L1.x > B1.x && L1.x < B2.x &&
        L1.y > B1.y && L1.y < B2.y &&
        L1.z > B1.z && L1.z < B2.z)
    {
        Hit = L1;
        return true;
    }
    if ((GetIntersection(L1.x - B1.x, L2.x - B1.x, L1, L2, ref Hit) && InBox(Hit, B1, B2, 1))
      || (GetIntersection(L1.y - B1.y, L2.y - B1.y, L1, L2, ref Hit) && InBox(Hit, B1, B2, 2))
      || (GetIntersection(L1.z - B1.z, L2.z - B1.z, L1, L2, ref Hit) && InBox(Hit, B1, B2, 3))
      || (GetIntersection(L1.x - B2.x, L2.x - B2.x, L1, L2, ref Hit) && InBox(Hit, B1, B2, 1))
      || (GetIntersection(L1.y - B2.y, L2.y - B2.y, L1, L2, ref Hit) && InBox(Hit, B1, B2, 2))
      || (GetIntersection(L1.z - B2.z, L2.z - B2.z, L1, L2, ref Hit) && InBox(Hit, B1, B2, 3)))
        return true;

    return false;
}

bool GetIntersection(float fDst1, float fDst2, Vector3 P1, Vector3 P2, ref Vector3 Hit)
{
    if ((fDst1 * fDst2) >= 0.0f) return false;
    if (fDst1 == fDst2) return false;
    Hit = P1 + (P2 - P1) * (-fDst1 / (fDst2 - fDst1));
    return true;
}

bool InBox(Vector3 Hit, Vector3 B1, Vector3 B2, int Axis)
{
    if (Axis == 1 && Hit.z > B1.z && Hit.z < B2.z && Hit.y > B1.y && Hit.y < B2.y) return true;
    if (Axis == 2 && Hit.z > B1.z && Hit.z < B2.z && Hit.x > B1.x && Hit.x < B2.x) return true;
    if (Axis == 3 && Hit.x > B1.x && Hit.x < B2.x && Hit.y > B1.y && Hit.y < B2.y) return true;
    return false;
}

InformationsquelleAutor qJake

1

Können Sie stellen Sie die bounding-box als 12 Dreiecke (2 für jede der 6 Flächen). Dann können Sie überprüfen, Schnittpunkt der Linie mit jedem von Ihnen. Ich habe ein line-triangle intersection-Funktion, aber geschrieben wurde es für meine eigene software-rendering-engine, nicht für D3D. Ich kann versuchen, es zu konvertieren, benötigen Sie den code.

Ich konnte dies tun, aber ich weiß nicht, wie performant wäre es... das läuft jedes "Update", so viele Male pro Sekunde, und ich bin nicht sicher, wie es ergehen würde, aber es ist sicherlich einen Versuch Wert. Wenn Sie nach dem code für line - /Dreieck-Kreuzung, und ich kann, dass die Arbeit (und es ist nicht langsam), ich werde es dir geben.

InformationsquelleAutor max

JavaScript-version, basierend auf SpikeX Antwort und glMatrix:

//all args are Vec3, Hit will be filled by this algo
function checkLineBox( B1, B2, L1, L2, Hit)
{
    if (L2[0] < B1[0] && L1[0] < B1[0]) return false;
    if (L2[0] > B2[0] && L1[0] > B2[0]) return false;
    if (L2[1] < B1[1] && L1[1] < B1[1]) return false;
    if (L2[1] > B2[1] && L1[1] > B2[1]) return false;
    if (L2[2] < B1[2] && L1[2] < B1[2]) return false;
    if (L2[2] > B2[2] && L1[2] > B2[2]) return false;
    if (L1[0] > B1[0] && L1[0] < B2[0] &&
        L1[1] > B1[1] && L1[1] < B2[1] &&
        L1[2] > B1[2] && L1[2] < B2[2])
    {
        vec3.set( L1, Hit);
        return true;
    }

    if ((getIntersection(L1[0] - B1[0], L2[0] - B1[0], L1, L2, Hit) && inBox(Hit, B1, B2, 1))
      || (getIntersection(L1[1] - B1[1], L2[1] - B1[1], L1, L2, Hit) && inBox(Hit, B1, B2, 2))
      || (getIntersection(L1[2] - B1[2], L2[2] - B1[2], L1, L2, Hit) && inBox(Hit, B1, B2, 3))
      || (getIntersection(L1[0] - B2[0], L2[0] - B2[0], L1, L2, Hit) && inBox(Hit, B1, B2, 1))
      || (getIntersection(L1[1] - B2[1], L2[1] - B2[1], L1, L2, Hit) && inBox(Hit, B1, B2, 2))
      || (getIntersection(L1[2] - B2[2], L2[2] - B2[2], L1, L2, Hit) && inBox(Hit, B1, B2, 3)))
        return true;

    return false;
}

var temp = vec3.create();
function getIntersection( fDst1, fDst2, P1, P2, Hit)
{
    if ((fDst1 * fDst2) >= 0) return false;
    if (fDst1 == fDst2) return false;

    vec3.subtract(P2, P1, temp);
    vec3.scale( temp, (-fDst1 / (fDst2 - fDst1)));
    vec3.add( temp, P1, Hit);

    return true;
}

function inBox(Hit, B1, B2, Axis)
{
    if (Axis == 1 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[1] > B1[1] && Hit[1] < B2[1]) return true;
    if (Axis == 2 && Hit[2] > B1[2] && Hit[2] < B2[2] && Hit[0] > B1[0] && Hit[0] < B2[0]) return true;
    if (Axis == 3 && Hit[0] > B1[0] && Hit[0] < B2[0] && Hit[1] > B1[1] && Hit[1] < B2[1]) return true;
    return false;
}

InformationsquelleAutor Ray Hulha

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.