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