Edit Mesh: New option "Split Edges & Faces" to "AutoMerge"

Ref T66423

Differential revision: https://developer.blender.org/D5562

2 files changed, 95 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_kdopbvh.h b/source/blender/blenlib/BLI_kdopbvh.h
index a348694c4da..abfd561200c 100644
--- a/source/blender/blenlib/BLI_kdopbvh.h
+++ b/source/blender/blenlib/BLI_kdopbvh.h
@@ -177,6 +177,12 @@ int BLI_bvhtree_find_nearest(BVHTree *tree,
                              BVHTree_NearestPointCallback callback,
                              void *userdata);
 
+int BLI_bvhtree_find_nearest_first(BVHTree *tree,
+                                   const float co[3],
+                                   const float dist_sq,
+                                   BVHTree_NearestPointCallback callback,
+                                   void *userdata);
+
 int BLI_bvhtree_ray_cast_ex(BVHTree *tree,
                             const float co[3],
                             const float dir[3],
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index 0e93fd8e13b..ed3c7096865 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -1467,6 +1467,95 @@ int BLI_bvhtree_find_nearest(BVHTree *tree,
 /** \} */
 
 /* -------------------------------------------------------------------- */
+/** \name BLI_bvhtree_find_nearest_first
+ * \{ */
+
+static bool isect_aabb_v3(BVHNode *node, const float co[3])
+{
+  const BVHTreeAxisRange *bv = (const BVHTreeAxisRange *)node->bv;
+
+  if (co[0] > bv[0].min && co[0] < bv[0].max && co[1] > bv[1].min && co[1] < bv[1].max &&
+      co[2] > bv[2].min && co[2] < bv[2].max) {
+    return true;
+  }
+
+  return false;
+}
+
+static bool dfs_find_duplicate_fast_dfs(BVHNearestData *data, BVHNode *node)
+{
+  if (node->totnode == 0) {
+    if (isect_aabb_v3(node, data->co)) {
+      if (data->callback) {
+        const float dist_sq = data->nearest.dist_sq;
+        data->callback(data->userdata, node->index, data->co, &data->nearest);
+        return (data->nearest.dist_sq < dist_sq);
+      }
+      else {
+        data->nearest.index = node->index;
+        return true;
+      }
+    }
+  }
+  else {
+    /* Better heuristic to pick the closest node to dive on */
+    int i;
+
+    if (data->proj[node->main_axis] <= node->children[0]->bv[node->main_axis * 2 + 1]) {
+      for (i = 0; i != node->totnode; i++) {
+        if (isect_aabb_v3(node->children[i], data->co)) {
+          if (dfs_find_duplicate_fast_dfs(data, node->children[i])) {
+            return true;
+          }
+        }
+      }
+    }
+    else {
+      for (i = node->totnode; i--;) {
+        if (isect_aabb_v3(node->children[i], data->co)) {
+          if (dfs_find_duplicate_fast_dfs(data, node->children[i])) {
+            return true;
+          }
+        }
+      }
+    }
+  }
+  return false;
+}
+
+/**
+ * Find the first node nearby.
+ * Favors speed over quality since it doesn't find the best target node.
+ */
+int BLI_bvhtree_find_nearest_first(BVHTree *tree,
+                                   const float co[3],
+                                   const float dist_sq,
+                                   BVHTree_NearestPointCallback callback,
+                                   void *userdata)
+{
+  BVHNearestData data;
+  BVHNode *root = tree->nodes[tree->totleaf];
+
+  /* init data to search */
+  data.tree = tree;
+  data.co = co;
+
+  data.callback = callback;
+  data.userdata = userdata;
+  data.nearest.index = -1;
+  data.nearest.dist_sq = dist_sq;
+
+  /* dfs search */
+  if (root) {
+    dfs_find_duplicate_fast_dfs(&data, root);
+  }
+
+  return data.nearest.index;
+}
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
 /** \name BLI_bvhtree_ray_cast
  *
  * raycast is done by performing a DFS on the BVHTree and saving the closest hit.