Terrain Tile Picking

Quadtrees

Technically, a quadtree is simply a tree data structure where each node in the tree has four child nodes, similar to the binary trees that are commonly used for dictionaries and hashmaps.  When used as a space partitioning structure, generally we take a 2D surface and recursively divide it into 4 equal quadrants, as in the diagram below.  Although we are working in 3D, rather than 2D, since our terrain is effectively a 2D surface, we can still use a quadtree, we just need to use AABs in order to capture the y-extents of the terrain region, rather than rectangles.

The data structure that we will use for our quadtree is very simple.  We have a container object, QuadTree, which contains the root node of the quadtree, along with any operations that we will define for querying and traversing the tree.  We will represent the nodes of the quadtree with QuadTreeNode class objects.  These nodes consist of a bounding box, which will define the area encompassed by this node, and an array of child nodes.  For leaf nodes, this array will be null, indicating that we are at the terminal end of the tree, otherwise this will contain the four subnodes that divide the node bounding region into quadrants.

// QuadTree.cs
class QuadTree {
    public QuadTreeNode Root;
}

class QuadTreeNode {
    public BoundingBox Bounds;
    public QuadTreeNode[] Children;
}

We will be building the quadtree as part of the initialization function for our Terrain class object, since we need access to the terrain dimensions and heightmap in order to create the bounding volumes.  Creating the quadtree will be our final step, after we have created the terrain heightmap, built the terrain geometry buffers, and created the texture blend map.  When we create the quadtree, we will use a helper function, BuildQuadTree(), to initialize the root node of the tree, passing in the upper-left and bottom-right heightmap index coordinates.

// Terrain.cs
private QuadTree _quadTree;

public void Init(Device device, DeviceContext dc, InitInfo info) {
    // perform all other terrain initialization...

    D3DApp.GD3DApp.ProgressUpdate.Draw(0.97f, "Building picking quadtree...");
    _quadTree = new QuadTree {
        Root = BuildQuadTree(
            new Vector2(0, 0), 
            new Vector2((Info.HeightMapWidth - 1), (Info.HeightMapHeight - 1)))
    };
}

Building the Terrain Quadtree

To construct the quadtree, we will use the recursive BuildQuadTree() function.  This functions accepts the minimum and maximum xz coordinates defining a rectangular region of the terrain heightmap.  First, we need to determine the y-coordinate extents of the terrain region in world-space, using the GetMinMaxY() function.  Next, we need to convert the heightmap-space region extents into world space according to the Terrain’s triangle cell spacing.  Once we have thus determined the world-space 3D extents of the terrain region, we can create a new QuadTreeNode with a bounding box encompassing the entire terrain region.

Next, we need to create the child nodes of the newly created QuadTreeNode.  First, we compute the height and depth of the rectangle defined by the top-left and bottom-right rectangle coordinate parameters.  If the rectangle defines a region larger than our minimum logical terrain tile size, in this example 2x2 heightmap entries, we create the four child nodes, by partitioning the current terrain region rectangle and recursively calling BuildQuadTree.  The recursion terminates when the leaf nodes’ bounding boxes describe a single logical terrain tile.  Ultimately, we return the root node of the quadtree, with complete sub-trees extending down to the individual logical terrain tile bounding boxes.

private QuadTreeNode BuildQuadTree(Vector2 topLeft, Vector2 bottomRight) {

    // search the heightmap in order to get the y-extents of the terrain region
    var minMaxY = GetMinMaxY(topLeft, bottomRight);

    // convert the heightmap index bounds into world-space coordinates
    var minX = topLeft.X*Info.CellSpacing - Width/2;
    var maxX = bottomRight.X*Info.CellSpacing - Width/2;
    var minZ = -topLeft.Y * Info.CellSpacing + Depth / 2;
    var maxZ = -bottomRight.Y * Info.CellSpacing + Depth / 2;
            
    // construct the new node and assign the world-space bounds of the terrain region
    var quadNode = new QuadTreeNode {
        Bounds = new BoundingBox(
            new Vector3(minX, minMaxY.X, minZ), 
            new Vector3(maxX, minMaxY.Y, maxZ)
        )
    };

    var width = (int)Math.Floor((bottomRight.X - topLeft.X)/2);
    var depth = (int)Math.Floor((bottomRight.Y - topLeft.Y)/2);

    // we will recurse until the terrain regions match our logical terrain tile sizes
    const int tileSize = 2;
    if (width >= tileSize && depth >= tileSize) {
        quadNode.Children = new[] {
            BuildQuadTree(
                topLeft, 
                new Vector2(topLeft.X + width, topLeft.Y + depth)
            ),
            BuildQuadTree(
                new Vector2(topLeft.X + width, topLeft.Y), 
                new Vector2(bottomRight.X, topLeft.Y + depth) 
            ),
            BuildQuadTree(
                new Vector2(topLeft.X, topLeft.Y+depth), 
                new Vector2(topLeft.X+depth, bottomRight.Y) 
            ),
            BuildQuadTree(
                new Vector2(topLeft.X+width, topLeft.Y+depth), 
                bottomRight 
            )
        };
    }
            
    return quadNode;
}

