From 20558848d311ac0be35d01ab8331f1330a9ad450 Mon Sep 17 00:00:00 2001
From: Germano Cavalcante <germano.costa@ig.com.br>
Date: Tue, 7 Jul 2020 09:45:53 -0300
Subject: Optimization: use `BLI_bvhtree_intersect_plane` to detect faces that
 will be affected by the knife tool

The knife code currently calls the `BLI_bvhtree_overlap` function that
tests the overlap between the mesh tree and an AABB that encompasses the
points projected in the clip_start, clip_end and or clip_planes of the
view.

This resulted in many false positives since the AABB is very large.
Often all the triangles "overlapped".

The solution was to create a new function that actually tests the
intersection of AABB with a plane.

Even not considering the clip_planes of the view, this solution is more
appropriate than using overlap.

Differential Revision: https://developer.blender.org/D8229
---
 source/blender/blenlib/intern/BLI_kdopbvh.c | 71 +++++++++++++++++++++++++++++
 1 file changed, 71 insertions(+)

(limited to 'source/blender/blenlib/intern')

diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index 0707e4c1d2a..e9946d81f75 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -169,6 +169,12 @@ typedef struct BVHNearestProjectedData {
 
 } BVHNearestProjectedData;
 
+typedef struct BVHIntersectPlaneData {
+  const BVHTree *tree;
+  float plane[4];
+  struct BLI_Stack *intersect; /* Store indexes. */
+} BVHIntersectPlaneData;
+
 /** \} */
 
 /**
@@ -1392,6 +1398,71 @@ BVHTreeOverlap *BLI_bvhtree_overlap(
 
 /** \} */
 
+/* -------------------------------------------------------------------- */
+/** \name BLI_bvhtree_intersect_plane
+ * \{ */
+
+static bool tree_intersect_plane_test(const float *bv, const float plane[4])
+{
+  /* TODO(germano): Support other kdop geometries. */
+  const float bb_min[3] = {bv[0], bv[2], bv[4]};
+  const float bb_max[3] = {bv[1], bv[3], bv[5]};
+  float bb_near[3], bb_far[3];
+  aabb_get_near_far_from_plane(plane, bb_min, bb_max, bb_near, bb_far);
+  if ((plane_point_side_v3(plane, bb_near) > 0.0f) !=
+      (plane_point_side_v3(plane, bb_far) > 0.0f)) {
+    return true;
+  }
+
+  return false;
+}
+
+static void bvhtree_intersect_plane_dfs_recursive(BVHIntersectPlaneData *__restrict data,
+                                                  const BVHNode *node)
+{
+  if (tree_intersect_plane_test(node->bv, data->plane)) {
+    /* check if node is a leaf */
+    if (!node->totnode) {
+      int *intersect = BLI_stack_push_r(data->intersect);
+      *intersect = node->index;
+    }
+    else {
+      for (int j = 0; j < data->tree->tree_type; j++) {
+        if (node->children[j]) {
+          bvhtree_intersect_plane_dfs_recursive(data, node->children[j]);
+        }
+      }
+    }
+  }
+}
+
+int *BLI_bvhtree_intersect_plane(BVHTree *tree, float plane[4], uint *r_intersect_tot)
+{
+  int *intersect = NULL;
+  size_t total = 0;
+
+  BVHNode *root = tree->nodes[tree->totleaf];
+  if (root != NULL) {
+    BVHIntersectPlaneData data;
+    data.tree = tree;
+    copy_v4_v4(data.plane, plane);
+    data.intersect = BLI_stack_new(sizeof(int), __func__);
+
+    bvhtree_intersect_plane_dfs_recursive(&data, root);
+
+    total = BLI_stack_count(data.intersect);
+    if (total) {
+      intersect = MEM_mallocN(sizeof(int) * total, __func__);
+      BLI_stack_pop_n(data.intersect, intersect, (uint)total);
+    }
+    BLI_stack_free(data.intersect);
+  }
+  *r_intersect_tot = (uint)total;
+  return intersect;
+}
+
+/** \} */
+
 /* -------------------------------------------------------------------- */
 /** \name BLI_bvhtree_find_nearest
  * \{ */
-- 
cgit v1.2.3