Kollisionserkennung: Visuelle Schnittpunkte in der Bildverarbeitung verstehen

Von Fouad Sabry

Was ist Kollisionserkennung?

Kollisionserkennung ist das Rechenproblem der Erkennung eines Schnittpunkts von zwei oder mehr räumlichen Objekten, üblicherweise Computergrafikobjekten. Es findet Anwendung in verschiedenen Computerbereichen, vor allem in der Computergrafik, in Computerspielen, in Computersimulationen, in der Robotik und in der Computerphysik. Die Kollisionserkennung ist ein klassisches Problem der Computergeometrie. Kollisionserkennungsalgorithmen können in die Arbeit mit 2D- oder 3D-Raumobjekten unterteilt werden.

Wie Sie davon profitieren

(I) Einblicke und Validierungen zu Folgendem Themen:

Kapitel 1: Kollisionserkennung

Kapitel 2: Raytracing (Grafik)

Kapitel 3: Binärraumpartitionierung

Kapitel 4: Schwerpunkt

Kapitel 5: Verzweigung und Grenze

Kapitel 6: Fluchtpunkt

Kapitel 7: Quadtree

Kapitel 8: Begrenzung Band

Kapitel 9: Zykluserkennung

Kapitel 10: Anordnung von Linien

(II) Beantwortung der häufigsten öffentlichen Fragen zur Kollisionserkennung.

(III) Beispiele aus der Praxis für den Einsatz der Kollisionserkennung in vielen Bereichen.

An wen sich dieses Buch richtet

Profis, Studenten und Doktoranden , Enthusiasten, Hobbyisten und diejenigen, die über grundlegende Kenntnisse oder Informationen für jede Art von Kollisionserkennung hinausgehen möchten.

 

 

• Sprache: Deutsch
• Herausgeber: Eine Milliarde Sachkundig [German]
• Erscheinungsdatum: 4. Mai 2024

Buchvorschau

Kapitel 1: Kollisionserkennung

Die Computeraufgabe, die Überschneidung von zwei oder mehr Objekten zu erkennen, wird als Kollisionserkennung bezeichnet. Die Kollisionserkennung ist ein klassisches Problem in der Computergeometrie und findet Anwendung in einer Vielzahl von Computerbereichen, vor allem in der Computergrafik, in Computerspielen, Computersimulationen, in der Robotik und in der Computerphysik. 2D- und 3D-Kollisionserkennungstechniken lassen sich durch ihre jeweiligen Objektdimensionen unterscheiden.

Bei der physikalischen Simulation werden Tests wie Billardspielen durchgeführt. Unter dem Schirm der starren Körperbewegung und der elastischen Kollisionen ist die Mechanik des Hüpfens von Billardbällen gut verstanden. Eine erste Beschreibung des Umstandes würde eine detaillierte physische Beschreibung des Billardtisches und der Bälle sowie die Startpositionen jeder Kugel beinhalten. Ausgehend von einer Kraft, die auf den Spielball ausgeübt wird (oft die Folge davon, dass ein Spieler den Ball mit seinem Spielstock schlägt), möchten wir ein Computerprogramm verwenden, um die Flugbahnen, die genaue Bewegung und die endgültigen Ruhepositionen aller Kugeln zu bestimmen. Eine Simulation dieses Spiels würde mehrere Module erfordern, von denen eines für die Berechnung der exakten Kollisionen zwischen den Billardkugeln verantwortlich wäre. Eine winzige Ungenauigkeit in jeder Berechnung führt zu dramatischen Änderungen der endgültigen Position der Billardkugeln, wie dieses Beispiel zeigt.

Die Kriterien für Videospiele sind vergleichbar, mit deutlichen Änderungen. Computersimulationen müssen die reale Physik so genau wie möglich imitieren, während Computerspiele die reale Physik auf akzeptable Weise, in Echtzeit und mit ausreichender Belastbarkeit simulieren müssen. Solange die resultierende Simulation für die Spieler des Spiels zufriedenstellend ist, sind Kompromisse erlaubt.

Unterschiedliche physikalische Simulatoren reagieren unterschiedlich auf Kollisionen. Einige nutzen die Weichheit des Materials, um eine Kraft zu berechnen, die die Kollision in nachfolgenden Zeitschritten auflöst, wie es in der Realität der Fall wäre. Aufgrund der Härte mancher Materialien erfordert dies eine hohe Rechenleistung. Einige Simulatoren schätzen die Kollisionszeit mithilfe linearer Interpolation, setzen die Simulation zurück und berechnen dann die Kollision mit abstrakteren Ansätzen, die auf Erhaltungsprinzipien basieren.

