Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Game Development
  2. Programming

So schneiden Sie eine konvexe Form dynamisch

by
Difficulty:AdvancedLength:LongLanguages:

German (Deutsch) translation by Federicco Ancie (you can also view the original English article)

Die Fähigkeit, eine konvexe Form dynamisch in zwei separate Formen aufzuteilen, ist eine sehr wertvolle Fähigkeit oder ein Werkzeug, das Sie in Ihrem Gamedev-Arsenal haben sollten. Diese Aufteilung ermöglicht fortgeschrittene Simulationstypen, wie z. B. binäre Raumpartitionen für Grafiken oder Physik, dynamisch zerstörerische Umgebungen(Sprödbruch!), Ozean- oder Wassersimulation, Kollisionsauflösung für Physik-Engines, binäre räumliche Partitionierung, und die Liste geht einfach weiter. Ein gutes Beispiel ist das Spiel Fruit Ninja für Kinect.

Was genau bedeutet es, eine konvexe Form zu teilen? In zwei Dimensionen bezeichnen wir eine Form als Polygon; In drei Dimensionen bezeichnen wir eine Form als Polyeder. (Polyeder ist das Wort, mit dem auf mehr als ein Polyeder verwiesen wird.)

Tipp: Im Allgemeinen vereinfachen konvexe Polygone und Polyeder viele Aspekte der Volumen- oder Netzmanipulation und -verwaltung. Aufgrund dieser Vereinfachung nimmt der gesamte Artikel konvexe Polygone und konvexe Polyeder an. Konkave Formen sind hier nicht zu diskutieren. Im Allgemeinen werden komplizierte konkave Formen als eine Sammlung verbundener konvexer Formen simuliert.


Voraussetzungen

Um die in diesem Artikel vorgestellten Ideen zu verstehen, benötigen Sie Grundkenntnisse in einer Programmiersprache und ein einfaches Verständnis des Punktprodukts.

Eine gute Möglichkeit, Formen in zwei und drei Dimensionen zu teilen, ist die Verwendung der Sutherland-Hodgman-Clipping-Routine. Diese Routine ist recht einfach und sehr effizient und kann auch geringfügig erweitert werden, um die numerische Robustheit zu berücksichtigen. Wenn Sie mit dem Algorithmus nicht vertraut sind, lesen Sie meinen vorherigen Artikel zu diesem Thema.

Ein Verständnis von Planes in zwei oder drei Dimensionen ist ebenfalls ein Muss. Es sollte beachtet werden, dass eine zweidimensionale Ebene als Projektion einer dreidimensionalen Ebene in zwei Dimensionen – oder, mit anderen Worten, eine Linie – betrachtet werden könnte.

Bitte haben Sie Verständnis dafür, dass ein Flugzeug auch als halber Raum betrachtet werden kann. Die Berechnung der Entfernung oder des Schnittpunkts von Punkten zu Halbräumen ist eine erforderliche Voraussetzung: Informationen hierzu finden Sie im letzten Abschnitt unter Erstellen einer benutzerdefinierten 2D-Physik-Engine: Die Core-Engine.


Demo-Quelle

Bitte beziehen Sie sich auf die Demonstrationsquelle (auch auf Bitbucket), die ich beim Lesen dieses Tutorials erstellt habe. Ich habe diese Demo zum Erstellen aller GIF-Bilder im Artikel verwendet. Der Quellcode ist in C++ (und sollte plattformübergreifend kompatibel sein), ist jedoch so geschrieben, dass er problemlos in jede Programmiersprache portiert werden kann.


Dreiecksteilung

Bevor wir uns mit dem Problem des Teilens eines gesamten Polygons befassen, werfen wir einen Blick auf das Problem des Teilens eines Dreiecks durch eine Schnittebene. Dies wird die Grundlage für das Verständnis bilden, um zu einer robusten und verallgemeinerten Lösung überzugehen.

