In Part 2 of the terrain series we looked at how to build the basic data storage containers that we'll be using to hold our vertex related data. In this segment we're going to examine the QuadTree we'll be using to manage our terrain. The QuadTree aids us in efficiently determining where we are in the terrain. We'll also be using it to determine which individual vertices to display and which groups of vertices will be active.
When implementing the terrain in your production game, you may wish to create a Terrain class that is the container for all of your quad trees. This will allow easy management of multiple trees as well as paging. To keep our example simple, we're using a single quad tree, so start by adding the QuadTree class to your Terrain project:
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
namespace Pyrite.Terrain
{
public class QuadTree
{
private QuadNode _rootNode;
private TreeVertexCollection _vertices;
private BufferManager _buffers;
private Vector3 _position;
private int _topNodeSize;
private Vector3 _cameraPosition;
private Vector3 _lastCameraPosition;
public int[] Indices;
public Matrix View;
public Matrix Projection;
public GraphicsDevice Device;
public int TopNodeSize { get { return _topNodeSize; } }
public QuadNode RootNode { get { return _rootNode; } }
public TreeVertexCollection Vertices { get { return _vertices; } }
public Vector3 CameraPosition
{
get { return _cameraPosition; }
set { _cameraPosition = value; }
}
internal BoundingFrustum ViewFrustrum { get; set; }
}
}
As we've said before, the QuadTree is going to be the container for all of our nodes. At each level there are four nodes (top left, top right, bottom left, bottom right) except for the very top level which will be a single full node. Each node will contain 9 vertices (Top Left, Top, Top Right, Left, Center, Right, Bottom Left, Bottom, Bottom Right). These vertices mark the bounds of the given quad and determine the detail level for that specific quad. Vertices are also shared between multiple quads. The top-right vertex of the top-left quad node will also be the top-left vertex of the top-right quad node.
Before we can proceed any further with the QuadTree, we need to define the objects it will contain. The QuadTree will contain QuadNodes, each with a NodeType, and each containing 9 NodeVertices. To start, we're going to define our NodeTypes. As we've stated before, the possible node types are FullNode, TopLeft, TopRight, BottomLeft and BottomRight. This is most easily expressed using an enumeration. Right click your terrain project and add a new class. Let's call this new class NodeType.cs. Erase the contents of NodeType.cs and replace them with the following:
namespace Pyrite.Terrain
{
public enum NodeType
{
FullNode = 0,
TopLeft = 1,
TopRight = 2,
BottomLeft = 3,
BottomRight = 4
}
}
Let's also go ahead and create the QuadNodeVertex object that we'll be using to represent the vertices for each quad node. As I stated before, I decided to use a struct for the QuadNodeVertex to avoid adding a tremendous amount of extra complexity to the data stored on the heap. The QuadNodeVertex struct contains two public members, Index and Activated. Index is an integer that points to the location in our array of vertices. Activated signals whether or not the specific vertex should be rendered. We'll leverage this heavily when we get to the section on LOD.
Let's go ahead and create our QuadNodeVertex struct. Once again, add a new class to the Terrain project and call it 'QuadNodeVertex'. Replace the contents with the following:
namespace Pyrite.Terrain
{
public struct QuadNodeVertex
{
public int Index;
public bool Activated;
}
}
Now that we've created the elements that each QuadNode needs, let's go ahead and create our QuadNode object. The quad node will have a reference to its parent node, the parent tree that contains all of the nodes and its neighbors. It will also contain instances of the structs defining its 9 vertices, a bounding box defining the space it consumes, as well as a few other pieces of data that we'll explore as we progress. Let's start by defining our QuadNode class:
using Microsoft.Xna.Framework;
namespace Pyrite.Terrain
{
public class QuadNode
{
}
}
Now let's go ahead and add the fields we need to hold the base QuadNode data. We're adding references to the parent node, the parent tree, each neighboring node and each child. We're also adding instances of the QuadNodeVertex struct we created for each of the 9 vertices in the quad. We're also storing a position index which indicates the index in the vertex array of the top left vertex.
QuadNode _parent;
QuadTree _parentTree;
int _positionIndex;
int _nodeDepth;
int _nodeSize;
bool HasChildren;
#region VERTICES
public QuadNodeVertex VertexTopLeft;
public QuadNodeVertex VertexTop;
public QuadNodeVertex VertexTopRight;
public QuadNodeVertex VertexLeft;
public QuadNodeVertex VertexCenter;
public QuadNodeVertex VertexRight;
public QuadNodeVertex VertexBottomLeft;
public QuadNodeVertex VertexBottom;
public QuadNodeVertex VertexBottomRight;
#endregion
#region CHILDREN
public QuadNode ChildTopLeft;
public QuadNode ChildTopRight;
public QuadNode ChildBottomLeft;
public QuadNode ChildBottomRight;
#endregion
#region NEIGHBORS
public QuadNode NeighborTop;
public QuadNode NeighborRight;
public QuadNode NeighborBottom;
public QuadNode NeighborLeft;
#endregion
public BoundingBox Bounds;
public NodeType NodeType;
Size Requirements and The 9 Vertices
At this point I want to stop back for a second and talk about size requirements and why each node contains 9 vertices instead of just the corners. Since we're dealing with a heightmap to generate terrain geometry, we have a couple of specific size requirements. Firstly, the height map needs to be square. That is, the width and height must be the same. Secondly, the size of the heightmap needs to be (a number divisible by 8) plus 1.
The requirements for the size have much to do with the way a quad tree is divided. Each time you split a quad node, the resulting 4 nodes occupy exactly 1/4 of the space of the parent quad node. Our quad nodes are defined by the vertices that make up their corners. Each node will also have exactly one more vertice than it's actual unscaled width. What this means is that a quad node of width 2 will actually have 3 horizontal vertices. The first vertice marks the zero position, or the top left corner, the middle vertice marks the one position, and the far right vertice marks the 2 position as seen in the image below:
[QUAD NODE VERTICES IMAGE COMING SOON]
In order to be properly divided, the top level quad node needs to have a width divisible by 8. Since we're generating our vertices from a heightmap, the first column represents the horizontal zero position and the first row represents the vertical zero position. This is the 9th vertice. Each quad node also shares vertices with its neighbors. So why do we have 9 vertices?
Simple. Everything is drawn as triangles, not squares. In order to properly divide a square, we need to be able to subdivide it into the triangles that make it up. We could easily divide a square with only four vertices by simply drawing a diagonal across the square, but this would not lend well to LOD.
Let's say you have a quad node of width 16. In our case we are always activating the top-left, top-right, center, bottom-left, bottom-right vertices of any activated quad so each active quad will always be comprised of 4 primary triangles. In the case of our width 16 quad, the 5 primary vertices {x , z} locations are represented as follows: TL:{0 , 0} TR:{16, 0} C:{8 , 8} BL:{0 , 16} BR:{16 , 16}. Now, if we split this quad, it will also need to have vertices activated half way between each of four corners. These woule be the Top vertex{8 , 0}, the Left vertex{0 , 8}, the Right vertex {16, 8} and the Bottom vertex {8, 16}.
[QUAD NODE SPLIT IMAGE COMING SOON]
Now let's say that quad has a neighbor to the right. Since we've activated the "Right" vertex on this node by splitting it we have to also activate the "Left" node on the neighbor to the right otherwise we'll have a split node up against an unsplit node which will create a visible seam. Having the extra vertices at the quad level allows us to activate only the necessary vertices without completely splitting the neighboring quad. This also allows us to display the terrain in progressively less detail as we move away from the quad we're splitting. We'll get into this in more detail when we come to the section of the series on LOD. The image below demonstrates an improperly split neighbor and a properly split neighbor:
[IMAGE COMING SOON]
Constructing the Quad Node
Now that we have the basic framework for our quad node, let's go ahead and build the constructor. For now, we're simply going to construct a single node, set the bounds, add the 9 vertices, and enable the initial 5 required vertices. Go ahead and add the following constructor to your QuadNode class:
/// <summary>
/// QuadNode constructor
/// </summary>
/// <param name="nodeType">Type of node.</param>
/// <param name="nodeSize">Width/Height of node (# of vertices across - 1).</param>
/// <param name="nodeDepth">Depth of current node</param>
/// <param name="parent">Parent QuadNode</param>
/// <param name="parentTree">Top level Tree.</param>
/// <param name="positionIndex">Index of top left Vertice in the parent tree Vertices array</param>
public QuadNode(NodeType nodeType, int nodeSize, int nodeDepth, QuadNode parent, QuadTree parentTree, int positionIndex)
{
NodeType = nodeType;
_nodeSize = nodeSize;
_nodeDepth = nodeDepth;
_positionIndex = positionIndex;
_parent = parent;
_parentTree = parentTree;
//Add the 9 vertices
AddVertices();
Bounds = new BoundingBox(_parentTree.Vertices[VertexTopLeft.Index].Position,
_parentTree.Vertices[VertexBottomRight.Index].Position);
Bounds.Min.Y = -950f;
Bounds.Max.Y = 950f;
if (nodeSize >= 4)
AddChildren();
//Make call to UpdateNeighbors from the parent node.
//This will update all neighbors recursively for the
//children as well. This ensures all nodes are created
//prior to updating neighbors.
if (_nodeDepth == 1)
{
AddNeighbors();
VertexTopLeft.Activated = true;
VertexTopRight.Activated = true;
VertexCenter.Activated = true;
VertexBottomLeft.Activated = true;
VertexBottomRight.Activated = true;
}
}
Here we've initialized our base QuadNode. nodeSize keeps track of the unscaled "width" of the current node, while nodeDepth keeps track of how deep we are in the tree.
We're constructing a bounding box that defines the borders of our quad. For this example we've just set the minimum and maximum Y values to -950f and 950f respectively. We'll be using this bounding box later to determine where to split our tree and to find other nodes that are within view. In a production system it would make more sense to use the maximum height value of your tree as a guide to define the bounds of your bounding box. You may even use the maximum height within each individual quad to define the bounds which would make culling away invisible quads much more efficient when you are standing on a mountain.
In fact, a more efficient method would be to use bounding shapes instead of volumes, using a rectangle as the bounding object. The view frustrum could then be projected onto the terrain as a 2D shape. Intersection checks for LOD would be much more efficient. In this series we're using volumes for simplicity, however I would encourage you to investigate the other possible methods to improve performance.
You'll also notice that we have calls to three additional methods: AddVertices(), AddChildren() and AddNeighbors(). AddChildren is only being called when the node size is greater than or equal to 4. This means that the final node size will be 2 (the child node of the node with width 4). A node with a size of 2 can still be split since it will have 9 vertices, but it is too small to contain additional children. You may want to play around with this minimum node size. Setting it to a higher number will result in a terrain with a lower maximum level of detail. For instance, setting it to >= 8 rather than >= 4 will result in a terrain that has one less depth level defined.
AddNeighbors() is called within an if statement that checks to see if the current node depth is 1, or rather, the top level node. As you'll see shortly, AddChildren creates additional quad nodes and this is done recursively until we reach the maximum depth of the tree. By only calling AddNeighbors from the top level node we ensure that all child nodes in the tree have been created. AddNeighbors will then recursively call AddNeighbors on each of the children to update all of the references. We're also activating the default vertices on the top level of the tree. Another way to accomplish this would be to call AddNeighbors from the QuadTree level after all of the nodes have been added. Feel free to use whichever method you prefer.
AddVertices looks at the NodeType of the current node so it can determine whether it can just use copies of vertices from the parent node. If the node type is FullNode there is no parent and all 9 vertices are created. Remember that these aren't actual vertices but rather a container that determines whether the vertex should be active and an index that tells where to locate the actual vertex in the master array of vertices.
Here are the methods you will need to add for adding the 9 vertices, the children and neighbor references to the nodes.
/// <summary>
/// Add vertices to the quad
/// </summary>
private void AddVertices()
{
switch (NodeType)
{
case NodeType.TopLeft:
VertexTopLeft = _parent.VertexTopLeft;
VertexTopRight = _parent.VertexTop;
VertexBottomLeft = _parent.VertexLeft;
VertexBottomRight = _parent.VertexCenter;
break;
case NodeType.TopRight:
VertexTopLeft = _parent.VertexTop;
VertexTopRight = _parent.VertexTopRight;
VertexBottomLeft = _parent.VertexCenter;
VertexBottomRight = _parent.VertexRight;
break;
case NodeType.BottomLeft:
VertexTopLeft = _parent.VertexLeft;
VertexTopRight = _parent.VertexCenter;
VertexBottomLeft = _parent.VertexBottomLeft;
VertexBottomRight = _parent.VertexBottom;
break;
case NodeType.BottomRight:
VertexTopLeft = _parent.VertexCenter;
VertexTopRight = _parent.VertexRight;
VertexBottomLeft = _parent.VertexBottom;
VertexBottomRight = _parent.VertexBottomRight;
break;
default:
VertexTopLeft = new QuadNodeVertex { Activated = true, Index = 0 };
VertexTopRight = new QuadNodeVertex {
Activated = true,
Index = VertexTopLeft.Index + _nodeSize };
VertexBottomLeft = new QuadNodeVertex {
Activated = true,
Index = (_parentTree.TopNodeSize + 1) * _parentTree.TopNodeSize };
VertexBottomRight = new QuadNodeVertex {
Activated = true,
Index = VertexBottomLeft.Index + _nodeSize };
break;
}
VertexTop = new QuadNodeVertex {
Activated = false,
Index = VertexTopLeft.Index + (_nodeSize / 2) };
VertexLeft = new QuadNodeVertex {
Activated = false,
Index = VertexTopLeft.Index + (_parentTree.TopNodeSize + 1) * (_nodeSize / 2) };
VertexCenter = new QuadNodeVertex {
Activated = false,
Index = VertexLeft.Index + (_nodeSize / 2) };
VertexRight = new QuadNodeVertex {
Activated = false,
Index = VertexLeft.Index + _nodeSize };
VertexBottom = new QuadNodeVertex {
Activated = false,
Index = VertexBottomLeft.Index + (_nodeSize / 2)};
}
/// <summary>
/// Add the 4 child quad nodes.
/// </summary>
private void AddChildren()
{
//Add top left (northwest) child
ChildTopLeft = new QuadNode(NodeType.TopLeft, _nodeSize / 2, _nodeDepth + 1, this, _parentTree, VertexTopLeft.Index);
//Add top right (northeast) child
ChildTopRight = new QuadNode(NodeType.TopRight, _nodeSize / 2, _nodeDepth + 1, this, _parentTree, VertexTop.Index);
//Add bottom left (southwest) child
ChildBottomLeft = new QuadNode(NodeType.BottomLeft, _nodeSize / 2, _nodeDepth + 1, this, _parentTree, VertexLeft.Index);
//Add bottom right (southeast) child
ChildBottomRight = new QuadNode(NodeType.BottomRight, _nodeSize / 2, _nodeDepth + 1, this, _parentTree, VertexCenter.Index);
HasChildren = true;
}
/// <summary>
/// Update reference to neighboring quads
/// </summary>
private void AddNeighbors()
{
switch (NodeType)
{
case NodeType.TopLeft: //Top Left Corner
//Top neighbor
if (_parent.NeighborTop != null)
NeighborTop = _parent.NeighborTop.ChildBottomLeft;
//Right neighbor
NeighborRight = _parent.ChildTopRight;
//Bottom neighbor
NeighborBottom = _parent.ChildBottomLeft;
//Left neighbor
if (_parent.NeighborLeft != null)
NeighborLeft = _parent.NeighborLeft.ChildTopRight;
break;
case NodeType.TopRight: //Top Right Corner
//Top neighbor
if (_parent.NeighborTop != null)
NeighborTop = _parent.NeighborTop.ChildBottomRight;
//Right neighbor
if (_parent.NeighborRight != null)
NeighborRight = _parent.NeighborRight.ChildTopLeft;
//Bottom neighbor
NeighborBottom = _parent.ChildBottomRight;
//Left neighbor
NeighborLeft = _parent.ChildTopLeft;
break;
case NodeType.BottomLeft: //Bottom Left Corner
//Top neighbor
NeighborTop = _parent.ChildTopLeft;
//Right neighbor
NeighborRight = _parent.ChildBottomRight;
//Bottom neighbor
if (_parent.NeighborBottom != null)
NeighborBottom = _parent.NeighborBottom.ChildTopLeft;
//Left neighbor
if (_parent.NeighborLeft != null)
NeighborLeft = _parent.NeighborLeft.ChildBottomRight;
break;
case NodeType.BottomRight: //Bottom Right Corner
//Top neighbor
NeighborTop = _parent.ChildTopRight;
//Right neighbor
if (_parent.NeighborRight != null)
NeighborRight = _parent.NeighborRight.ChildBottomLeft;
//Bottom neighbor
if (_parent.NeighborBottom != null)
NeighborBottom = _parent.NeighborBottom.ChildTopRight;
//Left neighbor
NeighborLeft = _parent.ChildBottomLeft;
break;
}
if (this.HasChildren)
{
ChildTopLeft.AddNeighbors();
ChildTopRight.AddNeighbors();
ChildBottomLeft.AddNeighbors();
ChildBottomRight.AddNeighbors();
}
}
Finishing the Quad Tree Base
Now that the base structure for our quad node is complete, we can finish up the base structure of our QuadTree class. Go ahead and open the QuadTree.cs file we created earlier. Below is a bit of explanation for some of the members we created.
_rootNode is the top level QuadNode. The quad tree itself does not need to contain references to all of the quads. It only needs to contain a reference to the root node which contains the references to it's children. Queries against the tree will be performed recursively starting at the root node.
_position and _topNodeSize just keep track of the top left corner position and the size of the top level quad node.
The camera position and last camera position are used to determine when the camera has moved to a different quad. For this demo we'll be using a fixed rotation camera that will only move up and down, forward and back, and side to side as well as pitch, so we're not going to be taking rotation into account, however in production you will want to use the camera's rotation as well as position to determine when the view of the user has changed.
We will be using View and Projection in a later part of the series. These are used to update a bounding frustrum that we'll be using for our culling. I've gone ahead and added them here since they are part of our QuadTree constructor.
device is a reference to the Graphics Device and will be used by the quad tree when it draws itself.
Now let's go ahead and build the contsructor for our QuadTree. Here we'll also initialize the Indices array large enough to hold the number of indices we'll need for our terrain:
public QuadTree(Vector3 position, Texture2D heightMap, Matrix viewMatrix, Matrix projectionMatrix, GraphicsDevice device, int scale)
{
Device = device;
_position = position;
_topNodeSize = heightMap.Width - 1;
_vertices = new TreeVertexCollection(position, heightMap, scale);
_buffers = new BufferManager(_vertices.Vertices, device);
_rootNode = new QuadNode(NodeType.FullNode, _topNodeSize, 1, null, this, 0);
View = viewMatrix;
Projection = projectionMatrix;
ViewFrustrum = new BoundingFrustum(viewMatrix * projectionMatrix);
//Construct an array large enough to hold all of the indices we'll need.
Indices = new int[((heightMap.Width + 1) * (heightMap.Height + 1)) * 3];
}
Conclusion
Now we have the base structure for our terrain. In the next part of this series we'll continue to update our QuadTree and QuadNode classes and add methods that allow us to draw our base terrain at different levels of detail. Then we'll look at modifying our classes to progressively LOD our terrain away from the position of the camera. Finally, we'll look at how to refine the LOD distance and precision to reduce visual popping and how to cull away geometry that is not within the view frustrum.
<< Go back to Part 2 Terrain Series Table of Contents Go to Part 4 >>