/****************************************************************************\ Copyright 1995 The University of North Carolina at Chapel Hill. All Rights Reserved. Permission to use, copy, modify and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice and the following three paragraphs appear in all copies. IN NO EVENT SHALL THE UNIVERSITY OF NORTH CAROLINA AT CHAPEL HILL BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES, INCLUDING LOST PROFITS, ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF NORTH CAROLINA HAVE BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES. Permission to use, copy, modify and distribute this software and its documentation for educational, research and non-profit purposes, without fee, and without a written agreement is hereby granted, provided that the above copyright notice and the following three paragraphs appear in all copies. THE UNIVERSITY OF NORTH CAROLINA SPECIFICALLY DISCLAIM ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF NORTH CAROLINA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. The authors may be contacted via: US Mail: Jonathan Cohen Amitabh Varshney Department of Computer Science Department of Computer Science Sitterson Hall, CB #3175 State University of New York University of N. Carolina Stony Brook, NY 11794-4400, USA Chapel Hill, NC 27599-3175 Phone: (919)962-1749 Phone: (516)632-8446 EMail: cohenj@cs.unc.edu varshney@cs.sunysb.edu \****************************************************************************/ /*****************************************************************************\ octree.c -- Description : Functions for octree space partitioning. This code currently uses only axis-aligned boxes for data elements and for querying. This doesn't work so well for long, thin, non-axis aligned triangles (i.e. you get a huge octree that bottoms out all over the place, and queries typically return O(n) overlaps). ---------------------------------------------------------------------------- $Source: /cvs/RenderPark/SE/Simplify/octree.c,v $ $Revision: 1.1.1.1 $ $Date: 2000/04/06 15:35:32 $ $Author: philippe $ $Locker: $ \*****************************************************************************/ /*----------------------------- Local Includes -----------------------------*/ #include #include #include /*----------------------------- Local Constants -----------------------------*/ /*------------------------------ Local Macros -------------------------------*/ #define MAX_RESOLUTION 64 #define MIN_MAX_NODE_OBJS 2 /*------------------------------- Local Types -------------------------------*/ /*------------------------ Local Function Prototypes ------------------------*/ static int get_child_overlap(Octree *tree, OctreeNode *node, Extents bbox); static void init_children(Octree *tree, OctreeNode *node); static void ot_insert(Octree *tree, OctreeNode *node, OctreeData *data); static void ot_remove(Octree *tree, OctreeNode *node, OctreeData *data); static void destroy_node(OctreeNode *node); static void range_query(Octree *tree, OctreeNode *node, Extents bbox, OctreeData **element_list, int *num_elements); static OctreeNode *point_query(Octree *tree, OctreeNode *node, Point point); static void print_leaf_stats(Octree *tree, OctreeNode *node, int *leaf_count, int *element_count, int *maxout_count); /*------------------------------ Local Globals ------------------------------*/ /*---------------------------------Functions-------------------------------- */ /*****************************************************************************\ @ get_child_overlap() ----------------------------------------------------------------------------- description : Given a query box and an octree cell, determine which of the 8 sub-cells the query box overlaps input : Octree, node in the octree, and query box output : 8-bit vector with 1's in the bits corresponding cells which overlap the query box and 0's in the rest notes : \*****************************************************************************/ static int get_child_overlap(Octree *tree, OctreeNode *node, Extents bbox) { #if 0 int overlap; overlap = 0; if (bbox[HI][X] > node->center[X] - tree->delta) { if (bbox[HI][Y] > node->center[Y] - tree->delta) { if (bbox[HI][Z] > node->center[Z] - tree->delta) overlap |= 1 << HXHYHZ; if (bbox[LO][Z] <= node->center[Z] + tree->delta) overlap |= 1 << HXHYLZ; } if (bbox[LO][Y] <= node->center[Y] + tree->delta) { if (bbox[HI][Z] > node->center[Z] - tree->delta) overlap |= 1 << HXLYHZ; if (bbox[LO][Z] <= node->center[Z] + tree->delta) overlap |= 1 << HXLYLZ; } } if (bbox[LO][X] <= node->center[X] + tree->delta) { if (bbox[HI][Y] > node->center[Y] - tree->delta) { if (bbox[HI][Z] > node->center[Z] - tree->delta) overlap |= 1 << LXHYHZ; if (bbox[LO][Z] <= node->center[Z] + tree->delta) overlap |= 1 << LXHYLZ; } if (bbox[LO][Y] <= node->center[Y] + tree->delta) { if (bbox[HI][Z] > node->center[Z] - tree->delta) overlap |= 1 << LXLYHZ; if (bbox[LO][Z] <= node->center[Z] + tree->delta) overlap |= 1 << LXLYLZ; } } #else int overlap; char hix, hiy, hiz, lox, loy, loz; overlap = 0; hix = bbox[HI][X] > node->center[X] - tree->delta; hiy = bbox[HI][Y] > node->center[Y] - tree->delta; hiz = bbox[HI][Z] > node->center[Z] - tree->delta; lox = bbox[LO][X] <= node->center[X] + tree->delta; loy = bbox[LO][Y] <= node->center[Y] + tree->delta; loz = bbox[LO][Z] <= node->center[Z] + tree->delta; if (hix) { if (hiy) { if (hiz) overlap |= 1 << HXHYHZ; if (loz) overlap |= 1 << HXHYLZ; } if (loy) { if (hiz) overlap |= 1 << HXLYHZ; if (loz) overlap |= 1 << HXLYLZ; } } if (lox) { if (hiy) { if (hiz) overlap |= 1 << LXHYHZ; if (loz) overlap |= 1 << LXHYLZ; } if (loy) { if (hiz) overlap |= 1 << LXLYHZ; if (loz) overlap |= 1 << LXLYLZ; } } #endif return overlap; } /** End of get_child_overlap() **/ /*****************************************************************************\ @ init_children() ----------------------------------------------------------------------------- description : Create 8 children for an octree node. input : Octree, octree node output : octree node now has 8 initialized, but empty, child nodes notes : \*****************************************************************************/ static void init_children(Octree *tree, OctreeNode *node) { int i; Point newsides; OctreeNode *child; VEC3_V_OP_S(newsides, node->sides, *, 0.5); ALLOCN(node->child, OctreeNode, 8); /* Set up the sides for children */ for (i = 0 ; i < 8; i++) VEC3_ASN_OP(node->child[i].sides, =, newsides); /* Set up center for children */ node->child[LXLYLZ].center[X] = node->center[X] - newsides[X]; node->child[LXLYLZ].center[Y] = node->center[Y] - newsides[Y]; node->child[LXLYLZ].center[Z] = node->center[Z] - newsides[Z]; node->child[LXLYHZ].center[X] = node->center[X] - newsides[X]; node->child[LXLYHZ].center[Y] = node->center[Y] - newsides[Y]; node->child[LXLYHZ].center[Z] = node->center[Z] + newsides[Z]; node->child[LXHYLZ].center[X] = node->center[X] - newsides[X]; node->child[LXHYLZ].center[Y] = node->center[Y] + newsides[Y]; node->child[LXHYLZ].center[Z] = node->center[Z] - newsides[Z]; node->child[LXHYHZ].center[X] = node->center[X] - newsides[X]; node->child[LXHYHZ].center[Y] = node->center[Y] + newsides[Y]; node->child[LXHYHZ].center[Z] = node->center[Z] + newsides[Z]; node->child[HXLYLZ].center[X] = node->center[X] + newsides[X]; node->child[HXLYLZ].center[Y] = node->center[Y] - newsides[Y]; node->child[HXLYLZ].center[Z] = node->center[Z] - newsides[Z]; node->child[HXLYHZ].center[X] = node->center[X] + newsides[X]; node->child[HXLYHZ].center[Y] = node->center[Y] - newsides[Y]; node->child[HXLYHZ].center[Z] = node->center[Z] + newsides[Z]; node->child[HXHYLZ].center[X] = node->center[X] + newsides[X]; node->child[HXHYLZ].center[Y] = node->center[Y] + newsides[Y]; node->child[HXHYLZ].center[Z] = node->center[Z] - newsides[Z]; node->child[HXHYHZ].center[X] = node->center[X] + newsides[X]; node->child[HXHYHZ].center[Y] = node->center[Y] + newsides[Y]; node->child[HXHYHZ].center[Z] = node->center[Z] + newsides[Z]; for (i = 0; i < 8; i++) { child = &(node->child[i]); child->parent = node; child->num_elements = 0; child->elements = NULL; child->child_elements = 0; child->child = NULL; child->max_elements = 0; } } /** End of init_children() **/ /*****************************************************************************\ @ ot_insert() ----------------------------------------------------------------------------- description : Recursively insert an octree data element into an octree node input : octree, octree node, data element output : Data element is inserted into the sub-tree rooted at the given octree node. notes : \*****************************************************************************/ static void ot_insert(Octree *tree, OctreeNode *node, OctreeData *data) { int i, j; double minside; int overlap_flags; OctreeData *element; if (node->child == NULL) { if ((node->num_elements + 1) > node->max_elements) { REALLOCN(node->elements, OctreeData *, node->max_elements, FMAX((node->num_elements + 1), (tree->max_node_objs+1))); node->max_elements = FMAX((node->num_elements+1), (tree->max_node_objs+1)); } node->elements[node->num_elements++] = data; if (node->num_elements > tree->max_node_objs) { minside = FMIN(node->sides[X], FMIN(node->sides[Y], node->sides[Z])); if ((minside / 2.0) > tree->min_side) { init_children(tree, node); for (i=0; inum_elements; i++) { element = node->elements[i]; overlap_flags = get_child_overlap(tree, node, element->bbox); for (j=0; j<8; j++) { if (overlap_flags & (1 << j)) ot_insert(tree, &(node->child[j]), element); } } node->child_elements = node->num_elements; node->num_elements = 0; FREE(node->elements); } } } else { overlap_flags = get_child_overlap(tree, node, data->bbox); for (i=0; i<8; i++) { if (overlap_flags & (1 << i)) ot_insert(tree, &(node->child[i]), data); } node->child_elements++; } } /** End of ot_insert() **/ /*****************************************************************************\ @ ot_remove() ----------------------------------------------------------------------------- description : Recursively remove a data element from an octree node input : Octree, octree node, data element output : Data element is removed from the sub-tree rooted at the given octree node notes : \*****************************************************************************/ static void ot_remove(Octree *tree, OctreeNode *node, OctreeData *data) { int i; OctreeData *element; int overlap_flags; if (node->child == NULL) { for (i=0; inum_elements; i++) { element = node->elements[i]; if (element == data) { node->elements[i] = node->elements[node->num_elements-1]; node->num_elements--; return; } } fprintf(stderr, "octree_remove: data not found\n"); return; } else { overlap_flags = get_child_overlap(tree, node, data->bbox); for (i=0; i<8; i++) { if (overlap_flags & (1 << i)) ot_remove(tree, &(node->child[i]), data); } node->child_elements--; } return; } /** End of ot_remove() **/ /*****************************************************************************\ @ range_query() ----------------------------------------------------------------------------- description : Recursively query an octree node with a query box input : octree, octree node, query box output : list of elements overlapping the query box and number of elements notes : \*****************************************************************************/ static void range_query(Octree *tree, OctreeNode *node, Extents bbox, OctreeData **element_list, int *num_elements) { int i, overlap; OctreeData *element; if (node->child != NULL) { overlap = get_child_overlap(tree, node, bbox); for (i=0; i<8; i++) { if (overlap & (1 << i)) range_query(tree, &(node->child[i]), bbox, element_list, num_elements); } } else { for (i=0; inum_elements; i++) { element = node->elements[i]; if ((element->found == FALSE) && (BBOX_OVERLAP(bbox, element->bbox) == TRUE)) { element_list[(*num_elements)++] = element; element->found = TRUE; } } } return; } /** End of range_query() **/ /*****************************************************************************\ @ point_query() ----------------------------------------------------------------------------- description : Recursively traverse sub-tree of octree node to determine which leaf node contains the given point. input : Octree, octree node, point output : Octree leaf node containing point notes : Not currently in use. \*****************************************************************************/ static OctreeNode *point_query(Octree *tree, OctreeNode *node, Point point) { int overlap_flags; Extents bbox; int i, count; if (node->child == NULL) return node; VEC3_ASN_OP(bbox[HI], =, point); VEC3_ASN_OP(bbox[LO], =, point); overlap_flags = get_child_overlap(tree, node, bbox); for (i=0, count=0; i<8; i++) if (overlap_flags & (1< 1) { fprintf(stderr, "octree_point_query: point too close to cell boundary\n"); return NULL; } for (i=0; i<8; i++) if (overlap_flags & (1<child[i]), point); fprintf(stderr, "octree_point_query: couldn't find node\n"); return NULL; } /** End of point_query() **/ /*****************************************************************************\ @ destroy_node() ----------------------------------------------------------------------------- description : Recursively deallocate an octree node input : octree node output : notes : \*****************************************************************************/ static void destroy_node(OctreeNode *node) { int i; if (node->child != NULL) { for (i=0; i<7; i++) destroy_node(&(node->child[i])); FREE(node->child); } if (node->elements != NULL) FREE(node->elements); return; } /** End of destroy_node() **/ /*****************************************************************************\ @ print_leaf_stats() ----------------------------------------------------------------------------- description : Local function to recursively gather octree statistics input : Octree, node to recurse. output : number of leaves, total elements (including replication), number of maxed-out leaves notes : \*****************************************************************************/ static void print_leaf_stats(Octree *tree, OctreeNode *node, int *leaf_count, int *element_count, int *maxout_count) { int i; if (node->child == NULL) { #if 0 fprintf(stderr, "leaf #%d: %d elements\n", *leaf_count, node->num_elements); #endif (*leaf_count)++; (*element_count) += node->num_elements; if (node->num_elements > tree->max_node_objs) (*maxout_count)++; } else { for (i=0; i<8; i++) print_leaf_stats(tree, &(node->child[i]), leaf_count, element_count, maxout_count); } return; } /** End of print_leaf_stats() **/ /*****************************************************************************\ @ octree_create() ----------------------------------------------------------------------------- description : Create an octree input : bbox - maximum extent of all objects to be stored in octree min_side - minimum cell width (full diameter, not radius) -- this should be based somehow on the size of the elements to be inserted max_node_objects - maximum number of objects to be stored in a cell (unless width becomes less than min_side) -- this should be based on the typical number of elements who are unavoidably in each others local neighborhood (e.g. number of triangles that meet a vertex) output : Octree and its root node are initialized notes : \*****************************************************************************/ void octree_create(Octree **tree, Extents bbox, double min_side, int max_node_objects) { int i; OctreeNode *root; double bbox_minside; ALLOCN(*tree, Octree, 1); ALLOCN((*tree)->root, OctreeNode, 1); root = (*tree)->root; root->parent = NULL; root->num_elements = 0; root->elements = NULL; root->child_elements = 0; root->child = NULL; for (i=0; i<3; i++) { root->center[i] = (bbox[LO][i] + bbox[HI][i]) / 2.0; root->sides[i] = (bbox[HI][i] - bbox[LO][i]) / 2.0; } bbox_minside = FMIN(root->sides[X], FMIN(root->sides[Y], root->sides[Z])); (*tree)->min_side = FMAX((min_side/2.0), (bbox_minside / MAX_RESOLUTION)); (*tree)->delta = (*tree)->min_side * 0.0001; (*tree)->max_node_objs = FMAX(max_node_objects, MIN_MAX_NODE_OBJS); } /** End of octree_create() **/ /*****************************************************************************\ @ octree_insert() ----------------------------------------------------------------------------- description : Insert a data element into an octree input : Octree and data element output : Data is inserted into octree notes : \*****************************************************************************/ void octree_insert(Octree *tree, OctreeData *data) { OctreeNode *root; root = tree->root; if ((data->bbox[HI][X] < (root->center[X] - root->sides[X])) || (data->bbox[HI][Y] < (root->center[Y] - root->sides[Y])) || (data->bbox[HI][Z] < (root->center[Z] - root->sides[Z])) || (data->bbox[LO][X] > (root->center[X] + root->sides[X])) || (data->bbox[LO][Y] > (root->center[Y] + root->sides[Y])) || (data->bbox[LO][Z] > (root->center[Z] + root->sides[Z]))) { fprintf(stderr, "octree_insert: data outside range of octree\n"); return; } data->found = FALSE; ot_insert(tree, root, data); return; } /** End of octree_insert() **/ /*****************************************************************************\ @ octree_remove() ----------------------------------------------------------------------------- description : Remove a data element from an octree input : Octree and data element output : data element is no longer in octree notes : \*****************************************************************************/ void octree_remove(Octree *tree, OctreeData *data) { OctreeNode *root; root = tree->root; if ((data->bbox[HI][X] < (root->center[X] - root->sides[X])) || (data->bbox[HI][Y] < (root->center[Y] - root->sides[Y])) || (data->bbox[HI][Z] < (root->center[Z] - root->sides[Z])) || (data->bbox[LO][X] > (root->center[X] + root->sides[X])) || (data->bbox[LO][Y] > (root->center[Y] + root->sides[Y])) || (data->bbox[LO][Z] > (root->center[Z] + root->sides[Z]))) { fprintf(stderr, "octree_remove: data outside range of octree\n"); return; } ot_remove(tree, root, data); } /** End of octree_remove() **/ /*****************************************************************************\ @ octree_destroy() ----------------------------------------------------------------------------- description : Octree space is all deallocated input : octree output : Octree space is all deallocated notes : \*****************************************************************************/ void octree_destroy(Octree **tree) { if ((*tree)->root != NULL) destroy_node((*tree)->root); FREE(*tree); return; } /** End of octree_destroy() **/ /*****************************************************************************\ @ octree_range_query() ----------------------------------------------------------------------------- description : Find all octree data elements that overlap an axis-aligned query box input : Octree, query box. output : element list contains pointers to the overlapping data elements and num_elements gives the number of overlapping elements notes : for now, don't apply any fuzz_factor to the bounding box when testing for overlaps (besides, the caller could work a fuzz_factor into the bbox before passing it in, perhaps) \*****************************************************************************/ void octree_range_query(Octree *tree, Extents bbox, OctreeData **element_list, int *num_elements) { int i; OctreeNode *root; root = tree->root; if ((bbox[HI][X] < (root->center[X] - root->sides[X])) || (bbox[HI][Y] < (root->center[Y] - root->sides[Y])) || (bbox[HI][Z] < (root->center[Z] - root->sides[Z])) || (bbox[LO][X] > (root->center[X] + root->sides[X])) || (bbox[LO][Y] > (root->center[Y] + root->sides[Y])) || (bbox[LO][Z] > (root->center[Z] + root->sides[Z]))) { fprintf(stderr, "octree_range_query: "); fprintf(stderr, "query range outside of tree range (not fatal)\n"); *num_elements = 0; return; } *num_elements = 0; range_query(tree, tree->root, bbox, element_list, num_elements); for (i=0; i < (*num_elements); i++) element_list[i]->found = FALSE; } /** End of octree_range_query() **/ /*****************************************************************************\ @ octree_point_query() ----------------------------------------------------------------------------- description : Find the octree leaf node containing a point input : Octree, point output : octree leaf node containing point notes : Not in current use -- should really try to return all data elements which contain this point \*****************************************************************************/ OctreeNode *octree_point_query(Octree *tree, Point point) { OctreeNode *root; root = tree->root; if ((point[X] < (root->center[X] - root->sides[X])) || (point[Y] < (root->center[Y] - root->sides[Y])) || (point[Z] < (root->center[Z] - root->sides[Z])) || (point[X] > (root->center[X] + root->sides[X])) || (point[Y] > (root->center[Y] + root->sides[Y])) || (point[Z] > (root->center[Z] + root->sides[Z]))) { fprintf(stderr, "octree_point_query: point outside of tree range\n"); return NULL; } return point_query(tree, tree->root, point); } /** End of octree_point_query() **/ /*****************************************************************************\ @ octree_print_stats() ----------------------------------------------------------------------------- description : Print out some overall statistics about the octree. input : Octree output : printed statistics notes : Requires a traversal of all O(nlogn) cells. \*****************************************************************************/ void octree_print_stats(Octree *tree) { int leaf_count, total_leaf_elements, maxout_count; float average_leaf_elements; fprintf(stderr, "octree statistics:\n"); leaf_count = 0; total_leaf_elements = 0; maxout_count = 0; print_leaf_stats(tree, tree->root, &leaf_count, &total_leaf_elements, &maxout_count); average_leaf_elements = (float)total_leaf_elements/(float)leaf_count; fprintf(stderr, "\tnumber of elements : %d\n", FMAX(tree->root->child_elements, tree->root->num_elements)); fprintf(stderr, "\tmax_node_objects : %d\n", tree->max_node_objs); fprintf(stderr, "\ttotal number of leaves: %d\n", leaf_count); fprintf(stderr, "\taverage elements/leaf : %f\n", average_leaf_elements); fprintf(stderr, "\tmaxed-out leaves : %d\n", maxout_count); fprintf(stderr, "\n"); return; } /** End of octree_print_stats() **/ /*****************************************************************************\ $Log: octree.c,v $ Revision 1.1.1.1 2000/04/06 15:35:32 philippe Initial CVS release Revision 1.4 1997/04/10 20:10:46 cohenj Added Amitabh's name to credits Revision 1.3 1996/04/08 18:51:26 cohenj added procedure comments and copyright * Revision 1.2 95/10/16 16:29:41 cohenj * added min_side and max_node_objects parameters to octree_create to allow * variation of these parameters between octrees (especially so the border * tubes could have octrees with a larger max_node_objects). * * Revision 1.1 95/09/15 16:28:21 cohenj * Initial revision * * Revision 1.1 1995/08/30 20:57:04 cohenj * Initial revision * * Revision 1.1 1995/08/30 20:57:04 cohenj * Initial revision * \*****************************************************************************/