Ist die Kollisionserkennung immer O (n ^ 2)?

14

Ist die Physik-Engine in der Lage, diese Komplexität zu verringern, indem beispielsweise nahe beieinander liegende Objekte gruppiert und innerhalb dieser Gruppe auf Kollisionen geprüft werden, anstatt gegen alle Objekte zu vergleichen? (Beispielsweise können ferne Objekte aus einer Gruppe entfernt werden, indem die Geschwindigkeit und der Abstand zu anderen Objekten betrachtet werden.)

Wenn nicht, ist die Kollision dann für Kugeln (in 3d) oder Scheiben (in 2d) trivial? Soll ich eine Doppelschleife erstellen oder stattdessen ein Array von Paaren erstellen?

EDIT: Ist die Kollisionserkennung für Physik-Engines wie bullet und box2d immer noch O (N ^ 2)?

jokoon
quelle
12
Zwei Wörter: Raumaufteilung
MichaelHouse
1
Wetten Sie? Ich glaube, beide haben Implementierungen von SAP ( Sweep and Prune ) (unter anderem), einem O (n log (n)) - Algorithmus. Suchen Sie nach "Broad Phase Collision Detection", um mehr zu erfahren.
MichaelHouse
2
@ Byte56 Sweep and Prune hat die Komplexität O (n log (n)) nur, wenn Sie bei jedem Test sortieren müssen. Sie möchten eine sortierte Liste von Objekten führen und jedes Mal, wenn Sie eines hinzufügen, sortieren Sie es einfach an der richtigen Stelle. O (log (n)), daher erhalten Sie O (log (n) + n) = O (n). Es wird jedoch sehr kompliziert, wenn sich Objekte bewegen!
MartinTeeVarga
1
@ sm4, wenn die Bewegungen begrenzt sind, können ein paar Durchgänge der Blasensortierung dafür sorgen (markieren Sie einfach die bewegten Objekte und bewegen Sie sie im Array vorwärts oder rückwärts, bis sie sortiert sind. Achten Sie auf andere bewegte Objekte
Ratschenfreak

Antworten:

14

Die räumliche Teilung ist im schlimmsten Fall immer O (N ^ 2), und darum geht es in der Informatik bei der Komplexität.

Es gibt jedoch Algorithmen, die in der linearen Zeit O (N) arbeiten . Alle basieren auf einer Art Sweep-Linie.

Grundsätzlich müssen Sie Ihre Objekte nach einer Koordinate sortieren. Angenommen, X. Wenn Sie die Sortierung jedes Mal vor der Kollisionserkennung durchführen, ist die Komplexität O (N * logN). Der Trick besteht darin, nur zu sortieren, wenn Sie der Szene Objekte hinzufügen, und später, wenn sich etwas in der Szene ändert. Das Sortieren nach Bewegung ist nicht trivial. In der unten verlinkten Veröffentlichung finden Sie einen Algorithmus, der Bewegungen berücksichtigt und dennoch in linearer Zeit arbeitet.

Dann fegen Sie von links nach rechts. Jedes Mal, wenn Ihre Sweep-Linie den Anfang eines Objekts kreuzt, wird es in eine temporäre Liste eingefügt. Jedes Mal, wenn Ihre Sweep-Linie das Objekt verlässt, nehmen Sie es aus der Liste heraus. Sie berücksichtigen Kollisionen nur innerhalb dieser temporären Liste.

Die naive Sweep-Linie ist im schlimmsten Fall auch O (N ^ 2) (Sie lassen alle Objekte die gesamte Karte von links nach rechts überspannen), aber Sie können sie O (N) machen, indem Sie sie schlauer machen (siehe Link unten). Ein wirklich guter Algorithmus wird ziemlich komplex sein.

Dies ist ein einfaches Diagramm, wie die Sweep-Linie funktioniert:

Sweep-Line-Algorithmus

Die Linie läuft von links nach rechts. Objekte werden nach X-Koordinaten sortiert.

  • Fall eins: Die ersten beiden Objekte werden geprüft. Das ist alles, was zählt.
  • Fall 2: Das erste Objekt wurde geprüft und ist aus der Liste verschwunden. Zwei und drei werden geprüft.
  • Fall drei: Selbst wenn dieses Objekt kollidiert, prüfen wir es nicht.
  • Fall 4: Weil wir in diesem Fall nachsehen!

Algorithmen wie diese haben die Komplexität O (C * N) = O (N).

Quelle: Zwei Jahre Kurse in Computergeometrie.

Bei der Kollisionserkennung wird dies normalerweise als Sweep and Prune bezeichnet , aber die Sweep-Linienfamilie von Algortithmen ist in vielen anderen Bereichen nützlich.

Weitere empfohlene Lektüre, die meines Erachtens außerhalb des Rahmens dieser Frage liegt, aber dennoch interessant ist: Effiziente Methoden für großflächiges Sweepen und Bereinigen mit AABB-Einfügung und -Entfernung - In diesem Artikel wird ein erweiterter Algorithmus für das Sweepen und Bereinigen vorgestellt, bei dem achsenausgerichtete Begrenzungsrahmen (AABB) verwendet werden ) mit einer Sortierung, die die Bewegung berücksichtigt. Algorigthm präsentiert in den Papierarbeiten in linearer Zeit.


