Unterteilung von Höhenfeldern

[Niki]

Hallo Leute,

bei mir steht nun das Terrain-Rendering auf dem Plan. Damit meine ich nicht Bäume, Büsche, und Grashalme, sondern lediglich Höhenfelder mit einfachem Tetxure-Splatting. Dieses Thema ist auch für mich nichts neues, allerdings war das Grundprinzip meiner früheren Implementierungen anders als das was ich jetzt haben möchte. Was ich diesmal tun möchte ist folgendes:

Ich habe ein großes Höhenfeld, zum Beispiel 4096x4096. Dieses Höhenfeld möchte ich in Planquadrate unterteilen, wobei jedes Planquadrat eine Heightmap-Textur hat. Als Beispiel sollen diese Heightmap-Texturen 1024x1024 Pixel groß sein. Insgesamt wären das also 16 Planquadrate und somit 16 Heightmap-Texturen. Jedes Planquadrat soll nun mit 32x32 Patches gerendert werden. Zu diesem Zweck bastele ich mir einen Vertex- und einen Index-Buffer der die Geometrie eines Patches enthält. Mittels Geometry-Instancing rendere ich dann die sichtbaren Patches. Ich möchte dies ohne LOD versuchen, und den Hardware-Tesselator möchte ich wegen Kollisionsabfragen nicht verwenden.

Wie unten beschrieben, geht die obige Rechnung leider nicht auf und mein Ziel ist es nun eine möglichst elegante, oder halt akzeptable Lösung zu finden. Eure Ideen und Erfahrungen wären mir dabei sehr hilfreich. Hier das Problem:

Wo sich zwei benachbarte Planquadrate treffen dürfen keine "Höhensprünge" entstehen, sondern das ganze muss nahtlos sein. Zu diesem Zweck könnte jedes Planquadrat die südlichsten Höhen des nördlichen Nachbarplanquadrates und die östlichsten Höhen des westlichen Nachbarplanquadrates duplizieren. Somit wäre nun jede Heightmap-Textur 1025x1025 und nicht mehr 1024x1024.
Und nun kommen die 32x32 Patches ins Spiel. Da sich zwei benachbarte Patches immer eine Zeile/Spalte teilen müssten die Planquadrate 1023x1023 und nicht 1024x1024 oder 1025x1025 groß sein. Das alles passt also nicht so richtig zusammen.
Es gilt hierfür eine akzeptable Lösung zu finden. Eine wäre die Welt in 1023x1023 Planquadrate zu unterteilen. Dadurch schneide ich etwas an den Rändern der 4096x4096 großen Welt ab, was nicht so schlimm wäre da es sich nur um wenige Spalten und Zeilen handelt. Allerdings haben die Heightmap-Texturen dann keine Zweierpotenz-Größen mehr, und ich bin mir nicht sicher ob das mittlerweile egal ist (mit DX11 Grafikkarte)

Ich gebe zu das mein Deutsch für einen Deutschen recht schlecht ist, aber ich hoffe das ihr mir trotzdem folgen konntet. Ich freue mich über jede Anregung die ihr zu bieten habt.

-- Niki

[dot]

Wieso müssen die Planquadrate auf separate Dateien aufgeteilt werden?

[Niki]

Ich glaube ich habe mich da wohl gewaltig verrechnet... wenn ich das richtig sehe dann lassen sich 1024x1024 Heightmap-Texturen mit 32x32 Patches perfekt rendern. Mann, bin ich im Moment verwirrt...

[Niki]

Wieso müssen die Planquadrate auf separate Dateien aufgeteilt werden?

Ja, das Aufteilen in separate Dateien ist mein Ziel. Bitte beachte, dass die Größenangabe 4096x4096 nur ein Beispiel ist. Es kann unter Umständen noch viel grösser werden. Die tatsächliche Größe wird von meinem Empfinden über die Auflösung des Terrains abhängen. Ist halt alles relativ... 4096x4096 kann verdammt klein sein, oder kann Skyrim-groß sein.

[dot]

