Große gitterartige Meshes effizient rendern

[mOfl]

Hallo liebe Leute!

Vielleicht hat einer von euch eine gute Lösung oder zumindest Idee für ein Problem, das mich momentan plagt. Im Prinzip geht es darum, ein Heightfield möglichst schnell in OpenGL zu rendern. An sich nicht gerade spannend, die Sache wird erst interessant, wenn das Heightfield riesig wird. Ich habe zum Beispiel ein Terrain aus Laserscandaten über 10x10 km mit einem Meter Auflösung und lasse darauf eine Simulation laufen, die mir ein zweites Heightfield erzeugt, das ich ebenfalls anzeigen will.

Was ich momentan mache:
Für jeden Gitterpunkt einen Punkt, also GL_POINT, rendern, im Geometry Shader daraus eine Gitterzelle (2 Dreiecke mit 4 Vertices als Triangle Strip) erzeugen, die Normalen an den vier Ecken der Zelle aus dem Heightfield berechnen und das dann shaden. Das mache ich für jedes Heightfield in jedem Frame, was den Vorteil hat, dass ich außer dem Heightfield selbst (pro Datenpunkt ein float, bei 10x10 km knapp 400 MB) nichts im Speicher halten muss. Der Nachteil ist, dass ich statische Daten beständig neu berechne anstatt sie zwischenzuspeichern. Das Heightfield des Terrains ändert sich dabei aber zur Laufzeit nur sehr selten, das der Simulation hingegen häufig. Nicht in jedem Frame, aber ist im Grunde schon dynamisch. Die Performance des Ganzen liegt in dem Beispiel mit ungefähr 200 Millionen Dreiecken bei etwa 80 ms allein für die beiden Heightfields.

Eine theoretische Alternative wäre, den Geometry Shader nur einmal auszuführen und die berechneten Daten über Transform Feedback in einen Buffer zu schreiben, den ich dann verwende. Praktisch muss ich dafür aber dann - da Transform Feedback jedes Primitiv getrennt schreibt - pro Zelle 6 Positionen (je 3 floats) und 6 Normalen (nochmal je 3 floats) rausschreiben für den Shading Pass, was bei Weitem keinen Platz im Speicher hat.

Da insbesondere bei dem Heightfield der Simulation die exakte Darstellung der Daten wichtig ist, kann ich die Heightfields auch nicht großartig in einem vorhergehenden Schritt vereinfachen oder verändern. Bei der Größe der Daten scheidet ein Processing auf der CPU ohnehin aus, irgendwelches Streaming/Out-of-Core-Rendering auch. Im allgemeinen Fall ist auch immer das gesamte Heightfield zu sehen, also irgendwelches Culling auf der GPU scheidet auch aus.

Was ich also bräuchte, ist eine Methode, ein großes Heightfield so zu rendern, dass die Geometrie nicht (vollständig) im Videospeicher liegen muss. Die Methode soll offensichtlich schneller sein als das, was ich jetzt mache, nämlich pro Zelle zwei Dreiecke im Geometry Shader zu basteln. Wie schnell, weiß ich selbst nicht genau, da 80 ms für 200 Millionen Dreiecke an sich schon nicht verkehrt sind, aber die Interaktivität des Renderings leidet doch merklich. Das Schöne ist, dass es dafür keinerlei Constraints in Sachen Hardwarekompatibilität gibt. Wenn es also ein schon unterstütztes OpenGL-4.5-Feature gibt, das nur auf Maxwell läuft, aber genau auf meine Anwendung passt, ist das kein Problem. Und wenn euch nur eine Lösung für DirectX einfällt, wär das auch schon was.

Ich bin sicher nicht der erste hier, der Heightfields rendert, und ihr habt euch sicherlich schon länger den Kopf darüber zerbrochen als ich. Ich bitte also um Vorschläge, Erfahrungen, Anmerkungen, Geldspenden, … . Wie rendert ihr die Terrains in euren Engines? Wie würdet ihr sie rendern, wenn ihr keine LoD-Informationen hättet? Jede Antwort ist willkommen! Danke schon im Voraus!

Gruß
mOfl

[Spiele Programmierer]

