Introduction

This article is the fourth in a series, and it assumes that you have already read the first three articles. If you haven't, they can be found on Gamasutra.com. I have also written two articles on atmospheric scattering: one on GameDev.net and the other in GPU Gems 2. Links to all of my online articles can be found on my website at http://sponeil.org/, along with the latest source code and executables for my published demos. The code has been completely re-factored since the last time I published it. All the common code has been pulled out into a shared library, and I borrowed a few concepts from GameDev's Enginuity series of articles.

The planet-rendering algorithm I published with the first three articles was a spherical implementation of ROAM. For a dynamic LOD implementation on a sphere, it was very clean and it created a fairly optimal mesh, but it had a number of drawbacks. Priority and frustum checks were made on every triangle, the vertex/index list was updated every frame, and it was difficult to keep vertex information in video memory. In short, the GPU was under-utilized and the CPU was over-utilized. It also required a lot of memory per triangle, stored no coherent height map anywhere, and had no space partitioning. This made placement of textures and objects on the surface difficult. Newer versions of ROAM may not have these problems, but my implementation did.

A few years ago, I decided to replace ROAM with a chunked quad-tree. Now each node gets its own vertex buffer, priority and frustum checks are done per node, space partitioning and object placement is relatively easy, and it is easy to apply dynamically-generated ground textures and objects. On the other hand, it is a more complicated implementation and it has to create more vertices/triangles to achieve the same level of detail. The extra vertices require extra calls to the fractal function, which hits the CPU very hard. However, there are ways to speed that up, and the extra calls go into building the ground texture, which improves visual quality a lot. Overall, the benefits more than make up for the drawbacks.

The Quad-Tree

Two main classes implement the quad-tree, CPlanetaryMap and CPlanetaryMapNode. The node class is the heart of the quad-tree. My implementation breaks each node into four quadrants, each with 16-24 triangles. When more detail is needed in a specific quadrant, it is split and becomes a new node under the parent. Just like the spherical ROAM implementation, there are six top-level square faces forming a cube. Also like the ROAM implementation, a quadrant can only be split one level deeper than any of its neighbors to avoid cracks in the mesh. In this implementation, extra edge triangles are rendered for each quadrant when its neighbor is at a lower level in the tree. Here is a figure illustrating the triangle layout:

The black dots and lines represent vertices and edges created for the top-level node (level 0). The green lines represent edges created at level 1 and the red lines represent edges created at level 2. In this image the level 0 NE quadrant split down to level 1, and then its SW quadrant split down to level 2. The second split forced the level 0 NW and SE quadrants to split to avoid cracks in the mesh. Note how the green lines creep into the last remaining level 0 quadrant, and how the red lines creep into all four of the neighboring level 1 quadrants. These illustrate the extra triangles that are needed at a quadrant's edges to avoid having cracks in the mesh.

It is fairly easy to determine which triangles need to be drawn for each quadrant. Take the level 0 SW quadrant above as an example. First draw the fan of eight triangles in the quadrant's center, which are highlighted in gray. Then draw the edge triangles surrounding the fan. Not counting the green lines, there are two triangles “facing” each edge of the quadrant (N/S/E/W). Where the quadrant's neighbor has been split into a full node (i.e. the north and east neighbors above), the two triangles facing that edge must be split into four triangles.

To account for the extra edge triangles needed when a quadrant's neighbor is split, extra vertices are generated when each node is built. To keep the code from looking even nastier, a fixed 9x9 grid of vertices is created for each node. I prefer to think of it as 8x8 plus 1 on each side because the resolution doubled = 17x17, tripled = 25x25, and quadrupled = 33x33 (i.e. it's always 8x8 * n + 1). The 4 vertices inside the gray fan above are never used, so you could save 16 vertices per node if you didn't care about making the code a bit messier. The height samples for those vertices need to be calculated anyway for the ground texture and normal map, so you wouldn't save much more than a bit of video memory and the bandwidth used to push that data into video memory. If you have bottlenecks there, then this might be a good optimization for you to consider.