Dennoch bleibt meine Frage: Wieso aufteilen? Das macht imo alles nur unnötig kompliziert...

[Niki]

Deine Frage gibt mir gerade echt zu denken. Eine einzige Textur würde vieles vereinfachen, wie zum Beispiel das Berechnen von Vertex-Normalen im Shader. Aber aus irgendeinem Grund klingeln da bei mir die Alarmglocken. Was wenn dieses Monstrum von Textur 1-2 mal pro Frame in den Videospeicher geschaufelt wird? (1-2 mal, weil ich Deferred Shading mit einem extra Depth-only Pass habe). Das Terrain ist ja nicht alles was ich rendere.

Aber ich bin ja nicht fixiert. Und deshalb ist das Verwenden einer riesigen Textur keineswegs ausgeschlossen. Vielleicht können Du und die anderen mir ja meine Ängste vor solchen Texturen nehmen.

[Schrompf]

Die Textur wird doch nur einmalig am Anfang in den VideoRAM geschaufelt, und dann wieder bei jeder Änderung. Aber wenn ich Dich richtig verstanden habe, ist die Textur statisch. Demzufolge ist Deine Furcht unbegründet.

Außerdem: wenn Du das Texturmonstrum in viele kleine Teile zerteilst, ist die Summe der Kleinteile doch wieder genauso groß...

[dot]

Naja, ich dachte vor allem an das Erstellen der Heightmap. Wenn du aus technischen Gründen die Daten am Ende dann in deiner Software aufteilst, ist das was anderes. Aber nun stellt sich mir eine weitere Frage: Wieso musst du die Heightmap im VertexShader lesen und die Normalen dort berechnen?

[Niki]

@Schrompf:
Die Textur ist während des Spielens statisch. Allerdings gibt es gewisse Editier-Möglichkeiten zur Entwicklung, wodurch ein Neu-Upload der Textur passieren würde. Das sollte aber okay sein, da die Editier-Funktionen ja nicht mit X FPS laufen müssen, und das meiste sowieso in Tools wie Photoshop gemacht wird. Aber es ist ja auch nicht nur die Heightmap-Textur. Dazu kommen noch die Opacity-Maps für die Materialen. Das summiert sich ganz schön. Und an der Stelle muss ich fragen: Was passiert denn heutzutage wenn der Videospeicher voll ist? Texture-Swapping wie früher?

Du hast recht, dass die Summe der Kleinteile genauso groß ist. Allerdings sind nur wenige der Kleinteile auf einmal sichtbar.

