Prozedural erzeugte 3D-Welten

OpenGL: Landschaftsgestaltung mit Height Maps & Co.
Kommentare

Endlose Weiten in Flugsimulationen, urbane Kriegsgebiete, Insel-, Dschungel- und Wüstengebiete, Minecraft-Landschaften und Planetenoberflächen – die Erschaffung von virtuellen Welten ist facettenreich und eine Herausforderung für jeden Spieleentwickler. Im Fokus des folgenden Beitrags stehen prozedural erzeugte Landschaften und ihre Darstellung mithilfe von Height Maps, Texture-Array- und Texture-Buffer-Objekten.

Die Spezies des Spieleprogrammierers gilt als neugierig, kreativ und ist bestrebt, stets Neues auszuprobieren, um die eigenen Fähigkeiten kontinuierlich weiterzuentwickeln. So ist es denn auch nicht verwunderlich, wenn der Anblick einer malerischen Insellandschaft oder der virtuelle Flug über eine in Echtzeit prozedural generierte Planetenoberfläche zu einem Kribbeln in den Fingerspitzen führt und man versucht ist, ein solches Szenario selbst einmal im Rahmen eines Prototyps zu implementieren. Also, legen wir los!

Technik im Wandel der Zeiten

Als erster großer Meilenstein bei der Darstellung von weitläufigen Landschaften gilt die Präsentation des so genannten ROAM-Algorithmus (Realtime Optimally Adapting Mesh) im Jahr 1997. Im Unterschied zu herkömmlichen 3-D-Modellen wird das Terrain hierbei nicht in Form eines statischen Vertex-Gitters im Grafikspeicher gehalten; stattdessen werden alle benötigten Vertex-Daten in Echtzeit berechnet, wobei der Detailgrad (die Auflösung) des Terrains mit zunehmendem Kameraabstand kontinuierlich reduziert wird. Da jedoch dieses als Triangulierung bekannte Verfahren von der CPU durchgeführt wurde und alle berechneten Daten im Anschluss daran zur Grafikkarte transferiert werden mussten, gilt der ROAM-Algorithmus heutzutage als vollkommen ineffizient.

Mit zunehmender Verbreitung von DirectX-9-fähigen Grafikkarten in den Jahren 2002 und 2003 wurde die CPU für Durchführung von Grafikberechnungen praktisch bedeutungslos. Neue Verfahren waren gefragt, bei denen die immer leistungsfähiger werdenden GPUs ihre Stärken voll ausspielen konnten. Während sich zumindest kleinere Terrains mittlerweile dank des großzügig dimensionierten Grafikspeichers ohne aufwändige Triangulierungs-Berechnungen in Form eines einzelnen regulären Vertex-Gitters (Uniform Grid) rendern lassen, kommen bei weitläufigen Landschaften für die Darstellung der sichtbaren Terrain-Bereiche kleine Vertex-Gitter – so genannte Terrain Tiles bzw. Kacheln – zum Einsatz. Im Rahmen dieser Verfahren erfolgt die Darstellung des Terrains in unmittelbarer Nähe zur Kamera mit dem maximal möglichen Detailgrad, wobei dieser mit zunehmendem Kameraabstand schrittweise reduziert wird. Ein weithin bekannter und häufig genutzter Vertreter dieser Technik ist der im Jahr 2004 von Losasso und Hoppe vorgestellte Geometry-Clipmap-Algorithmus.

Moderne Render-Techniken bei der Terrain-Darstellung

Das Prinzip, abwechslungsreiche Spielewelten mithilfe von schachbrettartig aneinandergereihten Tiles (Kacheln) darzustellen, ist nicht neu. Bereits in den 90er Jahren des letzten Jahrtausends kam diese Technik in bis heute unvergesslichen Spieleklassikern wie Command & Conquer, Diabolo oder Starcraft zum Einsatz. Moderne 3-D-Beschleuniger ermöglichen es, eine Vielzahl dieser Kacheln auf effiziente Weise in Form von texturierten Vertexquads (bestehend aus vier Vertices, die zusammen zwei rechtwinklige Dreiecke bilden) darzustellen. Noch vor wenigen Jahren hätte man die einzelnen sichtbaren Tiles nacheinander rendern müssen, was jedoch alles andere als performant ist, da dies mit unzähligen Draw Calls (beispielsweise würde die Darstellung von 1000 Tiles 1000 Render-Aufrufe erfordern!!!) und Texturwechseln einhergehen würde. Mit Einführung der Texture-Array-Objekte im Rahmen der OpenGL-Spezifikation 3.0 gehört das Problem der vielen Texturwechsel jedoch der Vergangenheit an, da sich nun vor Beginn des Render-Vorgangs alle für die Darstellung des Spielfelds relevanten Texturen als Texture Array an ein Shader-Programm übergeben lassen und die Auswahl zu verwendender Texturen aus diesem Array innerhalb des Shaders erfolgt. Dank einer weiteren mit OpenGL 3.1 eingeführten Rendering-Technik, dem Texture-Buffer-basierten Geometry Instancing, ist es zudem möglich, alle sichtbaren Tiles beziehungsweise das komplette Spielfeld mit einem einzigen Draw Call darzustellen.
Den kombinierten Einsatz von Texture-Array-Objekten in Verbindung mit Texture Buffer Instancing können Sie anhand des TerrainRenderingDemonstrations-Programmbeispiels (Bin/DemoConfig.txt, TerrainRenderTechnique: 0) nachvollziehen. Die in diesem Zusammenhang zum Einsatz kommenden Shader-Programme sind in den Listings 1 und 2 skizziert.

