quadtree: Add subtree area into tree statistics

[sdl-planets] / quadtree.c

diff --git a/quadtree.c b/quadtree.c
index 1417c54ca132583eb20e392809147a9089e7cf15..5edee753abaff4a33b93f6fed86da149944169e9 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -211,6 +211,25 @@ static void quadtree_recalculate_parent_stats(struct quadtree *node,
                        node->children += node->child[i]->children + 1;
                }
 
+               /* The space covered by the parent node's corner
+                * points needs be as wide as its widest child node's
+                * corners.
+                */
+#define CHILD_CORNER_SAFE(node, ch_idx, cor_idx, axis)              \
+               (node)->child[ch_idx] ?                              \
+                       (node)->child[ch_idx]->corner[cor_idx].axis : \
+                       (node)->pos.axis
+
+               node->corner[0].x = MIN(CHILD_CORNER_SAFE(node, 0, 0, x),
+                                       CHILD_CORNER_SAFE(node, 2, 0, x));
+               node->corner[0].y = MIN(CHILD_CORNER_SAFE(node, 0, 0, y),
+                                       CHILD_CORNER_SAFE(node, 1, 0, y));
+               node->corner[1].x = MAX(CHILD_CORNER_SAFE(node, 1, 1, x),
+                                       CHILD_CORNER_SAFE(node, 3, 1, x));
+               node->corner[1].y = MAX(CHILD_CORNER_SAFE(node, 2, 1, y),
+                                       CHILD_CORNER_SAFE(node, 3, 1, y));
+#undef CHILD_CORNER_SAFE
+
                if (ops->recalculate_stats)
                        ops->recalculate_stats(node);