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