Initial commit of cloth modifier from branch rev 13453
[blender.git] / source / blender / blenkernel / intern / kdop.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): none yet.
29 *
30 * ***** END GPL/BL DUAL LICENSE BLOCK *****
31 */
32
33 #include <math.h>
34 #include <stdlib.h>
35 #include <string.h>
36 #include "MEM_guardedalloc.h"
37 /* types */
38 #include "DNA_curve_types.h"
39 #include "DNA_object_types.h"
40 #include "DNA_object_force.h"
41 #include "DNA_cloth_types.h"    
42 #include "DNA_key_types.h"
43 #include "DNA_mesh_types.h"
44 #include "DNA_meshdata_types.h"
45 #include "DNA_lattice_types.h"
46 #include "DNA_scene_types.h"
47 #include "DNA_modifier_types.h"
48 #include "BLI_blenlib.h"
49 #include "BLI_arithb.h"
50 #include "BLI_edgehash.h"
51 #include "BLI_linklist.h"
52 #include "BKE_curve.h"
53 #include "BKE_deform.h"
54 #include "BKE_DerivedMesh.h"
55 #include "BKE_cdderivedmesh.h"
56 #include "BKE_displist.h"
57 #include "BKE_effect.h"
58 #include "BKE_global.h"
59 #include "BKE_key.h"
60 #include "BKE_mesh.h"
61 #include "BKE_object.h"
62 #include "BKE_cloth.h"
63 #include "BKE_modifier.h"
64 #include "BKE_utildefines.h"
65 #include "BKE_DerivedMesh.h"
66 #include "BIF_editdeform.h"
67 #include "BIF_editkey.h"
68 #include "DNA_screen_types.h"
69 #include "BSE_headerbuttons.h"
70 #include "BIF_screen.h"
71 #include "BIF_space.h"
72 #include "mydevice.h"
73
74
75 ////////////////////////////////////////////////////////////////////////
76 // Additional fastened appending function
77 // It uses the link to the last inserted node as start value 
78 // for searching the end of the list
79 // NEW: in compare to the original function, this one returns
80 // the reference to the last inserted node 
81 ////////////////////////////////////////////////////////////////////////
82 LinkNode *BLI_linklist_append_fast(LinkNode **listp, void *ptr) {
83         LinkNode *nlink= MEM_mallocN(sizeof(*nlink), "nlink");
84         LinkNode *node = *listp;
85
86         nlink->link = ptr;
87         nlink->next = NULL;
88
89         if(node == NULL){
90                 *listp = nlink;
91         } else {
92                 while(node->next != NULL){
93                         node = node->next;   
94                 }
95                 node->next = nlink;
96         }
97         return nlink;
98 }
99
100
101
102 ////////////////////////////////////////////////////////////////////////
103 // Bounding Volume Hierarchy Definition
104 // 
105 // Notes: From OBB until 26-DOP --> all bounding volumes possible, just choose type below
106 // Notes: You have to choose the type at compile time ITM
107 // Notes: You can choose the tree type --> binary, quad, octree, choose below
108 ////////////////////////////////////////////////////////////////////////
109
110 static float KDOP_AXES[13][3] =
111 { {1, 0, 0}, {0, 1, 0}, {0, 0, 1}, {1, 1, 1}, {1, -1, 1}, {1, 1, -1},
112 {1, -1, -1}, {1, 1, 0}, {1, 0, 1}, {0, 1, 1}, {1, -1, 0}, {1, 0, -1},
113 {0, 1, -1}
114 };
115
116 ///////////// choose bounding volume here! /////////////
117
118 // #define KDOP_26
119
120 // #define KDOP_14
121
122 // AABB:
123 // #define KDOP_8
124
125 // OBB: 
126 #define KDOP_6
127
128
129
130 #ifdef KDOP_26
131 #define KDOP_END 13
132 #define KDOP_START 0
133 #endif
134
135 // I didn't test this one!
136 #ifdef KDOP_18
137 #define KDOP_END 7
138 #define KDOP_START 13
139 #endif
140
141 #ifdef KDOP_14
142 #define KDOP_END 7
143 #define KDOP_START 0
144 #endif
145
146 // this is basicly some AABB
147 #ifdef KDOP_8
148 #define KDOP_END 4
149 #define KDOP_START 0
150 #endif
151
152 // this is basicly some OBB
153 #ifdef KDOP_6
154 #define KDOP_END 3
155 #define KDOP_START 0
156 #endif
157
158 //////////////////////////////////////////////////////////////////////////////////////////////////////
159 // Introsort 
160 // with permission deriven from the following Java code:
161 // http://ralphunden.net/content/tutorials/a-guide-to-introsort/
162 // and he derived it from the SUN STL 
163 //////////////////////////////////////////////////////////////////////////////////////////////////////
164 static int size_threshold = 16;
165 /*
166 * Common methods for all algorithms
167 */
168 DO_INLINE void bvh_exchange(CollisionTree **a, int i, int j)
169 {
170         CollisionTree *t=a[i];
171         a[i]=a[j];
172         a[j]=t;
173 }
174 DO_INLINE int floor_lg(int a)
175 {
176         return (int)(floor(log(a)/log(2)));
177 }
178
179 /*
180 * Insertion sort algorithm
181 */
182 static void bvh_insertionsort(CollisionTree **a, int lo, int hi, int axis)
183 {
184         int i,j;
185         CollisionTree *t;
186         for (i=lo; i < hi; i++)
187         {
188                 j=i;
189                 t = a[i];
190                 while((j!=lo) && (t->bv[axis] < (a[j-1])->bv[axis]))
191                 {
192                         a[j] = a[j-1];
193                         j--;
194                 }                               
195                 a[j] = t;
196         }
197 }
198
199 static int bvh_partition(CollisionTree **a, int lo, int hi, CollisionTree * x, int axis)
200 {
201         int i=lo, j=hi;
202         while (1)
203         {
204                 while ((a[i])->bv[axis] < x->bv[axis]) i++;
205                 j=j-1;
206                 while (x->bv[axis] < (a[j])->bv[axis]) j=j-1;
207                 if(!(i < j))
208                         return i;
209                 bvh_exchange(a, i,j);
210                 i++;
211         }
212 }
213
214 /*
215 * Heapsort algorithm
216 */
217 static void bvh_downheap(CollisionTree **a, int i, int n, int lo, int axis)
218 {
219         CollisionTree * d = a[lo+i-1];
220         int child;
221         while (i<=n/2)
222         {
223                 child = 2*i;
224                 if ((child < n) && ((a[lo+child-1])->bv[axis] < (a[lo+child])->bv[axis]))
225                 {
226                         child++;
227                 }
228                 if (!(d->bv[axis] < (a[lo+child-1])->bv[axis])) break;
229                 a[lo+i-1] = a[lo+child-1];
230                 i = child;
231         }
232         a[lo+i-1] = d;
233 }
234
235 static void bvh_heapsort(CollisionTree **a, int lo, int hi, int axis)
236 {
237         int n = hi-lo, i;
238         for (i=n/2; i>=1; i=i-1)
239         {
240                 bvh_downheap(a, i,n,lo, axis);
241         }
242         for (i=n; i>1; i=i-1)
243         {
244                 bvh_exchange(a, lo,lo+i-1);
245                 bvh_downheap(a, 1,i-1,lo, axis);
246         }
247 }
248
249 static CollisionTree *bvh_medianof3(CollisionTree **a, int lo, int mid, int hi, int axis) // returns Sortable
250 {
251         if ((a[mid])->bv[axis] < (a[lo])->bv[axis])
252         {
253                 if ((a[hi])->bv[axis] < (a[mid])->bv[axis])
254                         return a[mid];
255                 else
256                 {
257                         if ((a[hi])->bv[axis] < (a[lo])->bv[axis])
258                                 return a[hi];
259                         else
260                                 return a[lo];
261                 }
262         }
263         else
264         {
265                 if ((a[hi])->bv[axis] < (a[mid])->bv[axis])
266                 {
267                         if ((a[hi])->bv[axis] < (a[lo])->bv[axis])
268                                 return a[lo];
269                         else
270                                 return a[hi];
271                 }
272                 else
273                         return a[mid];
274         }
275 }
276 /*
277 * Quicksort algorithm modified for Introsort
278 */
279 static void bvh_introsort_loop (CollisionTree **a, int lo, int hi, int depth_limit, int axis)
280 {
281         int p;
282
283         while (hi-lo > size_threshold)
284         {
285                 if (depth_limit == 0)
286                 {
287                         bvh_heapsort(a, lo, hi, axis);
288                         return;
289                 }
290                 depth_limit=depth_limit-1;
291                 p=bvh_partition(a, lo, hi, bvh_medianof3(a, lo, lo+((hi-lo)/2)+1, hi-1, axis), axis);
292                 bvh_introsort_loop(a, p, hi, depth_limit, axis);
293                 hi=p;
294         }
295 }
296
297 DO_INLINE void bvh_sort(CollisionTree **a0, int begin, int end, int axis)
298 {
299         if (begin < end)
300         {
301                 CollisionTree **a=a0;
302                 bvh_introsort_loop(a, begin, end, 2*floor_lg(end-begin), axis);
303                 bvh_insertionsort(a, begin, end, axis);
304         }
305 }
306 DO_INLINE void bvh_sort_along_axis(CollisionTree **face_list, int start, int end, int axis)
307 {
308         bvh_sort(face_list, start, end, axis);
309 }
310 ////////////////////////////////////////////////////////////////////////////////////////////////
311 void bvh_free(BVH * bvh)
312 {
313         LinkNode *search = NULL;
314         CollisionTree *tree = NULL;
315
316         if (bvh) 
317         {
318
319                 search = bvh->tree;
320
321                 while(search)
322                 {
323                         LinkNode *next= search->next;
324                         tree = search->link;
325
326                         MEM_freeN(tree);
327
328                         search = next;
329                 }
330
331                 BLI_linklist_free(bvh->tree,NULL); 
332                 bvh->tree = NULL;
333                 
334                 if(bvh->current_x)
335                         MEM_freeN(bvh->current_x);
336                 if(bvh->current_xold)
337                         MEM_freeN(bvh->current_xold);
338
339                 MEM_freeN(bvh);
340                 bvh = NULL;
341         }
342 }
343
344 // only supports x,y,z axis in the moment
345 // but we should use a plain and simple function here for speed sake
346 DO_INLINE int bvh_largest_axis(float *bv)
347 {
348         float middle_point[3];
349
350         middle_point[0] = (bv[1]) - (bv[0]); // x axis
351         middle_point[1] = (bv[3]) - (bv[2]); // y axis
352         middle_point[2] = (bv[5]) - (bv[4]); // z axis
353         if (middle_point[0] > middle_point[1]) 
354         {
355                 if (middle_point[0] > middle_point[2])
356                         return 1; // max x axis
357                 else
358                         return 5; // max z axis
359         }
360         else 
361         {
362                 if (middle_point[1] > middle_point[2])
363                         return 3; // max y axis
364                 else
365                         return 5; // max z axis
366         }
367 }
368
369 // depends on the fact that the BVH's for each face is already build
370 DO_INLINE void bvh_calc_DOP_hull_from_faces(BVH * bvh, CollisionTree **tri, int numfaces, float *bv)
371 {
372         float newmin,newmax;
373         int i, j;
374         for (j = 0; j < numfaces; j++)
375         {
376                 // for all Axes.
377                 for (i = KDOP_START; i < KDOP_END; i++)
378                 {
379                         newmin = (tri [j])->bv[(2 * i)];        
380                         if ((newmin < bv[(2 * i)]) || (j == 0))
381                         {
382                                 bv[(2 * i)] = newmin;
383                         }
384
385                         newmax = (tri [j])->bv[(2 * i) + 1];
386                         if ((newmax > bv[(2 * i) + 1]) || (j == 0))
387                         {
388                                 bv[(2 * i) + 1] = newmax;
389                         }
390                 }
391         }
392 }
393
394 DO_INLINE void bvh_calc_DOP_hull_static(BVH * bvh, CollisionTree **tri, int numfaces, float *bv)
395 {
396         MFace *tempMFace = bvh->mfaces;
397         float *tempBV = bv;
398         float newminmax;
399         int i, j, k;
400         for (j = 0; j < numfaces; j++)
401         {
402                 tempMFace = bvh->mfaces + (tri [j])->tri_index;
403                 // 3 or 4 vertices per face.
404                 for (k = 0; k < 4; k++)
405                 {
406                         int temp = 0;  
407                         // If this is a triangle.
408                         if (k == 3 && !tempMFace->v4)
409                                 continue;
410                         // TODO: other name for "temp" this gets all vertices of a face
411                         if (k == 0)
412                                 temp = tempMFace->v1;
413                         else if (k == 1)
414                                 temp = tempMFace->v2;
415                         else if (k == 2)
416                                 temp = tempMFace->v3;
417                         else if (k == 3)
418                                 temp = tempMFace->v4;
419                         // for all Axes.
420                         for (i = KDOP_START; i < KDOP_END; i++)
421                         {                               
422                                 newminmax = INPR(bvh->current_xold[temp].co, KDOP_AXES[i]);
423                                 if ((newminmax < tempBV[(2 * i)]) || (k == 0 && j == 0))
424                                         tempBV[(2 * i)] = newminmax;
425                                 if ((newminmax > tempBV[(2 * i) + 1])|| (k == 0 && j == 0))
426                                         tempBV[(2 * i) + 1] = newminmax;
427                         }
428                 }
429         }
430 }
431
432 DO_INLINE void bvh_calc_DOP_hull_moving(BVH * bvh, CollisionTree **tri, int numfaces, float *bv)
433 {
434         MFace *tempMFace = bvh->mfaces;
435         float *tempBV = bv;
436         float newminmax;
437         int i, j, k;
438         for (j = 0; j < numfaces; j++)
439         {
440                 tempMFace = bvh->mfaces + (tri [j])->tri_index;
441                 // 3 or 4 vertices per face.
442                 for (k = 0; k < 4; k++)
443                 {
444                         int temp = 0;  
445                         // If this is a triangle.
446                         if (k == 3 && !tempMFace->v4)
447                                 continue;
448                         // TODO: other name for "temp" this gets all vertices of a face
449                         if (k == 0)
450                                 temp = tempMFace->v1;
451                         else if (k == 1)
452                                 temp = tempMFace->v2;
453                         else if (k == 2)
454                                 temp = tempMFace->v3;
455                         else if (k == 3)
456                                 temp = tempMFace->v4;
457                         // for all Axes.
458                         for (i = KDOP_START; i < KDOP_END; i++)
459                         {                               
460                                 newminmax = INPR(bvh->current_xold[temp].co, KDOP_AXES[i]);
461                                 if ((newminmax < tempBV[(2 * i)]) || (k == 0 && j == 0))
462                                         tempBV[(2 * i)] = newminmax;
463                                 if ((newminmax > tempBV[(2 * i) + 1])|| (k == 0 && j == 0))
464                                         tempBV[(2 * i) + 1] = newminmax;
465                                 
466                                 newminmax = INPR(bvh->current_x[temp].co, KDOP_AXES[i]);
467                                 if ((newminmax < tempBV[(2 * i)]) || (k == 0 && j == 0))
468                                         tempBV[(2 * i)] = newminmax;
469                                 if ((newminmax > tempBV[(2 * i) + 1])|| (k == 0 && j == 0))
470                                         tempBV[(2 * i) + 1] = newminmax;
471                         }
472                 }
473         }
474 }
475
476 static void bvh_div_env_node(BVH *bvh, CollisionTree *tree, CollisionTree **face_list, unsigned int start, unsigned int end, int lastaxis, LinkNode *nlink)
477 {
478         int             i = 0;
479         CollisionTree *newtree = NULL;
480         int laxis = 0, max_nodes=4;
481         unsigned int tstart, tend;
482         LinkNode *nlink1 = nlink;
483         LinkNode *tnlink;
484         tree->traversed = 0;    
485         // Determine which axis to split along
486         laxis = bvh_largest_axis(tree->bv);
487
488         // Sort along longest axis
489         if(laxis!=lastaxis)
490                 bvh_sort_along_axis(face_list, start, end, laxis);
491
492         max_nodes = MIN2((end-start + 1 ),4);
493
494         for (i = 0; i < max_nodes; i++)
495         {
496                 tree->count_nodes++;
497
498                 if(end-start > 4)
499                 {
500                         int quarter = ((float)((float)(end - start + 1) / 4.0f));
501                         tstart = start + i * quarter;
502                         tend = tstart + quarter - 1;
503
504                         // be sure that we get all faces
505                         if(i==3)
506                         {
507                                 tend = end;
508                         }
509                 }
510                 else
511                 {
512                         tend = tstart = start + i;
513                 }
514
515                 // Build tree until 4 node left.
516                 if ((tend-tstart + 1 ) > 1) 
517                 {
518                         newtree = (CollisionTree *)MEM_callocN(sizeof(CollisionTree), "CollisionTree");
519                         tnlink = BLI_linklist_append_fast(&nlink1->next, newtree);
520
521                         newtree->nodes[0] = newtree->nodes[1] = newtree->nodes[2] = newtree->nodes[3] = NULL;
522                         newtree->count_nodes = 0;
523                         newtree->parent = tree;
524                         newtree->isleaf = 0;
525
526                         tree->nodes[i] = newtree;
527
528                         nlink1 = tnlink;
529
530                         bvh_calc_DOP_hull_from_faces(bvh, &face_list[tstart], tend-tstart + 1, tree->nodes[i]->bv);
531
532                         bvh_div_env_node(bvh, tree->nodes[i], face_list, tstart, tend, laxis, nlink1);
533                 }
534                 else // ok, we have 1 left for this node
535                 {
536                         CollisionTree *tnode = face_list[tstart];
537                         tree->nodes[i] = tnode;
538                         tree->nodes[i]->parent = tree;
539                 }
540         }
541         return;
542 }
543
544 /* function cannot be directly called - needs alloced bvh */
545 void bvh_build (BVH *bvh)
546 {
547         unsigned int i = 0, j = 0, k = 0;
548         CollisionTree **face_list=NULL;
549         CollisionTree *tree=NULL;
550         LinkNode *nlink = NULL;
551         
552         tree = (CollisionTree *)MEM_callocN(sizeof(CollisionTree), "CollisionTree");
553         // TODO: check succesfull alloc
554         BLI_linklist_append(&bvh->tree, tree);
555
556         nlink = bvh->tree;
557
558         if (tree == NULL) 
559         {
560                 printf("bvh_build: Out of memory for nodes.\n");
561                 bvh_free(bvh);
562                 return;
563         }
564         bvh->root = bvh->tree->link;
565         bvh->root->isleaf = 0;
566         bvh->root->parent = NULL;
567         bvh->root->nodes[0] = bvh->root->nodes[1] = bvh->root->nodes[1] = bvh->root->nodes[3] = NULL;
568
569         if(bvh->numfaces<=1)
570         {
571                 bvh->root->tri_index = 0;       // Why that? --> only one face there 
572                 bvh->root->isleaf = 1;
573                 bvh->root->traversed = 0;
574                 bvh->root->count_nodes = 0;
575                 bvh->leaf_root = bvh->root;
576                 bvh->leaf_tree = bvh->root;
577                 bvh->root->nextLeaf = NULL;
578                 bvh->root->prevLeaf = NULL;
579         }
580         else
581         {
582                 // create face boxes            
583                 face_list = MEM_callocN (bvh->numfaces * sizeof (CollisionTree *), "CollisionTree");
584                 if (face_list == NULL) 
585                 {
586                         printf("bvh_build: Out of memory for face_list.\n");
587                         bvh_free(bvh);
588                         return;
589                 }
590
591                 // create face boxes
592                 for(i = 0, k = 0; i < bvh->numfaces; i++)
593                 {
594                         LinkNode *tnlink;
595
596                         tree = (CollisionTree *)MEM_callocN(sizeof(CollisionTree), "CollisionTree");
597                         // TODO: check succesfull alloc
598
599                         tnlink = BLI_linklist_append_fast(&nlink->next, tree);
600
601                         face_list[i] = tree;
602                         tree->tri_index = i;
603                         tree->isleaf = 1;
604                         tree->nextLeaf = NULL;
605                         tree->prevLeaf = bvh->leaf_tree;
606                         tree->parent = NULL;
607                         tree->count_nodes = 0;
608
609                         if(i==0)
610                         {
611                                 bvh->leaf_tree = bvh->leaf_root = tree;
612                         }
613                         else
614                         {
615                                 bvh->leaf_tree->nextLeaf = tree;
616                                 bvh->leaf_tree = bvh->leaf_tree->nextLeaf;
617                         }               
618
619                         tree->nodes[0] = tree->nodes[1] = tree->nodes[2] = tree->nodes[3] = NULL;               
620
621                         bvh_calc_DOP_hull_static(bvh, &face_list[i], 1, tree->bv);
622
623                         // inflate the bv with some epsilon
624                         for (j = KDOP_START; j < KDOP_END; j++)
625                         {
626                                 tree->bv[(2 * j)] -= bvh->epsilon; // minimum 
627                                 tree->bv[(2 * j) + 1] += bvh->epsilon;  // maximum 
628                         }
629                         
630                         nlink = tnlink;
631                 }
632                 
633                 // build root bvh
634                 bvh_calc_DOP_hull_from_faces(bvh, face_list, bvh->numfaces, bvh->root->bv);
635
636                 // This is the traversal function. 
637                 bvh_div_env_node(bvh, bvh->root, face_list, 0, bvh->numfaces-1, 0, nlink);
638                 if (face_list)
639                         MEM_freeN(face_list);
640                 
641         }
642         
643 }
644
645 // bvh_overlap - is it possbile for 2 bv's to collide ?
646 DO_INLINE int bvh_overlap(float *bv1, float *bv2)
647 {
648         int i = 0;
649         for (i = KDOP_START; i < KDOP_END; i++)
650         {
651                 // Minimum test.
652                 if (bv1[(2 * i)] > bv2[(2 * i) + 1]) 
653                 {
654                         return 0;
655                 }
656                 // Maxiumum test.
657                 if (bv2[(2 * i)] > bv1[(2 * i) + 1]) 
658                 {
659                         return 0;
660                 }
661         }
662         
663         return 1;
664 }
665
666 /**
667  * bvh_traverse - traverse two bvh trees looking for potential collisions.
668  *
669  * max collisions are n*n collisions --> every triangle collide with
670  * every other triangle that doesn't require any realloc, but uses
671  * much memory
672  */
673 int bvh_traverse ( ClothModifierData * clmd, CollisionModifierData * collmd, CollisionTree * tree1, CollisionTree * tree2, float step, CM_COLLISION_RESPONSE collision_response)
674 {
675         int i = 0, ret=0;
676         
677         /*
678         // Shouldn't be possible
679         if(!tree1 || !tree2)
680         {
681         printf("Error: no tree there\n");
682         return 0;
683 }
684         */      
685         if (bvh_overlap(tree1->bv, tree2->bv)) 
686         {               
687                 // Check if this node in the first tree is a leaf
688                 if (tree1->isleaf) 
689                 {
690                         // Check if this node in the second tree a leaf
691                         if (tree2->isleaf) 
692                         {
693                                 // Provide the collision response.
694                                 
695                                 if(collision_response)
696                                         collision_response (clmd, collmd, tree1, tree2);
697                                 return 1;
698                         }
699                         else 
700                         {
701                                 // Process the quad tree.
702                                 for (i = 0; i < 4; i++)
703                                 {
704                                         // Only traverse nodes that exist.
705                                         if (tree2->nodes[i] && bvh_traverse (clmd, collmd, tree1, tree2->nodes[i], step, collision_response))
706                                                 ret = 1;
707                                 }
708                         }
709                 }
710                 else 
711                 {
712                         // Process the quad tree.
713                         for (i = 0; i < 4; i++)
714                         {
715                                 // Only traverse nodes that exist.
716                                 if (tree1->nodes [i] && bvh_traverse (clmd, collmd, tree1->nodes[i], tree2, step, collision_response))
717                                         ret = 1;
718                         }
719                 }
720         }
721
722         return ret;
723 }
724
725 // bottom up update of bvh tree:
726 // join the 4 children here
727 void bvh_join(CollisionTree * tree)
728 {
729         int     i = 0, j = 0;
730         if (!tree)
731                 return;
732         
733         for (i = 0; i < 4; i++)
734         {
735                 if (tree->nodes[i]) 
736                 {
737                         for (j = KDOP_START; j < KDOP_END; j++)
738                         {
739                                 // update minimum 
740                                 if ((tree->nodes[i]->bv[(2 * j)] < tree->bv[(2 * j)]) || (i == 0)) 
741                                 {
742                                         tree->bv[(2 * j)] = tree->nodes[i]->bv[(2 * j)];
743                                 }
744                                 // update maximum 
745                                 if ((tree->nodes[i]->bv[(2 * j) + 1] > tree->bv[(2 * j) + 1])|| (i == 0))
746                                 {
747                                         tree->bv[(2 * j) + 1] = tree->nodes[i]->bv[(2 * j) + 1];
748                                 }
749                         }
750                 }
751                 else
752                         break;
753         }
754 }
755
756 // update static bvh
757 /* you have to update the bvh position before calling this function */
758 void bvh_update(BVH * bvh, int moving)
759 {
760         CollisionTree *leaf, *parent;
761         int traversecheck = 1;  // if this is zero we don't go further 
762         unsigned int j = 0;
763         
764         for (leaf = bvh->leaf_root; leaf; leaf = leaf->nextLeaf)
765         {
766                 traversecheck = 1;
767                 if ((leaf->parent) && (leaf->parent->traversed == leaf->parent->count_nodes)) 
768                 {                       
769                         leaf->parent->traversed = 0;
770                 }
771                 if(!moving)
772                         bvh_calc_DOP_hull_static(bvh, &leaf, 1, leaf->bv);
773                 else
774                         bvh_calc_DOP_hull_moving(bvh, &leaf, 1, leaf->bv);
775
776                 // inflate the bv with some epsilon
777                 for (j = KDOP_START; j < KDOP_END; j++)
778                 {                       
779                         leaf->bv[(2 * j)] -= bvh->epsilon; // minimum 
780                         leaf->bv[(2 * j) + 1] += bvh->epsilon;  // maximum 
781                 }
782
783                 for (parent = leaf->parent; parent; parent = parent->parent)
784                 {                       
785                         if (traversecheck) 
786                         {
787                                 parent->traversed++;    // we tried to go up in hierarchy 
788                                 if (parent->traversed < parent->count_nodes) 
789                                 {
790                                         traversecheck = 0;
791
792                                         if (parent->parent) 
793                                         {
794                                                 if (parent->parent->traversed == parent->parent->count_nodes) 
795                                                 {
796                                                         parent->parent->traversed = 0;
797                                                 }
798                                         }
799                                         break;  // we do not need to check further 
800                                 }
801                                 else 
802                                 {
803                                         bvh_join(parent);
804                                 }
805                         }
806
807                 }
808         }       
809 }
810