To determine the terrain region’s maximum and minimum Y height values, we need to search the terrain heightmap entries contained in the terrain region.  At present, I am simply performing a bilinear search; it is possible there is a more efficient method, but I am unaware of one at the moment.  If you have any suggestions, I would love to hear about it in the comments at the end of this post.

private Vector2 GetMinMaxY(Vector2 tl, Vector2 br) {
    var max = float.MinValue;
    var min = float.MaxValue;
    for (var x = (int) tl.X; x < br.X; x++) {
        for (var y = (int) tl.Y; y < br.Y; y++) {
            min = Math.Min(min, _heightMap[y, x]);
            max = Math.Max(max, _heightMap[y, x]);
        }
    }
    return new Vector2(min, max);
}

Picking the Terrain

Once we have created the terrain quad tree, we can use it to convert a window-space mouse coordinate into a world-space terrain tile position. We will add some code to our demo application’s OnMouseDown event handler to allow the user to right-click and select a terrain tile.  We will mark the picked tile by drawing a red sphere at the center of the tile.  We will generate the world-space picking ray from the window-space mouse coordinate by using our CameraBase.GetPickingRay() function, which we described previously in our original Picking post.

protected override void OnMouseDown(object sender, MouseEventArgs e) {
    if (e.Button == MouseButtons.Left) {
        _lastMousePos = e.Location;
        Window.Capture = true;
    } else if (e.Button == MouseButtons.Right) {
        var ray = _camera.GetPickingRay(new Vector2(e.X, e.Y), new Vector2(Viewport.Width, Viewport.Height));

        _showSphere = _terrain.Intersect(ray, ref _spherePos);
        Console.WriteLine("Clicked at " + _spherePos.ToString());
    }
}

In our Terrain class, we will add the new Intersect() function.  This function uses the Terrain’s QuadTree in order to determine the world-space position of the nearest intersecting terrain tile bounding box.  If there is an intersection, the quadtree returns the center point of the intersected tile bounding box, which may lie above or below the actual terrain surface, so we adjust the height of the intersection point so that it lies on the surface of the terrain.

public bool Intersect(Ray ray, ref Vector3 spherePos) {
    Vector3 ret;
    if (!_quadTree.Intersects(ray, out ret)) {
        return false;
    }
    ret.Y = Height(ret.X, ret.Z);
    spherePos = ret;
    return true;
}

The bulk of our intersection work is performed by the QuadTreeNode Intersects() function.  The QuadTree’s Intersects() function simply calls this function on the root node of the QuadTree.

// QuadTree
public bool Intersects(Ray ray, out Vector3 hit) {
    return Root.Intersects(ray, out hit);
}

Our QuadtreeNode.Intersects() function will return true, if a terrain tile was hit, or false if there was no intersection.  In the case that an intersection is found, the intersection point will be returned in the hit out parameter.  We start by defining our recursion-terminating condition: if the node has no child nodes, we intersect the node’s bounding box and return whether the terrain tile bounding box was hit, setting the intersection point, if there was one, to the center point of the leaf’s bounding box.

If the node has child nodes, we intersect each child’s bounding box, storing the child node and the distance to the intersection in a priority queue (implemented here using a SortedDictionary).  Intersecting the child’s bounding box, rather than the full subtree allows us to quickly cull large regions of the terrain that cannot possibly be picked in a relatively inexpensive manner.  If none of the child bounding volumes was intersected, then there was no intersection.