The main difficulty in implementing a spherical quad-tree lies in the fact that neighbors need to be checked by direction (N/S/E/W). On a cube there is no way to set up all 6 faces so that the directions map smoothly with each other. It's impossible to set it up so that going N and then S always puts you back in the same node. See the right-most face in figure 2 below for an example. Next, think about the code trying to determine whether that face's NW quadrant's neighbor to the north is split into a full node. When dealing with neighbors in the same cube face, you can look at the north neighbor's SW quadrant. In this specific case, you need to check the north neighbor's SE quadrant (but it can be different for each case).

Maintaining the neighbor pointers themselves is almost as much of a pain as figuring out which quadrant of each neighbor to check. To help deal with issues like this, I created lookup tables in PlanetaryMapNode.cpp for each of the 6 cube faces, 4 quadrants, and 4 directions. They look like this:

m_nFaceNeighbor[TopFace][LeftEdge] = LeftFace;
m_nFaceNeighbor[LeftFace][TopEdge] = TopFace;

This lets me know that going west from the top cube face takes you to the left cube face, but that you must go north to get back to the top cube face. The code for this is ugly, and I really hate ugly code, but once it's implemented you don't have to worry about it very often. If all else fails, you can also create a position with 3D coordinates a bit to the side of the current node and traverse the tree from the root node(s) to find where it falls.

Planetary Factories

To separate the node class from the code building the planet, I created a class called CPlanetaryFactory. Each class derived from CPlanetaryFactory adds something different to the planet, and factories can be combined in different ways to build different types of planets. The CPlanetaryMap class keeps a list of factories for each planet, and when a node in the quad-tree needs to be built, each factory's BuildNode() method is called. Just in case the factory creates something that needs to be cleaned up, each factory's DestroyNode() method is called when a node is destroyed.

Each factory object is initialized with a CPropertySet object, which is a simple map of named properties. This property set is currently loaded from a configuration file called Planet_Quad.conf. A custom RTTI implementation is used to allow class names to be specified in the configuration file, and to keep CPlanetaryMap from having to know how to create and initialize each factory class. This should make it easy for you to create your own factory class, load its type class, and then change the config file to use it without having to change CPlanetaryMap or CPlanetaryMapNode. This is a very useful separation which can be extended to load factories from other DLLs using LoadLibrary. That would allow new factories to be added dynamically without changing or recompiling the main project.

Here is a list of the factories that currently exist in the Planet_Quad project. All of these are proof-of-concept factories. They are very simple and not very well optimized for now, so there are plenty of things you can do to improve them.

CSimpleHeightMapFactory

This factory loops through each sample point in the node, calculates the direction vector from the center of the planet to that sample point, and passes it to a 3D noise function to determine the height for that sample.

CMixedHeightMapFactory

This factory is just like CSimpleHeightMapFactory, but it pre-generates the first few octaves of noise into buffers. This takes up extra memory and incurs a small performance hit when the demo is launched, but it speeds up the node building process noticeably. It would also be easy to change this so that the pre-generated buffers were created without using noise-based fractals. You could “grow” the planet using plate tectonics, volcanoes, impacts, and erosion. You could also use artist-generated height maps.

CSimpleColorFactory

This factory takes the height of each sample and applies a color to it. This factory is very simple, using height as its only criteria. It would be pretty easy to add latitude or other variables into the calculations, or to build a pre-generated map (i.e. if you “grow” your planet).

CSimpleCraterFactory

This factory adds millions, or even billions, of craters to the planetary surface fairly quickly and without using any memory. It does this by creating a “virtual” quad-tree (i.e. it creates the nodes it needs on the fly). To traverse this non-existent tree, instead of going to a child node, the random seed is altered in such a way that each virtual “child node” has a unique repeatable seed (or as close to unique as we can get it). A simple for loop runs through the levels, adjusting the height of each sample when it finds a “hit”. A very fast RNG (Random Number Generator) is important here. This virtual tree can be used for just about any type of special surface feature.

CGrassFactory