Immer weiter her mit Euren Meinungen :) Ihr habt mich schon zu über 50% überzeut den Ansatz einer Monster-Textur zu implementieren (und notfalls später zu entfernen wenn's doch Probleme geben sollte).

[Schrompf]

Tja... wenn Du wirklich mit so vielen Daten hantierst, dass Du erwartest, dass sie nicht mehr in den VideoRAM passen, dann solltest Du in der Tat in Segmente aufteilen und selbst pagen. Du kannst das auch Windows überlassen, das macht auch keinen schlechten Job, aber ich vermute, Dir geht bei großen Datenmengen bald der Adressraum aus. Du wirst wahrscheinlichen nur eine 32Bit-Anwendung schreiben.

Abgesehen davon kannst Du aber einfach nur ausrechnen, wie groß Deine Daten sind. Einmal 4Byte für die HeightMap und z.b. 2x 4Byte Alpha Map macht 12Byte pro Höhenpixel, bei einer 4096er HeightMap also 192MB. Das ist ziemlich wenig für ein Hobby-Spiel, dass nur auf PC laufen soll. Und die AlphaMaps sollten sich notfalls auch gut komprimieren lassen.

Wenn Du segmentierst, kommst Du um eine überlappende Segmentierung nicht drumrum. Du brauchst ja nicht nur für die Normalenberechnung die umliegenden Texel, sondern auch für evtl. LODs später. Ich würde also ein 1024er Segment mit mindestens vier Zeilen / Spalten in jede Richtung umgeben. Die Nicht-Mehr-Zweierpotenz-Größe stört keine Grafikkarte der letzten 10 Jahre mehr. Dann kannst Du selbst pagen, und das solltest Du auch. Du kannst zwar höchstwahrscheinlich keinen besseren Job als das Paging des Treibers oder von Windows machen, aber Du hast die Kontextinformationen, die das Betriebssystem nicht hat. Du weißt, welche Segmente demnächst in Sicht sein könnten, und kannst vorauseilend parallel laden und portionsweise hochladen, um Aussetzer in der Bildrate zu vermeiden.

[Niki]

Naja, ich dachte vor allem an das Erstellen der Heightmap. Wenn du aus technischen Gründen die Daten am Ende dann in deiner Software aufteilst, ist das was anderes. Aber nun stellt sich mir eine weitere Frage: Wieso musst du die Heightmap im VertexShader lesen und die Normalen dort berechnen?

Die Heightmap wird als ein großes Bild erstellt. Mit einer Mischung aus Tools wie Photoshop und/oder GeoControl. Das Resultat wollte ich dann in Planquadrate splitten, und in einer Art In-game Editor sehr beschränkte Anpassungs-Möglichkeiten geben (nur für Entwickler, nicht für Spieler... für den Spieler ist die gesamte Heightmap statisch).

Was die Normalen anbelangt, so kann man die natürlich auch in Texturen packen. Und genau das würde ich tun wenn ich in Planquadrate aufteile. Wenn ich nun aber eine Monster-Textur nehmen sollte, dann ist es ja einfach die Normalen im Vertex-Shader zu berechnen. Gerade während der anfänglichen Research-Phase finde ich das bequemer, weil die Normalen dann korrekt bleiben wenn ich mit dem Grid-Spacing oder der vertikalen Skalierung herumspiele.

[Niki]

@Schrompf:
Da hast Du genau den Punkt getroffen der mir Sorgen macht... die Datenmengen. Ich wünschte ich könnte diese abschätzen, kann's aber nicht. Klar kann ich die Datenmengen für das Heightfield selbst abschätzen. Aber einfach nur Heightfield ohne was drauf macht ja auch keinen Spaß :) Da kommen dann Büsche, Gras, Bäume, Brücken, Häuser und so weiter. Meine Bedenken sind das ich mich später mit der Qualität zurückhalten muss weil ich am Anfang zu viel mit Speicher geaast habe.
Wenn ich mich recht erinnere dann hast Du schon so'n Riesending programmiert. Die Splitterwelten sind doch von Dir? Welchen Weg hast Du gewählt, und hat dieser Weg Dir später Probleme bereitet (wg. Speicherverbrauch)?

[dot]

Nun, ohne weitere Information über die genaue Anwendung, würde ich es wohl so machen: Höhendaten für den angenehmen Umgang in einer großen Datei ablegen. Die zugrundeliegende Datenstruktur besteht aber aus einzelnen Kacheln. Erst wenn Kacheln benötigt werden (potentiell gerade sichtbar, Spieler bewegt sich in diese Richtung etc.), werden diese geladen. Wenn du Direct3D 11 verwendest, pack die Daten der Kacheln in Texturen, zeichne das Terrain per Bufferless Draw nur mit Index Buffer und generier die Vertices dynamisch im VertexShader. Wenn du OpenGL verwendest, schau ob deine OpenGL Version Bufferless Draw unterstützt (bin mir grad net sich ob das in irgendeiner Spec schon supported wird) und mach das gleiche wie gerade eben für D3D11 vorgeschlagen. Ansonsten erzeug für jede Kachel ein statisches VBO und fertig. Das wär zumindest mal mein initialer Ansatz. Wie gut oder schlecht das in der jeweiligen Anwendung dann tatsächlich funktioniert, steht natürlich auf einem anderen Blatt...

[Schrompf]

Was hast Du denn vor? Du machst Du nur ein Hobby-Projekt? Dann bau doch das, auf das Du Bock hast und bei dem Du am schnellsten Ergebnisse siehst. Hör auf, Dir Gedanken zu machen über Probleme, die Du evtl. in zwei Jahren bekommen wirst. Bis dahin hat die durchschnittliche Grafikkarte nochmal das Doppelte an RAM.

Bei den Splitterwelten nutze ich einen großen frei formbaren Mesh. Der wird dann in Segment-Kaskaden unterteilt und mittels Alpha Splatting mit Materialen besetzt. Die Segmente werden semi-lokal detailreduziert, wobei darauf geachtet wird, dass die Kanten zu den Nachbar-Segmenten symmetrisch geloddet werden. Die Segmente ziehen pro Kaskade ihre Daten aus Dateien, die nochmal gecached werden.

Das alles ist ein ziemlich komplexes Ding, dass zu seiner Entstehungszeit um 2004 auch seinen Sinn hatte. Heutzutage würde ich den ganzen Mesh in eine Datei hauen, im Gesamten in den Speicher laden, und wahrscheinlich auch in viel größere Segmente unterteilen. Außerdem würde ich einen Deferred Renderer dafür nutzen. Und ich würde eine Menge der internen Indirektionen knicken, um die Prozesse sinnvoll parallelisieren zu können. Wahrscheinlich würde ich auch den Gesamt-Mesh-Ansatz im Ganzen wegwerfen und eine Oberflächen-Generierung aus Volumen wie z.B. Marching Cubes probieren, weil die automatische Detailreduktion für dieses Mesh-Monster so abartige Bugs hervorgebracht hat, dass ich das mit dem heutigen Wissen nicht mehr probieren wollen würde.

Naja... nicht ganz. Heutzutage würde ich unbedingt mal einen Giga-Voxel-Ansatz erproben wollen. Eine ganzheitliche Landschafts-Erstellung, wenn man das so nennen will. Das wäre allerdings wieder ein abartiger Schwung an Tools zu programmieren, ganz zu schweigen von vielen Detailproblemen bei der Mesh-Generierung mit LODs und allem... das ist ein Ding, wenn ich mal ein halbes Jahr arbeitslos bin.

[edit] Ich würde Dir aber für praktisch alle Belange von Height Maps abraten. Die sind einfach langweilig, damit kriegt man kein sinnvolles Terrain hin. Einzig für RTS-Spiele oder ähnlich "distanziertes" Geschehen sind HeightMaps gerade noch so akzeptabel, wenn man sie mit einem riesigen Haufen Aufsteck-Models ergänzt.

[Niki]

@dot
Vielen Dank für Deine Hinweise. Die Benutzung von Bufferless Draw scheint mir eine gute Idee zu sein. D3D11 ist noch relativ neu für mich weshalb mir diese Technik noch nicht bewusst war. In den letzten 10 Jahren war ich beruflich nur mit der Softwareentwicklung für mobile Geräte beschäftigt, während PC Entwicklungen zu einem privaten Vergnügen wurden. Auch wenn ich davor praktisch nur PC Software entwickelt habe, so habe ich nun doch einiges an Wissen nachzuholen.

@Schrompf
Ich sehe schon Du hast einen völlig anderen Ansatz in Splitterwelten. Macht ja auch Sinn, wenn Du in der Tat "Splitter" hast die nicht ein zusammenhängendes Teil bilden. Ich kenne halt nur die Demo und konnte deshalb nicht abschätzen was außerhalb der Demo noch existiert.

Was das "Hobby-Projekt" anbelangt so muss ich da ein wenig korrigieren. Momentan handelt es sich tatsächlich noch um ein Hobby-Projekt. Ich weiß aber auch das mein Brötchengeber mich ab einem gewissen Punkt unterstützen wird (wenn ich mich dazu entscheide). Wir wissen ja beide, dass man so ein Projekt kaum alleine durchziehen kann. Ich kann nicht Programmierer, Grafiker, Musiker, Storywriter und Level-Designer in einer Person sein. Und jetzt stell Dir mal vor, wenn später ein Grafiker-Team dazukommt und die Unmengen an vermeidbaren Einschränkungen ausgesetzt sind. Deshalb mache ich mir all diese Gedanken im voraus, damit ich später auch mit gutem Gewissen sagen kann "So Leute, jetzt könnt Ihr einsteigen!".

@Alle
Nach all der Info in diesem Thread bin ich nun tatsächlich zu dem Schluss gekommen, dass ich segmentieren werde. Mit Bufferless Draw und überlappenden Segmenten. Danke Schrompf, dass Du die Sache mit dem 4-pixel Rand in alle Richtungen erwähnt hast. Etwas in dieser Art werde ich tun. Es ist nämlich so, dass ich zu diesem Zeitpunkt noch nicht sicher bin ob ich ohne LOD auskomme. Weniger wegen der Performance, sondern eher wegen der Z-Buffer-Auflösung in der Distanz.

[dot]

Mach dir nix draus, Bufferless Draw ist, wenngleich ungemein toll, wohl eines der weniger bis kaum bekannten Features von D3D11... ;)

