From 9b04b4e2a1147ed2a30e4f86dd403851036b3b51 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Tue, 27 Apr 2010 21:25:50 -0600 Subject: Replace BVSTs with priority R-trees. --- bench/libdimension/Makefile.am | 8 +- bench/libdimension/bvst.c | 170 ------------ bench/libdimension/prtree.c | 170 ++++++++++++ libdimension/Makefile.am | 4 +- libdimension/bvst.c | 388 ---------------------------- libdimension/bvst.h | 66 ----- libdimension/dimension_impl.h | 2 +- libdimension/prtree.c | 574 +++++++++++++++++++++++++++++++++++++++++ libdimension/prtree.h | 51 ++++ libdimension/raytrace.c | 31 +-- tests/libdimension/Makefile.am | 6 +- tests/libdimension/bvst.c | 72 ------ tests/libdimension/prtree.c | 31 +++ 13 files changed, 846 insertions(+), 727 deletions(-) delete mode 100644 bench/libdimension/bvst.c create mode 100644 bench/libdimension/prtree.c delete mode 100644 libdimension/bvst.c delete mode 100644 libdimension/bvst.h create mode 100644 libdimension/prtree.c create mode 100644 libdimension/prtree.h delete mode 100644 tests/libdimension/bvst.c create mode 100644 tests/libdimension/prtree.c 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/bvst.c deleted file mode 100644 index dd61a80..0000000 --- a/bench/libdimension/bvst.c +++ /dev/null @@ -1,170 +0,0 @@ -/************************************************************************* - * Copyright (C) 2010 Tavian Barnes * - * * - * This file is part of The Dimension Test Suite. * - * * - * The Dimension Test Suite is free software; you can redistribute it * - * and/or modify it under the terms of the GNU 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 Test Suite 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 * - * General Public License for more details. * - * * - * You should have received a copy of the GNU General Public License * - * along with this program. If not, see . * - *************************************************************************/ - -#include "../../libdimension/dimension_impl.h" -#include -#include - -bool -dmnsn_fake_intersection_fn(const dmnsn_object *object, dmnsn_line line, - dmnsn_intersection *intersection) -{ - intersection->t = (object->bounding_box.min.z - line.x0.z)/line.n.z; - intersection->texture = object->texture; - return true; -} - -void -dmnsn_randomize_bounding_box(dmnsn_object *object) -{ - double rand1, rand2; - - rand1 = 2.0*((double)rand())/RAND_MAX - 1.0; - rand2 = 2.0*((double)rand())/RAND_MAX - 1.0; - if (rand1 < rand2) { - object->bounding_box.min.x = rand1; - object->bounding_box.max.x = rand2; - } else { - object->bounding_box.max.x = rand1; - object->bounding_box.min.x = rand2; - } - - rand1 = 2.0*((double)rand())/RAND_MAX - 1.0; - rand2 = 2.0*((double)rand())/RAND_MAX - 1.0; - if (rand1 < rand2) { - object->bounding_box.min.y = rand1; - object->bounding_box.max.y = rand2; - } else { - object->bounding_box.max.y = rand1; - object->bounding_box.min.y = rand2; - } - - rand1 = 2.0*((double)rand())/RAND_MAX - 1.0; - rand2 = 2.0*((double)rand())/RAND_MAX - 1.0; - if (rand1 < rand2) { - object->bounding_box.min.z = rand1; - object->bounding_box.max.z = rand2; - } else { - object->bounding_box.max.z = rand1; - object->bounding_box.min.z = rand2; - } -} - -dmnsn_bvst_node * -dmnsn_bvst_deepest_recursive(dmnsn_bvst_node *node, - unsigned int depth, unsigned int *deepest) -{ - dmnsn_bvst_node *left = NULL, *right = NULL; - - if (node->contains) { - left = dmnsn_bvst_deepest_recursive(node->contains, depth + 1, deepest); - } - if (node->container) { - right = dmnsn_bvst_deepest_recursive(node->container, - depth + 1, deepest); - } - - if (right) { - return right; - } else if (left) { - return left; - } else if (depth >= *deepest) { - *deepest = depth; - return node; - } else { - return NULL; - } -} - -dmnsn_bvst_node * -dmnsn_bvst_deepest(dmnsn_bvst *tree) -{ - unsigned int deepest = 0; - return dmnsn_bvst_deepest_recursive(tree->root, 0, &deepest); -} - -int -main() -{ - dmnsn_bvst *tree; - dmnsn_bvst_node *node; - dmnsn_intersection intersection; - dmnsn_line ray; - const unsigned int nobjects = 128; - dmnsn_object *objects[nobjects]; - unsigned int i; - long grains; - - sandglass_t sandglass; - - if (sandglass_init_monotonic(&sandglass, SANDGLASS_CPUTIME) != 0) { - perror("sandglass_create()"); - return EXIT_FAILURE; - } - - tree = dmnsn_new_bvst(); - - for (i = 0; i < nobjects; ++i) { - objects[i] = dmnsn_new_object(); - - /* Generate a bounding box in (-1, -1, -1), (1, 1, 1) */ - dmnsn_randomize_bounding_box(objects[i]); - objects[i]->intersection_fn = &dmnsn_fake_intersection_fn; - } - - /* dmnsn_bvst_insert() */ - - grains = 0; - for (i = 0; i < nobjects; ++i) { - sandglass_bench_noprecache(&sandglass, - dmnsn_bvst_insert(tree, objects[i])); - sandglass.grains += grains; - grains = sandglass.grains; - } - printf("dmnsn_bvst_insert(): %ld\n", sandglass.grains/nobjects); - - /* 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); - - (*objects[0]->intersection_fn)(objects[0], ray, &intersection); - sandglass_bench_noprecache(&sandglass, { - dmnsn_bvst_search(tree, ray, &intersection); - }); - printf("dmnsn_bvst_search(): %ld\n", sandglass.grains); - - /* dmnsn_bvst_splay() */ - grains = 0; - for (i = 0; i < nobjects; ++i) { - node = dmnsn_bvst_deepest(tree); - sandglass_bench_noprecache(&sandglass, dmnsn_bvst_splay(tree, node)); - sandglass.grains += grains; - grains = sandglass.grains; - } - printf("dmnsn_bvst_splay(): %ld\n", sandglass.grains/nobjects); - - /* Cleanup */ - dmnsn_delete_bvst(tree); - for (i = 0; i < nobjects; ++i) { - dmnsn_delete_object(objects[i]); - } - - return EXIT_SUCCESS; -} diff --git a/bench/libdimension/prtree.c b/bench/libdimension/prtree.c new file mode 100644 index 0000000..5ee32cf --- /dev/null +++ b/bench/libdimension/prtree.c @@ -0,0 +1,170 @@ +/************************************************************************* + * Copyright (C) 2010 Tavian Barnes * + * * + * This file is part of The Dimension Test Suite. * + * * + * The Dimension Test Suite is free software; you can redistribute it * + * and/or modify it under the terms of the GNU 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 Test Suite 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 * + * General Public License for more details. * + * * + * You should have received a copy of the GNU General Public License * + * along with this program. If not, see . * + *************************************************************************/ + +#include "../../libdimension/dimension_impl.h" +#include +#include + +bool +dmnsn_fake_intersection_fn(const dmnsn_object *object, dmnsn_line line, + dmnsn_intersection *intersection) +{ + intersection->t = (object->bounding_box.min.z - line.x0.z)/line.n.z; + intersection->texture = object->texture; + return true; +} + +void +dmnsn_randomize_bounding_box(dmnsn_object *object) +{ + double rand1, rand2; + + rand1 = 2.0*((double)rand())/RAND_MAX - 1.0; + rand2 = 2.0*((double)rand())/RAND_MAX - 1.0; + if (rand1 < rand2) { + object->bounding_box.min.x = rand1; + object->bounding_box.max.x = rand2; + } else { + object->bounding_box.max.x = rand1; + object->bounding_box.min.x = rand2; + } + + rand1 = 2.0*((double)rand())/RAND_MAX - 1.0; + rand2 = 2.0*((double)rand())/RAND_MAX - 1.0; + if (rand1 < rand2) { + object->bounding_box.min.y = rand1; + object->bounding_box.max.y = rand2; + } else { + object->bounding_box.max.y = rand1; + object->bounding_box.min.y = rand2; + } + + rand1 = 2.0*((double)rand())/RAND_MAX - 1.0; + rand2 = 2.0*((double)rand())/RAND_MAX - 1.0; + if (rand1 < rand2) { + object->bounding_box.min.z = rand1; + object->bounding_box.max.z = rand2; + } else { + object->bounding_box.max.z = rand1; + object->bounding_box.min.z = rand2; + } +} + +dmnsn_prtree_node * +dmnsn_prtree_deepest_recursive(dmnsn_prtree_node *node, + unsigned int depth, unsigned int *deepest) +{ + dmnsn_prtree_node *left = NULL, *right = NULL; + + if (node->contains) { + left = dmnsn_prtree_deepest_recursive(node->contains, depth + 1, deepest); + } + if (node->container) { + right = dmnsn_prtree_deepest_recursive(node->container, + depth + 1, deepest); + } + + if (right) { + return right; + } else if (left) { + return left; + } else if (depth >= *deepest) { + *deepest = depth; + return node; + } else { + return NULL; + } +} + +dmnsn_prtree_node * +dmnsn_prtree_deepest(dmnsn_prtree *tree) +{ + unsigned int deepest = 0; + return dmnsn_prtree_deepest_recursive(tree->root, 0, &deepest); +} + +int +main() +{ + dmnsn_prtree *tree; + dmnsn_prtree_node *node; + dmnsn_intersection intersection; + dmnsn_line ray; + const unsigned int nobjects = 128; + dmnsn_object *objects[nobjects]; + unsigned int i; + long grains; + + sandglass_t sandglass; + + if (sandglass_init_monotonic(&sandglass, SANDGLASS_CPUTIME) != 0) { + perror("sandglass_create()"); + return EXIT_FAILURE; + } + + tree = dmnsn_new_prtree(); + + for (i = 0; i < nobjects; ++i) { + objects[i] = dmnsn_new_object(); + + /* Generate a bounding box in (-1, -1, -1), (1, 1, 1) */ + dmnsn_randomize_bounding_box(objects[i]); + objects[i]->intersection_fn = &dmnsn_fake_intersection_fn; + } + + /* dmnsn_prtree_insert() */ + + grains = 0; + for (i = 0; i < nobjects; ++i) { + sandglass_bench_noprecache(&sandglass, + dmnsn_prtree_insert(tree, objects[i])); + sandglass.grains += grains; + grains = sandglass.grains; + } + printf("dmnsn_prtree_insert(): %ld\n", sandglass.grains/nobjects); + + /* 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_prtree_search(tree, ray, &intersection); + }); + printf("dmnsn_prtree_search(): %ld\n", sandglass.grains); + + /* dmnsn_prtree_splay() */ + grains = 0; + for (i = 0; i < nobjects; ++i) { + node = dmnsn_prtree_deepest(tree); + sandglass_bench_noprecache(&sandglass, dmnsn_prtree_splay(tree, node)); + sandglass.grains += grains; + grains = sandglass.grains; + } + printf("dmnsn_prtree_splay(): %ld\n", sandglass.grains/nobjects); + + /* Cleanup */ + dmnsn_delete_prtree(tree); + for (i = 0; i < nobjects; ++i) { + dmnsn_delete_object(objects[i]); + } + + return EXIT_SUCCESS; +} 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 * - * * - * 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 * - * . * - *************************************************************************/ - -#include "dimension_impl.h" -#include - -/* 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/bvst.h b/libdimension/bvst.h deleted file mode 100644 index d300cf9..0000000 --- a/libdimension/bvst.h +++ /dev/null @@ -1,66 +0,0 @@ -/************************************************************************* - * Copyright (C) 2010 Tavian Barnes * - * * - * 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 * - * . * - *************************************************************************/ - -/* - * 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. - */ - -#ifndef DIMENSION_IMPL_BVST_H -#define DIMENSION_IMPL_BVST_H - -typedef struct dmnsn_bvst dmnsn_bvst; -typedef struct dmnsn_bvst_node dmnsn_bvst_node; - -struct dmnsn_bvst { - dmnsn_bvst_node *root; -}; - -struct dmnsn_bvst_node { - /* Tree children */ - dmnsn_bvst_node *contains, *container; - - /* Parent node for easy backtracking */ - dmnsn_bvst_node *parent; - - /* Bounding box */ - dmnsn_bounding_box bounding_box; - - /* 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); - -bool dmnsn_bvst_search(dmnsn_bvst *tree, dmnsn_line ray, - dmnsn_intersection *intersection); - -#endif /* DIMENSION_IMPL_BVST_H */ 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 * + * * + * 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 * + * . * + *************************************************************************/ + +#include "dimension_impl.h" +#include + +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/prtree.h b/libdimension/prtree.h new file mode 100644 index 0000000..999bc14 --- /dev/null +++ b/libdimension/prtree.h @@ -0,0 +1,51 @@ +/************************************************************************* + * Copyright (C) 2010 Tavian Barnes * + * * + * 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 * + * . * + *************************************************************************/ + +/* + * 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_PRTREE_H +#define DIMENSION_IMPL_PRTREE_H + +#include + +/* Number of children per node */ +#define DMNSN_PRTREE_B 6 + +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; + +dmnsn_prtree *dmnsn_new_prtree(const dmnsn_array *objects); +void dmnsn_delete_prtree(dmnsn_prtree *tree); + +bool dmnsn_prtree_search(const dmnsn_prtree *tree, dmnsn_line ray, + dmnsn_intersection *intersection); + +#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/bvst.c deleted file mode 100644 index 33c737b..0000000 --- a/tests/libdimension/bvst.c +++ /dev/null @@ -1,72 +0,0 @@ -/************************************************************************* - * Copyright (C) 2010 Tavian Barnes * - * * - * This file is part of The Dimension Test Suite. * - * * - * The Dimension Test Suite is free software; you can redistribute it * - * and/or modify it under the terms of the GNU 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 Test Suite 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 * - * General Public License for more details. * - * * - * You should have received a copy of the GNU General Public License * - * along with this program. If not, see . * - *************************************************************************/ - -/* - * Basic tests of our Bounding Volume Splay Tree framework - */ - -#include "../../libdimension/dimension_impl.h" -#include - -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; -} diff --git a/tests/libdimension/prtree.c b/tests/libdimension/prtree.c new file mode 100644 index 0000000..c75d8da --- /dev/null +++ b/tests/libdimension/prtree.c @@ -0,0 +1,31 @@ +/************************************************************************* + * Copyright (C) 2010 Tavian Barnes * + * * + * This file is part of The Dimension Test Suite. * + * * + * The Dimension Test Suite is free software; you can redistribute it * + * and/or modify it under the terms of the GNU 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 Test Suite 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 * + * General Public License for more details. * + * * + * You should have received a copy of the GNU General Public License * + * along with this program. If not, see . * + *************************************************************************/ + +/* + * Basic tests of PR-trees + */ + +#include "../../libdimension/dimension_impl.h" +#include + +int +main() +{ + return EXIT_SUCCESS; +} -- cgit v1.2.3