Terrain rendering can be done in many ways depending on the scope, scale, and desired visual quality. My ultimate goal is to render an entire planet, with rich detail from any viewpoint and the ability to zoom in/out and see the curvature of the planet. But as a first step, let's just render a "normal" terrain, using a heightmap and simple polygon reduction.
Heightmap definition
A heightmap is simply an image with elevation information. The basic form is a greyscale image where the luminance at each pixel represents elevation. But this can give only 8 bit precision and is not enough to represent a highly detailed terrain (in a greyscale image, all color components have the same 8bit value). A more popular way is to use all 4 channels of the image to reach 32bit precision. But I determined 24bit is enough for the kind of detail I want so I went for a heightmap with 3 channels worth of information: Basically, each channel is responsible for a different spacial magnitude, and when combining all three I get a very smooth terrain.
In my case, Red can displace in units of 100 (low frequency displacement), Green in units of 20 (medium frequency), and Blue in units of 5 (high frequency)  those are arbitrary values, completely tweakable. For example, the following heightmap, composed of the following channels, produces the terrain below:
Polygon complexity
The above 512x512 heightmap has 262144 pixels and produces a mesh with as many vertices. This can easily amount to 250K triangles. For a 1024x1024 heightmap, you can easily reach 1M triangles. At this point polygon reduction seems like a must to keep the terrain complexity under control.
The best practice is to do this reduction at runtime, where pieces of the terrain dynamically change resolution depending on the distance from the viewer. The part of the terrain that is closest needs to have the highest definition, and the farthest need not. Generally speaking, adapting mesh complexity to the view distance (or to any factor, it can be the screenspace area) is called Level of Detail (LOD) determination.
Currently, I don't need to do realtime LOD. For the kind of game I'm making, statically reducing the terrain complexity, combined with dynamic visibility determination using a Quadtree and Frustum culling, gives good results.
Polygon reduction using a Quadtree
A Quadtree is ideal for representing spatial information. In the case of terrain simplification, it can be used to "approximate" the terrain, and then we can create a mesh based on its structure.
In order to build the Quadtree, we must have a criteria to decide if we should subdivide a node or not. In my case, I chose the criteria to be the "height variation" of the vertices within a node. If all the vertices are approximately at the same height (within a certain threshold), I assume they can be "approximated" as a single flat patch, otherwise, I keep subdividing until the height variation is low enough.
The following is an example of how a terrain is approximated using a Quadtree, with different height variation thresholds:
Terrain tesselation using a Quadtree
Now that we have our Quadtree representation, we must create a mesh. As a first step, let's assume all the vertices have zero height to keep it simple, build our mesh, and then apply elevation as a last step.
Now it seems like all we have to do is add vertices at the corners of the quadtree nodes, and connect them to have a terrain right? Not so simple dude. The main challenge is to be able to address the vertices in a predictable way, to be able to build triangles out of them. Basically before you can make a triangle out of vertices x, y, z, you need to know that x, y, z are a valid combination. A good way to do this is to only allow adding vertices to predetermined locations on the quadtree nodes. For example, here are 9 valid positions for a vertex on a node:
This makes triangulation trivial, we know which triangles to create based on the vertices.
Preparing the Quadtree
The problem now is that it's not always possible to have these nice, predictable vertex positions on certain nodes, specially between nodes that have a very different subdivision level. When two neighboring nodes have a subdivision difference greater than 1, the 9 positions are not enough, you need to add more vertices to correctly represent the structure. Things just got out of hand again, by not being able to predetermine the vertex positions you can't determine the triangles easily. The following picture illustrates the problem:
The good thing is that we don't have to solve this problem, it's simpler to create a situation where it doesn't exist: Basically, by making sure two neighboring nodes can't have a subdivision difference greater than 1, those nice 9 vertex spots will always be enough to translate the quadtree into a terrain.
So let's iterate through it and determine the neighbors for each node. If a node has more than 2 neighbors on any side, we subdivide it. We repeat this process many times until no node needs subdivision. And tada, this yields the following quadtree (on the right) where two neighboring nodes can't have a subdivision difference great than 1. On the left is the old quadtree.
Building the mesh
Now we have a tesselationfriendly quadtree, where each node can reference at most 9 vertices. We can start adding the vertices to the terrain. Of course, we only add a vertices to leaf nodes, and make sure there are no duplicates. If a vertex is shared between 2 nodes, they both simply point to the same vertex instance. The unique vertex instances are accumulated in the terrain and will later end up in a VertexBuffer. After all vertices have been added, it's time to build an IndexBuffer to contain triangle information. It's easy to add triangles based on the vertex locations in each node. Basically, if a node has only corner vertices, we make 2 triangles out of it. Otherwise, if it has at least one edge vertex, we add a center vertex and create triangles based on the presence of each edge vertex. Here is how the terrain looks at this point:
Elevating the vertices
The last step is to elevate the vertices based on the heightmap data. The important thing is to keep track of the parent nodes for each vertex. This can be done at the tessellation stage. Then, we sample the pixels corresponding to each leaf node, and determine an average height for that node. Finally, for each vertex, we iterate through the parent nodes and determine a final average height. For a better approximation, the latter average should be weighted, meaning the parent nodes that cover more heightmap pixels should have a higher impact on the average. This is how the terrain looks after elevation:
Final result
After texturing the terrain and adding some fog, here is how my ingame environment looks now:
Heightmap definition
A heightmap is simply an image with elevation information. The basic form is a greyscale image where the luminance at each pixel represents elevation. But this can give only 8 bit precision and is not enough to represent a highly detailed terrain (in a greyscale image, all color components have the same 8bit value). A more popular way is to use all 4 channels of the image to reach 32bit precision. But I determined 24bit is enough for the kind of detail I want so I went for a heightmap with 3 channels worth of information: Basically, each channel is responsible for a different spacial magnitude, and when combining all three I get a very smooth terrain.
In my case, Red can displace in units of 100 (low frequency displacement), Green in units of 20 (medium frequency), and Blue in units of 5 (high frequency)  those are arbitrary values, completely tweakable. For example, the following heightmap, composed of the following channels, produces the terrain below:



