summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--bench/libdimension/Makefile.am10
-rw-r--r--bench/libdimension/bvst.c (renamed from bench/libdimension/kD_splay_tree.c)44
-rw-r--r--libdimension/Makefile.am4
-rw-r--r--libdimension/bvst.c (renamed from libdimension/kD_splay_tree.c)124
-rw-r--r--libdimension/bvst.h (renamed from libdimension/kD_splay_tree.h)35
-rw-r--r--libdimension/dimension_impl.h2
-rw-r--r--libdimension/raytrace.c37
-rw-r--r--tests/libdimension/Makefile.am6
-rw-r--r--tests/libdimension/bvst.c (renamed from tests/libdimension/kD_splay_tree.c)20
9 files changed, 138 insertions, 144 deletions
diff --git a/bench/libdimension/Makefile.am b/bench/libdimension/Makefile.am
index 8b124bc..2e23fde 100644
--- a/bench/libdimension/Makefile.am
+++ b/bench/libdimension/Makefile.am
@@ -19,7 +19,7 @@
INCLUDES = -I$(top_srcdir)/libdimension
-EXTRA_PROGRAMS = bench-array bench-geometry bench-kD_splay_tree
+EXTRA_PROGRAMS = bench-array bench-geometry bench-bvst
bench_array_SOURCES = array.c
bench_array_LDADD = -lsandglass $(top_builddir)/libdimension/libdimension.la
@@ -27,12 +27,12 @@ bench_array_LDADD = -lsandglass $(top_builddir)/libdimension/libdimension.la
bench_geometry_SOURCES = geometry.c
bench_geometry_LDADD = -lsandglass $(top_builddir)/libdimension/libdimension.la
-bench_kD_splay_tree_SOURCES = kD_splay_tree.c
-bench_kD_splay_tree_LDADD = -lsandglass $(top_builddir)/libdimension/libdimension.la
+bench_bvst_SOURCES = bvst.c
+bench_bvst_LDADD = -lsandglass $(top_builddir)/libdimension/libdimension.la
-bench: bench-array$(EXEEXT) bench-geometry$(EXEEXT) bench-kD_splay_tree$(EXEEXT)
+bench: bench-array$(EXEEXT) bench-geometry$(EXEEXT) bench-bvst$(EXEEXT)
./bench-array$(EXEEXT)
./bench-geometry$(EXEEXT)
- ./bench-kD_splay_tree$(EXEEXT)
+ ./bench-bvst$(EXEEXT)
.PHONY: bench
diff --git a/bench/libdimension/kD_splay_tree.c b/bench/libdimension/bvst.c
index fffab69..3d363ca 100644
--- a/bench/libdimension/kD_splay_tree.c
+++ b/bench/libdimension/bvst.c
@@ -66,17 +66,17 @@ dmnsn_randomize_bounding_box(dmnsn_object *object)
}
}
-dmnsn_kD_splay_node *
-dmnsn_kD_splay_deepest_recursive(dmnsn_kD_splay_node *node,
+dmnsn_bvst_node *
+dmnsn_bvst_deepest_recursive(dmnsn_bvst_node *node,
unsigned int depth, unsigned int *deepest)
{
- dmnsn_kD_splay_node *left = NULL, *right = NULL;
+ dmnsn_bvst_node *left = NULL, *right = NULL;
if (node->contains) {
- left = dmnsn_kD_splay_deepest_recursive(node->contains, depth + 1, deepest);
+ left = dmnsn_bvst_deepest_recursive(node->contains, depth + 1, deepest);
}
if (node->container) {
- right = dmnsn_kD_splay_deepest_recursive(node->container,
+ right = dmnsn_bvst_deepest_recursive(node->container,
depth + 1, deepest);
}
@@ -92,18 +92,18 @@ dmnsn_kD_splay_deepest_recursive(dmnsn_kD_splay_node *node,
}
}
-dmnsn_kD_splay_node *
-dmnsn_kD_splay_deepest(dmnsn_kD_splay_tree *tree)
+dmnsn_bvst_node *
+dmnsn_bvst_deepest(dmnsn_bvst *tree)
{
unsigned int deepest = 0;
- return dmnsn_kD_splay_deepest_recursive(tree->root, 0, &deepest);
+ return dmnsn_bvst_deepest_recursive(tree->root, 0, &deepest);
}
int
main()
{
- dmnsn_kD_splay_tree *tree;
- dmnsn_kD_splay_node *node;
+ dmnsn_bvst *tree;
+ dmnsn_bvst_node *node;
dmnsn_intersection *intersection;
dmnsn_line ray;
const unsigned int nobjects = 128;
@@ -119,7 +119,7 @@ main()
return EXIT_FAILURE;
}
- tree = dmnsn_new_kD_splay_tree();
+ tree = dmnsn_new_bvst();
for (i = 0; i < nobjects; ++i) {
objects[i] = dmnsn_new_object();
@@ -133,41 +133,41 @@ main()
objects[i]->intersection_fn = &dmnsn_fake_intersection_fn;
}
- /* dmnsn_kD_splay_insert() */
+ /* dmnsn_bvst_insert() */
grains = 0;
for (i = 0; i < nobjects; ++i) {
sandglass_bench_noprecache(&sandglass,
- dmnsn_kD_splay_insert(tree, objects[i]));
+ dmnsn_bvst_insert(tree, objects[i]));
sandglass.grains += grains;
grains = sandglass.grains;
}
- printf("dmnsn_kD_splay_insert(): %ld\n", sandglass.grains/nobjects);
+ printf("dmnsn_bvst_insert(): %ld\n", sandglass.grains/nobjects);
- /* dmnsn_kD_splay_search() */
+ /* dmnsn_bvst_search() */
ray.x0 = dmnsn_new_vector(0.0, 0.0, -2.0);
ray.n = dmnsn_new_vector(0.0, 0.0, 1.0);
dmnsn_delete_intersection((*objects[0]->intersection_fn)(objects[0], ray));
sandglass_bench_noprecache(&sandglass, {
- intersection = dmnsn_kD_splay_search(tree, ray);
+ intersection = dmnsn_bvst_search(tree, ray);
});
dmnsn_delete_intersection(intersection);
- printf("dmnsn_kD_splay_search(): %ld\n", sandglass.grains);
+ printf("dmnsn_bvst_search(): %ld\n", sandglass.grains);
- /* dmnsn_kD_splay() */
+ /* dmnsn_bvst_splay() */
grains = 0;
for (i = 0; i < nobjects; ++i) {
- node = dmnsn_kD_splay_deepest(tree);
- sandglass_bench_noprecache(&sandglass, dmnsn_kD_splay(tree, node));
+ node = dmnsn_bvst_deepest(tree);
+ sandglass_bench_noprecache(&sandglass, dmnsn_bvst_splay(tree, node));
sandglass.grains += grains;
grains = sandglass.grains;
}
- printf("dmnsn_kD_splay(): %ld\n", sandglass.grains/nobjects);
+ printf("dmnsn_bvst_splay(): %ld\n", sandglass.grains/nobjects);
/* Cleanup */
- dmnsn_delete_kD_splay_tree(tree);
+ dmnsn_delete_bvst(tree);
for (i = 0; i < nobjects; ++i) {
dmnsn_delete_object(objects[i]);
}
diff --git a/libdimension/Makefile.am b/libdimension/Makefile.am
index 0efa05c..b3f6813 100644
--- a/libdimension/Makefile.am
+++ b/libdimension/Makefile.am
@@ -42,6 +42,8 @@ lib_LTLIBRARIES = libdimension.la
libdimension_la_SOURCES = $(nobase_include_HEADERS) \
ambient.c \
+ bvst.c \
+ bvst.h \
camera.c \
canvas.c \
color.c \
@@ -53,8 +55,6 @@ libdimension_la_SOURCES = $(nobase_include_HEADERS) \
geometry.c \
gl.c \
inlines.c \
- kD_splay_tree.c \
- kD_splay_tree.h \
light.c \
object.c \
perspective.c \
diff --git a/libdimension/kD_splay_tree.c b/libdimension/bvst.c
index b6be801..a73b4b2 100644
--- a/libdimension/kD_splay_tree.c
+++ b/libdimension/bvst.c
@@ -21,14 +21,14 @@
#include "dimension_impl.h"
#include <stdlib.h>
-static dmnsn_kD_splay_node *dmnsn_new_kD_splay_node();
-static void dmnsn_delete_kD_splay_node(dmnsn_kD_splay_node *node);
+static dmnsn_bvst_node *dmnsn_new_bvst_node();
+static void dmnsn_delete_bvst_node(dmnsn_bvst_node *node);
/* Return an empty tree */
-dmnsn_kD_splay_tree *
-dmnsn_new_kD_splay_tree()
+dmnsn_bvst *
+dmnsn_new_bvst()
{
- dmnsn_kD_splay_tree *tree = malloc(sizeof(dmnsn_kD_splay_tree));
+ dmnsn_bvst *tree = malloc(sizeof(dmnsn_bvst));
if (tree) {
tree->root = NULL;
} else {
@@ -38,29 +38,29 @@ dmnsn_new_kD_splay_tree()
}
/* Recursively copy the nodes of a kD splay tree */
-static dmnsn_kD_splay_node *
-dmnsn_kD_splay_copy_recursive(dmnsn_kD_splay_node *root)
+static dmnsn_bvst_node *
+dmnsn_bvst_copy_recursive(dmnsn_bvst_node *root)
{
- dmnsn_kD_splay_node *node = dmnsn_new_kD_splay_node();
+ dmnsn_bvst_node *node = dmnsn_new_bvst_node();
*node = *root;
if (node->contains) {
- node->contains = dmnsn_kD_splay_copy_recursive(node->contains);
+ node->contains = dmnsn_bvst_copy_recursive(node->contains);
node->contains->parent = node;
}
if (node->container) {
- node->container = dmnsn_kD_splay_copy_recursive(node->container);
+ node->container = dmnsn_bvst_copy_recursive(node->container);
node->container->parent = node;
}
return node;
}
/* Copy a kD splay tree */
-dmnsn_kD_splay_tree *
-dmnsn_kD_splay_copy(dmnsn_kD_splay_tree *tree)
+dmnsn_bvst *
+dmnsn_bvst_copy(dmnsn_bvst *tree)
{
- dmnsn_kD_splay_tree *copy = dmnsn_new_kD_splay_tree();
+ dmnsn_bvst *copy = dmnsn_new_bvst();
if (tree->root)
- copy->root = dmnsn_kD_splay_copy_recursive(tree->root);
+ copy->root = dmnsn_bvst_copy_recursive(tree->root);
else
copy->root = NULL;
return copy;
@@ -68,21 +68,21 @@ dmnsn_kD_splay_copy(dmnsn_kD_splay_tree *tree)
/* Recursively free a kD splay tree */
void
-dmnsn_delete_kD_splay_tree_recursive(dmnsn_kD_splay_node *node)
+dmnsn_delete_bvst_recursive(dmnsn_bvst_node *node)
{
if (node) {
- dmnsn_delete_kD_splay_tree_recursive(node->contains);
- dmnsn_delete_kD_splay_tree_recursive(node->container);
- dmnsn_delete_kD_splay_node(node);
+ dmnsn_delete_bvst_recursive(node->contains);
+ dmnsn_delete_bvst_recursive(node->container);
+ dmnsn_delete_bvst_node(node);
}
}
/* Free a kD splay tree */
void
-dmnsn_delete_kD_splay_tree(dmnsn_kD_splay_tree *tree)
+dmnsn_delete_bvst(dmnsn_bvst *tree)
{
if (tree) {
- dmnsn_delete_kD_splay_tree_recursive(tree->root);
+ dmnsn_delete_bvst_recursive(tree->root);
free(tree);
}
}
@@ -91,14 +91,14 @@ dmnsn_delete_kD_splay_tree(dmnsn_kD_splay_tree *tree)
static int dmnsn_box_contains(dmnsn_vector p,
dmnsn_vector min, dmnsn_vector max);
/* Expand node to contain the bounding box from min to max */
-static void dmnsn_kD_splay_node_swallow(dmnsn_kD_splay_node *node,
- dmnsn_vector min, dmnsn_vector max);
+static void dmnsn_bvst_node_swallow(dmnsn_bvst_node *node,
+ dmnsn_vector min, dmnsn_vector max);
/* Insert an object into the tree */
void
-dmnsn_kD_splay_insert(dmnsn_kD_splay_tree *tree, dmnsn_object *object)
+dmnsn_bvst_insert(dmnsn_bvst *tree, dmnsn_object *object)
{
- dmnsn_kD_splay_node *node = dmnsn_new_kD_splay_node(), *parent = tree->root;
+ dmnsn_bvst_node *node = dmnsn_new_bvst_node(), *parent = tree->root;
/* Store the inverse of the transformation matrix */
object->trans_inv = dmnsn_matrix_inverse(object->trans);
@@ -117,31 +117,31 @@ dmnsn_kD_splay_insert(dmnsn_kD_splay_tree *tree, dmnsn_object *object)
dmnsn_vector corner;
corner = dmnsn_new_vector(object->min.x, object->min.y, object->max.z);
corner = dmnsn_matrix_vector_mul(object->trans, corner);
- dmnsn_kD_splay_node_swallow(node, corner, corner);
+ dmnsn_bvst_node_swallow(node, corner, corner);
corner = dmnsn_new_vector(object->min.x, object->max.y, object->min.z);
corner = dmnsn_matrix_vector_mul(object->trans, corner);
- dmnsn_kD_splay_node_swallow(node, corner, corner);
+ dmnsn_bvst_node_swallow(node, corner, corner);
corner = dmnsn_new_vector(object->min.x, object->max.y, object->max.z);
corner = dmnsn_matrix_vector_mul(object->trans, corner);
- dmnsn_kD_splay_node_swallow(node, corner, corner);
+ dmnsn_bvst_node_swallow(node, corner, corner);
corner = dmnsn_new_vector(object->max.x, object->min.y, object->min.z);
corner = dmnsn_matrix_vector_mul(object->trans, corner);
- dmnsn_kD_splay_node_swallow(node, corner, corner);
+ dmnsn_bvst_node_swallow(node, corner, corner);
corner = dmnsn_new_vector(object->max.x, object->min.y, object->max.z);
corner = dmnsn_matrix_vector_mul(object->trans, corner);
- dmnsn_kD_splay_node_swallow(node, corner, corner);
+ dmnsn_bvst_node_swallow(node, corner, corner);
corner = dmnsn_new_vector(object->max.x, object->max.y, object->min.z);
corner = dmnsn_matrix_vector_mul(object->trans, corner);
- dmnsn_kD_splay_node_swallow(node, corner, corner);
+ dmnsn_bvst_node_swallow(node, corner, corner);
corner = dmnsn_new_vector(object->max.x, object->max.y, object->max.z);
corner = dmnsn_matrix_vector_mul(object->trans, corner);
- dmnsn_kD_splay_node_swallow(node, corner, corner);
+ dmnsn_bvst_node_swallow(node, corner, corner);
/* Now insert the node */
@@ -160,7 +160,7 @@ dmnsn_kD_splay_insert(dmnsn_kD_splay_tree *tree, dmnsn_object *object)
} else {
/* Expand node's bounding box to fully contain parent's if it doesn't
already */
- dmnsn_kD_splay_node_swallow(node, parent->min, parent->max);
+ dmnsn_bvst_node_swallow(node, parent->min, parent->max);
/* node now fully contains parent */
if (parent->container)
parent = parent->container;
@@ -173,7 +173,7 @@ dmnsn_kD_splay_insert(dmnsn_kD_splay_tree *tree, dmnsn_object *object)
}
}
- dmnsn_kD_splay(tree, node);
+ dmnsn_bvst_splay(tree, node);
}
/* Return whether p is within the axis-aligned box with corners min and max */
@@ -186,8 +186,8 @@ dmnsn_box_contains(dmnsn_vector p, dmnsn_vector min, dmnsn_vector max)
/* Expand node to contain the bounding box from min to max */
static void
-dmnsn_kD_splay_node_swallow(dmnsn_kD_splay_node *node,
- dmnsn_vector min, dmnsn_vector max)
+dmnsn_bvst_node_swallow(dmnsn_bvst_node *node,
+ dmnsn_vector min, dmnsn_vector max)
{
if (node->min.x > min.x) node->min.x = min.x;
if (node->min.y > min.y) node->min.y = min.y;
@@ -199,28 +199,28 @@ dmnsn_kD_splay_node_swallow(dmnsn_kD_splay_node *node,
}
/* Tree rotations */
-static void dmnsn_kD_splay_rotate(dmnsn_kD_splay_node *node);
+static void dmnsn_bvst_rotate(dmnsn_bvst_node *node);
/* Splay a node: move it to the root via tree rotations */
void
-dmnsn_kD_splay(dmnsn_kD_splay_tree *tree, dmnsn_kD_splay_node *node)
+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_kD_splay_rotate(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_kD_splay_rotate(node->parent);
- dmnsn_kD_splay_rotate(node);
+ 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_kD_splay_rotate(node);
- dmnsn_kD_splay_rotate(node);
+ dmnsn_bvst_rotate(node);
+ dmnsn_bvst_rotate(node);
}
}
tree->root = node;
@@ -228,9 +228,9 @@ dmnsn_kD_splay(dmnsn_kD_splay_tree *tree, dmnsn_kD_splay_node *node)
/* Rotate a tree on the edge connecting node and node->parent */
static void
-dmnsn_kD_splay_rotate(dmnsn_kD_splay_node *node)
+dmnsn_bvst_rotate(dmnsn_bvst_node *node)
{
- dmnsn_kD_splay_node *P, *Q, *B;
+ dmnsn_bvst_node *P, *Q, *B;
if (node == node->parent->contains) {
/* We are a left child; perform a right rotation:
*
@@ -293,22 +293,21 @@ dmnsn_kD_splay_rotate(dmnsn_kD_splay_node *node)
}
typedef struct {
- dmnsn_kD_splay_node *node;
+ dmnsn_bvst_node *node;
dmnsn_intersection *intersection;
-} dmnsn_kD_splay_search_result;
+} dmnsn_bvst_search_result;
-static dmnsn_kD_splay_search_result
-dmnsn_kD_splay_search_recursive(dmnsn_kD_splay_node *node, dmnsn_line ray,
- double t);
+static dmnsn_bvst_search_result
+dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t);
dmnsn_intersection *
-dmnsn_kD_splay_search(dmnsn_kD_splay_tree *tree, dmnsn_line ray)
+dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray)
{
- dmnsn_kD_splay_search_result result
- = dmnsn_kD_splay_search_recursive(tree->root, ray, -1.0);
+ dmnsn_bvst_search_result result
+ = dmnsn_bvst_search_recursive(tree->root, ray, -1.0);
if (result.node)
- dmnsn_kD_splay(tree, result.node);
+ dmnsn_bvst_splay(tree, result.node);
return result.intersection;
}
@@ -316,19 +315,18 @@ dmnsn_kD_splay_search(dmnsn_kD_splay_tree *tree, dmnsn_line ray)
static int dmnsn_ray_box_intersection(dmnsn_line ray, dmnsn_vector min,
dmnsn_vector max, double t);
-static dmnsn_kD_splay_search_result
-dmnsn_kD_splay_search_recursive(dmnsn_kD_splay_node *node, dmnsn_line ray,
- double t)
+static dmnsn_bvst_search_result
+dmnsn_bvst_search_recursive(dmnsn_bvst_node *node, dmnsn_line ray, double t)
{
dmnsn_line ray_trans;
- dmnsn_kD_splay_search_result result = { NULL, NULL }, result_temp;
+ dmnsn_bvst_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);
+ 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;
@@ -376,7 +374,7 @@ dmnsn_kD_splay_search_recursive(dmnsn_kD_splay_node *node, dmnsn_line ray,
}
/* Go down the left subtree */
- result_temp = dmnsn_kD_splay_search_recursive(node->contains, ray, t);
+ result_temp = dmnsn_bvst_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_temp;
@@ -447,10 +445,10 @@ dmnsn_ray_box_intersection(dmnsn_line line, dmnsn_vector min, dmnsn_vector max,
return 0;
}
-static dmnsn_kD_splay_node *
-dmnsn_new_kD_splay_node()
+static dmnsn_bvst_node *
+dmnsn_new_bvst_node()
{
- dmnsn_kD_splay_node *node = malloc(sizeof(dmnsn_kD_splay_node));
+ dmnsn_bvst_node *node = malloc(sizeof(dmnsn_bvst_node));
if (!node) {
dmnsn_error(DMNSN_SEVERITY_HIGH, "kD splay tree node allocation failed.");
}
@@ -458,7 +456,7 @@ dmnsn_new_kD_splay_node()
}
static void
-dmnsn_delete_kD_splay_node(dmnsn_kD_splay_node *node)
+dmnsn_delete_bvst_node(dmnsn_bvst_node *node)
{
free(node);
}
diff --git a/libdimension/kD_splay_tree.h b/libdimension/bvst.h
index eac47d8..57b71b8 100644
--- a/libdimension/kD_splay_tree.h
+++ b/libdimension/bvst.h
@@ -19,7 +19,7 @@
*************************************************************************/
/*
- * k-dimensional (in this case, k == 3) trees for storing object bounding boxes.
+ * 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-
@@ -29,22 +29,22 @@
* are expanded to contain it.
*/
-#ifndef DIMENSION_IMPL_KD_SPLAY_TREE_H
-#define DIMENSION_IMPL_KD_SPLAY_TREE_H
+#ifndef DIMENSION_IMPL_BVST_H
+#define DIMENSION_IMPL_BVST_H
-typedef struct dmnsn_kD_splay_tree dmnsn_kD_splay_tree;
-typedef struct dmnsn_kD_splay_node dmnsn_kD_splay_node;
+typedef struct dmnsn_bvst dmnsn_bvst;
+typedef struct dmnsn_bvst_node dmnsn_bvst_node;
-struct dmnsn_kD_splay_tree {
- dmnsn_kD_splay_node *root;
+struct dmnsn_bvst {
+ dmnsn_bvst_node *root;
};
-struct dmnsn_kD_splay_node {
+struct dmnsn_bvst_node {
/* Tree children */
- dmnsn_kD_splay_node *contains, *container;
+ dmnsn_bvst_node *contains, *container;
/* Parent node for easy backtracking */
- dmnsn_kD_splay_node *parent;
+ dmnsn_bvst_node *parent;
/* Bounding box corners */
dmnsn_vector min, max;
@@ -53,14 +53,13 @@ struct dmnsn_kD_splay_node {
dmnsn_object *object;
};
-dmnsn_kD_splay_tree *dmnsn_new_kD_splay_tree();
-dmnsn_kD_splay_tree *dmnsn_kD_splay_copy(dmnsn_kD_splay_tree *tree);
-void dmnsn_delete_kD_splay_tree(dmnsn_kD_splay_tree *tree);
+dmnsn_bvst *dmnsn_new_bvst();
+dmnsn_bvst *dmnsn_bvst_copy(dmnsn_bvst *tree);
+void dmnsn_delete_bvst(dmnsn_bvst *tree);
-void dmnsn_kD_splay_insert(dmnsn_kD_splay_tree *tree, dmnsn_object *object);
-void dmnsn_kD_splay(dmnsn_kD_splay_tree *tree, dmnsn_kD_splay_node *node);
+void dmnsn_bvst_insert(dmnsn_bvst *tree, dmnsn_object *object);
+void dmnsn_bvst_splay(dmnsn_bvst *tree, dmnsn_bvst_node *node);
-dmnsn_intersection *dmnsn_kD_splay_search(dmnsn_kD_splay_tree *tree,
- dmnsn_line ray);
+dmnsn_intersection *dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray);
-#endif /* DIMENSION_IMPL_KD_SPLAY_TREE_H */
+#endif /* DIMENSION_IMPL_BVST_H */
diff --git a/libdimension/dimension_impl.h b/libdimension/dimension_impl.h
index 216302a..880aee7 100644
--- a/libdimension/dimension_impl.h
+++ b/libdimension/dimension_impl.h
@@ -22,6 +22,6 @@
#define DIMENSION_IMPL_H
#include "dimension.h"
-#include "kD_splay_tree.h"
+#include "bvst.h"
#endif /* DIMENSION_IMPL_H */
diff --git a/libdimension/raytrace.c b/libdimension/raytrace.c
index a76a2f5..1e03b91 100644
--- a/libdimension/raytrace.c
+++ b/libdimension/raytrace.c
@@ -30,7 +30,7 @@
typedef struct {
dmnsn_progress *progress;
dmnsn_scene *scene;
- dmnsn_kD_splay_tree *kD_splay_tree;
+ dmnsn_bvst *bvst;
/* For multithreading */
unsigned int index, threads;
@@ -63,19 +63,19 @@ dmnsn_raytrace_scene_async(dmnsn_scene *scene)
return NULL;
}
- payload->progress = progress;
- payload->scene = scene;
- payload->kD_splay_tree = dmnsn_new_kD_splay_tree();
+ payload->progress = progress;
+ payload->scene = scene;
+ payload->bvst = dmnsn_new_bvst();
for (i = 0; i < dmnsn_array_size(payload->scene->objects); ++i) {
dmnsn_array_get(payload->scene->objects, i, &object);
- dmnsn_kD_splay_insert(payload->kD_splay_tree, object);
+ dmnsn_bvst_insert(payload->bvst, object);
}
if (pthread_create(&progress->thread, NULL, &dmnsn_raytrace_scene_thread,
payload) != 0)
{
- dmnsn_delete_kD_splay_tree(payload->kD_splay_tree);
+ dmnsn_delete_bvst(payload->bvst);
free(payload);
dmnsn_delete_progress(progress);
return NULL;
@@ -145,8 +145,7 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload)
payloads[i].index = i;
payloads[i].threads = nthreads;
if (i > 0) {
- payloads[i].kD_splay_tree =
- dmnsn_kD_splay_copy(payloads[0].kD_splay_tree);
+ payloads[i].bvst = dmnsn_bvst_copy(payloads[0].bvst);
}
}
@@ -164,7 +163,7 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload)
} else {
/* Only free on a successful join - otherwise we might free a pointer
out from under a running thread */
- dmnsn_delete_kD_splay_tree(payloads[j].kD_splay_tree);
+ dmnsn_delete_bvst(payloads[j].bvst);
free(ptr);
}
}
@@ -182,7 +181,7 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload)
if (retval == 0) {
retval = *(int *)ptr;
}
- dmnsn_delete_kD_splay_tree(payloads[i].kD_splay_tree);
+ dmnsn_delete_bvst(payloads[i].bvst);
free(ptr);
}
}
@@ -195,7 +194,7 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload)
/* Actual raytracing implementation */
static int dmnsn_raytrace_scene_impl(dmnsn_progress *progress,
dmnsn_scene *scene,
- dmnsn_kD_splay_tree *kD_splay_tree,
+ dmnsn_bvst *bvst,
unsigned int index, unsigned int threads);
/* Multi-threading thread callback */
@@ -206,7 +205,7 @@ dmnsn_raytrace_scene_multithread_thread(void *ptr)
int *retval = malloc(sizeof(int));
if (retval) {
*retval = dmnsn_raytrace_scene_impl(payload->progress, payload->scene,
- payload->kD_splay_tree,
+ payload->bvst,
payload->index, payload->threads);
}
return retval;
@@ -219,7 +218,7 @@ dmnsn_raytrace_scene_multithread_thread(void *ptr)
typedef struct dmnsn_raytrace_state {
const dmnsn_scene *scene;
const dmnsn_intersection *intersection;
- dmnsn_kD_splay_tree *kD_splay_tree;
+ dmnsn_bvst *bvst;
unsigned int level;
dmnsn_vector r;
@@ -238,12 +237,12 @@ static dmnsn_color dmnsn_raytrace_shoot(dmnsn_raytrace_state *state,
/* Actually raytrace a scene */
static int
dmnsn_raytrace_scene_impl(dmnsn_progress *progress, dmnsn_scene *scene,
- dmnsn_kD_splay_tree *kD_splay_tree,
+ dmnsn_bvst *bvst,
unsigned int index, unsigned int threads)
{
dmnsn_raytrace_state state = {
.scene = scene,
- .kD_splay_tree = kD_splay_tree
+ .bvst = bvst
};
unsigned int width = scene->canvas->x;
@@ -339,10 +338,8 @@ dmnsn_raytrace_light_ray(const dmnsn_raytrace_state *state,
unsigned int level = state->level;
while (level) {
- dmnsn_intersection *shadow_caster = dmnsn_kD_splay_search(
- state->kD_splay_tree,
- shadow_ray
- );
+ dmnsn_intersection *shadow_caster
+ = dmnsn_bvst_search(state->bvst, shadow_ray);
if (!shadow_caster || shadow_caster->t > 1.0) {
dmnsn_delete_intersection(shadow_caster);
@@ -468,7 +465,7 @@ dmnsn_raytrace_shoot(dmnsn_raytrace_state *state, dmnsn_line ray)
--state->level;
dmnsn_intersection *intersection
- = dmnsn_kD_splay_search(state->kD_splay_tree, ray);
+ = dmnsn_bvst_search(state->bvst, ray);
dmnsn_color color = state->scene->background;
if (intersection) {
diff --git a/tests/libdimension/Makefile.am b/tests/libdimension/Makefile.am
index 7b238da..886eb42 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 \
- kD_splay_tree-test \
+ bvst-test \
png-test \
gl-test
TESTS = $(check_PROGRAMS)
@@ -45,8 +45,8 @@ error_test_LDADD = libdimension-tests.la
warning_test_SOURCES = warning.c
warning_test_LDADD = libdimension-tests.la
-kD_splay_tree_test_SOURCES = kD_splay_tree.c
-kD_splay_tree_test_LDADD = libdimension-tests.la
+bvst_test_SOURCES = bvst.c
+bvst_test_LDADD = libdimension-tests.la
png_test_SOURCES = png.c
png_test_LDADD = libdimension-tests.la
diff --git a/tests/libdimension/kD_splay_tree.c b/tests/libdimension/bvst.c
index ea53550..36dce04 100644
--- a/tests/libdimension/kD_splay_tree.c
+++ b/tests/libdimension/bvst.c
@@ -18,7 +18,7 @@
*************************************************************************/
/*
- * Basic tests of our fancy k-D splay tree framework
+ * Basic tests of our Bounding Volume Splay Tree framework
*/
#include "../../libdimension/dimension_impl.h"
@@ -27,7 +27,7 @@
int
main()
{
- dmnsn_kD_splay_tree *tree;
+ dmnsn_bvst *tree;
dmnsn_object *obj1, *obj2, *obj3;
obj1 = dmnsn_new_object();
@@ -43,28 +43,28 @@ main()
obj3->min = dmnsn_new_vector(-1.0, -1.0, -1.0);
obj3->max = dmnsn_new_vector(0.0, 0.0, 0.0);
- tree = dmnsn_new_kD_splay_tree();
+ tree = dmnsn_new_bvst();
- dmnsn_kD_splay_insert(tree, obj1);
+ dmnsn_bvst_insert(tree, obj1);
if (tree->root->object != obj1) {
- fprintf(stderr, "Wrong kD splay tree built.\n");
+ fprintf(stderr, "Wrong BVST built.\n");
return EXIT_FAILURE;
}
- dmnsn_kD_splay_insert(tree, obj2);
+ dmnsn_bvst_insert(tree, obj2);
if (tree->root->object != obj2 || tree->root->contains->object != obj1) {
- fprintf(stderr, "Wrong kD splay tree built.\n");
+ fprintf(stderr, "Wrong BVST built.\n");
return EXIT_FAILURE;
}
- dmnsn_kD_splay_insert(tree, obj3);
+ dmnsn_bvst_insert(tree, obj3);
if (tree->root->object != obj3 || tree->root->contains->object != obj1
|| tree->root->container->object != obj2) {
- fprintf(stderr, "Wrong kD splay tree built.\n");
+ fprintf(stderr, "Wrong BVST built.\n");
return EXIT_FAILURE;
}
- dmnsn_delete_kD_splay_tree(tree);
+ dmnsn_delete_bvst(tree);
dmnsn_delete_object(obj3);
dmnsn_delete_object(obj2);
dmnsn_delete_object(obj1);