Kollisionsentdeckung bezieht sich normalerweise auf das rechenbetonte Problem, die Kreuzung von zwei oder mehr Gegenständen zu entdecken. Während das Thema meistenteils mit seinem Gebrauch in Videospielen und anderen physischen Simulationen vereinigt wird, hat es auch Anwendungen in der Robotertechnik. Zusätzlich zur Bestimmung, ob zwei Gegenstände kollidiert haben, können Kollisionsentdeckungssysteme auch Zeit des Einflusses (TOI) berechnen, und eine Kontakt-Sammelleitung (der Satz melden, Punkte durchzuschneiden). Kollisionsansprechgeschäfte mit dem Simulieren, was geschieht, wenn eine Kollision entdeckt wird (sieh Physik-Motor, ragdoll Physik). Das Beheben von Kollisionsentdeckungsproblemen verlangt umfassenden Gebrauch von Konzepten von der geradlinigen Algebra und rechenbetonten Geometrie.

Übersicht

In der physischen Simulation möchten wir Experimente, wie das Spielen des Billards durchführen. Die Physik von strammen Billardbällen, wird unter dem Regenschirm der starren Körperbewegung und elastischen Kollisionen gut verstanden. Eine anfängliche Beschreibung der Situation, würde mit einer sehr genauen physischen Beschreibung des Billardtisches und der Bälle, sowie der anfänglichen Positionen aller Bälle gegeben. In Anbetracht einer Kraft, die auf den Stichwort-Ball angewandt ist (wahrscheinlich sich aus einem Spieler ergebend, der den Ball mit seinem oder ihrem Stichwort-Stock schlägt), wollen wir die Schussbahnen, genaue Bewegung und schließlichen Ruhestätten aller Bälle mit einem Computerprogramm berechnen. Ein Programm, um dieses Spiel vorzutäuschen, würde aus mehreren Teilen bestehen, von denen einer dafür verantwortlich sein würde, die genauen Einflüsse zwischen den Billardbällen zu berechnen. Dieses besondere Beispiel erweist sich auch, numerisch nicht stabil zu sein: Ein kleiner Fehler in jeder Berechnung wird drastische Änderungen in der Endposition der Billardbälle verursachen.

Videospiele haben ähnliche Voraussetzungen mit einigen entscheidenden Unterschieden. Während physische Simulation wirkliche Physik so genau vortäuschen muss wie möglich, müssen Videospiele wirkliche Physik auf eine annehmbare Weise in Realtime und robust vortäuschen. Kompromissen wird erlaubt, so lange die resultierende Simulation den Spielspielern befriedigt.

Kollisionsentdeckung in der physischen Simulation

Physische Simulatoren unterscheiden sich in der Weise, wie sie auf eine Kollision einwirken. Etwas Gebrauch die Weichheit des Materials, um eine Kraft zu berechnen, die die Kollision in den folgenden Zeitsprüngen wie es auflösen wird, ist in Wirklichkeit. Wegen der niedrigen Weichheit von einigen Materialien ist das sehr intensive Zentraleinheit. Einige Simulatoren schätzen die Zeit der Kollision durch die geradlinige Interpolation, wiederholen die Simulation, und berechnen die Kollision durch die abstrakteren Methoden von Bewahrungsgesetzen.

Einige wiederholen die geradlinige Interpolation (Die Methode des Newtons), um die Zeit der Kollision mit einer viel höheren Präzision zu berechnen, als der Rest der Simulation. Kollisionsentdeckung verwertet Zeitkohärenz, um noch feinere Zeitsprünge ohne viel zunehmende Zentraleinheitsnachfrage, solcher als in der Flugsicherung zu erlauben.

Nach einem unelastischen Stoß können spezielle Staaten des Schiebens und der Ruhe vorkommen und zum Beispiel der Offene Dynamik-Motor verwendet Einschränkungen, um sie vorzutäuschen. Einschränkungen vermeiden Trägheit und so Instabilität. Die Durchführung des Rests mittels eines Szene-Graphen vermeidet Antrieb.