Beachten Sie nun, dass dies der theoretisch beste Algorithmus ist . Es bedeutet nicht, dass es verwendet wird. In der Praxis hat der O (N ^ 2) -Algorithmus mit räumlicher Aufteilung im typischen Fall eine bessere Geschwindigkeit (nahe O (N)) und eine gewisse zusätzliche Speicheranforderung. Dies liegt daran, dass die Konstante C in O (C * N) sehr hoch sein kann! Da wir normalerweise über genügend Speicher verfügen und die Objekte in typischen Fällen gleichmäßig im Raum verteilt sind, funktioniert ein solcher Algorithmus BESSER. Aber O (N) ist die Antwort auf die ursprüngliche Frage.

MartinTeeVarga
quelle
verwendet box2d / bullet das?
jokoon
3
"Sweep and Prune" nennt man das normalerweise für die Physik. Das Schöne ist, dass Sie die Sortierung aktualisieren können, wenn die Simulation fortgeschritten ist. Außerdem ist die Sweep-Linie in Ihrer Grafik in Bezug auf die Implementierung ein wenig abweichend (allerdings gut für die Theorie) - Sie würden nur die Box-Starts / -Ende durchlaufen, sodass Sie nur die tatsächlichen potenziellen Kollisionen überprüfen würden. Diese Methode wurde verwendet, um leistungsfähigere räumliche Aufteilungsbäume zu generieren, anstatt sie auch direkt zu verwenden.
Sean Middleditch
3
Da es technisch gesehen tatsächlich zu O (N ^ 2) paarweisen Kollisionen kommen kann, ist es nicht ganz richtig zu sagen, dass Sweep-and-Prune immer O (N) ist. Die Kernkomplexität des Algorithmus ist vielmehr O (N + c), wobei c die Anzahl der vom Algorithmus gefundenen Kollisionen ist - es ist ausgangssensitiv , genauso wie viele konvexe Rumpfalgorithmen. (Referenz: en.wikipedia.org/wiki/Output-sensitive_algorithm )
Steven Stadnicki
1
Sie sollten Ihre Behauptungen mit einigen Veröffentlichungen oder zumindest Algorithmusnamen untermauern.
Sam Hocevar
1
@SamHocevar Ich habe einen Link zu einem wirklich fortgeschrittenen Sweep and Prune-Algorithmus hinzugefügt, der in linearer Zeit mit detaillierter Aufschlüsselung der Konstanten arbeitet. Die Tatsache, dass die Algorithmen "Sweep and Prune" heißen, war für mich neu, da ich nie damit gearbeitet habe. Ich habe diese Algorithmen bei der Kartenauswahl verwendet (das ist eine Art Kollision von 1 Punkt mit anderen Objekten), also habe ich nur das Wissen angewendet.
MartinTeeVarga
8

Nein. Die Kollisionserkennung ist nicht immer O (N ^ 2).

Nehmen wir zum Beispiel an, wir haben einen Raum von 100x100 mit Objekten der Größe 10x10. Wir könnten diesen Raum in Zellen von 10x10 mit einem Gitter teilen.

Jedes Objekt kann sich in bis zu 4 Rasterzellen befinden (es könnte direkt in einen Block passen oder sich "zwischen" Zellen befinden). Wir könnten eine Liste von Objekten in jeder Zelle führen.