Das Schöne an der Formteilung ist, dass Algorithmen in 2D häufig ohne große Probleme direkt in 3D erweitert werden können. Hier werde ich einen sehr einfachen Dreiecksaufteilungsalgorithmus für zwei und drei Dimensionen vorstellen.

Wenn sich ein Dreieck mit einer Teilungsebene schneidet, sollten drei neue Dreiecke generiert werden. Hier ist ein Bild, das ein Dreieck vor und nach dem Teilen entlang einer Ebene zeigt:

TriangleSplit

Bei einer Aufteilungsebene werden während des Schneidvorgangs drei neue Dreiecke ausgegeben. Lassen Sie uns etwas Code ins Freie werfen, vorausgesetzt, die drei Eckpunkte eines Dreiecks sind { a, b, c } gegen den Uhrzeigersinn(CCW) und wir wissen, dass die Kante ab (Kante der Eckpunkte a bis b) hat schnitt die Aufteilungsebene:

Hoffentlich hat dich der obige Code ein wenig erschreckt. Aber fürchte dich nicht; Wir berechnen hier lediglich einige Schnittpunkte, um zu wissen, wie drei neue Dreiecke generiert werden. Wenn man das vorherige Bild sorgfältig untersucht hätte, könnten die Positionen der Schnittpunkte offensichtlich sein: Sie sind dort, wo die gepunktete Linie auf die Aufteilungsebene trifft und wo die Kante ab die Aufteilungsebene schneidet. Hier ist ein Diagramm zur Vereinfachung:

TriangleSplitDiagram

Aus diesem Diagramm ist leicht ersichtlich, dass Ausgabedreiecke die Eckpunkte { a, ac, ab }, { ac, c, b } und { ab, ac, b } enthalten sollten. (Aber nicht unbedingt in genau diesem Format; zum Beispiel wäre { a, b, c } dasselbe Dreieck wie { c, b, a }, da die Eckpunkte einfach nach rechts verschoben wurden.)

Um zu bestimmen, welche Eckpunkte zu welchem der drei neuen Dreiecke beitragen, müssen wir bestimmen, ob der Eckpunkt a und der Eckpunkt c über oder unter der Ebene liegen. Da wir davon ausgehen, dass sich die Kante ab schneidet, können wir implizit ableiten, dass sich b auf der gegenüberliegenden Seite der Schnittebene von a befindet.

Wenn die Konvention eines negativen Abstands von einer Teilungsebene das Eindringen in die Ebene bedeutet, können wir ein Prädikat formulieren, um zu bestimmen, ob ein Punkt einen Halbraum schneidet: #define HitHalfspace( distance ) ((distance) < 0.0f). Dieses Prädikat wird in jeder if-Anweisung verwendet, um zu überprüfen, ob sich ein Punkt innerhalb des Halbraums der Schnittebene befindet.

Es gibt vier Fälle, in denen Kombinationen von a und b auf den Halbraum der Schnittebene treffen:

Da unsere Funktion erfordert, dass sich sowohl a als auch b auf gegenüberliegenden Seiten der Ebene befinden, werden zwei dieser Fälle fallen gelassen. Alles was übrig bleibt ist zu sehen, auf welcher Seite c liegt. Von hier aus ist die Ausrichtung aller drei Eckpunkte bekannt; Schnittpunkte und Ausgabescheitelpunkte können direkt berechnet werden.

Finden der Anfangskante

Um die SliceTriangle() -Funktion verwenden zu können, müssen wir eine Schnittkante eines Dreiecks finden. Die folgende Implementierung ist effizient und kann für alle Dreiecke in der Simulation verwendet werden, um möglicherweise aufgeteilt zu werden:

