diff options
author | Andre Susano Pinto <andresusanopinto@gmail.com> | 2008-08-05 00:30:57 +0400 |
---|---|---|
committer | Andre Susano Pinto <andresusanopinto@gmail.com> | 2008-08-05 00:30:57 +0400 |
commit | 0008b1d424647f7f174fa94c6309a7a4a00fb486 (patch) | |
tree | 9ccad4a7b3d3b2ed76ac70e25d48b0be15b8a78e | |
parent | a0f39107fdf9de8b0a21702d64301a06fab20713 (diff) |
Shrink BVHNode by 16bits
-rw-r--r-- | source/blender/blenlib/intern/BLI_kdopbvh.c | 38 |
1 files changed, 11 insertions, 27 deletions
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c index a65d2ca6ea0..96eb42136fb 100644 --- a/source/blender/blenlib/intern/BLI_kdopbvh.c +++ b/source/blender/blenlib/intern/BLI_kdopbvh.c @@ -45,12 +45,10 @@ typedef struct BVHNode { - struct BVHNode **children; // max 8 children - struct BVHNode *parent; // needed for bottom - top update - float *bv; // Bounding volume of all nodes, max 13 axis - int index; /* face, edge, vertex index */ - char totnode; // how many nodes are used, used for speedup - char traversed; // how many nodes already traversed until this level? + struct BVHNode **children; // max 8 children + float *bv; // Bounding volume of all nodes, max 13 axis + int index; // face, edge, vertex index + char totnode; // how many nodes are used, used for speedup char main_axis; } BVHNode; @@ -554,13 +552,10 @@ static void bvh_div_nodes(BVHTree *tree, BVHNode *node, int start, int end, int if(tend-start == 1) // ok, we have 1 left for this node { node->children[i] = tree->nodes[start]; - node->children[i]->parent = node; } else { BVHNode *tnode = node->children[i] = tree->nodes[free_node_index] = &(tree->nodearray[free_node_index]); -// printf("Used %d (%d)\n", free_node_index, tend-start); - tnode->parent = node; if(tend != end) partition_nth_element(tree->nodes, start, end, tend, laxis); @@ -608,7 +603,6 @@ static void omp_bvh_div_nodes(BVHTree *tree, BVHNode *node, int start, int end, if(tend-start == 1) { node->children[i] = tree->nodes[start]; - node->children[i]->parent = node; } else { @@ -905,23 +899,13 @@ int BLI_bvhtree_update_node(BVHTree *tree, int index, float *co, float *co_movin // call BLI_bvhtree_update_node() first for every node/point/triangle void BLI_bvhtree_update_tree(BVHTree *tree) { - BVHNode *leaf, *parent; - - // reset tree traversing flag - for (leaf = tree->nodearray + tree->totleaf; leaf != tree->nodearray + tree->totleaf + tree->totbranch; leaf++) - leaf->traversed = 0; - - for (leaf = tree->nodearray; leaf != tree->nodearray + tree->totleaf; leaf++) - { - for (parent = leaf->parent; parent; parent = parent->parent) - { - parent->traversed++; // we tried to go up in hierarchy - if (parent->traversed < parent->totnode) - break; // we do not need to check further - else - node_join(tree, parent); - } - } + BVHNode** root = tree->nodes + tree->totleaf; + BVHNode** index = tree->nodes + tree->totleaf + tree->totbranch-1; + + //Update bottom=>top + //TRICKY: the way we build the tree the parent of a child has an index < then the child index + for (; index != root; index--) + node_join(tree, *index); } float BLI_bvhtree_getepsilon(BVHTree *tree) |