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:
Figure 1. 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).
Figure 2. Those pesky neighbors
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:
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.
Printer-Friendly Version