Mit anderen Worten fungieren physische Simulatoren gewöhnlich einer von zwei Wegen, wo die Kollision a posteriori entdeckt wird (nachdem die Kollision vorkommt), oder a priori (bevor die Kollision vorkommt). Zusätzlich zu a posteriori und a priori Unterscheidung werden fast alle modernen Kollisionsentdeckungsalgorithmen in eine Hierarchie von Algorithmen gebrochen. Häufig werden die Begriffe "getrennter" und "dauernd" aber nicht a posteriori und a priori gebraucht.

A posteriori (getrennt) gegen (den dauernden) a priori

In a posteriori Fall bringen wir die physische Simulation durch einen kleinen Zeitsprung vor, überprüfen dann, ob sich irgendwelche Gegenstände schneiden, oder irgendwie so einander nah sind, dass wir sie halten, um uns zu schneiden. An jedem Simulierungsschritt wird eine Liste aller sich schneidenden Körper geschaffen, und die Positionen und Schussbahnen dieser Gegenstände werden irgendwie "befestigt", um für die Kollision verantwortlich zu sein. Wir sagen, dass diese Methode a posteriori darin besteht, weil wir normalerweise den wirklichen Moment der Kollision verpassen, und nur die Kollision fangen, nachdem es wirklich geschehen ist.

In den a priori Methoden schreiben wir einen Kollisionsentdeckungsalgorithmus, der im Stande sein wird, sehr genau die Schussbahnen der physischen Körper vorauszusagen. Die Momente der Kollision werden mit der hohen Präzision berechnet, und die physischen Körper dringen nie wirklich zwischenein. Wir nennen das a priori, weil wir die Momente der Kollision berechnen, bevor wir die Konfiguration der physischen Körper aktualisieren.

Die Hauptvorteile a posteriori Methoden sind wie folgt. In diesem Fall braucht der Kollisionsentdeckungsalgorithmus nicht der unzähligen physischen Variablen bewusst zu sein; eine einfache Liste von physischen Körpern wird zum Algorithmus gefüttert, und das Programm gibt eine Liste von sich schneidenden Körpern zurück. Der Kollisionsentdeckungsalgorithmus braucht Reibung, elastische Kollisionen, oder schlechtere, nichtelastische Kollisionen und verformbare Körper nicht zu verstehen. Außerdem a posteriori sind Algorithmen tatsächlich eine Dimension, die einfacher ist als die a priori Algorithmen. Tatsächlich muss sich ein a priori Algorithmus mit der Zeitvariable befassen, die von a posteriori Problem fehlt.

Andererseits a posteriori verursachen Algorithmen Probleme im "Befestigen"-Schritt, wo Kreuzungen (die nicht physisch richtig sind) korrigiert werden müssen. Außerdem, wenn der getrennte Schritt mit der Gegenstand-Verhältnisgeschwindigkeit nicht verbunden ist, konnte die Kollision unentdeckt gehen, auf einen Gegenstand hinauslaufend, der einen anderen, wenn schnell genug durchführt.

Die Vorteile der a priori Algorithmen sind vergrößerte Treue und Stabilität. Es ist schwierig (aber nicht völlig unmöglich), die physische Simulation vom Kollisionsentdeckungsalgorithmus zu trennen. Jedoch, in allen außer den einfachsten Fällen, hat das Problem der Bestimmung vorzeitig, wenn zwei Körper kollidieren werden (gegeben einige anfängliche Daten) keine geschlossene Form-Lösung — ein numerischer Wurzelfinder wird gewöhnlich beteiligt.

Einige Gegenstände sind im sich ausruhenden Kontakt, d. h. in der Kollision, aber weder von, noch das Zwischeneindringen wie eine Vase springend, die auf einem Tisch ruht. In allen Fällen, Kontakt ausruhen lassend, verlangt spezielle Behandlung: Wenn zwei Gegenstände (a posteriori) oder Gleiten (a priori) kollidieren und ihre Verhältnisbewegung unter einer Schwelle ist, wird Reibung stiction, und beide Gegenstände werden in demselben Zweig des Szene-Graphen eingeordnet