Wir müssen nur in diesen Zellen nach Kollisionen suchen. Wenn es eine maximale Anzahl von Objekten pro Gitterzelle gibt (dh es befinden sich nie mehr als 4 Objekte im selben Block), ist die Kollisionserkennung für jedes Objekt O (1) und die Kollisionserkennung für alle Objekte ist O (N).

Dies ist nicht der einzige Weg, um die Komplexität von O (N ^ 2) zu vermeiden. Es gibt andere Methoden, die für andere Anwendungsfälle besser geeignet sind - häufig unter Verwendung von baumbasierten Datenstrukturen.

Der von mir beschriebene Algorithmus ist eine Art der Raumpartitionierung , es gibt jedoch auch andere Algorithmen für die Raumpartitionierung. Weitere Algorithmen, die die zeitliche Komplexität von O (N ^ 2) vermeiden, finden Sie unter Typen von Datenstrukturen für die Raumpartitionierung.

Sowohl Box2D als auch Bullet unterstützen Mechanismen, um die Anzahl der überprüften Paare zu reduzieren.

Aus dem Handbuch , Abschnitt 4.15:

Die Kollisionsverarbeitung in einem physikalischen Schritt kann in eine schmale Phase und eine breite Phase unterteilt werden. In der schmalen Phase berechnen wir Kontaktpunkte zwischen Formpaaren. Stellen Sie sich vor, wir haben N Formen. Mit Brute Force müssten wir die Narrow-Phase für N * N / 2-Paare durchführen.

Die b2BroadPhase-Klasse reduziert diese Last, indem ein dynamischer Baum für die Paarverwaltung verwendet wird. Dies reduziert die Anzahl der Narrow-Phase-Anrufe erheblich.

Normalerweise interagiert man nicht direkt mit der breiten Phase. Stattdessen erstellt und verwaltet Box2D intern eine breite Phase. Außerdem wurde b2BroadPhase unter Berücksichtigung der Box2D-Simulationsschleife entwickelt, sodass es wahrscheinlich nicht für andere Anwendungsfälle geeignet ist.

Aus dem Bullet Wiki :

Es gibt verschiedene Arten von Breitbandalgorithmen, die den naiven O (n ^ 2) -Algorithmus verbessern und nur die vollständige Liste der Paare zurückgeben. Diese optimierten Broadphasen führen manchmal noch mehr nicht kollidierende Paare ein, was jedoch durch ihre allgemein verbesserte Ausführungszeit ausgeglichen wird. Sie haben unterschiedliche Leistungsmerkmale und keine übertrifft die anderen in allen Situationen.

Dynamischer AABB-Baum

Dies wird durch die btDbvtBroadphase in Bullet implementiert.

Wie der Name schon sagt, handelt es sich um einen dynamischen AABB-Baum . Ein nützliches Merkmal dieser breiten Phase ist, dass sich die Struktur dynamisch an die Dimensionen der Welt und ihrer Inhalte anpasst. Es ist sehr gut optimiert und eine sehr gute allgemeine Breitbandphase. Es verarbeitet dynamische Welten, in denen sich viele Objekte in Bewegung befinden, und das Hinzufügen und Entfernen von Objekten ist schneller als SAP.

Sweep and Prune (SAP)

In Bullet ist dies der AxisSweep-Klassenbereich. Dies ist auch eine gute allgemeine Breitbandphase, mit der Einschränkung, dass eine festgelegte Weltgröße erforderlich ist, die im Voraus bekannt ist. Diese breite Phase bietet die beste Leistung für typische Dynamikwelten, in denen sich die meisten Objekte kaum oder gar nicht bewegen. Sowohl btAxisSweep3 als auch bt32AxisSweep3 quantisieren den Anfangs- und Endpunkt für jede Achse als Ganzzahlen anstelle von Gleitkommazahlen, um die Leistung zu verbessern.

Der folgende Link ist eine allgemeine Einführung in die Broadphase und eine Beschreibung des Sweep- und Prune-Algorithmus (obwohl er "Sort and Sweep" heißt):

http://www.ziggyware.com/readarticle.php?article_id=128

Schauen Sie sich auch die Wikipedia-Seite an:

http://en.wikipedia.org/wiki/Sweep_and_prune

