Hi ihr,

Ich bin mal wieder am rumspielen. Ich möchte ein großes (bis zu 4ki × 4ki) Terrain erzeugen, modifizieren und, natürlich, rendern. Das Grundmodell soll aus einer beliebigen Heightmap generiert werden, danach sollen aber einige Modifikationen möglich sein, die unter anderem Klippen ermöglichen. Das Non-Plus-Ultra wäre, wenn diese *nicht* an das ursprüngliche Heightmapraster gebunden wären sondern mit einer definierten Genauigkeit auf das bestehende Mesh unter Erzeugung neuer Polygone angewandt werden könnten. Zusammengefasst:
(i) Exorbitante Vertexmenge
(ii) Nicht durchgehend (allein) durch Heightmap definierbar
(iii) Nur eingeschränkte Überlappungen. Es kann zwar Klippen geben, aber keine Überhänge.

Allein die Vertexmenge wird zu Problemen führen. Texturkoordinaten kann ich durch Shading zwar einsparen (das Terrain soll sowieso prozedural geshadet werden, das könnte man dann gleich im Shader machen), aber Normalen müssen, spätestens nach einer Modifikation irgendwo gespeichert und dann der Grafikkarte mitgegeben werden.
Klar ist, dass das ganze nicht ohne VBOs abläuft. Einen recht guten Speichermanager für VBOs inkl. Indicies habe ich bereits.

Die Modifikationen sollen ja mit einer endlichen Genauigkeit vorgenommen werden. Für das Erhöhen des Terrains müsste ich dann in der Umgebung der Erhöhung das bestehende Terrain subdividen, bis es eine bestimmte (optische) Genauigkeit für die entsprechende Anhöhe erreicht hat. Bedingung könnte da z.B. ein maximaler Unterschied zwischen zwei Flächennormalen sein.
Dann wiederum muss auch geprüft werden, ob die Veränderung des Terrains bei benachbarten Polygonen dazu geführt hat, dass der Normalenunterschied geringer ist als die Bedingung, sodass sie zusammen gefasst werden könnten und dann noch die Frage, wie.

Folgende Dinge sind für mich hier schwierig:
(a) Eine Datenstruktur finden, mit der ich schnell mit den Dreiecken arbeiten kann, also aufteilen und wieder zusammenführen, benachbarte Dreiecke finden. Gibts da was Schlaues oder sollte ich da den Dreiecken einfach nen Array mit ihren Nachbarn verpassen und damit dann rumhampeln?
(b) Inkrementelle Veränderungen, deren Stärke nicht für eine Subdivision reicht. Die Veränderungen sind Benutzerinduziert und es kann vorkommen, dass ein einzelner Schritt zu klein ist, um eine Subdivision der Polygone zu verursachen, zwei Schritte zusammenaddiert aber ausreichen. Wie könnte man das angehen? Ein Ansatz wäre, die Erhöhung zunächst auf die Vertices, die zum Polygon gehören, wo der Ansatzpunkt der Operation liegt (ich gehe mal von dem wahrscheinlichsten Fall aus, nämlich dass der Benutzer nicht genau ein Vertex trifft) und dies so lange fortzusetzen, bis die Normalenbedingung für eine Subdivision greift. Gibts da nen hübscheren Vorschlag? Ich stelle mir vor, dass das recht ruckelig oder merkwürdig aussieht.
(c) Wie bekomme ich die Geometrie in den Speicher gequetscht? Eine Idee wäre, nur eine bestimmte Menge an Terrainblöcken im Speicher zu halten und den Rest prozedural nachzugenerieren. Dazu müsste ich die initiale Heightmap (bzw deren Seed, falls sie wirklich aus dem Noise stammt) sowie alle Operationen speichern und ggf. anwenden, wenn das Terrainstück erneut gebraucht wird. Da sehe ich aber ein Problem, wenn schnell von A nach B gescrollt wird (was vorkommen kann). Allerdings käme hier LOD praktisch auf dem Präsentierteller serviert und man könnte die Darstellung des Terrains mit jedem Frame etwas genauer machen. Das ginge bei einem Terrain, wo die Änderungen fest in das Mesh gebaut werden, nicht so einfach.

So … Während dem Schreiben haben sich wie immer die Gedanken etwas sortiert, sodass ich jetzt unerwarteterweise schon die oben beschriebenen Ansätze habe. Dennoch hätte ich gern Eure Meinungen . Vorallem Zustimmung wäre sehr angenehm .

greetings

ps.: omg, ich stell mir gerade vor, was 4k × 4k × 2 Dreiecke an Speicher fressen, wenn da noch Pointer auf die Nachbarn dazu kommen … 1.610 Gigabytes (eins komma, nicht eintausend), wenn ich mich nicht verrechnet habe.

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

Was hälst du von einer Heightmap deren Vertices zusätzlich durch eine Displacementmap verschoben werden können. Die Heightmap kann den Vertex also nicht nur in der Höhe verschieben, sondern auch auf den beiden anderen Achsen. Um eine steile Klippe zu erreichen kannst du dann mit Hilfe des Displacements die Vertices entlang der Klippe zusammen bzw. übereinander schieben. Und an flachen Stellen ziehst du die Vertices auseinander damit du mehr Detail an anderen Stellen modellieren kannst. Dürfte sehr beschränkt sein, aber vielleicht reicht es ja für deine Zwecke.

Wenn du die Nachbarn eines Faces benötigst solltest du darüber nachdenken eine Halbkantenstruktur zu benutzen:
http://www.flipcode.com/archives/The_Ha ... ture.shtml
Diese ist recht Speichereffizient und lässt sich gut modifizieren. Dafür eignet sich allerdings eher weniger zum rendern.

_________________
Yeah!

Kurzes Überfliegen lässt die Halbkantenstruktur interessant klingen. Wenn ich dort Pointer auf die Indicies im VBO verwalte anstatt direkte Koordinaten, sollte das auch mit dem Rendern klappen.

Displacement: Erfordert ebenfalls Subdivision, weil sonst der Teil auf der verschobenen Seite der Klippe ungenauer wird.

greetings

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

Zwei Dinge habe ich festgestellt. Erstens: Die "Klippen" kommen sehr selten vor und in den Fällen ist es eigentlich sogar besser, die Geometrie vom Terrain zu trennen, es handelt sich eh eher um Fundamente als um Klippen. Damit ist das Terrain wieder durch eine Heightmap darstellbar.

Dann bin ich über Tutorial Terrain 3 gestolpert. Mit dem Algorithmus müsste man so ein Terrain dann doch recht gut darstellen können. Für das aktuelle Frustum holt man sich dann ein Terrainstück, welches dann durch den LOD-Algorithmus gejagt wird.

Klingt das gut, oder gibt es bessere Vorschläge?

greetings

//Edit: Jup, mit dem Terrain 3 Tutorial lässt sich auch ein 4097×4097 Punkte großes Heightfield wunderbar effizient rendern. Zumidnest wenn man die Triangulation cacht und nur bei Bedarf neu generiert. Schade, ich hab vergessen, auf die Zahl zu achten, sonst würde ich jetzt ne Vertexanzahl angeben, die er mir da so ungefähr raushaut, leider dauert es aber einige zeit, bis ein 4097×4097 Punkte großes Perlin Noise durch ist .

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb