deadleaves.acceleration
=======================

.. py:module:: deadleaves.acceleration


Submodules
----------

.. toctree::
   :maxdepth: 1

   /reference/deadleaves/acceleration/quadtree/index


Classes
-------

.. autoapisummary::

   deadleaves.acceleration.CoverageQuadTree


Package Contents
----------------

.. py:class:: 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 :meth:`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 :meth:`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.


   .. py:attribute:: _seg
      :type:  torch.Tensor

      Segmentation map



   .. py:attribute:: _pos
      :type:  torch.Tensor

      Position mask



   .. py:attribute:: _min_tile
      :type:  int
      :value: 16


      Minimum tile edge length.



   .. py:attribute:: _H
      :type:  int

      Height of canvas



   .. py:attribute:: _W
      :type:  int

      Width of canvas



   .. py:attribute:: _root
      :type:  Node

      Root node of Quadtree



   .. py:method:: _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).



   .. py:property:: has_live_nodes
      :type: bool


      True while any uncovered, mask-allowed pixel remains.



   .. py:method:: 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.



   .. py:method:: _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.



   .. py:method:: 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.



   .. py:method:: _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.



   .. py:method:: _propagate_node(node: Node) -> bool

      Returns True if node is alive.