Die Mathematik in Gamedev ist einfach. Triangulation und Triangle.Net in der Einheit

Published on January 07, 2019

Die Mathematik in Gamedev ist einfach. Triangulation und Triangle.Net in der Einheit

    Hallo allerseits! Mein Name ist Grisha und ich bin der Gründer von CGDevs. Mathematik ist ein sehr cooles Werkzeug bei der Entwicklung von Spielen. Aber wenn wir sagen, dass es prinzipiell schwierig ist, auf das Verständnis von Vektoren und Matrizen zu verzichten , dann sind die Triangulationsalgorithmen nicht so notwendig, aber mit deren Hilfe wird eine ausreichend große Anzahl von interessanten Problemen gelöst. Heute möchte ich über ein ziemlich wichtiges Werkzeug in der Computergeometrie sprechen, wie Triangulation und deren Anwendung in der Spielebranche. Außerdem habe ich einen Port und einige Wrapper der großartigen Triangle.Net-Bibliothek für Unity geschrieben. Bei Interesse - willkommen unter Katze. Link zu Githab ist beigefügt.



    Was ist Triangulation?


    Im Allgemeinen ist die Triangulation eine Unterteilung eines geometrischen Objekts in Dreiecke. Dieses Konzept an sich ist recht einfach. Das grundlegende Beispiel für Triangulation bei Game-Engines ist das Mesh. Streng genommen kann ein Mesh nicht nur aus Dreiecken bestehen, sondern in Game-Engines werden aus verschiedenen Gründen Meshes aus Dreiecken genommen.



    Triangulationen sind unterschiedlich, aber eine der beliebtesten Arten von Triangulationen ist die Delaunay-Triangulation. Diese Art der Triangulation unterscheidet sich durch die Eigenschaft, dass in dem um jedes Dreieck beschriebenen Kreis nur die Eckpunkte dieses Dreiecks vorhanden sind.



    Warum werden sie gebraucht?


    Im Allgemeinen werden außerhalb der Spielebranche eine Vielzahl von Problemen mit Triangulationen gelöst. Bei der Spielentwicklung ist die erste Aufgabe, die mir einfällt, das Navigationsnetz. Navmesh ist eine Datenstruktur, die bestimmt, welchen Raum ein Spieler gehen kann. Sie können so komplexe Rechenprobleme wie das Ermitteln von Kollisionen mit einem Teil der Umgebung vermeiden.

    Das zweite interessante Problem, das mit Hilfe der Delaunay-Triangulation in einem Spielentwickler gelöst wurde, ist die Erzeugung von Terranen und Objekten, die als eine Menge von Punkten dargestellt werden. Der Hauptvorteil der Delaunay-Triangulation besteht in diesem Fall darin, dass Sie aufgrund ihrer Eigenschaften sehr scharfe Dreiecke vermeiden können, die den Tyrrain stören und Artefakte verursachen.



    Durch die Verwendung der Delaunay-Triangulation mit Bedingungen und Algorithmen wie dem zweiten Algorithmus von Chew und dem Ruppert-Algorithmus ist es außerdem möglich, Gitter für Tirrains noch besser zu generieren und gute Gitter für eine andere Anwendung zu generieren - die Finite-Elemente-Methode.

    Die Finite-Elemente-Methode selbst ist eine der Methoden, mit denen Probleme der angewandten Physik gelöst werden. In geymdev können Sie viele Probleme lösen, die mit der Simulation von Verformungen, Fluidsimulationen und anderen Spezialanwendungen verbunden sind. Auswirkungen. In der Regel für die Aufzeichnung von Animationseffekten, da das Verfahren in Echtzeit einen zu hohen Rechenaufwand aufweist. Ein wichtiges Detail bei der Verwendung der Methode ist, dass der Fehler der Methode von den Winkeln der Dreiecke im Raster abhängt. Wenn das Raster sehr scharfe Ecken aufweist, führt die Methode zu einem großen Fehler, weshalb die oben aufgeführten Algorithmen erforderlich sind.



    Und natürlich generieren prozedurale Maschen im Allgemeinen. Als Beispiel im Githab-Projekt gibt es eine Szene mit der Möglichkeit, Netze zu zeichnen. Einige physikalische Rätsel verwenden diese Anwendung als grundlegende Mechanik. Darüber hinaus ermöglichen Triangulationsalgorithmen die Verwendung der Prozedurerzeugung, um Probleme wie die prozedurale Zerstörbarkeit usw. zu lösen.

    Zusätzlich zu Gamedev wird Triangulation in Netzwerken, in der Bildverarbeitung, in verschiedenen analytischen Algorithmen sowie bei einigen Problemen der rechnergestützten Geometrie verwendet, z. B. bei der Vereinigung und dem Ausschluss von Polygonen voneinander (was häufig bei Aufgaben nützlich ist, die bei der Entwicklung von Spielen anfallen).

    Ohrclipping mit Löchern




    Vielleicht einer der einfachsten Triangulationsalgorithmen. Gibt nicht das beste Gitter an und hat im schlimmsten Fall einen großen Rechenaufwand O (n ^ 2).

    Lesen Sie mehr darüber in diesem Artikel.

    Bowyer-Watson-Algorithmus




    Ein Algorithmus, der eine Delaunay-Triangulation für eine Reihe von Punkten generiert. Im Allgemeinen ist, wie bei den meisten Delone-Algorithmen, bei korrekter Implementierung die algorithmische Komplexität O (n log n), wobei n die Anzahl der Eckpunkte ist. In einigen Fällen kann es jedoch O (n ^ 2) belegen.

    Der Nachteil von Ear Clipping ist, dass dieser Algorithmus eine konvexe Triangulation erstellt und in der Grundimplementierung keine Löcher im resultierenden Gitter impliziert.

    Delaunay-Verfeinerungsverarbeitung




    Chews zweiter Algorithmus und Rupperts Algorithmus sind Algorithmen, mit denen Sie die Delaunay-Triangulation einschränken und den Mindestwinkel eines Dreiecks im Gitter festlegen können. Ein wichtiges Detail der Algorithmen ist, dass sie in eine Endlosschleife gelangen können und garantiert ein Ergebnis bei Winkeln zwischen ungefähr 20,7 Grad und 29 Grad liefern. Die Möglichkeit, den Mindestwinkel einzustellen, ist wichtig, wenn die oben beschriebenen Aufgaben gelöst werden.

    Der zweite Algorithmus von Chew ist im kostenlosen Paket www.cs.cmu.edu/~quake/triangle.html und dessen Port auf .Net archive.codeplex.com/?p=triangle implementiert

    Triangle.Net für die Einheit


    Nun, da Sie mit Hilfe von Triangulationen so viele coole Aufgaben lösen können, wollte ich in den Ferien meinen eigenen Wrapper für Unity implementieren, damit ich immer ein handliches Werkzeug zur Hand habe. In dieser Implementierung arbeitet der Triangulationsalgorithmus im Durchschnitt für O (n) und im schlimmsten Fall für O (n * log n), wobei n die Anzahl der Eckpunkte ist. Beim Testen auf 1k-Eckpunkte haben die zufällig im Editor des Intel Core i7-8700 über das Quadrat verteilten Einheiten das Raster in durchschnittlich 7,56 Sekunden erstellt.

    Die Hauptunterschiede zur Originalbibliothek bestehen darin, dass unter Unity geschärfte Methodenerweiterungen vorhanden sind und in der gesamten Bibliothek double durch float ersetzt wird (+ einige spezielle Operatoren für cast). Double in einer Unit ist nicht sehr sinnvoll. Wenn wir physikalische Simulationen berücksichtigen, würde ich eine separate Anwendung für die Plus-Bibliothek verwenden, und das Ergebnis der Berechnungen wurde bereits zur reinen Visualisierung an Unity übergeben. Außerdem wurde der Mesh-Typ in TriangleNetMesh umbenannt, um das Mesh nicht von Unity zu entfernen. Ja, sie befinden sich bereits in verschiedenen Namespaces, aber ich denke trotzdem, die Neulinge wären ein wenig verwirrt darüber, dass wir mit Hilfe eines Meshs ein anderes bekommen.

    Das Wesentliche an der Bibliothek ist, dass Sie zunächst ein sogenanntes Polygon definieren müssen. Generieren Sie dann auf der Grundlage ein Netz. Damit dies mit Einheitendatenstrukturen funktioniert, wurden verschiedene Erweiterungsmethoden eingeführt.

    Anwendungsbeispiel
    public void GenerateMesh()
    {
    	if(_CurrentState != MeshDrawerState.Nothing) return;
    	Polygon poly = new Polygon();
    	poly.Add(_Contour);
    	foreach (var hole in _Holes)
    	{
    		poly.Add(hole, true);
    	}
    	var triangleNetMesh = (TriangleNetMesh) poly.Triangulate();
    	GameObject go = new GameObject("Generated mesh");
    	var mf = go.AddComponent<MeshFilter>();
    	var mesh = triangleNetMesh.GenerateUnityMesh();
    	mesh.uv = GenerateUv(mesh.vertices);
    	mf.mesh = mesh;
    	var mr = go.AddComponent<MeshRenderer>();
    	mr.sharedMaterial = _MeshMaterial;
    	var collider = go.AddComponent<PolygonCollider2D>();
    	collider.points = _Contour.ToArray();
    	var rb = go.AddComponent<Rigidbody2D>();
    	rb.mass = triangleNetMesh.Triangles.Sum(tris => tris.Area);
    	Clear();
    }
    



    Zur Demonstration und Verwendung von Beispielen wurde eine spezielle Demoszene mit der Möglichkeit zum Zeichnen von Maschen erstellt. Damit ist auch der Library-Port im Github-Projekt zu finden.

    Vielen Dank für Ihre Aufmerksamkeit! Ich hoffe, dass der Port und der Artikel jemandem nützlich sein werden und es wurde ein wenig klarer, warum wir Triangulation und Kenntnisse der Mathematik im Allgemeinen brauchen. Ich werde weiterhin versuchen, den Einsatz und die Methoden zur Lösung verschiedener mathematischer Probleme in Spielentwicklern aufzuzeigen. In der rechnerischen Geometrie selbst gibt es noch viel Interessantes, aber dazu gibt es noch viele andere interessante Abschnitte der höheren Mathematik.