// Transformationsmatrix:
uniform mat4 matViewProjection;

// Texture Buffer mit allen Tile-Positionen und Texturindices:
uniform samplerBuffer TerrainPosAndTextureIDBuffer;

uniform float TileScale;

void main()
{
  vec4 Vertex = vec4(TileScale*gs_Vertex.x, TileScale*gs_Vertex.y, TileScale*gs_Vertex.z, gs_Vertex.w);
  
  // Texturindex sowie die Tile-Position in der Spielewelt
  // aus dem TerrainPosAndTextureIDBuffer auslesen:
  vec4 TerrainPosAndTextureID = texelFetch(TerrainPosAndTextureIDBuffer, gl_InstanceID);
  
  // Terrain Tile in der Spielewelt relativ zur Kamera positionieren:
  Vertex.xyz += TerrainPosAndTextureID.xyz;
  
  // Texturkoordinaten und Texturindex an den Fragment Shader übergeben:
  gs_TexCoord[0].stp = vec3(gs_MultiTexCoord0.st, TerrainPosAndTextureID.w);
  
  gl_Position = matViewProjection*Vertex;
}
uniform sampler2DArray SurfaceTextureArray;

void main()
{
  vec4 SurfaceColor = texture(SurfaceTextureArray, gs_TexCoord[0].stp);
  gs_FragColor = SurfaceColor;
}

Neben der offensichtlichen Tatsache, dass sich mithilfe der in den Listings 1 und 2 beschriebenen Techniken lediglich zweidimensionale Spielfelder darstellen lassen, gibt es ein gewichtiges Problem mit der Texturierung. Passen die Texturen zweier benachbarter Tiles nicht zusammen, so kommt es, wie in Abbildung 1 gezeigt, zu fehlerhaften Texturübergängen.

Abb. 1: Fehlerhafte Texturübergänge bei der Terrain-Darstellung

Abhilfe schafft ein als Textur-Splatting bekanntes Verfahren, das innerhalb der in den Listings 4 und 6 illustrierten Fragment-Shader-Programme zum Einsatz kommt und – wie in Abbildung 2 gezeigt – zu weichen Texturübergängen führt (TerrainRenderingDemonstrations-Programm, Bin/DemoConfig.txt, TerrainRenderTechnique: 1). Unabhängig von der konkreten Art der Implementierung – zu Zeiten, in denen programmierbare Shader noch nicht zum Mainstream gehörten, wurde das Splatting mittels Alpha-Blending umgesetzt – zielt das Verfahren darauf ab, eine Mischfarbe auf Basis mehrerer Texturen zu ermitteln. Wie im nachfolgenden Beispiel gezeigt, verwenden wir in unseren Demoprogrammen bis zu vier Texturen für diese Berechnungen:

Mischfarbe = 0.35*Textur1 + 0.3*Textur2 + 0.2*Textur3 + 0.15*Textur4

Die einzelnen Splatting-Faktoren (Gewichtungsfaktoren) – in unserem Beispiel sind dies 0.35, 0.3, 0.2 sowie 0.15 – werden bei der Erzeugung der Landschaft für alle Terrain-Vertices separat gespeichert und im Verlauf des Rendering-Prozesses innerhalb eines Vertex-Shader-Programms aus einem zweiten Texture-Buffer-Objekt (TextureSplattingValueBuffer) ausgelesen (Listings 3 und 4).

Abb. 2: Weiche Texturübergänge bei der Terrain-Darstellung (Texture Splatting)

// Transformationsmatrix:
uniform mat4 matViewProjection;

uniform samplerBuffer TerrainPosBuffer;
uniform samplerBuffer TextureSplattingValueBuffer;

uniform vec3  CameraPosition;
uniform float InvVertexDistance;
uniform float TileScale;
uniform float HalfTerrainRange;
uniform int NumVerticesPerDir;
uniform int NumVerticesMinus1;

flat out vec4 TextureIDVector;

