summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@gmail.com>2010-04-27 21:25:50 -0600
committerTavian Barnes <tavianator@gmail.com>2010-05-05 22:33:24 -0600
commit9b04b4e2a1147ed2a30e4f86dd403851036b3b51 (patch)
treeee0b612746e2a4acaeadf40bbac76fdad939cf6b
parent72a0b0d511822d7521e2d44f6e468f3d1870521e (diff)
downloaddimension-9b04b4e2a1147ed2a30e4f86dd403851036b3b51.tar.xz
Replace BVSTs with priority R-trees.
-rw-r--r--bench/libdimension/Makefile.am8
-rw-r--r--bench/libdimension/prtree.c (renamed from bench/libdimension/bvst.c)44
-rw-r--r--libdimension/Makefile.am4
-rw-r--r--libdimension/bvst.c388
-rw-r--r--libdimension/dimension_impl.h2
-rw-r--r--libdimension/prtree.c574
-rw-r--r--libdimension/prtree.h (renamed from libdimension/bvst.h)53
-rw-r--r--libdimension/raytrace.c31
-rw-r--r--tests/libdimension/Makefile.am6
-rw-r--r--tests/libdimension/prtree.c (renamed from tests/libdimension/bvst.c)43
10 files changed, 636 insertions, 517 deletions
diff --git a/bench/libdimension/Makefile.am b/bench/libdimension/Makefile.am
index cc3d122..a384b56 100644
--- a/bench/libdimension/Makefile.am
+++ b/bench/libdimension/Makefile.am
@@ -19,18 +19,18 @@
INCLUDES = -I$(top_srcdir)/libdimension
-EXTRA_PROGRAMS = bench-array bench-geometry bench-bvst
+EXTRA_PROGRAMS = bench-array bench-geometry bench-prtree
AM_CFLAGS = $(libsandglass_CFLAGS) -fno-inline
AM_LDFLAGS = $(libsandglass_LIBS) $(top_builddir)/libdimension/libdimension.la
bench_array_SOURCES = array.c
bench_geometry_SOURCES = geometry.c
-bench_bvst_SOURCES = bvst.c
+bench_prtree_SOURCES = prtree.c
-bench: bench-array$(EXEEXT) bench-geometry$(EXEEXT) bench-bvst$(EXEEXT)
+bench: bench-array$(EXEEXT) bench-geometry$(EXEEXT) bench-prtree$(EXEEXT)
./bench-array$(EXEEXT)
./bench-geometry$(EXEEXT)
- ./bench-bvst$(EXEEXT)
+ ./bench-prtree$(EXEEXT)
.PHONY: bench
diff --git a/bench/libdimension/bvst.c b/bench/libdimension/prtree.c
index dd61a80..5ee32cf 100644
--- a/bench/libdimension/bvst.c
+++ b/bench/libdimension/prtree.c
@@ -66,17 +66,17 @@ dmnsn_randomize_bounding_box(dmnsn_object *object)
}
}
-dmnsn_bvst_node *
-dmnsn_bvst_deepest_recursive(dmnsn_bvst_node *node,
+dmnsn_prtree_node *
+dmnsn_prtree_deepest_recursive(dmnsn_prtree_node *node,
unsigned int depth, unsigned int *deepest)
{
- dmnsn_bvst_node *left = NULL, *right = NULL;
+ dmnsn_prtree_node *left = NULL, *right = NULL;
if (node->contains) {
- left = dmnsn_bvst_deepest_recursive(node->contains, depth + 1, deepest);
+ left = dmnsn_prtree_deepest_recursive(node->contains, depth + 1, deepest);
}
if (node->container) {
- right = dmnsn_bvst_deepest_recursive(node->container,
+ right = dmnsn_prtree_deepest_recursive(node->container,
depth + 1, deepest);
}
@@ -92,18 +92,18 @@ dmnsn_bvst_deepest_recursive(dmnsn_bvst_node *node,
}
}
-dmnsn_bvst_node *
-dmnsn_bvst_deepest(dmnsn_bvst *tree)
+dmnsn_prtree_node *
+dmnsn_prtree_deepest(dmnsn_prtree *tree)
{
unsigned int deepest = 0;
- return dmnsn_bvst_deepest_recursive(tree->root, 0, &deepest);
+ return dmnsn_prtree_deepest_recursive(tree->root, 0, &deepest);
}
int
main()
{
- dmnsn_bvst *tree;
- dmnsn_bvst_node *node;
+ dmnsn_prtree *tree;
+ dmnsn_prtree_node *node;
dmnsn_intersection intersection;
dmnsn_line ray;
const unsigned int nobjects = 128;
@@ -118,7 +118,7 @@ main()
return EXIT_FAILURE;
}
- tree = dmnsn_new_bvst();
+ tree = dmnsn_new_prtree();
for (i = 0; i < nobjects; ++i) {
objects[i] = dmnsn_new_object();
@@ -128,40 +128,40 @@ main()
objects[i]->intersection_fn = &dmnsn_fake_intersection_fn;
}
- /* dmnsn_bvst_insert() */
+ /* dmnsn_prtree_insert() */
grains = 0;
for (i = 0; i < nobjects; ++i) {
sandglass_bench_noprecache(&sandglass,
- dmnsn_bvst_insert(tree, objects[i]));
+ dmnsn_prtree_insert(tree, objects[i]));
sandglass.grains += grains;
grains = sandglass.grains;
}
- printf("dmnsn_bvst_insert(): %ld\n", sandglass.grains/nobjects);
+ printf("dmnsn_prtree_insert(): %ld\n", sandglass.grains/nobjects);
- /* dmnsn_bvst_search() */
+ /* dmnsn_prtree_search() */
ray.x0 = dmnsn_new_vector(0.0, 0.0, -2.0);
ray.n = dmnsn_new_vector(0.0, 0.0, 1.0);
(*objects[0]->intersection_fn)(objects[0], ray, &intersection);
sandglass_bench_noprecache(&sandglass, {
- dmnsn_bvst_search(tree, ray, &intersection);
+ dmnsn_prtree_search(tree, ray, &intersection);
});
- printf("dmnsn_bvst_search(): %ld\n", sandglass.grains);
+ printf("dmnsn_prtree_search(): %ld\n", sandglass.grains);
- /* dmnsn_bvst_splay() */
+ /* dmnsn_prtree_splay() */
grains = 0;
for (i = 0; i < nobjects; ++i) {
- node = dmnsn_bvst_deepest(tree);
- sandglass_bench_noprecache(&sandglass, dmnsn_bvst_splay(tree, node));
+ node = dmnsn_prtree_deepest(tree);
+ sandglass_bench_noprecache(&sandglass, dmnsn_prtree_splay(tree, node));
sandglass.grains += grains;
grains = sandglass.grains;
}
- printf("dmnsn_bvst_splay(): %ld\n", sandglass.grains/nobjects);
+ printf("dmnsn_prtree_splay(): %ld\n", sandglass.grains/nobjects);
/* Cleanup */
- dmnsn_delete_bvst(tree);
+ dmnsn_delete_prtree(tree);
for (i = 0; i < nobjects; ++i) {
dmnsn_delete_object(objects[i]);
}
diff --git a/libdimension/Makefile.am b/libdimension/Makefile.am
index 535bd69..b5b0be1 100644
--- a/libdimension/Makefile.am
+++ b/libdimension/Makefile.am
@@ -49,8 +49,8 @@ lib_LTLIBRARIES = libdimension.la
libdimension_la_SOURCES = $(nobase_include_HEADERS) \
ambient.c \
- bvst.c \
- bvst.h \
+ prtree.c \
+ prtree.h \
camera.c \
canvas.c \
canvas_pigment.c \
diff --git a/libdimension/bvst.c b/libdimension/bvst.c
deleted file mode 100644
index 7a57c76..0000000
--- a/libdimension/bvst.c
+++ /dev/null
@@ -1,388 +0,0 @@
-/*************************************************************************
- * Copyright (C) 2010 Tavian Barnes <tavianator@gmail.com> *
- * *
- * This file is part of The Dimension Library. *
- * *
- * The Dimension Library is free software; you can redistribute it and/ *
- * or modify it under the terms of the GNU Lesser General Public License *
- * as published by the Free Software Foundation; either version 3 of the *
- * License, or (at your option) any later version. *
- * *
- * The Dimension Library is distributed in the hope that it will be *
- * useful, but WITHOUT ANY WARRANTY; without even the implied warranty *
- * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
- * Lesser General Public License for more details. *
- * *
- * You should have received a copy of the GNU Lesser General Public *
- * License along with this program. If not, see *
- * <http://www.gnu.org/licenses/>. *
- *************************************************************************/
-
-#include "dimension_impl.h"
-#include <stdlib.h>
-
-/* Return an empty tree */
-dmnsn_bvst *
-dmnsn_new_bvst()
-{
- dmnsn_bvst *tree = dmnsn_malloc(sizeof(dmnsn_bvst));
- tree->root = NULL;
- return tree;
-}
-
-static dmnsn_bvst_node *
-dmnsn_new_bvst_node()
-{
- dmnsn_bvst_node *node = dmnsn_malloc(sizeof(dmnsn_bvst_node));
- return node;
-}
-
-/* Recursively copy the nodes of a BVST */
-static dmnsn_bvst_node *
-dmnsn_bvst_copy_recursive(dmnsn_bvst_node *root)
-{
- dmnsn_bvst_node *node = dmnsn_new_bvst_node();
- *node = *root;
- if (node->contains) {
- node->contains = dmnsn_bvst_copy_recursive(node->contains);
- node->contains->parent = node;
- }
- if (node->container) {
- node->container = dmnsn_bvst_copy_recursive(node->container);
- node->container->parent = node;
- }
- return node;
-}
-
-/* Copy a BVST */
-dmnsn_bvst *
-dmnsn_copy_bvst(dmnsn_bvst *tree)
-{
- dmnsn_bvst *copy = dmnsn_new_bvst();
- if (tree->root)
- copy->root = dmnsn_bvst_copy_recursive(tree->root);
- else
- copy->root = NULL;
- return copy;
-}
-
-static void
-dmnsn_delete_bvst_node(dmnsn_bvst_node *node)
-{
- free(node);
-}
-
-/* Recursively free a BVST */
-static void
-dmnsn_delete_bvst_recursive(dmnsn_bvst_node *node)
-{
- if (node) {
- dmnsn_delete_bvst_recursive(node->contains);
- dmnsn_delete_bvst_recursive(node->container);
- dmnsn_delete_bvst_node(node);
- }
-}
-
-/* Free a BVST */
-void
-dmnsn_delete_bvst(dmnsn_bvst *tree)
-{
- if (tree) {
- dmnsn_delete_bvst_recursive(tree->root);
- free(tree);
- }
-}
-
-/* Expand node to contain the bounding box from min to max */
-static void dmnsn_bvst_node_swallow(dmnsn_bvst_node *node,
- dmnsn_bounding_box box);
-
-/* Insert an object into the tree */
-void
-dmnsn_bvst_insert(dmnsn_bvst *tree, dmnsn_object *object)
-{
- dmnsn_object_precompute(object);
-
- dmnsn_bvst_node *node = dmnsn_new_bvst_node(), *parent = tree->root;
-
- node->contains = NULL;
- node->container = NULL;
- node->parent = NULL;
- node->object = object;
- node->bounding_box = object->bounding_box;
-
- /* Now insert the node */
-
- while (parent) {
- if (dmnsn_bounding_box_contains(parent->bounding_box,
- node->bounding_box.min)
- && dmnsn_bounding_box_contains(parent->bounding_box,
- node->bounding_box.max))
- {
- /* parent fully contains node */
- if (parent->contains) {
- parent = parent->contains;
- } else {
- /* We found our parent; insert node into the tree */
- parent->contains = node;
- node->parent = parent;
- break;
- }
- } else {
- /* Expand node's bounding box to fully contain parent's if it doesn't
- already */
- dmnsn_bvst_node_swallow(node, parent->bounding_box);
- /* node now fully contains parent */
- if (parent->container) {
- parent = parent->container;
- } else {
- /* We found our parent; insert node into the tree */
- parent->container = node;
- node->parent = parent;
- break;
- }
- }
- }
-
- dmnsn_bvst_splay(tree, node);
-}
-
-/* Expand node to contain the bounding box from min to max */
-static void
-dmnsn_bvst_node_swallow(dmnsn_bvst_node *node, dmnsn_bounding_box box)
-{
- node->bounding_box.min = dmnsn_vector_min(node->bounding_box.min, box.min);
- node->bounding_box.max = dmnsn_vector_max(node->bounding_box.max, box.max);
-}
-
-/* Tree rotations */
-static void dmnsn_bvst_rotate(dmnsn_bvst_node *node);
-
-/* Splay a node: move it to the root via tree rotations */
-void
-dmnsn_bvst_splay(dmnsn_bvst *tree, dmnsn_bvst_node *node)
-{
- while (node->parent) {
- if (!node->parent->parent) {
- /* Zig step - we are a child of the root node */
- dmnsn_bvst_rotate(node);
- break;
- } else if ((node == node->parent->contains
- && node->parent == node->parent->parent->contains)
- || (node == node->parent->container
- && node->parent == node->parent->parent->container)) {
- /* Zig-zig step - we are a child on the same side as our parent */
- dmnsn_bvst_rotate(node->parent);
- dmnsn_bvst_rotate(node);
- } else {
- /* Zig-zag step - we are a child on a different side than our parent is */
- dmnsn_bvst_rotate(node);
- dmnsn_bvst_rotate(node);
- }
- }
- tree->root = node;
-}
-
-/* Rotate a tree on the edge connecting node and node->parent */
-static void
-dmnsn_bvst_rotate(dmnsn_bvst_node *node)
-{
- dmnsn_bvst_node *P, *Q, *B;
- if (node == node->parent->contains) {
- /* We are a left child; perform a right rotation:
- *
- * Q P
- * / \ / \
- * P C ---> A Q
- * / \ / \
- * A B B C
- */
- Q = node->parent;
- P = node;
- /* A = node->contains; */
- B = node->container;
- /* C = node->parent->container; */
-
- /* First fix up the parents */
- if (Q->parent) {
- if (Q->parent->contains == Q)
- Q->parent->contains = P;
- else
- Q->parent->container = P;
- }
- P->parent = Q->parent;
- Q->parent = P;
- if (B) B->parent = Q;
-
- /* Then the children */
- P->container = Q;
- Q->contains = B;
- } else {
- /* We are a right child; perform a left rotation:
- *
- * P Q
- * / \ / \
- * A Q ---> P C
- * / \ / \
- * B C A B
- */
- P = node->parent;
- Q = node;
- /* A = node->parent->contains; */
- B = node->contains;
- /* C = node->container; */
-
- /* First fix up the parents */
- if (P->parent) {
- if (P->parent->contains == P)
- P->parent->contains = Q;
- else
- P->parent->container = Q;
- }
- Q->parent = P->parent;
- P->parent = Q;
- if (B) B->parent = P;
-
- /* Then the children */
- Q->contains = P;
- P->container = B;
- }
-}
-
-typedef struct {
- dmnsn_bvst_node *node;
- bool intersected;
- dmnsn_intersection intersection;
-} dmnsn_bvst_search_result;
-
-static dmnsn_bvst_search_result
-dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t);
-
-bool
-dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray,
- dmnsn_intersection *intersection)
-{
- dmnsn_bvst_search_result result
- = dmnsn_bvst_search_recursive(tree->root, ray, -1.0);
-
- if (result.intersected) {
- dmnsn_bvst_splay(tree, result.node);
- *intersection = result.intersection;
- }
-
- return result.intersected;
-}
-
-static bool dmnsn_ray_box_intersection(dmnsn_line ray, dmnsn_bounding_box box,
- double t);
-
-static dmnsn_bvst_search_result
-dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t)
-{
- dmnsn_bvst_search_result result_temp, result = {
- .node = NULL,
- .intersected = false
- };
-
- 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_bvst_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;
- }
-
- if (dmnsn_bounding_box_contains(node->bounding_box, ray.x0)
- || dmnsn_ray_box_intersection(ray, node->bounding_box, t))
- {
- if (dmnsn_bounding_box_contains(node->object->bounding_box, ray.x0)
- || dmnsn_ray_box_intersection(ray, node->object->bounding_box, t))
- {
- result_temp.intersected =
- (*node->object->intersection_fn)(node->object, ray,
- &result_temp.intersection);
-
- if (result_temp.intersected
- && (t < 0.0 || result_temp.intersection.t < t)) {
- result.node = node;
- result.intersected = true;
- result.intersection = result_temp.intersection;
- t = result.intersection.t;
- }
- }
-
- /* Go down the left subtree */
- result_temp = dmnsn_bvst_search_recursive(node->contains, ray, t);
- if (result_temp.node && (t < 0.0 || result_temp.intersection.t < t)) {
- result = result_temp;
- }
- }
-
- return result;
-}
-
-static bool
-dmnsn_ray_box_intersection(dmnsn_line line, dmnsn_bounding_box box, double t)
-{
- double t_temp;
- dmnsn_vector p;
-
- if (line.n.x != 0.0) {
- /* x == box.min.x */
- t_temp = (box.min.x - line.x0.x)/line.n.x;
- p = dmnsn_line_point(line, t_temp);
- if (p.y >= box.min.y && p.y <= box.max.y
- && p.z >= box.min.z && p.z <= box.max.z
- && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
- return true;
-
- /* x == box.max.x */
- t_temp = (box.max.x - line.x0.x)/line.n.x;
- p = dmnsn_line_point(line, t_temp);
- if (p.y >= box.min.y && p.y <= box.max.y
- && p.z >= box.min.z && p.z <= box.max.z
- && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
- return true;
- }
-
- if (line.n.y != 0.0) {
- /* y == box.min.y */
- t_temp = (box.min.y - line.x0.y)/line.n.y;
- p = dmnsn_line_point(line, t_temp);
- if (p.x >= box.min.x && p.x <= box.max.x
- && p.z >= box.min.z && p.z <= box.max.z
- && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
- return true;
-
- /* y == box.max.y */
- t_temp = (box.max.y - line.x0.y)/line.n.y;
- p = dmnsn_line_point(line, t_temp);
- if (p.x >= box.min.x && p.x <= box.max.x
- && p.z >= box.min.z && p.z <= box.max.z
- && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
- return true;
- }
-
- if (line.n.z != 0.0) {
- /* z == box.min.z */
- t_temp = (box.min.z - line.x0.z)/line.n.z;
- p = dmnsn_line_point(line, t_temp);
- if (p.x >= box.min.x && p.x <= box.max.x
- && p.y >= box.min.y && p.y <= box.max.y
- && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
- return true;
-
- /* z == box.max.z */
- t_temp = (box.max.z - line.x0.z)/line.n.z;
- p = dmnsn_line_point(line, t_temp);
- if (p.x >= box.min.x && p.x <= box.max.x
- && p.y >= box.min.y && p.y <= box.max.y
- && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
- return true;
- }
-
- return false;
-}
diff --git a/libdimension/dimension_impl.h b/libdimension/dimension_impl.h
index 9fa2ef6..3c3283c 100644
--- a/libdimension/dimension_impl.h
+++ b/libdimension/dimension_impl.h
@@ -22,6 +22,6 @@
#define DIMENSION_IMPL_H
#include "dimension.h"
-#include "bvst.h"
+#include "prtree.h"
#endif /* DIMENSION_IMPL_H */
diff --git a/libdimension/prtree.c b/libdimension/prtree.c
new file mode 100644
index 0000000..a40100c
--- /dev/null
+++ b/libdimension/prtree.c
@@ -0,0 +1,574 @@
+/*************************************************************************
+ * Copyright (C) 2010 Tavian Barnes <tavianator@gmail.com> *
+ * *
+ * This file is part of The Dimension Library. *
+ * *
+ * The Dimension Library is free software; you can redistribute it and/ *
+ * or modify it under the terms of the GNU Lesser General Public License *
+ * as published by the Free Software Foundation; either version 3 of the *
+ * License, or (at your option) any later version. *
+ * *
+ * The Dimension Library is distributed in the hope that it will be *
+ * useful, but WITHOUT ANY WARRANTY; without even the implied warranty *
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
+ * Lesser General Public License for more details. *
+ * *
+ * You should have received a copy of the GNU Lesser General Public *
+ * License along with this program. If not, see *
+ * <http://www.gnu.org/licenses/>. *
+ *************************************************************************/
+
+#include "dimension_impl.h"
+#include <stdlib.h>
+
+typedef struct dmnsn_pseudo_prtree dmnsn_pseudo_prtree;
+
+typedef struct dmnsn_pseudo_prleaf {
+ void *children[DMNSN_PRTREE_B];
+ bool is_leaf;
+ dmnsn_bounding_box bounding_box;
+} dmnsn_pseudo_prleaf;
+
+typedef struct dmnsn_pseudo_prnode {
+ dmnsn_pseudo_prtree *left, *right;
+ dmnsn_pseudo_prleaf children[6];
+} dmnsn_pseudo_prnode;
+
+struct dmnsn_pseudo_prtree {
+ bool is_leaf;
+ union {
+ dmnsn_pseudo_prleaf leaf;
+ dmnsn_pseudo_prnode node;
+ };
+};
+
+/* Expand node to contain the bounding box from min to max */
+static void
+dmnsn_pseudo_prleaf_swallow(dmnsn_pseudo_prleaf *leaf, dmnsn_bounding_box box)
+{
+ leaf->bounding_box.min = dmnsn_vector_min(leaf->bounding_box.min, box.min);
+ leaf->bounding_box.max = dmnsn_vector_max(leaf->bounding_box.max, box.max);
+}
+
+/* Comparator types */
+enum {
+ DMNSN_XMIN,
+ DMNSN_YMIN,
+ DMNSN_ZMIN,
+ DMNSN_XMAX,
+ DMNSN_YMAX,
+ DMNSN_ZMAX
+};
+
+static double
+dmnsn_priority_get(dmnsn_list_iterator *i, bool is_object, int comparator)
+{
+ dmnsn_bounding_box box;
+
+ if (is_object) {
+ dmnsn_object *object;
+ dmnsn_list_get(i, &object);
+ box = object->bounding_box;
+ } else {
+ dmnsn_prtree *prnode;
+ dmnsn_list_get(i, &prnode);
+ box = prnode->bounding_box;
+ }
+
+ switch (comparator) {
+ case DMNSN_XMIN:
+ return box.min.x;
+ case DMNSN_YMIN:
+ return box.min.y;
+ case DMNSN_ZMIN:
+ return box.min.z;
+
+ case DMNSN_XMAX:
+ return -box.max.x;
+ case DMNSN_YMAX:
+ return -box.max.y;
+ case DMNSN_ZMAX:
+ return -box.max.z;
+
+ default:
+ dmnsn_assert(false, "Invalid comparator.");
+ return 0.0;
+ }
+}
+
+/* List sorting comparators */
+
+static bool
+dmnsn_xmin_object_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+ double lval = dmnsn_priority_get(l, true, DMNSN_XMIN);
+ double rval = dmnsn_priority_get(r, true, DMNSN_XMIN);
+ return lval < rval;
+}
+
+static bool
+dmnsn_xmin_prnode_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+ double lval = dmnsn_priority_get(l, false, DMNSN_XMIN);
+ double rval = dmnsn_priority_get(r, false, DMNSN_XMIN);
+ return lval < rval;
+}
+
+static bool
+dmnsn_ymin_object_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+ double lval = dmnsn_priority_get(l, true, DMNSN_YMIN);
+ double rval = dmnsn_priority_get(r, true, DMNSN_YMIN);
+ return lval < rval;
+}
+
+static bool
+dmnsn_ymin_prnode_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+ double lval = dmnsn_priority_get(l, false, DMNSN_YMIN);
+ double rval = dmnsn_priority_get(r, false, DMNSN_YMIN);
+ return lval < rval;
+}
+
+static bool
+dmnsn_zmin_object_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+ double lval = dmnsn_priority_get(l, true, DMNSN_ZMIN);
+ double rval = dmnsn_priority_get(r, true, DMNSN_ZMIN);
+ return lval < rval;
+}
+
+static bool
+dmnsn_zmin_prnode_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+ double lval = dmnsn_priority_get(l, false, DMNSN_ZMIN);
+ double rval = dmnsn_priority_get(r, false, DMNSN_ZMIN);
+ return lval < rval;
+}
+
+static bool
+dmnsn_xmax_object_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+ double lval = dmnsn_priority_get(l, true, DMNSN_XMAX);
+ double rval = dmnsn_priority_get(r, true, DMNSN_XMAX);
+ return lval < rval;
+}
+
+static bool
+dmnsn_xmax_prnode_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+ double lval = dmnsn_priority_get(l, false, DMNSN_XMAX);
+ double rval = dmnsn_priority_get(r, false, DMNSN_XMAX);
+ return lval < rval;
+}
+
+static bool
+dmnsn_ymax_object_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+ double lval = dmnsn_priority_get(l, true, DMNSN_YMAX);
+ double rval = dmnsn_priority_get(r, true, DMNSN_YMAX);
+ return lval < rval;
+}
+
+static bool
+dmnsn_ymax_prnode_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+ double lval = dmnsn_priority_get(l, false, DMNSN_YMAX);
+ double rval = dmnsn_priority_get(r, false, DMNSN_YMAX);
+ return lval < rval;
+}
+
+static bool
+dmnsn_zmax_object_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+ double lval = dmnsn_priority_get(l, true, DMNSN_ZMAX);
+ double rval = dmnsn_priority_get(r, true, DMNSN_ZMAX);
+ return lval < rval;
+}
+
+static bool
+dmnsn_zmax_prnode_comp(dmnsn_list_iterator *l, dmnsn_list_iterator *r)
+{
+ double lval = dmnsn_priority_get(l, false, DMNSN_ZMAX);
+ double rval = dmnsn_priority_get(r, false, DMNSN_ZMAX);
+ return lval < rval;
+}
+
+static dmnsn_comparator_fn *dmnsn_object_comparators[6] = {
+ [DMNSN_XMIN] = &dmnsn_xmin_object_comp,
+ [DMNSN_YMIN] = &dmnsn_ymin_object_comp,
+ [DMNSN_ZMIN] = &dmnsn_zmin_object_comp,
+ [DMNSN_XMAX] = &dmnsn_xmax_object_comp,
+ [DMNSN_YMAX] = &dmnsn_ymax_object_comp,
+ [DMNSN_ZMAX] = &dmnsn_zmax_object_comp
+};
+
+static dmnsn_comparator_fn *dmnsn_prnode_comparators[6] = {
+ [DMNSN_XMIN] = &dmnsn_xmin_prnode_comp,
+ [DMNSN_YMIN] = &dmnsn_ymin_prnode_comp,
+ [DMNSN_ZMIN] = &dmnsn_zmin_prnode_comp,
+ [DMNSN_XMAX] = &dmnsn_xmax_prnode_comp,
+ [DMNSN_YMAX] = &dmnsn_ymax_prnode_comp,
+ [DMNSN_ZMAX] = &dmnsn_zmax_prnode_comp
+};
+
+static dmnsn_list_iterator *
+dmnsn_priority_search(dmnsn_list *leaves, bool are_objects, int comparator)
+{
+ dmnsn_list_iterator *i = dmnsn_list_first(leaves);
+ if (i) {
+ double candidate = dmnsn_priority_get(i, are_objects, comparator);
+
+ dmnsn_list_iterator *j;
+ for (j = dmnsn_list_next(i); j != NULL; j = dmnsn_list_next(j)) {
+ double new_candidate = dmnsn_priority_get(j, are_objects, comparator);
+ if (new_candidate < candidate) {
+ candidate = new_candidate;
+ i = j;
+ }
+ }
+ }
+
+ return i;
+}
+
+/* Build a pseudo PR-tree */
+static dmnsn_pseudo_prtree *
+dmnsn_new_pseudo_prtree(dmnsn_list *leaves, bool are_objects, int comparator)
+{
+ dmnsn_pseudo_prtree *pseudo = dmnsn_malloc(sizeof(dmnsn_pseudo_prtree));
+
+ if (dmnsn_list_size(leaves) <= DMNSN_PRTREE_B) {
+ /* Make a leaf */
+ pseudo->is_leaf = true;
+ pseudo->leaf.bounding_box.min = dmnsn_zero;
+ pseudo->leaf.bounding_box.max = dmnsn_zero;
+
+ size_t i;
+ dmnsn_list_iterator *ii;
+ if (are_objects) {
+ pseudo->leaf.is_leaf = true;
+ for (i = 0, ii = dmnsn_list_first(leaves);
+ ii != NULL;
+ ++i, ii = dmnsn_list_next(ii))
+ {
+ dmnsn_object *object;
+ dmnsn_list_get(ii, &object);
+
+ pseudo->leaf.children[i] = object;
+ if (i == 0) {
+ pseudo->leaf.bounding_box = object->bounding_box;
+ } else {
+ dmnsn_pseudo_prleaf_swallow(&pseudo->leaf, object->bounding_box);
+ }
+ }
+ } else {
+ pseudo->leaf.is_leaf = false;
+ for (i = 0, ii = dmnsn_list_first(leaves);
+ ii != NULL;
+ ++i, ii = dmnsn_list_next(ii))
+ {
+ dmnsn_prtree *prnode;
+ dmnsn_list_get(ii, &prnode);
+
+ pseudo->leaf.children[i] = prnode;
+ if (i == 0) {
+ pseudo->leaf.bounding_box = prnode->bounding_box;
+ } else {
+ dmnsn_pseudo_prleaf_swallow(&pseudo->leaf, prnode->bounding_box);
+ }
+ }
+ }
+
+ for (; i < DMNSN_PRTREE_B; ++i) {
+ pseudo->leaf.children[i] = NULL;
+ }
+ } else {
+ /* Make an internal node */
+ pseudo->is_leaf = false;
+ size_t i;
+ for (i = 0; i < 6; ++i) {
+ pseudo->node.children[i].is_leaf = are_objects;
+ }
+
+ /* Fill the priority leaves */
+ size_t j;
+ for (i = 0; i < DMNSN_PRTREE_B; ++i) {
+ for (j = 0; j < 6; ++j) {
+ dmnsn_list_iterator *k = dmnsn_priority_search(leaves, are_objects, j);
+ if (!k)
+ break;
+
+ if (are_objects) {
+ dmnsn_object *object;
+ dmnsn_list_get(k, &object);
+ pseudo->node.children[j].children[i] = object;
+ if (i == 0) {
+ pseudo->node.children[j].bounding_box = object->bounding_box;
+ } else {
+ dmnsn_pseudo_prleaf_swallow(&pseudo->node.children[j],
+ object->bounding_box);
+ }
+ } else {
+ dmnsn_prtree *prnode;
+ dmnsn_list_get(k, &prnode);
+ pseudo->node.children[j].children[i] = prnode;
+ if (i == 0) {
+ pseudo->node.children[j].bounding_box = prnode->bounding_box;
+ } else {
+ dmnsn_pseudo_prleaf_swallow(&pseudo->node.children[j],
+ prnode->bounding_box);
+ }
+ }
+
+ dmnsn_list_remove(leaves, k);
+ }
+
+ if (dmnsn_list_size(leaves) == 0)
+ break;
+ }
+
+ /* Set remaining space in the priority leaves to NULL */
+ for (; i < DMNSN_PRTREE_B; ++i) {
+ for (; j < 6; ++j) {
+ if (i == 0) {
+ pseudo->node.children[j].bounding_box.min = dmnsn_zero;
+ pseudo->node.children[j].bounding_box.max = dmnsn_zero;
+ }
+ pseudo->node.children[j].children[i] = NULL;
+ }
+ j = 0;
+ }
+
+ /* Recursively build the subtrees */
+ if (are_objects)
+ dmnsn_list_sort(leaves, dmnsn_object_comparators[comparator]);
+ else
+ dmnsn_list_sort(leaves, dmnsn_prnode_comparators[comparator]);
+
+ dmnsn_list *half = dmnsn_list_split(leaves);
+ pseudo->node.left
+ = dmnsn_new_pseudo_prtree(leaves, are_objects, (comparator + 1)%6);
+ pseudo->node.right
+ = dmnsn_new_pseudo_prtree(half, are_objects, (comparator + 1)%6);
+ dmnsn_delete_list(half);
+ }
+
+ return pseudo;
+}
+
+static void
+dmnsn_delete_pseudo_prtree(dmnsn_pseudo_prtree *pseudo)
+{
+ if (pseudo) {
+ if (!pseudo->is_leaf) {
+ dmnsn_delete_pseudo_prtree(pseudo->node.left);
+ dmnsn_delete_pseudo_prtree(pseudo->node.right);
+ }
+ free(pseudo);
+ }
+}
+
+/* Construct a node from a pseudo leaf */
+static dmnsn_prtree *
+dmnsn_new_prtree_node(const dmnsn_pseudo_prleaf *leaf)
+{
+ dmnsn_prtree *node = dmnsn_malloc(sizeof(dmnsn_prtree));
+ node->is_leaf = leaf->is_leaf;
+ node->bounding_box = leaf->bounding_box;
+
+ size_t i;
+ for (i = 0; i < DMNSN_PRTREE_B; ++i) {
+ node->children[i] = leaf->children[i];
+ }
+
+ return node;
+}
+
+static void
+dmnsn_pseudo_prtree_add_leaf(const dmnsn_pseudo_prleaf *leaf,
+ dmnsn_list *leaves)
+{
+ /* Don't add empty leaves */
+ if (leaf->children[0]) {
+ dmnsn_prtree *prnode = dmnsn_new_prtree_node(leaf);
+ dmnsn_list_push(leaves, &prnode);
+ }
+}
+
+static void
+dmnsn_pseudo_prtree_leaves_recursive(const dmnsn_pseudo_prtree *node,
+ dmnsn_list *leaves)
+{
+ if (node->is_leaf) {
+ dmnsn_pseudo_prtree_add_leaf(&node->leaf, leaves);
+ } else {
+ size_t i;
+ for (i = 0; i < 6; ++i) {
+ dmnsn_pseudo_prtree_add_leaf(&node->node.children[i], leaves);
+ }
+ dmnsn_pseudo_prtree_leaves_recursive(node->node.left, leaves);
+ dmnsn_pseudo_prtree_leaves_recursive(node->node.right, leaves);
+ }
+}
+
+/* Extract the leaves of a pseudo PR-tree */
+static dmnsn_list *
+dmnsn_pseudo_prtree_leaves(const dmnsn_pseudo_prtree *pseudo)
+{
+ dmnsn_list *leaves = dmnsn_new_list(sizeof(dmnsn_prtree *));
+ dmnsn_pseudo_prtree_leaves_recursive(pseudo, leaves);
+ return leaves;
+}
+
+/* Construct a PR-tree from a bulk of objects */
+dmnsn_prtree *
+dmnsn_new_prtree(const dmnsn_array *objects)
+{
+ size_t i;
+ for (i = 0; i < dmnsn_array_size(objects); ++i) {
+ dmnsn_object *object;
+ dmnsn_array_get(objects, i, &object);
+ dmnsn_object_precompute(object);
+ }
+
+ dmnsn_list *leaves = dmnsn_list_from_array(objects);
+ dmnsn_pseudo_prtree *pseudo = dmnsn_new_pseudo_prtree(leaves, true, 0);
+ dmnsn_delete_list(leaves);
+ leaves = dmnsn_pseudo_prtree_leaves(pseudo);
+ dmnsn_delete_pseudo_prtree(pseudo);
+
+ while (dmnsn_list_size(leaves) > 1) {
+ pseudo = dmnsn_new_pseudo_prtree(leaves, false, 0);
+ dmnsn_delete_list(leaves);
+ leaves = dmnsn_pseudo_prtree_leaves(pseudo);
+ dmnsn_delete_pseudo_prtree(pseudo);
+ }
+
+ dmnsn_prtree *root;
+ dmnsn_list_get(dmnsn_list_first(leaves), &root);
+ dmnsn_delete_list(leaves);
+ return root;
+}
+
+/* Free a PR-tree */
+void
+dmnsn_delete_prtree(dmnsn_prtree *tree)
+{
+ if (tree) {
+ if (!tree->is_leaf) {
+ size_t i;
+ for (i = 0; i < DMNSN_PRTREE_B; ++i) {
+ dmnsn_delete_prtree(tree->children[i]);
+ }
+ }
+ free(tree);
+ }
+}
+
+static bool dmnsn_ray_box_intersection(dmnsn_line ray, dmnsn_bounding_box box,
+ double t);
+
+static void
+dmnsn_prtree_search_recursive(const dmnsn_prtree *node, dmnsn_line ray,
+ dmnsn_intersection *intersection, double *t)
+{
+ if (dmnsn_ray_box_intersection(ray, node->bounding_box, *t)) {
+ size_t i;
+ for (i = 0; i < DMNSN_PRTREE_B; ++i) {
+ if (!node->children[i])
+ break;
+
+ if (node->is_leaf) {
+ dmnsn_object *object = node->children[i];
+
+ dmnsn_intersection local_intersection;
+ if (dmnsn_ray_box_intersection(ray, object->bounding_box, *t)) {
+ if ((*object->intersection_fn)(object, ray, &local_intersection)) {
+ if (*t < 0.0 || local_intersection.t < *t) {
+ *intersection = local_intersection;
+ *t = local_intersection.t;
+ }
+ }
+ }
+ } else {
+ dmnsn_prtree_search_recursive(node->children[i], ray, intersection, t);
+ }
+ }
+ }
+}
+
+bool
+dmnsn_prtree_search(const dmnsn_prtree *tree, dmnsn_line ray,
+ dmnsn_intersection *intersection)
+{
+ double t = -1;
+ dmnsn_prtree_search_recursive(tree, ray, intersection, &t);
+ return t >= 0.0;
+}
+
+static bool
+dmnsn_ray_box_intersection(dmnsn_line line, dmnsn_bounding_box box, double t)
+{
+ if (dmnsn_bounding_box_contains(box, line.x0))
+ return true;
+
+ double t_temp;
+ dmnsn_vector p;
+
+ if (line.n.x != 0.0) {
+ /* x == box.min.x */
+ t_temp = (box.min.x - line.x0.x)/line.n.x;
+ p = dmnsn_line_point(line, t_temp);
+ if (p.y >= box.min.y && p.y <= box.max.y
+ && p.z >= box.min.z && p.z <= box.max.z
+ && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+ return true;
+
+ /* x == box.max.x */
+ t_temp = (box.max.x - line.x0.x)/line.n.x;
+ p = dmnsn_line_point(line, t_temp);
+ if (p.y >= box.min.y && p.y <= box.max.y
+ && p.z >= box.min.z && p.z <= box.max.z
+ && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+ return true;
+ }
+
+ if (line.n.y != 0.0) {
+ /* y == box.min.y */
+ t_temp = (box.min.y - line.x0.y)/line.n.y;
+ p = dmnsn_line_point(line, t_temp);
+ if (p.x >= box.min.x && p.x <= box.max.x
+ && p.z >= box.min.z && p.z <= box.max.z
+ && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+ return true;
+
+ /* y == box.max.y */
+ t_temp = (box.max.y - line.x0.y)/line.n.y;
+ p = dmnsn_line_point(line, t_temp);
+ if (p.x >= box.min.x && p.x <= box.max.x
+ && p.z >= box.min.z && p.z <= box.max.z
+ && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+ return true;
+ }
+
+ if (line.n.z != 0.0) {
+ /* z == box.min.z */
+ t_temp = (box.min.z - line.x0.z)/line.n.z;
+ p = dmnsn_line_point(line, t_temp);
+ if (p.x >= box.min.x && p.x <= box.max.x
+ && p.y >= box.min.y && p.y <= box.max.y
+ && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+ return true;
+
+ /* z == box.max.z */
+ t_temp = (box.max.z - line.x0.z)/line.n.z;
+ p = dmnsn_line_point(line, t_temp);
+ if (p.x >= box.min.x && p.x <= box.max.x
+ && p.y >= box.min.y && p.y <= box.max.y
+ && t_temp >= 0.0 && (t < 0.0 || t_temp < t))
+ return true;
+ }
+
+ return false;
+}
diff --git a/libdimension/bvst.h b/libdimension/prtree.h
index d300cf9..999bc14 100644
--- a/libdimension/bvst.h
+++ b/libdimension/prtree.h
@@ -19,48 +19,33 @@
*************************************************************************/
/*
- * Bounding Volume Splay Trees for storing object bounding boxes.
- * Each node's bounding box entirely contains the bounding boxes of the nodes
- * to its left, and is entirely contained by the bounding boxes of the nodes to
- * its right. Splay trees are used for the implementation, to bring commonly-
- * used objects (the most recent object which a ray has hit) near the root of
- * the tree for fast access. Object's bounding boxes are expanded as needed
- * when inserted into the tree: if they intersect an existing bounding box, they
- * are expanded to contain it.
+ * Priority R-Trees for storing bounding box hierarchies. PR-trees are a data
+ * structure introduced by Arge, de Berg, Haverkort, and Yi, which provides
+ * asymptotically optimal worst-case lookup, while remaining efficient with real-world
+ * data. Their structure is derived from B-trees.
*/
-#ifndef DIMENSION_IMPL_BVST_H
-#define DIMENSION_IMPL_BVST_H
+#ifndef DIMENSION_IMPL_PRTREE_H
+#define DIMENSION_IMPL_PRTREE_H
-typedef struct dmnsn_bvst dmnsn_bvst;
-typedef struct dmnsn_bvst_node dmnsn_bvst_node;
+#include <stdbool.h>
-struct dmnsn_bvst {
- dmnsn_bvst_node *root;
-};
+/* Number of children per node */
+#define DMNSN_PRTREE_B 6
-struct dmnsn_bvst_node {
- /* Tree children */
- dmnsn_bvst_node *contains, *container;
-
- /* Parent node for easy backtracking */
- dmnsn_bvst_node *parent;
+typedef struct dmnsn_prtree {
+ /* Children (objects or subtrees) */
+ void *children[DMNSN_PRTREE_B];
+ bool is_leaf;
/* Bounding box */
dmnsn_bounding_box bounding_box;
+} dmnsn_prtree;
- /* Node payload */
- dmnsn_object *object;
-};
-
-dmnsn_bvst *dmnsn_new_bvst();
-dmnsn_bvst *dmnsn_copy_bvst(dmnsn_bvst *tree);
-void dmnsn_delete_bvst(dmnsn_bvst *tree);
-
-void dmnsn_bvst_insert(dmnsn_bvst *tree, dmnsn_object *object);
-void dmnsn_bvst_splay(dmnsn_bvst *tree, dmnsn_bvst_node *node);
+dmnsn_prtree *dmnsn_new_prtree(const dmnsn_array *objects);
+void dmnsn_delete_prtree(dmnsn_prtree *tree);
-bool dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray,
- dmnsn_intersection *intersection);
+bool dmnsn_prtree_search(const dmnsn_prtree *tree, dmnsn_line ray,
+ dmnsn_intersection *intersection);
-#endif /* DIMENSION_IMPL_BVST_H */
+#endif /* DIMENSION_IMPL_PRTREE_H */
diff --git a/libdimension/raytrace.c b/libdimension/raytrace.c
index eb2f052..8946303 100644
--- a/libdimension/raytrace.c
+++ b/libdimension/raytrace.c
@@ -30,7 +30,7 @@
typedef struct {
dmnsn_progress *progress;
dmnsn_scene *scene;
- dmnsn_bvst *bvst;
+ dmnsn_prtree *prtree;
/* For multithreading */
unsigned int index, threads;
@@ -57,14 +57,6 @@ dmnsn_raytrace_scene_async(dmnsn_scene *scene)
= dmnsn_malloc(sizeof(dmnsn_raytrace_payload));
payload->progress = progress;
payload->scene = scene;
- payload->bvst = dmnsn_new_bvst();
-
- unsigned int i;
- for (i = 0; i < dmnsn_array_size(payload->scene->objects); ++i) {
- dmnsn_object *object;
- dmnsn_array_get(payload->scene->objects, i, &object);
- dmnsn_bvst_insert(payload->bvst, object);
- }
if (pthread_create(&progress->thread, NULL, &dmnsn_raytrace_scene_thread,
payload) != 0)
@@ -83,7 +75,9 @@ static void *
dmnsn_raytrace_scene_thread(void *ptr)
{
dmnsn_raytrace_payload *payload = ptr;
+ payload->prtree = dmnsn_new_prtree(payload->scene->objects);
dmnsn_raytrace_scene_multithread(payload);
+ dmnsn_delete_prtree(payload->prtree);
dmnsn_done_progress(payload->progress);
free(payload);
@@ -120,9 +114,6 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload)
payloads[i] = *payload;
payloads[i].index = i;
payloads[i].threads = nthreads;
- if (i > 0) {
- payloads[i].bvst = dmnsn_copy_bvst(payloads[0].bvst);
- }
}
/* Create the threads */
@@ -140,8 +131,6 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload)
if (pthread_join(threads[i], NULL)) {
dmnsn_error(DMNSN_SEVERITY_MEDIUM,
"Couldn't join worker thread in raytrace engine.");
- } else {
- dmnsn_delete_bvst(payloads[i].bvst);
}
}
@@ -152,7 +141,7 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload)
/* Actual raytracing implementation */
static void dmnsn_raytrace_scene_impl(dmnsn_progress *progress,
dmnsn_scene *scene,
- dmnsn_bvst *bvst,
+ dmnsn_prtree *prtree,
unsigned int index, unsigned int threads);
/* Multi-threading thread callback */
@@ -161,7 +150,7 @@ dmnsn_raytrace_scene_multithread_thread(void *ptr)
{
dmnsn_raytrace_payload *payload = ptr;
dmnsn_raytrace_scene_impl(payload->progress, payload->scene,
- payload->bvst, payload->index, payload->threads);
+ payload->prtree, payload->index, payload->threads);
return NULL;
}
@@ -174,7 +163,7 @@ typedef struct dmnsn_raytrace_state {
const dmnsn_scene *scene;
const dmnsn_intersection *intersection;
- dmnsn_bvst *bvst;
+ dmnsn_prtree *prtree;
unsigned int reclevel;
dmnsn_vector r;
@@ -195,13 +184,13 @@ static dmnsn_color dmnsn_raytrace_shoot(dmnsn_raytrace_state *state,
/* Actually raytrace a scene */
static void
dmnsn_raytrace_scene_impl(dmnsn_progress *progress, dmnsn_scene *scene,
- dmnsn_bvst *bvst,
+ dmnsn_prtree *prtree,
unsigned int index, unsigned int threads)
{
dmnsn_raytrace_state state = {
.parent = NULL,
.scene = scene,
- .bvst = bvst,
+ .prtree = prtree,
.ior = 1.0
};
@@ -289,7 +278,7 @@ dmnsn_raytrace_light_ray(const dmnsn_raytrace_state *state,
while (reclevel) {
dmnsn_intersection shadow_caster;
bool shadow_casted
- = dmnsn_bvst_search(state->bvst, shadow_ray, &shadow_caster);
+ = dmnsn_prtree_search(state->prtree, shadow_ray, &shadow_caster);
if (!shadow_casted || shadow_caster.t > 1.0) {
break;
@@ -450,7 +439,7 @@ dmnsn_raytrace_shoot(dmnsn_raytrace_state *state, dmnsn_line ray)
--state->reclevel;
dmnsn_intersection intersection;
- bool intersected = dmnsn_bvst_search(state->bvst, ray, &intersection);
+ bool intersected = dmnsn_prtree_search(state->prtree, ray, &intersection);
dmnsn_color color = state->scene->background;
if (intersected) {
diff --git a/tests/libdimension/Makefile.am b/tests/libdimension/Makefile.am
index 6fc3dc7..f59848e 100644
--- a/tests/libdimension/Makefile.am
+++ b/tests/libdimension/Makefile.am
@@ -22,7 +22,7 @@ INCLUDES = -I$(top_srcdir)/libdimension
check_LTLIBRARIES = libdimension-tests.la
check_PROGRAMS = error-test \
warning-test \
- bvst-test \
+ prtree-test \
png-test \
gl-test \
cxx-test
@@ -56,8 +56,8 @@ error_test_LDADD = libdimension-tests.la
warning_test_SOURCES = warning.c
warning_test_LDADD = libdimension-tests.la
-bvst_test_SOURCES = bvst.c
-bvst_test_LDADD = libdimension-tests.la
+prtree_test_SOURCES = prtree.c
+prtree_test_LDADD = libdimension-tests.la
png_test_SOURCES = png.c
png_test_LDADD = libdimension-tests.la
diff --git a/tests/libdimension/bvst.c b/tests/libdimension/prtree.c
index 33c737b..c75d8da 100644
--- a/tests/libdimension/bvst.c
+++ b/tests/libdimension/prtree.c
@@ -18,7 +18,7 @@
*************************************************************************/
/*
- * Basic tests of our Bounding Volume Splay Tree framework
+ * Basic tests of PR-trees
*/
#include "../../libdimension/dimension_impl.h"
@@ -27,46 +27,5 @@
int
main()
{
- dmnsn_bvst *tree;
- dmnsn_object *obj1, *obj2, *obj3;
-
- obj1 = dmnsn_new_object();
- obj2 = dmnsn_new_object();
- obj3 = dmnsn_new_object();
-
- obj1->bounding_box.min = dmnsn_new_vector(0.0, 0.0, 0.0);
- obj1->bounding_box.max = dmnsn_new_vector(1.0, 1.0, 1.0);
-
- obj2->bounding_box.min = dmnsn_new_vector(-2.0, -2.0, -2.0);
- obj2->bounding_box.max = dmnsn_new_vector(1.0, 1.0, 1.0);
-
- obj3->bounding_box.min = dmnsn_new_vector(-1.0, -1.0, -1.0);
- obj3->bounding_box.max = dmnsn_new_vector(0.0, 0.0, 0.0);
-
- tree = dmnsn_new_bvst();
-
- dmnsn_bvst_insert(tree, obj1);
- if (tree->root->object != obj1) {
- fprintf(stderr, "Wrong BVST built.\n");
- return EXIT_FAILURE;
- }
-
- dmnsn_bvst_insert(tree, obj2);
- if (tree->root->object != obj2 || tree->root->contains->object != obj1) {
- fprintf(stderr, "Wrong BVST built.\n");
- return EXIT_FAILURE;
- }
-
- dmnsn_bvst_insert(tree, obj3);
- if (tree->root->object != obj3 || tree->root->contains->object != obj1
- || tree->root->container->object != obj2) {
- fprintf(stderr, "Wrong BVST built.\n");
- return EXIT_FAILURE;
- }
-
- dmnsn_delete_bvst(tree);
- dmnsn_delete_object(obj3);
- dmnsn_delete_object(obj2);
- dmnsn_delete_object(obj1);
return EXIT_SUCCESS;
}