3D-Kollisionsdetektion

Dieser Artikel bietet eine Einführung in die verschiedenen Begrenzungsvolumen-Techniken, die zur Implementierung der Kollisionsdetektion in 3D-Umgebungen verwendet werden. Nachfolgende Artikel werden Implementierungen in spezifischen 3D-Bibliotheken behandeln.

Achsen-ausgerichtete Begrenzungsboxen

Wie bei der 2D-Kollisionsdetektion sind achsen-ausgerichtete Begrenzungsboxen (AABB) der schnellste Algorithmus, um zu bestimmen, ob sich zwei Spielelemente überschneiden oder nicht. Dies besteht darin, Spielelemente in einer nicht-gedrehten (also achsen-ausgerichteten) Box zu verpacken und die Positionen dieser Boxen im 3D-Koordinatenraum zu überprüfen, um festzustellen, ob sie sich überschneiden.

Zwei dreidimensionale, nicht-quadratische Objekte, die im Raum schweben und von virtuellen rechteckigen Boxen umgeben sind.

Die achsen-ausgerichtete Einschränkung besteht aus Leistungsgründen. Der Überlappungsbereich zwischen zwei nicht-gedrehten Boxen kann allein durch logische Vergleiche überprüft werden, während gedrehte Boxen zusätzliche trigonometrische Operationen erfordern, die langsamer zu berechnen sind. Wenn Sie Entitäten haben, die sich drehen, können Sie entweder die Abmessungen der Begrenzungsbox anpassen, damit sie das Objekt immer noch umschließt, oder Sie entscheiden sich für einen anderen Begrenzungsgeometrietyp, wie zum Beispiel Kugeln (die gegenüber Drehungen unveränderlich sind). Das animierte GIF unten zeigt ein grafisches Beispiel einer AABB, die ihre Größe anpasst, um die drehende Entität zu umschließen. Die Box ändert ständig ihre Dimensionen, um die in ihr enthaltene Entität passgenau zu umschließen.

Animierter drehender Knoten, der zeigt, wie sich die virtuelle rechteckige Box verkleinert und vergrößert, während der Knoten sich innerhalb dreht. Die Box dreht sich nicht.

Hinweis: Sehen Sie sich den Artikel Bounding Volumes with Three.js an, um eine praktische Implementierung dieser Technik zu sehen.

Punkt vs. AABB

Zu überprüfen, ob ein Punkt in einer AABB ist, ist ziemlich einfach — wir müssen nur überprüfen, ob die Koordinaten des Punktes innerhalb der AABB liegen, indem wir jede Achse separat betrachten. Wenn wir annehmen, dass P_x, P_y und P_z die Koordinaten des Punktes sind und B_minX–B_maxX, B_minY–B_maxY und B_minZ–B_maxZ die Bereiche jeder Achse der AABB sind, können wir berechnen, ob eine Kollision zwischen den beiden aufgetreten ist, indem wir die folgende Formel verwenden:

f(P, B)= (P_x \ge B_{minX} \wedge P_x \le B_{maxX}) \wedge (P_y \ge B_{minY} \wedge P_y \le B_{maxY}) \wedge (P_z \ge B_{minZ} \wedge P_z \le B_{maxZ})

Oder in JavaScript:

function isPointInsideAABB(point, box) {
  return (
    point.x >= box.minX &&
    point.x <= box.maxX &&
    point.y >= box.minY &&
    point.y <= box.maxY &&
    point.z >= box.minZ &&
    point.z <= box.maxZ
  );
}

AABB vs. AABB

Zu überprüfen, ob eine AABB eine andere AABB schneidet, ist ähnlich wie der Punkt-Test. Wir müssen nur einen Test pro Achse durchführen, indem wir die Grenzen der Boxen verwenden. Das Diagramm unten zeigt den Test, den wir über die X-Achse durchführen würden — im Grunde, überlappen sich die Bereiche A_minX–A_maxX und B_minX–B_maxX?