void main()
{
  gs_TexCoord[0] = gs_MultiTexCoord0;

  vec4 Vertex = vec4(TileScale*gs_Vertex.x, TileScale*gs_Vertex.y, TileScale*gs_Vertex.z, gs_Vertex.w);

  vec3 TerrainPos = texelFetch(TerrainPosBuffer, gl_InstanceID).xyz;

  // Terrain Tile in der Spielewelt (World Space) positionieren:
  Vertex.xyz += TerrainPos;

  // Vertexindex für alle weiteren Texture Buffer Zugriffe berechnen:
  int ix = int((Vertex.x + HalfTerrainRange)*InvVertexDistance);
  int iz = int((HalfTerrainRange - Vertex.z)*InvVertexDistance);
  int VertexID = clamp(ix + iz*NumVerticesPerDir, 0, NumVerticesMinus1);

  vec4 TextureSplattingValues = texelFetch(TextureSplattingValueBuffer, VertexID);

  // Die Stellen vor dem Komma entsprechen den Textur-Indices:
  TextureIDVector = floor(TextureSplattingValues);
  // Die Stellen hinter dem Komma entsprechen den Splatting-Faktoren:
  gs_TexCoord = TextureSplattingValues - TextureIDVector;

  // Terrain Tile relativ zur Kamera positionieren:
  Vertex.xyz -= CameraPosition;

  gl_Position = matViewProjection*Vertex;
}
uniform sampler2DArray SurfaceTextureArray;
flat in vec4 TextureIDVector;

void main()
{
  // Splatting-Faktoren: gs_TexCoord[1]
  // Texure-Array-Indices: TextureIDVector

  vec4 SurfaceColor  = gs_TexCoord[1].x*texture(SurfaceTextureArray,
                         vec3(gs_TexCoord[0].st, TextureIDVector.x));
  SurfaceColor += gs_TexCoord[1].y*texture(SurfaceTextureArray,
                         vec3(gs_TexCoord[0].st, TextureIDVector.y));
  SurfaceColor += gs_TexCoord[1].z*texture(SurfaceTextureArray,
                         vec3(gs_TexCoord[0].st, TextureIDVector.z));
  SurfaceColor += gs_TexCoord[1].w*texture(SurfaceTextureArray,
                         vec3(gs_TexCoord[0].st, TextureIDVector.w));

  gs_FragColor = SurfaceColor;
}

Von einem flachen Spielfeld hin zu einer dreidimensionalen Landschaft (TerrainRenderingDemonstrations-Programm, Bin/DemoConfig.txt, TerrainRenderTechnique: 2) ist es nunmehr ein kleiner Schritt – wir benötigen lediglich ein drittes Texture-Buffer-Objekt (NormalAndHeightBuffer, Listing 5) zum Speichern der Terrain-Höhenwerte samt der zugehörigen Vertexnormalen. Die Berechnung dieser Normalenvektoren erfolgt gemäß Abbildung 3 in drei Schritten: Zunächst bildet man für jeden Vertex die Differenzvektoren (Vertexposition A – Vertexposition B) zu den benachbarten Vertices, errechnet dann für jeweils zwei benachbarte Differenzvektoren das normierte Kreuzprodukt und bildet abschließend den normierten Mittelwert aus allen acht möglichen Produktvektoren.

Abb. 3: Berechnung der Terrain-Normalen für die Beleuchtung

Aufmacherbild: abstract future modern column hall with lighting stripes and reflections on the floor architecture rendering von Shutterstock / Urheberrecht: Adam Vilimek

[ header = Seite 2: Terrain Tiles mit unterschiedlicher Vertex-Anzahl ]

Eingangs wurde erwähnt, dass die Darstellung ausgedehnter Landschaften aus Performancegründen lediglich in Kameranähe mit den maximal möglichen Details erfolgt und dass diese mit zunehmender Entfernung schrittweise reduziert werden. Der jeweilige Detailgrad (LOD, Level Of Detail, Abb. 4) ist von der Vertex-Anzahl der beim Rendern verwendeten Terrain Tiles abhängig, wobei ein 2×2-Tile (4 Vertices, Vertexquad) der kleinstmöglichen LOD-Stufe entspricht. So weit, so gut – problematisch ist nur, dass solche diskontinuierlichen Änderungen des Detailgrads – wie in Abbildung 5 gezeigt – zu unschönen „Löchern“ im Terrain führen, da sich Terrain Tiles mit unterschiedlicher Vertex-Anzahl nicht nahtlos aneinander fügen lassen.

Abb. 4: Beispiel-Terrain mit dem maximal möglichen Detailgrad (max. LOD)

Abb. 5: „Löcher“ im Terrain bei Änderung des Detailgrads

Was sich uns auf den ersten Blick als ein sehr schwer zu lösendes Problem präsentiert, ist in der Praxis erstaunlich leicht zu beheben. Die Lösung wird natürlich ebenfalls in unserem TerrainRenderingDemonstrations-Programmbeispiel demonstriert (Bin/DemoConfig.txt, TerrainRenderTechnique: 3) und erfordert gottlob keinerlei Änderungen an unseren in den Listings 5 und 6 illustrierten Shader-Programmen. Um die Löcher zu verschließen (Abb. 6), müssen wir lediglich die Geometrie unserer Terrain Tiles ein wenig modifizieren und diese mit einer nach unten gerichteten vertikalen „Schürze“ umgeben. Für ein Terrain mit zwei unterschiedlichen Detailstufen benötigt man nun drei anstelle zweier Tiles, jeweils ein Tile für den maximalen und minimalen Detailgrad sowie ein geschürztes Tile zum Verschließen der Löcher, die gemäß des in Abbildung 7 skizzierten Schemas gerendert werden. Die zugehörige Render-Funktion können Sie anhand von Listing 7 nachvollziehen.

