Constructing a quadtree such that there is only one level difference between adjacent nodes (LOD)

Question

I'm trying to build a quadtree which subdivides a region based on a position and a maximum depth. I want to use this to implement level of detail in terrain. In other words I have a position (x, y), a region (x, y, width), and I pass it to some method build(region, position, maxDepth), which should then return an array of nodes which cover the entire plane.

My implementation differs slightly from this in that the depth, and the root region is represented by a Quadtree-object. To get the total subdivision one then calls the member method get(x, y, radius), which then returns an array of nodes which cover the entire root region (check the code at the bottom).

To avoid getting artifacts it is important for me that there is a maximum of 1 level between adjacent nodes.

Below is an example of an acceptable result. The biggest difference between adjacent nodes is 1. (You can disregard the diagonal lines, they're just a result of triangulation)

This on the other hand is not acceptable because there is a difference of 2 between three adjacent nodes.

To fix this we will have to split the adjacent nodes like this:

Another example of an acceptable solution would be this:

This is the code I have as of now.

class Quadtree {

    constructor({ x, y, width }, levels = 6, parent = null) {

        this.x = x;
        this.y = y;
        this.width = width;

        this.parent = parent;
        this.children = null;

        if (levels > 0) {
            this.children = this.constructor.split(this, levels); // recursively split quadtree.
        }
    }

    /**
     * Checks for intersection.
     * @param  {x, y, radius} circle
     * @param  {x, y, width} square
     * @return {boolean}
     */
    static intersects(circle, square) {
        let deltaX = circle.x - Math.max(square.x, Math.min(circle.x, square.x + square.width));
        let deltaY = circle.y - Math.max(square.y, Math.min(circle.y, square.y + square.width));

        return (deltaX * deltaX + deltaY * deltaY) < (circle.radius * circle.radius);
    }

    /**
     * Splits a node.
     */
    static split(node, levels) {
        let width = node.width / 2;
        let x = node.x;
        let y = node.y;

        // bottom left
        let q1 = new Quadtree({
            x: x,
            y: y,
            width
        }, levels - 1, node);

        // bottom right
        let q2 = new Quadtree({
            x: x + width,
            y: y,
            width
        }, levels - 1, node);

        // top left
        let q3 = new Quadtree({
            x: x,
            y: y + width,
            width
        }, levels - 1, node);

        // top right
        let q4 = new Quadtree({
            x: x + width,
            y: y + width,
            width
        }, levels - 1, node);

        return [q1, q2, q3, q4];
    }

    /**
     * Gets the least amount of nodes covered by the given circle.
     * @param  {x, y, radius} circle
     * @return {Array} An array of Quadtree-nodes.
     */
    get(circle) {

        if (this.children !== null && this.constructor.intersects(circle, { x: this.x, y: this.y, width: this.width })) { // we need to go deeper.
            return this.children.reduce((arr, child) => {

                return arr.concat(child.get(circle));

            }, []);

        } else {
            return [ this ];
        }
    }
}

Here's an example of how I would use it:

let tree = new Quadtree({ x: 0, y: 0, width: 100}, 2);
let nodes = tree.get({x: 15, y: 15, radius: 5}); // returns an array of nodes covering the whole region.

Examples:

tree.get({x: -15, y: -15, radius: 5});
[ Quadtree { x: 0, y: 0, width: 100 } ] // returns the top node.

tree.get({x: 15, y: 15, radius: 5});
[ 7 Quadtree-nodes ]

The last example returns seven Quadtree-nodes like this:

#-------#-------#
|       |       |
|       |       |
|       |       |
#---#---#-------#
|   |   |       |
#---#---|       |
|   |   |       |
#---#---#-------#

If it's useful the Quadtree-nodes also store a pointer to their parents.

Am I going at this in the wrong direction? Enforcing the constraints by going back up the tree, and keeping track of positions and what not, seems overly complicated to me. Is there a different angle here?

Answer 1

It is possible to ensure that no two adjacent nodes are more than two levels apart with only a slight modification to the algorithm. The idea is to split the node when there is an intersection between the circle and a certain rectangle whose dimensions depend on the node square as well as its depth.

Consider what affects whether a node at a given depth needs to be split, starting from the deepest level upwards.

1. A node of maximum depth cannot be split.

2. A node of depth maxDepth - 1 should only be split if it intersects the circle.

3. A node of depth maxDepth - 2 should be split if it either intersects the circle or is adjacent to a node of depth maxDepth (so keeping it unsplit would violate the requirement). But the latter condition is equivalent to being adjacent to a node of depth maxDepth - 1 that was split. Which, in turn, is equivalent to having an adjacent node of depth maxDepth - 1 that intersects the circle (see the previous paragraph). How do we determine whether this is the case without traversing the adjacent nodes and backtracking? Notice that the union of the current node (x, y, x + width, y + width) and all its adjacent nodes one level deeper equals to the intersection of the square (x - width/2, y - width/2, x + width*2, y+width*2) and the root square. So the whole condition boils down to finding an intersection between the circle, the root square, and the current square inflated to twice its size. (See the picture.)

4. Applying similar reasoning to the next level, a node (x, y, x + width, y + width) of depth maxDepth - 3 should be split if there is an intersection between the circle, the root square, and the square (x - width*3/4, y - width*3/4, x + width*5/2, y + width*5/2).

5. Finally, generalizing this to a node of arbitrary depth, a node (x, y, x + width, y + width) should be split if and only if there is an intersection between the circle, the root square, and the square (x - width*inflationRatio/2, y - inflationRatio/2, x + width*(1+inflationRatio), y + width*(1+inflationRatio)), where inflationRatio = 2^(2-maxDepth+depth). (This can be proved by induction, where each inflated square equals to the union of the node and all adjacent inflated squares one level deeper).