Optimierung

Die offensichtlichen Annäherungen an die Kollisionsentdeckung für vielfache Gegenstände sind sehr langsam.

Die Überprüfung jedes Gegenstands gegen jeden anderen Gegenstand wird natürlich arbeiten, aber ist

zu ineffizient, um verwendet zu werden, wenn die Zahl von Gegenständen überhaupt groß ist. Die Überprüfung von Gegenständen mit der komplizierten Geometrie gegen einander auf die offensichtliche Weise, durch die Überprüfung jedes Gesichtes gegen einander liegt, ist selbst ziemlich langsam. So ist beträchtliche Forschung darauf angewandt worden, das Problem zu beschleunigen.

Ausnutzung zeitlicher Kohärenz

In vielen Anwendungen, der Konfiguration von physischen Körpern von einem Zeitsprung bis die folgenden Änderungen sehr wenig. Viele der Gegenstände können sich überhaupt nicht bewegen.

Algorithmen sind entworfen worden, so dass die in einem vorhergehenden Zeitsprung getanen Berechnungen im Uhrzeit-Schritt wiederverwendet werden können, auf schnellere Algorithmen hinauslaufend.

Am rauen Niveau der Kollisionsentdeckung ist das Ziel, Paare von Gegenständen zu finden, die sich potenziell schneiden könnten. Jene Paare werden weitere Analyse verlangen. Ein früher hoher Leistungsalgorithmus dafür wurde von Ming C. Lin an der Universität Kaliforniens, Berkeley http://www.cs.berkeley.edu/~jfc/mirtich/collDet.html entwickelt, der vorgeschlagen hat, Achse-ausgerichtete begrenzende Kästen für alle n Körper in der Szene zu verwenden.

Jeder Kasten wird durch das Produkt von drei Zwischenräumen vertreten (d. h. ein Kasten würde sein.) Ist ein allgemeiner Algorithmus für die Kollisionsentdeckung von begrenzenden Kästen Kehren, und beschneiden. Wir bemerken, dass sich zwei solche Kästen, und schneiden, wenn sich und nur wenn, schneidet, sich schneidet und sich schneidet. Wir nehmen an, dass sich von einem Zeitsprung bis das folgende, und schneiden, dann ist es sehr wahrscheinlich, dass am folgenden Zeitsprung sie sich noch schneiden werden. Ebenfalls, wenn sie sich im vorherigen Zeitsprung nicht geschnitten haben, dann werden sie sehr wahrscheinlich nicht dazu weitermachen.

So reduzieren wir das Problem auf dieses des Verfolgens vom Rahmen bis Rahmen, den Zwischenräume wirklich durchschneiden. Wir haben drei Listen von Zwischenräumen (ein für jede Achse), und alle Listen sind dieselbe Länge (da jede Liste Länge, die Zahl von begrenzenden Kästen hat.) In jeder Liste wird jedem Zwischenraum erlaubt, alle anderen Zwischenräume in der Liste durchzuschneiden. So für jede Liste werden wir eine Matrix von zeroes und haben: Ist 1, wenn sich Zwischenräume und, und 0 schneiden, wenn sie sich nicht schneiden.

Durch unsere Annahme wird die zu einer Liste von Zwischenräumen vereinigte Matrix im Wesentlichen unverändert von einem Zeitsprung bis das folgende bleiben. Um das auszunutzen, wird die Liste von Zwischenräumen wirklich als eine Liste von etikettierten Endpunkten aufrechterhalten. Jedes Element der Liste hat die Koordinate eines Endpunkts eines Zwischenraums, sowie eine einzigartige ganze Zahl, die diesen Zwischenraum identifiziert. Dann sortieren wir die Liste durch Koordinaten, und aktualisieren die Matrix, als wir gehen. Es ist nicht so hart, um zu glauben, dass dieser Algorithmus relativ schnell arbeiten wird, wenn tatsächlich sich die Konfiguration von begrenzenden Kästen bedeutsam von einem Zeitsprung bis das folgende nicht ändert.