Abb. 6: Verwendung geschürzter Terrain-Tiles zum Verschließen der Löcher aus Abbildung 5

Abb. 7: Render-Schema für ein Terrain mit zwei Detailstufen

// Transformationsmatrix:
uniform mat4 matViewProjection;

uniform samplerBuffer TerrainPosBuffer;
uniform samplerBuffer TextureSplattingValueBuffer;
uniform samplerBuffer NormalAndHeightBuffer;

uniform vec3  CameraPosition;
uniform float InvVertexDistance;
uniform float TileScale;
uniform float HalfTerrainRange;
uniform int NumVerticesPerDir;
uniform int NumVerticesMinus1;

flat out vec4 TextureIDVector;

void main()
{
  gs_TexCoord[0] = gs_MultiTexCoord0;

  vec4 Vertex = vec4(TileScale*gs_Vertex.x, TileScale*gs_Vertex.y, TileScale*gs_Vertex.z, gs_Vertex.w);

  vec3 TerrainPos = texelFetch(TerrainPosBuffer, gl_InstanceID).xyz;

  // Terrain Tile in der Spielewelt (World Space) positionieren:
  Vertex.xyz += TerrainPos;

  // Vertexindex für alle weiteren Texture Buffer Zugriffe berechnen:
  int ix = int((Vertex.x + HalfTerrainRange)*InvVertexDistance);
  int iz = int((HalfTerrainRange - Vertex.z)*InvVertexDistance);
  int VertexID = clamp(ix + iz*NumVerticesPerDir, 0, NumVerticesMinus1);

  vec4 NormalAndHeight = texelFetch(NormalAndHeightBuffer, VertexID);

  // Terrain-Höhenwerte berücksichtigen:
  Vertex.y += NormalAndHeight.w;

  vec4 TextureSplattingValues = texelFetch(TextureSplattingValueBuffer, VertexID);

  // Die Stellen vor dem Komma entsprechen den Textur-Indices:
  TextureIDVector = floor(TextureSplattingValues);
  // Die Stellen hinter dem Komma entsprechen den Splatting-Faktoren:
  gs_TexCoord[1] = TextureSplattingValues - TextureIDVector;

  // Vertexnormale:
  gs_TexCoord[2].xyz = NormalAndHeight.xyz;

  // Terrain Tile relativ zur Kamera positionieren:
  Vertex.xyz -= CameraPosition;

  gl_Position = matViewProjection*Vertex;

  gs_TexCoord[3] = vec4(Vertex.xyz, gl_Position.z);
}
uniform sampler2DArray SurfaceTextureArray;
uniform sampler2DArray NormalTextureArray;

flat in vec4 TextureIDVector;

