From 4aa80fd16d2c64a4646f55138eba7c68d13d0b48 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Mon, 26 Oct 2009 16:35:38 -0400 Subject: Major dmnsn_kD_splay_search() optimization. At each level of recursion, we have to go down the right branch if it exists. But if we do this before we test the current node and the left branch, we can eliminate those tests in the likely case that we find a closer object in the geometrically larger right subtree. This gives about a 2X speed improvement according to `make bench'. --- libdimension/kD_splay_tree.c | 40 +++++++++++++++++++++------------------- 1 file changed, 21 insertions(+), 19 deletions(-) diff --git a/libdimension/kD_splay_tree.c b/libdimension/kD_splay_tree.c index a661602..c36eb99 100644 --- a/libdimension/kD_splay_tree.c +++ b/libdimension/kD_splay_tree.c @@ -318,11 +318,21 @@ dmnsn_kD_splay_search_recursive(dmnsn_kD_splay_node *node, dmnsn_line ray, double t) { dmnsn_line ray_trans; - dmnsn_kD_splay_search_result result = { NULL, NULL }, result_rec; + dmnsn_kD_splay_search_result result = { NULL, NULL }, result_temp; if (!node) return result; + /* Go down the right subtree first because the closest object is more likely + to lie in the larger bounding boxes */ + result_temp = dmnsn_kD_splay_search_recursive(node->container, ray, t); + if (result_temp.node && (t < 0.0 || result_temp.intersection->t < t)) { + result = result_temp; + t = result.intersection->t; + } else { + dmnsn_delete_intersection(result_temp.intersection); + } + if (dmnsn_box_contains(ray.x0, node->min, node->max) || dmnsn_ray_box_intersection(ray, node->min, node->max, t)) { @@ -333,39 +343,31 @@ dmnsn_kD_splay_search_recursive(dmnsn_kD_splay_node *node, dmnsn_line ray, || dmnsn_ray_box_intersection(ray_trans, node->object->min, node->object->max, t)) { - result.intersection = + result_temp.intersection = (*node->object->intersection_fn)(node->object, ray_trans); - if (result.intersection && (t < 0.0 || result.intersection->t < t)) { + if (result_temp.intersection + && (t < 0.0 || result_temp.intersection->t < t)) { + dmnsn_delete_intersection(result.intersection); result.node = node; + result.intersection = result_temp.intersection; t = result.intersection->t; } else { - dmnsn_delete_intersection(result.intersection); - result.intersection = NULL; + dmnsn_delete_intersection(result_temp.intersection); } } /* Go down the left subtree */ - result_rec = dmnsn_kD_splay_search_recursive(node->contains, ray, t); - if (result_rec.node && (t < 0.0 || result_rec.intersection->t < t)) { + result_temp = dmnsn_kD_splay_search_recursive(node->contains, ray, t); + if (result_temp.node && (t < 0.0 || result_temp.intersection->t < t)) { dmnsn_delete_intersection(result.intersection); - result = result_rec; + result = result_temp; t = result.intersection->t; } else { - dmnsn_delete_intersection(result_rec.intersection); + dmnsn_delete_intersection(result_temp.intersection); } } - /* Go down the right subtree */ - result_rec = dmnsn_kD_splay_search_recursive(node->container, ray, t); - if (result_rec.node && (t < 0.0 || result_rec.intersection->t < t)) { - dmnsn_delete_intersection(result.intersection); - result = result_rec; - t = result.intersection->t; - } else { - dmnsn_delete_intersection(result_rec.intersection); - } - return result; } -- cgit v1.2.3