Quadtree collapsing

Question

Okay so i've spent a few days learning what a quadtree is and how to implement one. So far I have a quadtree that when I click inside a leaf it subdivides, I wondering how do I get the previous subdivisions to collapse back up, so that only one area is subdivided at a time?

This is what mine looks like: (1. initial mouse click) (2. another mouse click)

The aim to to eventually track the position of my mouse and subdivide the area it is in dynamically.

THE OVERALL aim it to use this to create a terrain mesh and subdivide based on the camera. But I've gone right back to basics to get an understanding of how this will work.

Any advice would be grand! - Caius

Answer 1

Terminology first: I refer to quadtree quads as "nodes" within the quadtree structure, and I refer to flat array elements as "cells".

Every individual quad, at each subdivision depth, should have it's own wireframe view component. You should also have a flat 2D array that represents all of the quadtree leaf (i.e. deepest level) nodes in your entire root node. We'll call this a presence array. Basically this array shows us which cells have objects in them. You should have one such array for the last frame/update, and one for the new frame. At the start of every frame/update, determine deltas from the presence arrays by comparing their cells at each respective [x, y] location, and recording any differences into lists as follows:

1. enteredInto holds corresponding leaf nodes for any cells that changed from not present in last array -> present in new array.
2. departedFrom holds corresponding leaf nodes for any cells that changed from present in last array -> not present in new array.

I would keep each of these as List<T>.

These sets can each hold multiple entries because your object may be sitting over an intersection of four (or more) leaf cells, and because the object may be larger than a single cell.

Using these sets, you can flag each leaf node with a boolean to either render or not in the current frame/update. As soon as a leaf node is turned on for rendering, all of its ancestors must be automatically turned on for rendering, as well, right up to the root. I would implement this in a setter method, such that as soon as you set any lower level node, it walks up its ancestor list, setting flags all the way to the root. Be sure to switch off "just departed" cells before switching on "just entered" cells.

Answer 2

Implement the following methods: Add(point), Remove(point), Move(point) Move is not completeley necessary as it can be simulated by Remove and Add but that's less efficient.

Use the following mouse events: press -> Add, release -> Remove, drag -> Move

I assume you implemented your Remove and Move functions recursively. Return a boolean value from each Remove call in your Node, so you will know exactly which recursive path removed a point. If this value is true for a certain node, check if that node has any elements or child nodes inside. If it has neither, undo the subdivision.

Another approach may be to track the number of points inside each node (including children). This trades some computation time for memory and may actually be more efficient.

And a side-note: your example is not the best to demonstrate a quadtree. The idea behind quadtrees is that you only subdivide once a node has reached a certain number of points inside. If you only track one position (mouse pointer) you don't even have to subdivide at all. Instead, create a number of points that move around randomly.