Nach der Berechnung des vorzeichenbehafteten Abstands jedes Dreiecksscheitelpunkts zur Teilungsebene kann durch Multiplikation festgestellt werden, ob zwei unterschiedliche Punkte auf gegenüberliegenden Seiten einer Ebene liegen. Da die Abstände innerhalb eines Paares positiv und negativ sind, muss das Produkt der beiden multiplizierten Werte negativ sein. Dies ermöglicht die Verwendung eines einfachen Prädikats, um festzustellen, ob zwei Punkte auf beiden Seiten einer Ebene liegen: #define OnOppositeSides(distanceA, distanceB)((distanceA) * (distanceB) < 0.0f).

Sobald festgestellt wird, dass sich eine Kante mit der Teilungsebene schneidet, werden die Dreiecksscheitelpunkte umbenannt und verschoben und sofort an die innere SliceTriangle-Funktion weitergeleitet. Auf diese Weise wird die erste gefundene Schnittkante in ab umbenannt.

So kann ein endgültiges Arbeitsprodukt aussehen:

Splitting triangles along cutting planes dynamically via user interaction.
Dynamisches Teilen von Dreiecken entlang von Schnittebenen über Benutzerinteraktion.

Das Aufteilen von Dreiecken auf diese Weise berücksichtigt jedes Dreieck unabhängig, und der hier vorgestellte Algorithmus erstreckt sich ohne zusätzliches Authoring von zwei auf drei Dimensionen. Diese Form des Abschneidens von Dreiecken ist ideal, wenn keine Informationen zur Nachbarschaft von Dreiecken erforderlich sind oder wenn abgeschnittene Dreiecke nirgendwo im Speicher gespeichert sind. Dies ist häufig der Fall, wenn Volumen von Kreuzungen berechnet werden, wie bei der Auftriebsimulation.

Das einzige Problem beim isolierten Teilen von Dreiecken besteht darin, dass keine Informationen über nebeneinander liegende Dreiecke vorliegen. Wenn Sie das obige GIF sorgfältig untersuchen, können Sie feststellen, dass viele Dreiecke kollineare Scheitelpunkte gemeinsam haben und daher zu einem einzigen Dreieck zusammengefasst werden können, um effizient gerendert zu werden. Der nächste Abschnitt dieses Artikels behandelt dieses Problem mit einem anderen, komplexeren Algorithmus (der alle in diesem Abschnitt beschriebenen Taktiken verwendet).


Sutherland-Hodgman

Nun zum letzten Thema. Unter der Annahme eines funktionierenden Verständnisses des Sutherland-Hodgman-Algorithmus ist es recht einfach, dieses Verständnis zu erweitern, um eine Form mit einer Ebene zu teilen und Eckpunkte auf beiden Seiten der Ebene auszugeben. Auch die numerische Robustheit kann (und sollte) berücksichtigt werden.

Lassen Sie uns kurz die alten Sutherland-Hodgman-Clipping-Fälle untersuchen:

Diese drei Fälle funktionieren anständig, berücksichtigen jedoch nicht die Dicke der Aufteilungsebene. Infolgedessen kann ein numerischer Fehler auftreten, wenn sich Objekte bewegen, was zu einer geringen zeitlichen Rahmenkohärenz führt. Diese Art von numerischer Instabilität kann dazu führen, dass eine Ecke in einem Frame und nicht in einem anderen Frame abgeschnitten wird, und diese Art von Jitter kann visuell ziemlich hässlich oder für die physikalische Simulation nicht akzeptabel sein.

Ein weiterer Vorteil dieses Tests mit dicken Ebenen besteht darin, dass Punkte, die sehr nahe an der Ebene liegen, tatsächlich als auf der Ebene liegend betrachtet werden können, was die abgeschnittene Geometrie etwas nützlicher macht. Es ist durchaus möglich, dass ein berechneter Schnittpunkt numerisch auf der falschen Seite einer Ebene liegt! Dicke Flugzeuge vermeiden solche seltsamen Probleme.

Durch die Verwendung dicker Ebenen für Schnittpunkttests kann ein neuer Falltyp hinzugefügt werden: ein Punkt, der direkt auf einer Ebene liegt.

