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