void main()
{
  // Splatting-Faktoren: gs_TexCoord[1]
  // Texure-Array-Indices: TextureIDVector

  vec4 SurfaceColor  = gs_TexCoord[1].x*texture(SurfaceTextureArray,
                         vec3(gs_TexCoord[0].st, TextureIDVector.x));
  SurfaceColor += gs_TexCoord[1].y*texture(SurfaceTextureArray,
                         vec3(gs_TexCoord[0].st, TextureIDVector.y));
  SurfaceColor += gs_TexCoord[1].z*texture(SurfaceTextureArray,
                         vec3(gs_TexCoord[0].st, TextureIDVector.z));
  SurfaceColor += gs_TexCoord[1].w*texture(SurfaceTextureArray,
                         vec3(gs_TexCoord[0].st, TextureIDVector.w));

  vec4 NormalColor  = gs_TexCoord[1].x*texture(NormalTextureArray,
                        vec3(gs_TexCoord[0].st, TextureIDVector.x));
  NormalColor += gs_TexCoord[1].y*texture(NormalTextureArray,
                        vec3(gs_TexCoord[0].st, TextureIDVector.y));
  NormalColor += gs_TexCoord[1].z*texture(NormalTextureArray,
                        vec3(gs_TexCoord[0].st, TextureIDVector.z));
  NormalColor += gs_TexCoord[1].w*texture(NormalTextureArray,
                        vec3(gs_TexCoord[0].st, TextureIDVector.w));

  vec3 Normal = normalize(0.4*gs_TexCoord[2].xyz +
                  0.6*(2.0*NormalColor.rgb - vec3(1.0, 1.0, 1.0)));

  gs_FragColor[0] = SurfaceColor;
  gs_FragColor[1] = gs_TexCoord[3];
  gs_FragColor[2] = vec4(0.5+0.5*Normal.x, 0.5+0.5*Normal.y, 0.5+0.5*Normal.z, NormalColor.a);
  gs_FragColor[3] = vec4(0.0, 0.0, 0.0, 1.0);
  gs_FragColor[4] = vec4(0.0, 0.0, 0.0, 1.0);
}
void C3DLODTerrainWithTextureSplatting::Render_TerrainTiles(
     D3DXVECTOR3* pCameraPosition, D3DXMATRIXA16* pViewProjectionMatrix)
{
  // Terrain Tiles mit der maximalen Detailstufe rendern:
  Build_ShaderVector4Array(TileInstanceDataArray, TileInstanceRenderData1, NumVisibleTerrainTilesMaxLOD);
  
  // Pro Instance 16 Byte:
  TileInstancesTBO->Update_Buffer(TileInstanceDataArray, 0, 16*NumVisibleTerrainTilesMaxLOD);
  
  LODTerrainShader->Use_Shader();
  
  LODTerrainShader->Set_ShaderFloatVector3(pCameraPosition, "CameraPosition");
  LODTerrainShader->Set_ShaderFloatValue(InvVertexDistanceMaxLOD,
                                       "InvVertexDistance");
  LODTerrainShader->Set_ShaderFloatValue(TileScale, "TileScale");
  LODTerrainShader->Set_ShaderFloatValue(HalfTerrainRange, "HalfTerrainRange");
  LODTerrainShader->Set_ShaderIntValue(NumTerrainVerticesPerDirMaxLOD,
                                     "NumVerticesPerDir");
  LODTerrainShader->Set_ShaderIntValue(NumTerrainVerticesMaxLOD-1,
                                     "NumVerticesMinus1");
  LODTerrainShader->Set_ShaderMatrix4X4(pViewProjectionMatrix,
                                      "matViewProjection");
  LODTerrainShader->Set_TextureBuffer(0, TileInstancesTBO->Texture,
                                    "TerrainPosBuffer");
  LODTerrainShader->Set_TextureBuffer(1, TextureSplattingValuesTBO->Texture,
                                    "TextureSplattingValueBuffer");
  LODTerrainShader->Set_TextureBuffer(2, NormalAndHeightValuesTBO->Texture,
                                    "NormalAndHeightBuffer");
  LODTerrainShader->Set_TextureArray(3, SurfaceTextureArray->pTextureArray,
                  g_MipMappingSamplerID, "SurfaceTextureArray");
  LODTerrainShader->Set_TextureArray(4, NormalTextureArray->pTextureArray,
                                   "NormalTextureArray");
  
  pMaxLODTerrainTileVB_IB->Render_Mesh(LODTerrainShader, 0,
                         NumVisibleTerrainTilesMaxLOD);
  
  // geschürzte Terrain Tiles mit der minimalen Detailstufe rendern:
  Build_ShaderVector4Array(TileInstanceDataArray, TileInstanceRenderData3,
                         NumVisibleTerrainTilesLODChange);
  
  // Pro Instance 16 Byte:
  TileInstancesTBO->Update_Buffer(TileInstanceDataArray, 0,
                                16*NumVisibleTerrainTilesLODChange);
  
  pMinLODTerrainTileWithSkirtVB_IB->Render_Mesh(LODTerrainShader, 0,
                                  NumVisibleTerrainTilesLODChange);
  
  // Terrain Tiles mit der minimalen Detailstufe rendern:
  Build_ShaderVector4Array(TileInstanceDataArray, TileInstanceRenderData2,
                         NumVisibleTerrainTilesMinLOD);
  
  // Pro Instance 16 Byte:
  TileInstancesTBO->Update_Buffer(TileInstanceDataArray, 0,
                                16*NumVisibleTerrainTilesMinLOD);
  
  pMinLODTerrainTileVB_IB->Render_Mesh(LODTerrainShader, 0,
                         NumVisibleTerrainTilesMinLOD);
  
  LODTerrainShader->Stop_Using_Shader();
}

[ header = Seite 3: Prozedurale Landschaftsgestaltung ]

Prozedurale Landschaftsgestaltung

Sieht man einmal von Weltraumspielen ab, dann zählt die Landschaftsgestaltung zu den ersten und wichtigsten Schritten beim Design einer neuen Spielewelt oder eines neuen Levels. Obwohl man hierbei selbstverständlich auf real existierende geologische Daten zurückgreifen kann, bieten moderne Terrain-Editoren deutlich mehr Flexibilität bei der täglichen Arbeit, da sich dank ihrer Hilfe viele unterschiedliche und abwechslungsreiche Geländeformationen ohne großen Zeitaufwand prozedural generieren lassen. In der Regel beginnt man zunächst mit der Erzeugung eines zufallsbasierten Basis-Terrains (Beispiel Abb. 1), welches dann im weiteren Verlauf Schritt für Schritt an die Anforderungen der zu designenden Spielewelt angepasst werden muss. Unser TerrainRenderingDemonstrations-Programmbeispiel enthält zwar keinen vollwertigen Terrain-Editor; jedoch ist es möglich (damit Sie die hierbei zum Einsatz kommenden Techniken besser nachvollziehen können), eigene Landschaften mithilfe einer einfachen Skriptsprache zu generieren und abzuspeichern. Schauen wir uns einmal an, was in diesem Zusammenhang zum gegenwärtigen Zeitpunkt technisch bereits möglich ist:

