Quad-tree, in 3D.

Context

A quad-tree partitions a 2D plane by recursively splitting any over-crowded cell into four children. The structure itself — parent linked to four offspring — is a thing you almost never get to look at; you just feel it in the query speed. This sketch makes the structure literal: a 2D quad-tree on the right, and the same tree reified as a 3D spatial diagram on the left.

How it works

▸ Two panels, one tree

The Processing window is two stacked PGraphics buffers — a P3D panel on the left and a P2D panel on the right, both reading from a single QuadTree2D. Click anywhere on the 2D panel and the point is appended to the root; the partition splits as needed and the 3D mirror redraws on the next frame.

▸ The 3D tree of spheres

Each node becomes a sphere; each level of recursion drops by a fixed height (LEVEL_H = 90). The four children fan out diagonally by half-spread on the X/Z axes, so the geometry mirrors the spatial quadrants — top-right, top-left, bottom-left, bottom-right. Leaves are tinted red, branches blue, and sphere radius shrinks with the spread so deeper nodes look further away even before perspective kicks in.

private void draw3DNode(QuadTree2D.QuadNode node,
                        float cx, float cy, float cz,
                        float spread) {
  float childY = cy + LEVEL_H;
  float h = spread / 2;

  area3d.stroke(80);
  if (node.n11 != null) area3d.line(cx, cy, cz, cx + h, childY, cz + h);
  if (node.n12 != null) area3d.line(cx, cy, cz, cx + h, childY, cz - h);
  if (node.n21 != null) area3d.line(cx, cy, cz, cx - h, childY, cz - h);
  if (node.n22 != null) area3d.line(cx, cy, cz, cx - h, childY, cz + h);

  area3d.pushMatrix();
  area3d.translate(cx, cy, cz);
  boolean isLeaf =
      node.n11 == null && node.n12 == null
      && node.n21 == null && node.n22 == null;
  area3d.fill(isLeaf ? color(200, 80, 80) : color(80, 140, 200));
  area3d.sphere(max(4, spread / 10));
  area3d.popMatrix();

  if (node.n11 != null) draw3DNode(node.n11, cx + h, childY, cz + h, h);
  if (node.n12 != null) draw3DNode(node.n12, cx + h, childY, cz - h, h);
  if (node.n21 != null) draw3DNode(node.n21, cx - h, childY, cz - h, h);
  if (node.n22 != null) draw3DNode(node.n22, cx - h, childY, cz + h, h);
}

▸ The 2D partition

On the right panel each QuadNode draws its own bounding rectangle, then recurses into its children. The leaves end up as the smallest rectangles visible; the deposited points sit on top as red circles. Because both panels traverse the same tree, the moment a cell splits on the right, a new branch appears on the left.

▸ An orbiting camera

The 3D camera doesn't free-fly — it swings on a fixed pendulum between 0 and π/2 radians, easing the view back and forth across the front face of the tree. Enough motion to give parallax, not so much that you lose orientation.

Status

Under construction — write-up to add: notes on the underlying QuadTree2D implementation, the corner cases at the boundary, and a clip of the structure rebuilding under live point insertion.