Gamasutra is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Gamasutra: The Art & Business of Making Gamesspacer
Continuous LOD Terrain Meshing Using Adaptive Quadtrees
View All     RSS
November 13, 2019
arrowPress Releases
November 13, 2019
Games Press
View All     RSS







If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 

Continuous LOD Terrain Meshing Using Adaptive Quadtrees


February 28, 2000 Article Start Previous Page 3 of 4 Next
 

Details

That covers the essentials of the algorithm. What's left is a mass of details, some of them crucial. First of all, where is the height data actually stored? In all of the previously-published algorithms, there is a regular grid of height values (and other bookkeeping data), on top of which the mesh is implicitly [1] & [3] or explicitly [3] defined. The key innovation of my algorithm is that the data is actually stored in an adaptive quadtree. This results in two major benefits. First, storage can be allocated adaptively according to the actual dataset or the needs of the application; e.g. less storage can be used in smoother areas or areas where the viewpoint is not expected to travel. Second, the tree can grow or shrink dynamically according to where the viewpoint is; procedural detail can be added to the region near the viewpoint on-the-fly, and deleted when the viewpoint moves on.

In order to store heightfield information in a quadtree, each quadtree square must contain height values for at least its center vertex and two of its edge vertices. All of the other vertex heights are contained in other nearby nodes in the tree. The heights of the corner vertices, for instance, come from the parent quadtree square. The remaining edge vertex heights are stored in neighboring squares. In my current implementation, I actually store the center height and all four edge heights in the quadtree square structure. This simplifies things because all the necessary data to process a square is readily available within the square or as function parameters. The upshot is that the height of each edge vertex is actually stored twice in the quadtree.

Also, in my current implementation, the same quadtree used for heightfield storage is also used for meshing. It should be possible to use two separate heightfields, one for heightfield storage and one for meshing. The potential benefits of such an approach are discussed later.

A lot of the tricky implementation details center around the shared edge vertices between two adjacent squares. For instance, which square is responsible for doing the vertex-enabled test on a given edge vertex? My answer is to arbitrarily say that a square only tests its east and south edge vertices. A square relies on its neighbors to the north and to the west to test the corresponding edge vertices.

Another interesting question is, do we need to clear all enabled flags in the tree at the beginning of Update(), or can we proceed directly from the state left over from the previous frame? My answer is, work from the previous state (like [2], but unlike [1] and [4]). Which leads to more details: we've already covered the conditions that allow us to enable a vertex or a square, but how do we know when we can disable a vertex or a square? Remember from the original Update() explanation, the enabling of a vertex can cause dependent vertices to also be enabled, rippling changes through the tree. We can't just disable a vertex in the middle of one of these dependency chains, if the vertex depends on enabled vertices. Otherwise we'd either get cracks in the mesh, or important enabled vertices would not get rendered.

If you take a look at Figure 8, you'll notice that any given edge vertex has four adjacent sub-squares that use the vertex as a corner. If any vertex in any of those sub-squares is enabled, then the edge vertex must be enabled. Because the square itself will be enabled whenever a vertex within it is enabled, one approach would be to just check all the adjacent sub-squares of an edge vertex before disabling it. However, in my implementation, that would be costly, since finding those adjacent sub-squares involves traversing around the tree. Instead, I maintain a reference count for each edge vertex. The reference count records the number of adjacent sub-squares, from 0 to 4, which are enabled. That means that every time a square is enabled or disabled, the reference counts of its two adjacent edge vertices must be updated. Fortunately, the value is always in the range [0,4], so we can easily squeeze a reference count into three bits.

Figure 8. Each edge vertex has four adjacent sub-squares which use it as a corner. If any of those squares are enabled, then the edge vertex must be enabled. For example, the black vertex must be enabled if any of the four gray squares are enabled.

Thus the disable test for an edge vertex becomes straightforward: if the vertex is currently enabled, and the associated reference count is zero, and the vertex test with the current viewpoint returns false, then disable the edge vertex. Otherwise leave it alone. The conditions for disabling a square are fairly straightforward: if the square is currently enabled, and it's not the root of the tree, and none of its edge vertices are enabled, and none of its sub-squares are enabled, and the square fails the box test for the current viewpoint, then disable it.

Memory

