Voxel Face Crawling (Netzvereinfachung, möglicherweise mit Gier)

9

Bearbeiten: Dies ist nur für meine eigene Lernerfahrung, es ist NICHT aus Leistungsgründen, dass ich diese Frage stelle.

Dies betrifft einen Minecraft-ähnlichen Geländemotor. Ich speichere Blöcke in Blöcken (16x256x16 Blöcke in einem Block). Wenn ich einen Block generiere, verwende ich mehrere Prozedurtechniken, um das Gelände festzulegen und Objekte zu platzieren. Während des Generierens behalte ich ein 1D-Array für den gesamten Block (fest oder nicht) und ein separates 1D-Array von festen Blöcken.

Nach der Generierung durchlaufe ich die durchgezogenen Blöcke und überprüfe ihre Nachbarn, sodass ich nur Blockflächen generiere, die keine festen Nachbarn haben. Ich speichere die zu generierenden Gesichter in einer eigenen Liste (das sind 6 Listen, eine pro möglichem Gesicht / normal). Beim Rendern eines Blocks rendere ich alle Listen im aktuellen Block der Kamera und nur die Listen, die der Kamera zugewandt sind, in allen anderen Blöcken. Dazu speichere ich alle 6 Listen in einem Puffer und ändere dann einfach die Bereiche, die ich zeichne.

Mit einem 2D-Atlas mit diesem kleinen Shader-Trick, den Andrew Russell vorgeschlagen hat, möchte ich ähnliche Gesichter vollständig zusammenführen. Das heißt, wenn sie sich in derselben Liste befinden (dieselbe Normalität), nebeneinander liegen, dieselbe Lichtstärke haben usw. Ich weiß, dass ich immer noch Rechtecke habe, aber es sollte meine Anzahl der Scheitelpunkte leicht um 50% reduzieren. oder besser, wenn meine Schätzungen korrekt sind.

Ich würde davon ausgehen, dass jede der 6 Listen nach der Achse sortiert ist, auf der sie ruhen, und dann nach den beiden anderen Achsen (die Liste für die Oberseite eines Blocks wird nach dem Y-Wert, dann nach X und dann nach Z sortiert).

Allein damit könnte ich ganz leicht Streifen von Gesichtern zusammenführen, aber ich möchte, wenn möglich, mehr als nur Streifen zusammenführen. Ich habe mich über diesen gierigen Vernetzungsalgorithmus informiert, aber ich habe große Probleme, ihn zu verstehen.

Also, meine Frage: Um das Zusammenführen von Gesichtern wie beschrieben durchzuführen (ohne zu ignorieren, ob es eine schlechte Idee für dynamisches Gelände / Beleuchtung ist), gibt es vielleicht einen Algorithmus, der einfacher zu implementieren ist? Ich würde auch sehr gerne eine Antwort akzeptieren, die mich auf viel einfachere Weise durch den gierigen Algorithmus führt (einen Link oder eine Erklärung).

Ich habe nichts gegen einen leichten Leistungsabfall, wenn es einfacher zu implementieren ist oder wenn es nur ein bisschen besser ist als nur Strips zu machen. Ich mache mir Sorgen, dass sich die meisten Algorithmen eher auf Dreiecke als auf Quads konzentrieren und einen 2D-Atlas so verwenden, wie ich bin. Ich weiß nicht, dass ich mit meinen aktuellen Fähigkeiten ein Dreieck implementieren könnte.

PS: Ich habe bereits Kegelstumpf pro Stück und wie beschrieben auch Gesichter zwischen festen Blöcken ausgesucht. Ich habe noch keine Okklusion und kann es nie tun.

* Bearbeiten: Ich habe meine eigene kleine Technik implementiert, die wahrscheinlich einen Namen hat, aber ich gehe einfach meine 6 Listen durch, die nach den Achsen sortiert sind, auf denen sie ruhen, gefolgt vom Blocktyp und dann nach Beleuchtungsstärke. Ich iteriere durch sie und erstelle neue Rechtecke, während ich sie gleichzeitig vergrößere (mit einer starken Neigung zu einer bestimmten Achse). Es ist definitiv nicht optimal, aber es ist in der Tat ziemlich schnell und senkt meine Scheitelpunktzahl im Durchschnitt um fast 50%. Der Kommentar von Byte56 ist der Schrank, den ich für eine echte Antwort halte, aber ich kann ihn nicht für die Antwort / das Kopfgeld auswählen.