• Angabe aller benötigten Terrain-Texturen samt der dazugehörigen Height Maps
• Prozedurale Erzeugung eines Basis-Terrains, wobei verschiedene Algorithmen miteinander kombiniert werden können (Square Value Noise, Perlin Noise, Cell Noise (Voronoi), Diamond Square)
• Definition verschiedener rechteckiger und kreisförmiger Regionen, in denen das Terrain mit zufälligen Höhenwerten modifiziert wird
• Definition von Bergen und Hügeln (Height Peaks)
• Definition von flachen rechteckigen und kreisförmigen Bereichen/Regionen
• Definition von rechteckigen und kreisförmigen Bereichen, in denen sich das Terrain mit benutzerdefinierten digitalen Filtern (Beispiel: Glätten) modifizieren lässt
• Definition von rechteckigen und kreisförmigen Erosions-Bereichen
• Definition von rechteckigen Bereichen, in denen bis zu vier Texturen mittels Textur-Splatting miteinander kombiniert werden können
• Höhenabhängige Texturierung des Terrains (Beispiele: Gras-Texturen in den Tälern und Gletscher-Texturen im Hochgebirge)
• Steigungsabhängige Texturierung (Steilhänge und flache Abhänge werden unterschiedlich texturiert)
• Einheitliche Texturierung von rechteckigen und kreisförmigen Regionen

Unabhängig vom verwendeten Algorithmus erfolgt die prozedurale Generierung einer Landschaft stets nach dem gleichen Funktionsprinzip. Entweder generiert man zunächst die groben Details des Terrains und fügt mit jedem weiteren Rechenschritt (Iteration) neue und feinere Details hinzu oder man führt besagte Berechnungen in umgekehrter Abfolge durch. Besonders gut lässt sich diese Vorgehensweise anhand des in Listing 8 skizzierten (Square)-Value-Noise-Verfahrens veranschaulichen. Hierbei unterteilt man die Landschaft mit jeder Iteration in immer feinere quadratische Bereiche, denen ein zufälliger Höhenwert zugeordnet wird:

• erste Iteration: 1 Höhenquadrat
• zweite Iteration: 2 mal 2 = 4 Höhenquadrate
• dritte Iteration: 3 mal 3 = 9 Höhenquadrate
• usw.

Im Verlauf jedes Iterationsschritts ermittelt man nun für alle Terrain-Vertices die jeweiligen quadratischen Höhenbereiche, innerhalb derer sie sich befinden, und addiert die zugehörigen Höhenwerte zu den aktuellen Vertex-Höhen. Nach Abschluss aller Berechnungen ergibt sich ein terrassenförmiges Terrain im Minecraft-Look, welches sich im Anschluss daran mittels digitaler Filterung mehr oder weniger stark glätten lässt. Bei einer solchen Filter-Operation wird der Höhenwert eines Vertex unter Einbeziehung der Höhenwerte der acht benachbarten Vertices modifiziert, wobei sich der Einfluss der einzelnen Vertices mithilfe von insgesamt neun Gewichtungsfaktoren beliebig festlegen lässt. Damit man besser nachvollziehen kann, welcher Gewichtungsfaktor welchem Vertex zugeordnet ist, ordnet man die einzelnen Faktoren – so wie in den nachfolgenden Beispielen gezeigt – in Form einer 3×3-Matrix (Faltungsmatrix, Filtermaske, Convolution Kernel) an:

[Definition eines rechteckigen oder kreisförmigen Filterbereichs]
#NumIterations:# 10
#FilterMatrix:#    1.0, 2.0, 1.0,
                   2.0, 14.0, 2.0,
                   1.0, 2.0, 1.0
[Definition eines rechteckigen oder kreisförmigen Filterbereichs]
#NumIterations:# 2
#FilterMatrix:#    1.0, -2.0, 1.0,
                   -2.0, 14.0, -2.0,
                   1.0, -2.0, 1.0

Die Berechnungen selbst werden für alle innerhalb des Filterbereichs liegenden Terrain-Vertices gemäß dem nachfolgend skizzierten Schema durchgeführt:

