Hello Keep-framers =). In this topic, you will learn how the landscape works in video games. This topic was created in connection with the project Lost Geo-Odyssey which I am actively developing. But first, let's dive into the details, why do we need levels of detail?
Well... the fact is that your landscape in the game takes up a huge number of triangles, which will reduce the performance of your client's device that uses your product to zero. The level of detail cuts off several levels depending on the distance of the player or the game camera. This technology is also called "Clipmap"
Geometric clip maps are an elegant rendering technique for drawing huge landscapes in real time.
This technology was first published in 2004 by Frank Losasso и Hugues Hoppe. You can learn about this from the original source.
Shortly thereafter, a practical implementation of the GPU was described.
The idea behind geometric clip maps is that you load a mesh that is more finely tiled in the middle than at the edges, draw the mesh centered on the camera, and then move the vertices of the mesh to the desired height on the terrain. This way, you get more detail close to the camera and less detail where it's so far away that you can't see it anyway.
The mesh we send to the GPU might look like this:
And then we set the Z coordinates in the vertex shader so it looks like this:
There are many other LOD methods that achieve the same result, but clip maps stand out for their simplicity. You don't have to run complex decimation algorithms, you don't have to worry about stitching arbitrary meshes together, you don't have to select one of discrete LOD levels at runtime, it's easy to adjust quality for different quality settings, and you don't have to send tons of data to the GPU at each frame.
High-level implementation details
The original article divides the landscape into several different types of meshes and reuses them to draw the entire landscape. You can do it using one mesh.
Let's start with a top-down view of the flat terrain geometry, with each mesh colored according to its type:
You can see that there are several rings or levels. Each ring has the same number of vertices as the ring inside it, but it is twice as large, so the resolution is halved with each level.
You can also see that each level is basically made up of a grid of 4x4 square tiles (blue). Obviously you don't draw the inner 2x2 squares except for the innermost level.
Each level also has filler grids that effectively divide the level into a 2x2 grid of 2x2 squares (the red cross that gets thicker as you move outward), and an L-shaped trim grid that separates each level (the green grids).
To draw the terrain, you basically center the rings on the camera, put all the parts in the right places and that's it. I'll talk more about this later, but for now there's one important thing to note.
The position of each grid must be fixed to be a multiple of its resolution. Thus, if the mesh has a vertex every two units, it needs to snap to positions that are multiples of two. If you don't do this, the vertices will move up and down, floating across the terrain, and the terrain will look like it's shimmering or wobbling, which looks terrible.
With snapping, vertices can be added and removed as the level of detail changes, but they never move, which is much less noticeable.
One consequence of this is that the clipping levels move twice as fast as their inner neighbor. To prevent the tiles from overlapping, you need to add a gap so that each ring can surround not only the inner tier's 4x4 square cell grid, but also some additional padding to allow the inner tier to move while the outer tier remains stationary. That's why you need mesh fillers and trims! This video should show you what I mean:
Seams
If you look at the image from top to bottom again, you'll notice that there are T-junctions at the boundaries between the trim map levels, and T-junctions represent cracks in the terrain. In the image above I set the background color to red to make them stand out.
We're not completely free from having to deal with seams, but luckily they're pretty simple. If we draw the clipping levels slightly spaced from each other, we can draw the triangles we need for the seam geometry. The black lines are the tile boundaries, the gray lines are the triangle boundaries, and the red lines are the seam triangles.
But drawing them separately like this is actually a little misleading. There is no gap, and the vertices at the coarser clipping level match exactly with some of the vertices at the finer level. I drew green lines between the vertices that are in the same position, and I drew the triangles we actually need in red. It's about a third smaller and we don't have to do anything special on the corners.
I haven't drawn a full level, but this works as long as the length of the full side of the clip map is even. And they will be even numbers because we have four square tiles, one wide filler tile, and one wide trim tile. So 4x + 2, which is even. (try drawing all this if you don't believe me)
When you create the seam mesh, you must place the bottom left corner at point (0, 0) in object space.
Finally, we have trimmer grids. We need to rotate them into place, which is a little more difficult than what we've seen so far.
However, there is a little trick. Let's start with the letter L at the bottom left (like a regular L). Then take two bits: flipping the first bit flips the grid horizontally, and flipping the other bit flips the grid vertically. If we draw this, it will look like this:
From here we see that they are all equivalent to rotations around the Z axis:
And these two bits can be interpreted as decimal numbers from 0 to 3. So, when rendering, we can figure out which flips we need and use these bits to index into the rotations array.
To decide which bits to set, we need to figure out where the current clipping map layer is relative to the outer layer. If the current level is in the lower left corner of the hole, the trim needs to be done in the upper right corner and we set both bits. If the current level is at the top right, the trim should go to the bottom left, and we use 00. And so on.
The logic for determining which bits to set is a bit complicated. I do this by looking at the difference between the position of the current level's attached camera and the position of the next outer layer's attached camera. If the difference between them is less than one unit in the X and Y axes, the tile will be placed at the bottom left and the trim should be placed at the top right. If the difference is more than one unit, we set the bit for that axis.
The article turns into that, so let's finish.
I'll attach Mike's repository, he did a great job with Clipmap geometry, you can look at his implementation and support him.
Just know one thing - if you create your own worlds, or an open world game, you should think about Clipmap. Thank you for reading this topic to the end.
Implement, optimize, search, peace to all, see you. =)
Comments