quadtree: Optimize distance calculation

All of the distance values needed here are only used for comparing
between different distances. The actual distance itself is not used at
all. Thus, the distance calculation can be optimized by leaving out
all of the square root calculations and the end result is still the
same.

Signed-off-by: Timo Kokkonen <kaapeli@itanic.dy.fi>

diff --git a/quadtree.c b/quadtree.c
index cb4add658e44ed0d25a6968bf6a495c7595ec041..0e9b426a994de984388c1a962f1705e23b2af611 100644 (file)
--- a/quadtree.c
+++ b/quadtree.c
@@ -362,11 +362,11 @@ static struct quadtree *quadtree_find_nearest(struct quadtree *tree,
                nearest = tree;
 
        vector_sub(&nearest->pos, pos, &tmp);
-       distance = vector_abs(&tmp);
+       distance = vector_abs_squared(&tmp);
 
        if (tree != nearest) {
                vector_sub(&tree->pos, pos, &tmp);
-               dist = vector_abs(&tmp);
+               dist = vector_abs_squared(&tmp);
                if (dist < distance) {
                        nearest = tree;
                        distance = dist;
@@ -400,7 +400,7 @@ static struct quadtree *quadtree_find_nearest(struct quadtree *tree,
 
                if (node != nearest) {
                        vector_sub(&node->pos, pos, &tmp);
-                       dist = vector_abs(&tmp);
+                       dist = vector_abs_squared(&tmp);
                        if (dist < distance || !nearest) {
                                nearest = node;
                                distance = dist;
@@ -467,7 +467,7 @@ static struct quadtree *quadtree_find_nearest_noparent(struct quadtree *tree,
                                continue;
 
                        vector_sub(pos, &nearest->pos, &sub);
-                       dist = vector_abs(&sub);
+                       dist = vector_abs_squared(&sub);
                        continue;
                }
                node = quadtree_find_nearest(tree->child[i], pos, corner,
@@ -477,7 +477,7 @@ static struct quadtree *quadtree_find_nearest_noparent(struct quadtree *tree,
                        continue;
 
                vector_sub(pos, &node->pos, &sub);
-               dist2 = vector_abs(&sub);
+               dist2 = vector_abs_squared(&sub);
 
                if (dist2 < dist) {
                        nearest = node;