Cleanup: Move bvhutils.c to C++

This will be useful when adding a utility to create a BVH tree from a
`CurveEval` for the attribute proximity and attribute transfer nodes.

1 files changed, 0 insertions, 1790 deletions

diff --git a/source/blender/blenkernel/intern/bvhutils.c b/source/blender/blenkernel/intern/bvhutils.c
deleted file mode 100644
index 4659c464099..00000000000
--- a/source/blender/blenkernel/intern/bvhutils.c
+++ /dev/null
@@ -1,1790 +0,0 @@
-/*
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version 2
- * of the License, or (at your option) any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) Blender Foundation.
- * All rights reserved.
- */
-
-/** \file
- * \ingroup bke
- */
-
-#include <math.h>
-#include <stdio.h>
-#include <string.h>
-
-#include "DNA_mesh_types.h"
-#include "DNA_meshdata_types.h"
-#include "DNA_pointcloud_types.h"
-
-#include "BLI_linklist.h"
-#include "BLI_math.h"
-#include "BLI_task.h"
-#include "BLI_threads.h"
-#include "BLI_utildefines.h"
-
-#include "BKE_bvhutils.h"
-#include "BKE_editmesh.h"
-#include "BKE_mesh.h"
-#include "BKE_mesh_runtime.h"
-
-#include "MEM_guardedalloc.h"
-
-/* -------------------------------------------------------------------- */
-/** \name BVHCache
- * \{ */
-
-typedef struct BVHCacheItem {
-  bool is_filled;
-  BVHTree *tree;
-} BVHCacheItem;
-
-typedef struct BVHCache {
-  BVHCacheItem items[BVHTREE_MAX_ITEM];
-  ThreadMutex mutex;
-} BVHCache;
-
-/**
- * Queries a bvhcache for the cache bvhtree of the request type
- *
- * When the `r_locked` is filled and the tree could not be found the caches mutex will be
- * locked. This mutex can be unlocked by calling `bvhcache_unlock`.
- *
- * When `r_locked` is used the `mesh_eval_mutex` must contain the `Mesh_Runtime.eval_mutex`.
- */
-static bool bvhcache_find(BVHCache **bvh_cache_p,
-                          BVHCacheType type,
-                          BVHTree **r_tree,
-                          bool *r_locked,
-                          ThreadMutex *mesh_eval_mutex)
-{
-  bool do_lock = r_locked;
-  if (r_locked) {
-    *r_locked = false;
-  }
-  if (*bvh_cache_p == NULL) {
-    if (!do_lock) {
-      /* Cache does not exist and no lock is requested. */
-      return false;
-    }
-    /* Lazy initialization of the bvh_cache using the `mesh_eval_mutex`. */
-    BLI_mutex_lock(mesh_eval_mutex);
-    if (*bvh_cache_p == NULL) {
-      *bvh_cache_p = bvhcache_init();
-    }
-    BLI_mutex_unlock(mesh_eval_mutex);
-  }
-  BVHCache *bvh_cache = *bvh_cache_p;
-
-  if (bvh_cache->items[type].is_filled) {
-    *r_tree = bvh_cache->items[type].tree;
-    return true;
-  }
-  if (do_lock) {
-    BLI_mutex_lock(&bvh_cache->mutex);
-    bool in_cache = bvhcache_find(bvh_cache_p, type, r_tree, NULL, NULL);
-    if (in_cache) {
-      BLI_mutex_unlock(&bvh_cache->mutex);
-      return in_cache;
-    }
-    *r_locked = true;
-  }
-  return false;
-}
-
-static void bvhcache_unlock(BVHCache *bvh_cache, bool lock_started)
-{
-  if (lock_started) {
-    BLI_mutex_unlock(&bvh_cache->mutex);
-  }
-}
-
-bool bvhcache_has_tree(const BVHCache *bvh_cache, const BVHTree *tree)
-{
-  if (bvh_cache == NULL) {
-    return false;
-  }
-
-  for (BVHCacheType i = 0; i < BVHTREE_MAX_ITEM; i++) {
-    if (bvh_cache->items[i].tree == tree) {
-      return true;
-    }
-  }
-  return false;
-}
-
-BVHCache *bvhcache_init(void)
-{
-  BVHCache *cache = MEM_callocN(sizeof(BVHCache), __func__);
-  BLI_mutex_init(&cache->mutex);
-  return cache;
-}
-/**
- * Inserts a BVHTree of the given type under the cache
- * After that the caller no longer needs to worry when to free the BVHTree
- * as that will be done when the cache is freed.
- *
- * A call to this assumes that there was no previous cached tree of the given type
- * \warning The #BVHTree can be NULL.
- */
-static void bvhcache_insert(BVHCache *bvh_cache, BVHTree *tree, BVHCacheType type)
-{
-  BVHCacheItem *item = &bvh_cache->items[type];
-  BLI_assert(!item->is_filled);
-  item->tree = tree;
-  item->is_filled = true;
-}
-
-/**
- * frees a bvhcache
- */
-void bvhcache_free(BVHCache *bvh_cache)
-{
-  for (BVHCacheType index = 0; index < BVHTREE_MAX_ITEM; index++) {
-    BVHCacheItem *item = &bvh_cache->items[index];
-    BLI_bvhtree_free(item->tree);
-    item->tree = NULL;
-  }
-  BLI_mutex_end(&bvh_cache->mutex);
-  MEM_freeN(bvh_cache);
-}
-
-/* BVH tree balancing inside a mutex lock must be run in isolation. Balancing
- * is multithreaded, and we do not want the current thread to start another task
- * that may involve acquiring the same mutex lock that it is waiting for. */
-static void bvhtree_balance_isolated(void *userdata)
-{
-  BLI_bvhtree_balance((BVHTree *)userdata);
-}
-
-static void bvhtree_balance(BVHTree *tree, const bool isolate)
-{
-  if (tree) {
-    if (isolate) {
-      BLI_task_isolate(bvhtree_balance_isolated, tree);
-    }
-    else {
-      BLI_bvhtree_balance(tree);
-    }
-  }
-}
-
-/** \} */
-/* -------------------------------------------------------------------- */
-/** \name Local Callbacks
- * \{ */
-
-/* Math stuff for ray casting on mesh faces and for nearest surface */
-
-float bvhtree_ray_tri_intersection(const BVHTreeRay *ray,
-                                   const float UNUSED(m_dist),
-                                   const float v0[3],
-                                   const float v1[3],
-                                   const float v2[3])
-{
-  float dist;
-
-#ifdef USE_KDOPBVH_WATERTIGHT
-  if (isect_ray_tri_watertight_v3(ray->origin, ray->isect_precalc, v0, v1, v2, &dist, NULL))
-#else
-  if (isect_ray_tri_epsilon_v3(ray->origin, ray->direction, v0, v1, v2, &dist, NULL, FLT_EPSILON))
-#endif
-  {
-    return dist;
-  }
-
-  return FLT_MAX;
-}
-
-float bvhtree_sphereray_tri_intersection(const BVHTreeRay *ray,
-                                         float radius,
-                                         const float m_dist,
-                                         const float v0[3],
-                                         const float v1[3],
-                                         const float v2[3])
-{
-
-  float idist;
-  float p1[3];
-  float hit_point[3];
-
-  madd_v3_v3v3fl(p1, ray->origin, ray->direction, m_dist);
-  if (isect_sweeping_sphere_tri_v3(ray->origin, p1, radius, v0, v1, v2, &idist, hit_point)) {
-    return idist * m_dist;
-  }
-
-  return FLT_MAX;
-}
-
-/*
- * BVH from meshes callbacks
- */
-
-/* Callback to bvh tree nearest point. The tree must have been built using bvhtree_from_mesh_faces.
- * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
-static void mesh_faces_nearest_point(void *userdata,
-                                     int index,
-                                     const float co[3],
-                                     BVHTreeNearest *nearest)
-{
-  const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
-  const MVert *vert = data->vert;
-  const MFace *face = data->face + index;
-
-  const float *t0, *t1, *t2, *t3;
-  t0 = vert[face->v1].co;
-  t1 = vert[face->v2].co;
-  t2 = vert[face->v3].co;
-  t3 = face->v4 ? vert[face->v4].co : NULL;
-
-  do {
-    float nearest_tmp[3], dist_sq;
-
-    closest_on_tri_to_point_v3(nearest_tmp, co, t0, t1, t2);
-    dist_sq = len_squared_v3v3(co, nearest_tmp);
-
-    if (dist_sq < nearest->dist_sq) {
-      nearest->index = index;
-      nearest->dist_sq = dist_sq;
-      copy_v3_v3(nearest->co, nearest_tmp);
-      normal_tri_v3(nearest->no, t0, t1, t2);
-    }
-
-    t1 = t2;
-    t2 = t3;
-    t3 = NULL;
-
-  } while (t2);
-}
-/* copy of function above */
-static void mesh_looptri_nearest_point(void *userdata,
-                                       int index,
-                                       const float co[3],
-                                       BVHTreeNearest *nearest)
-{
-  const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
-  const MVert *vert = data->vert;
-  const MLoopTri *lt = &data->looptri[index];
-  const float *vtri_co[3] = {
-      vert[data->loop[lt->tri[0]].v].co,
-      vert[data->loop[lt->tri[1]].v].co,
-      vert[data->loop[lt->tri[2]].v].co,
-  };
-  float nearest_tmp[3], dist_sq;
-
-  closest_on_tri_to_point_v3(nearest_tmp, co, UNPACK3(vtri_co));
-  dist_sq = len_squared_v3v3(co, nearest_tmp);
-
-  if (dist_sq < nearest->dist_sq) {
-    nearest->index = index;
-    nearest->dist_sq = dist_sq;
-    copy_v3_v3(nearest->co, nearest_tmp);
-    normal_tri_v3(nearest->no, UNPACK3(vtri_co));
-  }
-}
-/* copy of function above (warning, should de-duplicate with editmesh_bvh.c) */
-static void editmesh_looptri_nearest_point(void *userdata,
-                                           int index,
-                                           const float co[3],
-                                           BVHTreeNearest *nearest)
-{
-  const BVHTreeFromEditMesh *data = userdata;
-  BMEditMesh *em = data->em;
-  const BMLoop **ltri = (const BMLoop **)em->looptris[index];
-
-  const float *t0, *t1, *t2;
-  t0 = ltri[0]->v->co;
-  t1 = ltri[1]->v->co;
-  t2 = ltri[2]->v->co;
-
-  {
-    float nearest_tmp[3], dist_sq;
-
-    closest_on_tri_to_point_v3(nearest_tmp, co, t0, t1, t2);
-    dist_sq = len_squared_v3v3(co, nearest_tmp);
-
-    if (dist_sq < nearest->dist_sq) {
-      nearest->index = index;
-      nearest->dist_sq = dist_sq;
-      copy_v3_v3(nearest->co, nearest_tmp);
-      normal_tri_v3(nearest->no, t0, t1, t2);
-    }
-  }
-}
-
-/* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_faces.
- * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
-static void mesh_faces_spherecast(void *userdata,
-                                  int index,
-                                  const BVHTreeRay *ray,
-                                  BVHTreeRayHit *hit)
-{
-  const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
-  const MVert *vert = data->vert;
-  const MFace *face = &data->face[index];
-
-  const float *t0, *t1, *t2, *t3;
-  t0 = vert[face->v1].co;
-  t1 = vert[face->v2].co;
-  t2 = vert[face->v3].co;
-  t3 = face->v4 ? vert[face->v4].co : NULL;
-
-  do {
-    float dist;
-    if (ray->radius == 0.0f) {
-      dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
-    }
-    else {
-      dist = bvhtree_sphereray_tri_intersection(ray, ray->radius, hit->dist, t0, t1, t2);
-    }
-
-    if (dist >= 0 && dist < hit->dist) {
-      hit->index = index;
-      hit->dist = dist;
-      madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
-
-      normal_tri_v3(hit->no, t0, t1, t2);
-    }
-
-    t1 = t2;
-    t2 = t3;
-    t3 = NULL;
-
-  } while (t2);
-}
-/* copy of function above */
-static void mesh_looptri_spherecast(void *userdata,
-                                    int index,
-                                    const BVHTreeRay *ray,
-                                    BVHTreeRayHit *hit)
-{
-  const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
-  const MVert *vert = data->vert;
-  const MLoopTri *lt = &data->looptri[index];
-  const float *vtri_co[3] = {
-      vert[data->loop[lt->tri[0]].v].co,
-      vert[data->loop[lt->tri[1]].v].co,
-      vert[data->loop[lt->tri[2]].v].co,
-  };
-  float dist;
-
-  if (ray->radius == 0.0f) {
-    dist = bvhtree_ray_tri_intersection(ray, hit->dist, UNPACK3(vtri_co));
-  }
-  else {
-    dist = bvhtree_sphereray_tri_intersection(ray, ray->radius, hit->dist, UNPACK3(vtri_co));
-  }
-
-  if (dist >= 0 && dist < hit->dist) {
-    hit->index = index;
-    hit->dist = dist;
-    madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
-
-    normal_tri_v3(hit->no, UNPACK3(vtri_co));
-  }
-}
-/* copy of function above (warning, should de-duplicate with editmesh_bvh.c) */
-static void editmesh_looptri_spherecast(void *userdata,
-                                        int index,
-                                        const BVHTreeRay *ray,
-                                        BVHTreeRayHit *hit)
-{
-  const BVHTreeFromEditMesh *data = (BVHTreeFromEditMesh *)userdata;
-  BMEditMesh *em = data->em;
-  const BMLoop **ltri = (const BMLoop **)em->looptris[index];
-
-  const float *t0, *t1, *t2;
-  t0 = ltri[0]->v->co;
-  t1 = ltri[1]->v->co;
-  t2 = ltri[2]->v->co;
-
-  {
-    float dist;
-    if (ray->radius == 0.0f) {
-      dist = bvhtree_ray_tri_intersection(ray, hit->dist, t0, t1, t2);
-    }
-    else {
-      dist = bvhtree_sphereray_tri_intersection(ray, ray->radius, hit->dist, t0, t1, t2);
-    }
-
-    if (dist >= 0 && dist < hit->dist) {
-      hit->index = index;
-      hit->dist = dist;
-      madd_v3_v3v3fl(hit->co, ray->origin, ray->direction, dist);
-
-      normal_tri_v3(hit->no, t0, t1, t2);
-    }
-  }
-}
-
-/* Callback to bvh tree nearest point. The tree must have been built using bvhtree_from_mesh_edges.
- * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
-static void mesh_edges_nearest_point(void *userdata,
-                                     int index,
-                                     const float co[3],
-                                     BVHTreeNearest *nearest)
-{
-  const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
-  const MVert *vert = data->vert;
-  const MEdge *edge = data->edge + index;
-  float nearest_tmp[3], dist_sq;
-
-  const float *t0, *t1;
-  t0 = vert[edge->v1].co;
-  t1 = vert[edge->v2].co;
-
-  closest_to_line_segment_v3(nearest_tmp, co, t0, t1);
-  dist_sq = len_squared_v3v3(nearest_tmp, co);
-
-  if (dist_sq < nearest->dist_sq) {
-    nearest->index = index;
-    nearest->dist_sq = dist_sq;
-    copy_v3_v3(nearest->co, nearest_tmp);
-    sub_v3_v3v3(nearest->no, t0, t1);
-    normalize_v3(nearest->no);
-  }
-}
-
-/* Helper, does all the point-spherecast work actually. */
-static void mesh_verts_spherecast_do(int index,
-                                     const float v[3],
-                                     const BVHTreeRay *ray,
-                                     BVHTreeRayHit *hit)
-{
-  float dist;
-  const float *r1;
-  float r2[3], i1[3];
-  r1 = ray->origin;
-  add_v3_v3v3(r2, r1, ray->direction);
-
-  closest_to_line_segment_v3(i1, v, r1, r2);
-
-  /* No hit if closest point is 'behind' the origin of the ray, or too far away from it. */
-  if ((dot_v3v3v3(r1, i1, r2) >= 0.0f) && ((dist = len_v3v3(r1, i1)) < hit->dist)) {
-    hit->index = index;
-    hit->dist = dist;
-    copy_v3_v3(hit->co, i1);
-  }
-}
-
-static void editmesh_verts_spherecast(void *userdata,
-                                      int index,
-                                      const BVHTreeRay *ray,
-                                      BVHTreeRayHit *hit)
-{
-  const BVHTreeFromEditMesh *data = userdata;
-  BMVert *eve = BM_vert_at_index(data->em->bm, index);
-
-  mesh_verts_spherecast_do(index, eve->co, ray, hit);
-}
-
-/* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_verts.
- * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
-static void mesh_verts_spherecast(void *userdata,
-                                  int index,
-                                  const BVHTreeRay *ray,
-                                  BVHTreeRayHit *hit)
-{
-  const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
-  const float *v = data->vert[index].co;
-
-  mesh_verts_spherecast_do(index, v, ray, hit);
-}
-
-/* Callback to bvh tree raycast. The tree must have been built using bvhtree_from_mesh_edges.
- * userdata must be a BVHMeshCallbackUserdata built from the same mesh as the tree. */
-static void mesh_edges_spherecast(void *userdata,
-                                  int index,
-                                  const BVHTreeRay *ray,
-                                  BVHTreeRayHit *hit)
-{
-  const BVHTreeFromMesh *data = (BVHTreeFromMesh *)userdata;
-  const MVert *vert = data->vert;
-  const MEdge *edge = &data->edge[index];
-
-  const float radius_sq = square_f(ray->radius);
-  float dist;
-  const float *v1, *v2, *r1;
-  float r2[3], i1[3], i2[3];
-  v1 = vert[edge->v1].co;
-  v2 = vert[edge->v2].co;
-
-  /* In case we get a zero-length edge, handle it as a point! */
-  if (equals_v3v3(v1, v2)) {
-    mesh_verts_spherecast_do(index, v1, ray, hit);
-    return;
-  }
-
-  r1 = ray->origin;
-  add_v3_v3v3(r2, r1, ray->direction);
-
-  if (isect_line_line_v3(v1, v2, r1, r2, i1, i2)) {
-    /* No hit if intersection point is 'behind' the origin of the ray, or too far away from it. */
-    if ((dot_v3v3v3(r1, i2, r2) >= 0.0f) && ((dist = len_v3v3(r1, i2)) < hit->dist)) {
-      const float e_fac = line_point_factor_v3(i1, v1, v2);
-      if (e_fac < 0.0f) {
-        copy_v3_v3(i1, v1);
-      }
-      else if (e_fac > 1.0f) {
-        copy_v3_v3(i1, v2);
-      }
-      /* Ensure ray is really close enough from edge! */
-      if (len_squared_v3v3(i1, i2) <= radius_sq) {
-        hit->index = index;
-        hit->dist = dist;
-        copy_v3_v3(hit->co, i2);
-      }
-    }
-  }
-}
-
-/** \} */
-
-/*
- * BVH builders
- */
-
-/* -------------------------------------------------------------------- */
-/** \name Vertex Builder
- * \{ */
-
-static BVHTree *bvhtree_from_editmesh_verts_create_tree(float epsilon,
-                                                        int tree_type,
-                                                        int axis,
-                                                        BMEditMesh *em,
-                                                        const BLI_bitmap *verts_mask,
-                                                        int verts_num_active)
-{
-  BM_mesh_elem_table_ensure(em->bm, BM_VERT);
-  const int verts_num = em->bm->totvert;
-  if (verts_mask) {
-    BLI_assert(IN_RANGE_INCL(verts_num_active, 0, verts_num));
-  }
-  else {
-    verts_num_active = verts_num;
-  }
-
-  BVHTree *tree = BLI_bvhtree_new(verts_num_active, epsilon, tree_type, axis);
-
-  if (tree) {
-    for (int i = 0; i < verts_num; i++) {
-      if (verts_mask && !BLI_BITMAP_TEST_BOOL(verts_mask, i)) {
-        continue;
-      }
-      BMVert *eve = BM_vert_at_index(em->bm, i);
-      BLI_bvhtree_insert(tree, i, eve->co, 1);
-    }
-    BLI_assert(BLI_bvhtree_get_len(tree) == verts_num_active);
-  }
-
-  return tree;
-}
-
-static BVHTree *bvhtree_from_mesh_verts_create_tree(float epsilon,
-                                                    int tree_type,
-                                                    int axis,
-                                                    const MVert *vert,
-                                                    const int verts_num,
-                                                    const BLI_bitmap *verts_mask,
-                                                    int verts_num_active)
-{
-  BVHTree *tree = NULL;
-
-  if (verts_mask) {
-    BLI_assert(IN_RANGE_INCL(verts_num_active, 0, verts_num));
-  }
-  else {
-    verts_num_active = verts_num;
-  }
-
-  if (verts_num_active) {
-    tree = BLI_bvhtree_new(verts_num_active, epsilon, tree_type, axis);
-
-    if (tree) {
-      for (int i = 0; i < verts_num; i++) {
-        if (verts_mask && !BLI_BITMAP_TEST_BOOL(verts_mask, i)) {
-          continue;
-        }
-        BLI_bvhtree_insert(tree, i, vert[i].co, 1);
-      }
-      BLI_assert(BLI_bvhtree_get_len(tree) == verts_num_active);
-    }
-  }
-
-  return tree;
-}
-
-static void bvhtree_from_mesh_verts_setup_data(BVHTreeFromMesh *data,
-                                               BVHTree *tree,
-                                               const bool is_cached,
-                                               const MVert *vert,
-                                               const bool vert_allocated)
-{
-  memset(data, 0, sizeof(*data));
-
-  data->tree = tree;
-  data->cached = is_cached;
-
-  /* a NULL nearest callback works fine
-   * remember the min distance to point is the same as the min distance to BV of point */
-  data->nearest_callback = NULL;
-  data->raycast_callback = mesh_verts_spherecast;
-
-  data->vert = vert;
-  data->vert_allocated = vert_allocated;
-}
-
-/* Builds a bvh tree where nodes are the vertices of the given em */
-BVHTree *bvhtree_from_editmesh_verts_ex(BVHTreeFromEditMesh *data,
-                                        BMEditMesh *em,
-                                        const BLI_bitmap *verts_mask,
-                                        int verts_num_active,
-                                        float epsilon,
-                                        int tree_type,
-                                        int axis,
-                                        const BVHCacheType bvh_cache_type,
-                                        BVHCache **bvh_cache_p,
-                                        ThreadMutex *mesh_eval_mutex)
-{
-  BVHTree *tree = NULL;
-
-  if (bvh_cache_p) {
-    bool lock_started = false;
-    data->cached = bvhcache_find(
-        bvh_cache_p, bvh_cache_type, &data->tree, &lock_started, mesh_eval_mutex);
-
-    if (data->cached == false) {
-      tree = bvhtree_from_editmesh_verts_create_tree(
-          epsilon, tree_type, axis, em, verts_mask, verts_num_active);
-      bvhtree_balance(tree, true);
-
-      /* Save on cache for later use */
-      /* printf("BVHTree built and saved on cache\n"); */
-      bvhcache_insert(*bvh_cache_p, tree, bvh_cache_type);
-      data->cached = true;
-    }
-    bvhcache_unlock(*bvh_cache_p, lock_started);
-  }
-  else {
-    tree = bvhtree_from_editmesh_verts_create_tree(
-        epsilon, tree_type, axis, em, verts_mask, verts_num_active);
-    bvhtree_balance(tree, false);
-  }
-
-  if (tree) {
-    memset(data, 0, sizeof(*data));
-    data->tree = tree;
-    data->em = em;
-    data->nearest_callback = NULL;
-    data->raycast_callback = editmesh_verts_spherecast;
-    data->cached = bvh_cache_p != NULL;
-  }
-
-  return tree;
-}
-
-BVHTree *bvhtree_from_editmesh_verts(
-    BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis)
-{
-  return bvhtree_from_editmesh_verts_ex(
-      data, em, NULL, -1, epsilon, tree_type, axis, 0, NULL, NULL);
-}
-
-/**
- * Builds a bvh tree where nodes are the given vertices (note: does not copy given mverts!).
- * \param vert_allocated: if true, vert freeing will be done when freeing data.
- * \param verts_mask: if not null, true elements give which vert to add to BVH tree.
- * \param verts_num_active: if >= 0, number of active verts to add to BVH tree
- * (else will be computed from mask).
- */
-BVHTree *bvhtree_from_mesh_verts_ex(BVHTreeFromMesh *data,
-                                    const MVert *vert,
-                                    const int verts_num,
-                                    const bool vert_allocated,
-                                    const BLI_bitmap *verts_mask,
-                                    int verts_num_active,
-                                    float epsilon,
-                                    int tree_type,
-                                    int axis,
-                                    const BVHCacheType bvh_cache_type,
-                                    BVHCache **bvh_cache_p,
-                                    ThreadMutex *mesh_eval_mutex)
-{
-  bool in_cache = false;
-  bool lock_started = false;
-  BVHTree *tree = NULL;
-  if (bvh_cache_p) {
-    in_cache = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
-  }
-
-  if (in_cache == false) {
-    tree = bvhtree_from_mesh_verts_create_tree(
-        epsilon, tree_type, axis, vert, verts_num, verts_mask, verts_num_active);
-    bvhtree_balance(tree, bvh_cache_p != NULL);
-
-    if (bvh_cache_p) {
-      /* Save on cache for later use */
-      /* printf("BVHTree built and saved on cache\n"); */
-      BVHCache *bvh_cache = *bvh_cache_p;
-      bvhcache_insert(bvh_cache, tree, bvh_cache_type);
-      in_cache = true;
-    }
-  }
-
-  if (bvh_cache_p) {
-    bvhcache_unlock(*bvh_cache_p, lock_started);
-  }
-
-  /* Setup BVHTreeFromMesh */
-  bvhtree_from_mesh_verts_setup_data(data, tree, in_cache, vert, vert_allocated);
-
-  return tree;
-}
-
-/** \} */
-
-/* -------------------------------------------------------------------- */
-/** \name Edge Builder
- * \{ */
-
-static BVHTree *bvhtree_from_editmesh_edges_create_tree(float epsilon,
-                                                        int tree_type,
-                                                        int axis,
-                                                        BMEditMesh *em,
-                                                        const BLI_bitmap *edges_mask,
-                                                        int edges_num_active)
-{
-  BM_mesh_elem_table_ensure(em->bm, BM_EDGE);
-  const int edges_num = em->bm->totedge;
-
-  if (edges_mask) {
-    BLI_assert(IN_RANGE_INCL(edges_num_active, 0, edges_num));
-  }
-  else {
-    edges_num_active = edges_num;
-  }
-
-  BVHTree *tree = BLI_bvhtree_new(edges_num_active, epsilon, tree_type, axis);
-
-  if (tree) {
-    int i;
-    BMIter iter;
-    BMEdge *eed;
-    BM_ITER_MESH_INDEX (eed, &iter, em->bm, BM_EDGES_OF_MESH, i) {
-      if (edges_mask && !BLI_BITMAP_TEST_BOOL(edges_mask, i)) {
-        continue;
-      }
-      float co[2][3];
-      copy_v3_v3(co[0], eed->v1->co);
-      copy_v3_v3(co[1], eed->v2->co);
-
-      BLI_bvhtree_insert(tree, i, co[0], 2);
-    }
-    BLI_assert(BLI_bvhtree_get_len(tree) == edges_num_active);
-  }
-
-  return tree;
-}
-
-static BVHTree *bvhtree_from_mesh_edges_create_tree(const MVert *vert,
-                                                    const MEdge *edge,
-                                                    const int edge_num,
-                                                    const BLI_bitmap *edges_mask,
-                                                    int edges_num_active,
-                                                    float epsilon,
-                                                    int tree_type,
-                                                    int axis)
-{
-  BVHTree *tree = NULL;
-
-  if (edges_mask) {
-    BLI_assert(IN_RANGE_INCL(edges_num_active, 0, edge_num));
-  }
-  else {
-    edges_num_active = edge_num;
-  }
-
-  if (edges_num_active) {
-    /* Create a bvh-tree of the given target */
-    tree = BLI_bvhtree_new(edges_num_active, epsilon, tree_type, axis);
-    if (tree) {
-      for (int i = 0; i < edge_num; i++) {
-        if (edges_mask && !BLI_BITMAP_TEST_BOOL(edges_mask, i)) {
-          continue;
-        }
-        float co[2][3];
-        copy_v3_v3(co[0], vert[edge[i].v1].co);
-        copy_v3_v3(co[1], vert[edge[i].v2].co);
-
-        BLI_bvhtree_insert(tree, i, co[0], 2);
-      }
-    }
-  }
-
-  return tree;
-}
-
-static void bvhtree_from_mesh_edges_setup_data(BVHTreeFromMesh *data,
-                                               BVHTree *tree,
-                                               const bool is_cached,
-                                               const MVert *vert,
-                                               const bool vert_allocated,
-                                               const MEdge *edge,
-                                               const bool edge_allocated)
-{
-  memset(data, 0, sizeof(*data));
-
-  data->tree = tree;
-
-  data->cached = is_cached;
-
-  data->nearest_callback = mesh_edges_nearest_point;
-  data->raycast_callback = mesh_edges_spherecast;
-
-  data->vert = vert;
-  data->vert_allocated = vert_allocated;
-  data->edge = edge;
-  data->edge_allocated = edge_allocated;
-}
-
-/* Builds a bvh tree where nodes are the edges of the given em */
-BVHTree *bvhtree_from_editmesh_edges_ex(BVHTreeFromEditMesh *data,
-                                        BMEditMesh *em,
-                                        const BLI_bitmap *edges_mask,
-                                        int edges_num_active,
-                                        float epsilon,
-                                        int tree_type,
-                                        int axis,
-                                        const BVHCacheType bvh_cache_type,
-                                        BVHCache **bvh_cache_p,
-                                        ThreadMutex *mesh_eval_mutex)
-{
-  BVHTree *tree = NULL;
-
-  if (bvh_cache_p) {
-    bool lock_started = false;
-    data->cached = bvhcache_find(
-        bvh_cache_p, bvh_cache_type, &data->tree, &lock_started, mesh_eval_mutex);
-    BVHCache *bvh_cache = *bvh_cache_p;
-    if (data->cached == false) {
-      tree = bvhtree_from_editmesh_edges_create_tree(
-          epsilon, tree_type, axis, em, edges_mask, edges_num_active);
-      bvhtree_balance(tree, true);
-      /* Save on cache for later use */
-      /* printf("BVHTree built and saved on cache\n"); */
-      bvhcache_insert(bvh_cache, tree, bvh_cache_type);
-      data->cached = true;
-    }
-    bvhcache_unlock(bvh_cache, lock_started);
-  }
-  else {
-    tree = bvhtree_from_editmesh_edges_create_tree(
-        epsilon, tree_type, axis, em, edges_mask, edges_num_active);
-    bvhtree_balance(tree, false);
-  }
-
-  if (tree) {
-    memset(data, 0, sizeof(*data));
-    data->tree = tree;
-    data->em = em;
-    data->nearest_callback = NULL; /* TODO */
-    data->raycast_callback = NULL; /* TODO */
-    data->cached = bvh_cache_p != NULL;
-  }
-
-  return tree;
-}
-
-BVHTree *bvhtree_from_editmesh_edges(
-    BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis)
-{
-  return bvhtree_from_editmesh_edges_ex(
-      data, em, NULL, -1, epsilon, tree_type, axis, 0, NULL, NULL);
-}
-
-/**
- * Builds a bvh tree where nodes are the given edges .
- * \param vert, vert_allocated: if true, elem freeing will be done when freeing data.
- * \param edge, edge_allocated: if true, elem freeing will be done when freeing data.
- * \param edges_mask: if not null, true elements give which vert to add to BVH tree.
- * \param edges_num_active: if >= 0, number of active edges to add to BVH tree
- * (else will be computed from mask).
- */
-BVHTree *bvhtree_from_mesh_edges_ex(BVHTreeFromMesh *data,
-                                    const MVert *vert,
-                                    const bool vert_allocated,
-                                    const MEdge *edge,
-                                    const int edges_num,
-                                    const bool edge_allocated,
-                                    const BLI_bitmap *edges_mask,
-                                    int edges_num_active,
-                                    float epsilon,
-                                    int tree_type,
-                                    int axis,
-                                    const BVHCacheType bvh_cache_type,
-                                    BVHCache **bvh_cache_p,
-                                    ThreadMutex *mesh_eval_mutex)
-{
-  bool in_cache = false;
-  bool lock_started = false;
-  BVHTree *tree = NULL;
-  if (bvh_cache_p) {
-    in_cache = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
-  }
-
-  if (in_cache == false) {
-    tree = bvhtree_from_mesh_edges_create_tree(
-        vert, edge, edges_num, edges_mask, edges_num_active, epsilon, tree_type, axis);
-
-    if (bvh_cache_p) {
-      bvhtree_balance(tree, true);
-
-      BVHCache *bvh_cache = *bvh_cache_p;
-      /* Save on cache for later use */
-      /* printf("BVHTree built and saved on cache\n"); */
-      bvhcache_insert(bvh_cache, tree, bvh_cache_type);
-      in_cache = true;
-    }
-    else {
-      bvhtree_balance(tree, false);
-    }
-  }
-
-  if (bvh_cache_p) {
-    bvhcache_unlock(*bvh_cache_p, lock_started);
-  }
-
-  /* Setup BVHTreeFromMesh */
-  bvhtree_from_mesh_edges_setup_data(
-      data, tree, in_cache, vert, vert_allocated, edge, edge_allocated);
-
-  return tree;
-}
-
-/** \} */
-
-/* -------------------------------------------------------------------- */
-/** \name Tessellated Face Builder
- * \{ */
-
-static BVHTree *bvhtree_from_mesh_faces_create_tree(float epsilon,
-                                                    int tree_type,
-                                                    int axis,
-                                                    const MVert *vert,
-                                                    const MFace *face,
-                                                    const int faces_num,
-                                                    const BLI_bitmap *faces_mask,
-                                                    int faces_num_active)
-{
-  BVHTree *tree = NULL;
-
-  if (faces_num) {
-    if (faces_mask) {
-      BLI_assert(IN_RANGE_INCL(faces_num_active, 0, faces_num));
-    }
-    else {
-      faces_num_active = faces_num;
-    }
-
-    /* Create a bvh-tree of the given target */
-    /* printf("%s: building BVH, total=%d\n", __func__, numFaces); */
-    tree = BLI_bvhtree_new(faces_num_active, epsilon, tree_type, axis);
-    if (tree) {
-      if (vert && face) {
-        for (int i = 0; i < faces_num; i++) {
-          float co[4][3];
-          if (faces_mask && !BLI_BITMAP_TEST_BOOL(faces_mask, i)) {
-            continue;
-          }
-
-          copy_v3_v3(co[0], vert[face[i].v1].co);
-          copy_v3_v3(co[1], vert[face[i].v2].co);
-          copy_v3_v3(co[2], vert[face[i].v3].co);
-          if (face[i].v4) {
-            copy_v3_v3(co[3], vert[face[i].v4].co);
-          }
-
-          BLI_bvhtree_insert(tree, i, co[0], face[i].v4 ? 4 : 3);
-        }
-      }
-      BLI_assert(BLI_bvhtree_get_len(tree) == faces_num_active);
-    }
-  }
-
-  return tree;
-}
-
-static void bvhtree_from_mesh_faces_setup_data(BVHTreeFromMesh *data,
-                                               BVHTree *tree,
-                                               const bool is_cached,
-                                               const MVert *vert,
-                                               const bool vert_allocated,
-                                               const MFace *face,
-                                               const bool face_allocated)
-{
-  memset(data, 0, sizeof(*data));
-
-  data->tree = tree;
-  data->cached = is_cached;
-
-  data->nearest_callback = mesh_faces_nearest_point;
-  data->raycast_callback = mesh_faces_spherecast;
-
-  data->vert = vert;
-  data->vert_allocated = vert_allocated;
-  data->face = face;
-  data->face_allocated = face_allocated;
-}
-
-/**
- * Builds a bvh tree where nodes are the given tessellated faces
- * (note: does not copy given mfaces!).
- * \param vert_allocated: if true, vert freeing will be done when freeing data.
- * \param face_allocated: if true, face freeing will be done when freeing data.
- * \param faces_mask: if not null, true elements give which faces to add to BVH tree.
- * \param faces_num_active: if >= 0, number of active faces to add to BVH tree
- * (else will be computed from mask).
- */
-BVHTree *bvhtree_from_mesh_faces_ex(BVHTreeFromMesh *data,
-                                    const MVert *vert,
-                                    const bool vert_allocated,
-                                    const MFace *face,
-                                    const int numFaces,
-                                    const bool face_allocated,
-                                    const BLI_bitmap *faces_mask,
-                                    int faces_num_active,
-                                    float epsilon,
-                                    int tree_type,
-                                    int axis,
-                                    const BVHCacheType bvh_cache_type,
-                                    BVHCache **bvh_cache_p,
-                                    ThreadMutex *mesh_eval_mutex)
-{
-  bool in_cache = false;
-  bool lock_started = false;
-  BVHTree *tree = NULL;
-  if (bvh_cache_p) {
-    in_cache = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
-  }
-
-  if (in_cache == false) {
-    tree = bvhtree_from_mesh_faces_create_tree(
-        epsilon, tree_type, axis, vert, face, numFaces, faces_mask, faces_num_active);
-    bvhtree_balance(tree, bvh_cache_p != NULL);
-
-    if (bvh_cache_p) {
-      /* Save on cache for later use */
-      /* printf("BVHTree built and saved on cache\n"); */
-      BVHCache *bvh_cache = *bvh_cache_p;
-      bvhcache_insert(bvh_cache, tree, bvh_cache_type);
-      in_cache = true;
-    }
-  }
-
-  if (bvh_cache_p) {
-    bvhcache_unlock(*bvh_cache_p, lock_started);
-  }
-
-  /* Setup BVHTreeFromMesh */
-  bvhtree_from_mesh_faces_setup_data(
-      data, tree, in_cache, vert, vert_allocated, face, face_allocated);
-
-  return tree;
-}
-
-/** \} */
-
-/* -------------------------------------------------------------------- */
-/** \name LoopTri Face Builder
- * \{ */
-
-static BVHTree *bvhtree_from_editmesh_looptri_create_tree(float epsilon,
-                                                          int tree_type,
-                                                          int axis,
-                                                          BMEditMesh *em,
-                                                          const BLI_bitmap *looptri_mask,
-                                                          int looptri_num_active)
-{
-  BVHTree *tree = NULL;
-  const int looptri_num = em->tottri;
-
-  if (looptri_num) {
-    if (looptri_mask) {
-      BLI_assert(IN_RANGE_INCL(looptri_num_active, 0, looptri_num));
-    }
-    else {
-      looptri_num_active = looptri_num;
-    }
-
-    /* Create a bvh-tree of the given target */
-    /* printf("%s: building BVH, total=%d\n", __func__, numFaces); */
-    tree = BLI_bvhtree_new(looptri_num_active, epsilon, tree_type, axis);
-    if (tree) {
-      const struct BMLoop *(*looptris)[3] = (void *)em->looptris;
-
-      /* Insert BMesh-tessellation triangles into the bvh tree, unless they are hidden
-       * and/or selected. Even if the faces themselves are not selected for the snapped
-       * transform, having a vertex selected means the face (and thus it's tessellated
-       * triangles) will be moving and will not be a good snap targets. */
-      for (int i = 0; i < looptri_num; i++) {
-        const BMLoop **ltri = looptris[i];
-        bool insert = looptri_mask ? BLI_BITMAP_TEST_BOOL(looptri_mask, i) : true;
-
-        if (insert) {
-          /* No reason found to block hit-testing the triangle for snap, so insert it now. */
-          float co[3][3];
-          copy_v3_v3(co[0], ltri[0]->v->co);
-          copy_v3_v3(co[1], ltri[1]->v->co);
-          copy_v3_v3(co[2], ltri[2]->v->co);
-
-          BLI_bvhtree_insert(tree, i, co[0], 3);
-        }
-      }
-      BLI_assert(BLI_bvhtree_get_len(tree) == looptri_num_active);
-    }
-  }
-
-  return tree;
-}
-
-static BVHTree *bvhtree_from_mesh_looptri_create_tree(float epsilon,
-                                                      int tree_type,
-                                                      int axis,
-                                                      const MVert *vert,
-                                                      const MLoop *mloop,
-                                                      const MLoopTri *looptri,
-                                                      const int looptri_num,
-                                                      const BLI_bitmap *looptri_mask,
-                                                      int looptri_num_active)
-{
-  BVHTree *tree = NULL;
-
-  if (looptri_mask) {
-    BLI_assert(IN_RANGE_INCL(looptri_num_active, 0, looptri_num));
-  }
-  else {
-    looptri_num_active = looptri_num;
-  }
-
-  if (looptri_num_active) {
-    /* Create a bvh-tree of the given target */
-    /* printf("%s: building BVH, total=%d\n", __func__, numFaces); */
-    tree = BLI_bvhtree_new(looptri_num_active, epsilon, tree_type, axis);
-    if (tree) {
-      if (vert && looptri) {
-        for (int i = 0; i < looptri_num; i++) {
-          float co[3][3];
-          if (looptri_mask && !BLI_BITMAP_TEST_BOOL(looptri_mask, i)) {
-            continue;
-          }
-
-          copy_v3_v3(co[0], vert[mloop[looptri[i].tri[0]].v].co);
-          copy_v3_v3(co[1], vert[mloop[looptri[i].tri[1]].v].co);
-          copy_v3_v3(co[2], vert[mloop[looptri[i].tri[2]].v].co);
-
-          BLI_bvhtree_insert(tree, i, co[0], 3);
-        }
-      }
-      BLI_assert(BLI_bvhtree_get_len(tree) == looptri_num_active);
-    }
-  }
-
-  return tree;
-}
-
-static void bvhtree_from_mesh_looptri_setup_data(BVHTreeFromMesh *data,
-                                                 BVHTree *tree,
-                                                 const bool is_cached,
-                                                 const MVert *vert,
-                                                 const bool vert_allocated,
-                                                 const MLoop *mloop,
-                                                 const bool loop_allocated,
-                                                 const MLoopTri *looptri,
-                                                 const bool looptri_allocated)
-{
-  memset(data, 0, sizeof(*data));
-
-  data->tree = tree;
-  data->cached = is_cached;
-
-  data->nearest_callback = mesh_looptri_nearest_point;
-  data->raycast_callback = mesh_looptri_spherecast;
-
-  data->vert = vert;
-  data->vert_allocated = vert_allocated;
-  data->loop = mloop;
-  data->loop_allocated = loop_allocated;
-  data->looptri = looptri;
-  data->looptri_allocated = looptri_allocated;
-}
-
-/**
- * Builds a bvh tree where nodes are the looptri faces of the given bm
- */
-BVHTree *bvhtree_from_editmesh_looptri_ex(BVHTreeFromEditMesh *data,
-                                          BMEditMesh *em,
-                                          const BLI_bitmap *looptri_mask,
-                                          int looptri_num_active,
-                                          float epsilon,
-                                          int tree_type,
-                                          int axis,
-                                          const BVHCacheType bvh_cache_type,
-                                          BVHCache **bvh_cache_p,
-                                          ThreadMutex *mesh_eval_mutex)
-{
-  /* BMESH specific check that we have tessfaces,
-   * we _could_ tessellate here but rather not - campbell */
-
-  BVHTree *tree = NULL;
-  if (bvh_cache_p) {
-    bool lock_started = false;
-    bool in_cache = bvhcache_find(
-        bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
-    BVHCache *bvh_cache = *bvh_cache_p;
-    bvhtree_balance(tree, true);
-
-    if (in_cache == false) {
-      tree = bvhtree_from_editmesh_looptri_create_tree(
-          epsilon, tree_type, axis, em, looptri_mask, looptri_num_active);
-
-      /* Save on cache for later use */
-      /* printf("BVHTree built and saved on cache\n"); */
-      bvhcache_insert(bvh_cache, tree, bvh_cache_type);
-    }
-    bvhcache_unlock(bvh_cache, lock_started);
-  }
-  else {
-    tree = bvhtree_from_editmesh_looptri_create_tree(
-        epsilon, tree_type, axis, em, looptri_mask, looptri_num_active);
-    bvhtree_balance(tree, false);
-  }
-
-  if (tree) {
-    data->tree = tree;
-    data->nearest_callback = editmesh_looptri_nearest_point;
-    data->raycast_callback = editmesh_looptri_spherecast;
-    data->em = em;
-    data->cached = bvh_cache_p != NULL;
-  }
-  return tree;
-}
-
-BVHTree *bvhtree_from_editmesh_looptri(
-    BVHTreeFromEditMesh *data, BMEditMesh *em, float epsilon, int tree_type, int axis)
-{
-  return bvhtree_from_editmesh_looptri_ex(
-      data, em, NULL, -1, epsilon, tree_type, axis, 0, NULL, NULL);
-}
-
-/**
- * Builds a bvh tree where nodes are the looptri faces of the given dm
- *
- * \note for editmesh this is currently a duplicate of bvhtree_from_mesh_faces_ex
- */
-BVHTree *bvhtree_from_mesh_looptri_ex(BVHTreeFromMesh *data,
-                                      const struct MVert *vert,
-                                      const bool vert_allocated,
-                                      const struct MLoop *mloop,
-                                      const bool loop_allocated,
-                                      const struct MLoopTri *looptri,
-                                      const int looptri_num,
-                                      const bool looptri_allocated,
-                                      const BLI_bitmap *looptri_mask,
-                                      int looptri_num_active,
-                                      float epsilon,
-                                      int tree_type,
-                                      int axis,
-                                      const BVHCacheType bvh_cache_type,
-                                      BVHCache **bvh_cache_p,
-                                      ThreadMutex *mesh_eval_mutex)
-{
-  bool in_cache = false;
-  bool lock_started = false;
-  BVHTree *tree = NULL;
-  if (bvh_cache_p) {
-    in_cache = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, &lock_started, mesh_eval_mutex);
-  }
-
-  if (in_cache == false) {
-    /* Setup BVHTreeFromMesh */
-    tree = bvhtree_from_mesh_looptri_create_tree(epsilon,
-                                                 tree_type,
-                                                 axis,
-                                                 vert,
-                                                 mloop,
-                                                 looptri,
-                                                 looptri_num,
-                                                 looptri_mask,
-                                                 looptri_num_active);
-
-    bvhtree_balance(tree, bvh_cache_p != NULL);
-
-    if (bvh_cache_p) {
-      BVHCache *bvh_cache = *bvh_cache_p;
-      bvhcache_insert(bvh_cache, tree, bvh_cache_type);
-      in_cache = true;
-    }
-  }
-
-  if (bvh_cache_p) {
-    bvhcache_unlock(*bvh_cache_p, lock_started);
-  }
-
-  /* Setup BVHTreeFromMesh */
-  bvhtree_from_mesh_looptri_setup_data(data,
-                                       tree,
-                                       in_cache,
-                                       vert,
-                                       vert_allocated,
-                                       mloop,
-                                       loop_allocated,
-                                       looptri,
-                                       looptri_allocated);
-
-  return tree;
-}
-
-static BLI_bitmap *loose_verts_map_get(const MEdge *medge,
-                                       int edges_num,
-                                       const MVert *UNUSED(mvert),
-                                       int verts_num,
-                                       int *r_loose_vert_num)
-{
-  BLI_bitmap *loose_verts_mask = BLI_BITMAP_NEW(verts_num, __func__);
-  BLI_bitmap_set_all(loose_verts_mask, true, verts_num);
-
-  const MEdge *e = medge;
-  int num_linked_verts = 0;
-  for (; edges_num--; e++) {
-    if (BLI_BITMAP_TEST(loose_verts_mask, e->v1)) {
-      BLI_BITMAP_DISABLE(loose_verts_mask, e->v1);
-      num_linked_verts++;
-    }
-    if (BLI_BITMAP_TEST(loose_verts_mask, e->v2)) {
-      BLI_BITMAP_DISABLE(loose_verts_mask, e->v2);
-      num_linked_verts++;
-    }
-  }
-
-  *r_loose_vert_num = verts_num - num_linked_verts;
-
-  return loose_verts_mask;
-}
-
-static BLI_bitmap *loose_edges_map_get(const MEdge *medge,
-                                       const int edges_len,
-                                       int *r_loose_edge_len)
-{
-  BLI_bitmap *loose_edges_mask = BLI_BITMAP_NEW(edges_len, __func__);
-
-  int loose_edges_len = 0;
-  const MEdge *e = medge;
-  for (int i = 0; i < edges_len; i++, e++) {
-    if (e->flag & ME_LOOSEEDGE) {
-      BLI_BITMAP_ENABLE(loose_edges_mask, i);
-      loose_edges_len++;
-    }
-    else {
-      BLI_BITMAP_DISABLE(loose_edges_mask, i);
-    }
-  }
-
-  *r_loose_edge_len = loose_edges_len;
-
-  return loose_edges_mask;
-}
-
-static BLI_bitmap *looptri_no_hidden_map_get(const MPoly *mpoly,
-                                             const int looptri_len,
-                                             int *r_looptri_active_len)
-{
-  BLI_bitmap *looptri_mask = BLI_BITMAP_NEW(looptri_len, __func__);
-
-  int looptri_no_hidden_len = 0;
-  int looptri_iter = 0;
-  const MPoly *mp = mpoly;
-  while (looptri_iter != looptri_len) {
-    int mp_totlooptri = mp->totloop - 2;
-    if (mp->flag & ME_HIDE) {
-      looptri_iter += mp_totlooptri;
-    }
-    else {
-      while (mp_totlooptri--) {
-        BLI_BITMAP_ENABLE(looptri_mask, looptri_iter);
-        looptri_iter++;
-        looptri_no_hidden_len++;
-      }
-    }
-    mp++;
-  }
-
-  *r_looptri_active_len = looptri_no_hidden_len;
-
-  return looptri_mask;
-}
-
-/**
- * Builds or queries a bvhcache for the cache bvhtree of the request type.
- */
-BVHTree *BKE_bvhtree_from_mesh_get(struct BVHTreeFromMesh *data,
-                                   struct Mesh *mesh,
-                                   const BVHCacheType bvh_cache_type,
-                                   const int tree_type)
-{
-  BVHTree *tree = NULL;
-  BVHCache **bvh_cache_p = (BVHCache **)&mesh->runtime.bvh_cache;
-  ThreadMutex *mesh_eval_mutex = (ThreadMutex *)mesh->runtime.eval_mutex;
-
-  bool is_cached = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, NULL, NULL);
-
-  if (is_cached && tree == NULL) {
-    memset(data, 0, sizeof(*data));
-    return tree;
-  }
-
-  switch (bvh_cache_type) {
-    case BVHTREE_FROM_VERTS:
-    case BVHTREE_FROM_LOOSEVERTS:
-      if (is_cached == false) {
-        BLI_bitmap *loose_verts_mask = NULL;
-        int loose_vert_len = -1;
-        int verts_len = mesh->totvert;
-
-        if (bvh_cache_type == BVHTREE_FROM_LOOSEVERTS) {
-          loose_verts_mask = loose_verts_map_get(
-              mesh->medge, mesh->totedge, mesh->mvert, verts_len, &loose_vert_len);
-        }
-
-        tree = bvhtree_from_mesh_verts_ex(data,
-                                          mesh->mvert,
-                                          verts_len,
-                                          false,
-                                          loose_verts_mask,
-                                          loose_vert_len,
-                                          0.0f,
-                                          tree_type,
-                                          6,
-                                          bvh_cache_type,
-                                          bvh_cache_p,
-                                          mesh_eval_mutex);
-
-        if (loose_verts_mask != NULL) {
-          MEM_freeN(loose_verts_mask);
-        }
-      }
-      else {
-        /* Setup BVHTreeFromMesh */
-        bvhtree_from_mesh_verts_setup_data(data, tree, true, mesh->mvert, false);
-      }
-      break;
-
-    case BVHTREE_FROM_EDGES:
-    case BVHTREE_FROM_LOOSEEDGES:
-      if (is_cached == false) {
-        BLI_bitmap *loose_edges_mask = NULL;
-        int loose_edges_len = -1;
-        int edges_len = mesh->totedge;
-
-        if (bvh_cache_type == BVHTREE_FROM_LOOSEEDGES) {
-          loose_edges_mask = loose_edges_map_get(mesh->medge, edges_len, &loose_edges_len);
-        }
-
-        tree = bvhtree_from_mesh_edges_ex(data,
-                                          mesh->mvert,
-                                          false,
-                                          mesh->medge,
-                                          edges_len,
-                                          false,
-                                          loose_edges_mask,
-                                          loose_edges_len,
-                                          0.0,
-                                          tree_type,
-                                          6,
-                                          bvh_cache_type,
-                                          bvh_cache_p,
-                                          mesh_eval_mutex);
-
-        if (loose_edges_mask != NULL) {
-          MEM_freeN(loose_edges_mask);
-        }
-      }
-      else {
-        /* Setup BVHTreeFromMesh */
-        bvhtree_from_mesh_edges_setup_data(
-            data, tree, true, mesh->mvert, false, mesh->medge, false);
-      }
-      break;
-
-    case BVHTREE_FROM_FACES:
-      if (is_cached == false) {
-        int num_faces = mesh->totface;
-        BLI_assert(!(num_faces == 0 && mesh->totpoly != 0));
-
-        tree = bvhtree_from_mesh_faces_ex(data,
-                                          mesh->mvert,
-                                          false,
-                                          mesh->mface,
-                                          num_faces,
-                                          false,
-                                          NULL,
-                                          -1,
-                                          0.0,
-                                          tree_type,
-                                          6,
-                                          bvh_cache_type,
-                                          bvh_cache_p,
-                                          mesh_eval_mutex);
-      }
-      else {
-        /* Setup BVHTreeFromMesh */
-        bvhtree_from_mesh_faces_setup_data(
-            data, tree, true, mesh->mvert, false, mesh->mface, false);
-      }
-      break;
-
-    case BVHTREE_FROM_LOOPTRI:
-    case BVHTREE_FROM_LOOPTRI_NO_HIDDEN:
-      if (is_cached == false) {
-        const MLoopTri *mlooptri = BKE_mesh_runtime_looptri_ensure(mesh);
-        int looptri_len = BKE_mesh_runtime_looptri_len(mesh);
-
-        int looptri_mask_active_len = -1;
-        BLI_bitmap *looptri_mask = NULL;
-        if (bvh_cache_type == BVHTREE_FROM_LOOPTRI_NO_HIDDEN) {
-          looptri_mask = looptri_no_hidden_map_get(
-              mesh->mpoly, looptri_len, &looptri_mask_active_len);
-        }
-
-        tree = bvhtree_from_mesh_looptri_ex(data,
-                                            mesh->mvert,
-                                            false,
-                                            mesh->mloop,
-                                            false,
-                                            mlooptri,
-                                            looptri_len,
-                                            false,
-                                            looptri_mask,
-                                            looptri_mask_active_len,
-                                            0.0,
-                                            tree_type,
-                                            6,
-                                            bvh_cache_type,
-                                            bvh_cache_p,
-                                            mesh_eval_mutex);
-
-        if (looptri_mask != NULL) {
-          MEM_freeN(looptri_mask);
-        }
-      }
-      else {
-        /* Setup BVHTreeFromMesh */
-        const MLoopTri *mlooptri = BKE_mesh_runtime_looptri_ensure(mesh);
-        bvhtree_from_mesh_looptri_setup_data(
-            data, tree, true, mesh->mvert, false, mesh->mloop, false, mlooptri, false);
-      }
-      break;
-    case BVHTREE_FROM_EM_VERTS:
-    case BVHTREE_FROM_EM_EDGES:
-    case BVHTREE_FROM_EM_LOOPTRI:
-    case BVHTREE_MAX_ITEM:
-      BLI_assert(false);
-      break;
-  }
-
-  if (data->tree != NULL) {
-#ifdef DEBUG
-    if (BLI_bvhtree_get_tree_type(data->tree) != tree_type) {
-      printf("tree_type %d obtained instead of %d\n",
-             BLI_bvhtree_get_tree_type(data->tree),
-             tree_type);
-    }
-#endif
-    BLI_assert(data->cached);
-  }
-  else {
-    free_bvhtree_from_mesh(data);
-    memset(data, 0, sizeof(*data));
-  }
-
-  return tree;
-}
-
-/**
- * Builds or queries a bvhcache for the cache bvhtree of the request type.
- */
-BVHTree *BKE_bvhtree_from_editmesh_get(BVHTreeFromEditMesh *data,
-                                       struct BMEditMesh *em,
-                                       const int tree_type,
-                                       const BVHCacheType bvh_cache_type,
-                                       BVHCache **bvh_cache_p,
-                                       ThreadMutex *mesh_eval_mutex)
-{
-  BVHTree *tree = NULL;
-  bool is_cached = false;
-
-  memset(data, 0, sizeof(*data));
-
-  if (bvh_cache_p) {
-    is_cached = bvhcache_find(bvh_cache_p, bvh_cache_type, &tree, NULL, NULL);
-
-    if (is_cached && tree == NULL) {
-      return tree;
-    }
-  }
-  data->tree = tree;
-  data->em = em;
-  data->cached = is_cached;
-
-  switch (bvh_cache_type) {
-    case BVHTREE_FROM_EM_VERTS:
-      if (is_cached == false) {
-        tree = bvhtree_from_editmesh_verts_ex(
-            data, em, NULL, -1, 0.0f, tree_type, 6, bvh_cache_type, bvh_cache_p, mesh_eval_mutex);
-      }
-      else {
-        data->nearest_callback = NULL;
-        data->raycast_callback = editmesh_verts_spherecast;
-      }
-      break;
-
-    case BVHTREE_FROM_EM_EDGES:
-      if (is_cached == false) {
-        tree = bvhtree_from_editmesh_edges_ex(
-            data, em, NULL, -1, 0.0f, tree_type, 6, bvh_cache_type, bvh_cache_p, mesh_eval_mutex);
-      }
-      else {
-        /* Setup BVHTreeFromMesh */
-        data->nearest_callback = NULL; /* TODO */
-        data->raycast_callback = NULL; /* TODO */
-      }
-      break;
-
-    case BVHTREE_FROM_EM_LOOPTRI:
-      if (is_cached == false) {
-        tree = bvhtree_from_editmesh_looptri_ex(
-            data, em, NULL, -1, 0.0f, tree_type, 6, bvh_cache_type, bvh_cache_p, mesh_eval_mutex);
-      }
-      else {
-        /* Setup BVHTreeFromMesh */
-        data->nearest_callback = editmesh_looptri_nearest_point;
-        data->raycast_callback = editmesh_looptri_spherecast;
-      }
-      break;
-    case BVHTREE_FROM_VERTS:
-    case BVHTREE_FROM_EDGES:
-    case BVHTREE_FROM_FACES:
-    case BVHTREE_FROM_LOOPTRI:
-    case BVHTREE_FROM_LOOPTRI_NO_HIDDEN:
-    case BVHTREE_FROM_LOOSEVERTS:
-    case BVHTREE_FROM_LOOSEEDGES:
-    case BVHTREE_MAX_ITEM:
-      BLI_assert(false);
-      break;
-  }
-
-  if (data->tree != NULL) {
-#ifdef DEBUG
-    if (BLI_bvhtree_get_tree_type(data->tree) != tree_type) {
-      printf("tree_type %d obtained instead of %d\n",
-             BLI_bvhtree_get_tree_type(data->tree),
-             tree_type);
-    }
-#endif
-    BLI_assert(data->cached);
-  }
-  else {
-    free_bvhtree_from_editmesh(data);
-    memset(data, 0, sizeof(*data));
-  }
-
-  return tree;
-}
-
-/** \} */
-
-/* Frees data allocated by a call to bvhtree_from_editmesh_*. */
-void free_bvhtree_from_editmesh(struct BVHTreeFromEditMesh *data)
-{
-  if (data->tree) {
-    if (!data->cached) {
-      BLI_bvhtree_free(data->tree);
-    }
-    memset(data, 0, sizeof(*data));
-  }
-}
-
-/* Frees data allocated by a call to bvhtree_from_mesh_*. */
-void free_bvhtree_from_mesh(struct BVHTreeFromMesh *data)
-{
-  if (data->tree && !data->cached) {
-    BLI_bvhtree_free(data->tree);
-  }
-
-  if (data->vert_allocated) {
-    MEM_freeN((void *)data->vert);
-  }
-  if (data->edge_allocated) {
-    MEM_freeN((void *)data->edge);
-  }
-  if (data->face_allocated) {
-    MEM_freeN((void *)data->face);
-  }
-  if (data->loop_allocated) {
-    MEM_freeN((void *)data->loop);
-  }
-  if (data->looptri_allocated) {
-    MEM_freeN((void *)data->looptri);
-  }
-
-  memset(data, 0, sizeof(*data));
-}
-
-/** \} */
-
-/* -------------------------------------------------------------------- */
-/** \name Point Cloud BVH Building
- * \{ */
-
-BVHTree *BKE_bvhtree_from_pointcloud_get(BVHTreeFromPointCloud *data,
-                                         const PointCloud *pointcloud,
-                                         const int tree_type)
-{
-  BVHTree *tree = BLI_bvhtree_new(pointcloud->totpoint, 0.0f, tree_type, 6);
-  if (!tree) {
-    return NULL;
-  }
-
-  for (int i = 0; i < pointcloud->totpoint; i++) {
-    BLI_bvhtree_insert(tree, i, pointcloud->co[i], 1);
-  }
-  BLI_assert(BLI_bvhtree_get_len(tree) == pointcloud->totpoint);
-  bvhtree_balance(tree, false);
-
-  data->coords = pointcloud->co;
-  data->tree = tree;
-  data->nearest_callback = NULL;
-
-  return tree;
-}
-
-void free_bvhtree_from_pointcloud(BVHTreeFromPointCloud *data)
-{
-  if (data->tree) {
-    BLI_bvhtree_free(data->tree);
-  }
-  memset(data, 0, sizeof(*data));
-}
-
-/** \} */