Punkt-Dreieck Kollisionserkennung in 3D

StackOverflow https://stackoverflow.com/questions/99542

  •  01-07-2019
  •  | 
  •  

Frage

Wie korrigiere ich für Punktfehler in der folgenden physikalischen Simulation floating:

  • Ursprungspunkt (x, y, z),
  • gewünschter Punkt (x 'y', z ') nach Kräften aufgebracht werden.
  • Zwei Dreiecke (A, B, C) und (B, C, D), die Kante BC
    • teilen

Ich bin mit dieser Methode zur Kollisionserkennung: 

For each Triangle
    If the original point is in front of the current triangle, and the desired point is behind the desired triangle:
        Calculate the intersection point of the ray (original-desired) and the plane (triangle's normal).
        If the intersection point is inside the triangle edges (!)
            Respond to the collision.
        End If
    End If
Next Triangle

Das Problem, das ich habe ist, dass manchmal der Punkt in den grauen Bereich fällt von Gleitkomma-Mathematik, wo es auf die Linie so nah vor Christus, dass es entweder mit Dreieck kollidieren nicht, obwohl es technisch immer mit einem kollidieren sollte oder die andere, da sie eine Kante teilen. Wenn dies der Punkt passiert, verläuft direkt zwischen den beiden Randteilung Dreiecke. Ich habe mit einer Zeile des Codes markiert (!) , weil ich glaube, das ist, wo ich soll eine Änderung werden zu machen.

Eine Idee, die in sehr wenige Fällen funktioniert, ist die Kantenprüfung zu überspringen. Effektiv Drehen der Dreiecke in Flugzeugen. Dies funktioniert nur, wenn meine Maschen sind konvexe Hüllen, aber ich plane konvexe Formen zu erstellen.

Ich bin mit speziell auf das Punktprodukt und Dreieck Normalen für all mein Front-Back-Testing.

War es hilfreich?

Lösung

Dies ist ein unvermeidliches Problem, wenn ein einzelnen Strahl gegen eine Geometrie mit Kanten und Ecken zu schießen. Es ist erstaunlich, wie physikalische Simulationen scheinen die kleinsten von numerischen Ungenauigkeiten zu suchen!

Einige der Erklärungen und Lösungen von anderen Befragten vorgeschlagen wird nicht funktionieren. Insbesondere gilt Folgendes:

  • Numerische Ungenauigkeit wirklich kann dazu führen, ein Strahl auf „durch den Spalt fallen“. Das Problem ist, dass wir den Strahl mit der Ebene ABC (immer den Punkt P, sagen) vor dem Test gegen Linie BC schneiden. Dann haben wir den Strahl mit dem Flugzeug BCD schneiden (immer den Punkt Q, sagt) vor dem Test gegen Linie BC. P und Q dargestellt sind beide von der engsten Annäherung Gleitkommazahl; es gibt keinen Grund zu erwarten, dass diese genau auf den Ebenen liegen, die sie eigentlich liegen, und so jede Möglichkeit, dass Sie beide P links von BC und Q rechts von BC.

  • Mit weniger als oder gleich Test nicht helfen; es ist eine Ungenauigkeit in dem Schnittpunkt des Strahls und die Ebene, die die Mühe ist.

  • Quadratwurzeln sind nicht das Problem; Sie können alle notwendigen Berechnungen unter Verwendung von Punktprodukten und Floating-Point-Division.

Hier sind einige echte Lösungen:

Lassen Sie mich stark das Buch Real-Time Collision Detection von Christer Ericson empfehlen. Es gibt eine Diskussion über dieses Problem genau auf den Seiten 446-448, und eine Erläuterung des Spatprodukt Ansatzes auf den Seiten 184-188 einen Strahl mit einem Dreieck zu schneiden.

Andere Tipps

Es klingt wie Sie nicht Prüfung einschließlich, wenn es auf den Rand des (Sie schreiben „Inside Dreieckskanten“). Versuchen Sie Code ändern zu „kleiner oder gleich“ (nach innen oder überlappend).

Ich finde es eher unwahrscheinlich, dass Ihr Strahl genau in einer Art und Weise zwischen der Dreiecke fallen würde, dass die Gleitkommagenauigkeit in Kraft treten sollte. Sind Sie absolut positiv, dass dies in der Tat das Problem?

Auf jeden Fall eine mögliche Lösung ist anstelle des Schießens nur ein Strahl drei zu schießen, die einander sehr nahe sind. Wenn man fällt genau dazwischen, dass atleast einer der beiden anderen garantiert auf einem Dreieck fallen.

Dies wird Ihnen atleast erlauben zu testen, ob das Problem wirklich der Floating-Point-Fehler ist oder etwas wahrscheinlicher.

@Statement: Ich bin ja auch schon mit einem „größer oder gleich“ -Vergleich in meinem Code, danke für die Anregung. 1

Meine aktuelle Lösung ist eine kleine Schub Menge an den Rande Test hinzuzufügen. Grundsätzlich, wenn jedes Dreieck getestet wird, werden seine Kanten durch einen sehr kleinen Betrag herausgedrückt, den Fehler in Gleitkomma- entgegenzuwirken. So ähnlich wie die Prüfung, ob das Ergebnis einer Gleitkomma-Berechnung weniger als 0,01 und nicht die Prüfung auf Gleichheit mit null.

Ist das eine vernünftige Lösung?

Wenn Sie Distanzmessungen tun, achten Sie auf Quadratwurzeln aus. Sie haben eine schlechte Angewohnheit wegzuwerfen Hälfte Ihrer Präzision. Wenn Sie ein paar von diesen Berechnungen bis stapeln, können Sie schnell in große Schwierigkeiten geraten. Hier ist eine Abstandsfunktion die ich verwendet habe. 

double Distance(double x0, double y0, double x1, double y1)
{
  double a, b, dx, dy;

  dx = abs(x1 - x0);
  dy = abs(y1 - y0);

  a = max(dx, dy));
  if (a == 0)
    return 0;
  b = min(dx, dy);

  return a * sqrt( 1 + (b*b) / (a*a) );
}

Da die letzte Operation keine Quadratwurzel ist, verlieren Sie nicht die Präzision nicht mehr.

Ich entdeckte dies in einem Projekt, das ich gerade arbeitete. Nachdem es zu studieren und herauszufinden, was es tat ich den Programmierer aufgespürt, die ich dachte, war verantwortlich ihm zu gratulieren, aber er hatte keine Ahnung, was ich rede.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top