Sutherland-Hodgman sollte wie folgt modifiziert werden (mit einem Gleitkomma-EPSILON, um dicke Ebenen zu berücksichtigen):

Diese Form von Sutherland-Hodgman gibt jedoch nur Eckpunkte auf einer Seite der Aufteilungsebene aus. Diese fünf Fälle können leicht auf neun erweitert werden, um Scheitelpunkte auf beiden Seiten einer Aufteilungsebene auszugeben:

Eine Implementierung dieser neun Fälle könnte folgendermaßen aussehen (abgeleitet von Ericsons Echtzeit-Kollisionserkennung):

Hier ist ein Beispiel von Sutherland-Hodgman in Aktion:

Splitting a polygon via Sutherland-Hodgman by user interaction. Polygons are triangulated as a triangle fan.
Dynamisches Teilen eines Polygons über Sutherland-Hodgman durch Benutzerinteraktion. Polygone werden als Dreiecksfächer trianguliert.

Es ist erwähnenswert, dass die endgültigen Polygone als Scheitelpunktliste im Format eines Dreiecksfächers gerendert werden können.

Numerische Robustheit

Es gibt ein Problem, das Sie beachten sollten: Wenn Sie einen Schnittpunkt von ab und eine Teilungsebene berechnen, leidet dieser Punkt unter einer numerischen Quantisierung. Dies bedeutet, dass jeder Schnittwert eine Annäherung an den tatsächlichen Schnittwert ist. Dies bedeutet auch, dass der Schnittpunkt ba numerisch nicht gleich ist; Eine winzige numerische Drift führt tatsächlich zu zwei unterschiedlichen Werten!

Example of a visible crack between triangles as a result of inconsistent clipping (image inspired by Ericson's Real-Time Collision Detection book).
Beispiel eines sichtbaren Risses zwischen Dreiecken infolge inkonsistenten Ausschnitts (Bild inspiriert von Ericsons Real-Time Collision Detection-Buch).

Eine naive Clipping-Routine kann einen großen Fehler bei der blinden Berechnung von Schnittpunkten machen, was zu T-Übergängen oder anderen Lücken in der Geometrie führen kann. Um ein solches Problem zu vermeiden, muss eine konsistente Schnittorientierung verwendet werden. Konventionell sollten Punkte von einer Seite einer Ebene zur anderen abgeschnitten werden. Diese strikte Schnittreihenfolge stellt sicher, dass derselbe Schnittpunkt berechnet wird, und löst potenzielle Lücken in der Geometrie (wie in der Abbildung oben gezeigt, gibt es rechts ein konsistentes Beschneidungsergebnis).


UV-Koordinaten

Um Texturen tatsächlich über geteilte Formen zu rendern (möglicherweise beim Teilen von Sprites), müssen Sie die UV-Koordinaten verstehen. Eine vollständige Erörterung der UV-Koordinaten und der Texturabbildung geht weit über den Rahmen dieses Artikels hinaus. Wenn Sie jedoch bereits über dieses Verständnis verfügen, sollte es einfach sein, Schnittpunkte in den UV-Raum umzuwandeln.

Bitte haben Sie Verständnis dafür, dass eine Transformation vom Weltraum zum UV-Raum eine Änderung der Basistransformation erfordert. Ich werde UV-Transformationen als Übung für den Leser hinterlassen!


Abschluss

In diesem Tutorial haben wir uns einige einfache lineare Algebra-Techniken angesehen, um das Problem der dynamischen Aufteilung generischer Formen anzugehen. Ich habe auch einige Probleme mit der numerischen Robustheit angesprochen. Sie sollten jetzt in der Lage sein, Ihren eigenen Formaufteilungscode zu implementieren oder die Demonstrationsquelle zu verwenden, um viele erweiterte und interessante Effekte oder Funktionen für die allgemeine Spielprogrammierung zu erzielen.

Referenzen

Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.