Einige iterieren die lineare Interpolation (Newtons Ansatz), um die Kollisionszeit mit deutlich größerer Genauigkeit zu berechnen als der Rest der Simulation. Durch die Nutzung der zeitlichen Kohärenz ermöglicht die Kollisionserkennung immer feinere Zeitschritte, ohne den CPU-Bedarf signifikant zu erhöhen, wie z. B. in der Flugsicherung.

Nach einer inelastischen Kollision können spezielle Gleit- und Ruhezustände auftreten, die von der Open Dynamics Engine mit Einschränkungen modelliert werden. Abhängigkeiten verhindern Trägheit und damit Instabilität. Das Implementieren von Ruhe über ein Szenendiagramm verhindert Drift.

Mit anderen Worten, physische Simulatoren erkennen Kollisionen in der Regel entweder a posteriori (nach der Kollision) oder a priori (vor der Kollision) (bevor die Kollision auftritt). Neben der Unterscheidung zwischen a posteriori und a priori sind praktisch alle neueren Kollisionserkennungsalgorithmen hierarchisch organisiert. In der Regel werden diskret und kontinuierlich anstelle von a posteriori und a priori verwendet.

In der a posteriori Instanz wird die physikalische Simulation um ein winziges Stück vorangetrieben, und dann wird bestimmt, ob sich Objekte überlappen oder ob sie sich sichtbar überschneiden. Bei jedem Simulationsschritt werden die Positionen und Trajektorien aller sich kreuzenden Körper fixiert, um die Kollision zu berücksichtigen. Diese Methode wird als a posteriori bezeichnet, da sie in der Regel den genauen Moment des Aufpralls verfehlt und erst im Nachhinein erkennt.

Bei A-priori-Ansätzen gibt es einen Kollisionserkennungsalgorithmus, der die Flugbahnen physischer Körper mit großer Genauigkeit vorhersagen kann. Die Augenblicke der Kollision sind genau berechnet, und die physischen Körper kollidieren nie wirklich. Dies wird als a priori bezeichnet, da die Kollisionserkennungsmethode die Kollisionszeitpunkte berechnet, bevor die Konfiguration der physischen Körper aktualisiert wird.

Die Hauptvorteile von A-posteriori-Ansätzen sind folgende. Dem Algorithmus wird eine einfache Liste von physischen Körpern zur Verfügung gestellt, und das Programm erzeugt eine Liste von Körpern, die sich überschneiden. Die Kollisionserkennungstechnik erfordert keine Kenntnisse über Reibung, elastische oder inelastische Kollisionen oder verformbare Körper. Darüber hinaus sind die a posteriori Algorithmen eine Dimension einfacher als ihre a priori Gegenstücke. Die Zeitvariable wird im A-posteriori-Problem weggelassen, was einen A-priori-Algorithmus erfordert.

Auf der anderen Seite weisen a posteriori Algorithmen Probleme während des Fixing-Schritts auf, bei dem physikalisch falsche Schnittpunkte repariert werden müssen. Wenn der diskrete Schritt zu groß ist, kann die Kollision nicht erkannt werden, was dazu führt, dass ein Objekt durch ein anderes hindurchgeht, wenn es ausreichend schnell oder klein ist.

Die Vorteile von A-priori-Algorithmen sind eine verbesserte Präzision und Konsistenz. Die Trennung der physikalischen Simulation von der Kollisionserkennungsmethode ist schwierig (wenn auch nicht unmöglich). Abgesehen von den einfachsten Umständen gibt es für die Frage der Vorhersage, wann zwei Körper kollidieren würden (bei gegebenen Anfangsdaten), jedoch keine Lösung in geschlossener Form – ein numerischer Wurzelfinder ist in der Regel erforderlich.

Ein Beispiel: Eine Vase, die auf einem Tisch steht, befindet sich in Ruhekontakt oder Kollision, springt aber weder ab noch durchdringt sie sich. Ruhekontakt erfordert immer eine spezifische Behandlung: Wenn zwei Objekte kollidieren (a posteriori) oder rutschen (a priori) und ihre relative Geschwindigkeit kleiner als ein Schwellenwert ist, wird die Reibung zur Haftreibung und beide Objekte befinden sich auf demselben Ast des Szenengraphen.

