Up to this point in the series we have accomplished a few major milestones. We've created a set of data objects to hold the information needed by our terrain, we've constructed a quad tree to allow efficient traversal through different portions of our terrain, and we've implemented the logic to draw our terrain at different levels of detail. In this part of the series we're going to explore adding LOD to our terrain. The level of detail code we're going to implement will be simple and linear.
Only the deepest node containing our camera will be drawn at highest detail and it will step away the detail one unit at a time as it gets further from the camera. As you'll soon see, this leads to some decent but less desirable results. Terrain drawn in the distance will be subject to some visible "popping" as the LOD transition changes and vertices not visible to the user will still be drawn, however we will address these issues in the next parts of the series. For now, our goal is to simply implement a system that allows a transition of detail from our target point outward.
If you've been following this series from Part 1 forward you may have noticed a few errors and inconsistencies in the tutorial and code. Over the past few days, I painstakingly followed my own tutorial and combed through the text to find these issues. All code in the first four sections has been updated and fixed as well as some basic refactoring. These updates will be the base for the project going forward. To avoid making you go back and find all of the changes, I have uploaded a Visual Studio 2010 solution that contains all of the code from Part 1 through Part 4. You can download the solution here. I'm also taking a different approach to writing the series going forward. Since I have a completed project I was previously trying to strip out the bits needed for the tutorial but that approach was error prone. I'm now developing a completely new solution as I go to avoid as many of these issues as possible moving forward.
Selecting our Target Node
Our first goal is to locate the deepest node that contains our desired point. If you remember from earlier parts of this series, we created a bounding box for each quad node with height that ranges from -950f to 950f to make sure our nodes are visible when necessary. We also explored the possibility of other methods being used (such as a bounding rectangle instead of a volume). We're going to stick with a bounding box for this series, however we may explore increasing efficiency later on through use of different bounding objects.
The first thing we need to do is define a method that checks whether the specified point is in the current node. To do this, we're going to simply check the containment type of the point against the bounding box. Go ahead and open QuadNode.cs and add the following method:
/// <summary>
/// Returns true if the QuadNode contains a specific point.
/// </summary>
/// <param name="point">Vector3 representing the target point</param>
/// <returns>True if point is contained in the node's bounding box</returns>
public bool Contains(Vector3 point)
{
point.Y = 0;
return Bounds.Contains(point) == ContainmentType.Contains;
}
Now that we have our first Contains method in place, we can start to traverse the tree to find the deepest node that meets our requirements. To do this, we're going to write a method that recursively travels the tree to find the deepest node with that point. Ideally, this search should start at the root level node of the tree. It will check each child of the current node. If that child doesn't contain the point, the search stops for that section of the terrain, otherwise it continues deeper. This is where the power of our quad tree starts to become more evident. Searching only continues for segments of the terrain that contain the point and areas that don't contain it are pruned away.
As a side note, this is done recursively as our method calls the matching method on each child node. If you want to get really crazy with performance, it should be noted that each time a method is called a small amount of memory is allocated on the stack and that memory remains while the method is executing. When you call methods recursively (or methods call other methods) the memory allocated by the top level method can't be released until all of it's child methods are finished. To make this more efficient, you could write a loop to handle these checks instead of recursing. To keep the code simple we're going to stick with recursion.
Now we're going to create our method that searches the tree. We're going to call this method DeepestNodeWithPoint and it will accept a Vector3 which represents the point we want to search for. Go ahead and add the following method to your QuadNode class:
/// <summary>
/// Get a reference to the deepest node that contains a point.
/// </summary>
/// <param name="point">Vector3 representing the target point</param>
/// <returns>Deepest quad node containing target point</returns>
public QuadNode DeepestNodeWithPoint(Vector3 point)
{
//If the point isn't in this node, return null
if (!Contains(point))
return null;
if (HasChildren)
{
if (ChildTopLeft.Contains(point))
return ChildTopLeft.DeepestNodeWithPoint(point);
if (ChildTopRight.Contains(point))
return ChildTopRight.DeepestNodeWithPoint(point);
if (ChildBottomLeft.Contains(point))
return ChildBottomLeft.DeepestNodeWithPoint(point);
//It's contained in this node and not in the first 3
//children, so has to be in 4th child. No need to check.
return ChildBottomRight.DeepestNodeWithPoint(point);
}
//No children, return this QuadNode
return this;
}
And that's it. We now have the ability to find the deepest node in our tree that contains our point. It should also be noted that it is possible for more than one node to contain a point. Since neighboring nodes share vertices, they also share an infinite number of possible points along their shared edges. In fact, if the target location falls directly on the point where all four quads meet, the point is technically contained in all four quads. In our implementation, we're simply returning the first node that it was located in and the others will be ignored. You could return all containing nodes and refine the mesh on all of them which would result in a bit more accurate LOD, however you'd lose some of the finer control over how many vertices are rendered as you may never be sure whether you're tightening the mesh around a single node or up to 4 nodes.
Splitting our Nodes
To adjust the level of detail for our quad, we split nodes. Splitting a node is simply the process of activating our extra vertices and making the child nodes active. There are a few steps involved to splitting a node. First, we need to verify that the node isn't already split. Next we have to make sure the node's parent is also split. This insures that all of the relevant vertices are active. And finally, we have to make sure the node's neighbors honor the split by activating vertices on the neighboring nodes to eliminate seams.
When splitting a node, you could automatically split its neighbors, however this would cause an issue. The entire terrain would be split to the same depth. Instead, we simply activate the shared vertices on the neighbor nodes to make sure the edges of the generated triangles match. This means that the shared edge of the neighbor node will be drawn at the same level of detail as the current node, however the rest of the neighbor node will be drawn at a level of detail lower. We're also checking each of the neighbors to make sure their parent nodes are split, one level more shallow than the current node. If the parent of the neighbor is not split, a split operation is performed and that node checks its neighbors and so on, resulting in a progressively lessening level of detail as we move away from the node containing our target point.
This will all make more sense once we have code in place so let's move forward. The first thing we're going to do is add a couple of properties to our class. Specifically, we need to be able to check whether the node IsSplit and whether the node CanSplit. We already have a private boolean _isSplit variable, so let's add a property to access it. Let's also add a simple property that determines whether the node itself can split. The criteria in this case is simple. The node width needs to be greater than 2. Any node of width 2 cannot be split so the relevant Top, Left, Right and Bottom vertices will simply be activated in the Split method as you'll soon see. I've implemented this as a property, but a method would suffice as well since there is no backing variable that actually holds the value. And finally, we need a way for nodes to access eachother's Parent. Add the following three properties to your QuadNode class
public bool IsSplit { get { return _isSplit; } }
/// <summary>
/// Returns true of the node contains enough vertices to split
/// </summary>
public bool CanSplit { get { return (_nodeSize >= 2); } }
///<summary>
/// Parent node reference
///</summary>
public QuadNode Parent
{
get { return _parent; }
}
With these properties in place, we can implement our Split( ) method and our EnsureNeighborParentSplit( ) methods. As we discussed earlier, the Split method makes sure the parent node is split. Next it checks for children. If children exist, it activates those children, otherwise it sets itself as the active node. It then activates the appropriate vertices, ensures that the neighbor parents are split, and activates the appropriate neighbor vertices. The EnsureNeighborParentSplit method actually performes the verification that each neighbor's parent is split. Here is the code for these two methods:
/// <summary>
/// Split the node by activating vertices
/// </summary>
public void Split()
{
//Make sure parent node is split
if (_parent != null && !_parent.IsSplit)
_parent.Split();
if (CanSplit)
{
//Set active nodes
if (HasChildren)
{
ChildTopLeft.Activate();
ChildTopRight.Activate();
ChildBottomLeft.Activate();
ChildBottomRight.Activate();
_isActive = false;
}
else
{
_isActive = true;
}
_isSplit = true;
//Set active vertices
VertexTop.Activated = true;
VertexLeft.Activated = true;
VertexRight.Activated = true;
VertexBottom.Activated = true;
}
//Make sure neighbor parents are split
EnsureNeighborParentSplit(NeighborTop);
EnsureNeighborParentSplit(NeighborRight);
EnsureNeighborParentSplit(NeighborBottom);
EnsureNeighborParentSplit(NeighborLeft);
//Make sure neighbor vertices are active
if (NeighborTop != null)
NeighborTop.VertexBottom.Activated = true;
if (NeighborRight != null)
NeighborRight.VertexLeft.Activated = true;
if (NeighborBottom != null)
NeighborBottom.VertexTop.Activated = true;
if (NeighborLeft != null)
NeighborLeft.VertexRight.Activated = true;
}
/// <summary>
/// Make sure neighbor parents are split to ensure
/// consistency with vertex sharing and tessellation.
/// </summary>
private static void EnsureNeighborParentSplit(QuadNode neighbor)
{
//Checking for null neighbor and null parent in case
//we recode for additional quad trees in the future.
if (neighbor != null && neighbor.Parent != null)
if (!neighbor.Parent.IsSplit)
neighbor.Parent.Split();
}
Triggering the LOD
With our basic level of detail in place, all that's left to do is trigger the splitting mechanism and draw the terrain. The final changes will be made in the QuadTree class, so if it's not already open, go ahead and open QuadTree.cs. Here we're going to keep a private reference to the current active node and we're going to call the split operation on that node. That node is the deepest node containing our point. Go ahead and add a private variable to store the active node at the top of your QuadTree class.
private QuadNode _activeNode;
Now all that's left to do is make a few simple changes to our QuadTree class and to our Game class to see the results. First, we're working with a small terrain and we want to see the full result of our split so we need to remove the minimum depth that we applied earlier. Find the MinimumDepth member we created earlier and remove its value. Since this is an "int", it will be the default value of zero:
public int MinimumDepth;
Now let's make the necessary changes to our Update method to make sure the node is split. We need to retrieve the deepest node and if it's not null, split it. This should happen immediately after _rootNode.EnforceMinimumDepth. Here is the entire code for the Update method of our QuadTree class:
public void Update(GameTime gameTime)
{
//Only update if the camera position has changed
if (_cameraPosition == _lastCameraPosition)
return;
Effect.View = View;
Effect.Projection = Projection;
_lastCameraPosition = _cameraPosition;
IndexCount = 0;
_rootNode.EnforceMinimumDepth();
_activeNode = _rootNode.DeepestNodeWithPoint(CameraPosition);
if (_activeNode != null)
{
_activeNode.Split();
}
_rootNode.SetActiveVertices();
_buffers.UpdateIndexBuffer(Indices, IndexCount);
_buffers.SwapBuffer();
}
Currently the tree is only capable of splitting. Since our camera is stationary at the moment this will be fine, however once we've rendered the result we'll go back and add the code necessary to merge the tree and return to the top level node. With the QuadTree now complete, let's return to the Game class where we have to make a few more modifications.
Drawing the LODed Terrain
If it's not already open, go ahead and open your Game1.cs file. We're going to be adding a few more private variables that allows us to switch between shaded and wireframe mode. At the top of your Game class, add the following four members:
RasterizerState _rsDefault = new RasterizerState();
RasterizerState _rsWire = new RasterizerState();
bool _isWire;
KeyboardState _previousKeyboardState;
Now we also want to update our camera to get a better view of the terrain we're rendering so we can see the LOD in action. Find the LoadContent( ) method and the line where the _camera variable is initialized. We want to change our position and target so it's looking more down on the terrain and from a higher angle, so change the Camera initialization line to the following:
_camera = new Camera(new Vector3(320, 600, 500), new Vector3(320, 0, 400), _device, 7000f);
Also, in case you glossed over it previously, make sure the MinimumDepth value of the QuadTree is not set... so right below the _quadTree variable initialization, go ahead and add this line:
_quadTree.MinimumDepth = 0;
We also need to setup the RasterizerState objects that we created. At the top of your LoadContent( ) method, add the following code:
_rsDefault.CullMode = CullMode.CullCounterClockwiseFace;
_rsDefault.FillMode = FillMode.Solid;
_rsWire.CullMode = CullMode.CullCounterClockwiseFace;
_rsWire.FillMode = FillMode.WireFrame;
And finally, we need to modify the Update method of our Game class. We're going to compare the current keyboard state against the previous keyboard state to determine whether we need to change the mode to Wireframe. We're also going to exit the running game if the Escape key is pressed. Our entire Game class Update method should now look like this:
protected override void Update(GameTime gameTime)
{
var currentKeyboardState = Keyboard.GetState();
if (_previousKeyboardState == null)
_previousKeyboardState = currentKeyboardState;
// Allows the game to exit
if (currentKeyboardState.IsKeyDown(Keys.Escape))
Exit();
if (currentKeyboardState[Keys.W] == KeyState.Up && _previousKeyboardState.IsKeyDown(Keys.W))
{
if (_isWire)
{
_device.RasterizerState = _rsDefault;
_isWire = false;
}
else
{
_device.RasterizerState = _rsWire;
_isWire = true;
}
}
_previousKeyboardState = currentKeyboardState;
_quadTree.View = _camera.View;
_quadTree.Projection = _camera.Projection;
_quadTree.CameraPosition = _camera.Position;
_quadTree.Update(gameTime);
base.Update(gameTime);
}
Now run your game and press the "W" key on your keyboard to switch from shaded to wireframe. You'll notice some shading inconsistencies (darker areas) on your terrain. This is caused by the Distance Fog we applied to our effect class inside our QuadTree. The result of running your game should look something like this:
Merging Nodes
Before I close out this section of the series I want to add functionality to merge the tree. This will be necessary when moving the camera later so we can reset the level of detail of the current position before refining at the next. In our example we're going to merge the entire tree every time we update it, but it may be more practicle to only merge when the current active node has changed which would make updates more efficient for terrains with a large scale where it takes the camera time to move further than a single unit. Let's start by adding an IsActive property to return the value of our _isActive variable. This variable is used to determine whether the current node is at the active depth level. Go ahead and open your QuadNode.cs file and add the following property to the top:
public bool IsActive
{
get { return _isActive; }
internal set { _isActive = value; }
}
Now let's add our Merge method. Also in your QuadNode class, add the following method that recursively merges all nodes down.
/// <summary>
/// Merge split quad nodes
/// </summary>
public void Merge()
{
//Only perform the merge if there are children
VertexTop.Activated = false;
VertexLeft.Activated = false;
VertexRight.Activated = false;
VertexBottom.Activated = false;
if (NodeType != NodeType.FullNode)
{
VertexTopLeft.Activated = false;
VertexTopRight.Activated = false;
VertexBottomLeft.Activated = false;
VertexBottomRight.Activated = false;
}
_isActive = true;
_isSplit = false;
if (HasChildren)
{
if (ChildTopLeft.IsSplit)
{
ChildTopLeft.Merge();
ChildTopLeft.IsActive = false;
}
else
{
ChildTopLeft.VertexTop.Activated = false;
ChildTopLeft.VertexLeft.Activated = false;
ChildTopLeft.VertexRight.Activated = false;
ChildTopLeft.VertexBottom.Activated = false;
}
if (ChildTopRight.IsSplit)
{
ChildTopRight.Merge();
ChildTopRight.IsActive = false;
}
else
{
ChildTopRight.VertexTop.Activated = false;
ChildTopRight.VertexLeft.Activated = false;
ChildTopRight.VertexRight.Activated = false;
ChildTopRight.VertexBottom.Activated = false;
}
if (ChildBottomLeft.IsSplit)
{
ChildBottomLeft.Merge();
ChildBottomLeft.IsActive = false;
}
else
{
ChildBottomLeft.VertexTop.Activated = false;
ChildBottomLeft.VertexLeft.Activated = false;
ChildBottomLeft.VertexRight.Activated = false;
ChildBottomLeft.VertexBottom.Activated = false;
}
if (ChildBottomRight.IsSplit)
{
ChildBottomRight.Merge();
ChildBottomRight.IsActive = false;
}
else
{
ChildBottomRight.VertexTop.Activated = false;
ChildBottomRight.VertexLeft.Activated = false;
ChildBottomRight.VertexRight.Activated = false;
ChildBottomRight.VertexBottom.Activated = false;
}
}
}
And the last step is to make the call to the Merge function. Open QuadTree.cs and navigate to the Update method. Just before _rootNode.EnforceMinimumDepth(); add the following line:
_rootNode.Merge();
Conclusion
We now have a basic LOD system implemented in our terrain. We're able to specify a point in our terrain and progressively decrease the detail as we move away from that point. In the next section of this series I'm going to show you how to implement view frustrum culling so only nodes and vertices that are within view of the camera are drawn. In the section following that one I'll show you how to implement scaling and distance to your LOD so you're not left with a linear regression of detail. We'll also add movement to the camera and setup a temporary second camera that we'll use for rendering so you can see the LOD in action as it draws the terrain. Finally, we'll make the terrain updates asynchronous to improve performance.
<< Go back to Part 4 Terrain Series Table of Contents Go to Part 6 >>