From 450eb86adf1d0634dd4c97bfc1bae405ca51f491 Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Sun, 6 Jun 2010 00:20:43 -0600 Subject: New bounding box special constructors. --- libdimension/csg.c | 2 +- libdimension/dimension/geometry.h | 20 +++++++++++++++++++ libdimension/plane.c | 3 +-- libdimension/prtree.c | 42 +++++++++++++-------------------------- libdimension/prtree.h | 1 + 5 files changed, 37 insertions(+), 31 deletions(-) diff --git a/libdimension/csg.c b/libdimension/csg.c index 0f6c4c1..02c4d37 100644 --- a/libdimension/csg.c +++ b/libdimension/csg.c @@ -67,7 +67,7 @@ dmnsn_csg_union_init_fn(dmnsn_object *csg) dmnsn_prtree *prtree = dmnsn_new_prtree(csg->children); csg->ptr = prtree; - csg->bounding_box = prtree->root->bounding_box; + csg->bounding_box = prtree->bounding_box; } static void diff --git a/libdimension/dimension/geometry.h b/libdimension/dimension/geometry.h index 8e2e47c..effac7c 100644 --- a/libdimension/dimension/geometry.h +++ b/libdimension/dimension/geometry.h @@ -101,6 +101,26 @@ dmnsn_new_line(dmnsn_vector x0, dmnsn_vector n) return l; } +DMNSN_INLINE dmnsn_bounding_box +dmnsn_zero_bounding_box() +{ + dmnsn_bounding_box box = { + { INFINITY, INFINITY, INFINITY }, + { -INFINITY, -INFINITY, -INFINITY } + }; + return box; +} + +DMNSN_INLINE dmnsn_bounding_box +dmnsn_infinite_bounding_box() +{ + dmnsn_bounding_box box = { + { -INFINITY, -INFINITY, -INFINITY }, + { INFINITY, INFINITY, INFINITY } + }; + return box; +} + /* Vector element access */ enum { diff --git a/libdimension/plane.c b/libdimension/plane.c index 76071df..ce39561 100644 --- a/libdimension/plane.c +++ b/libdimension/plane.c @@ -46,8 +46,7 @@ dmnsn_new_plane(dmnsn_vector normal) plane->intersection_fn = &dmnsn_plane_intersection_fn; plane->inside_fn = &dmnsn_plane_inside_fn; plane->free_fn = &free; - plane->bounding_box.min = dmnsn_new_vector(-INFINITY, -INFINITY, -INFINITY); - plane->bounding_box.max = dmnsn_new_vector(INFINITY, INFINITY, INFINITY); + plane->bounding_box = dmnsn_infinite_bounding_box(); plane->ptr = param; return plane; } diff --git a/libdimension/prtree.c b/libdimension/prtree.c index e42748e..cce8b38 100644 --- a/libdimension/prtree.c +++ b/libdimension/prtree.c @@ -243,8 +243,7 @@ dmnsn_new_pseudo_prtree(dmnsn_list *leaves, bool are_objects, int comparator) 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; + pseudo->leaf.bounding_box = dmnsn_zero_bounding_box(); size_t i; dmnsn_list_iterator *ii; @@ -258,11 +257,7 @@ dmnsn_new_pseudo_prtree(dmnsn_list *leaves, bool are_objects, int comparator) 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); - } + dmnsn_pseudo_prleaf_swallow(&pseudo->leaf, object->bounding_box); } } else { pseudo->leaf.is_leaf = false; @@ -274,11 +269,7 @@ dmnsn_new_pseudo_prtree(dmnsn_list *leaves, bool are_objects, int comparator) 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); - } + dmnsn_pseudo_prleaf_swallow(&pseudo->leaf, prnode->bounding_box); } } @@ -290,6 +281,7 @@ dmnsn_new_pseudo_prtree(dmnsn_list *leaves, bool are_objects, int comparator) pseudo->is_leaf = false; for (size_t i = 0; i < 6; ++i) { pseudo->node.children[i].is_leaf = are_objects; + pseudo->node.children[i].bounding_box = dmnsn_zero_bounding_box(); } /* Fill the priority leaves */ @@ -304,22 +296,14 @@ dmnsn_new_pseudo_prtree(dmnsn_list *leaves, bool are_objects, int comparator) 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); - } + dmnsn_pseudo_prleaf_swallow(&pseudo->node.children[j], + object->bounding_box); } else { dmnsn_prtree_node *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_pseudo_prleaf_swallow(&pseudo->node.children[j], + prnode->bounding_box); } dmnsn_list_remove(leaves, k); @@ -332,10 +316,6 @@ dmnsn_new_pseudo_prtree(dmnsn_list *leaves, bool are_objects, int comparator) /* 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; @@ -507,6 +487,12 @@ dmnsn_new_prtree(const dmnsn_array *objects) dmnsn_list_get(dmnsn_list_first(leaves), &prtree->root); prtree->unbounded = dmnsn_array_from_list(unbounded); + if (dmnsn_array_size(prtree->unbounded) > 0) { + prtree->bounding_box = dmnsn_infinite_bounding_box(); + } else { + prtree->bounding_box = prtree->root->bounding_box; + } + dmnsn_delete_list(unbounded); dmnsn_delete_list(leaves); return prtree; diff --git a/libdimension/prtree.h b/libdimension/prtree.h index 30ecbd6..7848879 100644 --- a/libdimension/prtree.h +++ b/libdimension/prtree.h @@ -43,6 +43,7 @@ typedef struct dmnsn_prtree_node { } dmnsn_prtree_node; typedef struct dmnsn_prtree { + dmnsn_bounding_box bounding_box; dmnsn_prtree_node *root; dmnsn_array *unbounded; } dmnsn_prtree; -- cgit v1.2.3