deadleaves.acceleration.quadtree

Spatial acceleration for dead leaves coverage tracking.

A quadtree that tracks which regions of the canvas still contain uncovered pixels. Fully covered subtrees are pruned from future queries, so late in the sampling process, when most of the canvas is filled, only the sparse frontier of remaining gaps is visited.

Classes

CoverageQuadTree

Quadtree that tracks uncovered pixels in the segmentation map.

Module Contents

class deadleaves.acceleration.quadtree.CoverageQuadTree(image_shape: tuple[int, int], position_mask: torch.Tensor, segmentation_map: torch.Tensor, min_tile: int = 16)

Quadtree that tracks uncovered pixels in the segmentation map.

Build once before the sampling loop, then call query_live_tiles() to get only the leaf tiles that (a) still contain uncovered pixels and (b) overlap a given AABB. After writing into the segmentation map, call update_tile() on each affected tile to propagate coverage status upward.

Args:

image_shape:

(H, W) of the canvas.

position_mask:

Integer tensor (H, W) — 1 where sampling is allowed. Tiles that fall entirely outside the position mask are born dead.

min_tile:

Minimum tile edge length. Must be a power of two.

_seg: torch.Tensor

Segmentation map

_pos: torch.Tensor

Position mask

_min_tile: int = 16

Minimum tile edge length.

_H: int

Height of canvas

_W: int

Width of canvas

_root: Node

Root node of Quadtree

_build(y0: int, x0: int, y1: int, x1: int) → Node

Build node for given canvas region

Args:

y0, x0, y1, x1:

Half-open pixel region [y0, y1) x [x0, x1).

property has_live_nodes: bool

True while any uncovered, mask-allowed pixel remains.

query_live_tiles(y_min: int, x_min: int, y_max: int, x_max: int) → list[Node]

Return all alive leaf nodes overlapping the given AABB.

Args:

y_min, x_min, y_max, x_max:

Query bounding box (not clipped — can exceed canvas).

Returns:

List of alive leaf Node objects whose regions intersect the query box.

_query(node: Node, y_min: int, x_min: int, y_max: int, x_max: int, out: list[Node]) → None

Recursively collect all leaf nodes that overlap a query rectangle.

Starting from node, this method traverses the tree and appends all alive leaf nodes whose bounding boxes overlap the given axis-aligned query region to out.

Args:

node (Node):

The current node to test and recurse into.

y_min, x_min, y_max, x_max:

Boundaries of query rectangle.

out (list[Node]):

List that is populated in-place with all matching leaf nodes.

update_tile(tile: Node) → None

Re-check a leaf tile and propagate status up the tree.

Call this after writing pixels into the segmentation map within tile’s region. If the tile is now fully covered, it is marked dead and the change bubbles up.

_propagate_up() → None

Walk the entire tree bottom-up and collapse dead subtrees.

This is cheap because the tree has O(N / min_tile²) leaf nodes and is only called when a tile dies — which can happen at most once per tile over the whole run.

_propagate_node(node: Node) → bool

Returns True if node is alive.