Im Fall von verformbaren Körpern wie Tuchsimulation kann es nicht möglich sein, einen spezifischeren pairwise Beschneidung des Algorithmus, wie besprochen, unten zu verwenden, und ein N-Körperbeschneidungsalgorithmus ist am besten, dass getan werden kann.

Wenn ein gebundener oberer auf der Geschwindigkeit der physischen Körper in einer Szene gelegt werden kann, dann können Paare von Gegenständen gestützt auf ihrer anfänglichen Entfernung und der Größe des Zeitsprunges beschnitten werden.

Beschneidung von Pairwise

Sobald wir ein Paar von physischen Körpern für die weitere Untersuchung ausgewählt haben, müssen wir für Kollisionen sorgfältiger überprüfen. Jedoch, in vielen Anwendungen, werden individuelle Gegenstände (wenn sie nicht zu verformbar sind) durch eine Reihe kleinerer Primitiver, hauptsächlich Dreiecke beschrieben. So jetzt haben wir zwei Sätze von Dreiecken, und (für die Einfachheit, wir werden annehmen, dass jeder Satz dieselbe Zahl von Dreiecken hat.)

Das offensichtliche Ding zu tun ist, alle Dreiecke gegen alle Dreiecke für Kollisionen zu überprüfen, aber das schließt Vergleiche ein, der hoch ineffizient ist. Wenn möglich, ist es wünschenswert, einen Beschneidungsalgorithmus zu verwenden, um die Anzahl von Paaren von Dreiecken zu vermindern, die wir überprüfen müssen.

Die am weitesten verwendete Familie von Algorithmen ist als die hierarchische begrenzende Volumen-Methode bekannt. Als ein Aufbereitungsschritt für jeden Gegenstand (in unserem Beispiel, und) werden wir eine Hierarchie von begrenzenden Volumina berechnen. Dann jedes Mal wird Schritt, wenn wir für Kollisionen zwischen und, die hierarchischen begrenzenden Volumina überprüfen müssen, verwendet, um die Anzahl von Paaren von Dreiecken unter der Rücksicht zu vermindern. Für die Einfachheit werden wir einem Beispiel-Verwenden-Springen Bereiche geben, obwohl es bemerkt worden ist, dass Bereiche in vielen Fällen unerwünscht sind.

Wenn eine Reihe von Dreiecken ist, können wir einen begrenzenden Bereich vorberechnen. Es gibt viele Weisen zu wählen, wir nehmen nur an, dass das ein Bereich ist, der völlig enthält und so klein wie möglich ist.

Vorzeitig können wir rechnen und. Klar, wenn sich diese zwei Bereiche nicht schneiden (und das sehr leicht ist zu prüfen), dann tut keiner und. Das ist nicht viel besser als ein N-Körperbeschneidungsalgorithmus jedoch.

Wenn eine Reihe von Dreiecken ist, dann können wir es in zwei Hälften spalten und. Wir können das zu tun und, und wir können (vorzeitig) die begrenzenden Bereiche berechnen und. Die Hoffnung hier besteht darin, dass diese springenden Bereiche viel kleiner sind als und. Und, wenn sich zum Beispiel, und nicht schneiden, dann gibt es keinen Sinn in der Anmeldung jedes Dreiecks gegen jedes Dreieck darin.

Als eine Vorberechnung können wir jeden physischen Körper (vertreten durch eine Reihe von Dreiecken) nehmen und ihn rekursiv in einen binären Baum zersetzen, wo jeder Knoten eine Reihe von Dreiecken vertritt, und seine zwei Kinder vertreten und. An jedem Knoten im Baum können wir den begrenzenden Bereich vorschätzen.