Once we have populated our child intersection priority queue, we loop over the possible candidates, saving the best intersection point.  We call Intersects() recursively on each child candidate, ignoring those that do not intersect.  If we find an intersection, we take the dot product of the vector between the normalized ray between the intersection point and the ray origin, in order to determine the angle between the intersection point and the ray direction.  This is mainly to ensure that we don’t get false positives if we are looking up at mountains in our terrain, with a flat plain behind us, which can sometimes generate intersections behind the ray origin; using a tolerance of 0.9 ensures that the intersection point will be within approximately a 25 degree cone of the picking ray.  Assuming that we have not discarded the intersection yet, we then check that the distance to this intersection point is closer than the best intersection point we have found thus far.  If it is, we store the intersection point and continue to the next child intersection.  Finally, we return the best intersection that we have found.

Fortunately, the SlimDX Ray and BoundingBox classes have intersections methods that we can use, so that we do not need to write our own ray-box intersection methods.

// QuadTreeNode
public bool Intersects(Ray ray, out Vector3 hit) {
    hit = new Vector3(float.MaxValue);
            

    // This is our terminating condition
    if (Children == null) {
        float d;
        // check if the ray intersects this leaf node's bounding box
        if (!Ray.Intersects(ray, Bounds, out d)) {
            // No intersection
            return false;
        }
        // return the centerpoint of the leaf's bounding box
        hit =  (Bounds.Minimum + Bounds.Maximum ) /2;
        return true;
    }

    // If the node has children, we need to intersect each child.
    // We only intersect the child's immediate bounding volume, in order to avoid fully intersecting 
    // It is possible that the closest child intersection does not actually contain the closest
    // node that intersects the ray, so we maintain a priority queue of the child nodes that were hit, 
    // indexed by the distance to intersection
    var pq = new SortedDictionary<float, QuadTreeNode>();
    foreach (var bvhNode in Children) {
        float cd;
        if (Ray.Intersects(ray, bvhNode.Bounds, out cd)) {
            while (pq.ContainsKey(cd)) {
                // perturb things slightly so that we don't have duplicate keys
                cd += MathF.Rand(-0.001f, 0.001f);
            }
            pq.Add(cd, bvhNode);
        }
    }

    // If there were no child intersections
    if (pq.Count <= 0) {
        return false;
    }

    // check the child intersections for the nearest intersection
    var intersect = false;
    // setup a very-far away intersection point to compare against
    var bestHit = ray.Position + ray.Direction*1000;
    foreach (var bvhNode in pq) {
        Vector3 thisHit;
        // intersect the child node recursively
        var wasHit = bvhNode.Value.Intersects(ray, out thisHit);
        if (!wasHit) {
            // no intersection, continue and intersect the other children
            continue;
        }
        // Make sure that the intersection point is in front of the ray's world-space origin
        var dot = (Vector3.Dot(Vector3.Normalize(thisHit - ray.Position), ray.Direction));
        if (!(dot > 0.9f)) {
            continue;
        }

        // check that the intersection is closer than the nearest intersection found thus far
        if (!((ray.Position - thisHit).LengthSquared() < (ray.Position - bestHit).LengthSquared()))
            continue;

        // if we have found a closer intersection store the new closest intersection
        bestHit = thisHit;
        intersect = true;
    }
    // bestHit now contains the closest intersection found, or the distant sentinel value
    hit = bestHit;
    return intersect;
}

In the video below, you can see the terrain picking in action, with the red ball changing position with each click.

Next Time…

Now that we have picking enabled for the terrain, I think that the next topic I will tackle will be adding A* pathfinding.  With picking and pathfinding, we’ll be able to start adding in units and moving them around on the terrain.  At that point, we’ll start to have something that begins to actually look like a game.  These next steps will probably keep me occupied for a couple weeks, although I may be able to devote more time to this project shortly.  Somewhere on the horizon, I’d like to implement some basic AI, once I have units moving on the terrain, because what I am envisioning for this ultimately will involve commanding formations of units, something like the tactical battles in the Total War series.  I’ve also started on some exploratory work on generating strategic-level maps using Voronoi polygons, and developing a simple physics engine to bolt into my developing engine.  Of course, there are always extras that I need to get to at some point, like creating a text-rendering subsystem, sound and music, networking, a Quake-style console, menu and UI elements, and on and on.  I’ve got no shortage of material…  At some point, I am also going to need to either learn Blender or find somebody who enjoys doing modeling and rigging to work with, so that I can get some original content to work with, once I settle on a direction that I am going with this project (aside from just learning and sharing, that is…).