Cleanup: comments (long lines) in 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
572  * (else will be computed from mask).
573  */
574 BVHTree *bvhtree_from_mesh_verts_ex(BVHTreeFromMesh *data,
575                                     const MVert *vert,
576                                     const int verts_num,
577                                     const bool vert_allocated,
578                                     const BLI_bitmap *verts_mask,
579                                     int verts_num_active,
580                                     float epsilon,
581                                     int tree_type,
582                                     int axis)
583 {
584   BVHTree *tree = bvhtree_from_mesh_verts_create_tree(
585       epsilon, tree_type, axis, vert, verts_num, verts_mask, verts_num_active);
586
587   /* Setup BVHTreeFromMesh */
588   bvhtree_from_mesh_verts_setup_data(data, tree, false, vert, vert_allocated);
589
590   return tree;
591 }
592
593 /** \} */
594
595 /* -------------------------------------------------------------------- */
596 /** \name Edge Builder
597  * \{ */
598
599 static BVHTree *bvhtree_from_editmesh_edges_create_tree(float epsilon,
600                                                         int tree_type,
601                                                         int axis,
602                                                         BMEditMesh *em,
603                                                         const int edges_num,
604                                                         const BLI_bitmap *edges_mask,
605                                                         int edges_num_active)
606 {
607   BM_mesh_elem_table_ensure(em->bm, BM_EDGE);
608   if (edges_mask) {
609     BLI_assert(IN_RANGE_INCL(edges_num_active, 0, edges_num));
610   }
611   else {
612     edges_num_active = edges_num;
613   }
614
615   BVHTree *tree = BLI_bvhtree_new(edges_num_active, epsilon, tree_type, axis);
616
617   if (tree) {
618     int i;
619     BMIter iter;
620     BMEdge *eed;
621     BM_ITER_MESH_INDEX (eed, &iter, em->bm, BM_EDGES_OF_MESH, i) {
622       if (edges_mask && !BLI_BITMAP_TEST_BOOL(edges_mask, i)) {
623         continue;
624       }
625       float co[2][3];
626       copy_v3_v3(co[0], eed->v1->co);
627       copy_v3_v3(co[1], eed->v2->co);
628
629       BLI_bvhtree_insert(tree, i, co[0], 2);
630     }
631     BLI_assert(BLI_bvhtree_get_len(tree) == edges_num_active);
632     BLI_bvhtree_balance(tree);
633   }
634
635   return tree;
636 }
637
638 static BVHTree *bvhtree_from_mesh_edges_create_tree(const MVert *vert,
639                                                     const MEdge *edge,
640                                                     const int edge_num,
641                                                     const BLI_bitmap *edges_mask,
642                                                     int edges_num_active,
643                                                     float epsilon,
644                                                     int tree_type,
645                                                     int axis)
646 {
647   BVHTree *tree = NULL;
648
649   if (edges_mask) {
650     BLI_assert(IN_RANGE_INCL(edges_num_active, 0, edge_num));
651   }
652   else {
653     edges_num_active = edge_num;
654   }
655
656   if (edges_num_active) {
657     /* Create a bvh-tree of the given target */
658     tree = BLI_bvhtree_new(edges_num_active, epsilon, tree_type, axis);
659     if (tree) {
660       for (int i = 0; i < edge_num; i++) {
661         if (edges_mask && !BLI_BITMAP_TEST_BOOL(edges_mask, i)) {
662           continue;
663         }
664         float co[2][3];
665         copy_v3_v3(co[0], vert[edge[i].v1].co);
666         copy_v3_v3(co[1], vert[edge[i].v2].co);
667
668         BLI_bvhtree_insert(tree, i, co[0], 2);
669       }
670       BLI_bvhtree_balance(tree);
671     }
672   }
673
674   return tree;
675 }
676
677 static void bvhtree_from_mesh_edges_setup_data(BVHTreeFromMesh *data,
678                                                BVHTree *tree,
679                                                const bool is_cached,
680                                                const MVert *vert,
681                                                const bool vert_allocated,
682                                                const MEdge *edge,
683                                                const bool edge_allocated)
684 {
685   memset(data, 0, sizeof(*data));
686
687   data->tree = tree;
688
689   data->cached = is_cached;
690
691   data->nearest_callback = mesh_edges_nearest_point;
692   data->raycast_callback = mesh_edges_spherecast;
693
694   data->vert = vert;
695   data->vert_allocated = vert_allocated;
696   data->edge = edge;
697   data->edge_allocated = edge_allocated;
698 }
699
700 /* Builds a bvh tree where nodes are the edges of the given em */
701 BVHTree *bvhtree_from_editmesh_edges_ex(BVHTreeFromEditMesh *data,
702                                         BMEditMesh *em,
703                                         const BLI_bitmap *edges_mask,
704                                         int edges_num_active,
705                                         float epsilon,
706                                         int tree_type,
707                                         int axis)
708 {
709   int edge_num = em->bm->totedge;
710
711   BVHTree *tree = bvhtree_from_editmesh_edges_create_tree(
712       epsilon, tree_type, axis, em, edge_num, edges_mask, edges_num_active);
713
714   if (tree) {
715     memset(data, 0, sizeof(*data));
716     data->tree = tree;
717     data->em = em;
718     data->nearest_callback = NULL; /* TODO */
719     data->raycast_callback = NULL; /* TODO */
720   }
721
722   return tree;
723 }
724
725 BVHTree *bvhtree_from_editmesh_edges(BVHTreeFromEditMesh *data,
726                                      BMEditMesh *em,
727                                      float epsilon,
728                                      int tree_type,
729                                      int axis,
730                                      BVHCache **bvh_cache)
731 {
732   if (bvh_cache) {
733     BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
734     data->cached = bvhcache_find(*bvh_cache, BVHTREE_FROM_EM_EDGES, &data->tree);
735     BLI_rw_mutex_unlock(&cache_rwlock);
736
737     if (data->cached == false) {
738       BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
739       data->cached = bvhcache_find(*bvh_cache, BVHTREE_FROM_EM_EDGES, &data->tree);
740       if (data->cached == false) {
741         data->tree = bvhtree_from_editmesh_edges_ex(data, em, NULL, -1, epsilon, tree_type, axis);
742
743         /* Save on cache for later use */
744         /* printf("BVHTree built and saved on cache\n"); */
745         bvhcache_insert(bvh_cache, data->tree, BVHTREE_FROM_EM_EDGES);
746       }
747       BLI_rw_mutex_unlock(&cache_rwlock);
748     }
749   }
750   else {
751     data->tree = bvhtree_from_editmesh_edges_ex(data, em, NULL, -1, epsilon, tree_type, axis);
752   }
753
754   return data->tree;
755 }
756
757 /**
758  * Builds a bvh tree where nodes are the given edges .
759  * \param vert, vert_allocated: if true, elem freeing will be done when freeing data.
760  * \param edge, edge_allocated: if true, elem freeing will be done when freeing data.
761  * \param edges_mask: if not null, true elements give which vert to add to BVH tree.
762  * \param edges_num_active: if >= 0, number of active edges to add to BVH tree
763  * (else will be computed from mask).
764  */
765 BVHTree *bvhtree_from_mesh_edges_ex(BVHTreeFromMesh *data,
766                                     const MVert *vert,
767                                     const bool vert_allocated,
768                                     const MEdge *edge,
769                                     const int edges_num,
770                                     const bool edge_allocated,
771                                     const BLI_bitmap *edges_mask,
772                                     int edges_num_active,
773                                     float epsilon,
774                                     int tree_type,
775                                     int axis)
776 {
777   BVHTree *tree = bvhtree_from_mesh_edges_create_tree(
778       vert, edge, edges_num, edges_mask, edges_num_active, epsilon, tree_type, axis);
779
780   /* Setup BVHTreeFromMesh */
781   bvhtree_from_mesh_edges_setup_data(
782       data, tree, false, vert, vert_allocated, edge, edge_allocated);
783
784   return tree;
785 }
786
787 /** \} */
788
789 /* -------------------------------------------------------------------- */
790 /** \name Tessellated Face Builder
791  * \{ */
792
793 static BVHTree *bvhtree_from_mesh_faces_create_tree(float epsilon,
794                                                     int tree_type,
795                                                     int axis,
796                                                     const MVert *vert,
797                                                     const MFace *face,
798                                                     const int faces_num,
799                                                     const BLI_bitmap *faces_mask,
800                                                     int faces_num_active)
801 {
802   BVHTree *tree = NULL;
803   int i;
804
805   if (faces_num) {
806     if (faces_mask) {
807       BLI_assert(IN_RANGE_INCL(faces_num_active, 0, faces_num));
808     }
809     else {
810       faces_num_active = faces_num;
811     }
812
813     /* Create a bvh-tree of the given target */
814     /* printf("%s: building BVH, total=%d\n", __func__, numFaces); */
815     tree = BLI_bvhtree_new(faces_num_active, epsilon, tree_type, axis);
816     if (tree) {
817       if (vert && face) {
818         for (i = 0; i < faces_num; i++) {
819           float co[4][3];
820           if (faces_mask && !BLI_BITMAP_TEST_BOOL(faces_mask, i)) {
821             continue;
822           }
823
824           copy_v3_v3(co[0], vert[face[i].v1].co);
825           copy_v3_v3(co[1], vert[face[i].v2].co);
826           copy_v3_v3(co[2], vert[face[i].v3].co);
827           if (face[i].v4) {
828             copy_v3_v3(co[3], vert[face[i].v4].co);
829           }
830
831           BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
832         }
833       }
834       BLI_assert(BLI_bvhtree_get_len(tree) == faces_num_active);
835       BLI_bvhtree_balance(tree);
836     }
837   }
838
839   return tree;
840 }
841
842 static void bvhtree_from_mesh_faces_setup_data(BVHTreeFromMesh *data,
843                                                BVHTree *tree,
844                                                const bool is_cached,
845                                                const MVert *vert,
846                                                const bool vert_allocated,
847                                                const MFace *face,
848                                                const bool face_allocated)
849 {
850   memset(data, 0, sizeof(*data));
851
852   data->tree = tree;
853   data->cached = is_cached;
854
855   data->nearest_callback = mesh_faces_nearest_point;
856   data->raycast_callback = mesh_faces_spherecast;
857
858   data->vert = vert;
859   data->vert_allocated = vert_allocated;
860   data->face = face;
861   data->face_allocated = face_allocated;
862 }
863
864 /**
865  * Builds a bvh tree where nodes are the given tessellated faces
866  * (note: does not copy given mfaces!).
867  * \param vert_allocated: if true, vert freeing will be done when freeing data.
868  * \param face_allocated: if true, face freeing will be done when freeing data.
869  * \param faces_mask: if not null, true elements give which faces to add to BVH tree.
870  * \param faces_num_active: if >= 0, number of active faces to add to BVH tree
871  * (else will be computed from mask).
872  */
873 BVHTree *bvhtree_from_mesh_faces_ex(BVHTreeFromMesh *data,
874                                     const MVert *vert,
875                                     const bool vert_allocated,
876                                     const MFace *face,
877                                     const int numFaces,
878                                     const bool face_allocated,
879                                     const BLI_bitmap *faces_mask,
880                                     int faces_num_active,
881                                     float epsilon,
882                                     int tree_type,
883                                     int axis)
884 {
885   BVHTree *tree = bvhtree_from_mesh_faces_create_tree(
886       epsilon, tree_type, axis, vert, face, numFaces, faces_mask, faces_num_active);
887
888   /* Setup BVHTreeFromMesh */
889   bvhtree_from_mesh_faces_setup_data(
890       data, tree, false, vert, vert_allocated, face, face_allocated);
891
892   return tree;
893 }
894
895 /** \} */
896
897 /* -------------------------------------------------------------------- */
898 /** \name LoopTri Face Builder
899  * \{ */
900
901 static BVHTree *bvhtree_from_editmesh_looptri_create_tree(float epsilon,
902                                                           int tree_type,
903                                                           int axis,
904                                                           BMEditMesh *em,
905                                                           const int looptri_num,
906                                                           const BLI_bitmap *looptri_mask,
907                                                           int looptri_num_active)
908 {
909   BVHTree *tree = NULL;
910   int i;
911
912   if (looptri_num) {
913     if (looptri_mask) {
914       BLI_assert(IN_RANGE_INCL(looptri_num_active, 0, looptri_num));
915     }
916     else {
917       looptri_num_active = looptri_num;
918     }
919
920     /* Create a bvh-tree of the given target */
921     /* printf("%s: building BVH, total=%d\n", __func__, numFaces); */
922     tree = BLI_bvhtree_new(looptri_num_active, epsilon, tree_type, axis);
923     if (tree) {
924       if (em) {
925         const struct BMLoop *(*looptris)[3] = (void *)em->looptris;
926
927         /* Insert BMesh-tessellation triangles into the bvh tree, unless they are hidden
928          * and/or selected. Even if the faces themselves are not selected for the snapped
929          * transform, having a vertex selected means the face (and thus it's tessellated
930          * triangles) will be moving and will not be a good snap targets. */
931         for (i = 0; i < looptri_num; i++) {
932           const BMLoop **ltri = looptris[i];
933           bool insert = looptri_mask ? BLI_BITMAP_TEST_BOOL(looptri_mask, i) : true;
934
935           if (insert) {
936             /* No reason found to block hit-testing the triangle for snap, so insert it now.*/
937             float co[3][3];
938             copy_v3_v3(co[0], ltri[0]->v->co);
939             copy_v3_v3(co[1], ltri[1]->v->co);
940             copy_v3_v3(co[2], ltri[2]->v->co);
941
942             BLI_bvhtree_insert(tree, i, co[0], 3);
943           }
944         }
945       }
946       BLI_assert(BLI_bvhtree_get_len(tree) == looptri_num_active);
947       BLI_bvhtree_balance(tree);
948     }
949   }
950
951   return tree;
952 }
953
954 static BVHTree *bvhtree_from_mesh_looptri_create_tree(float epsilon,
955                                                       int tree_type,
956                                                       int axis,
957                                                       const MVert *vert,
958                                                       const MLoop *mloop,
959                                                       const MLoopTri *looptri,
960                                                       const int looptri_num,
961                                                       const BLI_bitmap *looptri_mask,
962                                                       int looptri_num_active)
963 {
964   BVHTree *tree = NULL;
965
966   if (looptri_mask) {
967     BLI_assert(IN_RANGE_INCL(looptri_num_active, 0, looptri_num));
968   }
969   else {
970     looptri_num_active = looptri_num;
971   }
972
973   if (looptri_num_active) {
974     /* Create a bvh-tree of the given target */
975     /* printf("%s: building BVH, total=%d\n", __func__, numFaces); */
976     tree = BLI_bvhtree_new(looptri_num_active, epsilon, tree_type, axis);
977     if (tree) {
978       if (vert && looptri) {
979         for (int i = 0; i < looptri_num; i++) {
980           float co[3][3];
981           if (looptri_mask && !BLI_BITMAP_TEST_BOOL(looptri_mask, i)) {
982             continue;
983           }
984
985           copy_v3_v3(co[0], vert[mloop[looptri[i].tri[0]].v].co);
986           copy_v3_v3(co[1], vert[mloop[looptri[i].tri[1]].v].co);
987           copy_v3_v3(co[2], vert[mloop[looptri[i].tri[2]].v].co);
988
989           BLI_bvhtree_insert(tree, i, co[0], 3);
990         }
991       }
992       BLI_assert(BLI_bvhtree_get_len(tree) == looptri_num_active);
993       BLI_bvhtree_balance(tree);
994     }
995   }
996
997   return tree;
998 }
999
1000 static void bvhtree_from_mesh_looptri_setup_data(BVHTreeFromMesh *data,
1001                                                  BVHTree *tree,
1002                                                  const bool is_cached,
1003                                                  const MVert *vert,
1004                                                  const bool vert_allocated,
1005                                                  const MLoop *mloop,
1006                                                  const bool loop_allocated,
1007                                                  const MLoopTri *looptri,
1008                                                  const bool looptri_allocated)
1009 {
1010   memset(data, 0, sizeof(*data));
1011
1012   data->tree = tree;
1013   data->cached = is_cached;
1014
1015   data->nearest_callback = mesh_looptri_nearest_point;
1016   data->raycast_callback = mesh_looptri_spherecast;
1017
1018   data->vert = vert;
1019   data->vert_allocated = vert_allocated;
1020   data->loop = mloop;
1021   data->loop_allocated = loop_allocated;
1022   data->looptri = looptri;
1023   data->looptri_allocated = looptri_allocated;
1024 }
1025
1026 /**
1027  * Builds a bvh tree where nodes are the looptri faces of the given bm
1028  */
1029 BVHTree *bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh *data,
1030                                           BMEditMesh *em,
1031                                           const BLI_bitmap *looptri_mask,
1032                                           int looptri_num_active,
1033                                           float epsilon,
1034                                           int tree_type,
1035                                           int axis,
1036                                           BVHCache **bvhCache)
1037 {
1038   /* BMESH specific check that we have tessfaces,
1039    * we _could_ tessellate here but rather not - campbell */
1040
1041   BVHTree *tree = NULL;
1042   if (bvhCache) {
1043     BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
1044     bool in_cache = bvhcache_find(*bvhCache, BVHTREE_FROM_EM_LOOPTRI, &tree);
1045     BLI_rw_mutex_unlock(&cache_rwlock);
1046     if (in_cache == false) {
1047       BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
1048       in_cache = bvhcache_find(*bvhCache, BVHTREE_FROM_EM_LOOPTRI, &tree);
1049       if (in_cache == false) {
1050         tree = bvhtree_from_editmesh_looptri_create_tree(
1051             epsilon, tree_type, axis, em, em->tottri, looptri_mask, looptri_num_active);
1052
1053         /* Save on cache for later use */
1054         /* printf("BVHTree built and saved on cache\n"); */
1055         bvhcache_insert(bvhCache, tree, BVHTREE_FROM_EM_LOOPTRI);
1056       }
1057       BLI_rw_mutex_unlock(&cache_rwlock);
1058     }
1059   }
1060   else {
1061     tree = bvhtree_from_editmesh_looptri_create_tree(
1062         epsilon, tree_type, axis, em, em->tottri, looptri_mask, looptri_num_active);
1063   }
1064
1065   if (tree) {
1066     data->tree = tree;
1067     data->nearest_callback = editmesh_looptri_nearest_point;
1068     data->raycast_callback = editmesh_looptri_spherecast;
1069     data->em = em;
1070     data->cached = bvhCache != NULL;
1071   }
1072   return tree;
1073 }
1074
1075 BVHTree *bvhtree_from_editmesh_looptri(BVHTreeFromEditMesh *data,
1076                                        BMEditMesh *em,
1077                                        float epsilon,
1078                                        int tree_type,
1079                                        int axis,
1080                                        BVHCache **bvhCache)
1081 {
1082   return bvhtree_from_editmesh_looptri_ex(data, em, NULL, -1, epsilon, tree_type, axis, bvhCache);
1083 }
1084
1085 /**
1086  * Builds a bvh tree where nodes are the looptri faces of the given dm
1087  *
1088  * \note for editmesh this is currently a duplicate of bvhtree_from_mesh_faces_ex
1089  */
1090 BVHTree *bvhtree_from_mesh_looptri_ex(BVHTreeFromMesh *data,
1091                                       const struct MVert *vert,
1092                                       const bool vert_allocated,
1093                                       const struct MLoop *mloop,
1094                                       const bool loop_allocated,
1095                                       const struct MLoopTri *looptri,
1096                                       const int looptri_num,
1097                                       const bool looptri_allocated,
1098                                       const BLI_bitmap *looptri_mask,
1099                                       int looptri_num_active,
1100                                       float epsilon,
1101                                       int tree_type,
1102                                       int axis)
1103 {
1104   BVHTree *tree = bvhtree_from_mesh_looptri_create_tree(epsilon,
1105                                                         tree_type,
1106                                                         axis,
1107                                                         vert,
1108                                                         mloop,
1109                                                         looptri,
1110                                                         looptri_num,
1111                                                         looptri_mask,
1112                                                         looptri_num_active);
1113
1114   /* Setup BVHTreeFromMesh */
1115   bvhtree_from_mesh_looptri_setup_data(
1116       data, tree, false, vert, vert_allocated, mloop, loop_allocated, looptri, looptri_allocated);
1117
1118   return tree;
1119 }
1120
1121 static BLI_bitmap *loose_verts_map_get(const MEdge *medge,
1122                                        int edges_num,
1123                                        const MVert *UNUSED(mvert),
1124                                        int verts_num,
1125                                        int *r_loose_vert_num)
1126 {
1127   BLI_bitmap *loose_verts_mask = BLI_BITMAP_NEW(verts_num, __func__);
1128   BLI_bitmap_set_all(loose_verts_mask, true, verts_num);
1129
1130   const MEdge *e = medge;
1131   int num_linked_verts = 0;
1132   for (; edges_num--; e++) {
1133     if (BLI_BITMAP_TEST(loose_verts_mask, e->v1)) {
1134       BLI_BITMAP_DISABLE(loose_verts_mask, e->v1);
1135       num_linked_verts++;
1136     }
1137     if (BLI_BITMAP_TEST(loose_verts_mask, e->v2)) {
1138       BLI_BITMAP_DISABLE(loose_verts_mask, e->v2);
1139       num_linked_verts++;
1140     }
1141   }
1142
1143   *r_loose_vert_num = verts_num - num_linked_verts;
1144
1145   return loose_verts_mask;
1146 }
1147
1148 static BLI_bitmap *loose_edges_map_get(const MEdge *medge,
1149                                        const int edges_len,
1150                                        int *r_loose_edge_len)
1151 {
1152   BLI_bitmap *loose_edges_mask = BLI_BITMAP_NEW(edges_len, __func__);
1153
1154   int loose_edges_len = 0;
1155   const MEdge *e = medge;
1156   for (int i = 0; i < edges_len; i++, e++) {
1157     if (e->flag & ME_LOOSEEDGE) {
1158       BLI_BITMAP_ENABLE(loose_edges_mask, i);
1159       loose_edges_len++;
1160     }
1161     else {
1162       BLI_BITMAP_DISABLE(loose_edges_mask, i);
1163     }
1164   }
1165
1166   *r_loose_edge_len = loose_edges_len;
1167
1168   return loose_edges_mask;
1169 }
1170
1171 /**
1172  * Builds or queries a bvhcache for the cache bvhtree of the request type.
1173  */
1174 BVHTree *BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data,
1175                                    struct Mesh *mesh,
1176                                    const int type,
1177                                    const int tree_type)
1178 {
1179   struct BVHTreeFromMesh data_cp = {0};
1180
1181   BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_READ);
1182   data_cp.cached = bvhcache_find(mesh->runtime.bvh_cache, type, &data_cp.tree);
1183   BLI_rw_mutex_unlock(&cache_rwlock);
1184
1185   if (data_cp.cached && data_cp.tree == NULL) {
1186     memset(data, 0, sizeof(*data));
1187     return data_cp.tree;
1188   }
1189
1190   switch (type) {
1191     case BVHTREE_FROM_VERTS:
1192     case BVHTREE_FROM_LOOSEVERTS:
1193       data_cp.raycast_callback = mesh_verts_spherecast;
1194
1195       data_cp.vert = mesh->mvert;
1196
1197       if (data_cp.cached == false) {
1198         /* TODO: a global mutex lock held during the expensive operation of
1199          * building the BVH tree is really bad for performance. */
1200         BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
1201         data_cp.cached = bvhcache_find(mesh->runtime.bvh_cache, type, &data_cp.tree);
1202
1203         if (data_cp.cached == false) {
1204           BLI_bitmap *loose_verts_mask = NULL;
1205           int loose_vert_len = -1;
1206           int verts_len = mesh->totvert;
1207
1208           if (type == BVHTREE_FROM_LOOSEVERTS) {
1209             loose_verts_mask = loose_verts_map_get(
1210                 mesh->medge, mesh->totedge, data_cp.vert, verts_len, &loose_vert_len);
1211           }
1212
1213           data_cp.tree = bvhtree_from_mesh_verts_create_tree(
1214               0.0, tree_type, 6, data_cp.vert, verts_len, loose_verts_mask, loose_vert_len);
1215
1216           if (loose_verts_mask != NULL) {
1217             MEM_freeN(loose_verts_mask);
1218           }
1219
1220           /* Save on cache for later use */
1221           /* printf("BVHTree built and saved on cache\n"); */
1222           bvhcache_insert(&mesh->runtime.bvh_cache, data_cp.tree, type);
1223         }
1224         BLI_rw_mutex_unlock(&cache_rwlock);
1225       }
1226       break;
1227
1228     case BVHTREE_FROM_EDGES:
1229     case BVHTREE_FROM_LOOSEEDGES:
1230       data_cp.nearest_callback = mesh_edges_nearest_point;
1231       data_cp.raycast_callback = mesh_edges_spherecast;
1232
1233       data_cp.vert = mesh->mvert;
1234       data_cp.edge = mesh->medge;
1235
1236       if (data_cp.cached == false) {
1237         BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
1238         data_cp.cached = bvhcache_find(mesh->runtime.bvh_cache, type, &data_cp.tree);
1239         if (data_cp.cached == false) {
1240           BLI_bitmap *loose_edges_mask = NULL;
1241           int loose_edges_len = -1;
1242           int edges_len = mesh->totedge;
1243
1244           if (type == BVHTREE_FROM_LOOSEEDGES) {
1245             loose_edges_mask = loose_edges_map_get(data_cp.edge, edges_len, &loose_edges_len);
1246           }
1247
1248           data_cp.tree = bvhtree_from_mesh_edges_create_tree(data_cp.vert,
1249                                                              data_cp.edge,
1250                                                              edges_len,
1251                                                              loose_edges_mask,
1252                                                              loose_edges_len,
1253                                                              0.0,
1254                                                              tree_type,
1255                                                              6);
1256
1257           if (loose_edges_mask != NULL) {
1258             MEM_freeN(loose_edges_mask);
1259           }
1260
1261           /* Save on cache for later use */
1262           /* printf("BVHTree built and saved on cache\n"); */
1263           bvhcache_insert(&mesh->runtime.bvh_cache, data_cp.tree, type);
1264         }
1265         BLI_rw_mutex_unlock(&cache_rwlock);
1266       }
1267       break;
1268
1269     case BVHTREE_FROM_FACES:
1270       data_cp.nearest_callback = mesh_faces_nearest_point;
1271       data_cp.raycast_callback = mesh_faces_spherecast;
1272
1273       data_cp.vert = mesh->mvert;
1274       data_cp.face = mesh->mface;
1275
1276       if (data_cp.cached == false) {
1277         BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
1278         data_cp.cached = bvhcache_find(mesh->runtime.bvh_cache, BVHTREE_FROM_FACES, &data_cp.tree);
1279         if (data_cp.cached == false) {
1280           int num_faces = mesh->totface;
1281           BLI_assert(!(num_faces == 0 && mesh->totpoly != 0));
1282
1283           data_cp.tree = bvhtree_from_mesh_faces_create_tree(
1284               0.0, tree_type, 6, data_cp.vert, data_cp.face, num_faces, NULL, -1);
1285
1286           /* Save on cache for later use */
1287           /* printf("BVHTree built and saved on cache\n"); */
1288           bvhcache_insert(&mesh->runtime.bvh_cache, data_cp.tree, BVHTREE_FROM_FACES);
1289         }
1290         BLI_rw_mutex_unlock(&cache_rwlock);
1291       }
1292       break;
1293
1294     case BVHTREE_FROM_LOOPTRI:
1295       data_cp.nearest_callback = mesh_looptri_nearest_point;
1296       data_cp.raycast_callback = mesh_looptri_spherecast;
1297
1298       data_cp.vert = mesh->mvert;
1299       data_cp.loop = mesh->mloop;
1300
1301       /* TODO: store looptris somewhere? */
1302       data_cp.looptri = BKE_mesh_runtime_looptri_ensure(mesh);
1303
1304       if (data_cp.cached == false) {
1305         BLI_rw_mutex_lock(&cache_rwlock, THREAD_LOCK_WRITE);
1306         data_cp.cached = bvhcache_find(
1307             mesh->runtime.bvh_cache, BVHTREE_FROM_LOOPTRI, &data_cp.tree);
1308         if (data_cp.cached == false) {
1309           int looptri_num = BKE_mesh_runtime_looptri_len(mesh);
1310           /* this assert checks we have looptris,
1311            * if not caller should use DM_ensure_looptri() */
1312           BLI_assert(!(looptri_num == 0 && mesh->totpoly != 0));
1313
1314           data_cp.tree = bvhtree_from_mesh_looptri_create_tree(0.0,
1315                                                                tree_type,
1316                                                                6,
1317                                                                data_cp.vert,
1318                                                                data_cp.loop,
1319                                                                data_cp.looptri,
1320                                                                looptri_num,
1321                                                                NULL,
1322                                                                -1);
1323
1324           /* Save on cache for later use */
1325           /* printf("BVHTree built and saved on cache\n"); */
1326           bvhcache_insert(&mesh->runtime.bvh_cache, data_cp.tree, BVHTREE_FROM_LOOPTRI);
1327         }
1328         BLI_rw_mutex_unlock(&cache_rwlock);
1329       }
1330       break;
1331     case BVHTREE_FROM_EM_VERTS:
1332     case BVHTREE_FROM_EM_EDGES:
1333     case BVHTREE_FROM_EM_LOOPTRI:
1334       BLI_assert(false);
1335       break;
1336   }
1337
1338   if (data_cp.tree != NULL) {
1339 #ifdef DEBUG
1340     if (BLI_bvhtree_get_tree_type(data_cp.tree) != tree_type) {
1341       printf("tree_type %d obtained instead of %d\n",
1342              BLI_bvhtree_get_tree_type(data_cp.tree),
1343              tree_type);
1344     }
1345 #endif
1346     data_cp.cached = true;
1347     memcpy(data, &data_cp, sizeof(*data));
1348   }
1349   else {
1350     free_bvhtree_from_mesh(&data_cp);
1351     memset(data, 0, sizeof(*data));
1352   }
1353
1354   return data_cp.tree;
1355 }
1356
1357 /** \} */
1358
1359 /* Frees data allocated by a call to bvhtree_from_editmesh_*. */
1360 void free_bvhtree_from_editmesh(struct BVHTreeFromEditMesh *data)
1361 {
1362   if (data->tree) {
1363     if (!data->cached) {
1364       BLI_bvhtree_free(data->tree);
1365     }
1366     memset(data, 0, sizeof(*data));
1367   }
1368 }
1369
1370 /* Frees data allocated by a call to bvhtree_from_mesh_*. */
1371 void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data)
1372 {
1373   if (data->tree && !data->cached) {
1374     BLI_bvhtree_free(data->tree);
1375   }
1376
1377   if (data->vert_allocated) {
1378     MEM_freeN((void *)data->vert);
1379   }
1380   if (data->edge_allocated) {
1381     MEM_freeN((void *)data->edge);
1382   }
1383   if (data->face_allocated) {
1384     MEM_freeN((void *)data->face);
1385   }
1386   if (data->loop_allocated) {
1387     MEM_freeN((void *)data->loop);
1388   }
1389   if (data->looptri_allocated) {
1390     MEM_freeN((void *)data->looptri);
1391   }
1392
1393   memset(data, 0, sizeof(*data));
1394 }
1395
1396 /* -------------------------------------------------------------------- */
1397 /** \name BVHCache
1398  * \{ */
1399
1400 typedef struct BVHCacheItem {
1401   int type;
1402   BVHTree *tree;
1403
1404 } BVHCacheItem;
1405
1406 /**
1407  * Queries a bvhcache for the cache bvhtree of the request type
1408  */
1409 bool bvhcache_find(const BVHCache *cache, int type, BVHTree **r_tree)
1410 {
1411   while (cache) {
1412     const BVHCacheItem *item = cache->link;
1413     if (item->type == type) {
1414       *r_tree = item->tree;
1415       return true;
1416     }
1417     cache = cache->next;
1418   }
1419   return false;
1420 }
1421
1422 bool bvhcache_has_tree(const BVHCache *cache, const BVHTree *tree)
1423 {
1424   while (cache) {
1425     const BVHCacheItem *item = cache->link;
1426     if (item->tree == tree) {
1427       return true;
1428     }
1429     cache = cache->next;
1430   }
1431   return false;
1432 }
1433
1434 /**
1435  * Inserts a BVHTree of the given type under the cache
1436  * After that the caller no longer needs to worry when to free the BVHTree
1437  * as that will be done when the cache is freed.
1438  *
1439  * A call to this assumes that there was no previous cached tree of the given type
1440  */
1441 void bvhcache_insert(BVHCache **cache_p, BVHTree *tree, int type)
1442 {
1443   BVHCacheItem *item = NULL;
1444
1445   assert(bvhcache_find(*cache_p, type, &(BVHTree *){0}) == false);
1446
1447   item = MEM_mallocN(sizeof(BVHCacheItem), "BVHCacheItem");
1448
1449   item->type = type;
1450   item->tree = tree;
1451
1452   BLI_linklist_prepend(cache_p, item);
1453 }
1454
1455 /**
1456  * frees a bvhcache
1457  */
1458 static void bvhcacheitem_free(void *_item)
1459 {
1460   BVHCacheItem *item = (BVHCacheItem *)_item;
1461
1462   BLI_bvhtree_free(item->tree);
1463   MEM_freeN(item);
1464 }
1465
1466 void bvhcache_free(BVHCache **cache_p)
1467 {
1468   BLI_linklist_free(*cache_p, (LinkNodeFreeFP)bvhcacheitem_free);
1469   *cache_p = NULL;
1470 }
1471
1472 /** \} */