Mir geistert schon seit ca. einer Woche eine Idee für Terraindarstellung mit Vertex- und Fragmentshadern im Kopf herum, die ich irgendwann auch in ein konkretes Projekt umsetzen möchte.
Wie auch immer, die Idee (ob sie wirklich neu ist, weiß ich natürlich nicht) ist Folgende und setzt GLSL voraus, mit dem man auch im Vertexshader Texturen auslesen kann:

Das Terrain besteht aus quadratischen Vertexpatches, mit Zweierpotenzen als Seitenlänge und wird über eine Textur generiert. Die Vertexpatches werden nicht direkt gezeichnet, vielmehr handelt es sich um 2D-Vertices, deren x- und y Komponente nichts anderes als der Index des jeweiligen Texels ist, die x- und y Komponenten gehen also immer von 0 bis 1.
Zum Zeitpunkt der Darstellung wird die Transformationsmatrix so eingestellt, dass die Vertexdaten auf den richtigen Wertebereich transformiert werden, den z-Wert holt man sich über die untransformierten x- und y- Komponenten aus der Textur - vor der tatsächlichen ModelView Transformation ist dann auch der richtige Zeitpunkt weitere Daten (höhenabhängige Farbe, Detailtextur, pseudozufällige Werte) zu generieren, die man eventuell im Fragmentshader später braucht.

Der Clou ist nun folgender: aufgrund der Tatsache, dass jedes Patch genau die selben Daten enthält, genügt es wenn man genau ein Patch in einer Displayliste oder einem statischen (sehr schnellen) VBO ablegt, und immer wieder zeichnet - durch die übergebenen Parameter holt sich der Shader dann selbständig die "richtigen" Daten aus der Textur - und es kommt noch besser - LOD ist ebenfalls ganz einfach zu implementieren:
Für jede LOD Stufe legt man sich ebenso eine Displayliste des LOD-Patches an (es sind dann weniger Vertices, die X- und Y-Komponenten liegen dann halt entsprechend weiter auseinander), und fertig ist die Geschichte. Um unschöne Sprünge zwischen LOD-Stufen zu vermeiden, kann man für jede LOD Stufe 16 Versionen erstellen, bei denen jeweils eine beliebige Kombination von Rändern in der Auflösung der jeweils niedrigeren Stufe vorliegt.

Zur Laufzeit entscheidet man sich dann aufgrund der Distanz des Patches zum Viewer für eine LOD-Stufe, wählt auf Grund der Detailstufe der Ränder benachbarter Patches eine der 16 Unterversionen, schickt die entsprechende Displayliste an OpenGL und fertig ist das Ganze.

Meiner Ansicht nach müsste das Ganze sehr performant sein - und das Nachladen von Heightmapdaten beschränkt sich auf das Nachladen der entsprechenden Texturen (keine Nachbearbeitung notwendig).
Die Patches müssen nur ein einziges mal berechnet werden und bleiben dann immer gleich - als Startpatch würde ich eine Ausdehnung von 128x128 Schnittpunkten in eine 1024x1024 Textur vorschlagen (pro Textur werden also 8x8 Patches gerendert), wenn man vier TMUs mit Texturen a' 1024x1024 befüllt, kann man sogar dynamisch über ein quasi unendliches Terrain wandern, da die Texturen dynamisch in die jeweiligen TMUs geladen werden können. Kein Problem, da man auf Karten, die über GLSL verfügen ohnehin genügend TMUs zur Verfügung haben sollte (wenn man zuerst das Terrain und dann Objekte rendert, kann man sie danach ja für andere Zwecke verwenden).

Die selbe Methode für Terrain mit LOD würde natürlich auch funktionieren, wenn man die Höhendaten nicht aus Texturen nimmt, sondern diese im Vertexshader selbst berechnet, als Grundlage würden einfach die X- und Y- Komponenten der Vertices dienen, die in statischen Patches (wie oben beschrieben) vorliegen und somit extrem schnell an die Grafikkarte gesendet werden (oder von Vorneherein im Videospeicher liegen).

Theoretisch müsste es im Fragmentshader sogar möglich sein, das Terrain auf sich selbst Schatten werfen zu lassen - auf die Höhendaten kann ja zugegriffen werden, wenn die Lichtposition übergeben wurde, muss man nur schauen, ob zwischen Lichtquelle und dem gezeichneten Pixel (dessen 3D-Position ja auch bekannt ist) ein Hindernis liegt - das gilt dann natürlich auch für später gezeichnete Objekte.

(Eventuell könnte man auch erst alles ohne Schatten rendern, den Depth Buffer in eine Textur bringen und dann ein bildschirmfüllendes Rechteck zeichnen, bei dem ein Fragmentshader aufgrund der x- und y- Werte des Fragments, sowie der Tiefe im Depth Buffer eine 3D-Koordinate generiert und dann über die Höhendatentextur entscheidet, ob diese nun im Schatten liegt oder nicht - ob das pratikabel ist, bin ich nicht sicher, da es davon abhängt, ob man die Tiefendaten performant in eine Textur bringt oder nicht).