Warum setzt du keine LOD Techniken ein? Ein FullHD Bildschirm hat ungefähr 2 Millionen Pixel. 200 Millionen Polygone können dort also ohnehin nicht gleichzeitig dargestellt werden und es liegt nahe, die Datenmenge durch ein LOD System zu reduzieren. Ich würde zuerst das versuchen, das scheint mir der einzig richtige Weg.

Wenn du einen speziellen Anwendungsfall hast, könnte man vielleicht auch versuchen, die gewaltige Datenmenge von der anderen Seite anzupacken und anstatt sporadisch einzelne Pixel mit "Dreiecken" zu füllen, für jeden Pixel (in einem Fragment Shader) einen Punkt in der Datenmenge suchen und im Prinzip Raytracing betreiben.

Ich mache das bei meinen Terrain so:
Ich habe mein Terrain in 256² Blöcken organisiert. Ich speichere nur die Höhe und nicht die X, Z Koordinate eines Punktes um Speicherplatz/Bandbreite zu sparen, die X, Z Koordinaten berechne ich dynamisch aus der Position des Blocks und der VertexID. Geometry Shader verwende ich für die normale Oberfläche keinen, stattdessen setze ich einen Index Buffer ein, der ein Triangle Strip über alle Vertices beschreibt. LOD realisiere ich einfach, in dem ich den Index Buffer austausche. Ich verwende dabei aber einen einzigen Index Buffer für alle Blöcke des Terrains, denn die Reihenfolge der Vertices ist in den Blöcken überall gleich. Das Triangle Strip im Index Buffer habe ich Schlangenartig ausgelegt, um den Post Transform Cache wirken zu lassen. Die Normalen berechne ich im voraus, aber direkt auf der GPU. Dafür nehme ich einfach ein simples Framebuffer Object das in eine Textur rendert. Die kann ich dann auch bei anderer LOD-Stufe verwenden und exakte Normalen genießen. Ohne LOD und Versionsbeschränkungen könnte man auch versuchen das mit dem Compute Shader in einem gewöhnlichen Vertexbuffer zu erledigen.

[Schrompf]

Sowas in der Richtung hätte ich auch vorgeschlagen. Also a) bei 200 Millionen Dreiecken ist jede aktuelle Grafikkarte langsam. Also lodden. Und b) warum nicht ein hübsch indizierter und vertexcache-optimierter Mesh, der z.b. 256x256 Gitterzellen darstellt. Dann musst Du im VertexShader nur noch pro Vertex die Höhe ausrechnen, musst also keine Geometrie mehr im VertexShader erzeugen. Und Du könntest für a) das Lodden auch die Gitterzellen mal doppelt so groß zeichnen und aus der ersten MipMap-Stufe der HeightMap lesen.

Außerdem: I demand pictures!

[mOfl]

Vielen Dank erst mal für eure Antworten! Da ihr beide das blockweise Rendering angesprochen habt, dachte ich, ich probier das mal aus. Nach der ersten rudimentären Implementierung ist das Rendering schon grob doppelt so schnell - ist ja auch logisch, es fällt ja beinahe die Hälfte aller Vertextransformationen weg. Kam mir irgendwie nicht in den Sinn, das mal zu testen … Gut, dass ich gefragt hab! Ich werde jetzt mal ein wenig mit unterschiedlichen Blockgrößen und Indexlayouts experimentieren, da ist sicher noch mehr drin.

Den Vorschlag zum Ray Tracing fand ich übrigens auch interessant. Durch die Regelmäßigkeit des Gitters kann man einige Schnittberechnungen stark vereinfachen, habe auch mehrere Papers dazu gefunden. Wäre auf jeden Fall auch ein Ansatz, aber da Ray Tracing im Allgemeinen dann wieder zu ganz anderen Problemen führt (Sampling/Aliasing z. B.), bleib ich erst mal beim Rasterizer.

