diff options
Diffstat (limited to 'libdimension')
| -rw-r--r-- | libdimension/Makefile.am | 4 | ||||
| -rw-r--r-- | libdimension/bvst.c | 388 | ||||
| -rw-r--r-- | libdimension/dimension_impl.h | 2 | ||||
| -rw-r--r-- | libdimension/prtree.c | 574 | ||||
| -rw-r--r-- | libdimension/prtree.h (renamed from libdimension/bvst.h) | 53 | ||||
| -rw-r--r-- | libdimension/raytrace.c | 31 |
6 files changed, 606 insertions, 446 deletions
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) { |