     |
 |
 |
 | | | | |
 |
|||
 |
||||||
          |
 |
 |
||||
|
A Real-Time Procedural Universe, 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-TreeTwo 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; 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. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Introduction
Features
|
|
|