1 files changed, 159 insertions, 199 deletions

diff --git a/source/blender/editors/mesh/editmesh_knife.c b/source/blender/editors/mesh/editmesh_knife.c
index adc3be6b2ac..0394874e8c1 100644
--- a/source/blender/editors/mesh/editmesh_knife.c
+++ b/source/blender/editors/mesh/editmesh_knife.c
@@ -102,7 +102,7 @@ typedef struct KnifeVert {
   ListBase edges;
   ListBase faces;
 
-  float co[3], cageco[3], sco[2]; /* sco is screen coordinates for cageco */
+  float co[3], cageco[3];
   bool is_face, in_space;
   bool is_cut; /* along a cut created by user input (will draw too) */
 } KnifeVert;
@@ -429,8 +429,6 @@ static KnifeVert *new_knife_vert(KnifeTool_OpData *kcd, const float co[3], const
   copy_v3_v3(kfv->co, co);
   copy_v3_v3(kfv->cageco, cageco);
 
-  knife_project_v2(kcd, kfv->cageco, kfv->sco);
-
   return kfv;
 }
 
@@ -1548,8 +1546,8 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd)
 {
   SmallHash faces, kfes, kfvs;
   float v1[3], v2[3], v3[3], v4[3], s1[2], s2[2];
-  BVHTree *planetree, *tree;
-  BVHTreeOverlap *results, *result;
+  BVHTree *tree;
+  int *results, *result;
   BMLoop **ls;
   BMFace *f;
   KnifeEdge *kfe;
@@ -1562,7 +1560,6 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd)
   KnifeLineHit hit;
   void *val;
   void **val_p;
-  float plane_cos[12];
   float s[2], se1[2], se2[2], sint[2];
   float r1[3], r2[3];
   float d, d1, d2, lambda;
@@ -1623,22 +1620,22 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd)
     clip_to_ortho_planes(v2, v4, kcd->ortho_extent_center, kcd->ortho_extent + 10.0f);
   }
 
+  float plane[4];
+  {
+    float v1_v2[3], v1_v3[3];
+    sub_v3_v3v3(v1_v2, v2, v1);
+    sub_v3_v3v3(v1_v3, v3, v1);
+    cross_v3_v3v3(plane, v1_v2, v1_v3);
+    plane_from_point_normal_v3(plane, v1, plane);
+  }
+
   /* First use bvh tree to find faces, knife edges, and knife verts that might
    * intersect the cut plane with rays v1-v3 and v2-v4.
    * This deduplicates the candidates before doing more expensive intersection tests. */
 
   tree = BKE_bmbvh_tree_get(kcd->bmbvh);
-  planetree = BLI_bvhtree_new(4, FLT_EPSILON * 4, 8, 8);
-  copy_v3_v3(plane_cos + 0, v1);
-  copy_v3_v3(plane_cos + 3, v2);
-  copy_v3_v3(plane_cos + 6, v3);
-  copy_v3_v3(plane_cos + 9, v4);
-  BLI_bvhtree_insert(planetree, 0, plane_cos, 4);
-  BLI_bvhtree_balance(planetree);
-
-  results = BLI_bvhtree_overlap(tree, planetree, &tot, NULL, NULL);
+  results = BLI_bvhtree_intersect_plane(tree, plane, &tot);
   if (!results) {
-    BLI_bvhtree_free(planetree);
     return;
   }
 