Handzeichnung von zwei Rechtecken, die die obere rechte Ecke von A zeigen, die sich über die untere linke Ecke von B überlappt, da die größte x-Koordinate von A größer ist als die kleinste x-Koordinate von B.

Mathematisch würde das so aussehen:

f(A, B) = (A_{minX} \le B_{maxX} \wedge A_{maxX} \ge B_{minX}) \wedge ( A_{minY} \le B_{maxY} \wedge A_{maxY} \ge B_{minY}) \wedge (A_{minZ} \le B_{maxZ} \wedge A_{maxZ} \ge B_{minZ})

Und in JavaScript würden wir dies verwenden:

function intersect(a, b) {
  return (
    a.minX <= b.maxX &&
    a.maxX >= b.minX &&
    a.minY <= b.maxY &&
    a.maxY >= b.minY &&
    a.minZ <= b.maxZ &&
    a.maxZ >= b.minZ
  );
}

Begrenzungssphären

Kollisionsdetektion mit Begrenzungssphären zu verwenden ist etwas komplexer als AABB, liefert jedoch immer noch schnelle Ergebnisse. Der Hauptvorteil von Sphären ist, dass sie invariant gegenüber Drehungen sind. Wenn die umfasste Entität rotiert, bleibt die Begrenzungssphäre gleich. Ihr Hauptnachteil ist, dass sie, sofern die umfasste Entität nicht tatsächlich kugelförmig ist, in der Regel schlecht passt (d.h. eine Person mit einer Begrenzungssphäre zu umschließen, wird viele Fehlalarme auslösen, während eine AABB eine bessere Übereinstimmung wäre).

Punkt vs. Sphäre

Um zu überprüfen, ob eine Sphäre einen Punkt enthält, müssen wir den Abstand zwischen dem Punkt und dem Zentrum der Sphäre berechnen. Wenn dieser Abstand kleiner oder gleich dem Radius der Sphäre ist, liegt der Punkt innerhalb der Sphäre.

Handzeichnung einer 2D-Projektion einer Sphäre und eines Punktes in einem kartesischen Koordinatensystem. Der Punkt befindet sich außerhalb des Kreises unten rechts. Der Abstand ist durch eine gestrichelte Linie, die mit D beschriftet ist, vom Mittelpunkt des Kreises zum Punkt gekennzeichnet. Eine hellere Linie zeigt den Radius, bezeichnet mit R, vom Mittelpunkt des Kreises zur Grenze des Kreises.

Unter Berücksichtigung, dass der euklidische Abstand zwischen zwei Punkten A und B $\sqrt{(A_x - B_x)^2 + (A_y - B_y)^2 + (A_z - B_z)^2}$ ist, würde unsere Formel für die Kollisionsdetektion von Punkt vs. Sphäre wie folgt aussehen:

f(P,S) = S_{radius} \ge \sqrt{(P_x - S_x)^2 + (P_y - S_y)^2 + (P_z - S_z)^2}

Oder in JavaScript:

function isPointInsideSphere(point, sphere) {
  // we are using multiplications because is faster than calling Math.pow
  const distance = Math.sqrt(
    (point.x - sphere.x) * (point.x - sphere.x) +
      (point.y - sphere.y) * (point.y - sphere.y) +
      (point.z - sphere.z) * (point.z - sphere.z),
  );
  return distance < sphere.radius;
}

Hinweis: Der obige Code enthält eine Quadratwurzel, die kostspielig zu berechnen sein kann. Eine effektive Optimierung, um sie zu vermeiden, besteht darin, den quadrierten Abstand mit dem quadrierten Radius zu vergleichen, sodass die optimierte Gleichung stattdessen distanceSqr < sphere.radius * sphere.radius beinhalten würde.

Sphäre vs. Sphäre

Der Test Sphäre vs. Sphäre ähnelt dem Punkt vs. Sphäre-Test. Hier müssen wir überprüfen, ob der Abstand zwischen den Zentren der Sphären kleiner oder gleich der Summe ihrer Radien ist.