Luiscubal
quelle
Einige Links zu ähnlichen Fragen und externen Ressourcen machen dies zu einer großartigen Antwort.
MichaelHouse
3
Das ist falsch. Du bekommst immer noch O (N ^ 2). Es wird viel schneller sein, so etwas wie N ^ 2/100, aber immer noch N ^ 2. Als Beweis sei nur angenommen, dass sich alle Objekte in einer Zelle befinden.
MartinTeeVarga
4
@ sm4 Dies ist der ungünstigste Fall O (N ^ 2). Dies ist in der Tat der Fall, wenn sich alle Objekte in einer Zelle befinden. In einer Physik-Engine befinden sich Objekte jedoch normalerweise nicht in einer Zelle. In meinem Beispiel kann kein Objekt jemals dieselbe Zelle mit mehr als 3 anderen Objekten teilen. Dies würde in einer Physik-Engine für "normale" Objekte passieren (und mit "normal" meine ich "nicht nur einen Sensor").
Luiscubal
Ich denke, Ihr Algorithmus würde das Einchecken der 8 Zellen erfordern, nicht nur der 4 Zellen.
jokoon
6
@ Luiscubal Komplexität ist immer "worst case". Theoretisch suchen Sie nach "garantierter" Komplexität. Ähnlich verhält es sich mit Quicksort (O (N ^ 2)) und Mergesort (O (N * logN)). Quicksort ist bei realen Daten leistungsfähiger und benötigt weniger Platz. Mergesort hat jedoch eine bessere Komplexität garantiert. Wenn Sie etwas prüfen müssen, verwenden Sie mergesort. Wenn Sie etwas sortieren müssen, verwenden Sie Quicksort.
MartinTeeVarga
2

O (N ^ 2) bezieht sich auf die Tatsache, dass Sie, wenn Sie N Objekte haben, herausfinden, was mit den im schlimmsten Fall N ^ 2 Kollisionsberechnungen kollidiert . Angenommen, Sie haben 3 Objekte. Um "wer trifft wen" zu finden, müssen Sie Folgendes finden:

o1 hitting o2?  o1 hitting o3?
o2 hitting o1?  o2 hitting o3?
o3 hitting o1?  o3 hitting o2?

Das sind 6 Prüfungen auf Kollisionen oder N * (N-1) Prüfungen. In der asymptotischen Analyse würden wir das Polynom erweitern und als O (N ^ 2) approximieren. Wenn Sie 100 Objekte hätten, wäre das 100 * 99, was nahe genug bei 100 * 100 liegt.

Wenn Sie also beispielsweise den Raum mit einem Octree partitionieren, wird die durchschnittliche Anzahl der Vergleiche zwischen Körpern reduziert. Wenn es möglich ist, dass sich alle Objekte in einem sehr kleinen Bereich ansammeln (z. B. wenn Sie eine Art Partikelflusssimulation durchführen, bei der sich Partikel im selben Bereich ansammeln können), kann das O (N ^ 2) immer noch bei auftreten Punkte in der Simulation (an welchen Punkten sehen Sie eine Verlangsamung).

Der ganze Punkt von O (N ^ 2) liegt also in der Natur jedes Körpers, der jeden anderen Körper in der Szene überprüft. Das ist nur die Art der Berechnung. Viele Dinge können jedoch dazu beitragen, dies billiger zu machen. Sogar ein Szenendiagramm (z. B. das Erkennen zwischen Objekten nur im selben Raum ) reduziert die Anzahl der durchzuführenden Kollisionsberechnungen erheblich, aber es ist immer noch O (M ^ 2) (wobei M die Anzahl der Objekte im Raum ist) Kollision erkannt werden gegen). Sphärische Begrenzungsvolumina führen die anfängliche Überprüfung sehr schnell durch ( if( distance( myCenter, hisCenter ) > (myRadius+hisRadius) ) then MISS). Selbst wenn die Kollisionserkennung 0 (N ^ 2) ist, werden die Berechnungen der Begrenzungskugeln wahrscheinlich sehr schnell durchgeführt.

Bobobobo
quelle
Es ist nicht erforderlich, die Brute-Force-Prüfung als Referenz heranzuziehen: Unabhängig von cleveren Algorithmen können N Objekte mit allen anderen Objekten kollidieren, sodass O (N ^ 2) Kollisionen entstehen, für deren Verarbeitung O (N ^ 2) Arbeit erforderlich ist. Gute Algorithmen können nur dann bessere Ergebnisse erzielen, wenn weniger Kollisionen vorliegen.
Lorenzo Gatti