Wenn die Zeit kommt, für ein Paar von Gegenständen für die Kollision zu prüfen, kann ihr begrenzender Bereich-Baum verwendet werden, um viele Paare von Dreiecken zu beseitigen.

Viele Varianten der Algorithmen werden durch die Auswahl von etwas anderem erhalten als ein Bereich dafür. Wenn man Achse-ausgerichtete begrenzende Kästen wählt, bekommt man AABBTrees. Orientierte begrenzende Kasten-Bäume werden OBBTrees genannt. Einige Bäume sind leichter zu aktualisieren, wenn sich der zu Grunde liegende Gegenstand ändert. Einige Bäume können höhere Ordnungsprimitive wie Fugenbretter statt einfacher Dreiecke anpassen.

Genaue pairwise Kollisionsentdeckung

Sobald wir getan werden beschneidend, werden wir mit mehreren Kandidat-Paaren verlassen, für die genaue Kollisionsentdeckung zu überprüfen.

Eine grundlegende Beobachtung besteht darin, dass für irgendwelche zwei konvexen Gegenstände, die zusammenhanglos sind, man ein Flugzeug im Raum finden kann, so dass ein Gegenstand völlig auf einer Seite dieses Flugzeugs liegt, und der andere Gegenstand auf der Gegenseite dieses Flugzeugs liegt. Das erlaubt die Entwicklung von sehr schnellen Kollisionsentdeckungsalgorithmen für konvexe Gegenstände.

Die frühe Arbeit in diesem Gebiet ist "mit dem Trennen des Flugzeugs" Methoden verbunden gewesen. Zwei Dreiecke kollidieren im Wesentlichen nur, wenn sie durch ein Flugzeug nicht getrennt werden können, das drei Scheitelpunkte durchgeht. D. h. wenn die Dreiecke sind, und wo jeder ein Vektor darin ist, dann können wir drei Scheitelpunkte nehmen, finden Sie, dass ein Flugzeug, das alle drei Scheitelpunkte und Kontrolle durchgeht sieht, ob das ein sich trennendes Flugzeug ist. Wenn ein solches Flugzeug ein sich trennendes Flugzeug ist, dann, wie man hält, sind die Dreiecke zusammenhanglos. Andererseits, wenn keines dieser Flugzeuge Flugzeuge trennt, dann, wie man hält, schneiden sich die Dreiecke. Es gibt zwanzig solche Flugzeuge.

Wenn die Dreiecke coplanar sind, ist dieser Test nicht völlig erfolgreich. Man kann einige Extraflugzeuge, zum Beispiel, Flugzeuge hinzufügen, die zu Dreieck-Rändern normal sind, um das Problem völlig zu befestigen. In anderen Fällen müssen sich Gegenstände, die sich an einem flachen Gesicht treffen, notwendigerweise auch in einem Winkel anderswohin treffen, folglich wird die gesamte Kollisionsentdeckung im Stande sein, die Kollision zu finden.

Bessere Methoden sind seitdem entwickelt worden. Sehr schnelle Algorithmen sind verfügbar, für die nächsten Punkte auf der Oberfläche von zwei konvexen polyedrischen Gegenständen zu finden. Die frühe Arbeit von Ming C. Lin hat eine Schwankung auf dem Simplexalgorithmus von der geradlinigen Programmierung verwendet. Der Entfernungsalgorithmus von Gilbert-Johnson-Keerthi hat diese Annäherung ersetzt. Diese Algorithmen nähern sich unveränderlicher Zeit, wenn angewandt, wiederholt Paaren von stationären oder schleppenden Gegenständen, wenn verwendet, mit Startpunkten von der vorherigen Kollisionskontrolle.

Das Endergebnis dieser ganzen algorithmischen Arbeit besteht darin, dass Kollisionsentdeckung effizient für Tausende davon getan werden kann, Gegenstände in Realtime auf typischen Personalcomputern und Spielkonsolen zu bewegen.

