svn merge -r37335:37500 https://svn.blender.org/svnroot/bf-blender/trunk/blender
[blender.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_squared_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->getTessFaceDataArray(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->getNumTessFaces(mesh);
579                 MVert *vert     = mesh->getVertDataArray(mesh, CD_MVERT);
580                 MFace *face = mesh->getTessFaceDataArray(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 #if 0 //BMESH_TODO
590                                 EditMesh *em= data->em_evil;
591                                 if(em) {
592                                         EditFace *efa= em->faces.first;
593                                         for(i = 0; i < numFaces; i++, efa= efa->next) {
594                                                 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))) {
595                                                         float co[4][3];
596                                                         VECCOPY(co[0], vert[ face[i].v1 ].co);
597                                                         VECCOPY(co[1], vert[ face[i].v2 ].co);
598                                                         VECCOPY(co[2], vert[ face[i].v3 ].co);
599                                                         if(face[i].v4)
600                                                                 VECCOPY(co[3], vert[ face[i].v4 ].co);
601                                         
602                                                         BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
603                                                 }
604                                         }
605 #else
606                                 if (0) {
607 #endif
608                                 }
609                                 else {
610                                         for(i = 0; i < numFaces; i++) {
611                                                 float co[4][3];
612                                                 VECCOPY(co[0], vert[ face[i].v1 ].co);
613                                                 VECCOPY(co[1], vert[ face[i].v2 ].co);
614                                                 VECCOPY(co[2], vert[ face[i].v3 ].co);
615                                                 if(face[i].v4)
616                                                         VECCOPY(co[3], vert[ face[i].v4 ].co);
617                                 
618                                                 BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
619                                         }
620                                 }
621                                 BLI_bvhtree_balance(tree);
622
623                                 //Save on cache for later use
624 //                              printf("BVHTree built and saved on cache\n");
625                                 bvhcache_insert(&mesh->bvhCache, tree, BVHTREE_FROM_FACES);
626                         }
627                 }
628         }
629         else
630         {
631 //              printf("BVHTree is already build, using cached tree\n");
632         }
633
634
635         //Setup BVHTreeFromMesh
636         memset(data, 0, sizeof(*data));
637         data->tree = tree;
638
639         if(data->tree)
640         {
641                 data->cached = TRUE;
642
643                 data->nearest_callback = mesh_faces_nearest_point;
644                 data->raycast_callback = mesh_faces_spherecast;
645
646                 data->mesh = mesh;
647                 data->vert = mesh->getVertDataArray(mesh, CD_MVERT);
648                 data->face = mesh->getTessFaceDataArray(mesh, CD_MFACE);
649
650                 data->sphere_radius = epsilon;
651         }
652         return data->tree;
653
654 }
655
656 // Builds a bvh tree.. where nodes are the faces of the given mesh.
657 BVHTree* bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *mesh, float epsilon, int tree_type, int axis)
658 {
659         BVHTree *tree = bvhcache_find(&mesh->bvhCache, BVHTREE_FROM_EDGES);
660
661         //Not in cache
662         if(tree == NULL)
663         {
664                 int i;
665                 int numEdges= mesh->getNumEdges(mesh);
666                 MVert *vert     = mesh->getVertDataArray(mesh, CD_MVERT);
667                 MEdge *edge = mesh->getEdgeDataArray(mesh, CD_MEDGE);
668
669                 if(vert != NULL && edge != NULL)
670                 {
671                         /* Create a bvh-tree of the given target */
672                         tree = BLI_bvhtree_new(numEdges, epsilon, tree_type, axis);
673                         if(tree != NULL)
674                         {
675                                 for(i = 0; i < numEdges; i++)
676                                 {
677                                         float co[4][3];
678                                         VECCOPY(co[0], vert[ edge[i].v1 ].co);
679                                         VECCOPY(co[1], vert[ edge[i].v2 ].co);
680                         
681                                         BLI_bvhtree_insert(tree, i, co[0], 2);
682                                 }
683                                 BLI_bvhtree_balance(tree);
684
685                                 //Save on cache for later use
686 //                              printf("BVHTree built and saved on cache\n");
687                                 bvhcache_insert(&mesh->bvhCache, tree, BVHTREE_FROM_EDGES);
688                         }
689                 }
690         }
691         else
692         {
693 //              printf("BVHTree is already build, using cached tree\n");
694         }
695
696
697         //Setup BVHTreeFromMesh
698         memset(data, 0, sizeof(*data));
699         data->tree = tree;
700
701         if(data->tree)
702         {
703                 data->cached = TRUE;
704
705                 data->nearest_callback = mesh_edges_nearest_point;
706                 data->raycast_callback = NULL;
707
708                 data->mesh = mesh;
709                 data->vert = mesh->getVertDataArray(mesh, CD_MVERT);
710                 data->edge = mesh->getEdgeDataArray(mesh, CD_MEDGE);
711
712                 data->sphere_radius = epsilon;
713         }
714         return data->tree;
715
716 }
717
718 // Frees data allocated by a call to bvhtree_from_mesh_*.
719 void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data)
720 {
721         if(data->tree)
722         {
723                 if(!data->cached)
724                         BLI_bvhtree_free(data->tree);
725
726                 memset( data, 0, sizeof(data) );
727         }
728 }
729
730
731 /* BVHCache */
732 typedef struct BVHCacheItem
733 {
734         int type;
735         BVHTree *tree;
736
737 } BVHCacheItem;
738
739 static void bvhcacheitem_set_if_match(void *_cached, void *_search)
740 {
741         BVHCacheItem * cached = (BVHCacheItem *)_cached;
742         BVHCacheItem * search = (BVHCacheItem *)_search;
743
744         if(search->type == cached->type)
745         {
746                 search->tree = cached->tree;            
747         }
748
749
750 BVHTree *bvhcache_find(BVHCache *cache, int type)
751 {
752         BVHCacheItem item;
753         item.type = type;
754         item.tree = NULL;
755
756         BLI_linklist_apply(*cache, bvhcacheitem_set_if_match, &item);
757         return item.tree;
758 }
759
760 void bvhcache_insert(BVHCache *cache, BVHTree *tree, int type)
761 {
762         BVHCacheItem *item = NULL;
763
764         assert( tree != NULL );
765         assert( bvhcache_find(cache, type) == NULL );
766
767         item = MEM_mallocN(sizeof(BVHCacheItem), "BVHCacheItem");
768         assert( item != NULL );
769
770         item->type = type;
771         item->tree = tree;
772
773         BLI_linklist_prepend( cache, item );
774 }
775
776
777 void bvhcache_init(BVHCache *cache)
778 {
779         *cache = NULL;
780 }
781
782 static void bvhcacheitem_free(void *_item)
783 {
784         BVHCacheItem *item = (BVHCacheItem *)_item;
785
786         BLI_bvhtree_free(item->tree);
787         MEM_freeN(item);
788 }
789
790
791 void bvhcache_free(BVHCache *cache)
792 {
793         BLI_linklist_free(*cache, (LinkNodeFreeFP)bvhcacheitem_free);
794         *cache = NULL;
795 }
796
797