Edit: LOD sollte sich mit der Technik, denk ich, ganz gut umsetzen lassen, braucht nur einen anderen Index Buffer für den jeweiligen LOD und los gehts. Tessellation ist da aber wohl natürlich eine Sache, die man sich zumindest überlegen sollte...

[Niki]

Meinst Du Hardware Tessellation? Das wäre ja so schön, weil so herrlich einfach. Nur weiß ich leider nicht wie ich das Kollisionsproblem lösen soll. In meinem Falle sieht der Spieler die Welt durch eine First-Person Kamera. Da kann man mit einer bilinearen Interpolation von Höhen ja noch tricksen. Aber da sollen auch noch NPCs und Monster rumlaufen. Für die muss ich die Terrainhöhe unter den Füssen ermitteln. Und wenn da plötzlich eine krasse Steigung ist, dann ist es nicht mehr egal ob ein Quad / oder \ in Dreiecke unterteilt wird. Ich mag definitiv keine NPCs die oben auf'm Berg in der Luft schweben oder halb im Boden versinken :)
Aber wer weiß... vielleicht ist's ja wieder nur mangelndes Wissen meinerseits. Weißt Du eine Lösung für das Problem? Für mich wäre Hardware Tessellation dann die ultimative Lösung.

EDIT: Ich habe da eine Idee die hinhauen könnte. Je höher die Auflösung der Heightmap, desto weniger weicht eine bilinear interpolierte Höhe von dem ab was der Tessellator rendert (unter der Voraussetzung das der Tessellator auch mindestens dieselbe Auflösung nimmt). Wenn ich nun die Heightmap in der niedrigen Auflösung lasse, aber im Tessellator extra Höhen bilinear interpolieren, dann sollte ich doch in der Lage sein eine interpolierte Kollisionshöhe aus der Heightmap zu nutzen?! Klar ist das nicht 100% genau, könnte aber genau genug sein. Was denkt Ihr?

