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