Final heightmap 
Corresponding terrain, 1 vertex per heightmap pixel 
The above 512x512 heightmap has 262144 pixels and produces a mesh with as many vertices. This can easily amount to 250K triangles. For a 1024x1024 heightmap, you can easily reach 1M triangles. At this point polygon reduction seems like a must to keep the terrain complexity under control.
The best practice is to do this reduction at runtime, where pieces of the terrain dynamically change resolution depending on the distance from the viewer. The part of the terrain that is closest needs to have the highest definition, and the farthest need not. Generally speaking, adapting mesh complexity to the view distance (or to any factor, it can be the screenspace area) is called Level of Detail (LOD) determination.
Currently, I don't need to do realtime LOD. For the kind of game I'm making, statically reducing the terrain complexity, combined with dynamic visibility determination using a Quadtree and Frustum culling, gives good results.
Polygon reduction using a Quadtree
A Quadtree is ideal for representing spatial information. In the case of terrain simplification, it can be used to "approximate" the terrain, and then we can create a mesh based on its structure.
In order to build the Quadtree, we must have a criteria to decide if we should subdivide a node or not. In my case, I chose the criteria to be the "height variation" of the vertices within a node. If all the vertices are approximately at the same height (within a certain threshold), I assume they can be "approximated" as a single flat patch, otherwise, I keep subdividing until the height variation is low enough.
The following is an example of how a terrain is approximated using a Quadtree, with different height variation thresholds:


T = 20, looks about right 
Now that we have our Quadtree representation, we must create a mesh. As a first step, let's assume all the vertices have zero height to keep it simple, build our mesh, and then apply elevation as a last step.
Now it seems like all we have to do is add vertices at the corners of the quadtree nodes, and connect them to have a terrain right? Not so simple dude. The main challenge is to be able to address the vertices in a predictable way, to be able to build triangles out of them. Basically before you can make a triangle out of vertices x, y, z, you need to know that x, y, z are a valid combination. A good way to do this is to only allow adding vertices to predetermined locations on the quadtree nodes. For example, here are 9 valid positions for a vertex on a node:
This makes triangulation trivial, we know which triangles to create based on the vertices.
Preparing the Quadtree
The problem now is that it's not always possible to have these nice, predictable vertex positions on certain nodes, specially between nodes that have a very different subdivision level. When two neighboring nodes have a subdivision difference greater than 1, the 9 positions are not enough, you need to add more vertices to correctly represent the structure. Things just got out of hand again, by not being able to predetermine the vertex positions you can't determine the triangles easily. The following picture illustrates the problem:
Irregular vertex combination on a node 
So let's iterate through it and determine the neighbors for each node. If a node has more than 2 neighbors on any side, we subdivide it. We repeat this process many times until no node needs subdivision. And tada, this yields the following quadtree (on the right) where two neighboring nodes can't have a subdivision difference great than 1. On the left is the old quadtree.
Quadtree before "normalization" 
After normalization, neighboring nodes differ by 1 subdivision level at most 
Building the mesh
Now we have a tesselationfriendly quadtree, where each node can reference at most 9 vertices. We can start adding the vertices to the terrain. Of course, we only add a vertices to leaf nodes, and make sure there are no duplicates. If a vertex is shared between 2 nodes, they both simply point to the same vertex instance. The unique vertex instances are accumulated in the terrain and will later end up in a VertexBuffer. After all vertices have been added, it's time to build an IndexBuffer to contain triangle information. It's easy to add triangles based on the vertex locations in each node. Basically, if a node has only corner vertices, we make 2 triangles out of it. Otherwise, if it has at least one edge vertex, we add a center vertex and create triangles based on the presence of each edge vertex. Here is how the terrain looks at this point:
Elevating the vertices
The last step is to elevate the vertices based on the heightmap data. The important thing is to keep track of the parent nodes for each vertex. This can be done at the tessellation stage. Then, we sample the pixels corresponding to each leaf node, and determine an average height for that node. Finally, for each vertex, we iterate through the parent nodes and determine a final average height. For a better approximation, the latter average should be weighted, meaning the parent nodes that cover more heightmap pixels should have a higher impact on the average. This is how the terrain looks after elevation:
Final result
After texturing the terrain and adding some fog, here is how my ingame environment looks now:
Screenshot from Starports: Space Defense 
No comments:
Post a Comment