Ich arbeite an der Suche nach einem RTS-Spiel, bei dem ich ein Navigationsgitter aus dem Gitter des Spiels baue.Schnellster Triangulationsalgorithmus mit Löchern?
Ich habe einen ähnlichen Algorithmus wie Marching Squares geschrieben, der die Grenzen zwischen den begehbaren und nicht begehbaren Regionen der Karte erstellt und vereinfacht. Jetzt habe ich ein "Mesh", das nur aus Kanten besteht. Ich muss dieses Mesh so triangulieren, dass die finale Triangulation die ursprünglichen Kanten enthält, und dann kann ich die nicht begehbaren Regionen entfernen, um Löcher im Navigationsnetz zu erzeugen. Zum Beispiel, ich brauche dies zu tun ...
Die Dreiecke, die begehbaren Bereiche der Karte darstellen. Die Löcher repräsentieren nicht begehbare Regionen wie Berge oder Gebäude. Das Mesh kann als 2D betrachtet werden, da die Höhe irrelevant ist. Dies ist offensichtlich ein sehr vereinfachter Fall. Das Navigations-Mesh im Spiel wird aus tausenden von Vertices und vielen Löchern bestehen, aber ich kann es für dynamische Updates in kleinere Stücke zerlegen.
Ich habe eingeschränkte Delaunay-Triangulation-Algorithmen untersucht, die zuerst eine Delaunay-Triangulation der Punkte erstellen und dann alle Dreiecke entfernen, die die beschränkten Kanten schneiden, und dann die entfernten Dreiecke neu trianguliert.
Dies scheint ein wenig überflüssig für meine Zwecke. Mein Mesh muss nicht Delaunay sein, und es besteht komplett aus eingeschränkten Kanten, also würde ich gerne die zusätzlichen Triangulationen überspringen, wenn möglich. Gibt es dafür einen besseren Algorithmus? Ich habe geschaut und geschaut und konnte nur eingeschränkte Delaunay-Algorithmen finden. Oder vielleicht liege ich falsch, und ein eingeschränkter Delaunay-Algorithmus wäre am besten?
Ich habe Navigation Mesh Pfad von Anfang an von vorne gemacht, aber musste das Navigations-Mesh selbst nie generieren. Triangulationsalgorithmen sind neu für mich. Irgendeine Einsicht?
Da Sie keine speziellen Anforderungen für Dreiecke haben, ist ein einfacherer Ansatz wie [Polygontriangulation] (http://en.wikipedia.org/wiki/Polygon_triangulation) besser zu verwenden als Delaunay. – Ante
Ich schaute auf die Ear-Clipping-Methode, die etwas langsamer als eine Delaunay-Triangulation zu sein scheint, aber ich würde meine Scheitelpunkte in Looping-Ordnungen sortieren müssen, oder? –
Jetzt merke ich, dass du nur Kanten hast. In jedem Fall müssen Sie Kanten verbinden und ausrichten, für einen Teil finden Sie in einem anderen Teil (um zu wissen, ob es ein Loch ist oder nicht) und dann ein Polygon mit Löchern triangulieren. Löcher können entfernt werden, indem zwei gleiche Kanten von einem Loch zu einer Polygongrenze oder einem anderen Loch hinzugefügt werden. Ear Clipping ist eine einfache Methode und mit Space Partitioning (BSP-Baum, Quad-Baum, ...) ist es schneller als O (n^2). – Ante