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