kollidiert mit einem Loci Mesh

Question

Ich möchte vermeiden, dass mein Spieler in Wänden stehen kann. Jedes Spiel Tick mein Spieler bewegt sich eine kleine Entfernung und/oder dreht sich.

TL; DR Bitte eine Variante des klassischen Liniensegment liefern -> - Triangulationsverfahrens Algorithmus, der zu Beinaheunfälle zurückkehrt, oder lösen das Problem auf andere Weise Das Liniensegment schneidet, wenn sie innerhalb eines gibt gegebene Entfernung des Dreiecks. Das Problem ist sehr subtil, beispielsweise wenn die Ecken des Dreiecks gerundet sind und das Liniensegment tangential zum Dreieck verläuft.

Ich habe den üblichen Strahl/Dreieck-Schnittpunktcode.

Ein Strahl ist jedoch eine sehr schlechte Annäherung an einen sich bewegenden Spieler! Ich habe Probleme mit den fehlenden Kanten des Spielers, aber das Spieler-Mesh passiert sie.

Wie bestimmen Sie effizient, wann und wo ein Spieler in einer 3D-Umgebung mit Wänden und Hindernissen kollidiert?

Ein allgemeiner Ansatz wäre es, einen Beinahe-Dreieck-Code zu haben, bei dem der Strahl ein kugelgefüllter Zylinder ist.

Die allgemeine Lösung, die ich versucht habe, ist, sich vorzustellen, der Spieler sei eine Kugel; Ich habe versucht, ein Gitter zu erzeugen, dessen Radius größer als die tatsächlichen Wände ist, und Kollisionsstrahlen zu erzeugen. Ich möchte ein Netz berechnen, das eine bestimmte Entfernung vor diesem Netz hat, d. H. Ein Würfel würde sich zu einem etwas größeren Würfel mit abgerundeten Kanten und Ecken ausdehnen. (Meine Netze sind weniger regelmäßig als ein Würfel. Stellen Sie sich eine Netzdarstellung des Inneren eines Heizraumes vor, und stellen Sie sich vor, ein Netz zu berechnen, das 20 cm von allen Wänden und Kesseln und Türrahmen und so in diesem Raum entfernt ist.) hier ist ein einfaches Netz um ein Fass:

für jede Fläche I die Oberflächennormale berechnen kann; So weiß ich, welcher Weg "out" ist.

Mein Brainstorming lässt mich vorstellen, die Normale jeder Seite um die feste Distanz zu multiplizieren und dann ein Dreieck mit dem entsprechenden Offset auszusenden.

Dies würde jedoch Löcher an den Kanten hinterlassen und würde vielleicht (?) Dazu führen, dass einige Kanten sehr enge spitze Ecken passieren?

Ich kann mir auch vorstellen, jede Kante als ball-ended Zylinder zu verbinden und so weiter.

Der Ansatz, den ich für den obigen Lauf verwendet habe, besteht darin, die Durchschnittsnormale aller Flächen zu berechnen, die sich eine Ecke teilen, und diese dann mit dem Kollisionsradius zu multiplizieren. Es kommt nicht gut mit spitzen Winkeln zurecht, und was ist zu tun, wenn ein Scheitel zwischen Flächen, die sich auf gegenüberliegenden Seiten befinden, falsch geteilt wird?

Ich werde dieses Mesh berechnen und Ray-Schnittpunkte in Javacsript durchführen. Leistung ist also auch eine Überlegung. Ein zu feines detailliertes Netz wird teuer sein, um eine Kollisionserkennung durchzuführen.

Wie können Sie ein gutes Loci-Mesh effektiv berechnen? Oder machen Loci-bewusste Fuzzy-Dreieck-Kreuzung? Oder gibt es einen besseren Weg, Kollisionen zu machen, und kann es irgendwie modellieren, dass sich Dinge in Bögen bewegen statt in geraden Linien?

Answer 1

(niemand nahm die Prämie :(Nathan Reed on gamedev.stackexchange half mit der Terminologie. Es heißt Kapseldreieck Kreuzung.)

Seine überraschend knifflige Mathematik und Googeln findet nicht viel vorgefertigten Code zu kopieren.

Eine standard way ist zu extrudieren das Dreieck durch den Radius, fügen Sie auch Test jeder der drei dreieckigen Kanten als Kapseln.

Um das Dreieck zu extrudieren, multiplizieren Sie einfach die Normale des Dreiecks mit dem Kapselradius, versetzten jede Dreieckecke um diesen Betrag und führen dann den normalen Liniensegmentdreiecktest dagegen durch.

Der Kapsel-Test für jede Dreieckskante ist ziemlich teuer, da Sie es dreimal machen müssen. Es ist möglich, dass die Verwendung der baryzentrischen Koordinaten aus dem Dreieckstest dazu beiträgt, einige der Kapselrandtests zu vermeiden, aber ich habe das nicht durchdacht. Sie können auch den Kapsel-Test an Kanten vermeiden, die mit anderen Dreiecken geteilt werden, die stumpf genug sind; Sie könnten dies berechnen und diese Kanten markieren. Ich habe mich (noch) nicht geärgert.

Ich fand, dass die Vorberechnung der Begrenzungssphäre jedes Gesichts und das Durchführen eines Schnitttests mit der Begrenzungskugel der Kapsel eine super billige Möglichkeit war, diesen teuren Test die meiste Zeit zu vermeiden. Ich berechne auch die Normalen für jedes Gesicht vor, obwohl das ein kleinerer Gewinn ist.

Da der Test so teuer ist, ist es am besten, den Player als eine einzige Kugel zu behandeln und den Schnittpunktcode mit einer Liste von Gesichtskreuzungen zu versehen. Sie können dann den Spieler als eine Reihe von kleineren Sphären, die in Formation fliegen, modellieren, und Sie müssen nur für die Gesichter, die der erste Durchgang mit der größeren Kugel gefunden hat, einen Kreuzschnitt für die Kapselfläche machen.