[dot]

Für die Kollision sollten doch auf jeden Fall die Höhendaten ausreichen, oder? Aber rein prinzpiell wirst du die Physik ja wohl auf der CPU rechnen und brauchst entsprechende Daten also sowieso nochmal irgendwo im RAM...

[Niki]

Da hast du mich falsch verstanden. Ich versuch's mal etwas visueller. Zeichne ein Quadrat auf ein Blatt Papier und benenne die Ecken mit A, B, C, und D. Dieses Quadrat stellt ein einzelnes Quad aus dem Terrain dar (zwei zusammengehörige Dreiecke). A, B, C, und D haben je eine Höhe aus der Heightmap. Nimm als Beispiel A=0, B=0, C=0, und D=100. Du hast zwei Möglichkeiten das Quad in zwei Dreiecke zu unterteilen:

Fall 1: Hypotenuse geht von A nach C
Fall 2: Hypotenuse geht von B nach D

Jetzt möchtest du die Höhe in der Mitte des Quads wissen. Für Fall 1 ist diese Höhe 0, aber für Fall 2 ist sie 50. Das ist ein großer Unterschied, und je größer die Quads auf dem Bildschirm erscheinen desto stärker fällt dieser Unterschied auf (NPCs schweben über dem Boden oder versinken darin). Ob der Tessellator nun Fall 1 oder Fall 2 nimmt, das weiß nur der Tessellator, nicht aber die CPU die versucht die Höhen immer mit Fall 1 zu berechnen.