Handzeichnung von zwei sich teilweise überlappenden Kreisen. Jeder Kreis (in unterschiedlicher Größe) hat eine helle Radiuslinie, die von seinem Mittelpunkt bis zu seinem Rand verläuft, mit R gekennzeichnet. Der Abstand wird durch eine gepunktete Linie, mit D beschriftet, verbunden zwischen den Mittelpunkten beider Kreise dargestellt.

Mathematisch sieht das so aus:

f(A,B) = \sqrt{(A_x - B_x)^2 + (A_y - B_y)^2 + (A_z - B_z)^2} \le A_{radius} + B_{radius}

Oder in JavaScript:

function intersect(sphere, other) {
  // we are using multiplications because it's faster than calling Math.pow
  const distance = Math.sqrt(
    (sphere.x - other.x) * (sphere.x - other.x) +
      (sphere.y - other.y) * (sphere.y - other.y) +
      (sphere.z - other.z) * (sphere.z - other.z),
  );
  return distance < sphere.radius + other.radius;
}

Sphäre vs. AABB

Zu testen, ob eine Sphäre und eine AABB kollidieren, ist etwas komplizierter, aber immer noch einfach und schnell. Ein logischer Ansatz wäre, jeden Scheitelpunkt der AABB zu überprüfen, indem für jeden ein Punkt-gegen-Sphäre-Test durchgeführt wird. Dies ist jedoch überflüssig — das Testen aller Scheitelpunkte ist unnötig, da wir lediglich den Abstand zwischen dem nächsten Punkt der AABB (nicht unbedingt ein Scheitelpunkt) und dem Zentrum der Sphäre berechnen müssen, um festzustellen, ob er kleiner oder gleich dem Radius der Sphäre ist. Diesen Wert können wir erhalten, indem wir das Zentrum der Sphäre auf die Grenzen der AABB beschränken.

Handzeichnung eines Quadrats, das teilweise den oberen Teil eines Kreises überlappt. Der Radius wird durch eine helle Linie bezeichnet, die mit R beschriftet ist. Die Distanzlinie verläuft vom Zentrum des Kreises zum nächsten Punkt des Quadrats.

In JavaScript würden wir diesen Test wie folgt durchführen:

function intersect(sphere, box) {
  // get box closest point to sphere center by clamping
  const x = Math.max(box.minX, Math.min(sphere.x, box.maxX));
  const y = Math.max(box.minY, Math.min(sphere.y, box.maxY));
  const z = Math.max(box.minZ, Math.min(sphere.z, box.maxZ));

  // this is the same as isPointInsideSphere
  const distance = Math.sqrt(
    (x - sphere.x) * (x - sphere.x) +
      (y - sphere.y) * (y - sphere.y) +
      (z - sphere.z) * (z - sphere.z),
  );

  return distance < sphere.radius;
}

Verwendung einer Physik-Engine

3D-Physik-Engines bieten Algorithmen zur Kollisionsdetektion, die meist ebenfalls auf Begrenzungsvolumen basieren. Eine Physik-Engine funktioniert, indem sie einen physischen Körper erstellt, der normalerweise an eine visuelle Darstellung gebunden ist. Dieser Körper besitzt Eigenschaften wie Geschwindigkeit, Position, Rotation, Drehmoment usw., und auch eine physische Form. Diese Form wird in den Berechnungen zur Kollisionsdetektion berücksichtigt.

Wir haben eine Live-Demonstration zur Kollisionsdetektion (mit Quellcode) vorbereitet, die Sie sich ansehen können, um solche Techniken in Aktion zu sehen — diese verwendet die Open-Source-3D-Physik-Engine cannon.js.

Siehe auch

Verwandte Artikel auf MDN:

Externe Ressourcen:

Simple intersection tests for games auf Game Developer
Bounding volume auf Wikipedia

Help improve MDN

Learn how to contribute Diese Seite wurde automatisch aus dem Englischen übersetzt.

Übersetzung auf GitHub anzeigen • Fehler mit dieser Übersetzung melden