A priori Beschneidung

Wo die meisten beteiligten Gegenstände befestigt werden, wie für Videospiele typisch ist, können a priori Methoden mit der Vorberechnung verwendet werden, um Ausführung zu beschleunigen.

Beschneidung ist auch hier, sowohl N-Körperbeschneidung als auch Pairwise-Beschneidung wünschenswert, aber die Algorithmen müssen Zeit in Anspruch nehmen und die Typen von Bewegungen, die im zu Grunde liegenden physischen System in die Rücksicht verwendet sind.

Wenn es zur genauen pairwise Kollisionsentdeckung kommt, ist das hoch Schussbahn-Abhängiger, und man muss fast einen numerischen wurzelfindenden Algorithmus verwenden, um den Moment des Einflusses zu schätzen.

Als ein Beispiel, denken Sie zwei Dreiecke, die sich rechtzeitig bewegen und. An jedem Punkt rechtzeitig können die zwei Dreiecke für die Kreuzung mit den zwanzig vorher erwähnten Flugzeugen überprüft werden. Jedoch können wir besser tun, da diese zwanzig Flugzeuge alle rechtzeitig verfolgt werden können. Wenn das Flugzeug ist, das Punkte in dann durchgeht, gibt ihm zwanzig Flugzeuge, um zu verfolgen. Jedes Flugzeug muss gegen drei Scheitelpunkte verfolgt werden, das gibt sechzig Werte, um zu verfolgen. Das Verwenden eines Wurzelfinders auf diesen sechzig Funktionen erzeugt die genauen Kollisionszeiten für die zwei gegebenen Dreiecke und die zwei gegebene Schussbahn. Wir bemerken hier, dass, wenn, wie man annimmt, die Schussbahnen der Scheitelpunkte geradlinige Polynome in dann den sechzig Endfunktionen sind, tatsächlich Kubikpolynome, und in diesem Ausnahmefall sind, ist es möglich, die genaue Kollisionszeit mit der Formel für die Wurzeln des kubischen ausfindig zu machen. Einige numerische Analytiker schlagen vor, dass das Verwenden der Formel für die Wurzeln des kubischen nicht so numerisch stabil ist wie das Verwenden eines Wurzelfinders für Polynome.

Das Raumverteilen

Alternative Algorithmen werden unter dem Raumverteilen-Regenschirm gruppiert, der octrees, das binäre Raumverteilen (oder BSP Bäume) und anderer, ähnliche Annäherungen einschließt. Wenn man Raum in mehrere einfache Zellen spaltet, und wenn, wie man zeigen kann, zwei Gegenstände in derselben Zelle nicht sind, dann brauchen sie nicht für die Kreuzung überprüft zu werden. Da BSP Bäume vorgeschätzt werden können, wird dieser Annäherung behandelnden Wänden und festen Hindernissen in Spielen gut angepasst. Diese Algorithmen sind allgemein älter als die Algorithmen, die oben beschrieben sind.

Videospiele

Videospiele müssen ihre sehr beschränkte Rechenzeit zwischen mehreren Aufgaben spalten. Trotz dieser Quellengrenze und des Gebrauches von relativ primitiven Kollisionsentdeckungsalgorithmen sind Programmierer im Stande gewesen, glaubwürdig, wenn ungenau, Systeme für den Gebrauch in Spielen zu schaffen.

Seit langem hatten Videospiele sehr begrenzte Zahl von Gegenständen, und so Überprüfung zu behandeln, dass alle Paare nicht ein Problem waren. In zweidimensionalen Spielen, in einigen Fällen, ist die Hardware im Stande gewesen, überlappende Pixel zwischen Elfen auf dem Schirm effizient zu entdecken und zu melden. In anderen Fällen, einfach den Schirm mit Ziegeln deckend und jede Elfe in die Ziegel bindend, überlappt es stellt genügend Beschneidung, und für Pairwise-Kontrollen zur Verfügung, Rechtecke begrenzend, oder Kreise haben gerufen hitboxes werden verwendet und genug genau gehalten.

