Cleanup: style, use braces for blenkernel
[blender.git] / source / blender / blenkernel / intern / bvhutils.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup bke
22  */
23
24 #include <stdio.h>
25 #include <string.h>
26 #include <math.h>
27 #include <assert.h>
28
29 #include "DNA_mesh_types.h"
30 #include "DNA_meshdata_types.h"
31
32 #include "BLI_utildefines.h"
33 #include "BLI_linklist.h"
34 #include "BLI_math.h"
35 #include "BLI_threads.h"
36
37 #include "BKE_bvhutils.h"
38 #include "BKE_editmesh.h"
39 #include "BKE_mesh.h"
40 #include "BKE_mesh_runtime.h"
41
42 #include "MEM_guardedalloc.h"
43
44 static ThreadRWMutex cache_rwlock = BLI_RWLOCK_INITIALIZER;
45
46 /* -------------------------------------------------------------------- */
47 /** \name Local Callbacks
48  * \{ */
49
50 /* Math stuff for ray casting on mesh faces and for nearest surface */
51
52 float bvhtree_ray_tri_intersection(const BVHTreeRay *ray,
53                                    const float UNUSED(m_dist),
54                                    const float v0[3],
55                                    const float v1[3],
56                                    const float v2[3])
57 {
58   float dist;
59
60 #ifdef USE_KDOPBVH_WATERTIGHT
61   if (isect_ray_tri_watertight_v3(ray->origin, ray->isect_precalc, v0, v1, v2, &dist, NULL))
62 #else
63   if (isect_ray_tri_epsilon_v3(ray->origin, ray->direction, v0, v1, v2, &dist, NULL, FLT_EPSILON))
64 #endif
65   {
66     return dist;
67   }
68
69   return FLT_MAX;
70 }
71
72 float bvhtree_sphereray_tri_intersection(const BVHTreeRay *ray,
73                                          float radius,
74                                          const float m_dist,
75                                          const float v0[3],
76                                          const float v1[3],
77                                          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,
99                                      int index,
100                                      const float co[3],
101                                      BVHTreeNearest *nearest)
102 {
103   const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
104   const MVert *vert = data->vert;
105   const MFace *face = data->face + index;
106
107   const float *t0, *t1, *t2, *t3;
108   t0 = vert[face->v1].co;
109   t1 = vert[face->v2].co;
110   t2 = vert[face->v3].co;
111   t3 = face->v4 ? vert[face->v4].co : NULL;
112
113   do {
114     float nearest_tmp[3], dist_sq;
115
116     closest_on_tri_to_point_v3(nearest_tmp, co, t0, t1, t2);
117     dist_sq = len_squared_v3v3(co, nearest_tmp);
118
119     if (dist_sq < nearest->dist_sq) {
120       nearest->index = index;
121       nearest->dist_sq = dist_sq;
122       copy_v3_v3(nearest->co, nearest_tmp);
123       normal_tri_v3(nearest->no, t0, t1, t2);
124     }
125
126     t1 = t2;
127     t2 = t3;
128     t3 = NULL;
129
130   } while (t2);
131 }
132 /* copy of function above */
133 static void mesh_looptri_nearest_point(void *userdata,
134                                        int index,
135                                        const float co[3],
136                                        BVHTreeNearest *nearest)
137 {
138   const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
139   const MVert *vert = data->vert;
140   const MLoopTri *lt = &data->looptri[index];
141   const float *vtri_co[3] = {
142       vert[data->loop[lt->tri[0]].v].co,
143       vert[data->loop[lt->tri[1]].v].co,
144       vert[data->loop[lt->tri[2]].v].co,
145   };
146   float nearest_tmp[3], dist_sq;
147
148   closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(vtri_co));
149   dist_sq = len_squared_v3v3(co, nearest_tmp);
150
151   if (dist_sq < nearest->dist_sq) {
152     nearest->index = index;
153     nearest->dist_sq = dist_sq;
154     copy_v3_v3(nearest->co, nearest_tmp);
155     normal_tri_v3(nearest->no, UNPACK3(vtri_co));
156   }
157 }
158 /* copy of function above (warning, should de-duplicate with editmesh_bvh.c) */
159 static void editmesh_looptri_nearest_point(void *userdata,
160                                            int index,
161                                            const float co[3],
162                                            BVHTreeNearest *nearest)
163 {
164   const BVHTreeFromEditMesh *data = userdata;
165   BMEditMesh *em = data->em;
166   const BMLoop **ltri = (const BMLoop **)em->looptris[index];
167
168   const float *t0, *t1, *t2;
169   t0 = ltri[0]->v->co;
170   t1 = ltri[1]->v->co;
171   t2 = ltri[2]->v->co;
172
173   {
174     float nearest_tmp[3], dist_sq;
175
176     closest_on_tri_to_point_v3(nearest_tmp, co, t0, t1, t2);
177     dist_sq = len_squared_v3v3(co, nearest_tmp);
178
179     if (dist_sq < nearest->dist_sq) {
180       nearest->index = index;
181       nearest->dist_sq = dist_sq;
182       copy_v3_v3(nearest->co, nearest_tmp);
183       normal_tri_v3(nearest->no, t0, t1, t2);
184     }
185   }
186 }
187
188 /* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_faces.
189  * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
190 static void mesh_faces_spherecast(void *userdata,
191                                   int index,
192                                   const BVHTreeRay *ray,
193                                   BVHTreeRayHit *hit)
194 {
195   const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
196   const MVert *vert = data->vert;
197   const MFace *face = &data->face[index];
198
199   const float *t0, *t1, *t2, *t3;
200   t0 = vert[face->v1].co;
201   t1 = vert[face->v2].co;
202   t2 = vert[face->v3].co;
203   t3 = face->v4 ? vert[face->v4].co : NULL;
204
205   do {
206     float dist;
207     if (ray->radius == 0.0f) {
208       dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
209     }
210     else {
211       dist = bvhtree_sphereray_tri_intersection(ray, ray->radius, hit->dist, t0, t1, t2);
212     }
213
214     if (dist >= 0 && dist < hit->dist) {
215       hit->index = index;
216       hit->dist = dist;
217       madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
218
219       normal_tri_v3(hit->no, t0, t1, t2);
220     }
221
222     t1 = t2;
223     t2 = t3;
224     t3 = NULL;
225
226   } while (t2);
227 }
228 /* copy of function above */
229 static void mesh_looptri_spherecast(void *userdata,
230                                     int index,
231                                     const BVHTreeRay *ray,
232                                     BVHTreeRayHit *hit)
233 {
234   const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
235   const MVert *vert = data->vert;
236   const MLoopTri *lt = &data->looptri[index];
237   const float *vtri_co[3] = {
238       vert[data->loop[lt->tri[0]].v].co,
239       vert[data->loop[lt->tri[1]].v].co,
240       vert[data->loop[lt->tri[2]].v].co,
241   };
242   float dist;
243
244   if (ray->radius == 0.0f) {
245     dist = bvhtree_ray_tri_intersection(ray, hit->dist, UNPACK3(vtri_co));
246   }
247   else {
248     dist = bvhtree_sphereray_tri_intersection(ray, ray->radius, hit->dist, UNPACK3(vtri_co));
249   }
250
251   if (dist >= 0 && dist < hit->dist) {
252     hit->index = index;
253     hit->dist = dist;
254     madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
255
256     normal_tri_v3(hit->no, UNPACK3(vtri_co));
257   }
258 }
259 /* copy of function above (warning, should de-duplicate with editmesh_bvh.c) */
260 static void editmesh_looptri_spherecast(void *userdata,
261                                         int index,
262                                         const BVHTreeRay *ray,
263                                         BVHTreeRayHit *hit)
264 {
265   const BVHTreeFromEditMesh *data = (BVHTreeFromEditMesh *)userdata;
266   BMEditMesh *em = data->em;
267   const BMLoop **ltri = (const BMLoop **)em->looptris[index];
268
269   const float *t0, *t1, *t2;
270   t0 = ltri[0]->v->co;
271   t1 = ltri[1]->v->co;
272   t2 = ltri[2]->v->co;
273
274   {
275     float dist;
276     if (ray->radius == 0.0f) {
277       dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
278     }
279     else {
280       dist = bvhtree_sphereray_tri_intersection(ray, ray->radius, hit->dist, t0, t1, t2);
281     }
282
283     if (dist >= 0 && dist < hit->dist) {
284       hit->index = index;
285       hit->dist = dist;
286       madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
287
288       normal_tri_v3(hit->no, t0, t1, t2);
289     }
290   }
291 }
292
293 /* Callback to bvh tree nearest point. The tree must have been built using bvhtree_from_mesh_edges.
294  * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
295 static void mesh_edges_nearest_point(void *userdata,
296                                      int index,
297                                      const float co[3],
298                                      BVHTreeNearest *nearest)
299 {
300   const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
301   const MVert *vert = data->vert;
302   const MEdge *edge = data->edge + index;
303   float nearest_tmp[3], dist_sq;
304
305   const float *t0, *t1;
306   t0 = vert[edge->v1].co;
307   t1 = vert[edge->v2].co;
308
309   closest_to_line_segment_v3(nearest_tmp, co, t0, t1);
310   dist_sq = len_squared_v3v3(nearest_tmp, co);
311
312   if (dist_sq < nearest->dist_sq) {
313     nearest->index = index;
314     nearest->dist_sq = dist_sq;
315     copy_v3_v3(nearest->co, nearest_tmp);
316     sub_v3_v3v3(nearest->no, t0, t1);
317     normalize_v3(nearest->no);
318   }
319 }
320
321 /* Helper, does all the point-spherecast work actually. */
322 static void mesh_verts_spherecast_do(int index,
323                                      const float v[3],
324                                      const BVHTreeRay *ray,
325                                      BVHTreeRayHit *hit)
326 {
327   float dist;
328   const float *r1;
329   float r2[3], i1[3];
330   r1 = ray->origin;
331   add_v3_v3v3(r2, r1, ray->direction);
332
333   closest_to_line_segment_v3(i1, v, r1, r2);
334
335   /* No hit if closest point is 'behind' the origin of the ray, or too far away from it. */
336   if ((dot_v3v3v3(r1, i1, r2) >= 0.0f) && ((dist = len_v3v3(r1, i1)) < hit->dist)) {
337     hit->index = index;
338     hit->dist = dist;
339     copy_v3_v3(hit->co, i1);
340   }
341 }
342
343 static void editmesh_verts_spherecast(void *userdata,
344                                       int index,
345                                       const BVHTreeRay *ray,
346                                       BVHTreeRayHit *hit)
347 {
348   const BVHTreeFromEditMesh *data = userdata;
349   BMVert *eve = BM_vert_at_index(data->em->bm, index);
350
351   mesh_verts_spherecast_do(index, eve->co, ray, hit);
352 }
353
354 /* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_verts.
355  * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
356 static void mesh_verts_spherecast(void *userdata,
357                                   int index,
358                                   const BVHTreeRay *ray,
359                                   BVHTreeRayHit *hit)
360 {
361   const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
362   const float *v = data->vert[index].co;
363
364   mesh_verts_spherecast_do(index, v, ray, hit);
365 }
366
367 /* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_edges.
368  * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
369 static void mesh_edges_spherecast(void *userdata,
370                                   int index,
371                                   const BVHTreeRay *ray,
372                                   BVHTreeRayHit *hit)
373 {
374   const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
375   const MVert *vert = data->vert;
376   const MEdge *edge = &data->edge[index];
377
378   const float radius_sq = SQUARE(ray->radius);
379   float dist;
380   const float *v1, *v2, *r1;
381   float r2[3], i1[3], i2[3];
382   v1 = vert[edge->v1].co;
383   v2 = vert[edge->v2].co;
384
385   /* In case we get a zero-length edge, handle it as a point! */
386   if (equals_v3v3(v1, v2)) {
387     mesh_verts_spherecast_do(index, v1, ray, hit);
388     return;
389   }
390
391   r1 = ray->origin;
392   add_v3_v3v3(r2, r1, ray->direction);
393
394   if (isect_line_line_v3(v1, v2, r1, r2, i1, i2)) {
395     /* No hit if intersection point is 'behind' the origin of the ray, or too far away from it. */
396     if ((dot_v3v3v3(r1, i2, r2) >= 0.0f) && ((dist = len_v3v3(r1, i2)) < hit->dist)) {
397       const float e_fac = line_point_factor_v3(i1, v1, v2);
398       if (e_fac < 0.0f) {
399         copy_v3_v3(i1, v1);
400       }
401       else if (e_fac > 1.0f) {
402         copy_v3_v3(i1, v2);
403       }
404       /* Ensure ray is really close enough from edge! */
405       if (len_squared_v3v3(i1, i2) <= radius_sq) {
406         hit->index = index;
407         hit->dist = dist;
408         copy_v3_v3(hit->co, i2);
409       }
410     }
411   }
412 }
413
414 /** \} */
415
416 /*
417  * BVH builders
418  */
419
420 /* -------------------------------------------------------------------- */
421 /** \name Vertex Builder
422  * \{ */
423
424 static BVHTree *bvhtree_from_editmesh_verts_create_tree(float epsilon,
425                                                         int tree_type,
426                                                         int axis,
427                                                         BMEditMesh *em,
428                                                         const int verts_num,
429                                                         const BLI_bitmap *verts_mask,
430                                                         int verts_num_active)
431 {
432   BM_mesh_elem_table_ensure(em->bm, BM_VERT);
433   if (verts_mask) {
434     BLI_assert(IN_RANGE_INCL(verts_num_active, 0, verts_num));
435   }
436   else {
437     verts_num_active = verts_num;
438   }
439
440   BVHTree *tree = BLI_bvhtree_new(verts_num_active, epsilon, tree_type, axis);
441
442   if (tree) {
443     for (int i = 0; i < verts_num; i++) {
444       if (verts_mask && !BLI_BITMAP_TEST_BOOL(verts_mask, i)) {
445         continue;
446       }
447       BMVert *eve = BM_vert_at_index(em->bm, i);
448       BLI_bvhtree_insert(tree, i, eve->co, 1);
449     }
450     BLI_assert(BLI_bvhtree_get_len(tree) == verts_num_active);
451     BLI_bvhtree_balance(tree);
452   }
453
454   return tree;
455 }
456
457 static BVHTree *bvhtree_from_mesh_verts_create_tree(float epsilon,
458                                                     int tree_type,
459                                                     int axis,
460                                                     const MVert *vert,
461                                                     const int verts_num,
462                                                     const BLI_bitmap *verts_mask,
463                                                     int verts_num_active)
464 {
465   BVHTree *tree = NULL;
466
467   if (verts_mask) {
468     BLI_assert(IN_RANGE_INCL(verts_num_active, 0, verts_num));
469   }
470   else {
471     verts_num_active = verts_num;
472   }
473
474   if (verts_num_active) {
475     tree = BLI_bvhtree_new(verts_num_active, epsilon, tree_type, axis);
476
477     if (tree) {
478       for (int i = 0; i < verts_num; i++) {
479         if (verts_mask && !BLI_BITMAP_TEST_BOOL(verts_mask, i)) {
480           continue;
481         }
482         BLI_bvhtree_insert(tree, i, vert[i].co, 1);
483       }
484       BLI_assert(BLI_bvhtree_get_len(tree) == verts_num_active);
485       BLI_bvhtree_balance(tree);
486     }
487   }
488
489   return tree;
490 }
491
492 static void bvhtree_from_mesh_verts_setup_data(BVHTreeFromMesh *data,
493                                                BVHTree *tree,
494                                                const bool is_cached,
495                                                const MVert *vert,
496                                                const bool vert_allocated)
497 {
498   memset(data, 0, sizeof(*data));
499
500   data->tree = tree;
501   data->cached = is_cached;
502
503   /* a NULL nearest callback works fine
504    * remember the min distance to point is the same as the min distance to BV of point */
505   data->nearest_callback = NULL;
506   data->raycast_callback = mesh_verts_spherecast;
507
508   data->vert = vert;
509   data->vert_allocated = vert_allocated;
510 }
511
512 /* Builds a bvh tree where nodes are the vertices of the given em */
513 BVHTree *bvhtree_from_editmesh_verts_ex(BVHTreeFromEditMesh *data,
514                                         BMEditMesh *em,
515                                         const BLI_bitmap *verts_mask,
516                                         int verts_num_active,
517                                         float epsilon,
518                                         int tree_type,
519                                         int axis)
520 {
521   BVHTree *tree = bvhtree_from_editmesh_verts_create_tree(
522       epsilon, tree_type, axis, em, em->bm->totvert, verts_mask, verts_num_active);
523
524   if (tree) {
525     memset(data, 0, sizeof(*data));
526     data->tree = tree;
527     data->em = em;
528     data->nearest_callback = NULL;
529     data->raycast_callback = editmesh_verts_spherecast;
530   }
531
532   return tree;
533 }
534
535 BVHTree *bvhtree_from_editmesh_verts(BVHTreeFromEditMesh *data,
536                                      BMEditMesh *em,
537                                      float epsilon,
538                                      int tree_type,
539                                      int axis,
540                                      BVHCache **bvh_cache)
541 {
542   if (bvh_cache) {
543     BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
544     data->cached = bvhcache_find(*bvh_cache, BVHTREE_FROM_EM_VERTS, &data->tree);
545     BLI_rw_mutex_unlock(&cache_rwlock);
546
547     if (data->cached == false) {
548       BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
549       data->cached = bvhcache_find(*bvh_cache, BVHTREE_FROM_EM_VERTS, &data->tree);
550       if (data->cached == false) {
551         data->tree = bvhtree_from_editmesh_verts_ex(data, em, NULL, -1, epsilon, tree_type, axis);
552
553         /* Save on cache for later use */
554         /* printf("BVHTree built and saved on cache\n"); */
555         bvhcache_insert(bvh_cache, data->tree, BVHTREE_FROM_EM_VERTS);
556       }
557       BLI_rw_mutex_unlock(&cache_rwlock);
558     }
559   }
560   else {
561     data->tree = bvhtree_from_editmesh_verts_ex(data, em, NULL, -1, epsilon, tree_type, axis);
562   }
563
564   return data->tree;
565 }
566
567 /**
568  * Builds a bvh tree where nodes are the given vertices (note: does not copy given mverts!).
569  * \param vert_allocated: if true, vert freeing will be done when freeing data.
570  * \param verts_mask: if not null, true elements give which vert to add to BVH tree.
571  * \param verts_num_active: if >= 0, number of active verts to add to BVH tree (else will be computed from mask).
572  */
573 BVHTree *bvhtree_from_mesh_verts_ex(BVHTreeFromMesh *data,
574                                     const MVert *vert,
575                                     const int verts_num,
576                                     const bool vert_allocated,
577                                     const BLI_bitmap *verts_mask,
578                                     int verts_num_active,
579                                     float epsilon,
580                                     int tree_type,
581                                     int axis)
582 {
583   BVHTree *tree = bvhtree_from_mesh_verts_create_tree(
584       epsilon, tree_type, axis, vert, verts_num, verts_mask, verts_num_active);
585
586   /* Setup BVHTreeFromMesh */
587   bvhtree_from_mesh_verts_setup_data(data, tree, false, vert, vert_allocated);
588
589   return tree;
590 }
591
592 /** \} */
593
594 /* -------------------------------------------------------------------- */
595 /** \name Edge Builder
596  * \{ */
597
598 static BVHTree *bvhtree_from_editmesh_edges_create_tree(float epsilon,
599                                                         int tree_type,
600                                                         int axis,
601                                                         BMEditMesh *em,
602                                                         const int edges_num,
603                                                         const BLI_bitmap *edges_mask,
604                                                         int edges_num_active)
605 {
606   BM_mesh_elem_table_ensure(em->bm, BM_EDGE);
607   if (edges_mask) {
608     BLI_assert(IN_RANGE_INCL(edges_num_active, 0, edges_num));
609   }
610   else {
611     edges_num_active = edges_num;
612   }
613
614   BVHTree *tree = BLI_bvhtree_new(edges_num_active, epsilon, tree_type, axis);
615
616   if (tree) {
617     int i;
618     BMIter iter;
619     BMEdge *eed;
620     BM_ITER_MESH_INDEX (eed, &iter, em->bm, BM_EDGES_OF_MESH, i) {
621       if (edges_mask && !BLI_BITMAP_TEST_BOOL(edges_mask, i)) {
622         continue;
623       }
624       float co[2][3];
625       copy_v3_v3(co[0], eed->v1->co);
626       copy_v3_v3(co[1], eed->v2->co);
627
628       BLI_bvhtree_insert(tree, i, co[0], 2);
629     }
630     BLI_assert(BLI_bvhtree_get_len(tree) == edges_num_active);
631     BLI_bvhtree_balance(tree);
632   }
633
634   return tree;
635 }
636
637 static BVHTree *bvhtree_from_mesh_edges_create_tree(const MVert *vert,
638                                                     const MEdge *edge,
639                                                     const int edge_num,
640                                                     const BLI_bitmap *edges_mask,
641                                                     int edges_num_active,
642                                                     float epsilon,
643                                                     int tree_type,
644                                                     int axis)
645 {
646   BVHTree *tree = NULL;
647
648   if (edges_mask) {
649     BLI_assert(IN_RANGE_INCL(edges_num_active, 0, edge_num));
650   }
651   else {
652     edges_num_active = edge_num;
653   }
654
655   if (edges_num_active) {
656     /* Create a bvh-tree of the given target */
657     tree = BLI_bvhtree_new(edges_num_active, epsilon, tree_type, axis);
658     if (tree) {
659       for (int i = 0; i < edge_num; i++) {
660         if (edges_mask && !BLI_BITMAP_TEST_BOOL(edges_mask, i)) {
661           continue;
662         }
663         float co[2][3];
664         copy_v3_v3(co[0], vert[edge[i].v1].co);
665         copy_v3_v3(co[1], vert[edge[i].v2].co);
666
667         BLI_bvhtree_insert(tree, i, co[0], 2);
668       }
669       BLI_bvhtree_balance(tree);
670     }
671   }
672
673   return tree;
674 }
675
676 static void bvhtree_from_mesh_edges_setup_data(BVHTreeFromMesh *data,
677                                                BVHTree *tree,
678                                                const bool is_cached,
679                                                const MVert *vert,
680                                                const bool vert_allocated,
681                                                const MEdge *edge,
682                                                const bool edge_allocated)
683 {
684   memset(data, 0, sizeof(*data));
685
686   data->tree = tree;
687
688   data->cached = is_cached;
689
690   data->nearest_callback = mesh_edges_nearest_point;
691   data->raycast_callback = mesh_edges_spherecast;
692
693   data->vert = vert;
694   data->vert_allocated = vert_allocated;
695   data->edge = edge;
696   data->edge_allocated = edge_allocated;
697 }
698
699 /* Builds a bvh tree where nodes are the edges of the given em */
700 BVHTree *bvhtree_from_editmesh_edges_ex(BVHTreeFromEditMesh *data,
701                                         BMEditMesh *em,
702                                         const BLI_bitmap *edges_mask,
703                                         int edges_num_active,
704                                         float epsilon,
705                                         int tree_type,
706                                         int axis)
707 {
708   int edge_num = em->bm->totedge;
709
710   BVHTree *tree = bvhtree_from_editmesh_edges_create_tree(
711       epsilon, tree_type, axis, em, edge_num, edges_mask, edges_num_active);
712
713   if (tree) {
714     memset(data, 0, sizeof(*data));
715     data->tree = tree;
716     data->em = em;
717     data->nearest_callback = NULL; /* TODO */
718     data->raycast_callback = NULL; /* TODO */
719   }
720
721   return tree;
722 }
723
724 BVHTree *bvhtree_from_editmesh_edges(BVHTreeFromEditMesh *data,
725                                      BMEditMesh *em,
726                                      float epsilon,
727                                      int tree_type,
728                                      int axis,
729                                      BVHCache **bvh_cache)
730 {
731   if (bvh_cache) {
732     BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
733     data->cached = bvhcache_find(*bvh_cache, BVHTREE_FROM_EM_EDGES, &data->tree);
734     BLI_rw_mutex_unlock(&cache_rwlock);
735
736     if (data->cached == false) {
737       BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
738       data->cached = bvhcache_find(*bvh_cache, BVHTREE_FROM_EM_EDGES, &data->tree);
739       if (data->cached == false) {
740         data->tree = bvhtree_from_editmesh_edges_ex(data, em, NULL, -1, epsilon, tree_type, axis);
741
742         /* Save on cache for later use */
743         /* printf("BVHTree built and saved on cache\n"); */
744         bvhcache_insert(bvh_cache, data->tree, BVHTREE_FROM_EM_EDGES);
745       }
746       BLI_rw_mutex_unlock(&cache_rwlock);
747     }
748   }
749   else {
750     data->tree = bvhtree_from_editmesh_edges_ex(data, em, NULL, -1, epsilon, tree_type, axis);
751   }
752
753   return data->tree;
754 }
755
756 /**
757  * Builds a bvh tree where nodes are the given edges .
758  * \param vert, vert_allocated: if true, elem freeing will be done when freeing data.
759  * \param edge, edge_allocated: if true, elem freeing will be done when freeing data.
760  * \param edges_mask: if not null, true elements give which vert to add to BVH tree.
761  * \param edges_num_active: if >= 0, number of active edges to add to BVH tree (else will be computed from mask).
762  */
763 BVHTree *bvhtree_from_mesh_edges_ex(BVHTreeFromMesh *data,
764                                     const MVert *vert,
765                                     const bool vert_allocated,
766                                     const MEdge *edge,
767                                     const int edges_num,
768                                     const bool edge_allocated,
769                                     const BLI_bitmap *edges_mask,
770                                     int edges_num_active,
771                                     float epsilon,
772                                     int tree_type,
773                                     int axis)
774 {
775   BVHTree *tree = bvhtree_from_mesh_edges_create_tree(
776       vert, edge, edges_num, edges_mask, edges_num_active, epsilon, tree_type, axis);
777
778   /* Setup BVHTreeFromMesh */
779   bvhtree_from_mesh_edges_setup_data(
780       data, tree, false, vert, vert_allocated, edge, edge_allocated);
781
782   return tree;
783 }
784
785 /** \} */
786
787 /* -------------------------------------------------------------------- */
788 /** \name Tessellated Face Builder
789  * \{ */
790
791 static BVHTree *bvhtree_from_mesh_faces_create_tree(float epsilon,
792                                                     int tree_type,
793                                                     int axis,
794                                                     const MVert *vert,
795                                                     const MFace *face,
796                                                     const int faces_num,
797                                                     const BLI_bitmap *faces_mask,
798                                                     int faces_num_active)
799 {
800   BVHTree *tree = NULL;
801   int i;
802
803   if (faces_num) {
804     if (faces_mask) {
805       BLI_assert(IN_RANGE_INCL(faces_num_active, 0, faces_num));
806     }
807     else {
808       faces_num_active = faces_num;
809     }
810
811     /* Create a bvh-tree of the given target */
812     /* printf("%s: building BVH, total=%d\n", __func__, numFaces); */
813     tree = BLI_bvhtree_new(faces_num_active, epsilon, tree_type, axis);
814     if (tree) {
815       if (vert && face) {
816         for (i = 0; i < faces_num; i++) {
817           float co[4][3];
818           if (faces_mask && !BLI_BITMAP_TEST_BOOL(faces_mask, i)) {
819             continue;
820           }
821
822           copy_v3_v3(co[0], vert[face[i].v1].co);
823           copy_v3_v3(co[1], vert[face[i].v2].co);
824           copy_v3_v3(co[2], vert[face[i].v3].co);
825           if (face[i].v4) {
826             copy_v3_v3(co[3], vert[face[i].v4].co);
827           }
828
829           BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
830         }
831       }
832       BLI_assert(BLI_bvhtree_get_len(tree) == faces_num_active);
833       BLI_bvhtree_balance(tree);
834     }
835   }
836
837   return tree;
838 }
839
840 static void bvhtree_from_mesh_faces_setup_data(BVHTreeFromMesh *data,
841                                                BVHTree *tree,
842                                                const bool is_cached,
843                                                const MVert *vert,
844                                                const bool vert_allocated,
845                                                const MFace *face,
846                                                const bool face_allocated)
847 {
848   memset(data, 0, sizeof(*data));
849
850   data->tree = tree;
851   data->cached = is_cached;
852
853   data->nearest_callback = mesh_faces_nearest_point;
854   data->raycast_callback = mesh_faces_spherecast;
855
856   data->vert = vert;
857   data->vert_allocated = vert_allocated;
858   data->face = face;
859   data->face_allocated = face_allocated;
860 }
861
862 /**
863  * Builds a bvh tree where nodes are the given tessellated faces (note: does not copy given mfaces!).
864  * \param vert_allocated: if true, vert freeing will be done when freeing data.
865  * \param face_allocated: if true, face freeing will be done when freeing data.
866  * \param faces_mask: if not null, true elements give which faces to add to BVH tree.
867  * \param faces_num_active: if >= 0, number of active faces to add to BVH tree (else will be computed from mask).
868  */
869 BVHTree *bvhtree_from_mesh_faces_ex(BVHTreeFromMesh *data,
870                                     const MVert *vert,
871                                     const bool vert_allocated,
872                                     const MFace *face,
873                                     const int numFaces,
874                                     const bool face_allocated,
875                                     const BLI_bitmap *faces_mask,
876                                     int faces_num_active,
877                                     float epsilon,
878                                     int tree_type,
879                                     int axis)
880 {
881   BVHTree *tree = bvhtree_from_mesh_faces_create_tree(
882       epsilon, tree_type, axis, vert, face, numFaces, faces_mask, faces_num_active);
883
884   /* Setup BVHTreeFromMesh */
885   bvhtree_from_mesh_faces_setup_data(
886       data, tree, false, vert, vert_allocated, face, face_allocated);
887
888   return tree;
889 }
890
891 /** \} */
892
893 /* -------------------------------------------------------------------- */
894 /** \name LoopTri Face Builder
895  * \{ */
896
897 static BVHTree *bvhtree_from_editmesh_looptri_create_tree(float epsilon,
898                                                           int tree_type,
899                                                           int axis,
900                                                           BMEditMesh *em,
901                                                           const int looptri_num,
902                                                           const BLI_bitmap *looptri_mask,
903                                                           int looptri_num_active)
904 {
905   BVHTree *tree = NULL;
906   int i;
907
908   if (looptri_num) {
909     if (looptri_mask) {
910       BLI_assert(IN_RANGE_INCL(looptri_num_active, 0, looptri_num));
911     }
912     else {
913       looptri_num_active = looptri_num;
914     }
915
916     /* Create a bvh-tree of the given target */
917     /* printf("%s: building BVH, total=%d\n", __func__, numFaces); */
918     tree = BLI_bvhtree_new(looptri_num_active, epsilon, tree_type, axis);
919     if (tree) {
920       if (em) {
921         const struct BMLoop *(*looptris)[3] = (void *)em->looptris;
922
923         /* Insert BMesh-tessellation triangles into the bvh tree, unless they are hidden
924          * and/or selected. Even if the faces themselves are not selected for the snapped
925          * transform, having a vertex selected means the face (and thus it's tessellated
926          * triangles) will be moving and will not be a good snap targets. */
927         for (i = 0; i < looptri_num; i++) {
928           const BMLoop **ltri = looptris[i];
929           bool insert = looptri_mask ? BLI_BITMAP_TEST_BOOL(looptri_mask, i) : true;
930
931           if (insert) {
932             /* No reason found to block hit-testing the triangle for snap, so insert it now.*/
933             float co[3][3];
934             copy_v3_v3(co[0], ltri[0]->v->co);
935             copy_v3_v3(co[1], ltri[1]->v->co);
936             copy_v3_v3(co[2], ltri[2]->v->co);
937
938             BLI_bvhtree_insert(tree, i, co[0], 3);
939           }
940         }
941       }
942       BLI_assert(BLI_bvhtree_get_len(tree) == looptri_num_active);
943       BLI_bvhtree_balance(tree);
944     }
945   }
946
947   return tree;
948 }
949
950 static BVHTree *bvhtree_from_mesh_looptri_create_tree(float epsilon,
951                                                       int tree_type,
952                                                       int axis,
953                                                       const MVert *vert,
954                                                       const MLoop *mloop,
955                                                       const MLoopTri *looptri,
956                                                       const int looptri_num,
957                                                       const BLI_bitmap *looptri_mask,
958                                                       int looptri_num_active)
959 {
960   BVHTree *tree = NULL;
961
962   if (looptri_mask) {
963     BLI_assert(IN_RANGE_INCL(looptri_num_active, 0, looptri_num));
964   }
965   else {
966     looptri_num_active = looptri_num;
967   }
968
969   if (looptri_num_active) {
970     /* Create a bvh-tree of the given target */
971     /* printf("%s: building BVH, total=%d\n", __func__, numFaces); */
972     tree = BLI_bvhtree_new(looptri_num_active, epsilon, tree_type, axis);
973     if (tree) {
974       if (vert && looptri) {
975         for (int i = 0; i < looptri_num; i++) {
976           float co[3][3];
977           if (looptri_mask && !BLI_BITMAP_TEST_BOOL(looptri_mask, i)) {
978             continue;
979           }
980
981           copy_v3_v3(co[0], vert[mloop[looptri[i].tri[0]].v].co);
982           copy_v3_v3(co[1], vert[mloop[looptri[i].tri[1]].v].co);
983           copy_v3_v3(co[2], vert[mloop[looptri[i].tri[2]].v].co);
984
985           BLI_bvhtree_insert(tree, i, co[0], 3);
986         }
987       }
988       BLI_assert(BLI_bvhtree_get_len(tree) == looptri_num_active);
989       BLI_bvhtree_balance(tree);
990     }
991   }
992
993   return tree;
994 }
995
996 static void bvhtree_from_mesh_looptri_setup_data(BVHTreeFromMesh *data,
997                                                  BVHTree *tree,
998                                                  const bool is_cached,
999                                                  const MVert *vert,
1000                                                  const bool vert_allocated,
1001                                                  const MLoop *mloop,
1002                                                  const bool loop_allocated,
1003                                                  const MLoopTri *looptri,
1004                                                  const bool looptri_allocated)
1005 {
1006   memset(data, 0, sizeof(*data));
1007
1008   data->tree = tree;
1009   data->cached = is_cached;
1010
1011   data->nearest_callback = mesh_looptri_nearest_point;
1012   data->raycast_callback = mesh_looptri_spherecast;
1013
1014   data->vert = vert;
1015   data->vert_allocated = vert_allocated;
1016   data->loop = mloop;
1017   data->loop_allocated = loop_allocated;
1018   data->looptri = looptri;
1019   data->looptri_allocated = looptri_allocated;
1020 }
1021
1022 /**
1023  * Builds a bvh tree where nodes are the looptri faces of the given bm
1024  */
1025 BVHTree *bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh *data,
1026                                           BMEditMesh *em,
1027                                           const BLI_bitmap *looptri_mask,
1028                                           int looptri_num_active,
1029                                           float epsilon,
1030                                           int tree_type,
1031                                           int axis,
1032                                           BVHCache **bvhCache)
1033 {
1034   /* BMESH specific check that we have tessfaces,
1035    * we _could_ tessellate here but rather not - campbell */
1036
1037   BVHTree *tree = NULL;
1038   if (bvhCache) {
1039     BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
1040     bool in_cache = bvhcache_find(*bvhCache, BVHTREE_FROM_EM_LOOPTRI, &tree);
1041     BLI_rw_mutex_unlock(&cache_rwlock);
1042     if (in_cache == false) {
1043       BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
1044       in_cache = bvhcache_find(*bvhCache, BVHTREE_FROM_EM_LOOPTRI, &tree);
1045       if (in_cache == false) {
1046         tree = bvhtree_from_editmesh_looptri_create_tree(
1047             epsilon, tree_type, axis, em, em->tottri, looptri_mask, looptri_num_active);
1048
1049         /* Save on cache for later use */
1050         /* printf("BVHTree built and saved on cache\n"); */
1051         bvhcache_insert(bvhCache, tree, BVHTREE_FROM_EM_LOOPTRI);
1052       }
1053       BLI_rw_mutex_unlock(&cache_rwlock);
1054     }
1055   }
1056   else {
1057     tree = bvhtree_from_editmesh_looptri_create_tree(
1058         epsilon, tree_type, axis, em, em->tottri, looptri_mask, looptri_num_active);
1059   }
1060
1061   if (tree) {
1062     data->tree = tree;
1063     data->nearest_callback = editmesh_looptri_nearest_point;
1064     data->raycast_callback = editmesh_looptri_spherecast;
1065     data->em = em;
1066     data->cached = bvhCache != NULL;
1067   }
1068   return tree;
1069 }
1070
1071 BVHTree *bvhtree_from_editmesh_looptri(BVHTreeFromEditMesh *data,
1072                                        BMEditMesh *em,
1073                                        float epsilon,
1074                                        int tree_type,
1075                                        int axis,
1076                                        BVHCache **bvhCache)
1077 {
1078   return bvhtree_from_editmesh_looptri_ex(data, em, NULL, -1, epsilon, tree_type, axis, bvhCache);
1079 }
1080
1081 /**
1082  * Builds a bvh tree where nodes are the looptri faces of the given dm
1083  *
1084  * \note for editmesh this is currently a duplicate of bvhtree_from_mesh_faces_ex
1085  */
1086 BVHTree *bvhtree_from_mesh_looptri_ex(BVHTreeFromMesh *data,
1087                                       const struct MVert *vert,
1088                                       const bool vert_allocated,
1089                                       const struct MLoop *mloop,
1090                                       const bool loop_allocated,
1091                                       const struct MLoopTri *looptri,
1092                                       const int looptri_num,
1093                                       const bool looptri_allocated,
1094                                       const BLI_bitmap *looptri_mask,
1095                                       int looptri_num_active,
1096                                       float epsilon,
1097                                       int tree_type,
1098                                       int axis)
1099 {
1100   BVHTree *tree = bvhtree_from_mesh_looptri_create_tree(epsilon,
1101                                                         tree_type,
1102                                                         axis,
1103                                                         vert,
1104                                                         mloop,
1105                                                         looptri,
1106                                                         looptri_num,
1107                                                         looptri_mask,
1108                                                         looptri_num_active);
1109
1110   /* Setup BVHTreeFromMesh */
1111   bvhtree_from_mesh_looptri_setup_data(
1112       data, tree, false, vert, vert_allocated, mloop, loop_allocated, looptri, looptri_allocated);
1113
1114   return tree;
1115 }
1116
1117 static BLI_bitmap *loose_verts_map_get(const MEdge *medge,
1118                                        int edges_num,
1119                                        const MVert *UNUSED(mvert),
1120                                        int verts_num,
1121                                        int *r_loose_vert_num)
1122 {
1123   BLI_bitmap *loose_verts_mask = BLI_BITMAP_NEW(verts_num, __func__);
1124   BLI_bitmap_set_all(loose_verts_mask, true, verts_num);
1125
1126   const MEdge *e = medge;
1127   int num_linked_verts = 0;
1128   for (; edges_num--; e++) {
1129     if (BLI_BITMAP_TEST(loose_verts_mask, e->v1)) {
1130       BLI_BITMAP_DISABLE(loose_verts_mask, e->v1);
1131       num_linked_verts++;
1132     }
1133     if (BLI_BITMAP_TEST(loose_verts_mask, e->v2)) {
1134       BLI_BITMAP_DISABLE(loose_verts_mask, e->v2);
1135       num_linked_verts++;
1136     }
1137   }
1138
1139   *r_loose_vert_num = verts_num - num_linked_verts;
1140
1141   return loose_verts_mask;
1142 }
1143
1144 static BLI_bitmap *loose_edges_map_get(const MEdge *medge,
1145                                        const int edges_len,
1146                                        int *r_loose_edge_len)
1147 {
1148   BLI_bitmap *loose_edges_mask = BLI_BITMAP_NEW(edges_len, __func__);
1149
1150   int loose_edges_len = 0;
1151   const MEdge *e = medge;
1152   for (int i = 0; i < edges_len; i++, e++) {
1153     if (e->flag & ME_LOOSEEDGE) {
1154       BLI_BITMAP_ENABLE(loose_edges_mask, i);
1155       loose_edges_len++;
1156     }
1157     else {
1158       BLI_BITMAP_DISABLE(loose_edges_mask, i);
1159     }
1160   }
1161
1162   *r_loose_edge_len = loose_edges_len;
1163
1164   return loose_edges_mask;
1165 }
1166
1167 /**
1168  * Builds or queries a bvhcache for the cache bvhtree of the request type.
1169  */
1170 BVHTree *BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data,
1171                                    struct Mesh *mesh,
1172                                    const int type,
1173                                    const int tree_type)
1174 {
1175   struct BVHTreeFromMesh data_cp = {0};
1176
1177   BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
1178   data_cp.cached = bvhcache_find(mesh->runtime.bvh_cache, type, &data_cp.tree);
1179   BLI_rw_mutex_unlock(&cache_rwlock);
1180
1181   if (data_cp.cached && data_cp.tree == NULL) {
1182     memset(data, 0, sizeof(*data));
1183     return data_cp.tree;
1184   }
1185
1186   switch (type) {
1187     case BVHTREE_FROM_VERTS:
1188     case BVHTREE_FROM_LOOSEVERTS:
1189       data_cp.raycast_callback = mesh_verts_spherecast;
1190
1191       data_cp.vert = mesh->mvert;
1192
1193       if (data_cp.cached == false) {
1194         /* TODO: a global mutex lock held during the expensive operation of
1195          * building the BVH tree is really bad for performance. */
1196         BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
1197         data_cp.cached = bvhcache_find(mesh->runtime.bvh_cache, type, &data_cp.tree);
1198
1199         if (data_cp.cached == false) {
1200           BLI_bitmap *loose_verts_mask = NULL;
1201           int loose_vert_len = -1;
1202           int verts_len = mesh->totvert;
1203
1204           if (type == BVHTREE_FROM_LOOSEVERTS) {
1205             loose_verts_mask = loose_verts_map_get(
1206                 mesh->medge, mesh->totedge, data_cp.vert, verts_len, &loose_vert_len);
1207           }
1208
1209           data_cp.tree = bvhtree_from_mesh_verts_create_tree(
1210               0.0, tree_type, 6, data_cp.vert, verts_len, loose_verts_mask, loose_vert_len);
1211
1212           if (loose_verts_mask != NULL) {
1213             MEM_freeN(loose_verts_mask);
1214           }
1215
1216           /* Save on cache for later use */
1217           /* printf("BVHTree built and saved on cache\n"); */
1218           bvhcache_insert(&mesh->runtime.bvh_cache, data_cp.tree, type);
1219         }
1220         BLI_rw_mutex_unlock(&cache_rwlock);
1221       }
1222       break;
1223
1224     case BVHTREE_FROM_EDGES:
1225     case BVHTREE_FROM_LOOSEEDGES:
1226       data_cp.nearest_callback = mesh_edges_nearest_point;
1227       data_cp.raycast_callback = mesh_edges_spherecast;
1228
1229       data_cp.vert = mesh->mvert;
1230       data_cp.edge = mesh->medge;
1231
1232       if (data_cp.cached == false) {
1233         BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
1234         data_cp.cached = bvhcache_find(mesh->runtime.bvh_cache, type, &data_cp.tree);
1235         if (data_cp.cached == false) {
1236           BLI_bitmap *loose_edges_mask = NULL;
1237           int loose_edges_len = -1;
1238           int edges_len = mesh->totedge;
1239
1240           if (type == BVHTREE_FROM_LOOSEEDGES) {
1241             loose_edges_mask = loose_edges_map_get(data_cp.edge, edges_len, &loose_edges_len);
1242           }
1243
1244           data_cp.tree = bvhtree_from_mesh_edges_create_tree(data_cp.vert,
1245                                                              data_cp.edge,
1246                                                              edges_len,
1247                                                              loose_edges_mask,
1248                                                              loose_edges_len,
1249                                                              0.0,
1250                                                              tree_type,
1251                                                              6);
1252
1253           if (loose_edges_mask != NULL) {
1254             MEM_freeN(loose_edges_mask);
1255           }
1256
1257           /* Save on cache for later use */
1258           /* printf("BVHTree built and saved on cache\n"); */
1259           bvhcache_insert(&mesh->runtime.bvh_cache, data_cp.tree, type);
1260         }
1261         BLI_rw_mutex_unlock(&cache_rwlock);
1262       }
1263       break;
1264
1265     case BVHTREE_FROM_FACES:
1266       data_cp.nearest_callback = mesh_faces_nearest_point;
1267       data_cp.raycast_callback = mesh_faces_spherecast;
1268
1269       data_cp.vert = mesh->mvert;
1270       data_cp.face = mesh->mface;
1271
1272       if (data_cp.cached == false) {
1273         BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
1274         data_cp.cached = bvhcache_find(mesh->runtime.bvh_cache, BVHTREE_FROM_FACES, &data_cp.tree);
1275         if (data_cp.cached == false) {
1276           int num_faces = mesh->totface;
1277           BLI_assert(!(num_faces == 0 && mesh->totpoly != 0));
1278
1279           data_cp.tree = bvhtree_from_mesh_faces_create_tree(
1280               0.0, tree_type, 6, data_cp.vert, data_cp.face, num_faces, NULL, -1);
1281
1282           /* Save on cache for later use */
1283           /* printf("BVHTree built and saved on cache\n"); */
1284           bvhcache_insert(&mesh->runtime.bvh_cache, data_cp.tree, BVHTREE_FROM_FACES);
1285         }
1286         BLI_rw_mutex_unlock(&cache_rwlock);
1287       }
1288       break;
1289
1290     case BVHTREE_FROM_LOOPTRI:
1291       data_cp.nearest_callback = mesh_looptri_nearest_point;
1292       data_cp.raycast_callback = mesh_looptri_spherecast;
1293
1294       data_cp.vert = mesh->mvert;
1295       data_cp.loop = mesh->mloop;
1296
1297       /* TODO: store looptris somewhere? */
1298       data_cp.looptri = BKE_mesh_runtime_looptri_ensure(mesh);
1299
1300       if (data_cp.cached == false) {
1301         BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
1302         data_cp.cached = bvhcache_find(
1303             mesh->runtime.bvh_cache, BVHTREE_FROM_LOOPTRI, &data_cp.tree);
1304         if (data_cp.cached == false) {
1305           int looptri_num = BKE_mesh_runtime_looptri_len(mesh);
1306           /* this assert checks we have looptris,
1307            * if not caller should use DM_ensure_looptri() */
1308           BLI_assert(!(looptri_num == 0 && mesh->totpoly != 0));
1309
1310           data_cp.tree = bvhtree_from_mesh_looptri_create_tree(0.0,
1311                                                                tree_type,
1312                                                                6,
1313                                                                data_cp.vert,
1314                                                                data_cp.loop,
1315                                                                data_cp.looptri,
1316                                                                looptri_num,
1317                                                                NULL,
1318                                                                -1);
1319
1320           /* Save on cache for later use */
1321           /* printf("BVHTree built and saved on cache\n"); */
1322           bvhcache_insert(&mesh->runtime.bvh_cache, data_cp.tree, BVHTREE_FROM_LOOPTRI);
1323         }
1324         BLI_rw_mutex_unlock(&cache_rwlock);
1325       }
1326       break;
1327     case BVHTREE_FROM_EM_VERTS:
1328     case BVHTREE_FROM_EM_EDGES:
1329     case BVHTREE_FROM_EM_LOOPTRI:
1330       BLI_assert(false);
1331       break;
1332   }
1333
1334   if (data_cp.tree != NULL) {
1335 #ifdef DEBUG
1336     if (BLI_bvhtree_get_tree_type(data_cp.tree) != tree_type) {
1337       printf("tree_type %d obtained instead of %d\n",
1338              BLI_bvhtree_get_tree_type(data_cp.tree),
1339              tree_type);
1340     }
1341 #endif
1342     data_cp.cached = true;
1343     memcpy(data, &data_cp, sizeof(*data));
1344   }
1345   else {
1346     free_bvhtree_from_mesh(&data_cp);
1347     memset(data, 0, sizeof(*data));
1348   }
1349
1350   return data_cp.tree;
1351 }
1352
1353 /** \} */
1354
1355 /* Frees data allocated by a call to bvhtree_from_editmesh_*. */
1356 void free_bvhtree_from_editmesh(struct BVHTreeFromEditMesh *data)
1357 {
1358   if (data->tree) {
1359     if (!data->cached) {
1360       BLI_bvhtree_free(data->tree);
1361     }
1362     memset(data, 0, sizeof(*data));
1363   }
1364 }
1365
1366 /* Frees data allocated by a call to bvhtree_from_mesh_*. */
1367 void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data)
1368 {
1369   if (data->tree && !data->cached) {
1370     BLI_bvhtree_free(data->tree);
1371   }
1372
1373   if (data->vert_allocated) {
1374     MEM_freeN((void *)data->vert);
1375   }
1376   if (data->edge_allocated) {
1377     MEM_freeN((void *)data->edge);
1378   }
1379   if (data->face_allocated) {
1380     MEM_freeN((void *)data->face);
1381   }
1382   if (data->loop_allocated) {
1383     MEM_freeN((void *)data->loop);
1384   }
1385   if (data->looptri_allocated) {
1386     MEM_freeN((void *)data->looptri);
1387   }
1388
1389   memset(data, 0, sizeof(*data));
1390 }
1391
1392 /* -------------------------------------------------------------------- */
1393 /** \name BVHCache
1394  * \{ */
1395
1396 typedef struct BVHCacheItem {
1397   int type;
1398   BVHTree *tree;
1399
1400 } BVHCacheItem;
1401
1402 /**
1403  * Queries a bvhcache for the cache bvhtree of the request type
1404  */
1405 bool bvhcache_find(const BVHCache *cache, int type, BVHTree **r_tree)
1406 {
1407   while (cache) {
1408     const BVHCacheItem *item = cache->link;
1409     if (item->type == type) {
1410       *r_tree = item->tree;
1411       return true;
1412     }
1413     cache = cache->next;
1414   }
1415   return false;
1416 }
1417
1418 bool bvhcache_has_tree(const BVHCache *cache, const BVHTree *tree)
1419 {
1420   while (cache) {
1421     const BVHCacheItem *item = cache->link;
1422     if (item->tree == tree) {
1423       return true;
1424     }
1425     cache = cache->next;
1426   }
1427   return false;
1428 }
1429
1430 /**
1431  * Inserts a BVHTree of the given type under the cache
1432  * After that the caller no longer needs to worry when to free the BVHTree
1433  * as that will be done when the cache is freed.
1434  *
1435  * A call to this assumes that there was no previous cached tree of the given type
1436  */
1437 void bvhcache_insert(BVHCache **cache_p, BVHTree *tree, int type)
1438 {
1439   BVHCacheItem *item = NULL;
1440
1441   assert(bvhcache_find(*cache_p, type, &(BVHTree *){0}) == false);
1442
1443   item = MEM_mallocN(sizeof(BVHCacheItem), "BVHCacheItem");
1444
1445   item->type = type;
1446   item->tree = tree;
1447
1448   BLI_linklist_prepend(cache_p, item);
1449 }
1450
1451 /**
1452  * frees a bvhcache
1453  */
1454 static void bvhcacheitem_free(void *_item)
1455 {
1456   BVHCacheItem *item = (BVHCacheItem *)_item;
1457
1458   BLI_bvhtree_free(item->tree);
1459   MEM_freeN(item);
1460 }
1461
1462 void bvhcache_free(BVHCache **cache_p)
1463 {
1464   BLI_linklist_free(*cache_p, (LinkNodeFreeFP)bvhcacheitem_free);
1465   *cache_p = NULL;
1466 }
1467
1468 /** \} */