From d0f6f7a588663c9495f8829b1c8f68991ec90599 Mon Sep 17 00:00:00 2001 From: Timo Kokkonen Date: Tue, 12 Jul 2011 19:38:18 +0300 Subject: [PATCH] quadtree: Factor out tree area stats calculation This makes it possible to only update the tree area statistics, in case nothing else has updated from the tree. Signed-off-by: Timo Kokkonen --- quadtree.c | 50 ++++++++++++++++++++++++++++++++------------------ 1 file changed, 32 insertions(+), 18 deletions(-) diff --git a/quadtree.c b/quadtree.c index 81552f6..e35505d 100644 --- a/quadtree.c +++ b/quadtree.c @@ -189,6 +189,37 @@ static struct quadtree *_quadtree_add(struct quadtree *parent, return new; } +static void _recalculate_node_area_stats(struct quadtree *node) +{ + /* 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 +} + +static void recalculate_parent_area_stats(struct quadtree *node) +{ + while (node) { + _recalculate_node_area_stats(node); + + node = node->parent; + } +} + /* * Recursively walk through the tree and propagate changes made to the * given node up until the highest parent. @@ -211,24 +242,7 @@ 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 + _recalculate_node_area_stats(node); if (ops->recalculate_stats) ops->recalculate_stats(node); -- 2.44.0