Eine Frage ist natürlich auch, ob man mit gut aussehenden Terrains überhaupt noch jemand vom Hocker haut - schließlich sind die Grafikkarten recht schnell geworden - wenn man allerdings berücksichtigt, dass es mit dieser Methode auch für riesige Landschaften kaum Nachladezeiten gibt, und der Verwaltungsoverhead sehr klein ist (das LOD wird ja quasi im Voraus berechnet) könnte sie schon interessant sein.

_________________
Viel Spaß beim Programmieren,
Mars
http://www.basegraph.com/

Ähm, ich glaube schon, deiner Argumentierung folgen zu können, aber was ist denn der Unterschied zu "traditionellem" Heightmapping? Du verschiebst ja praktisch nur das Auslesen der Höhendaten vom Initalisieren in den Shader, oder hab ich da was übersehen?
Außerdem ist mir aufgefallen, dass bei den verschiedenen LOD-Stufen ja nach Löcher prodizert werden, die man natürlich eliminieren müsste.

_________________
"Du musst ein Schwein sein in dieser Welt, sangen die Prinzen, das ist so 1.0. Du musst auf YouTube zeigen, dass dir dein Schweinsein gefällt, das ist leuchtendes, echtes Web 2.0."
- Hal Faber
Meine Homepage: http://laboda.delphigl.com

Denke mal das Problem wird die Geschwindigkeit sein, denn das Auslesen einer Vertex Texture benötigt 20 Takte und dann kommt ja noch der Rest des Shaders hinzu der davon abhängt. Dann müssen ja noch die Normalen usw.. berechnet werden.
Anstelle das Displacement in einer Texture zu speichern, kann man es ja auch in einem separaten Buffer ablegen. Die Vertex Arrays kann man ja fast beliebig kombinieren.
Raytracing zur Schattenberechnung gibt's beim Relief Mapping auch - neuerding auch in Doom3. Nur das da das Displacement per Pixel und nicht per Vertex ist.

Ja, das ist prinzipiell richtig - allerdings geht die Übergabe der Vertexdaten somit sehr schnell, da diese eben nicht dynamisch nachgeladen (oder gar generiert) werden müssen - das CPU-lastige Berechnen eines CLODs entfällt. Es ist allerdings im Grunde ein ganz normaler Heightmapalgorithmus, bei dem aber, aufgrund der der Funkionalität des Vertexshaders, fast alles vorberechnet werden kann - da dies aber nicht nur für Heightmaps funktioniert, sondern auch für funktionsbasierte Terraindarstellungen, habe ich auch das Thema entsprechend benannt.


Nein - jede LOD Stufe liegt ja in 16 Versionen vor, bei welchen jede Kombination der Ränder (4^2=16) in der jeweils übergeordneten (also höher aufgelösten) LOD Stufe gezeichnet wird. Bei der Auswahl der Displayliste (oder des VBOs) für das Patch orientiert man sich dann an den LOD Stufen der benachbarten Patches (zwei benachbarte Patches liegen ja sinnvollerweise maximal eine LOD-Stufe auseinander) ist noch kein Patch benachbart, schaut man, dass der entsprechende Rand in der niedrigeren Detailstufe (an der man ja interessiert ist) gezeichnet wird - das benachbarte Patch wird sich dann mit dieser Methode automatisch anpassen - es entstehen also keine Löcher.
Elegant ist IMHO übrigens auch, dass die geometrischen Primitive, aus denen die Patches bestehen dem Vertexshader völlig egal sind (am geeignetsten sind wahrscheinlich Trianglestrips, evtl. -fans) - auch die Erstellungsdauer ist nicht wichtig, da sie ohnehin in eine Displayliste oder ein VBO kompiliert werden. Wer keine abrupten Sprünge zwischen LOD Stufen haben möchte, kann die Patches also auch langsam an der entsprechenden Seite in die höhere Detailstufe übergehen lassen, z.B. von der Mitte ausgehend, anstelle einfach die letzte Dreiecksreihe höher aufgelöst zu zeichnen.

_________________
Viel Spaß beim Programmieren,
Mars
http://www.basegraph.com/

Stimmt, im Endeffekt hilft wahrscheinlich ohnehin nur Ausprobieren


Jein - die könnte man ja auch in einer Normal Map speichern (um TMUs zu sparen könnte man auch RGBA Texturen verwenden, bei denen der Höhenwert im Alphakanal, die Normale in den RGB Werten steckt)


dann funktioniert leider die Vorausberechnung des LODs nicht mehr, das Schöne war ja gerade, dass man mit den X- und Y- Komponenten des Vertex auf eine Textur wie in ein zweidimensionales Array zugreifen kann. Meines Wissens kann man im Vertexshader nicht eine Komponente eines Schnittpunktes als Index in eine andere Schnittpunkttabelle verwenden - ich lasse mich aber gerne korrigieren.


