Erstellen eines Octree für die Geländegenerierung

9

Ich habe zuvor Marschwürfel / Tetraeder implementiert, um eine IsoSurface zu rendern. Es hat funktioniert ( YouTube ), aber die Leistung war schlecht, da ich nie dazu gekommen bin, eine variable Detailebene basierend auf der Sichtweite zu implementieren (oder sogar alte, entfernte Teile zu entfernen).

Ich beschloss, es noch einmal richtig zu machen. Ich habe damit begonnen, einen OctreeNode zu erstellen, der beim Aufruf wie folgt funktioniert Build().

  • Wenn der Block zu klein zum Bauen ist, kehren Sie sofort zurück.
  • Berechnen Sie, ob die Oberfläche das Volumen dieses Blocks durchläuft.
  • Wenn ja, dann entscheiden Sie, ob wir die LOD erhöhen möchten (weil die Kamera in der Nähe ist).
  • Wenn ja, dann spawne 8 Kinder und rufe den gleichen Prozess auf
  • Wenn nicht, erstellen Sie das Netz anhand der Abmessungen des aktuellen Knotens

Einige PseudoCode:

OctNode Build() {
    if(this.ChunkSize < minChunkSize) {
        return null;
    }
    densityRange = densitySource¹.GetDensityRange(this.bounds);
    if(densityRange.min < surface < densityRange.max) {
        if(loDProvider.DesiredLod(bounds > currentLoD) {
            for(i 1 to 8) {
                if(children[i] == null) {
                    children[i] = new OctNode(...)
                }
                children[i] = children[i].Build();
            }
        } else {
            BuildMesh();
        }
        return this;
    }
}

¹ Die Dichtequelle kann nicht nur die Dichte an einem Punkt zurückgeben, sondern auch den möglichen Dichtebereich für ein bestimmtes Volumen bestimmen.

² Der LoD-Anbieter nimmt einen Begrenzungsrahmen und gibt den maximal gewünschten LoD basierend auf Kameraposition / Kegelstumpf, Benutzereinstellungen usw. zurück.

Also ... das alles funktioniert ziemlich gut. Verwenden einer einfachen Kugel als Dichtequelle und Anzeigen aller Knoten:

Voller Octree

Und nur die Blätter:

Octree zeigt nur Blätter

Es gibt jedoch einige Probleme:

  • Ich muss das anfängliche Begrenzungsvolumen definieren (und je größer es ist, desto mehr Verarbeitung muss ich durchführen)
  • An der Wurzel des Baumes habe ich keine Ahnung, wie tief die Blätter sein werden, daher beginnt meine LoD-Nummerierung bei der niedrigsten Qualität (Wurzel) und nimmt zu, wenn die Brocken kleiner werden. Da LoD jetzt relativ zum Anfangsvolumen ist, ist es nicht sehr nützlich, wenn ich Dinge mit bestimmten Größen / Qualitäten tun möchte.

Ich habe über ein paar Optionen nachgedacht, aber beide scheinen fehlerhaft zu sein:

  • Pflegen Sie eine Sammlung von Octrees und fügen Sie sie je nach Entfernung hinzu oder entfernen Sie sie. Ich kann nicht sehen, wie ich gut ineinander greifen würde¹, und ich benötige eine Liste mit bekannten leeren Knoten, insbesondere wenn ich beliebige 3D-Oberflächen möchte (um zu vermeiden, dass leere Volumina wiederholt neu berechnet werden).
  • Fügen Sie dem aktuellen Stamm einen übergeordneten Knoten hinzu, und fügen Sie dann sieben Geschwister für den ursprünglichen Knoten hinzu. Dies würde funktionieren und auf Abruf erfolgen, aber es scheint komplex, sich vernünftig zurückzuziehen, wenn sich der Spieler durch die Landschaft bewegt. Dies würde auch die LoD-Zahlen noch weniger aussagekräftig machen.

¹ [Zur Verdeutlichung von Q unten] Wenn sich derzeit zwei physisch benachbarte Knoten im Baum an verschiedenen LODs befinden, habe ich einen Code, um die Verts so zu erzwingen, dass beim Generieren der Netze keine Naht entsteht. Ich kann dies tun, indem ich die Dichte für mehrere umgebende Knoten kenne. In einem Szenario, in dem ich zwei unabhängige Oktrees nebeneinander habe, hätte ich keine einfache Möglichkeit, diese Informationen abzurufen, was zu Nähten führt.

Was ist ein optimaler Weg, um dies zu erreichen?

Basic
quelle

Antworten:

1

Ich bin mir nicht sicher, ob ich die genaue Frage beantworte, daher werde ich in Segmenten antworten und kann gerne in Kommentaren antworten, wenn ein Missverständnis über die Einzelheiten einer bestimmten Frage vorliegt.

Ich muss das anfängliche Begrenzungsvolumen definieren (und je größer es ist, desto mehr Verarbeitung muss ich durchführen)

Dies scheint nicht der Fall zu sein. Da die Granularität des Octrees exponentiell zunimmt, sollte das Hinzufügen einiger Ebenen oben eine sehr geringe Nettoerhöhung des Leistungseinbruchs bedeuten.

An der Wurzel des Baumes habe ich keine Ahnung, wie tief die Blätter sein werden, daher beginnt meine LoD-Nummerierung bei der niedrigsten Qualität (Wurzel) und nimmt zu, wenn die Brocken kleiner werden. Da LoD jetzt relativ zum Anfangsvolumen ist, ist es nicht sehr nützlich, wenn ich Dinge mit bestimmten Größen / Qualitäten tun möchte.

Wenn Sie Ihren Root-Octree auf einen "ausreichend großen Wert" festlegen, sollte "LoD relativ zum ursprünglichen Volume" kein Problem darstellen. Und wie oben erwähnt, denke ich nicht, dass ein zusätzliches Level an der Spitze die Gesamtleistung beeinflusst.

Pflegen Sie eine Sammlung von Octrees und fügen Sie sie je nach Entfernung hinzu oder entfernen Sie sie. Ich kann nicht sehen, wie ich gut ineinander greifen würde, und ich benötige eine Liste mit bekannten leeren Knoten, insbesondere wenn ich beliebige 3D-Oberflächen möchte (um zu vermeiden, dass leere Volumina wiederholt neu berechnet werden).

Nach meinem Verständnis geht es bei dieser vorgeschlagenen Lösung darum, die LoD zu senken, wenn Sie sich von einem zuvor detaillierten Bereich entfernen. Ich denke, es sollte dem Codepfad "Zunehmender LoD" sehr ähnlich sehen:

if (loDProvider.DesiredLod(bounds) <(is a lot less than)< currentLoD) { 
    for(i = 1 to 8) { 
        children[i].Destroy();
    }
    BuildMesh();
}

Dann verbringen Sie nicht zu viel Zeit damit, entfernte Knoten zu überprüfen, da Sie sich darauf verlassen können, dass es in der Ferne nicht zu viele "aktive" Knoten gibt, da alle Knoten mit höherer Auflösung entfernt wurden.


Angenommen, kleine Knoten sind im Felsmaßstab, würde dies möglicherweise Dutzende, wenn nicht Hunderte von Ebenen bedeuten, wenn ich über einen Kontinent reise

Ich denke, die logarithmische Skala des Octree macht es noch machbar. Wenn Ihre oberste Ebene 1.000.0000.000 m breit ist (dies wäre 25-mal breiter als die reale Erde und mit der 625-fachen Oberfläche) und Ihre Bits der niedrigsten Ebene einen Durchmesser von 10 cm haben, sind das wahrscheinlich 32 Ebenen im Octree überschaubar genug. Wenn Sie einen Planeten haben möchten, der 100-mal breiter als die Erde ist (und 10000-mal mehr Oberfläche hat), sind das nur zusätzliche 3-4 Ebenen in Ihrem Octree. Zu diesem Zeitpunkt würde ein Spieler Hunderte von Jahren brauchen, um die Welt zu bereisen, und wenn Sie naive Gleitkomma-Mathematik verwenden, wird die Welt Präzisionsfehler ansammeln.

Pflegen Sie eine Sammlung von Octrees und fügen Sie sie je nach Entfernung hinzu oder entfernen Sie sie. Ich kann nicht sehen, wie ich gut ineinander greifen würde¹, und ich benötige eine Liste mit bekannten leeren Knoten, insbesondere wenn ich beliebige 3D-Oberflächen möchte (um zu vermeiden, dass leere Volumina wiederholt neu berechnet werden).

Ist das nicht im Grunde gleichbedeutend mit dem milliardenkilnen Oktree, aber einer Liste von Zeigern auf jeden Block von beispielsweise 1 km? Dann würde sich "Vernetzen" einfach auf die 2 km großen Knoten verlassen. Wenn Sie einen lokalen Verweis auf jeden "großen Block" der mittleren Ebene beibehalten, müssen Sie auch nicht durch die Knoten der obersten Ebene iterieren, wenn Sie sich Sorgen über die "möglicherweise Dutzende zusätzlicher Octree-Ebenen" machen.

Jimmy
quelle
Danke für die Antwort. Ich kann nicht einfach ein massives Anfangsvolumen auswählen, da mein Gelände unendlich ist (das ist mein Ziel). Sehen Sie sich das Video an, um sich ein Bild zu machen. Als solches würde mein Knotenbaum immer höher werden. Angenommen, kleine Knoten sind im Felsmaßstab, würde dies möglicherweise Dutzende, wenn nicht Hunderte von Ebenen bedeuten, wenn ich über einen Kontinent reise. Betreff: Vernetzen, lassen Sie mich der Frage [Fertig]
Basic
Für den Spieler ist "eine Milliarde Meilen" ziemlich nahe an "unendlich". Weitere Argumente für ein festes Anfangsvolumen wurden zur Antwort hinzugefügt.
Jimmy
Ich bin immer noch nicht überzeugt. Warum mehr als 30 Schichten bekanntermaßen nutzloser Verarbeitung? Es ist nicht elegant, geschweige denn effizient. Ich nehme Ihren Standpunkt zur Zeit zum Überqueren, aber wir sprechen einfach über die Geländegenerierung. Nichts, was besagt, dass ich mich am Ursprung zentrieren muss, noch dass es unmöglich ist, mit hoher Geschwindigkeit zu fliegen (obwohl ich mit dieser Geschwindigkeit nicht ineinander greifen würde!). FWIW Ich verwende intern Doppel, um dieses Präzisionsproblem zu vermeiden.
Basic