bug in bvhkdop (bad diff merged, pointed out by jaguarandi)
[blender.git] / source / blender / blenlib / intern / BLI_kdopbvh.c
1 /*  kdop.c      
2
3 *
4 * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version. The Blender
10 * Foundation also sells licenses for use in proprietary software under
11 * the Blender License.  See http://www.blender.org/BL/ for information
12 * about this.
13 *
14 * This program is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with this program; if not, write to the Free Software Foundation,
21 * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22 *
23 * The Original Code is Copyright (C) Blender Foundation
24 * All rights reserved.
25 *
26 * The Original Code is: all of this file.
27 *
28 * Contributor(s): Daniel Genrich, Andre Pinto
29 *
30 * ***** END GPL/BL DUAL LICENSE BLOCK *****
31 */
32
33 #include "math.h"
34 #include <stdio.h>
35 #include <stdlib.h> 
36 #include <string.h>
37
38 #include "MEM_guardedalloc.h"
39
40 #include "BKE_utildefines.h"
41
42 #include "BLI_kdopbvh.h"
43 #include "BLI_arithb.h"
44
45 #ifdef _OPENMP
46 #include <omp.h>
47 #endif
48
49 typedef struct BVHNode
50 {
51         struct BVHNode *children[8]; // max 8 children
52         struct BVHNode *parent; // needed for bottom - top update
53         float bv[26]; // Bounding volume of all nodes, max 13 axis
54         int index; /* face, edge, vertex index */
55         char totnode; // how many nodes are used, used for speedup
56         char traversed;  // how many nodes already traversed until this level?
57         char main_axis;
58 } BVHNode;
59
60 struct BVHTree
61 {
62         BVHNode **nodes;
63         BVHNode *nodearray; /* pre-alloc branch nodes */
64         float   epsilon; /* epslion is used for inflation of the k-dop     */
65         int     totleaf; // leafs
66         int     totbranch;
67         char    tree_type; // type of tree (4 => quadtree)
68         char    axis; // kdop type (6 => OBB, 7 => AABB, ...)
69         char    start_axis, stop_axis; // KDOP_AXES array indices according to axis
70 };
71
72 typedef struct BVHOverlapData 
73 {  
74         BVHTree *tree1, *tree2; 
75         BVHTreeOverlap *overlap; 
76         int i, max_overlap; /* i is number of overlaps */
77 } BVHOverlapData;
78 ////////////////////////////////////////
79
80
81 ////////////////////////////////////////////////////////////////////////
82 // Bounding Volume Hierarchy Definition
83 // 
84 // Notes: From OBB until 26-DOP --> all bounding volumes possible, just choose type below
85 // Notes: You have to choose the type at compile time ITM
86 // Notes: You can choose the tree type --> binary, quad, octree, choose below
87 ////////////////////////////////////////////////////////////////////////
88
89 static float KDOP_AXES[13][3] =
90 { {1.0, 0, 0}, {0, 1.0, 0}, {0, 0, 1.0}, {1.0, 1.0, 1.0}, {1.0, -1.0, 1.0}, {1.0, 1.0, -1.0},
91 {1.0, -1.0, -1.0}, {1.0, 1.0, 0}, {1.0, 0, 1.0}, {0, 1.0, 1.0}, {1.0, -1.0, 0}, {1.0, 0, -1.0},
92 {0, 1.0, -1.0}
93 };
94
95 //////////////////////////////////////////////////////////////////////////////////////////////////////
96 // Introsort 
97 // with permission deriven from the following Java code:
98 // http://ralphunden.net/content/tutorials/a-guide-to-introsort/
99 // and he derived it from the SUN STL 
100 //////////////////////////////////////////////////////////////////////////////////////////////////////
101 static int size_threshold = 16;
102 /*
103 * Common methods for all algorithms
104 */
105 static int floor_lg(int a)
106 {
107         return (int)(floor(log(a)/log(2)));
108 }
109
110 /*
111 * Insertion sort algorithm
112 */
113 static void bvh_insertionsort(BVHNode **a, int lo, int hi, int axis)
114 {
115         int i,j;
116         BVHNode *t;
117         for (i=lo; i < hi; i++)
118         {
119                 j=i;
120                 t = a[i];
121                 while((j!=lo) && (t->bv[axis] < (a[j-1])->bv[axis]))
122                 {
123                         a[j] = a[j-1];
124                         j--;
125                 }
126                 a[j] = t;
127         }
128 }
129
130 static int bvh_partition(BVHNode **a, int lo, int hi, BVHNode * x, int axis)
131 {
132         int i=lo, j=hi;
133         while (1)
134         {
135                 while ((a[i])->bv[axis] < x->bv[axis]) i++;
136                 j--;
137                 while (x->bv[axis] < (a[j])->bv[axis]) j--;
138                 if(!(i < j))
139                         return i;
140                 SWAP( BVHNode* , a[i], a[j]);
141                 i++;
142         }
143 }
144
145 /*
146 * Heapsort algorithm
147 */
148 static void bvh_downheap(BVHNode **a, int i, int n, int lo, int axis)
149 {
150         BVHNode * d = a[lo+i-1];
151         int child;
152         while (i<=n/2)
153         {
154                 child = 2*i;
155                 if ((child < n) && ((a[lo+child-1])->bv[axis] < (a[lo+child])->bv[axis]))
156                 {
157                         child++;
158                 }
159                 if (!(d->bv[axis] < (a[lo+child-1])->bv[axis])) break;
160                 a[lo+i-1] = a[lo+child-1];
161                 i = child;
162         }
163         a[lo+i-1] = d;
164 }
165
166 static void bvh_heapsort(BVHNode **a, int lo, int hi, int axis)
167 {
168         int n = hi-lo, i;
169         for (i=n/2; i>=1; i=i-1)
170         {
171                 bvh_downheap(a, i,n,lo, axis);
172         }
173         for (i=n; i>1; i=i-1)
174         {
175                 SWAP(BVHNode*, a[lo],a[lo+i-1]);
176                 bvh_downheap(a, 1,i-1,lo, axis);
177         }
178 }
179
180 static BVHNode *bvh_medianof3(BVHNode **a, int lo, int mid, int hi, int axis) // returns Sortable
181 {
182         if ((a[mid])->bv[axis] < (a[lo])->bv[axis])
183         {
184                 if ((a[hi])->bv[axis] < (a[mid])->bv[axis])
185                         return a[mid];
186                 else
187                 {
188                         if ((a[hi])->bv[axis] < (a[lo])->bv[axis])
189                                 return a[hi];
190                         else
191                                 return a[lo];
192                 }
193         }
194         else
195         {
196                 if ((a[hi])->bv[axis] < (a[mid])->bv[axis])
197                 {
198                         if ((a[hi])->bv[axis] < (a[lo])->bv[axis])
199                                 return a[lo];
200                         else
201                                 return a[hi];
202                 }
203                 else
204                         return a[mid];
205         }
206 }
207 /*
208 * Quicksort algorithm modified for Introsort
209 */
210 static void bvh_introsort_loop (BVHNode **a, int lo, int hi, int depth_limit, int axis)
211 {
212         int p;
213
214         while (hi-lo > size_threshold)
215         {
216                 if (depth_limit == 0)
217                 {
218                         bvh_heapsort(a, lo, hi, axis);
219                         return;
220                 }
221                 depth_limit=depth_limit-1;
222                 p=bvh_partition(a, lo, hi, bvh_medianof3(a, lo, lo+((hi-lo)/2)+1, hi-1, axis), axis);
223                 bvh_introsort_loop(a, p, hi, depth_limit, axis);
224                 hi=p;
225         }
226 }
227
228 static void sort(BVHNode **a0, int begin, int end, int axis)
229 {
230         if (begin < end)
231         {
232                 BVHNode **a=a0;
233                 bvh_introsort_loop(a, begin, end, 2*floor_lg(end-begin), axis);
234                 bvh_insertionsort(a, begin, end, axis);
235         }
236 }
237 void sort_along_axis(BVHTree *tree, int start, int end, int axis)
238 {
239         sort(tree->nodes, start, end, axis);
240 }
241
242 //after a call to this function you can expect one of:
243 //      every node to left of a[n] are smaller than it
244 //      every node to the right of a[n-1] are greater than it
245 void partition_nth_element(BVHNode **a, int _begin, int _end, int n, int axis)
246 {
247         int begin = _begin, end = _end;
248         while(begin < n && end >= n)
249         {
250                 int mid = bvh_partition(a, begin, end, bvh_medianof3(a, begin, (begin+end-1)/2, end-1, axis), axis );
251
252                 if(mid >= n)
253                         end = n-1;
254                 else
255                         begin = n+1;
256         }
257
258 }
259
260
261 //////////////////////////////////////////////////////////////////////////////////////////////////////
262
263 void BLI_bvhtree_free(BVHTree *tree)
264 {       
265         if(tree)
266         {
267                 MEM_freeN(tree->nodes);
268                 MEM_freeN(tree->nodearray);
269                 MEM_freeN(tree);
270         }
271 }
272
273 BVHTree *BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
274 {
275         BVHTree *tree;
276         int numbranches=0, i;
277         
278         // only support up to octree
279         if(tree_type > 8)
280                 return NULL;
281
282         tree = (BVHTree *)MEM_callocN(sizeof(BVHTree), "BVHTree");
283         
284         if(tree)
285         {
286                 // calculate max number of branches, our bvh kdop is "almost perfect"
287                 for(i = 1; i <= (int)ceil((float)((float)log(maxsize)/(float)log(tree_type))); i++)
288                         numbranches += (pow(tree_type, i) / tree_type);
289                 
290                 tree->nodes = (BVHNode **)MEM_callocN(sizeof(BVHNode *)*(numbranches+maxsize + tree_type), "BVHNodes");
291                 
292                 if(!tree->nodes)
293                 {
294                         MEM_freeN(tree);
295                         return NULL;
296                 }
297                 
298                 tree->nodearray = (BVHNode *)MEM_callocN(sizeof(BVHNode)*(numbranches+maxsize + tree_type), "BVHNodeArray");
299                 
300                 if(!tree->nodearray)
301                 {
302                         MEM_freeN(tree);
303                         MEM_freeN(tree->nodes);
304                         return NULL;
305                 }
306                 
307                 tree->epsilon = epsilon;
308                 tree->tree_type = tree_type; 
309                 tree->axis = axis;
310                 
311                 if(axis == 26)
312                 {
313                         tree->start_axis = 0;
314                         tree->stop_axis = 13;
315                 }
316                 else if(axis == 18)
317                 {
318                         tree->start_axis = 7;
319                         tree->stop_axis = 13;
320                 }
321                 else if(axis == 14)
322                 {
323                         tree->start_axis = 0;
324                         tree->stop_axis = 7;
325                 }
326                 else if(axis == 8) // AABB
327                 {
328                         tree->start_axis = 0;
329                         tree->stop_axis = 4;
330                 }
331                 else if(axis == 6) // OBB
332                 {
333                         tree->start_axis = 0;
334                         tree->stop_axis = 3;
335                 }
336                 else
337                 {
338                         BLI_bvhtree_free(tree);
339                         return NULL;
340                 }
341         }
342
343         return tree;
344 }
345
346 static void create_kdop_hull(BVHTree *tree, BVHNode *node, float *co, int numpoints, int moving)
347 {
348         float newminmax;
349         int i, k;
350         
351         // don't init boudings for the moving case
352         if(!moving)
353         {
354                 for (i = tree->start_axis; i < tree->stop_axis; i++)
355                 {
356                         node->bv[2*i] = FLT_MAX;
357                         node->bv[2*i + 1] = -FLT_MAX;
358                 }
359         }
360         
361         for(k = 0; k < numpoints; k++)
362         {
363                 // for all Axes.
364                 for (i = tree->start_axis; i < tree->stop_axis; i++)
365                 {
366                         newminmax = INPR(&co[k * 3], KDOP_AXES[i]);
367                         if (newminmax < node->bv[2 * i])
368                                 node->bv[2 * i] = newminmax;
369                         if (newminmax > node->bv[(2 * i) + 1])
370                                 node->bv[(2 * i) + 1] = newminmax;
371                 }
372         }
373 }
374
375 // depends on the fact that the BVH's for each face is already build
376 static void refit_kdop_hull(BVHTree *tree, BVHNode *node, int start, int end)
377 {
378         float newmin,newmax;
379         int i, j;
380         float *bv = node->bv;
381         
382         for (i = tree->start_axis; i < tree->stop_axis; i++)
383         {
384                 bv[2*i] = FLT_MAX;
385                 bv[2*i + 1] = -FLT_MAX;
386         }
387
388         for (j = start; j < end; j++)
389         {
390                 // for all Axes.
391                 for (i = tree->start_axis; i < tree->stop_axis; i++)
392                 {
393                         newmin = tree->nodes[j]->bv[(2 * i)];   
394                         if ((newmin < bv[(2 * i)]))
395                                 bv[(2 * i)] = newmin;
396  
397                         newmax = tree->nodes[j]->bv[(2 * i) + 1];
398                         if ((newmax > bv[(2 * i) + 1]))
399                                 bv[(2 * i) + 1] = newmax;
400                 }
401         }
402 }
403
404 int BLI_bvhtree_insert(BVHTree *tree, int index, float *co, int numpoints)
405 {
406         BVHNode *node= NULL;
407         int i;
408         
409         // insert should only possible as long as tree->totbranch is 0
410         if(tree->totbranch > 0)
411                 return 0;
412         
413         if(tree->totleaf+1 >= MEM_allocN_len(tree->nodes))
414                 return 0;
415         
416         // TODO check if have enough nodes in array
417         
418         node = tree->nodes[tree->totleaf] = &(tree->nodearray[tree->totleaf]);
419         tree->totleaf++;
420         
421         create_kdop_hull(tree, node, co, numpoints, 0);
422         
423         // inflate the bv with some epsilon
424         for (i = tree->start_axis; i < tree->stop_axis; i++)
425         {
426                 node->bv[(2 * i)] -= tree->epsilon; // minimum 
427                 node->bv[(2 * i) + 1] += tree->epsilon; // maximum 
428         }
429
430         node->index= index;
431         
432         return 1;
433 }
434
435 // only supports x,y,z axis in the moment
436 // but we should use a plain and simple function here for speed sake
437 static char get_largest_axis(float *bv)
438 {
439         float middle_point[3];
440
441         middle_point[0] = (bv[1]) - (bv[0]); // x axis
442         middle_point[1] = (bv[3]) - (bv[2]); // y axis
443         middle_point[2] = (bv[5]) - (bv[4]); // z axis
444         if (middle_point[0] > middle_point[1]) 
445         {
446                 if (middle_point[0] > middle_point[2])
447                         return 1; // max x axis
448                 else
449                         return 5; // max z axis
450         }
451         else 
452         {
453                 if (middle_point[1] > middle_point[2])
454                         return 3; // max y axis
455                 else
456                         return 5; // max z axis
457         }
458 }
459
460 static void bvh_div_nodes(BVHTree *tree, BVHNode *node, int start, int end, char lastaxis)
461 {
462         char laxis;
463         int i, tend;
464         BVHNode *tnode;
465         int slice = (end-start+tree->tree_type-1)/tree->tree_type;      //division rounded up
466         
467         // Determine which axis to split along
468         laxis = get_largest_axis(node->bv);
469         
470         // split nodes along longest axis
471         for (i=0; start < end; start += slice, i++) //i counts the current child
472         {       
473                 tend = start + slice;
474                 
475                 partition_nth_element(tree->nodes, start, end, tend, laxis);
476                 
477                 if(tend > end) tend = end;
478                 
479                 if(tend-start == 1)     // ok, we have 1 left for this node
480                 {
481                         node->children[i] = tree->nodes[start];
482                         node->children[i]->parent = node;
483                 }
484                 else
485                 {
486                         tnode = node->children[i] = tree->nodes[tree->totleaf  + tree->totbranch] = &(tree->nodearray[tree->totbranch + tree->totleaf]);
487                         tree->totbranch++;
488                         tnode->parent = node;
489
490                         partition_nth_element(tree->nodes, start, end, tend, laxis);
491                         refit_kdop_hull(tree, tnode, start, tend);
492                         bvh_div_nodes(tree, tnode, start, tend, laxis);
493                 }
494                 node->totnode++;
495         }
496         
497         return;
498 }
499
500 static void verify_tree(BVHTree *tree)
501 {
502         int i, j, check = 0;
503         
504         // check the pointer list
505         for(i = 0; i < tree->totleaf; i++)
506         {
507                 if(tree->nodes[i]->parent == NULL)
508                         printf("Leaf has no parent: %d\n", i);
509                 else
510                 {
511                         for(j = 0; j < tree->tree_type; j++)
512                         {
513                                 if(tree->nodes[i]->parent->children[j] == tree->nodes[i])
514                                         check = 1;
515                         }
516                         if(!check)
517                         {
518                                 printf("Parent child relationship doesn't match: %d\n", i);
519                         }
520                         check = 0;
521                 }
522         }
523         
524         // check the leaf list
525         for(i = 0; i < tree->totleaf; i++)
526         {
527                 if(tree->nodearray[i].parent == NULL)
528                         printf("Leaf has no parent: %d\n", i);
529                 else
530                 {
531                         for(j = 0; j < tree->tree_type; j++)
532                         {
533                                 if(tree->nodearray[i].parent->children[j] == &tree->nodearray[i])
534                                         check = 1;
535                         }
536                         if(!check)
537                         {
538                                 printf("Parent child relationship doesn't match: %d\n", i);
539                         }
540                         check = 0;
541                 }
542         }
543         
544         printf("branches: %d, leafs: %d, total: %d\n", tree->totbranch, tree->totleaf, tree->totbranch + tree->totleaf);
545 }
546         
547 void BLI_bvhtree_balance(BVHTree *tree)
548 {
549         BVHNode *node;
550         
551         if(tree->totleaf == 0)
552                 return;
553         
554         // create root node
555         node = tree->nodes[tree->totleaf] = &(tree->nodearray[tree->totleaf]);
556         tree->totbranch++;
557         
558         // refit root bvh node
559         refit_kdop_hull(tree, tree->nodes[tree->totleaf], 0, tree->totleaf);
560         // create + balance tree
561         bvh_div_nodes(tree, tree->nodes[tree->totleaf], 0, tree->totleaf, 0);
562         
563         // verify_tree(tree);
564 }
565
566 // overlap - is it possbile for 2 bv's to collide ?
567 static int tree_overlap(float *bv1, float *bv2, int start_axis, int stop_axis)
568 {
569         float *bv1_end = bv1 + (stop_axis<<1);
570                 
571         bv1 += start_axis<<1;
572         bv2 += start_axis<<1;
573         
574         // test all axis if min + max overlap
575         for (; bv1 != bv1_end; bv1+=2, bv2+=2)
576         {
577                 if ((*(bv1) > *(bv2 + 1)) || (*(bv2) > *(bv1 + 1))) 
578                         return 0;
579         }
580         
581         return 1;
582 }
583
584 static void traverse(BVHOverlapData *data, BVHNode *node1, BVHNode *node2)
585 {
586         int j;
587         
588         if(tree_overlap(node1->bv, node2->bv, MIN2(data->tree1->start_axis, data->tree2->start_axis), MIN2(data->tree1->stop_axis, data->tree2->stop_axis)))
589         {
590                 // check if node1 is a leaf
591                 if(node1->index)
592                 {
593                         // check if node2 is a leaf
594                         if(node2->index)
595                         {
596                                 
597                                 if(node1 == node2)
598                                 {
599                                         return;
600                                 }
601                                         
602                                 if(data->i >= data->max_overlap)
603                                 {       
604                                         // try to make alloc'ed memory bigger
605                                         data->overlap = realloc(data->overlap, sizeof(BVHTreeOverlap)*data->max_overlap*2);
606                                         
607                                         if(!data->overlap)
608                                         {
609                                                 printf("Out of Memory in traverse\n");
610                                                 return;
611                                         }
612                                         data->max_overlap *= 2;
613                                 }
614                                 
615                                 // both leafs, insert overlap!
616                                 data->overlap[data->i].indexA = node1->index;
617                                 data->overlap[data->i].indexB = node2->index;
618
619                                 data->i++;
620                         }
621                         else
622                         {
623                                 for(j = 0; j < data->tree2->tree_type; j++)
624                                 {
625                                         if(node2->children[j])
626                                                 traverse(data, node1, node2->children[j]);
627                                 }
628                         }
629                 }
630                 else
631                 {
632                         
633                         for(j = 0; j < data->tree2->tree_type; j++)
634                         {
635                                 if(node1->children[j])
636                                         traverse(data, node1->children[j], node2);
637                         }
638                 }
639         }
640         return;
641 }
642
643 BVHTreeOverlap *BLI_bvhtree_overlap(BVHTree *tree1, BVHTree *tree2, int *result)
644 {
645         int j, total = 0;
646         BVHTreeOverlap *overlap = NULL, *to = NULL;
647         BVHOverlapData *data[tree1->tree_type];
648         
649         // check for compatibility of both trees (can't compare 14-DOP with 18-DOP)
650         if((tree1->axis != tree2->axis) && ((tree1->axis == 14) || tree2->axis == 14))
651                 return 0;
652         
653         // fast check root nodes for collision before doing big splitting + traversal
654         if(!tree_overlap(tree1->nodes[tree1->totleaf]->bv, tree2->nodes[tree2->totleaf]->bv, MIN2(tree1->start_axis, tree2->start_axis), MIN2(tree1->stop_axis, tree2->stop_axis)))
655                 return 0;
656         
657         for(j = 0; j < tree1->tree_type; j++)
658         {
659                 data[j] = (BVHOverlapData *)MEM_callocN(sizeof(BVHOverlapData), "BVHOverlapData");
660                 
661                 // init BVHOverlapData
662                 data[j]->overlap = (BVHTreeOverlap *)malloc(sizeof(BVHTreeOverlap)*MAX2(tree1->totleaf, tree2->totleaf));
663                 data[j]->tree1 = tree1;
664                 data[j]->tree2 = tree2;
665                 data[j]->max_overlap = MAX2(tree1->totleaf, tree2->totleaf);
666                 data[j]->i = 0;
667         }
668
669 #pragma omp parallel for private(j) schedule(static)
670         for(j = 0; j < tree1->tree_type; j++)
671         {
672                 traverse(data[j], tree1->nodes[tree1->totleaf]->children[j], tree2->nodes[tree2->totleaf]);
673         }
674         
675         for(j = 0; j < tree1->tree_type; j++)
676                 total += data[j]->i;
677         
678         to = overlap = (BVHTreeOverlap *)MEM_callocN(sizeof(BVHTreeOverlap)*total, "BVHTreeOverlap");
679         
680         for(j = 0; j < tree1->tree_type; j++)
681         {
682                 memcpy(to, data[j]->overlap, data[j]->i*sizeof(BVHTreeOverlap));
683                 to+=data[j]->i;
684         }
685         
686         for(j = 0; j < tree1->tree_type; j++)
687         {
688                 free(data[j]->overlap);
689                 MEM_freeN(data[j]);
690         }
691         
692         (*result) = total;
693         return overlap;
694 }
695
696
697 // bottom up update of bvh tree:
698 // join the 4 children here
699 static void node_join(BVHTree *tree, BVHNode *node)
700 {
701         int i, j;
702         
703         for (i = tree->start_axis; i < tree->stop_axis; i++)
704         {
705                 node->bv[2*i] = FLT_MAX;
706                 node->bv[2*i + 1] = -FLT_MAX;
707         }
708         
709         for (i = 0; i < tree->tree_type; i++)
710         {
711                 if (node->children[i]) 
712                 {
713                         for (j = tree->start_axis; j < tree->stop_axis; j++)
714                         {
715                                 // update minimum 
716                                 if (node->children[i]->bv[(2 * j)] < node->bv[(2 * j)]) 
717                                         node->bv[(2 * j)] = node->children[i]->bv[(2 * j)];
718                                 
719                                 // update maximum 
720                                 if (node->children[i]->bv[(2 * j) + 1] > node->bv[(2 * j) + 1])
721                                         node->bv[(2 * j) + 1] = node->children[i]->bv[(2 * j) + 1];
722                         }
723                 }
724                 else
725                         break;
726         }
727 }
728
729 // call before BLI_bvhtree_update_tree()
730 int BLI_bvhtree_update_node(BVHTree *tree, int index, float *co, float *co_moving, int numpoints)
731 {
732         BVHNode *node= NULL;
733         int i = 0;
734         
735         // check if index exists
736         if(index > tree->totleaf)
737                 return 0;
738         
739         node = tree->nodearray + index;
740         
741         create_kdop_hull(tree, node, co, numpoints, 0);
742         
743         if(co_moving)
744                 create_kdop_hull(tree, node, co_moving, numpoints, 1);
745         
746         // inflate the bv with some epsilon
747         for (i = tree->start_axis; i < tree->stop_axis; i++)
748         {
749                 node->bv[(2 * i)] -= tree->epsilon; // minimum 
750                 node->bv[(2 * i) + 1] += tree->epsilon; // maximum 
751         }
752         
753         return 1;
754 }
755
756 // call BLI_bvhtree_update_node() first for every node/point/triangle
757 void BLI_bvhtree_update_tree(BVHTree *tree)
758 {
759         BVHNode *leaf, *parent;
760         
761         // reset tree traversing flag
762         for (leaf = tree->nodearray + tree->totleaf; leaf != tree->nodearray + tree->totleaf + tree->totbranch; leaf++)
763                 leaf->traversed = 0;
764         
765         for (leaf = tree->nodearray; leaf != tree->nodearray + tree->totleaf; leaf++)
766         {
767                 for (parent = leaf->parent; parent; parent = parent->parent)
768                 {
769                         parent->traversed++;    // we tried to go up in hierarchy 
770                         if (parent->traversed < parent->totnode) 
771                                 break;  // we do not need to check further 
772                         else 
773                                 node_join(tree, parent);
774                 }
775         }
776 }
777
778 float BLI_bvhtree_getepsilon(BVHTree *tree)
779 {
780         return tree->epsilon;
781 }