Für euch beide scheint das kein Problem zu sein, dass ich das Heightfield mit einem LoD-Algorithmus rendere. Anscheinend übersehe ich hier was, weil ich habe keine richtige Idee, wie ich das angehen sollte. Wie gesagt, die Daten sind zu groß, um Vorberechnungen auf der CPU zu machen, und auf der GPU lohnt sich das auch nur für statische Daten. Von dem Heightfield z. B. jedes Mal eine Mipmap berechnen, wenn sich was geändert hat, kostet mich sicher mehr als alles naiv zu rendern. Zudem kann ich auch nicht wirklich mit gemittelten Werten arbeiten, weil dann an irgendeinem Punkt das Rendering falsch ist, z. B. dass Wasser der Simulation auf einmal in Bereichen gerendert wird, wo es eigentlich gar nicht direkt ist, sondern nur dicht drum herum. Aber prinzipiell klingt eine view-dependent LoD-Geschichte schon sinnvoll.

[Spiele Programmierer]

Wie können Daten zu groß sein, um keine Vorberechnungen auf der CPU machen zu können? Man kann doch immer Vorberechnungen auf der CPU machen, wenn die Daten ohnehin von der CPU kommen. Mit den Mip Maps sollte es sich auch anders verhalten: Momentan betrachtest du jeden Datenpunkt in jedem Frame, machst diverse Berechnungen und zeichnest ein Dreieck. Da wäre es auf jeden Fall schneller einmal alle Datenpunkte anzuschauen, einmal zu verrechnen und dann immer in jedem Frame die vereinfachten Daten zugreifen zu können.

Eventuell wäre es selbst besser, wenn es ein paar Sekunden dauert, wenn das Terrain geladen wird, anstatt dann die ganze Zeit eine niedrige rucklige Framerate zu haben. Das muss natürlich du wissen und das kommt auch ganz darauf an, wie häufig sich wie viel vom Terrain ändert. Aber einige LOD Methoden für Terrains kommen mit sehr wenig Vorberechnungen aus. Bei mir hat es sogar zu ausreicht, das Terrain gar nicht zu bearbeiten, sondern einfach bloß das Dreiecksnetz weniger eng über die selben Daten zu spannen. Man kann natürlich auch andere Dinge probieren, wie zum Beispiel in dem man die Datenwerte mittelt. Das mit dem Wasser mag kritisch klingen, ist es aber vielleicht in der Praxis gar nicht so schlimm. Wir reden hier schließlich von Flächen letztendlich in der Größe von wenigen Pixeln. Normalerweise sollte das kaum auffallen oder ist gar nicht sichtbar.

[Schrompf]

View-dependant LOD ist ja irgendwie das Einzige, womit man wirklichen Datenmassen Herr werden kann :-) Jede Engine mit größeren Datenmengen macht das. Und Du könntest dadurch evtl. sogar Bildqualität gewinnen, weil Du ja aktuell statistisch betrachtet 200 Dreiecke pro Pixel renderst, was auf Distanz ein übelster Pixelkrieg sein dürfte. Ein LOD, was auch nur halbwegs die Dreieckdichte auf 1 pro Bildschirmpixel runterbringt und dabei sinnvoll antialiased, würde da schon einen gewaltigen Fortschritt erbringen.

Und ich denke, Du kannst das ganz einfach machen. Du musst ja nur das Grid doppelt so groß skalieren und die Height Samples dann entsprechend weiter auseinander setzen. Die Benutzung der MipMap, um kostenlos 4:1 Samples zusammengefasst zu bekommen, musst Du natürlich nicht nutzen - evtl. kann es sich bei Deiner Speicherknappheit tatsächlich lohnen, im VertexShader 4 Samples statt einem zu nehmen und das MipMapping quasi "live" zu betreiben. Oder halt einfach das Aliasing in Kauf zu nehmen und immer einzeln aus der primären MipMap zu lesen. Dann gewinnst Du zwar keine Bildqualität wie oben beschrieben, aber zumindest massive Performance.

Wenn Du das Grid wiederverwendest, solltest Du evtl. auch im VertexShader einen "Rand-LOD-Faktor" mitgeben, mit dem Du angibst, ob an dieser Seite des Quadrats die nächste LOD-Stufe anschließt. Dann brauchst Du im VertexShader am Rand jeden zweiten Vertex auf seinen Nachbarn abbilden und bekommst so erstmal eine billige Methode, die Lücken zwischen den LOD-Stufen zu schließen.