This factory is a very simple test to show that distinct objects can be added to the planet easily. It is just a proof-of-concept. The objects are grass billboards, which are managed in the factory object itself. This helps keep them all together for quick batched rendering, which is important for a large number of small similar objects like grass billboards. For objects that can move around and bump into each other, or for objects where rendering order is important, it would probably be better to manage the objects in the quad-tree.

Dynamically-Generated Ground Textures

Because each node is square and a small height map is generated for each one, it is fairly easy to dynamically generate and apply ground textures. There are a few complications to worry about, and I will explain them here. To start with, here are some constants I have defined in PlanetaryMapNode.h:

#define NODE_WIDTH 8
#define HEIGHT_MAP_SCALE 2

// The surface map will have 9x9 vertices
#define SURFACE_MAP_WIDTH (NODE_WIDTH+1)
#define SURFACE_MAP_COUNT (SURFACE_MAP_WIDTH*SURFACE_MAP_WIDTH)

// The height map will be a multiple of the surface map (i.e. 17X17 or 33x33)
#define HEIGHT_MAP_WIDTH (NODE_WIDTH*HEIGHT_MAP_SCALE+1)
#define HEIGHT_MAP_COUNT (HEIGHT_MAP_WIDTH*HEIGHT_MAP_WIDTH)

// The height map resolution plus a border surrounding it for normal calculations
#define BORDER_MAP_WIDTH (HEIGHT_MAP_WIDTH+2)
#define BORDER_MAP_COUNT (BORDER_MAP_WIDTH*BORDER_MAP_WIDTH)

The surface map size is used for the vertex map, and the height map size is used for the texture and normal maps. The vertex map size is currently fixed at 9x9, and can't be changed without rewriting some of the code used in CPlanetaryNode. The texture/normal map size can be changed by changing HEIGHT_MAP_SCALE. Using a scale of 2, each node gets a 17x17 texture map and a 17x17 normal map. A scale of 4 (33x33) makes the ground textures look very sharp, but it brings the system to a crawl when a lot of nodes need to be split. These are odd sizes for a texture, but keep in mind that the nodes share edges, and the edges of neighboring texture maps must match perfectly to avoid visible seams. The edges of neighboring textures generated from the 17x17 height maps must always match, but re-sampling it down to 16x16 would throw them off.

Fortunately, it is easy to create a 1024x1024 texture (or larger) and treat it like an array of smaller textures. The CTextureArray class handles all of this and makes it relatively painless. It doesn't matter whether the smaller textures inside it are an odd size or not. Odd texture sizes simply cause a little space to be wasted at the edges of the larger parent texture. The CTextureArray class has a method for generating a texture matrix that maps an arbitrary rectangle perfectly to a sub-texture, which makes it easy to set up texture coordinates for each node.

The normal map generation is so similar to the texture map generation that I use the same type of sub-textures for them, and I put them in the same 1024x1024 texture array. The 8-bit RGB values don't allow much precision, but they seem to be sufficient in this case. The only issue we need to worry about is that we need to generate an extra set of height values around the border of the height map to get accurate normals at the edges. It increases the expense of building a node, but without it seams appear at node boundaries.

No matter what you do, seams will show up at the boundary between levels in the quad-tree (i.e. between levels 5 and 6). I'm not certain whether anything can make it go away completely because one node will have more detail and its neighbor will have less. However, there are ways to make this less noticeable. First, keep the texture resolution high. The closer each texel is to one pixel in size, the less visible the problem will be. Second, try to avoid very high-frequency changes in the color or normal maps. If either changes a lot from one level to the next, the seam between levels will be much more noticeable than if the changes are smoother.

Atmospheric Scattering

The ScatterCPU demo was originally published and explained in a GameDev article. The ScatterGPU demo was originally published and explained in a GPU Gems 2 article. Read the articles for an explanation of these algorithms. ScatterCPU is a more accurate approximation of scattering, but it is slower and eats up too much CPU time. Because the Planet_Quad demo uses the version from ScatterGPU, I'll mention some of the problems you may notice with it: