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