@@ -1647,9 +1644,9 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd)
   BLI_smallhash_init(&kfvs);
 
   for (i = 0, result = results; i < tot; i++, result++) {
-    ls = (BMLoop **)kcd->em->looptris[result->indexA];
+    ls = (BMLoop **)kcd->em->looptris[*result];
     f = ls[0]->f;
-    set_lowest_face_tri(kcd, f, result->indexA);
+    set_lowest_face_tri(kcd, f, *result);
 
     /* occlude but never cut unselected faces (when only_select is used) */
     if (kcd->only_select && !BM_elem_flag_test(f, BM_ELEM_SELECT)) {
@@ -1834,7 +1831,6 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd)
   BLI_smallhash_release(&faces);
   BLI_smallhash_release(&kfes);
   BLI_smallhash_release(&kfvs);
-  BLI_bvhtree_free(planetree);
   if (results) {
     MEM_freeN(results);
   }
@@ -1928,10 +1924,11 @@ static int knife_sample_screen_density(KnifeTool_OpData *kcd, const float radius
 
       for (i = 0; i < 2; i++) {
         KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
+        float kfv_sco[2];
 
-        knife_project_v2(kcd, kfv->cageco, kfv->sco);
+        knife_project_v2(kcd, kfv->cageco, kfv_sco);
 
-        dis_sq = len_squared_v2v2(kfv->sco, sco);
+        dis_sq = len_squared_v2v2(kfv_sco, sco);
         if (dis_sq < radius_sq) {
           if (RV3D_CLIPPING_ENABLED(kcd->vc.v3d, kcd->vc.rv3d)) {
             if (ED_view3d_clipping_test(kcd->vc.rv3d, kfv->cageco, true) == 0) {
@@ -1961,11 +1958,12 @@ static float knife_snap_size(KnifeTool_OpData *kcd, float maxsize)
 }
 
 /* p is closest point on edge to the mouse cursor */
-static KnifeEdge *knife_find_closest_edge(
-    KnifeTool_OpData *kcd, float p[3], float cagep[3], BMFace **fptr, bool *is_space)
+static KnifeEdge *knife_find_closest_edge_of_face(KnifeTool_OpData *kcd,
+                                                  BMFace *f,
+                                                  float p[3],
+                                                  float cagep[3])
 {
-  BMFace *f;
-  float co[3], cageco[3], sco[2];
+  float sco[2];
   float maxdist;
 
   if (kcd->is_interactive) {
@@ -1979,127 +1977,105 @@ static KnifeEdge *knife_find_closest_edge(
     maxdist = KNIFE_FLT_EPS;
   }
 
-  f = knife_find_closest_face(kcd, co, cageco, NULL);
-  *is_space = !f;
-
-  kcd->curr.bmface = f;
-
-  if (f) {
-    const float maxdist_sq = maxdist * maxdist;
-    KnifeEdge *cure = NULL;
-    float cur_cagep[3];
-    ListBase *lst;
-    Ref *ref;
-    float dis_sq, curdis_sq = FLT_MAX;
-
-    /* set p to co, in case we don't find anything, means a face cut */
-    copy_v3_v3(p, co);
-    copy_v3_v3(cagep, cageco);
-
-    knife_project_v2(kcd, cageco, sco);
-
-    /* look through all edges associated with this face */
-    lst = knife_get_face_kedges(kcd, f);
-    for (ref = lst->first; ref; ref = ref->next) {
-      KnifeEdge *kfe = ref->ref;
-      float test_cagep[3];
-      float lambda;
-
-      /* project edge vertices into screen space */
-      knife_project_v2(kcd, kfe->v1->cageco, kfe->v1->sco);
-      knife_project_v2(kcd, kfe->v2->cageco, kfe->v2->sco);
-
-      /* check if we're close enough and calculate 'lambda' */
-      if (kcd->is_angle_snapping) {
-        /* if snapping, check we're in bounds */
-        float sco_snap[2];
-        isect_line_line_v2_point(
-            kfe->v1->sco, kfe->v2->sco, kcd->prev.mval, kcd->curr.mval, sco_snap);
-        lambda = line_point_factor_v2(sco_snap, kfe->v1->sco, kfe->v2->sco);
-
-        /* be strict about angle-snapping within edge */
-        if ((lambda < 0.0f - KNIFE_FLT_EPSBIG) || (lambda > 1.0f + KNIFE_FLT_EPSBIG)) {
-          continue;
-        }
+  const float maxdist_sq = maxdist * maxdist;
+  KnifeEdge *cure = NULL;
+  float cur_cagep[3];
+  ListBase *lst;
+  Ref *ref;
+  float dis_sq, curdis_sq = FLT_MAX;
+
+  knife_project_v2(kcd, cagep, sco);
+
+  /* look through all edges associated with this face */
+  lst = knife_get_face_kedges(kcd, f);
+  for (ref = lst->first; ref; ref = ref->next) {
+    KnifeEdge *kfe = ref->ref;
+    float kfv1_sco[2], kfv2_sco[2], test_cagep[3];
+    float lambda;
+
+    /* project edge vertices into screen space */
+    knife_project_v2(kcd, kfe->v1->cageco, kfv1_sco);
+    knife_project_v2(kcd, kfe->v2->cageco, kfv2_sco);
+
+    /* check if we're close enough and calculate 'lambda' */
+    if (kcd->is_angle_snapping) {
+      /* if snapping, check we're in bounds */
+      float sco_snap[2];
+      isect_line_line_v2_point(kfv1_sco, kfv2_sco, kcd->prev.mval, kcd->curr.mval, sco_snap);
+      lambda = line_point_factor_v2(sco_snap, kfv1_sco, kfv2_sco);
+
+      /* be strict about angle-snapping within edge */
+      if ((lambda < 0.0f - KNIFE_FLT_EPSBIG) || (lambda > 1.0f + KNIFE_FLT_EPSBIG)) {
+        continue;
+      }
 
-        dis_sq = len_squared_v2v2(sco, sco_snap);
-        if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
-          /* we already have 'lambda' */
-        }
-        else {
-          continue;
-        }
+      dis_sq = len_squared_v2v2(sco, sco_snap);
+      if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
+        /* we already have 'lambda' */
       }
       else {
-        dis_sq = dist_squared_to_line_segment_v2(sco, kfe->v1->sco, kfe->v2->sco);
-        if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
-          lambda = line_point_factor_v2(sco, kfe->v1->sco, kfe->v2->sco);
-        }
-        else {
-          continue;
-        }
+        continue;
       }
-
-      /* now we have 'lambda' calculated (in screen-space) */
-      knife_interp_v3_v3v3(kcd, test_cagep, kfe->v1->cageco, kfe->v2->cageco, lambda);
-
-      if (RV3D_CLIPPING_ENABLED(kcd->vc.v3d, kcd->vc.rv3d)) {
-        /* check we're in the view */
-        if (ED_view3d_clipping_test(kcd->vc.rv3d, test_cagep, true)) {
-          continue;
-        }
+    }
+    else {
+      dis_sq = dist_squared_to_line_segment_v2(sco, kfv1_sco, kfv2_sco);
+      if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
+        lambda = line_point_factor_v2(sco, kfv1_sco, kfv2_sco);
+      }
+      else {
+        continue;
       }
-
-      cure = kfe;
-      curdis_sq = dis_sq;
-      copy_v3_v3(cur_cagep, test_cagep);
     }
 
-    if (fptr) {
-      *fptr = f;
+    /* now we have 'lambda' calculated (in screen-space) */
+    knife_interp_v3_v3v3(kcd, test_cagep, kfe->v1->cageco, kfe->v2->cageco, lambda);
+
+    if (RV3D_CLIPPING_ENABLED(kcd->vc.v3d, kcd->vc.rv3d)) {
+      /* check we're in the view */
+      if (ED_view3d_clipping_test(kcd->vc.rv3d, test_cagep, true)) {
+        continue;
+      }
     }
 
-    if (cure) {
-      if (!kcd->ignore_edge_snapping || !(cure->e)) {
-        KnifeVert *edgesnap = NULL;
+    cure = kfe;
+    curdis_sq = dis_sq;
+    copy_v3_v3(cur_cagep, test_cagep);
+  }
 
-        if (kcd->snap_midpoints) {
-          mid_v3_v3v3(p, cure->v1->co, cure->v2->co);
-          mid_v3_v3v3(cagep, cure->v1->cageco, cure->v2->cageco);
-        }
-        else {
-          float lambda = line_point_factor_v3(cur_cagep, cure->v1->cageco, cure->v2->cageco);
-          copy_v3_v3(cagep, cur_cagep);
-          interp_v3_v3v3(p, cure->v1->co, cure->v2->co, lambda);
-        }
+  if (cure) {
+    if (!kcd->ignore_edge_snapping || !(cure->e)) {
+      KnifeVert *edgesnap = NULL;
 
-        /* update mouse coordinates to the snapped-to edge's screen coordinates
-         * this is important for angle snap, which uses the previous mouse position */
-        edgesnap = new_knife_vert(kcd, p, cagep);
-        kcd->curr.mval[0] = edgesnap->sco[0];
-        kcd->curr.mval[1] = edgesnap->sco[1];
+      if (kcd->snap_midpoints) {
+        mid_v3_v3v3(p, cure->v1->co, cure->v2->co);
+        mid_v3_v3v3(cagep, cure->v1->cageco, cure->v2->cageco);
       }
       else {
-        return NULL;
+        float lambda = line_point_factor_v3(cur_cagep, cure->v1->cageco, cure->v2->cageco);
+        copy_v3_v3(cagep, cur_cagep);
+        interp_v3_v3v3(p, cure->v1->co, cure->v2->co, lambda);
       }
-    }
-
-    return cure;
-  }
 
-  if (fptr) {
-    *fptr = NULL;
+      /* update mouse coordinates to the snapped-to edge's screen coordinates
+       * this is important for angle snap, which uses the previous mouse position */
+      edgesnap = new_knife_vert(kcd, p, cagep);
+      knife_project_v2(kcd, edgesnap->cageco, kcd->curr.mval);
+    }
+    else {
+      return NULL;
+    }
   }
 
-  return NULL;
+  return cure;
 }
 
 /* find a vertex near the mouse cursor, if it exists */
-static KnifeVert *knife_find_closest_vert(
-    KnifeTool_OpData *kcd, float p[3], float cagep[3], BMFace **fptr, bool *is_space)
+static KnifeVert *knife_find_closest_vert_of_face(KnifeTool_OpData *kcd,
+                                                  BMFace *f,
+                                                  float p[3],
+                                                  float cagep[3])
 {
-  BMFace *f;
-  float co[3], cageco[3], sco[2];
+  float sco[2];
   float maxdist;
 
   if (kcd->is_interactive) {
@@ -2112,84 +2088,58 @@ static KnifeVert *knife_find_closest_vert(
     maxdist = KNIFE_FLT_EPS;
   }
 
-  f = knife_find_closest_face(kcd, co, cageco, is_space);
-
-  kcd->curr.bmface = f;
-
-  if (f) {
-    const float maxdist_sq = maxdist * maxdist;
-    ListBase *lst;
-    Ref *ref;
-    KnifeVert *curv = NULL;
-    float dis_sq, curdis_sq = FLT_MAX;
-
-    /* set p to co, in case we don't find anything, means a face cut */
-    copy_v3_v3(p, co);
-    copy_v3_v3(cagep, cageco);
+  const float maxdist_sq = maxdist * maxdist;
+  ListBase *lst;
+  Ref *ref;
+  KnifeVert *curv = NULL;
+  float cur_kfv_sco[2];
+  float dis_sq, curdis_sq = FLT_MAX;
 
-    knife_project_v2(kcd, cageco, sco);
+  knife_project_v2(kcd, cagep, sco);
 
-    lst = knife_get_face_kedges(kcd, f);
-    for (ref = lst->first; ref; ref = ref->next) {
-      KnifeEdge *kfe = ref->ref;
-      int i;
+  lst = knife_get_face_kedges(kcd, f);
+  for (ref = lst->first; ref; ref = ref->next) {
+    KnifeEdge *kfe = ref->ref;
+    int i;
 
-      for (i = 0; i < 2; i++) {
-        KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
+    for (i = 0; i < 2; i++) {
+      KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
+      float kfv_sco[2];
 
-        knife_project_v2(kcd, kfv->cageco, kfv->sco);
+      knife_project_v2(kcd, kfv->cageco, kfv_sco);
 
-        /* be strict about angle snapping, the vertex needs to be very close to the angle,
-         * or we ignore */
-        if (kcd->is_angle_snapping) {
-          if (dist_squared_to_line_segment_v2(kfv->sco, kcd->prev.mval, kcd->curr.mval) >
-              KNIFE_FLT_EPSBIG) {
-            continue;
-          }
+      /* be strict about angle snapping, the vertex needs to be very close to the angle,
+       * or we ignore */
+      if (kcd->is_angle_snapping) {
+        if (dist_squared_to_line_segment_v2(kfv_sco, kcd->prev.mval, kcd->curr.mval) >
+            KNIFE_FLT_EPSBIG) {
+          continue;
         }
+      }
 
-        dis_sq = len_squared_v2v2(kfv->sco, sco);
-        if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
-          if (RV3D_CLIPPING_ENABLED(kcd->vc.v3d, kcd->vc.rv3d)) {
-            if (ED_view3d_clipping_test(kcd->vc.rv3d, kfv->cageco, true) == 0) {
-              curv = kfv;
-              curdis_sq = dis_sq;
-            }
-          }
-          else {
-            curv = kfv;
-            curdis_sq = dis_sq;
-          }
+      dis_sq = len_squared_v2v2(kfv_sco, sco);
+      if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
+        if (!RV3D_CLIPPING_ENABLED(kcd->vc.v3d, kcd->vc.rv3d) ||
+            !ED_view3d_clipping_test(kcd->vc.rv3d, kfv->cageco, true)) {
+          curv = kfv;
+          curdis_sq = dis_sq;
+          copy_v2_v2(cur_kfv_sco, kfv_sco);
         }
       }
     }
+  }
 
-    if (!kcd->ignore_vert_snapping || !(curv && curv->v)) {
-      if (fptr) {
-        *fptr = f;
-      }
-
-      if (curv) {
-        copy_v3_v3(p, curv->co);
-        copy_v3_v3(cagep, curv->cageco);
-
-        /* update mouse coordinates to the snapped-to vertex's screen coordinates
-         * this is important for angle snap, which uses the previous mouse position */
-        kcd->curr.mval[0] = curv->sco[0];
-        kcd->curr.mval[1] = curv->sco[1];
-      }
-
-      return curv;
-    }
+  if (!kcd->ignore_vert_snapping || !(curv && curv->v)) {
+    if (curv) {
+      copy_v3_v3(p, curv->co);
+      copy_v3_v3(cagep, curv->cageco);
 
-    if (fptr) {
-      *fptr = f;
+      /* update mouse coordinates to the snapped-to vertex's screen coordinates
+       * this is important for angle snap, which uses the previous mouse position */
+      copy_v2_v2(kcd->curr.mval, cur_kfv_sco);
     }
-    return NULL;
-  }
 
-  if (fptr) {
-    *fptr = NULL;
+    return curv;
   }
 
   return NULL;
@@ -2236,11 +2186,10 @@ static bool knife_snap_angle(KnifeTool_OpData *kcd)
   return true;
 }
 
-/* update active knife edge/vert pointers */
-static int knife_update_active(KnifeTool_OpData *kcd)
+static void knife_snap_update_from_mval(KnifeTool_OpData *kcd, const float mval[2])
 {
   knife_pos_data_clear(&kcd->curr);
-  copy_v2_v2(kcd->curr.mval, kcd->mval);
+  copy_v2_v2(kcd->curr.mval, mval);
 
   /* view matrix may have changed, reproject */
   knife_project_v2(kcd, kcd->prev.cage, kcd->prev.mval);
@@ -2252,15 +2201,26 @@ static int knife_update_active(KnifeTool_OpData *kcd)
     kcd->is_angle_snapping = false;
   }
 
-  kcd->curr.vert = knife_find_closest_vert(
-      kcd, kcd->curr.co, kcd->curr.cage, &kcd->curr.bmface, &kcd->curr.is_space);
+  kcd->curr.bmface = knife_find_closest_face(
+      kcd, kcd->curr.co, kcd->curr.cage, &kcd->curr.is_space);
+
+  if (kcd->curr.bmface) {
+    kcd->curr.vert = knife_find_closest_vert_of_face(
+        kcd, kcd->curr.bmface, kcd->curr.co, kcd->curr.cage);
 
-  if (!kcd->curr.vert &&
-      /* no edge snapping while dragging (edges are too sticky when cuts are immediate) */
-      !kcd->is_drag_hold) {
-    kcd->curr.edge = knife_find_closest_edge(
-        kcd, kcd->curr.co, kcd->curr.cage, &kcd->curr.bmface, &kcd->curr.is_space);
+    if (!kcd->curr.vert &&
+        /* no edge snapping while dragging (edges are too sticky when cuts are immediate) */
+        !kcd->is_drag_hold) {
+      kcd->curr.edge = knife_find_closest_edge_of_face(
+          kcd, kcd->curr.bmface, kcd->curr.co, kcd->curr.cage);
+    }
   }
+}
+
+/* update active knife edge/vert pointers */
+static int knife_update_active(KnifeTool_OpData *kcd)
+{
+  knife_snap_update_from_mval(kcd, kcd->mval);
 
   /* if no hits are found this would normally default to (0, 0, 0) so instead
    * get a point at the mouse ray closest to the previous point.