Hier ist meine schnelle und vereinfachte Methode, mit der ich dieses Problem behandle, nachdem ich das gesamte ursprüngliche Terrain ohne große Optimierung generiert habe. Angenommen, alle angegebenen Quadrate sind das gleiche Bild, Lichtstärke, Normal usw. Jede Farbe ist ein anderes Quad, das ich rendern würde. Da meine Listen so sortiert sind, wie sie sind, ist dies ein sehr einfacher und schneller Ansatz.

Mythik
quelle
Nach all Ihren Optimierungen treten immer noch Leistungsprobleme auf? Haben Sie versucht, den Code zu profilieren, um festzustellen, wo die Probleme liegen?
MichaelHouse
@ Byte56 Oh, es ist momentan definitiv kein Leistungsproblem. Es kann eine in der Zukunft sein, wenn ich versuche, das, was ich lerne, für ein echtes Spiel zu verwenden. Im Moment möchte ich einfach nur lernen. Ich habe nichts davon gesagt, weil ich weniger Hilfe zu bekommen scheine, wenn ich nur Dinge lernen will, nur um sie zu lernen.
Mythics
Ich denke, ich sollte auch sagen, dass ich die sichtbare Welt RIESIG haben möchte, wenn ich tatsächlich ein richtiges Spiel damit versuche. Ich möchte nicht, dass der Charakter 2 Blöcke hoch und 1 Block breit ist, wie Minecraft und viele andere, sondern eher 3 Blöcke breit / lang und 6-9 hoch. Wahrscheinlich statisches Gelände.
Mythics
1
Ah, OK Tim. Danke für die Erklärung. Ich habe dies untersucht, als ich die Engine für mein Spiel entwickelte. Da meine Landschaft dynamisch ist, hätte ich nicht gedacht, dass es die Leistungskosten jedes Mal wert wäre, wenn etwas geändert wird. In diesem Artikel finden Sie jedoch möglicherweise eine Verwendung zum Problem des maximalen Rechtecks. Im Wesentlichen ist es der Algorithmus, über den Sie sprechen, um ähnliche Gesichter zusammenzuführen (vielleicht nicht gierig, aber optimal). Viel Glück!
MichaelHouse
@ Byte56 Danke, ich weiß das sehr zu schätzen. Das kommt der Art von Algorithmus, nach der ich suche, sicherlich näher, wenn nicht genau richtig. Ich muss ein bisschen daran basteln, um zu sehen, ob ich mit einem einzigen Durchlauf alle maximalen Rechtecke erhalten kann. Ich werde vielleicht gleich ein Kopfgeld dafür aufbringen, da ich denke, dass sowohl die Frage als auch eine detaillierte Antwort vielen anderen in Zukunft helfen könnten.
Mythics

Antworten:

4

Sie möchten nur Streifen oder bestenfalls Rechtecke machen. Es gibt keine anderen Formen, die für Sie lösbar oder nützlich sind.

Ich möchte auch darauf hinweisen, dass Sie, wenn Sie 6 Listen pro Block führen, zu jedem Zeitpunkt 5 Listen aus den Blöcken in Himmelsrichtung und mindestens 3 in jedem anderen verwenden werden. Sie verschwenden hier Zeit, wenn nicht nur die Grafikkarte diese Optimierung für Sie durchführen kann, sondern selbst wenn Sie dies selbst tun, ist es besser, alle Gesichter an einem Ort zu halten und die Normalen mit der Richtung mit der zu vergleichen Kamera (Research DOT-Produkt von Vektoren).

Die bereits gesehenen Links von CaptainRedMuff zu Greedy Meshing sind DIE Antwort auf Ihr Problem. Es sollte auch klar sein, dass Sie am Ende "gestreifte" Netze haben werden, aber diese sind vollkommen effektiv, und es wird komplizierter sein, mit etwas Optimalerem zu kommen, und Sie haben zum Ausdruck gebracht, dass das gierige Netz bereits zu kompliziert ist.

Wenn Sie Leistungsprobleme mit einem einzelnen Block haben, denke ich, dass etwas anderes sehr falsch ist.

Meine erste Vermutung wäre, dass Sie eine Ziehoperation viel zu oft aufrufen. Sie können die Grafikkarte nur anweisen, je nach Hardware zwischen 50 und 400 Mal pro Sekunde zu zeichnen. Wie viele Aufrufe von .setData oder .draw ____ Primitives tätigen Sie?

