Cleanup: warnings & style
[blender.git] / source / blender / blenkernel / intern / bvhutils.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Andr Pinto.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/bvhutils.c
29  *  \ingroup bke
30  */
31
32 #include <stdio.h>
33 #include <string.h>
34 #include <math.h>
35 #include <assert.h>
36
37 #include "DNA_meshdata_types.h"
38
39 #include "BLI_utildefines.h"
40 #include "BLI_linklist.h"
41 #include "BLI_math.h"
42 #include "BLI_threads.h"
43
44 #include "BKE_DerivedMesh.h"
45 #include "BKE_editmesh.h"
46
47 #include "MEM_guardedalloc.h"
48
49 static ThreadRWMutex cache_rwlock = BLI_RWLOCK_INITIALIZER;
50
51 /* -------------------------------------------------------------------- */
52 /** \name Local Callbacks
53  * \{ */
54
55 /* Math stuff for ray casting on mesh faces and for nearest surface */
56
57 float bvhtree_ray_tri_intersection(
58         const BVHTreeRay *ray, const float UNUSED(m_dist),
59         const float v0[3], const float v1[3], const float v2[3])
60 {
61         float dist;
62
63 #ifdef USE_KDOPBVH_WATERTIGHT
64         if (isect_ray_tri_watertight_v3(ray->origin, ray->isect_precalc, v0, v1, v2, &dist, NULL))
65 #else
66         if (isect_ray_tri_epsilon_v3(ray->origin, ray->direction, v0, v1, v2, &dist, NULL, FLT_EPSILON))
67 #endif
68         {
69                 return dist;
70         }
71
72         return FLT_MAX;
73 }
74
75 float bvhtree_sphereray_tri_intersection(
76         const BVHTreeRay *ray, float radius, const float m_dist,
77         const float v0[3], const float v1[3], const float v2[3])
78 {
79         
80         float idist;
81         float p1[3];
82         float hit_point[3];
83
84         madd_v3_v3v3fl(p1, ray->origin, ray->direction, m_dist);
85         if (isect_sweeping_sphere_tri_v3(ray->origin, p1, radius, v0, v1, v2, &idist, hit_point)) {
86                 return idist * m_dist;
87         }
88
89         return FLT_MAX;
90 }
91
92 /*
93  * BVH from meshes callbacks
94  */
95
96 /* Callback to bvh tree nearest point. The tree must have been built using bvhtree_from_mesh_faces.
97  * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
98 static void mesh_faces_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
99 {
100         const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata;
101         const MVert *vert = data->vert;
102         const MFace *face = data->face + index;
103
104         const float *t0, *t1, *t2, *t3;
105         t0 = vert[face->v1].co;
106         t1 = vert[face->v2].co;
107         t2 = vert[face->v3].co;
108         t3 = face->v4 ? vert[face->v4].co : NULL;
109
110         
111         do {
112                 float nearest_tmp[3], dist_sq;
113
114                 closest_on_tri_to_point_v3(nearest_tmp, co, t0, t1, t2);
115                 dist_sq = len_squared_v3v3(co, nearest_tmp);
116
117                 if (dist_sq < nearest->dist_sq) {
118                         nearest->index = index;
119                         nearest->dist_sq = dist_sq;
120                         copy_v3_v3(nearest->co, nearest_tmp);
121                         normal_tri_v3(nearest->no, t0, t1, t2);
122                 }
123
124                 t1 = t2;
125                 t2 = t3;
126                 t3 = NULL;
127
128         } while (t2);
129 }
130 /* copy of function above */
131 static void mesh_looptri_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
132 {
133         const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata;
134         const MVert *vert = data->vert;
135         const MLoopTri *lt = &data->looptri[index];
136         const float *vtri_co[3] = {
137             vert[data->loop[lt->tri[0]].v].co,
138             vert[data->loop[lt->tri[1]].v].co,
139             vert[data->loop[lt->tri[2]].v].co,
140         };
141         float nearest_tmp[3], dist_sq;
142
143         closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(vtri_co));
144         dist_sq = len_squared_v3v3(co, nearest_tmp);
145
146         if (dist_sq < nearest->dist_sq) {
147                 nearest->index = index;
148                 nearest->dist_sq = dist_sq;
149                 copy_v3_v3(nearest->co, nearest_tmp);
150                 normal_tri_v3(nearest->no, UNPACK3(vtri_co));
151         }
152 }
153 /* copy of function above (warning, should de-duplicate with editmesh_bvh.c) */
154 static void editmesh_faces_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
155 {
156         const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata;
157         BMEditMesh *em = data->em_evil;
158         const BMLoop **ltri = (const BMLoop **)em->looptris[index];
159
160         const float *t0, *t1, *t2;
161         t0 = ltri[0]->v->co;
162         t1 = ltri[1]->v->co;
163         t2 = ltri[2]->v->co;
164
165         {
166                 float nearest_tmp[3], dist_sq;
167
168                 closest_on_tri_to_point_v3(nearest_tmp, co, t0, t1, t2);
169                 dist_sq = len_squared_v3v3(co, nearest_tmp);
170
171                 if (dist_sq < nearest->dist_sq) {
172                         nearest->index = index;
173                         nearest->dist_sq = dist_sq;
174                         copy_v3_v3(nearest->co, nearest_tmp);
175                         normal_tri_v3(nearest->no, t0, t1, t2);
176                 }
177         }
178 }
179
180 /* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_faces.
181  * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
182 static void mesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
183 {
184         const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata;
185         const MVert *vert = data->vert;
186         const MFace *face = &data->face[index];
187
188         const float *t0, *t1, *t2, *t3;
189         t0 = vert[face->v1].co;
190         t1 = vert[face->v2].co;
191         t2 = vert[face->v3].co;
192         t3 = face->v4 ? vert[face->v4].co : NULL;
193
194         
195         do {
196                 float dist;
197                 if (data->sphere_radius == 0.0f)
198                         dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
199                 else
200                         dist = bvhtree_sphereray_tri_intersection(ray, data->sphere_radius, hit->dist, t0, t1, t2);
201
202                 if (dist >= 0 && dist < hit->dist) {
203                         hit->index = index;
204                         hit->dist = dist;
205                         madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
206
207                         normal_tri_v3(hit->no, t0, t1, t2);
208                 }
209
210                 t1 = t2;
211                 t2 = t3;
212                 t3 = NULL;
213
214         } while (t2);
215 }
216 /* copy of function above */
217 static void mesh_looptri_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
218 {
219         const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata;
220         const MVert *vert = data->vert;
221         const MLoopTri *lt = &data->looptri[index];
222         const float *vtri_co[3] = {
223             vert[data->loop[lt->tri[0]].v].co,
224             vert[data->loop[lt->tri[1]].v].co,
225             vert[data->loop[lt->tri[2]].v].co,
226         };
227         float dist;
228
229         if (data->sphere_radius == 0.0f)
230                 dist = bvhtree_ray_tri_intersection(ray, hit->dist, UNPACK3(vtri_co));
231         else
232                 dist = bvhtree_sphereray_tri_intersection(ray, data->sphere_radius, hit->dist, UNPACK3(vtri_co));
233
234         if (dist >= 0 && dist < hit->dist) {
235                 hit->index = index;
236                 hit->dist = dist;
237                 madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
238
239                 normal_tri_v3(hit->no, UNPACK3(vtri_co));
240         }
241 }
242 /* copy of function above (warning, should de-duplicate with editmesh_bvh.c) */
243 static void editmesh_faces_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
244 {
245         const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata;
246         BMEditMesh *em = data->em_evil;
247         const BMLoop **ltri = (const BMLoop **)em->looptris[index];
248
249         const float *t0, *t1, *t2;
250         t0 = ltri[0]->v->co;
251         t1 = ltri[1]->v->co;
252         t2 = ltri[2]->v->co;
253
254
255         {
256                 float dist;
257                 if (data->sphere_radius == 0.0f)
258                         dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
259                 else
260                         dist = bvhtree_sphereray_tri_intersection(ray, data->sphere_radius, hit->dist, t0, t1, t2);
261
262                 if (dist >= 0 && dist < hit->dist) {
263                         hit->index = index;
264                         hit->dist = dist;
265                         madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
266
267                         normal_tri_v3(hit->no, t0, t1, t2);
268                 }
269         }
270 }
271
272 /* Callback to bvh tree nearest point. The tree must have been built using bvhtree_from_mesh_edges.
273  * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
274 static void mesh_edges_nearest_point(void *userdata, int index, const float co[3], BVHTreeNearest *nearest)
275 {
276         const BVHTreeFromMesh *data = (BVHTreeFromMesh *) userdata;
277         const MVert *vert = data->vert;
278         const MEdge *edge = data->edge + index;
279         float nearest_tmp[3], dist_sq;
280
281         const float *t0, *t1;
282         t0 = vert[edge->v1].co;
283         t1 = vert[edge->v2].co;
284
285         closest_to_line_segment_v3(nearest_tmp, co, t0, t1);
286         dist_sq = len_squared_v3v3(nearest_tmp, co);
287         
288         if (dist_sq < nearest->dist_sq) {
289                 nearest->index = index;
290                 nearest->dist_sq = dist_sq;
291                 copy_v3_v3(nearest->co, nearest_tmp);
292                 sub_v3_v3v3(nearest->no, t0, t1);
293                 normalize_v3(nearest->no);
294         }
295 }
296
297 /* Helper, does all the point-spherecast work actually. */
298 static void mesh_verts_spherecast_do(
299         const BVHTreeFromMesh *UNUSED(data), int index, const float v[3], const BVHTreeRay *ray, BVHTreeRayHit *hit)
300 {
301         float dist;
302         const float *r1;
303         float r2[3], i1[3];
304         r1 = ray->origin;
305         add_v3_v3v3(r2, r1, ray->direction);
306
307         closest_to_line_segment_v3(i1, v, r1, r2);
308
309         /* No hit if closest point is 'behind' the origin of the ray, or too far away from it. */
310         if ((dot_v3v3v3(r1, i1, r2) >= 0.0f) && ((dist = len_v3v3(r1, i1)) < hit->dist)) {
311                 hit->index = index;
312                 hit->dist = dist;
313                 copy_v3_v3(hit->co, i1);
314         }
315 }
316
317 /* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_verts.
318  * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
319 static void mesh_verts_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
320 {
321         const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
322         const float *v = data->vert[index].co;
323
324         mesh_verts_spherecast_do(data, index, v, ray, hit);
325 }
326
327 /* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_edges.
328  * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
329 static void mesh_edges_spherecast(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
330 {
331         const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
332         const MVert *vert = data->vert;
333         const MEdge *edge = &data->edge[index];
334
335         const float radius_sq = SQUARE(data->sphere_radius);
336         float dist;
337         const float *v1, *v2, *r1;
338         float r2[3], i1[3], i2[3];
339         v1 = vert[edge->v1].co;
340         v2 = vert[edge->v2].co;
341
342         /* In case we get a zero-length edge, handle it as a point! */
343         if (equals_v3v3(v1, v2)) {
344                 mesh_verts_spherecast_do(data, index, v1, ray, hit);
345                 return;
346         }
347
348         r1 = ray->origin;
349         add_v3_v3v3(r2, r1, ray->direction);
350
351         if (isect_line_line_v3(v1, v2, r1, r2, i1, i2)) {
352                 /* No hit if intersection point is 'behind' the origin of the ray, or too far away from it. */
353                 if ((dot_v3v3v3(r1, i2, r2) >= 0.0f) && ((dist = len_v3v3(r1, i2)) < hit->dist)) {
354                         const float e_fac = line_point_factor_v3(i1, v1, v2);
355                         if (e_fac < 0.0f) {
356                                 copy_v3_v3(i1, v1);
357                         }
358                         else if (e_fac > 1.0f) {
359                                 copy_v3_v3(i1, v2);
360                         }
361                         /* Ensure ray is really close enough from edge! */
362                         if (len_squared_v3v3(i1, i2) <= radius_sq) {
363                                 hit->index = index;
364                                 hit->dist = dist;
365                                 copy_v3_v3(hit->co, i2);
366                         }
367                 }
368         }
369 }
370
371 /** \} */
372
373 /*
374  * BVH builders
375  */
376
377
378 /* -------------------------------------------------------------------- */
379
380 /** \name Vertex Builder
381  * \{ */
382
383 static BVHTree *bvhtree_from_mesh_verts_create_tree(
384         float epsilon, int tree_type, int axis,
385         BMEditMesh *em, const int *index_array,
386         MVert *vert, const int numVerts,
387         BLI_bitmap *mask, int numVerts_active)
388 {
389         BVHTree *tree = NULL;
390         BMVert *eve = NULL;
391         int i;
392         int index = 0;
393         if (em != NULL) {
394                 BM_mesh_elem_table_ensure(em->bm, BM_VERT);
395         }
396         if (vert) {
397                 if (mask && numVerts_active < 0) {
398                         numVerts_active = 0;
399                         for (i = 0; i < numVerts; i++) {
400                                 if (BLI_BITMAP_TEST_BOOL(mask, i)) {
401                                         if (em != NULL) {
402                                                 if (index_array) {
403                                                         index = index_array[i];
404                                                         if (index == ORIGINDEX_NONE) {
405                                                                 continue;
406                                                         }
407                                                 }
408                                                 else {
409                                                         index = i;
410                                                 }
411
412                                                 eve = BM_vert_at_index(em->bm, index);
413                                                 if (BM_elem_flag_test(eve, BM_ELEM_HIDDEN) ||
414                                                     BM_elem_flag_test(eve, BM_ELEM_SELECT))
415                                                 {
416                                                         continue;
417                                                 }
418                                         }
419                                         numVerts_active++;
420                                 }
421                         }
422                 }
423                 else if (!mask) {
424                         numVerts_active = numVerts;
425                 }
426
427                 tree = BLI_bvhtree_new(numVerts_active, epsilon, tree_type, axis);
428
429                 if (tree) {
430                         for (i = 0; i < numVerts; i++) {
431                                 if (mask && !BLI_BITMAP_TEST_BOOL(mask, i)) {
432                                         continue;
433                                 }
434                                 if (em != NULL) {
435                                         if (index_array) {
436                                                 index = index_array[i];
437                                                 if (index == ORIGINDEX_NONE) {
438                                                         continue;
439                                                 }
440                                         }
441                                         else {
442                                                 index = i;
443                                         }
444
445                                         eve = BM_vert_at_index(em->bm, index);
446                                         if (BM_elem_flag_test(eve, BM_ELEM_HIDDEN) ||
447                                             BM_elem_flag_test(eve, BM_ELEM_SELECT))
448                                         {
449                                                 continue;
450                                         }
451                                 }
452                                 BLI_bvhtree_insert(tree, i, vert[i].co, 1);
453                         }
454
455                         BLI_bvhtree_balance(tree);
456                 }
457         }
458
459         return tree;
460 }
461
462 static void bvhtree_from_mesh_verts_setup_data(
463         BVHTreeFromMesh *data, BVHTree *tree, const bool is_cached, float epsilon,
464         MVert *vert, const bool vert_allocated)
465 {
466         memset(data, 0, sizeof(*data));
467
468         if (tree) {
469                 data->tree = tree;
470                 data->cached = is_cached;
471
472                 /* a NULL nearest callback works fine
473                  * remember the min distance to point is the same as the min distance to BV of point */
474                 data->nearest_callback = NULL;
475                 data->raycast_callback = mesh_verts_spherecast;
476                 data->nearest_to_ray_callback = NULL;
477
478                 data->vert = vert;
479                 data->vert_allocated = vert_allocated;
480                 //data->face = DM_get_tessface_array(dm, &data->face_allocated);  /* XXX WHY???? */
481
482                 data->sphere_radius = epsilon;
483         }
484         else {
485                 if (vert_allocated) {
486                         MEM_freeN(vert);
487                 }
488         }
489 }
490
491 /* Builds a bvh tree where nodes are the vertices of the given dm */
492 BVHTree *bvhtree_from_mesh_verts(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis)
493 {
494         BMEditMesh *em = data->em_evil;
495         const int bvhcache_type = em ? BVHTREE_FROM_VERTS_EDITMESH_SNAP : BVHTREE_FROM_VERTS;
496         BVHTree *tree;
497         MVert *vert;
498         bool vert_allocated;
499
500         BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
501         tree = bvhcache_find(&dm->bvhCache, bvhcache_type);
502         BLI_rw_mutex_unlock(&cache_rwlock);
503
504         vert = DM_get_vert_array(dm, &vert_allocated);
505
506         /* Not in cache */
507         if (tree == NULL) {
508                 BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
509                 tree = bvhcache_find(&dm->bvhCache, bvhcache_type);
510                 if (tree == NULL) {
511                         int vert_num, *index_array = NULL;
512                         if (em != NULL) {
513                                 vert_num = em->bm->totvert;
514                                 index_array = dm->getVertDataArray(dm, CD_ORIGINDEX);
515                         }
516                         else {
517                                 vert_num = dm->getNumVerts(dm);
518                                 BLI_assert(vert_num != 0);
519                         }
520                         tree = bvhtree_from_mesh_verts_create_tree(
521                                 epsilon, tree_type, axis,
522                                 em, index_array,
523                                 vert, vert_num, NULL, -1);
524
525                         if (tree) {
526                                 /* Save on cache for later use */
527                                 /* printf("BVHTree built and saved on cache\n"); */
528                                 bvhcache_insert(&dm->bvhCache, tree, bvhcache_type);
529                         }
530                 }
531                 BLI_rw_mutex_unlock(&cache_rwlock);
532         }
533         else {
534                 /* printf("BVHTree is already build, using cached tree\n"); */
535         }
536
537         /* Setup BVHTreeFromMesh */
538         bvhtree_from_mesh_verts_setup_data(data, tree, true, epsilon, vert, vert_allocated);
539
540         return data->tree;
541 }
542
543 /**
544  * Builds a bvh tree where nodes are the given vertices (note: does not copy given mverts!).
545  * \param vert_allocated if true, vert freeing will be done when freeing data.
546  * \param mask if not null, true elements give which vert to add to BVH tree.
547  * \param numVerts_active if >= 0, number of active verts to add to BVH tree (else will be computed from mask).
548  */
549 BVHTree *bvhtree_from_mesh_verts_ex(
550         BVHTreeFromMesh *data, MVert *vert, const int numVerts, const bool vert_allocated,
551         BLI_bitmap *mask, int numVerts_active,
552         float epsilon, int tree_type, int axis)
553 {
554         BVHTree *tree = bvhtree_from_mesh_verts_create_tree(epsilon, tree_type, axis, NULL, NULL, vert, numVerts, mask, numVerts_active);
555
556         /* Setup BVHTreeFromMesh */
557         bvhtree_from_mesh_verts_setup_data(data, tree, false, epsilon, vert, vert_allocated);
558
559         return data->tree;
560 }
561
562 /** \} */
563
564
565 /* -------------------------------------------------------------------- */
566
567 /** \name Edge Builder
568  * \{ */
569
570 /* Builds a bvh tree where nodes are the edges of the given dm */
571 BVHTree *bvhtree_from_mesh_edges(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis)
572 {
573         BVHTree *tree;
574         MVert *vert;
575         MEdge *edge;
576         bool vert_allocated, edge_allocated;
577
578         BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
579         tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_EDGES);
580         BLI_rw_mutex_unlock(&cache_rwlock);
581
582         vert = DM_get_vert_array(dm, &vert_allocated);
583         edge = DM_get_edge_array(dm, &edge_allocated);
584
585         /* Not in cache */
586         if (tree == NULL) {
587                 BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
588                 tree = bvhcache_find(&dm->bvhCache, BVHTREE_FROM_EDGES);
589                 if (tree == NULL) {
590                         int i;
591                         int numEdges = dm->getNumEdges(dm);
592
593                         if (vert != NULL && edge != NULL) {
594                                 /* Create a bvh-tree of the given target */
595                                 tree = BLI_bvhtree_new(numEdges, epsilon, tree_type, axis);
596                                 if (tree != NULL) {
597                                         for (i = 0; i < numEdges; i++) {
598                                                 float co[2][3];
599                                                 copy_v3_v3(co[0], vert[edge[i].v1].co);
600                                                 copy_v3_v3(co[1], vert[edge[i].v2].co);
601
602                                                 BLI_bvhtree_insert(tree, i, co[0], 2);
603                                         }
604                                         BLI_bvhtree_balance(tree);
605
606                                         /* Save on cache for later use */
607                                         /* printf("BVHTree built and saved on cache\n"); */
608                                         bvhcache_insert(&dm->bvhCache, tree, BVHTREE_FROM_EDGES);
609                                 }
610                         }
611                 }
612                 BLI_rw_mutex_unlock(&cache_rwlock);
613         }
614         else {
615                 /* printf("BVHTree is already build, using cached tree\n"); */
616         }
617
618
619         /* Setup BVHTreeFromMesh */
620         memset(data, 0, sizeof(*data));
621         data->tree = tree;
622
623         if (data->tree) {
624                 data->cached = true;
625
626                 data->nearest_callback = mesh_edges_nearest_point;
627                 data->raycast_callback = mesh_edges_spherecast;
628                 data->nearest_to_ray_callback = NULL;
629
630                 data->vert = vert;
631                 data->vert_allocated = vert_allocated;
632                 data->edge = edge;
633                 data->edge_allocated = edge_allocated;
634
635                 data->sphere_radius = epsilon;
636         }
637         else {
638                 if (vert_allocated) {
639                         MEM_freeN(vert);
640                 }
641                 if (edge_allocated) {
642                         MEM_freeN(edge);
643                 }
644         }
645         return data->tree;
646 }
647
648 /** \} */
649
650
651 /* -------------------------------------------------------------------- */
652
653 /** \name Tessellated Face Builder
654  * \{ */
655
656 static BVHTree *bvhtree_from_mesh_faces_create_tree(
657         float epsilon, int tree_type, int axis,
658         BMEditMesh *em, const bool em_all,
659         MVert *vert, MFace *face, const int numFaces,
660         BLI_bitmap *mask, int numFaces_active)
661 {
662         BVHTree *tree = NULL;
663         int i;
664
665         if (numFaces) {
666                 if (mask && numFaces_active < 0) {
667                         numFaces_active = 0;
668                         for (i = 0; i < numFaces; i++) {
669                                 if (BLI_BITMAP_TEST_BOOL(mask, i)) {
670                                         numFaces_active++;
671                                 }
672                         }
673                 }
674                 else if (!mask) {
675                         numFaces_active = numFaces;
676                 }
677
678                 /* Create a bvh-tree of the given target */
679                 /* printf("%s: building BVH, total=%d\n", __func__, numFaces); */
680                 tree = BLI_bvhtree_new(numFaces_active, epsilon, tree_type, axis);
681                 if (tree) {
682                         if (em) {
683                                 const struct BMLoop *(*looptris)[3] = (void *)em->looptris;
684
685                                 /* avoid double-up on face searches for quads-ngons */
686                                 bool insert_prev = false;
687                                 BMFace *f_prev = NULL;
688
689                                 /* data->em_evil is only set for snapping, and only for the mesh of the object
690                                  * which is currently open in edit mode. When set, the bvhtree should not contain
691                                  * faces that will interfere with snapping (e.g. faces that are hidden/selected
692                                  * or faces that have selected verts). */
693
694                                 /* Insert BMesh-tessellation triangles into the bvh tree, unless they are hidden
695                                  * and/or selected. Even if the faces themselves are not selected for the snapped
696                                  * transform, having a vertex selected means the face (and thus it's tessellated
697                                  * triangles) will be moving and will not be a good snap targets. */
698                                 for (i = 0; i < numFaces; i++) {
699                                         const BMLoop **ltri = looptris[i];
700                                         BMFace *f = ltri[0]->f;
701                                         bool insert = mask ? BLI_BITMAP_TEST_BOOL(mask, i) : true;
702
703                                         /* Start with the assumption the triangle should be included for snapping. */
704                                         if (f == f_prev) {
705                                                 insert = insert_prev;
706                                         }
707                                         else if (insert) {
708                                                 if (em_all) {
709                                                         /* pass */
710                                                 }
711                                                 else if (BM_elem_flag_test(f, BM_ELEM_SELECT) || BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
712                                                         /* Don't insert triangles tessellated from faces that are hidden or selected */
713                                                         insert = false;
714                                                 }
715                                                 else {
716                                                         BMLoop *l_iter, *l_first;
717                                                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
718                                                         do {
719                                                                 if (BM_elem_flag_test(l_iter->v, BM_ELEM_SELECT)) {
720                                                                         /* Don't insert triangles tessellated from faces that have any selected verts */
721                                                                         insert = false;
722                                                                         break;
723                                                                 }
724                                                         } while ((l_iter = l_iter->next) != l_first);
725                                                 }
726
727                                                 /* skip if face doesn't change */
728                                                 f_prev = f;
729                                                 insert_prev = insert;
730                                         }
731
732                                         if (insert) {
733                                                 /* No reason found to block hit-testing the triangle for snap, so insert it now.*/
734                                                 float co[3][3];
735                                                 copy_v3_v3(co[0], ltri[0]->v->co);
736                                                 copy_v3_v3(co[1], ltri[1]->v->co);
737                                                 copy_v3_v3(co[2], ltri[2]->v->co);
738
739                                                 BLI_bvhtree_insert(tree, i, co[0], 3);
740                                         }
741                                 }
742                         }
743                         else {
744                                 if (vert && face) {
745                                         for (i = 0; i < numFaces; i++) {
746                                                 float co[4][3];
747                                                 if (mask && !BLI_BITMAP_TEST_BOOL(mask, i)) {
748                                                         continue;
749                                                 }
750
751                                                 copy_v3_v3(co[0], vert[face[i].v1].co);
752                                                 copy_v3_v3(co[1], vert[face[i].v2].co);
753                                                 copy_v3_v3(co[2], vert[face[i].v3].co);
754                                                 if (face[i].v4)
755                                                         copy_v3_v3(co[3], vert[face[i].v4].co);
756
757                                                 BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
758                                         }
759                                 }
760                         }
761                         BLI_bvhtree_balance(tree);
762                 }
763         }
764
765         return tree;
766 }
767
768 static void bvhtree_from_mesh_faces_setup_data(
769         BVHTreeFromMesh *data, BVHTree *tree, const bool is_cached,
770         float epsilon, BMEditMesh *em,
771         MVert *vert, const bool vert_allocated,
772         MFace *face, const bool face_allocated)
773 {
774         memset(data, 0, sizeof(*data));
775         data->em_evil = em;
776
777         if (tree) {
778                 data->tree = tree;
779                 data->cached = is_cached;
780
781                 if (em) {
782                         data->nearest_callback = editmesh_faces_nearest_point;
783                         data->raycast_callback = editmesh_faces_spherecast;
784                         data->nearest_to_ray_callback = NULL;
785                 }
786                 else {
787                         data->nearest_callback = mesh_faces_nearest_point;
788                         data->raycast_callback = mesh_faces_spherecast;
789                         data->nearest_to_ray_callback = NULL;
790
791                         data->vert = vert;
792                         data->vert_allocated = vert_allocated;
793                         data->face = face;
794                         data->face_allocated = face_allocated;
795                 }
796
797                 data->sphere_radius = epsilon;
798         }
799         else {
800                 if (vert_allocated) {
801                         MEM_freeN(vert);
802                 }
803                 if (face_allocated) {
804                         MEM_freeN(face);
805                 }
806         }
807 }
808
809 /* Builds a bvh tree where nodes are the tesselated faces of the given dm */
810 BVHTree *bvhtree_from_mesh_faces(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis)
811 {
812         BMEditMesh *em = data->em_evil;
813         const int bvhcache_type = em ?
814                 (data->em_evil_all ? BVHTREE_FROM_FACES_EDITMESH_ALL : BVHTREE_FROM_FACES_EDITMESH_SNAP) :
815                 BVHTREE_FROM_FACES;
816         BVHTree *tree;
817         MVert *vert = NULL;
818         MFace *face = NULL;
819         bool vert_allocated = false, face_allocated = false;
820
821         BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
822         tree = bvhcache_find(&dm->bvhCache, bvhcache_type);
823         BLI_rw_mutex_unlock(&cache_rwlock);
824
825         if (em == NULL) {
826                 vert = DM_get_vert_array(dm, &vert_allocated);
827                 face = DM_get_tessface_array(dm, &face_allocated);
828         }
829
830         /* Not in cache */
831         if (tree == NULL) {
832                 BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
833                 tree = bvhcache_find(&dm->bvhCache, bvhcache_type);
834                 if (tree == NULL) {
835                         int numFaces;
836
837                         /* BMESH specific check that we have tessfaces,
838                          * we _could_ tessellate here but rather not - campbell
839                          *
840                          * this assert checks we have tessfaces,
841                          * if not caller should use DM_ensure_tessface() */
842                         if (em) {
843                                 numFaces = em->tottri;
844                         }
845                         else {
846                                 numFaces = dm->getNumTessFaces(dm);
847                                 BLI_assert(!(numFaces == 0 && dm->getNumPolys(dm) != 0));
848                         }
849
850                         tree = bvhtree_from_mesh_faces_create_tree(
851                                 epsilon, tree_type, axis,
852                                 em, (bvhcache_type == BVHTREE_FROM_FACES_EDITMESH_ALL),
853                                 vert, face, numFaces, NULL, -1);
854                         if (tree) {
855                                 /* Save on cache for later use */
856                                 /* printf("BVHTree built and saved on cache\n"); */
857                                 bvhcache_insert(&dm->bvhCache, tree, bvhcache_type);
858                         }
859                 }
860                 BLI_rw_mutex_unlock(&cache_rwlock);
861         }
862         else {
863                 /* printf("BVHTree is already build, using cached tree\n"); */
864         }
865
866         /* Setup BVHTreeFromMesh */
867         bvhtree_from_mesh_faces_setup_data(data, tree, true, epsilon, em, vert, vert_allocated, face, face_allocated);
868
869         return data->tree;
870 }
871
872 /**
873  * Builds a bvh tree where nodes are the given tessellated faces (note: does not copy given mfaces!).
874  * \param vert_allocated if true, vert freeing will be done when freeing data.
875  * \param face_allocated if true, face freeing will be done when freeing data.
876  * \param mask if not null, true elements give which faces to add to BVH tree.
877  * \param numFaces_active if >= 0, number of active faces to add to BVH tree (else will be computed from mask).
878  */
879 BVHTree *bvhtree_from_mesh_faces_ex(
880         BVHTreeFromMesh *data, MVert *vert, const bool vert_allocated,
881         MFace *face, const int numFaces, const bool face_allocated,
882         BLI_bitmap *mask, int numFaces_active, float epsilon, int tree_type, int axis)
883 {
884         BVHTree *tree = bvhtree_from_mesh_faces_create_tree(
885                 epsilon, tree_type, axis,
886                 NULL, false,
887                 vert, face, numFaces,
888                 mask, numFaces_active);
889
890         /* Setup BVHTreeFromMesh */
891         bvhtree_from_mesh_faces_setup_data(data, tree, false, epsilon, NULL, vert, vert_allocated, face, face_allocated);
892
893         return data->tree;
894 }
895
896 /** \} */
897
898
899 /* -------------------------------------------------------------------- */
900
901 /** \name LoopTri Face Builder
902  * \{ */
903
904 static BVHTree *bvhtree_from_mesh_looptri_create_tree(
905         float epsilon, int tree_type, int axis,
906         BMEditMesh *em, const bool em_all,
907         const MVert *vert, const MLoop *mloop, const MLoopTri *looptri, const int looptri_num,
908         BLI_bitmap *mask, int looptri_num_active)
909 {
910         BVHTree *tree = NULL;
911         int i;
912
913         if (looptri_num) {
914                 if (mask && looptri_num_active < 0) {
915                         looptri_num_active = 0;
916                         for (i = 0; i < looptri_num; i++) {
917                                 if (BLI_BITMAP_TEST_BOOL(mask, i)) {
918                                         looptri_num_active++;
919                                 }
920                         }
921                 }
922                 else if (!mask) {
923                         looptri_num_active = looptri_num;
924                 }
925
926                 /* Create a bvh-tree of the given target */
927                 /* printf("%s: building BVH, total=%d\n", __func__, numFaces); */
928                 tree = BLI_bvhtree_new(looptri_num_active, epsilon, tree_type, axis);
929                 if (tree) {
930                         if (em) {
931                                 const struct BMLoop *(*looptris)[3] = (void *)em->looptris;
932
933                                 /* avoid double-up on face searches for quads-ngons */
934                                 bool insert_prev = false;
935                                 BMFace *f_prev = NULL;
936
937                                 /* data->em_evil is only set for snapping, and only for the mesh of the object
938                                  * which is currently open in edit mode. When set, the bvhtree should not contain
939                                  * faces that will interfere with snapping (e.g. faces that are hidden/selected
940                                  * or faces that have selected verts). */
941
942                                 /* Insert BMesh-tessellation triangles into the bvh tree, unless they are hidden
943                                  * and/or selected. Even if the faces themselves are not selected for the snapped
944                                  * transform, having a vertex selected means the face (and thus it's tessellated
945                                  * triangles) will be moving and will not be a good snap targets. */
946                                 for (i = 0; i < looptri_num; i++) {
947                                         const BMLoop **ltri = looptris[i];
948                                         BMFace *f = ltri[0]->f;
949                                         bool insert = mask ? BLI_BITMAP_TEST_BOOL(mask, i) : true;
950
951                                         /* Start with the assumption the triangle should be included for snapping. */
952                                         if (f == f_prev) {
953                                                 insert = insert_prev;
954                                         }
955                                         else if (insert) {
956                                                 if (em_all) {
957                                                         /* pass */
958                                                 }
959                                                 else if (BM_elem_flag_test(f, BM_ELEM_SELECT) || BM_elem_flag_test(f, BM_ELEM_HIDDEN)) {
960                                                         /* Don't insert triangles tessellated from faces that are hidden or selected */
961                                                         insert = false;
962                                                 }
963                                                 else {
964                                                         BMLoop *l_iter, *l_first;
965                                                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
966                                                         do {
967                                                                 if (BM_elem_flag_test(l_iter->v, BM_ELEM_SELECT)) {
968                                                                         /* Don't insert triangles tessellated from faces that have any selected verts */
969                                                                         insert = false;
970                                                                         break;
971                                                                 }
972                                                         } while ((l_iter = l_iter->next) != l_first);
973                                                 }
974
975                                                 /* skip if face doesn't change */
976                                                 f_prev = f;
977                                                 insert_prev = insert;
978                                         }
979
980                                         if (insert) {
981                                                 /* No reason found to block hit-testing the triangle for snap, so insert it now.*/
982                                                 float co[3][3];
983                                                 copy_v3_v3(co[0], ltri[0]->v->co);
984                                                 copy_v3_v3(co[1], ltri[1]->v->co);
985                                                 copy_v3_v3(co[2], ltri[2]->v->co);
986
987                                                 BLI_bvhtree_insert(tree, i, co[0], 3);
988                                         }
989                                 }
990                         }
991                         else {
992                                 if (vert && looptri) {
993                                         for (i = 0; i < looptri_num; i++) {
994                                                 float co[3][3];
995                                                 if (mask && !BLI_BITMAP_TEST_BOOL(mask, i)) {
996                                                         continue;
997                                                 }
998
999                                                 copy_v3_v3(co[0], vert[mloop[looptri[i].tri[0]].v].co);
1000                                                 copy_v3_v3(co[1], vert[mloop[looptri[i].tri[1]].v].co);
1001                                                 copy_v3_v3(co[2], vert[mloop[looptri[i].tri[2]].v].co);
1002
1003                                                 BLI_bvhtree_insert(tree, i, co[0], 3);
1004                                         }
1005                                 }
1006                         }
1007                         BLI_bvhtree_balance(tree);
1008                 }
1009         }
1010
1011         return tree;
1012 }
1013
1014 static void bvhtree_from_mesh_looptri_setup_data(
1015         BVHTreeFromMesh *data, BVHTree *tree, const bool is_cached,
1016         float epsilon, BMEditMesh *em,
1017         const MVert *vert, const bool vert_allocated,
1018         const MLoop *mloop, const bool loop_allocated,
1019         const MLoopTri *looptri, const bool looptri_allocated)
1020 {
1021         memset(data, 0, sizeof(*data));
1022         data->em_evil = em;
1023
1024         if (tree) {
1025                 data->tree = tree;
1026                 data->cached = is_cached;
1027
1028                 if (em) {
1029                         data->nearest_callback = editmesh_faces_nearest_point;
1030                         data->raycast_callback = editmesh_faces_spherecast;
1031                         data->nearest_to_ray_callback = NULL;
1032                 }
1033                 else {
1034                         data->nearest_callback = mesh_looptri_nearest_point;
1035                         data->raycast_callback = mesh_looptri_spherecast;
1036                         data->nearest_to_ray_callback = NULL;
1037
1038                         data->vert = vert;
1039                         data->vert_allocated = vert_allocated;
1040                         data->loop = mloop;
1041                         data->loop_allocated = loop_allocated;
1042                         data->looptri = looptri;
1043                         data->looptri_allocated = looptri_allocated;
1044                 }
1045
1046                 data->sphere_radius = epsilon;
1047         }
1048         else {
1049                 if (vert_allocated) {
1050                         MEM_freeN((void *)vert);
1051                 }
1052                 if (loop_allocated) {
1053                         MEM_freeN((void *)mloop);
1054                 }
1055                 if (looptri_allocated) {
1056                         MEM_freeN((void *)looptri);
1057                 }
1058         }
1059 }
1060
1061 /**
1062  * Builds a bvh tree where nodes are the looptri faces of the given dm
1063  *
1064  * \note for editmesh this is currently a duplicate of bvhtree_from_mesh_faces
1065  */
1066 BVHTree *bvhtree_from_mesh_looptri(BVHTreeFromMesh *data, DerivedMesh *dm, float epsilon, int tree_type, int axis)
1067 {
1068         BMEditMesh *em = data->em_evil;
1069         const int bvhcache_type = em ?
1070                 (data->em_evil_all ? BVHTREE_FROM_FACES_EDITMESH_ALL : BVHTREE_FROM_FACES_EDITMESH_SNAP) :
1071                 BVHTREE_FROM_LOOPTRI;
1072         BVHTree *tree;
1073         MVert *mvert = NULL;
1074         MLoop *mloop = NULL;
1075         const MLoopTri *looptri = NULL;
1076         bool vert_allocated = false;
1077         bool loop_allocated = false;
1078         bool looptri_allocated = false;
1079
1080         BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
1081         tree = bvhcache_find(&dm->bvhCache, bvhcache_type);
1082         BLI_rw_mutex_unlock(&cache_rwlock);
1083
1084         if (em == NULL) {
1085                 MPoly *mpoly;
1086                 bool poly_allocated = false;
1087
1088                 mvert = DM_get_vert_array(dm, &vert_allocated);
1089                 mpoly = DM_get_poly_array(dm, &poly_allocated);
1090
1091                 mloop = DM_get_loop_array(dm, &loop_allocated);
1092                 looptri = DM_get_looptri_array(
1093                         dm,
1094                         mvert,
1095                         mpoly, dm->getNumPolys(dm),
1096                         mloop, dm->getNumLoops(dm),
1097                         &looptri_allocated);
1098
1099                 if (poly_allocated) {
1100                         MEM_freeN(mpoly);
1101                 }
1102
1103         }
1104
1105         /* Not in cache */
1106         if (tree == NULL) {
1107                 BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
1108                 tree = bvhcache_find(&dm->bvhCache, bvhcache_type);
1109                 if (tree == NULL) {
1110                         int looptri_num;
1111
1112                         /* BMESH specific check that we have tessfaces,
1113                          * we _could_ tessellate here but rather not - campbell
1114                          *
1115                          * this assert checks we have tessfaces,
1116                          * if not caller should use DM_ensure_tessface() */
1117                         if (em) {
1118                                 looptri_num = em->tottri;
1119                         }
1120                         else {
1121                                 looptri_num = dm->getNumLoopTri(dm);
1122                                 BLI_assert(!(looptri_num == 0 && dm->getNumPolys(dm) != 0));
1123                         }
1124
1125                         tree = bvhtree_from_mesh_looptri_create_tree(
1126                                 epsilon, tree_type, axis,
1127                                 em, (bvhcache_type == BVHTREE_FROM_FACES_EDITMESH_ALL),
1128                                 mvert, mloop, looptri, looptri_num, NULL, -1);
1129                         if (tree) {
1130                                 /* Save on cache for later use */
1131                                 /* printf("BVHTree built and saved on cache\n"); */
1132                                 bvhcache_insert(&dm->bvhCache, tree, bvhcache_type);
1133                         }
1134                 }
1135                 BLI_rw_mutex_unlock(&cache_rwlock);
1136         }
1137         else {
1138                 /* printf("BVHTree is already build, using cached tree\n"); */
1139         }
1140
1141         /* Setup BVHTreeFromMesh */
1142         bvhtree_from_mesh_looptri_setup_data(
1143                 data, tree, true, epsilon, em,
1144                 mvert, vert_allocated,
1145                 mloop, loop_allocated,
1146                 looptri, looptri_allocated);
1147
1148         return data->tree;
1149 }
1150
1151 BVHTree *bvhtree_from_mesh_looptri_ex(
1152         BVHTreeFromMesh *data,
1153         const struct MVert *vert, const bool vert_allocated,
1154         const struct MLoop *mloop, const bool loop_allocated,
1155         const struct MLoopTri *looptri, const int looptri_num, const bool looptri_allocated,
1156         BLI_bitmap *mask, int looptri_num_active,
1157         float epsilon, int tree_type, int axis)
1158 {
1159         BVHTree *tree = bvhtree_from_mesh_looptri_create_tree(
1160                 epsilon, tree_type, axis,
1161                 NULL, false,
1162                 vert, mloop, looptri, looptri_num,
1163                 mask, looptri_num_active);
1164
1165         /* Setup BVHTreeFromMesh */
1166         bvhtree_from_mesh_looptri_setup_data(
1167                 data, tree, false, epsilon, NULL,
1168                 vert, vert_allocated,
1169                 mloop, loop_allocated,
1170                 looptri, looptri_allocated);
1171
1172         return data->tree;
1173 }
1174
1175 /** \} */
1176
1177
1178 /* Frees data allocated by a call to bvhtree_from_mesh_*. */
1179 void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data)
1180 {
1181         if (data->tree) {
1182                 if (!data->cached) {
1183                         BLI_bvhtree_free(data->tree);
1184                 }
1185
1186                 if (data->vert_allocated) {
1187                         MEM_freeN((void *)data->vert);
1188                 }
1189                 if (data->edge_allocated) {
1190                         MEM_freeN((void *)data->edge);
1191                 }
1192                 if (data->face_allocated) {
1193                         MEM_freeN((void *)data->face);
1194                 }
1195                 if (data->loop_allocated) {
1196                         MEM_freeN((void *)data->loop);
1197                 }
1198                 if (data->looptri_allocated) {
1199                         MEM_freeN((void *)data->looptri);
1200                 }
1201
1202                 memset(data, 0, sizeof(*data));
1203         }
1204 }
1205
1206
1207 /* -------------------------------------------------------------------- */
1208
1209 /** \name BVHCache
1210  * \{ */
1211
1212 typedef struct BVHCacheItem {
1213         int type;
1214         BVHTree *tree;
1215
1216 } BVHCacheItem;
1217
1218 static void bvhcacheitem_set_if_match(void *_cached, void *_search)
1219 {
1220         BVHCacheItem *cached = (BVHCacheItem *)_cached;
1221         BVHCacheItem *search = (BVHCacheItem *)_search;
1222
1223         if (search->type == cached->type) {
1224                 search->tree = cached->tree;
1225         }
1226
1227
1228 BVHTree *bvhcache_find(BVHCache *cache, int type)
1229 {
1230         BVHCacheItem item;
1231         item.type = type;
1232         item.tree = NULL;
1233
1234         BLI_linklist_apply(*cache, bvhcacheitem_set_if_match, &item);
1235         return item.tree;
1236 }
1237
1238 void bvhcache_insert(BVHCache *cache, BVHTree *tree, int type)
1239 {
1240         BVHCacheItem *item = NULL;
1241
1242         assert(tree != NULL);
1243         assert(bvhcache_find(cache, type) == NULL);
1244
1245         item = MEM_mallocN(sizeof(BVHCacheItem), "BVHCacheItem");
1246         assert(item != NULL);
1247
1248         item->type = type;
1249         item->tree = tree;
1250
1251         BLI_linklist_prepend(cache, item);
1252 }
1253
1254
1255 void bvhcache_init(BVHCache *cache)
1256 {
1257         *cache = NULL;
1258 }
1259
1260 static void bvhcacheitem_free(void *_item)
1261 {
1262         BVHCacheItem *item = (BVHCacheItem *)_item;
1263
1264         BLI_bvhtree_free(item->tree);
1265         MEM_freeN(item);
1266 }
1267
1268
1269 void bvhcache_free(BVHCache *cache)
1270 {
1271         BLI_linklist_free(*cache, (LinkNodeFreeFP)bvhcacheitem_free);
1272         *cache = NULL;
1273 }
1274
1275 /** \} */