Die herkömmlichen Methoden zur Detektion von Kollisionen zwischen mehreren Objekten sind extrem träge. Natürlich funktioniert es, jedes Objekt mit jedem anderen Objekt zu vergleichen, aber es ist verschwenderisch, wenn die Anzahl der Objekte signifikant ist. Das Vergleichen von Objekten mit komplexer Geometrie auf herkömmliche Weise, indem jede Fläche mit jeder anderen Fläche verglichen wird, ist ein zeitaufwändiger Prozess. Daher wurden umfangreiche Studien durchgeführt, um die Lösung des Problems zu beschleunigen.

In vielen Anwendungen variiert die Konfiguration physischer Körper von einem Zeitschritt zum nächsten kaum. Viele der Objekte können unbeweglich sein. Es wurden Algorithmen erstellt, die es ermöglichen, dass Berechnungen, die in einem vorherigen Zeitschritt durchgeführt wurden, im aktuellen Zeitschritt verwendet werden können, was zu einer schnelleren Berechnung führt.

Auf der groben Ebene der Kollisionserkennung besteht das Ziel darin, Objektpaare zu identifizieren, die potenziell kollidieren könnten. Diese Paare benötigen zusätzliche Untersuchungen. Ming C. Lin von der University of California, Berkeley [1] hat für diesen Zweck eine frühe Methode mit hoher Leistungsfähigkeit entwickelt.

Jedes Kästchen wird durch das Produkt von drei Intervallen bezeichnet (d. h. 1, 2 und 3), ein Kästchen wäre

I_{1}\times I_{2}\times I_{3}=[a_{1},b_{1}]\times [a_{2},b_{2}]\times [a_{3},b_{3}]

).

Sweep and Prune ist ein typisches Verfahren zur Kollisionserkennung von Begrenzungsrahmen.

Beachten Sie, dass es zwei solcher Kästchen gibt, I_{1}\times I_{2}\times I_{3} J_{1}\times J_{2}\times J_{3} und schneiden sich wenn, sowie wenn, I_{1} schneidet J_{1} , I_{2} schneidet J_{2} sich und I_{3} schneidet J_3 .

Es wird erwartet, dass von einem Zeitschritt zum nächsten, wenn I_{k} und  sich J_{k} überschneiden, dann ist es sehr wahrscheinlich, dass sie sich im folgenden Zeitschritt weiterhin überlappen werden.

Wenn sie sich während des vorherigen Zeitschritts nicht überschnitten haben, werden sie dies auch jetzt nicht tun, dann werden sie dies wahrscheinlich auch weiterhin tun.

Damit vereinfachen wir das Thema zu einem Tracking, von Bild zu Bild, welche sich überschneidenden Intervalle existieren.

Wir haben drei Listen von Intervallen (eine für jede Achse) und alle Listen haben die gleiche Länge (da jede Liste die Länge hat n , die Anzahl der Begrenzungsboxen. In jeder Liste kann sich jedes Intervall mit jedem anderen Intervall in der Liste überschneiden.

Daher haben wir für jede Liste eine n\times n Matrix M=(m_{{ij}}) aus Nullen und Einsen: m_{ij} ist 1, wenn Intervalle i sind und  sich j schneiden, 0, wenn sich die beiden Linien nicht schneiden.

Nach unserer Schätzung wird die Matrix, die M einer Liste von Intervallen zugeordnet ist, von einem Zeitschritt zum nächsten im Wesentlichen unverändert bleiben.

Um dies zu nutzen, wird die Liste der Intervalle als Liste der beschrifteten Endpunkte geführt.

Jedes Element in der Liste enthält die Endpunktkoordinaten eines Intervalls sowie eine eindeutige ganze Zahl, die dieses Intervall identifiziert.

Dann wird die Liste nach Koordinaten sortiert und die Matrix nach M und nach aktualisiert.

Wenn sich die Konfiguration der Begrenzungsrahmen von einem Zeitschritt zum nächsten nicht wesentlich ändert, ist es nicht schwer zu glauben, dass diese Methode recht schnell ablaufen wird.

Im Falle von verformbaren Körpern, wie z. B. bei der Stoffsimulation, ist es möglicherweise nicht praktikabel, eine speziellere paarweise Beschneidungsstrategie wie unten beschrieben anzuwenden. Ein N-Körper-Beschneidungsansatz ist das Beste, was erreicht werden kann.

Wenn eine Obergrenze für die Geschwindigkeit der physischen Körper in