5520e4d1d412cb129edf8c4e3175a1aa23b23304
[blender-staging.git] / source / blender / blenkernel / intern / bvhutils.c
1 /*
2  *
3  * $Id$
4  *
5  * ***** BEGIN GPL LICENSE BLOCK *****
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, write to the Free Software Foundation,
19  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20  *
21  * The Original Code is Copyright (C) Blender Foundation.
22  * All rights reserved.
23  *
24  * The Original Code is: all of this file.
25  *
26  * Contributor(s): Andr Pinto.
27  *
28  * ***** END GPL LICENSE BLOCK *****
29  */
30
31 /** \file blender/blenkernel/intern/bvhutils.c
32  *  \ingroup bke
33  */
34
35 #include <stdio.h>
36 #include <string.h>
37 #include <math.h>
38 #include <assert.h>
39
40 #include "DNA_meshdata_types.h"
41
42 #include "BLI_editVert.h"
43 #include "BLI_utildefines.h"
44
45 #include "BKE_DerivedMesh.h"
46
47
48 #include "BLI_math.h"
49 #include "MEM_guardedalloc.h"
50
51 /* Math stuff for ray casting on mesh faces and for nearest surface */
52
53 static float ray_tri_intersection(const BVHTreeRay *ray, const float UNUSED(m_dist), const float *v0, const float *v1, const float *v2)
54 {
55         float dist;
56
57         if(isect_ray_tri_v3((float*)ray->origin, (float*)ray->direction, (float*)v0, (float*)v1, (float*)v2, &dist, NULL))
58                 return dist;
59
60         return FLT_MAX;
61 }
62
63 static float sphereray_tri_intersection(const BVHTreeRay *ray, float radius, const float m_dist, const float *v0, const float *v1, const float *v2)
64 {
65         
66         float idist;
67         float p1[3];
68         float plane_normal[3], hit_point[3];
69
70         normal_tri_v3( plane_normal,(float*)v0, (float*)v1, (float*)v2);
71
72         VECADDFAC( p1, ray->origin, ray->direction, m_dist);
73         if(isect_sweeping_sphere_tri_v3((float*)ray->origin, p1, radius, (float*)v0, (float*)v1, (float*)v2, &idist, hit_point))
74         {
75                 return idist * m_dist;
76         }
77
78         return FLT_MAX;
79 }
80
81
82 /*
83  * Function adapted from David Eberly's distance tools (LGPL)
84  * http://www.geometrictools.com/LibFoundation/Distance/Distance.html
85  */
86 static float nearest_point_in_tri_surface(const float *v0,const float *v1,const float *v2,const float *p, int *v, int *e, float *nearest )
87 {
88         float diff[3];
89         float e0[3];
90         float e1[3];
91         float A00;
92         float A01;
93         float A11;
94         float B0;
95         float B1;
96         float C;
97         float Det;
98         float S;
99         float T;
100         float sqrDist;
101         int lv = -1, le = -1;
102         
103         VECSUB(diff, v0, p);
104         VECSUB(e0, v1, v0);
105         VECSUB(e1, v2, v0);
106         
107         A00 = INPR ( e0, e0 );
108         A01 = INPR( e0, e1 );
109         A11 = INPR ( e1, e1 );
110         B0 = INPR( diff, e0 );
111         B1 = INPR( diff, e1 );
112         C = INPR( diff, diff );
113         Det = fabs( A00 * A11 - A01 * A01 );
114         S = A01 * B1 - A11 * B0;
115         T = A01 * B0 - A00 * B1;
116
117         if ( S + T <= Det )
118         {
119                 if ( S < 0.0f )
120                 {
121                         if ( T < 0.0f )  // Region 4
122                         {
123                                 if ( B0 < 0.0f )
124                                 {
125                                         T = 0.0f;
126                                         if ( -B0 >= A00 )
127                                         {
128                                                 S = (float)1.0;
129                                                 sqrDist = A00 + 2.0f * B0 + C;
130                                                 lv = 1;
131                                         }
132                                         else
133                                         {
134                                                 if(fabsf(A00) > FLT_EPSILON)
135                                                         S = -B0/A00;
136                                                 else
137                                                         S = 0.0f;
138                                                 sqrDist = B0 * S + C;
139                                                 le = 0;
140                                         }
141                                 }
142                                 else
143                                 {
144                                         S = 0.0f;
145                                         if ( B1 >= 0.0f )
146                                         {
147                                                 T = 0.0f;
148                                                 sqrDist = C;
149                                                 lv = 0;
150                                         }
151                                         else if ( -B1 >= A11 )
152                                         {
153                                                 T = 1.0f;
154                                                 sqrDist = A11 + 2.0f * B1 + C;
155                                                 lv = 2;
156                                         }
157                                         else
158                                         {
159                                                 if(fabsf(A11) > FLT_EPSILON)
160                                                         T = -B1 / A11;
161                                                 else
162                                                         T = 0.0f;
163                                                 sqrDist = B1 * T + C;
164                                                 le = 1;
165                                         }
166                                 }
167                         }
168                         else  // Region 3
169                         {
170                                 S = 0.0f;
171                                 if ( B1 >= 0.0f )
172                                 {
173                                         T = 0.0f;
174                                         sqrDist = C;
175                                         lv = 0;
176                                 }
177                                 else if ( -B1 >= A11 )
178                                 {
179                                         T = 1.0f;
180                                         sqrDist = A11 + 2.0f * B1 + C;
181                                         lv = 2;
182                                 }
183                                 else
184                                 {
185                                         if(fabsf(A11) > FLT_EPSILON)
186                                                 T = -B1 / A11;
187                                         else
188                                                 T = 0.0;
189                                         sqrDist = B1 * T + C;
190                                         le = 1;
191                                 }
192                         }
193                 }
194                 else if ( T < 0.0f )  // Region 5
195                 {
196                         T = 0.0f;
197                         if ( B0 >= 0.0f )
198                         {
199                                 S = 0.0f;
200                                 sqrDist = C;
201                                 lv = 0;
202                         }
203                         else if ( -B0 >= A00 )
204                         {
205                                 S = 1.0f;
206                                 sqrDist = A00 + 2.0f * B0 + C;
207                                 lv = 1;
208                         }
209                         else
210                         {
211                                 if(fabsf(A00) > FLT_EPSILON)
212                                         S = -B0 / A00;
213                                 else
214                                         S = 0.0f;
215                                 sqrDist = B0 * S + C;
216                                 le = 0;
217                         }
218                 }
219                 else  // Region 0
220                 {
221                         // Minimum at interior lv
222                         float invDet;
223                         if(fabsf(Det) > FLT_EPSILON)
224                                 invDet = 1.0f / Det;
225                         else
226                                 invDet = 0.0f;
227                         S *= invDet;
228                         T *= invDet;
229                         sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0) +
230                                         T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
231                 }
232         }
233         else
234         {
235                 float tmp0, tmp1, numer, denom;
236
237                 if ( S < 0.0f )  // Region 2
238                 {
239                         tmp0 = A01 + B0;
240                         tmp1 = A11 + B1;
241                         if ( tmp1 > tmp0 )
242                         {
243                                 numer = tmp1 - tmp0;
244                                 denom = A00 - 2.0f * A01 + A11;
245                                 if ( numer >= denom )
246                                 {
247                                         S = 1.0f;
248                                         T = 0.0f;
249                                         sqrDist = A00 + 2.0f * B0 + C;
250                                         lv = 1;
251                                 }
252                                 else
253                                 {
254                                         if(fabsf(denom) > FLT_EPSILON)
255                                                 S = numer / denom;
256                                         else
257                                                 S = 0.0f;
258                                         T = 1.0f - S;
259                                         sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) +
260                                                         T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
261                                         le = 2;
262                                 }
263                         }
264                         else
265                         {
266                                 S = 0.0f;
267                                 if ( tmp1 <= 0.0f )
268                                 {
269                                         T = 1.0f;
270                                         sqrDist = A11 + 2.0f * B1 + C;
271                                         lv = 2;
272                                 }
273                                 else if ( B1 >= 0.0f )
274                                 {
275                                         T = 0.0f;
276                                         sqrDist = C;
277                                         lv = 0;
278                                 }
279                                 else
280                                 {
281                                         if(fabsf(A11) > FLT_EPSILON)
282                                                 T = -B1 / A11;
283                                         else
284                                                 T = 0.0f;
285                                         sqrDist = B1 * T + C;
286                                         le = 1;
287                                 }
288                         }
289                 }
290                 else if ( T < 0.0f )  // Region 6
291                 {
292                         tmp0 = A01 + B1;
293                         tmp1 = A00 + B0;
294                         if ( tmp1 > tmp0 )
295                         {
296                                 numer = tmp1 - tmp0;
297                                 denom = A00 - 2.0f * A01 + A11;
298                                 if ( numer >= denom )
299                                 {
300                                         T = 1.0f;
301                                         S = 0.0f;
302                                         sqrDist = A11 + 2.0f * B1 + C;
303                                         lv = 2;
304                                 }
305                                 else
306                                 {
307                                         if(fabsf(denom) > FLT_EPSILON)
308                                                 T = numer / denom;
309                                         else
310                                                 T = 0.0f;
311                                         S = 1.0f - T;
312                                         sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) +
313                                                         T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
314                                         le = 2;
315                                 }
316                         }
317                         else
318                         {
319                                 T = 0.0f;
320                                 if ( tmp1 <= 0.0f )
321                                 {
322                                         S = 1.0f;
323                                         sqrDist = A00 + 2.0f * B0 + C;
324                                         lv = 1;
325                                 }
326                                 else if ( B0 >= 0.0f )
327                                 {
328                                         S = 0.0f;
329                                         sqrDist = C;
330                                         lv = 0;
331                                 }
332                                 else
333                                 {
334                                         if(fabsf(A00) > FLT_EPSILON)
335                                                 S = -B0 / A00;
336                                         else
337                                                 S = 0.0f;
338                                         sqrDist = B0 * S + C;
339                                         le = 0;
340                                 }
341                         }
342                 }
343                 else  // Region 1
344                 {
345                         numer = A11 + B1 - A01 - B0;
346                         if ( numer <= 0.0f )
347                         {
348                                 S = 0.0f;
349                                 T = 1.0f;
350                                 sqrDist = A11 + 2.0f * B1 + C;
351                                 lv = 2;
352                         }
353                         else
354                         {
355                                 denom = A00 - 2.0f * A01 + A11;
356                                 if ( numer >= denom )
357                                 {
358                                         S = 1.0f;
359                                         T = 0.0f;
360                                         sqrDist = A00 + 2.0f * B0 + C;
361                                         lv = 1;
362                                 }
363                                 else
364                                 {
365                                         if(fabsf(denom) > FLT_EPSILON)
366                                                 S = numer / denom;
367                                         else
368                                                 S = 0.0f;
369                                         T = 1.0f - S;
370                                         sqrDist = S * ( A00 * S + A01 * T + 2.0f * B0 ) +
371                                                         T * ( A01 * S + A11 * T + 2.0f * B1 ) + C;
372                                         le = 2;
373                                 }
374                         }
375                 }
376         }
377
378         // Account for numerical round-off error
379         if ( sqrDist < FLT_EPSILON )
380                 sqrDist = 0.0f;
381         
382         {
383                 float w[3], x[3], y[3], z[3];
384                 VECCOPY(w, v0);
385                 VECCOPY(x, e0);
386                 mul_v3_fl(x, S);
387                 VECCOPY(y, e1);
388                 mul_v3_fl(y, T);
389                 VECADD(z, w, x);
390                 VECADD(z, z, y);
391                 //VECSUB(d, p, z);
392                 VECCOPY(nearest, z);
393                 // d = p - ( v0 + S * e0 + T * e1 );
394         }
395         *v = lv;
396         *e = le;
397
398         return sqrDist;
399 }
400
401
402 /*
403  * BVH from meshs callbacks
404  */
405
406 // Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_faces.
407 // userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
408 static void mesh_faces_nearest_point(void *userdata, int index, const float *co, BVHTreeNearest *nearest)
409 {
410         const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
411         MVert *vert     = data->vert;
412         MFace *face = data->face + index;
413
414         float *t0, *t1, *t2, *t3;
415         t0 = vert[ face->v1 ].co;
416         t1 = vert[ face->v2 ].co;
417         t2 = vert[ face->v3 ].co;
418         t3 = face->v4 ? vert[ face->v4].co : NULL;
419
420         
421         do
422         {       
423                 float nearest_tmp[3], dist;
424                 int vertex, edge;
425                 
426                 dist = nearest_point_in_tri_surface(t0, t1, t2, co, &vertex, &edge, nearest_tmp);
427                 if(dist < nearest->dist)
428                 {
429                         nearest->index = index;
430                         nearest->dist = dist;
431                         VECCOPY(nearest->co, nearest_tmp);
432                         normal_tri_v3( nearest->no,t0, t1, t2);
433                 }
434
435                 t1 = t2;
436                 t2 = t3;
437                 t3 = NULL;
438
439         } while(t2);
440 }
441
442 // Callback to bvh tree raycast. The tree must bust have been built using bvhtree_from_mesh_faces.
443 // userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
444 static void mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
445 {
446         const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
447         MVert *vert     = data->vert;
448         MFace *face = data->face + index;
449
450         float *t0, *t1, *t2, *t3;
451         t0 = vert[ face->v1 ].co;
452         t1 = vert[ face->v2 ].co;
453         t2 = vert[ face->v3 ].co;
454         t3 = face->v4 ? vert[ face->v4].co : NULL;
455
456         
457         do
458         {       
459                 float dist;
460                 if(data->sphere_radius == 0.0f)
461                         dist = ray_tri_intersection(ray, hit->dist, t0, t1, t2);
462                 else
463                         dist = sphereray_tri_intersection(ray, data->sphere_radius, hit->dist, t0, t1, t2);
464
465                 if(dist >= 0 && dist < hit->dist)
466                 {
467                         hit->index = index;
468                         hit->dist = dist;
469                         VECADDFAC(hit->co, ray->origin, ray->direction, dist);
470
471                         normal_tri_v3( hit->no,t0, t1, t2);
472                 }
473
474                 t1 = t2;
475                 t2 = t3;
476                 t3 = NULL;
477
478         } while(t2);
479 }
480
481 // Callback to bvh tree nearest point. The tree must bust have been built using bvhtree_from_mesh_edges.
482 // userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree.
483 static void mesh_edges_nearest_point(void *userdata, int index, const float *co, BVHTreeNearest *nearest)
484 {
485         const BVHTreeFromMesh *data = (BVHTreeFromMesh*) userdata;
486         MVert *vert     = data->vert;
487         MEdge *edge = data->edge + index;
488         float nearest_tmp[3], dist;
489
490         float *t0, *t1;
491         t0 = vert[ edge->v1 ].co;
492         t1 = vert[ edge->v2 ].co;
493         
494         // NOTE: casts to "float*" here are due to co being "const float*"
495         closest_to_line_segment_v3(nearest_tmp, (float*)co, t0, t1);
496         dist = len_v3v3(nearest_tmp, (float*)co);
497         
498         if(dist < nearest->dist)
499         {
500                 nearest->index = index;
501                 nearest->dist = dist;
502                 VECCOPY(nearest->co, nearest_tmp);
503                 sub_v3_v3v3(nearest->no, t0, t1);
504                 normalize_v3(nearest->no);
505         }
506 }
507
508 /*
509  * BVH builders
510  */
511 // Builds a bvh tree.. where nodes are the vertexs of the given mesh
512 BVHTree* bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis)
513 {
514         BVHTree *tree = bvhcache_find(&mesh->bvhCache, BVHTREE_FROM_VERTICES);
515
516         //Not in cache
517         if(tree == NULL)
518         {
519                 int i;
520                 int numVerts= mesh->getNumVerts(mesh);
521                 MVert *vert     = mesh->getVertDataArray(mesh, CD_MVERT);
522
523                 if(vert != NULL)
524                 {
525                         tree = BLI_bvhtree_new(numVerts, epsilon, tree_type, axis);
526
527                         if(tree != NULL)
528                         {
529                                 for(i = 0; i < numVerts; i++)
530                                         BLI_bvhtree_insert(tree, i, vert[i].co, 1);
531
532                                 BLI_bvhtree_balance(tree);
533
534                                 //Save on cache for later use
535 //                              printf("BVHTree built and saved on cache\n");
536                                 bvhcache_insert(&mesh->bvhCache, tree, BVHTREE_FROM_VERTICES);
537                         }
538                 }
539         }
540         else
541         {
542 //              printf("BVHTree is already build, using cached tree\n");
543         }
544
545
546         //Setup BVHTreeFromMesh
547         memset(data, 0, sizeof(*data));
548         data->tree = tree;
549
550         if(data->tree)
551         {
552                 data->cached = TRUE;
553
554                 //a NULL nearest callback works fine
555                 //remeber the min distance to point is the same as the min distance to BV of point
556                 data->nearest_callback = NULL;
557                 data->raycast_callback = NULL;
558
559                 data->mesh = mesh;
560                 data->vert = mesh->getVertDataArray(mesh, CD_MVERT);
561                 data->face = mesh->getFaceDataArray(mesh, CD_MFACE);
562
563                 data->sphere_radius = epsilon;
564         }
565
566         return data->tree;
567 }
568
569 // Builds a bvh tree.. where nodes are the faces of the given mesh.
570 BVHTree* bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis)
571 {
572         BVHTree *tree = bvhcache_find(&mesh->bvhCache, BVHTREE_FROM_FACES);
573
574         //Not in cache
575         if(tree == NULL)
576         {
577                 int i;
578                 int numFaces= mesh->getNumFaces(mesh);
579                 MVert *vert     = mesh->getVertDataArray(mesh, CD_MVERT);
580                 MFace *face = mesh->getFaceDataArray(mesh, CD_MFACE);
581
582                 if(vert != NULL && face != NULL)
583                 {
584                         /* Create a bvh-tree of the given target */
585                         tree = BLI_bvhtree_new(numFaces, epsilon, tree_type, axis);
586                         if(tree != NULL)
587                         {
588                                 /* XXX, for snap only, em & dm are assumed to be aligned, since dm is the em's cage */
589                                 EditMesh *em= data->em_evil;
590                                 if(em) {
591                                         EditFace *efa= em->faces.first;
592                                         for(i = 0; i < numFaces; i++, efa= efa->next) {
593                                                 if(!(efa->f & 1) && efa->h==0 && !((efa->v1->f&1)+(efa->v2->f&1)+(efa->v3->f&1)+(efa->v4?efa->v4->f&1:0))) {
594                                                         float co[4][3];
595                                                         VECCOPY(co[0], vert[ face[i].v1 ].co);
596                                                         VECCOPY(co[1], vert[ face[i].v2 ].co);
597                                                         VECCOPY(co[2], vert[ face[i].v3 ].co);
598                                                         if(face[i].v4)
599                                                                 VECCOPY(co[3], vert[ face[i].v4 ].co);
600                                         
601                                                         BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
602                                                 }
603                                         }
604                                 }
605                                 else {
606                                         for(i = 0; i < numFaces; i++) {
607                                                 float co[4][3];
608                                                 VECCOPY(co[0], vert[ face[i].v1 ].co);
609                                                 VECCOPY(co[1], vert[ face[i].v2 ].co);
610                                                 VECCOPY(co[2], vert[ face[i].v3 ].co);
611                                                 if(face[i].v4)
612                                                         VECCOPY(co[3], vert[ face[i].v4 ].co);
613                                 
614                                                 BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
615                                         }
616                                 }
617                                 BLI_bvhtree_balance(tree);
618
619                                 //Save on cache for later use
620 //                              printf("BVHTree built and saved on cache\n");
621                                 bvhcache_insert(&mesh->bvhCache, tree, BVHTREE_FROM_FACES);
622                         }
623                 }
624         }
625         else
626         {
627 //              printf("BVHTree is already build, using cached tree\n");
628         }
629
630
631         //Setup BVHTreeFromMesh
632         memset(data, 0, sizeof(*data));
633         data->tree = tree;
634
635         if(data->tree)
636         {
637                 data->cached = TRUE;
638
639                 data->nearest_callback = mesh_faces_nearest_point;
640                 data->raycast_callback = mesh_faces_spherecast;
641
642                 data->mesh = mesh;
643                 data->vert = mesh->getVertDataArray(mesh, CD_MVERT);
644                 data->face = mesh->getFaceDataArray(mesh, CD_MFACE);
645
646                 data->sphere_radius = epsilon;
647         }
648         return data->tree;
649
650 }
651
652 // Builds a bvh tree.. where nodes are the faces of the given mesh.
653 BVHTree* bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis)
654 {
655         BVHTree *tree = bvhcache_find(&mesh->bvhCache, BVHTREE_FROM_EDGES);
656
657         //Not in cache
658         if(tree == NULL)
659         {
660                 int i;
661                 int numEdges= mesh->getNumEdges(mesh);
662                 MVert *vert     = mesh->getVertDataArray(mesh, CD_MVERT);
663                 MEdge *edge = mesh->getEdgeDataArray(mesh, CD_MEDGE);
664
665                 if(vert != NULL && edge != NULL)
666                 {
667                         /* Create a bvh-tree of the given target */
668                         tree = BLI_bvhtree_new(numEdges, epsilon, tree_type, axis);
669                         if(tree != NULL)
670                         {
671                                 for(i = 0; i < numEdges; i++)
672                                 {
673                                         float co[4][3];
674                                         VECCOPY(co[0], vert[ edge[i].v1 ].co);
675                                         VECCOPY(co[1], vert[ edge[i].v2 ].co);
676                         
677                                         BLI_bvhtree_insert(tree, i, co[0], 2);
678                                 }
679                                 BLI_bvhtree_balance(tree);
680
681                                 //Save on cache for later use
682 //                              printf("BVHTree built and saved on cache\n");
683                                 bvhcache_insert(&mesh->bvhCache, tree, BVHTREE_FROM_EDGES);
684                         }
685                 }
686         }
687         else
688         {
689 //              printf("BVHTree is already build, using cached tree\n");
690         }
691
692
693         //Setup BVHTreeFromMesh
694         memset(data, 0, sizeof(*data));
695         data->tree = tree;
696
697         if(data->tree)
698         {
699                 data->cached = TRUE;
700
701                 data->nearest_callback = mesh_edges_nearest_point;
702                 data->raycast_callback = NULL;
703
704                 data->mesh = mesh;
705                 data->vert = mesh->getVertDataArray(mesh, CD_MVERT);
706                 data->edge = mesh->getEdgeDataArray(mesh, CD_MEDGE);
707
708                 data->sphere_radius = epsilon;
709         }
710         return data->tree;
711
712 }
713
714 // Frees data allocated by a call to bvhtree_from_mesh_*.
715 void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data)
716 {
717         if(data->tree)
718         {
719                 if(!data->cached)
720                         BLI_bvhtree_free(data->tree);
721
722                 memset( data, 0, sizeof(data) );
723         }
724 }
725
726
727 /* BVHCache */
728 typedef struct BVHCacheItem
729 {
730         int type;
731         BVHTree *tree;
732
733 } BVHCacheItem;
734
735 static void bvhcacheitem_set_if_match(void *_cached, void *_search)
736 {
737         BVHCacheItem * cached = (BVHCacheItem *)_cached;
738         BVHCacheItem * search = (BVHCacheItem *)_search;
739
740         if(search->type == cached->type)
741         {
742                 search->tree = cached->tree;            
743         }
744
745
746 BVHTree *bvhcache_find(BVHCache *cache, int type)
747 {
748         BVHCacheItem item;
749         item.type = type;
750         item.tree = NULL;
751
752         BLI_linklist_apply(*cache, bvhcacheitem_set_if_match, &item);
753         return item.tree;
754 }
755
756 void bvhcache_insert(BVHCache *cache, BVHTree *tree, int type)
757 {
758         BVHCacheItem *item = NULL;
759
760         assert( tree != NULL );
761         assert( bvhcache_find(cache, type) == NULL );
762
763         item = MEM_mallocN(sizeof(BVHCacheItem), "BVHCacheItem");
764         assert( item != NULL );
765
766         item->type = type;
767         item->tree = tree;
768
769         BLI_linklist_prepend( cache, item );
770 }
771
772
773 void bvhcache_init(BVHCache *cache)
774 {
775         *cache = NULL;
776 }
777
778 static void bvhcacheitem_free(void *_item)
779 {
780         BVHCacheItem *item = (BVHCacheItem *)_item;
781
782         BLI_bvhtree_free(item->tree);
783         MEM_freeN(item);
784 }
785
786
787 void bvhcache_free(BVHCache *cache)
788 {
789         BLI_linklist_free(*cache, (LinkNodeFreeFP)bvhcacheitem_free);
790         *cache = NULL;
791 }
792
793