Phil
quelle
Rechtecke sind was ich will. Byte56 hat einen Algorithmus verknüpft, der viel einfacher zu befolgen ist als gierig, aber ich kann einen Kommentar nicht als Antwort akzeptieren. Ich nahm an, dass er stattdessen kommentierte, weil er nur mit einem Algorithmus verknüpft war, anstatt ihn zu erklären. Ich weiß nicht, was du mit meinen Listen meinst. Ich habe normalerweise 1-2 Draw Calls pro Chunk. Meine Listen werden in einem Puffer pro Block gespeichert. Ich ändere, welche Bereiche pro Frame gezeichnet werden sollen. Ich könnte mich irren, aber das Senden unnötiger Daten an die GPU scheint kontraproduktiv. Ein oder zwei zusätzliche Ziehungen pro Block scheinen besser zu sein, als mehr Daten an die GPU zu senden und sie zu zwingen, auch zu töten.
Mythics
Ich habe keine Leistungsprobleme. Ich genieße es einfach, diese Dinge zu lernen. Ich werde meine Frage bearbeiten, um dies zu sagen, aber wie ich auch Byte56 gesagt habe, bekomme ich weniger Hilfe, wenn das, was ich versuche, nicht wirklich ein Problem löst. Um Ihre Frage zu beantworten, rendere ich derzeit höchstens 200-260 Chunks pro Frame. Das sind ziemlich häufige 500ish DrawIndexedPrimitives pro Frame. Ich bekomme regelmäßig 100-130 FPS ohne vsync, was 65.000 Anrufe pro Sekunde macht. Ich versuche nicht unhöflich zu sein, aber wenig, was du gesagt hast, macht für mich Sinn. Ich kann nicht verstehen, also bitte näher erläutern, wenn ich falsch verstanden habe. Vielleicht hat es mit XNA zu tun?
Mythics
Ah, sorry, ich wollte pro Bild sagen, nicht pro Sekunde. Sie nähern sich dort einer Obergrenze, und wenn Sie sich nur im Gelände befinden, sind Sie ziemlich erschöpft.
Phil
Ich habe Ihre Antwort gegeben, da ich mir ein paar Verbesserungen überlegt habe, die ich machen könnte, aber nichts mit der Frage zu tun hat. Außerdem dachte ich, ich sollte eine Antwort von Nathan Reed über den möglichen Link zum
teilen
Ich muss den Artikel finden, den ich gelesen habe und der 400-500 als Limit zitiert. Ein schneller Google hat mir nicht geholfen.
Phil
0

Der Artikel, auf den Sie verlinken, enthält keinen Algorithmus zum Generieren des Netzes. Es gibt einen Weg an, mögliche Lösungen zu bewerten.

Im Allgemeinen gibt der Artikel jedoch eine gute Zusammenfassung: 1) Die naive Lösung ist schlecht, 2) Es gibt eine optimale Lösung, aber das Schreiben und Ausführen ist zeitaufwändig. 3) Ein schnelles Keulen führt zu viel besseren Ergebnissen ( und das ist alles, was Minecraft selbst tut), und schließlich 4) könnte es eine intelligentere Lösung geben (den gierigen Algorithmus).

Die "Lösung", die Sie in dem Bild in Ihrer Frage implizieren, ist der gierige Algorithmus. Ihre Frage scheint zu lauten: "Habe ich seine Lösung korrekt implementiert?" worauf ich antworten muss "er hat keine lösung gegeben; du hast das nur selbst gelöst."

Kann Ihre Lösung besser sein? Meh. Sicher. Wahrscheinlich nicht wert. Ich denke, Okklusions-Culling oder LOD wären die nächsten Schritte besser. Minecraft verschwendet eine gute Anzahl von Zyklen, um die Oberfläche zu zeichnen, selbst wenn Sie sich im Untergrund befinden, und um riesige Netzwerke von Höhlen- und Minensystemen zu zeichnen, wenn Sie sich an der Oberfläche befinden. Sobald Sie eine gute Netzaufteilung haben, kann es eine gute Sache sein, verdeckte Oberflächen zu entfernen - aber (z. B.) ist es im Allgemeinen schneller, Ihre Grafikkarte Backface-Culling durchführen zu lassen, als dies auf der CPU zu tun.

AndrewS
quelle