Vertexhöhe(x, z) =
f1*Vertexhöhe(x-1, z+1) + f2*Vertexhöhe(x, z+1) + f3*Vertexhöhe(x+1, z+1) +
f4*Vertexhöhe(x-1, z) + f5*Vertexhöhe(x, z) + f6*Vertexhöhe(x+1, z) +
f7*Vertexhöhe(x-1, z-1) + f8*Vertexhöhe(x, z-1) + f9*Vertexhöhe(x+1, z-1) +
void Run_SquareValueNoise(float* pHeightField, long NumTerrainVerticesPerDir,
                          float Scale, float HeightStepExponent,
                          float MinRandomVariation, float MaxRandomVariation,
                          float ScaleDecreaseMultiplicator, long IterationSteps,
                          long FirstIterationStep, long IterationStepThreshold)
{
  if(FirstIterationStep < 2)
    FirstIterationStep = 2;

  if(IterationStepThreshold <= FirstIterationStep)
    IterationStepThreshold = FirstIterationStep+1;

  long i, j, k, RandomHeightValueX, RandomHeightValueZ;
  long RandomHeightValueID, TerrainVertexID;
  float RelCoordX, RelCoordZ;

  long NumRandomValues = IterationSteps*IterationSteps;

  float* RandomValueList = new float[NumRandomValues];
  float* RandomVariationList = new float[IterationSteps];

  for(i = 0; i < IterationSteps; i++)
    RandomVariationList[i] = RandomValue.Next_FloatNumber(MinRandomVariation, MaxRandomVariation);

  long NumTerrainVertices = NumTerrainVerticesPerDir*NumTerrainVerticesPerDir;

  // Alle Höhenwerte auf 0 setzen:
  for(i = 0; i < NumTerrainVertices; i++)
    pHeightField[i] = 0.0f;

  float amplitudeCorrected;
  float amplitude = 1.0f;

  for (k = FirstIterationStep; k <= IterationSteps; k++)
  {
    NumRandomValues = k*k;

    // zufällige Höhenwerte aller quadratischen Bereiche generieren (Hinweis: Mit jedem Iterationsschritt wird das Terrain in immer mehr quadratische Bereiche unterteilt):
    for(i = 0; i < NumRandomValues; i++)
      RandomValueList[i] = RandomValue.Next_FloatNumber(0.0f, 1.0f);

    // mögliche Höhenänderungen (Vertexhöhen) im Verlauf einer Iteration nach dem Zufallsprinzip variieren (Hinweis: Der Höhenverlauf wird hierdurch sehr viel abwechslungsreicher):
    amplitudeCorrected = amplitude*RandomVariationList[k-1];

    for(i = 0; i < NumTerrainVerticesPerDir; i++)
    {
      for(j = 0; j < NumTerrainVerticesPerDir; j++)
      {
        TerrainVertexID = j + i*NumTerrainVerticesPerDir;

        RelCoordX = (float)j/(float)NumTerrainVerticesPerDir;
        RelCoordZ = (float)i/(float)NumTerrainVerticesPerDir;

        // Index des quadratischen Höhenbereichs bestimmen:
        RandomHeightValueX = (int)(RelCoordX*(float)k);
        RandomHeightValueZ = (int)(RelCoordZ*(float)k);
        RandomHeightValueID = RandomHeightValueX + k*RandomHeightValueZ;

        // alte Vertex-Höhe bei der Berechnung der neuen Höhe berücksichtigen:
        if(k > IterationStepThreshold)
          pHeightField[TerrainVertexID] +=
            pow(pHeightField[TerrainVertexID], HeightStepExponent)*
            Scale*RandomValueList[RandomHeightValueID]*amplitudeCorrected;
          else
            pHeightField[TerrainVertexID] +=
              Scale*RandomValueList[RandomHeightValueID]*amplitudeCorrected;
    }}

    // Amplitude verkleinern, damit die neuen Terrain-Details mit jedem Iterationsschritt feiner werden:
    amplitude *= ScaleDecreaseMultiplicator;
  }
  SAFE_DELETE_ARRAY(RandomVariationList)
  SAFE_DELETE_ARRAY(RandomValueList)
}

Prozedurale Techniken bieten uns zwar die Möglichkeit, eine Vielzahl von Geländeformationen zu generieren – jedoch sehen sich viele dieser Landschaften recht ähnlich, sofern man bei ihrer Erzeugung immer auf dasselbe Verfahren zurückgreift. Die Lösung dieses Problems bedeutet für uns Programmierer zwar einigen Mehraufwand, das Ergebnis kann sich jedoch sehen lassen – man generiert mehrere prozedurale Terrains mit unterschiedlichen Algorithmen und addiert im Anschluss daran die einzelnen Ergebnisse mit unterschiedlichen Gewichtungsfaktoren:

#Weighting Factors Diamond Square/Cell Noise/Perlin Noise/Square Value Noise:#
0.25, 0.25, 0.25, 0.25

Zu den bekanntesten Algorithmen zählt das von Ken Perlin entwickelte gradientenbasierte Perlin-Noise-Verfahren, welches bereits 1982 bei der Textursynthese im Film Tron zum Einsatz kam und 1997 mit einem Oscar ausgezeichnet wurde. Zellähnliche Strukturen, Stein-, Wasser- oder sogar ganze Planetenoberflächen lassen sich mithilfe des im Jahr 1996 von Steven Worley vorgestellten Cell-Noise-Verfahrens (Worley Noise) simulieren. Die Funktionsweise des nicht minder bekannten, auf der SIGGRAPH 1982 von Fournier, Fussell und Carpenter zum ersten Mal vorgestellten Diamond-Square-Algorithmus, ist in Abbildung 8 skizziert. Im Zuge der Initialisierung teilt man das Terrain zunächst in quadratische Bereiche auf und generiert für deren Eckpunkte zufallsbasierte Höhenwerte (Abb. 8, Start). Indem man nun jeden dieser Bereiche im Verlauf einer Iteration in jeweils vier kleinere Flächen unterteilt, lassen sich zunehmend feinere Terrain-Details erzeugen. Hierbei entspricht jeder neue Höhenwert dem arithmetischen Mittel aus den Höhenwerten der vier nächstgelegenen Vertices, zuzüglich einer zufälligen Höhenmodifikation. Im ersten Schritt berechnet man zunächst – wie in Abbildung 8, Schritt 1 dargestellt – die Höhenwerte der Quadrat-Mittelpunkte unter Berücksichtigung der Höhenwerte der Quadrat-Eckpunkte und kann dann, mithilfe der Ergebnisse aus Schritt 1, die Höhenwerte der Seitenhalbierenden berechnen (Abb. 8, Schritt 2). Bitte beachten Sie in diesem Zusammenhang, dass die vier nächstgelegenen Vertices im ersten Schritt quadratisch und im zweiten Schritt diamantenförmig um den neu zu berechnenden Höhenwert angeordnet sind – eine Tatsache, die zugleich namensgebend für das hier betrachtete Verfahren ist.

