Wie funktionieren Kollisionsnetze in Spielen wie Zelda auf dem N64?

Ich habe kürzlich über die Technologie von Ocarina of Time / Majoras Mask gelesen und festgestellt, dass die Weltkollision mit einem einzelnen Dreiecksnetz (Eckpunkte, Normalen usw.) für einen gesamten Bereich erfolgt. Es gibt auch keine Anzeichen für vorverarbeitete räumliche Partitionierungsmethoden in dieser Datenstruktur.

Welche Algorithmen gibt es, um eine Zeichenkollision auf einem ähnlichen beliebigen Dreiecksnetz schnell genug durchzuführen, um auf einer Plattform wie dem N64 ausgeführt zu werden?

Quake ist ein zeitgemäßes Spiel mit einer ähnlichen Funktion, die mir in den Sinn kam. Ich verstehe, dass Quake Brush Collision funktioniert, indem ein AABB mit Ebenen unterteilt wird. Befindet sich ein Punkt im AABB und hinter allen Ebenen, kommt es zu einer Kollision. Diese Methode funktioniert jedoch nur mit einer Reihe einzelner konvexer Objekte, um eine Kollisionsszene zu erstellen.

Details zur Zelda-Datenstruktur Hier:

http://wiki.spinout182.com/w/Zelda_64:_Collision_Format http://zeldaspeedruns.com/oot/generalknowledge/zelda-64-engine

BEARBEITEN - Ich muss die reale Methode des realen Spiels nicht kennen, Zelda ist ein Beispiel. Ich suche nach einer Methode, um unter ähnlichen Hardwareeinschränkungen einen ähnlichen Effekt zu erzielen.

BEARBEITEN :

Dieses Projekt hat Mario 64 dekompiliert und enthält die Quelle für die Kollision.

Tigorus Rat befolgen. Ich habe stattdessen gesucht, wie die Technik in Mario 64 gemacht wird. (Zeldas Engine ist eine direkte Ableitung).

Ich fand heraus, dass dieses Dokument in Mario 64-Diskussionen mehrmals erwähnt wurde.

Ich habe das Papier gelesen und es beschreibt einen Algorithmus, der dieses Problem lösen würde. Es funktioniert ähnlich wie das Befegen von Ellipsen beim Beben, basiert jedoch eher auf Dreiecksuppe als auf Pinsel / Hobelsuppe.

Der in diesem Artikel vorgestellte Algorithmus behandelt die Kollisionserkennung gegen beliebige Netze, die als sogenannte Polygonsuppe gespeichert sind. Wenn eine Kollision erkannt wird, schiebt der Algorithmus das sich bewegende Objekt entlang der Hindernisse, wie es normalerweise in 3D-Computerspielen zu sehen ist. Die sich bewegende Einheit wird mit einem Ellipsoid angenähert, das für die meisten humanoiden oder tierischen Formen eine ziemlich enge Passform bietet.

Der Algorithmus löst auch viele Leistungsprobleme:

Persönlich hatte ich keine Leistungsprobleme damit und man muss sich auch daran erinnern, dass es zwei „Early Out“ -Punkte in der Funktion gibt, die tatsächlich ziemlich oft auftreten. Hier einige Statistiken: Ich bin ein paar Minuten in einer ERA-Testkarte herumgelaufen, die sowohl aus einem Gelände (erstellt aus einer Höhenkarte) als auch aus Polygonnetzen wie Häusern, Treppen usw. bestand. Insgesamt wurden 1,1 Millionen Dreiecke an die Funktion über die gesendet Der gesamte Testzeitraum und von diesen ungefähr 40% wurden als rückseitig erkannt und somit übersprungen1. Von den verbleibenden 700.000 Dreiecken konnten 65% die Funktion nach nur wenigen billigen Tests zur Berechnung der Zeitwerte t0 und t1 vorzeitig verlassen. Von den Dreiecken, die nicht früh austraten, mussten die meisten den Sweep-Test durchführen, aber einige konnten den Sweep überspringen, da eine Kollision mit der Innenseite des Dreiecks festgestellt wurde. Insgesamt mussten nur etwa 20% der an die Funktion gesendeten Dreiecke tatsächlich auf Kollision mit der Innenseite oder Kante des Dreiecks überprüft werden und zahlten somit den vollen Preis für die ziemlich lange Funktion.

Es würde mich wundern, wenn sie diese Liste der geladenen Polygone nicht in eine räumliche Datenstruktur vorverarbeiten. Es könnte so einfach sein wie ein einheitliches 2D-Gitter auf der ganzen Welt oder etwas komplizierteres wie ein kd-Baum.

Auf diese Weise können Sie schnell eine kurze Liste der Polygone finden, die sich in der Nähe eines interessierenden Punkts befinden, und Sie können dann jedes einzelne testen, um festzustellen, ob Sie kollidieren.

Jede moderne Physik-Engine sollte ein statisches Netz von Kollisionspolygonen mithilfe einer räumlichen Unterteilung problemlos effizient handhaben können. Schauen Sie sich zum Beispiel die btBvhTriangleMeshShape an, über die das Aufzählungszeichen verfügt .