Und wenn das alles dann geht, kannst Du Dir ja überlegen, die Texturen dynamischer zu nutzen. Wenn Du weißt, dass Du in der Entfernung eh nur kleinere MipMap-Stufen samplest, brauchst Du die großen gar nicht erst hochzuladen und sparst Dir wiederrum massiv VideoRAM. Dann sind war aber schon bei Streaming-Lösungen, wie sie Google Earth und so einsetzen dürften.

Ich würde da gern dran rumspielen. Ich finde das ein spannendes Thema. Hab leider eh schon viel zu viel zu tun.

[mOfl]

So, nochmal vielen Dank für eure Antworten!

Wie können Daten zu groß sein, um keine Vorberechnungen auf der CPU machen zu können? Man kann doch immer Vorberechnungen auf der CPU machen, wenn die Daten ohnehin von der CPU kommen. Mit den Mip Maps sollte es sich auch anders verhalten: Momentan betrachtest du jeden Datenpunkt in jedem Frame, machst diverse Berechnungen und zeichnest ein Dreieck. Da wäre es auf jeden Fall schneller einmal alle Datenpunkte anzuschauen, einmal zu verrechnen und dann immer in jedem Frame die vereinfachten Daten zugreifen zu können.

Die Daten sind ziemlich groß, heißt so in der Größenordnung von 500 MB. Das traversiert man nicht mal eben in Echtzeit pro Frame oder für jeden 5. Frame (wann immer sich halt in den dynamischen Heightfields was ändert) auf der CPU, um irgendeine hierarchische Struktur dafür zu basteln. Die Daten kommen übrigens auch nicht von der CPU, sondern direkt von CUDA und werden nur je nach Speicherplatz gecachet und geswapt. Also ein dynamisches Heightfield ist je nachdem, was grad gefordert wird (z. B. Änderung des Heightfields über Zeit als Animation), vielleicht nur einen Frame lang gültig und wird dann verworfen. Pausiert man die Animation dann, wird das Heightfield zu diesem Zeitpunkt statisch und solche Berechnungen würden eventuell Sinn machen. Im Allgemeinen kann man aber die Vorberechnungen nicht immer machen. Es hilft vermutlich, wenn ich dynamische und statische Heightfields getrennt betrachte, obwohl die Repräsentation dafür die gleiche ist und auch das Rendering im Prinzip das gleiche. Aber beim Terrain könnte man tatsächlich mehr optimieren als bei Simulationsergebnissen.

Sagt, habt ihr irgendeine Referenz für einen guten LoD-Algorithmus für Heightfields? Woran es bei mir hapert, ist die Entscheidung, welcher LoD in einer Zelle zu verwenden ist. Kann man das mit textureQueryLod o. ä. im Shader machen? Ich hatte mal was mit adaptiver Tessellation für ein fraktales Terrain gemacht, aber das schon so lange her … Obwohl man bei view-dependent LoD ja dann wieder ein Problem mit den T-Junctions bekommt, und ob man die einfach vermeiden kann, ohne nochmal richtig viele Informationen (lies: ein Flag pro Zelle) im VRAM zu halten? Weil wenn ich das richtig verstehe, hätte Schrompf ja so was vorgeschlagen.

Zu guter Letzt ist das natürlich auch alles dadurch ein wirkliches Problem, weil meine Anwendung momentan und bis auf Weiteres kein Texturstreaming kann. Eine komplette Pipeline für Virtual Texturing mit Prediction und allem in ein bestehendes System bauen ist schon ein großer Aufwand. Für so was war bisher nie Zeit und auch bis jetzt kein Bedarf, es hat immer locker alles in den Videospeicher gepasst.

[mOfl]

Sagt, habt ihr irgendeine Referenz für einen guten LoD-Algorithmus für Heightfields? Woran es bei mir hapert, ist die Entscheidung, welcher LoD in einer Zelle zu verwenden ist. Kann man das mit textureQueryLod o. ä. im Shader machen?

Ich beantworte das mal selber für mich und die Nachwelt: Nvidia hat genau dafür eine Demo, die die LoD-Berechnung im Tessellation Control Shader macht anhand der Kantenlänge eines Primitivs im Screen Space. Mal schauen, wie weit ich damit komm, das sieht relativ vollständig aus.