A very important issue with this (or any) LOD method is memory consumption. In a fully populated quadtree, a single quadtree square is equivalent to about three vertices of an ordinary heightfield, so it is imperative to keep the square data-structure as compact as possible. Fortunately, the needs of the Update() and Render() algorithms do not require each square to contain all the information about 9 vertices. Instead, this is the laundry list of required data:

 

  • 5 vertex heights (center, and edges verts east, north, west, south)
  • 6 error values (edge verts east and south, and the 4 child squares)
  • 2 sub-square-enabled reference counts (for east and south verts)
  • 8 1-bit enabled flags (for each edge vertex and each child square)
  • 4 child-square pointers
  • 2 height values for min/max vertical extent
  • 1 1-bit 'static' flag, to mark nodes that can't be deleted

 

Depending on the needs of the application, the height values can usually be squeezed comfortably into 8 or 16 bits. The error values can use the same precision, or you can also do some non-linear mapping voodoo to squeeze them into smaller data sizes. The reference counts can fit into one byte along with the static flag. The enabled flags fit in one byte. The size of the child-square pointers depends on the maximum number of nodes you anticipate. I typically see node counts in the hundreds of thousands, so I would say 20 bits each as a minimum. The min/max vertical values can be squeezed in various ways if desired, but 8 bits each seems like a reasonable minimum. All told, this amounts to at least 191 bits (24 bytes) per square assuming 8-bit height values. 16-bit height values bring the total to at least 29 bytes. A 32-byte sizeof(square) seems like a good target for a thrifty implementation. 36 bytes is what I currently live with in Soul Ride, because I haven't gotten around to trying to bit-pack the child pointers. Another byte-saving trick I use in Soul Ride is to use a fixed-pool allocator replacement for quadquare::new() and delete(). You can eliminate whatever overhead the C++ library imposes (at least 4 bytes I would expect) in favor of a single allocated bit per square.

There are various compression schemes and tricks that could be used to squeeze the data even smaller, at the expense of complexity and performance degradation. In any case, 36 bytes per 3 vertices is not entirely unrespectable. That's 12 bytes/vertex. [1] reports implementations as small as 6 bytes per vertex. [2] only requires storage of vertex heights and "wedgie thicknesses", so the base data could be quite tiny by comparison. [4], using a modified [2], reports the storage of wedgie thicknesses at a fraction of the resolution of the height mesh, giving further savings.

However, such comparisons are put in a different light when you consider that the quadtree data structure is completely adaptive: in very smooth areas or areas where the viewer won't ever go near, you need only store sparse data. At the same time, in areas of high importance to the game, you can include very detailed features; for example the roadway in a driving game can have shapely speed bumps and potholes.

Geomorphs

[2] and [3] go into some detail on "vertex morphing", or "geomorphs". Basically, geomorphing is a technique whereby when vertices are enabled, they smoothly animate from their interpolated position to their correct position. It looks great and eliminates unsightly popping; see McNally's TreadMarks for a nice example.

Unfortunately, doing geomorphs requires storing yet another height value for the vertices that must morph, which would present a real data-size problem for the adaptive quadtree algorithm as I've implemented it. It could result in adding several bytes per square to the storage requirements, which should not be done lightly. [3] incurs the same per-vertex storage penalty, but [2] avoids it because it only has to store the extra height values for vertices that are actually in the current mesh, not for every vertex in the dataset.

I have three suggestions for how to address the geomorph issue. The first alternative is to spend the extra memory. The second alternative is to optimize the implementation, so that really small error tolerances would be practical and geomorphs unnecessary. Moore's Law may take care of this fairly soon without any additional software work. The third alternative is to split the quadtree into two trees, a "storage tree" and a "mesh tree". The storage tree would hold all the heightfield information and precomputed errors, but none of the transitory rendering data like enabled flags, reference counts, geomorph heights, etc. The mesh tree would hold all that stuff, along with links into the storage tree to facilitate expanding the mesh tree and accessing the height data. The mesh tree could be relatively laissez-faire about memory consumption, because its size would only be proportional to the amount of currently-rendered detail. Whereas the storage tree, because it would be static, could trim some fat by eliminating most of the child links.

The storage-tree/mesh-tree split could also, in addition to reducing total storage, increase data locality and improve the algorithm's cache usage.


Article Start Previous Page 3 of 4 Next

Related Jobs

Supergiant Games
Supergiant Games — San Francisco, California, United States
[11.12.19]

Engine Programmer at Supergiant Games
Sucker Punch Productions
Sucker Punch Productions — Bellevue, Washington, United States
[11.12.19]

Camera Designer
Sucker Punch Productions
Sucker Punch Productions — Bellevue, Washington, United States
[11.12.19]

Encounter Designer
Big Red Button Entertainment
Big Red Button Entertainment — El Segundo, California, United States
[11.12.19]

Unity UI/UX Programmer





Loading Comments

loader image