summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--libdimension/prtree.c212
1 files changed, 115 insertions, 97 deletions
diff --git a/libdimension/prtree.c b/libdimension/prtree.c
index ba26d30..c012e6f 100644
--- a/libdimension/prtree.c
+++ b/libdimension/prtree.c
@@ -1,5 +1,5 @@
/*************************************************************************
- * Copyright (C) 2010-2012 Tavian Barnes <tavianator@tavianator.com> *
+ * Copyright (C) 2010-2013 Tavian Barnes <tavianator@tavianator.com> *
* *
* This file is part of The Dimension Library. *
* *
@@ -57,78 +57,54 @@ enum {
DMNSN_ZMAX
};
-/** Get a coordinate of the bounding box of a node. */
-static inline double
-dmnsn_get_coordinate(const dmnsn_bvh_node * const *node, int comparator)
-{
- switch (comparator) {
- case DMNSN_XMIN:
- return (*node)->bounding_box.min.x;
- case DMNSN_YMIN:
- return (*node)->bounding_box.min.y;
- case DMNSN_ZMIN:
- return (*node)->bounding_box.min.z;
-
- case DMNSN_XMAX:
- return -(*node)->bounding_box.max.x;
- case DMNSN_YMAX:
- return -(*node)->bounding_box.max.y;
- case DMNSN_ZMAX:
- return -(*node)->bounding_box.max.z;
-
- default:
- dmnsn_unreachable("Invalid comparator.");
- }
-}
-
/* List sorting comparators */
static int
dmnsn_xmin_comp(const void *l, const void *r)
{
- double lval = dmnsn_get_coordinate(l, DMNSN_XMIN);
- double rval = dmnsn_get_coordinate(r, DMNSN_XMIN);
+ double lval = (*(const dmnsn_bvh_node **)l)->bounding_box.min.x;
+ double rval = (*(const dmnsn_bvh_node **)r)->bounding_box.min.x;
return (lval > rval) - (lval < rval);
}
static int
dmnsn_ymin_comp(const void *l, const void *r)
{
- double lval = dmnsn_get_coordinate(l, DMNSN_YMIN);
- double rval = dmnsn_get_coordinate(r, DMNSN_YMIN);
+ double lval = (*(const dmnsn_bvh_node **)l)->bounding_box.min.y;
+ double rval = (*(const dmnsn_bvh_node **)r)->bounding_box.min.y;
return (lval > rval) - (lval < rval);
}
static int
dmnsn_zmin_comp(const void *l, const void *r)
{
- double lval = dmnsn_get_coordinate(l, DMNSN_ZMIN);
- double rval = dmnsn_get_coordinate(r, DMNSN_ZMIN);
+ double lval = (*(const dmnsn_bvh_node **)l)->bounding_box.min.z;
+ double rval = (*(const dmnsn_bvh_node **)r)->bounding_box.min.z;
return (lval > rval) - (lval < rval);
}
static int
dmnsn_xmax_comp(const void *l, const void *r)
{
- double lval = dmnsn_get_coordinate(l, DMNSN_XMAX);
- double rval = dmnsn_get_coordinate(r, DMNSN_XMAX);
- return (lval > rval) - (lval < rval);
+ double lval = (*(const dmnsn_bvh_node **)l)->bounding_box.max.x;
+ double rval = (*(const dmnsn_bvh_node **)r)->bounding_box.max.x;
+ return (lval < rval) - (lval > rval);
}
static int
dmnsn_ymax_comp(const void *l, const void *r)
{
- double lval = dmnsn_get_coordinate(l, DMNSN_YMAX);
- double rval = dmnsn_get_coordinate(r, DMNSN_YMAX);
- return (lval > rval) - (lval < rval);
+ double lval = (*(const dmnsn_bvh_node **)l)->bounding_box.max.y;
+ double rval = (*(const dmnsn_bvh_node **)r)->bounding_box.max.y;
+ return (lval < rval) - (lval > rval);
}
static int
dmnsn_zmax_comp(const void *l, const void *r)
{
- double lval = dmnsn_get_coordinate(l, DMNSN_ZMAX);
- double rval = dmnsn_get_coordinate(r, DMNSN_ZMAX);
- return (lval > rval) - (lval < rval);
+ double lval = (*(const dmnsn_bvh_node **)l)->bounding_box.max.z;
+ double rval = (*(const dmnsn_bvh_node **)r)->bounding_box.max.z;
+ return (lval < rval) - (lval > rval);
}
/** All comparators. */
@@ -138,19 +114,20 @@ static dmnsn_array_comparator_fn *const dmnsn_comparators[DMNSN_PSEUDO_B] = {
[DMNSN_ZMIN] = dmnsn_zmin_comp,
[DMNSN_XMAX] = dmnsn_xmax_comp,
[DMNSN_YMAX] = dmnsn_ymax_comp,
- [DMNSN_ZMAX] = dmnsn_zmax_comp
+ [DMNSN_ZMAX] = dmnsn_zmax_comp,
};
/** Add the priority leaves for this level. */
static void
-dmnsn_add_priority_leaves(dmnsn_array *sorted_leaves[DMNSN_PSEUDO_B],
+dmnsn_add_priority_leaves(dmnsn_bvh_node **sorted_leaves[DMNSN_PSEUDO_B],
+ size_t nleaves,
dmnsn_array *new_leaves)
{
for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
dmnsn_bvh_node *leaf = NULL;
- dmnsn_bvh_node **leaves = dmnsn_array_first(sorted_leaves[i]);
- for (size_t j = 0, size = dmnsn_array_size(sorted_leaves[i]);
- j < size && (!leaf || leaf->nchildren < DMNSN_PRTREE_B);
+ dmnsn_bvh_node **leaves = sorted_leaves[i];
+ for (size_t j = 0;
+ j < nleaves && (!leaf || leaf->nchildren < DMNSN_PRTREE_B);
++j)
{
/* Skip all the previously found extreme nodes */
@@ -173,80 +150,112 @@ dmnsn_add_priority_leaves(dmnsn_array *sorted_leaves[DMNSN_PSEUDO_B],
}
}
-/** Split the sorted lists into the left and right subtrees. */
-static bool
-dmnsn_split_sorted_leaves(dmnsn_array *sorted_leaves[DMNSN_PSEUDO_B],
- dmnsn_array *right_sorted_leaves[DMNSN_PSEUDO_B],
- size_t i)
+static void
+dmnsn_split_sorted_leaves_easy(dmnsn_bvh_node **leaves,
+ size_t *nleaves,
+ size_t *nright_leaves)
{
/* Get rid of the extreme nodes */
- dmnsn_bvh_node **leaves = dmnsn_array_first(sorted_leaves[i]);
- size_t j, skip;
- for (j = 0, skip = 0; j < dmnsn_array_size(sorted_leaves[i]); ++j) {
- if (leaves[j]->data == DMNSN_PRTREE_LEAF) {
+ size_t i, skip, size = *nleaves;
+ for (i = 0, skip = 0; i < size; ++i) {
+ if (leaves[i]->data == DMNSN_PRTREE_LEAF) {
++skip;
} else {
- leaves[j - skip] = leaves[j];
+ leaves[i - skip] = leaves[i];
}
}
- dmnsn_array_resize(sorted_leaves[i], j - skip);
- if (dmnsn_array_size(sorted_leaves[i]) == 0) {
- return false;
+ size -= skip;
+
+ /* Split the leaves and mark the left and right child nodes */
+ size_t left_size = (size + 1)/2;
+ for (i = 0; i < left_size; ++i) {
+ leaves[i]->data = DMNSN_PRTREE_LEFT;
+ }
+ for (i = left_size; i < size; ++i) {
+ leaves[i]->data = DMNSN_PRTREE_RIGHT;
}
- /* Split the appropriate list and mark the left and right child nodes */
- right_sorted_leaves[i] = dmnsn_array_split(sorted_leaves[i]);
- DMNSN_ARRAY_FOREACH (dmnsn_bvh_node **, node, sorted_leaves[i]) {
- (*node)->data = DMNSN_PRTREE_LEFT;
+ *nleaves = left_size;
+ *nright_leaves = size - left_size;
+}
+
+static void
+dmnsn_split_sorted_leaves_hard(dmnsn_bvh_node **leaves,
+ dmnsn_bvh_node **buffer,
+ size_t nleaves)
+{
+ size_t i, j, skip;
+ for (i = 0, j = 0, skip = 0; i < nleaves; ++i) {
+ if (leaves[i]->data == DMNSN_PRTREE_LEFT) {
+ leaves[i - skip] = leaves[i];
+ } else {
+ if (leaves[i]->data == DMNSN_PRTREE_RIGHT) {
+ buffer[j] = leaves[i];
+ ++j;
+ }
+ ++skip;
+ }
}
- DMNSN_ARRAY_FOREACH (dmnsn_bvh_node **, node, right_sorted_leaves[i]) {
- (*node)->data = DMNSN_PRTREE_RIGHT;
+
+ size_t left_size = i - skip;
+ for (i = 0; i < j; ++i) {
+ leaves[left_size + i] = buffer[i];
}
+}
+
+/** Split the sorted lists into the left and right subtrees. */
+static void
+dmnsn_split_sorted_leaves(dmnsn_bvh_node **sorted_leaves[DMNSN_PSEUDO_B],
+ size_t *nleaves,
+ dmnsn_bvh_node **right_sorted_leaves[DMNSN_PSEUDO_B],
+ size_t *nright_leaves,
+ dmnsn_bvh_node **buffer,
+ size_t i)
+{
+ size_t original_size = *nleaves;
+
+ /* Split the ith list */
+ dmnsn_split_sorted_leaves_easy(sorted_leaves[i], nleaves, nright_leaves);
/* Split the rest of the lists */
for (size_t j = 0; j < DMNSN_PSEUDO_B; ++j) {
- if (j != i) {
- right_sorted_leaves[j] = dmnsn_new_array(sizeof(dmnsn_bvh_node *));
-
- dmnsn_bvh_node **leaves = dmnsn_array_first(sorted_leaves[j]);
- size_t k, skip;
- for (k = 0, skip = 0; k < dmnsn_array_size(sorted_leaves[j]); ++k) {
- if (leaves[k]->data == DMNSN_PRTREE_LEAF) {
- ++skip;
- } else if (leaves[k]->data == DMNSN_PRTREE_RIGHT) {
- dmnsn_array_push(right_sorted_leaves[j], &leaves[k]);
- ++skip;
- } else {
- leaves[k - skip] = leaves[k];
- }
- }
- dmnsn_array_resize(sorted_leaves[j], k - skip);
+ right_sorted_leaves[j] = sorted_leaves[j] + *nleaves;
+ if (j == i) {
+ continue;
}
- }
- return true;
+ dmnsn_split_sorted_leaves_hard(sorted_leaves[j], buffer, original_size);
+ }
}
/** Recursively constructs an implicit pseudo-PR-tree and collects the priority
leaves. */
static void
-dmnsn_priority_leaves_recursive(dmnsn_array *sorted_leaves[DMNSN_PSEUDO_B],
+dmnsn_priority_leaves_recursive(dmnsn_bvh_node **sorted_leaves[DMNSN_PSEUDO_B],
+ size_t nleaves,
+ dmnsn_bvh_node **buffer,
dmnsn_array *new_leaves,
int comparator)
{
- dmnsn_add_priority_leaves(sorted_leaves, new_leaves);
+ dmnsn_add_priority_leaves(sorted_leaves, nleaves, new_leaves);
+
+ dmnsn_bvh_node **right_sorted_leaves[DMNSN_PSEUDO_B];
+ size_t right_nleaves;
- dmnsn_array *right_sorted_leaves[DMNSN_PSEUDO_B];
- if (dmnsn_split_sorted_leaves(sorted_leaves, right_sorted_leaves, comparator))
- {
- dmnsn_priority_leaves_recursive(right_sorted_leaves, new_leaves,
+ dmnsn_split_sorted_leaves(sorted_leaves, &nleaves,
+ right_sorted_leaves, &right_nleaves,
+ buffer, comparator);
+
+ if (nleaves > 0) {
+ dmnsn_priority_leaves_recursive(sorted_leaves, nleaves,
+ buffer, new_leaves,
(comparator + 1)%DMNSN_PSEUDO_B);
- for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
- dmnsn_delete_array(right_sorted_leaves[i]);
- }
+ }
- dmnsn_priority_leaves_recursive(sorted_leaves, new_leaves,
+ if (right_nleaves > 0) {
+ dmnsn_priority_leaves_recursive(right_sorted_leaves, right_nleaves,
+ buffer, new_leaves,
(comparator + 1)%DMNSN_PSEUDO_B);
}
}
@@ -255,17 +264,26 @@ dmnsn_priority_leaves_recursive(dmnsn_array *sorted_leaves[DMNSN_PSEUDO_B],
static dmnsn_array *
dmnsn_priority_leaves(const dmnsn_array *leaves)
{
- dmnsn_array *sorted_leaves[DMNSN_PSEUDO_B];
+ dmnsn_bvh_node **leaves_arr = dmnsn_array_first(leaves);
+ dmnsn_bvh_node **sorted_leaves[DMNSN_PSEUDO_B];
+ size_t nleaves = dmnsn_array_size(leaves);
+ size_t leaves_size = nleaves*sizeof(dmnsn_bvh_node *);
+
for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
- sorted_leaves[i] = dmnsn_array_copy(leaves);
- dmnsn_array_sort(sorted_leaves[i], dmnsn_comparators[i]);
+ sorted_leaves[i] = dmnsn_malloc(leaves_size);
+ memcpy(sorted_leaves[i], leaves_arr, leaves_size);
+ qsort(sorted_leaves[i], nleaves, sizeof(dmnsn_bvh_node *),
+ dmnsn_comparators[i]);
}
dmnsn_array *new_leaves = dmnsn_new_array(sizeof(dmnsn_bvh_node *));
- dmnsn_priority_leaves_recursive(sorted_leaves, new_leaves, 0);
+ dmnsn_bvh_node **buffer = dmnsn_malloc(leaves_size/2);
+ dmnsn_priority_leaves_recursive(sorted_leaves, nleaves, buffer, new_leaves,
+ 0);
+ dmnsn_free(buffer);
for (size_t i = 0; i < DMNSN_PSEUDO_B; ++i) {
- dmnsn_delete_array(sorted_leaves[i]);
+ dmnsn_free(sorted_leaves[i]);
}
return new_leaves;