Abb. 8: Diamond-Square-Algorithmus (Rechenschema)

Um nun ein zufallsgeneriertes Basis-Terrain an die Anforderungen der zu designenden Spielewelt anzupassen, bietet unser Terrain-Skript einerseits die Möglichkeit, störende – dem Spielspaß abträgliche – prozedural erzeugte Gebirge mittels digitaler Filterung und/oder Erosion einzuebnen und andererseits die Option, weitere Hügel, Berge oder ganze Bergketten gezielt in der Landschaft zu platzieren, wobei sich die Höhe, Breite und Form eines Berges mithilfe der nachfolgend gezeigten Parameter nahezu beliebig variieren lässt (Listing 9).

#Num Height Peaks:# 1

#Maximum Height Value:# 25.0
#RandomSmoothness(>=0):# 1
#Minimum Random Height Value:# -1.5
#Maximum Random Height Value:# 1.5
#Influence Radius^2 (Calculation Function 2+3):# 0.05
#Inv Influence Radius^2 (Calculation Function 3):# 7.0
#HeightCalculationExponent:# 0.9
#AdditionalHeightCalculationFactor:# 0.1
#Height Calculation Function (0 = constHeight, 1 = PeakSquareDist^Exp,
 2 = 1/(AdditionalCalcFactor+PeakDist^Exp)):# 1
#HeightModification(0 = Add, 1 = Substitute, 2 = Clamp To Max HeightValue,
                    3 = max):# 1
#Coordinates (0.0 to 1.0):# 0.5, 0.7

Wenn man ein wenig mit den im TerrainRenderingDemonstrations-Programmbeispiel implementierten prozeduralen Algorithmen herumexperimentiert, stellt man sehr bald fest, dass viele der so erzeugten Basis-Terrains relativ uneben sind. Das kann auf der einen Seite zwar optisch durchaus ansprechend sein, mitunter jedoch zur totalen Unspielbarkeit führen, sofern die vielen Höhenunterschiede unüberwindbare Hindernisse für Fahrzeuge und andere Bodeneinheiten darstellen. Auf die digitale Filterung als Möglichkeit zur Glättung des Terrains sind wir bereits eingegangen. Der Nutzen dieses Verfahrens ist jedoch begrenzt, da es nicht selektiv arbeitet – flache Bereiche werden genauso geglättet wie steile Abhänge. An dieser Stelle kommt die Erosion ins Spiel. In der Natur unterscheidet man zwischen thermalen und hydraulischen Prozessen. Temperaturveränderungen führen zur Verwitterung und Bildung von Steilhängen, und der durch Wasser verursachte Abtransport von Gestein ist dafür verantwortlich, dass raue Felskanten mit der Zeit glatt geschliffen werden. Programmiertechnisch können wir solche Prozesse mithilfe von selektiv wirkenden digitalen Filtern simulieren. Zum jetzigen Zeitpunkt bietet unser Programmbeispiel die Möglichkeit, partiell die flachen Bereiche eines Terrains (Flat Terrain Erosion) oder aber die Abhänge zu erodieren:

[Definition eines rechteckigen oder kreisförmigen Erosionsbereichs]
#Flat Terrain Erosion (0=no, 1=yes):# 1
#HeightVariationThreshold:# 11.0
#NumIterations:# 10
#FilterMatrix:#      1.0, 2.0, 1.0,
                     2.0, 14.0, 2.0,
                     1.0, 2.0, 1.0

Um zu entscheiden, ob ein Höhenwert modifiziert werden muss, ermittelt man zunächst den maximalen und minimalen Höhenwert der benachbarten Vertices, bildet daraus die Differenz (heightDiff) und vergleicht diese mit dem im Skript definieren Schwellenwert (HeightVariationThreshold, Listing 10).

heightDiff = maxHeight - minHeight;

if(RectangularErosionRegionDesc[k].FlatTerrainErosion == 1)
{
  if(heightDiff > HeightVariationThreshold)
    continue;
  }
  else
  {
  if(heightDiff < HeightVariationThreshold)
    continue;
}
[andernfalls Erosion berechnen (digitale Filterung)]
Unsere Redaktion empfiehlt:

Relevante Beiträge

Meinungen zu diesem Beitrag

X
- Gib Deinen Standort ein -
- or -