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