Dreidimensionale Spiele haben Raumverteilen-Methoden für - Körperbeschneidung verwendet, und seit langem einen oder einige Bereiche pro wirklichen 3D-Gegenstand für Pairwise-Kontrollen verwendet. Genaue Kontrollen sind sehr selten, außer in Spielen, die versuchen, Wirklichkeit nah vorzutäuschen. Sogar dann werden genaue Kontrollen in allen Fällen nicht notwendigerweise verwendet.

Weil Spiele wirkliche Physik nicht nachzuahmen brauchen, ist Stabilität nicht so viel eines Problems. Fast alle Spiele verwenden a posteriori Kollisionsentdeckung, und Kollisionen werden häufig mit sehr einfachen Regeln aufgelöst. Zum Beispiel, wenn ein Charakter eingebettet in einer Wand wird, könnte er einfach zu seiner letzten bekannten guten Position zurückgekehrt werden. Einige Spiele werden die Entfernung berechnen, die der Charakter bewegen, bevor er in eine Wand eingebettet wird, und ihm nur erlauben kann, das weit zu bewegen.

In vielen Fällen für Videospiele ist das Approximieren den Charakteren durch einen Punkt zum Zweck der Kollisionsentdeckung mit der Umgebung genügend. In diesem Fall stellen Binäre Raumverteilen-Bäume einen lebensfähigen, effizienten und einfachen Algorithmus zur Verfügung, um zu überprüfen, ob ein Punkt in der Landschaft eingebettet wird oder nicht. Solch eine Datenstruktur kann auch verwendet werden, um "sich ausruhende Position" Situation anmutig zu behandeln, wenn ein Charakter entlang dem Boden läuft. Kollisionen zwischen Charakteren und Kollisionen mit Kugeln und Gefahren, werden getrennt behandelt.

Ein robuster Simulator ist derjenige, der auf jeden Eingang auf eine angemessene Weise reagieren wird. Zum Beispiel, wenn wir uns vorstellen, dass ein hohes Geschwindigkeitsrennauto-Videospiel, von einer Simulation zum folgenden gehen, ist es denkbar, dass die Autos eine wesentliche Entfernung entlang der Rasse-Spur vorbringen würden. Wenn es ein seichtes Hindernis auf der Spur gibt (wie eine Backsteinmauer), ist es nicht völlig unwahrscheinlich, dass das Auto darüber völlig springen wird, und das sehr unerwünscht ist. In anderen Beispielen wird das "Befestigen", dass a posteriori Algorithmen verlangen, richtig nicht durchgeführt, und Charaktere finden sich eingebettet in Wänden oder dem Zurückgehen in eine tiefe Leere, manchmal gekennzeichnet als "schwarze Hölle," "blaue Hölle," oder "grüne Hölle," abhängig von der vorherrschenden Farbe. Das sind die Gütestempel einer Mangel-Kollisionsentdeckung und physischen Simulierungssystems. ist ein berüchtigtes Beispiel eines Spiels, das entweder ein Mangel-Kollisionsentdeckungssystem hat oder dasjenige nicht sogar hat.

Siehe auch

• Erfolg-Prüfung
• Das Springen des Volumens
• Spielphysik
• Entfernungsalgorithmus von Gilbert-Johnson-Keerthi
• Physik-Motor
• Lubachevsky-Stillinger Algorithmus
• Physik von Ragdoll

Links

• OZCollide Frei, Schnell und Quer-Plattform-Entdeckungsbibliothek.
• Universität North Carolinas an der Kapelle-Hügel-Kollisionsentdeckungsforschungswebsite
• Prof. Steven Cameron (die Universität Oxford) Website auf der Kollisionsentdeckung
• Wie man eine Kollision durch George Beck, Wolfram-Demonstrationsprojekt vermeidet.