In diesem Fall ist es auch nur "halb" per Vertex, da ja Dreiecke zwischen den Höhendaten interpoliert werden, die Schattenberechnung aber direkt auf die Höhendaten zugreift - in diesem Fall ist auch nicht eine verfeinerte Detaildarstellung wichtig (die wäre natürlich auch interessant) sondern überhaupt die Möglichkeit in Echtzeit Schatten passend zu der erzeugten Geometrie darzustellen, ohne aber zusätzliche Dreiecke ins Spiel bringen zu müssen.

_________________
Viel Spaß beim Programmieren,
Mars
http://www.basegraph.com/

Ich kenn mich mit Shadern zwar nur sehr wenig aus (um nicht zu sagen: Gar nicht), aber euer Problem kommt mir bekannt vor...

Vor ein paar Tagen hab ich im Netz eine nette Seite gefunden, die ein Programm namens xvox beschrieb. In diesem Programm wurde eine Landschaft mit Adaptive Degradation gerendert, die ihre Daten aus einem Shader bezog. Ich weiß nicht, ob es das ist, was ihr sucht, die Landschaft schaut aber in jedem Fall sehr schön und auch sehr groß aus...

http://users.belgacom.net/xvox/

_________________
"Für kein Tier wird so viel gearbeitet wie für die Katz'."

So wie ich das verstehe, funktioniert das ähnlich - es werden ebenfalls LOD-Muster für Patches an die Grafikkarte gesandt, die dann über "Vertex Streams" an die Grafikkarte gesandt werden - die Textur wird dann auch im Shader ausgelesen.
Ich habe mir vorgenommen, so ich neben Arbeit, Privatleben und Spellforce noch Zeit dafür finde, ein entsprechendes Demo zu schreiben - nachdem ich mir jetzt extra um ein Heidengeld ein Notebook gekauft habe, mit dem man auch grafisch anspruchsvolle Sachen machen kann, will das ja auch genutzt werden.

_________________
Viel Spaß beim Programmieren,
Mars
http://www.basegraph.com/

Die Demo ist schon etwas älter und so wie ich das gesehen habe, nutzen die den Shader nur um jeweils zwei Detailstufen abhängig von der Entfernung ineinander zu blenden und so einen weichen Übergang ohne hohe CPU Kosten zu haben.

Ein an sich niedrig aufgelöstes Heightfield könnte man versuchen durch Cosinus Interpolation (z.B. hier beschrieben http://freespace.virgin.net/hugo.elias/models/m_perlin.htm) im Shader glatt darzustellen. Das hätte dann einen ähnlichen Effekt, wie die klassischen OpenGL Evaluatoren, ist aber sehr viel leichter implementierbar und schneller (Bin grad am ausprobieren, wie das aussieht, zur Zeit allerdings ohne Shader)
Die anzahl der Samples zwischen zwei Höhenkoordinaten könnte man wieder von der Entfernung abhängig machen - das LOD würde genau gleich funktionieren wie oben beschrieben, nur dass die Höhe aus den Texturdaten bei bedarf interpoliert wird.

Das Heightfield unten besteht in Wirklichkeit aus 5x5 floats, der Rest der Schnittpunkte wird interpoliert - das Ganze lässt sich auch problemlos in einem Vertexshader machen. Ein Problem ist die Normalenberechnung, wahrscheinlich bleibt nichts anderes übrig, als zu jedem Schnittpunkt drei Punkte mit hinreichend geringem Abstand, verschoben jeweils auf x und z Achse zu generieren und von dem resultierenden Dreieck die Flächennormale zu berechnen - aber sogar dies sollte hinreichend schnell gehen.

Weiters ist mir noch aufgefallen, dass man langsam aufpassen muss, wo man optimiert: selbst wenn ich ein großes Heightfield (8192 * 8192) rendere, macht es überhaupt keinen Unterschied, ob für jedes Quad (alle sind sichtbar) ein Frustum Test (Sphere) aufgerufen wird oder nicht, weil das Rendern zig- mal mehr Zeit braucht, als der vergleichsweise primitive Test - wenn man dann noch bedenkt, dass durch die dynamische Interpolation ein Heightfield kaum mehr größer als (sagen wir) 512 x 512 sein muss (und dennoch eine riesige Map darstellen kann), fragt sich wirklich, ob eine hierarchische Datenstruktur wie ein Quadtree überhaupt notwendig ist, oder ob es nicht geschickter ist einfach für jeden Bereich zwischen Höhenwerten direkt einen Frustum Test aufzurufen, weil die 260000 Tests pro Frame ohnehin keinen Unterschied machen...

_________________
Viel Spaß beim Programmieren,
Mars
http://www.basegraph.com/