diff options
Diffstat (limited to 'libdimension/bvh.c')
| -rw-r--r-- | libdimension/bvh.c | 404 |
1 files changed, 0 insertions, 404 deletions
diff --git a/libdimension/bvh.c b/libdimension/bvh.c deleted file mode 100644 index d1bd0fc..0000000 --- a/libdimension/bvh.c +++ /dev/null @@ -1,404 +0,0 @@ -/************************************************************************* - * Copyright (C) 2012-2014 Tavian Barnes <tavianator@tavianator.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/>. * - *************************************************************************/ - -/** - * @file - * BVH implementation. These are the hottest code paths in libdimension. - */ - -#include "dimension-internal.h" - -/// Implementation for DMNSN_BVH_NONE: just stick all objects in one node. -static dmnsn_bvh_node * -dmnsn_new_stupid_bvh(const dmnsn_array *objects) -{ - dmnsn_bvh_node *root = dmnsn_new_bvh_node(dmnsn_array_size(objects)); - - DMNSN_ARRAY_FOREACH (dmnsn_object **, object, objects) { - dmnsn_bvh_node *leaf = dmnsn_new_bvh_leaf_node(*object); - dmnsn_bvh_node_add(root, leaf); - } - - return root; -} - -// Implementation of opaque dmnsn_bvh type. -struct dmnsn_bvh { - dmnsn_array *unbounded; ///< The unbounded objects. - dmnsn_array *bounded; ///< The BVH of the bounded objects. - pthread_key_t intersection_cache; ///< The thread-local intersection cache. -}; - -/// A flat BVH node for storing in an array for fast pre-order traversal. -typedef struct dmnsn_flat_bvh_node { - dmnsn_bounding_box bounding_box; // The bounding box of this node. - dmnsn_object *object; // The referenced object, for leaf nodes. - ptrdiff_t skip; // Displacement to the next sibling. -} dmnsn_flat_bvh_node; - -/// Add an object or its children, if any, to an array. -static void -dmnsn_split_add_object(dmnsn_array *objects, const dmnsn_object *object) -{ - if (object->split_children) { - DMNSN_ARRAY_FOREACH (const dmnsn_object **, child, object->children) { - dmnsn_split_add_object(objects, *child); - } - } else { - dmnsn_array_push(objects, &object); - } -} - -/// Split unions to create the input for the BVH. -static dmnsn_array * -dmnsn_split_objects(const dmnsn_array *objects) -{ - dmnsn_array *split = DMNSN_NEW_ARRAY(dmnsn_object *); - DMNSN_ARRAY_FOREACH (const dmnsn_object **, object, objects) { - dmnsn_split_add_object(split, *object); - } - return split; -} - -/// Split unbounded objects into a new array. -static dmnsn_array * -dmnsn_split_unbounded(dmnsn_array *objects) -{ - dmnsn_array *unbounded = DMNSN_NEW_ARRAY(dmnsn_object *); - - dmnsn_object **array = dmnsn_array_first(objects); - size_t i, skip; - for (i = 0, skip = 0; i < dmnsn_array_size(objects); ++i) { - if (dmnsn_bounding_box_is_infinite(array[i]->bounding_box)) { - dmnsn_array_push(unbounded, &array[i]); - ++skip; - } else { - array[i - skip] = array[i]; - } - } - dmnsn_array_resize(objects, i - skip); - - return unbounded; -} - -/// Recursively flatten a BVH into an array of flat nodes. -static void -dmnsn_flatten_bvh_recursive(dmnsn_bvh_node *node, dmnsn_array *flat) -{ - size_t currenti = dmnsn_array_size(flat); - dmnsn_array_resize(flat, currenti + 1); - dmnsn_flat_bvh_node *flatnode = dmnsn_array_at(flat, currenti); - - flatnode->bounding_box = node->bounding_box; - flatnode->object = node->object; - - for (size_t i = 0; i < node->nchildren && node->children[i]; ++i) { - dmnsn_flatten_bvh_recursive(node->children[i], flat); - } - - // Array could have been realloc()'d somewhere else above - flatnode = dmnsn_array_at(flat, currenti); - flatnode->skip = dmnsn_array_size(flat) - currenti; -} - -/// Flatten a BVH into an array of flat nodes. -static dmnsn_array * -dmnsn_flatten_bvh(dmnsn_bvh_node *root) -{ - dmnsn_array *flat = DMNSN_NEW_ARRAY(dmnsn_flat_bvh_node); - if (root) { - dmnsn_flatten_bvh_recursive(root, flat); - } - return flat; -} - -dmnsn_bvh *dmnsn_new_bvh(const dmnsn_array *objects, dmnsn_bvh_kind kind) -{ - dmnsn_bvh *bvh = DMNSN_MALLOC(dmnsn_bvh); - - dmnsn_array *bounded = dmnsn_split_objects(objects); - bvh->unbounded = dmnsn_split_unbounded(bounded); - - dmnsn_bvh_node *root = NULL; - if (dmnsn_array_size(bounded) > 0) { - switch (kind) { - case DMNSN_BVH_NONE: - root = dmnsn_new_stupid_bvh(bounded); - break; - case DMNSN_BVH_PRTREE: - root = dmnsn_new_prtree(bounded); - break; - default: - dmnsn_unreachable("Invalid BVH kind."); - } - } - bvh->bounded = dmnsn_flatten_bvh(root); - - dmnsn_delete_bvh_node(root); - dmnsn_delete_array(bounded); - - dmnsn_key_create(&bvh->intersection_cache, dmnsn_free); - - return bvh; -} - -void -dmnsn_delete_bvh(dmnsn_bvh *bvh) -{ - if (bvh) { - dmnsn_free(pthread_getspecific(bvh->intersection_cache)); - dmnsn_key_delete(bvh->intersection_cache); - dmnsn_delete_array(bvh->bounded); - dmnsn_delete_array(bvh->unbounded); - dmnsn_free(bvh); - } -} - -/// A line with pre-calculated reciprocals to avoid divisions. -typedef struct dmnsn_optimized_line { - dmnsn_vector x0; ///< The origin of the line. - dmnsn_vector n_inv; ///< The inverse of each component of the line's slope -} dmnsn_optimized_line; - -/// Precompute inverses for faster ray-box intersection tests. -static inline dmnsn_optimized_line -dmnsn_optimize_line(dmnsn_line line) -{ - dmnsn_optimized_line optline = { - .x0 = line.x0, - .n_inv = dmnsn_new_vector(1.0/line.n.x, 1.0/line.n.y, 1.0/line.n.z) - }; - return optline; -} - -/// Ray-AABB intersection test, by the slab method. Highly optimized. -static inline bool -dmnsn_ray_box_intersection(dmnsn_optimized_line optline, - dmnsn_bounding_box box, double t) -{ - // This is actually correct, even though it appears not to handle edge cases - // (line.n.{x,y,z} == 0). It works because the infinities that result from - // dividing by zero will still behave correctly in the comparisons. Lines - // which are parallel to an axis and outside the box will have tmin == inf - // or tmax == -inf, while lines inside the box will have tmin and tmax - // unchanged. - - double tx1 = (box.min.x - optline.x0.x)*optline.n_inv.x; - double tx2 = (box.max.x - optline.x0.x)*optline.n_inv.x; - - double tmin = dmnsn_min(tx1, tx2); - double tmax = dmnsn_max(tx1, tx2); - - double ty1 = (box.min.y - optline.x0.y)*optline.n_inv.y; - double ty2 = (box.max.y - optline.x0.y)*optline.n_inv.y; - - tmin = dmnsn_max(tmin, dmnsn_min(ty1, ty2)); - tmax = dmnsn_min(tmax, dmnsn_max(ty1, ty2)); - - double tz1 = (box.min.z - optline.x0.z)*optline.n_inv.z; - double tz2 = (box.max.z - optline.x0.z)*optline.n_inv.z; - - tmin = dmnsn_max(tmin, dmnsn_min(tz1, tz2)); - tmax = dmnsn_min(tmax, dmnsn_max(tz1, tz2)); - - return tmax >= dmnsn_max(0.0, tmin) && tmin < t; -} - -/// The number of intersections to cache. -#define DMNSN_INTERSECTION_CACHE_SIZE 32 - -/// An array of cached intersections. -typedef struct dmnsn_intersection_cache { - size_t i; - dmnsn_object *objects[DMNSN_INTERSECTION_CACHE_SIZE]; -} dmnsn_intersection_cache; - -static dmnsn_intersection_cache * -dmnsn_get_intersection_cache(const dmnsn_bvh *bvh) -{ - dmnsn_intersection_cache *cache - = pthread_getspecific(bvh->intersection_cache); - - if (!cache) { - cache = DMNSN_MALLOC(dmnsn_intersection_cache); - cache->i = 0; - for (size_t i = 0; i < DMNSN_INTERSECTION_CACHE_SIZE; ++i) { - cache->objects[i] = NULL; - } - dmnsn_setspecific(bvh->intersection_cache, cache); - } - - return cache; -} - -/// Test for a closer object intersection than we've found so far. -static inline bool -dmnsn_closer_intersection(dmnsn_object *object, dmnsn_line ray, - dmnsn_intersection *intersection, double *t) -{ - dmnsn_intersection local_intersection; - if (dmnsn_object_intersection(object, ray, &local_intersection)) { - if (local_intersection.t < *t) { - *intersection = local_intersection; - *t = local_intersection.t; - return true; - } - } - return false; -} - -DMNSN_HOT bool -dmnsn_bvh_intersection(const dmnsn_bvh *bvh, dmnsn_line ray, - dmnsn_intersection *intersection, bool reset) -{ - double t = INFINITY; - - // Search the unbounded objects - DMNSN_ARRAY_FOREACH (dmnsn_object **, object, bvh->unbounded) { - dmnsn_closer_intersection(*object, ray, intersection, &t); - } - - // Precalculate 1.0/ray.n.{x,y,z} to save time in intersection tests - dmnsn_optimized_line optline = dmnsn_optimize_line(ray); - - // Search the intersection cache - dmnsn_intersection_cache *cache = dmnsn_get_intersection_cache(bvh); - if (dmnsn_unlikely(reset)) { - cache->i = 0; - } - dmnsn_object *cached = NULL, *found = NULL; - if (dmnsn_likely(cache->i < DMNSN_INTERSECTION_CACHE_SIZE)) { - cached = cache->objects[cache->i]; - } - if (cached && dmnsn_ray_box_intersection(optline, cached->bounding_box, t)) { - if (dmnsn_closer_intersection(cached, ray, intersection, &t)) { - found = cached; - } - } - - // Search the bounded objects - dmnsn_flat_bvh_node *node = dmnsn_array_first(bvh->bounded); - dmnsn_flat_bvh_node *last = dmnsn_array_last(bvh->bounded); - while (node <= last) { - if (dmnsn_ray_box_intersection(optline, node->bounding_box, t)) { - if (node->object && node->object != cached) { - if (dmnsn_closer_intersection(node->object, ray, intersection, &t)) { - found = node->object; - } - } - ++node; - } else { - node += node->skip; - } - } - - // Update the cache - if (dmnsn_likely(cache->i < DMNSN_INTERSECTION_CACHE_SIZE)) { - cache->objects[cache->i] = found; - ++cache->i; - } - - return !isinf(t); -} - -DMNSN_HOT bool -dmnsn_bvh_inside(const dmnsn_bvh *bvh, dmnsn_vector point) -{ - // Search the unbounded objects - DMNSN_ARRAY_FOREACH (dmnsn_object **, object, bvh->unbounded) { - if (dmnsn_object_inside(*object, point)) - return true; - } - - // Search the bounded objects - dmnsn_flat_bvh_node *node = dmnsn_array_first(bvh->bounded); - dmnsn_flat_bvh_node *last = dmnsn_array_last(bvh->bounded); - while (node <= last) { - if (dmnsn_bounding_box_contains(node->bounding_box, point)) { - if (node->object && dmnsn_object_inside(node->object, point)) { - return true; - } - ++node; - } else { - node += node->skip; - } - } - - return false; -} - -dmnsn_bounding_box -dmnsn_bvh_bounding_box(const dmnsn_bvh *bvh) -{ - if (dmnsn_array_size(bvh->unbounded) > 0) { - return dmnsn_infinite_bounding_box(); - } else if (dmnsn_array_size(bvh->bounded) > 0) { - dmnsn_flat_bvh_node *root = dmnsn_array_first(bvh->bounded); - return root->bounding_box; - } else { - return dmnsn_zero_bounding_box(); - } -} - -dmnsn_bvh_node * -dmnsn_new_bvh_node(unsigned int max_children) -{ - dmnsn_bvh_node *node = dmnsn_malloc(sizeof(dmnsn_bvh_node) + max_children*sizeof(dmnsn_bvh_node *)); - node->bounding_box = dmnsn_zero_bounding_box(); - node->object = NULL; - node->nchildren = 0; - node->max_children = max_children; - return node; -} - -dmnsn_bvh_node * -dmnsn_new_bvh_leaf_node(dmnsn_object *object) -{ - dmnsn_bvh_node *node = DMNSN_MALLOC(dmnsn_bvh_node); - node->bounding_box = object->bounding_box; - node->object = object; - node->nchildren = 0; - node->max_children = 0; - return node; -} - -void -dmnsn_delete_bvh_node(dmnsn_bvh_node *node) -{ - if (node) { - for (size_t i = 0; i < node->nchildren; ++i) { - dmnsn_delete_bvh_node(node->children[i]); - } - dmnsn_free(node); - } -} - -void -dmnsn_bvh_node_add(dmnsn_bvh_node *parent, dmnsn_bvh_node *child) -{ - dmnsn_assert(parent->nchildren < parent->max_children, - "Too many BVH children inserted."); - - parent->bounding_box.min = dmnsn_vector_min(parent->bounding_box.min, - child->bounding_box.min); - parent->bounding_box.max = dmnsn_vector_max(parent->bounding_box.max, - child->bounding_box.max); - parent->children[parent->nchildren++] = child; -} |