Je kleiner die Quads nun auf dem Bildschirm werden desto weniger sollten diese Fehler optisch auffallen. Deshalb die Idee das sowohl die Hull/Domain-Shader als auch die CPU neue Höhen mittels irgendeiner Interpolation hinzufügen. Dadurch sollte der Fehler geringer und optisch akzeptabler werden. So hoffe ich jedenfalls...

[dot]

Das ist mir schon klar, was mir nicht klar ist, ist inwiefern das für die Kollisionsabfrage relevant ist!?

[Niki]

Das ist mir schon klar, was mir nicht klar ist, ist inwiefern das für die Kollisionsabfrage relevant ist!?

Du renderst einen NPC so das die Füße des NPCs in der Mitte des Quads auf dem Boden stehen. Die CPU nimmt Fall 1 und bestimmt "Ok, die Füße stehen an Höhe 0". Der Tessellator entscheidet sich aber nun evtl. für Fall 2, womit die Füße an Höhe 50 sein sollten. Sind sie aber nicht. Die Füße sind bei Höhe 0 und damit verschwindet ein Teil des NPCs optisch im Boden.

[dot]

Naja, der einzige Weg um das richtig hinzubekommen, ist eben auf der CPU die gleiche Interpolation durchzuführen, wie du sie auf der GPU bei der Tessellation anwendest... ;)

[Niki]

Naja, der einzige Weg um das richtig hinzubekommen, ist eben auf der CPU die gleiche Interpolation durchzuführen, wie du sie auf der GPU bei der Tessellation anwendest... ;)

Bingo! Zwar kann ich meines Wissens nach der GPU nicht sagen "Nimm immer Fall 1, wie die CPU auch", aber durch das Hinzufügen neuer interpolierter Höhen (die auch nicht in Heightmap-Textur existieren) sollte ich hoffentlich in der Lage sein das Problem auf ein akzeptables Maß zu reduzieren. Diese Interpolation wird dann von CPU und GPU durchgeführt. Von der CPU für die Kollision und von der GPU für's visuelle. Mit etwas Glück haut das ganze vielleicht auch für Hardware LOD noch relativ gut hin. Na, ja, da gibt's halt viel zu probieren, aber glücklicherweise habe ich für das Terrain recht viel Zeit eingeplant :)

[dot]

Wenn du Tessellation verwenden willst, kannst du das der GPU sogar ganz genau sagen, da du den entsprechenden Shader (DomainShader) sowieso selber schreiben musst... ;)

[Niki]

Im ernst? :o Wie? Da muss ich wohl irgendwas falsch machen?! Bei mir mischt der Tessellator Fall 1 und Fall 2.

EDIT: Beispiel Image hochgeladen. Hoffe das funzt. Selten das man bei einem Forum was hochladen kann. In dem Bild ist das gesamt Terrain nur ein einziger Patch. Die Fälle wechseln also innerhalb des Patches.

[dot]

Achso, sry, da hatte ich was falsch verstanden, das kannst du natürlich nicht beeinflussen. Die Frage ist allerdings, ob das auch wirklich so ein Problem ist...

[Niki]

Achso, sry, da hatte ich was falsch verstanden, das kannst du natürlich nicht beeinflussen. Die Frage ist allerdings, ob das auch wirklich so ein Problem ist...

Ich fürchte ja :( Zumindest ist das ein wirklich hässliches Problem wenn du ein low-res 4096x4096 Höhenfeld auf ein riesiges Spielfeld anwendest. Du hast dann halt große Quads und NPCs die optisch durch Bergränder durchlaufen oder darüber hinweg schweben. Deswegen will ich ja versuchen die Auflösung künstlich zu erhöhen ohne die Gesamt-Heightmap zu vergrößern. Ich hoffe es klappt so wie ich es mir vorstelle.