Fix T41164: Knife creates duplicate verts
[blender-staging.git] / source / blender / editors / mesh / editmesh_knife.c
index 490603ac0a71f17e9c6e409959d0a8781010d6c9..7421acac9b592f6f1cd6e4e8bffb3b874c904ea8 100644 (file)
@@ -78,6 +78,7 @@
 #define KNIFE_FLT_EPS          0.00001f
 #define KNIFE_FLT_EPS_SQUARED  (KNIFE_FLT_EPS * KNIFE_FLT_EPS)
 #define KNIFE_FLT_EPSBIG       0.0005f
+#define KNIFE_FLT_EPS_PX       0.2f
 
 typedef struct KnifeColors {
        unsigned char line[3];
@@ -208,6 +209,9 @@ typedef struct KnifeTool_OpData {
        bool ignore_edge_snapping;
        bool ignore_vert_snapping;
 
+       /* use to check if we're currently dragging an angle snapped line */
+       bool is_angle_snapping;
+
        enum {
                ANGLE_FREE,
                ANGLE_0,
@@ -1156,48 +1160,52 @@ static void calc_ortho_extent(KnifeTool_OpData *kcd)
  * s in screen projection of p. */
 static bool point_is_visible(KnifeTool_OpData *kcd, const float p[3], const float s[2], bglMats *mats)
 {
-       float p1[3];
        BMFace *f_hit;
 
+       /* If box clipping on, make sure p is not clipped */
+       if (kcd->vc.rv3d->rflag & RV3D_CLIPPING &&
+           ED_view3d_clipping_test(kcd->vc.rv3d, p, true))
+       {
+               return false;
+       }
+
        /* If not cutting through, make sure no face is in front of p */
        if (!kcd->cut_through) {
                float dist;
-               float view[3];
+               float view[3], p_ofs[3];
 
                /* TODO: I think there's a simpler way to get the required raycast ray */
                ED_view3d_unproject(mats, view, s[0], s[1], 0.0f);
 
+               mul_m4_v3(kcd->ob->imat, view);
+
+               /* make p_ofs a little towards view, so ray doesn't hit p's face. */
+               sub_v3_v3(view, p);
+               dist = normalize_v3(view);
+               madd_v3_v3v3fl(p_ofs, p, view, KNIFE_FLT_EPSBIG * 3.0f);
+
                /* avoid projecting behind the viewpoint */
-               if (kcd->is_ortho) {
-                       dist = FLT_MAX;
-               }
-               else {
-                       float p_world[3];
-                       mul_v3_m4v3(p_world, kcd->ob->obmat, p);
-                       dist = len_v3v3(view, p_world);
+               if (kcd->is_ortho && (kcd->vc.rv3d->persp != RV3D_CAMOB)) {
+                       dist = kcd->vc.v3d->far * 2.0f;
                }
 
-               mul_m4_v3(kcd->ob->imat, view);
+               if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
+                       float view_clip[2][3];
+                       /* note: view_clip[0] should never get clipped */
+                       copy_v3_v3(view_clip[0], p_ofs);
+                       madd_v3_v3v3fl(view_clip[1], p_ofs, view, dist);
 
-               /* make p1 a little towards view, so ray doesn't hit p's face. */
-               copy_v3_v3(p1, p);
-               sub_v3_v3(view, p1);
-               normalize_v3(view);
-               madd_v3_v3fl(p1, view, 3.0f * KNIFE_FLT_EPSBIG);
+                       if (clip_segment_v3_plane_n(view_clip[0], view_clip[1], kcd->vc.rv3d->clip_local, 6)) {
+                               dist = len_v3v3(p_ofs, view_clip[1]);
+                       }
+               }
 
                /* see if there's a face hit between p1 and the view */
-               f_hit = BKE_bmbvh_ray_cast(kcd->bmbvh, p1, view, KNIFE_FLT_EPS, &dist, NULL, NULL);
+               f_hit = BKE_bmbvh_ray_cast(kcd->bmbvh, p_ofs, view, KNIFE_FLT_EPS, &dist, NULL, NULL);
                if (f_hit)
                        return false;
        }
 
-       /* If box clipping on, make sure p is not clipped */
-       if (kcd->vc.rv3d->rflag & RV3D_CLIPPING &&
-           ED_view3d_clipping_test(kcd->vc.rv3d, p, true))
-       {
-               return false;
-       }
-
        return true;
 }
 
@@ -1219,7 +1227,7 @@ static void set_linehit_depth(KnifeTool_OpData *kcd, KnifeLineHit *lh)
 
        ED_view3d_win_to_segment(kcd->ar, kcd->vc.v3d, lh->schit, vnear, vfar, true);
        mul_m4_v3(kcd->ob->imat, vnear);
-       if (kcd->is_ortho) {
+       if (kcd->is_ortho && (kcd->vc.rv3d->persp != RV3D_CAMOB)) {
                if (kcd->ortho_extent == 0.0f)
                        calc_ortho_extent(kcd);
                clip_to_ortho_planes(vnear, vfar, kcd->ortho_extent + 10.0f);
@@ -1251,6 +1259,7 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd)
        float p[3], p2[3], r1[3], r2[3];
        float d, d1, d2, lambda;
        float vert_tol, vert_tol_sq, line_tol, face_tol;
+       float eps_scale;
        int isect_kind;
        unsigned int tot;
        int i;
@@ -1295,7 +1304,7 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd)
         * this gives precision error; rather then solving properly
         * (which may involve using doubles everywhere!),
         * limit the distance between these points */
-       if (kcd->is_ortho) {
+       if (kcd->is_ortho && (kcd->vc.rv3d->persp != RV3D_CAMOB)) {
                if (kcd->ortho_extent == 0.0f)
                        calc_ortho_extent(kcd);
                clip_to_ortho_planes(v1, v3, kcd->ortho_extent + 10.0f);
@@ -1353,8 +1362,16 @@ static void knife_find_line_hits(KnifeTool_OpData *kcd)
 
        /* Now go through the candidates and find intersections */
        /* These tolerances, in screen space, are for intermediate hits, as ends are already snapped to screen */
-       vert_tol = KNIFE_FLT_EPS * 2000.0f;
-       line_tol = KNIFE_FLT_EPS * 2000.0f;
+       {
+               /* Scale the epsilon by the zoom level
+                * to compensate for projection imprecision, see T41164 */
+               float zoom_xy[2] = {kcd->vc.rv3d->winmat[0][0],
+                                   kcd->vc.rv3d->winmat[1][1]};
+               eps_scale = len_v2(zoom_xy);
+       }
+
+       vert_tol = KNIFE_FLT_EPS_PX * eps_scale;
+       line_tol = KNIFE_FLT_EPS_PX * eps_scale;
        vert_tol_sq = vert_tol * vert_tol;
        face_tol = max_ff(vert_tol, line_tol);
        /* Assume these tolerances swamp floating point rounding errors in calculations below */
@@ -1613,6 +1630,7 @@ static KnifeEdge *knife_find_closest_edge(KnifeTool_OpData *kcd, float p[3], flo
        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;
@@ -1623,29 +1641,56 @@ static KnifeEdge *knife_find_closest_edge(KnifeTool_OpData *kcd, float p[3], flo
                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);
 
-                       dis_sq = dist_squared_to_line_segment_v2(sco, kfe->v1->sco, kfe->v2->sco);
-                       if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
-                               if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
-                                       float lambda = line_point_factor_v2(sco, kfe->v1->sco, kfe->v2->sco);
-                                       float vec[3];
+                       /* 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);
 
-                                       interp_v3_v3v3(vec, kfe->v1->cageco, kfe->v2->cageco, lambda);
+                               /* be strict about angle-snapping within edge */
+                               if ((lambda < 0.0f - KNIFE_FLT_EPSBIG) || (lambda > 1.0f + KNIFE_FLT_EPSBIG)) {
+                                       continue;
+                               }
 
-                                       if (ED_view3d_clipping_test(kcd->vc.rv3d, vec, true) == 0) {
-                                               cure = kfe;
-                                               curdis_sq = dis_sq;
-                                       }
+                               dis_sq = len_squared_v2v2(sco, sco_snap);
+                               if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
+                                       /* we already have 'lambda' */
+                               }
+                               else {
+                                       continue;
+                               }
+                       }
+                       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 {
-                                       cure = kfe;
-                                       curdis_sq = dis_sq;
+                                       continue;
+                               }
+                       }
+
+                       /* now we have 'lambda' calculated */
+                       interp_v3_v3v3(test_cagep, kfe->v1->cageco, kfe->v2->cageco, lambda);
+
+                       if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
+                               /* check we're in the view */
+                               if (ED_view3d_clipping_test(kcd->vc.rv3d, test_cagep, true)) {
+                                       continue;
                                }
                        }
+
+                       cure = kfe;
+                       curdis_sq = dis_sq;
+                       copy_v3_v3(cur_cagep, test_cagep);
                }
 
                if (fptr)
@@ -1660,11 +1705,9 @@ static KnifeEdge *knife_find_closest_edge(KnifeTool_OpData *kcd, float p[3], flo
                                        mid_v3_v3v3(cagep, cure->v1->cageco, cure->v2->cageco);
                                }
                                else {
-                                       float d;
-
-                                       closest_to_line_segment_v3(cagep, cageco, cure->v1->cageco, cure->v2->cageco);
-                                       d = len_v3v3(cagep, cure->v1->cageco) / len_v3v3(cure->v1->cageco, cure->v2->cageco);
-                                       interp_v3_v3v3(p, cure->v1->co, cure->v2->co, d);
+                                       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);
                                }
 
                                /* update mouse coordinates to the snapped-to edge's screen coordinates
@@ -1724,6 +1767,13 @@ static KnifeVert *knife_find_closest_vert(KnifeTool_OpData *kcd, float p[3], flo
 
                                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;
+                                       }
+                               }
+
                                dis_sq = len_squared_v2v2(kfv->sco, sco);
                                if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
                                        if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
@@ -1771,7 +1821,7 @@ static KnifeVert *knife_find_closest_vert(KnifeTool_OpData *kcd, float p[3], flo
 }
 
 /* update both kcd->curr.mval and kcd->mval to snap to required angle */
-static void knife_snap_angle(KnifeTool_OpData *kcd)
+static bool knife_snap_angle(KnifeTool_OpData *kcd)
 {
        float dx, dy;
        float w, abs_tan;
@@ -1779,7 +1829,7 @@ static void knife_snap_angle(KnifeTool_OpData *kcd)
        dx = kcd->curr.mval[0] - kcd->prev.mval[0];
        dy = kcd->curr.mval[1] - kcd->prev.mval[1];
        if (dx == 0.0f && dy == 0.0f)
-               return;
+               return false;
 
        if (dx == 0.0f) {
                kcd->angle_snapping = ANGLE_90;
@@ -1808,6 +1858,8 @@ static void knife_snap_angle(KnifeTool_OpData *kcd)
        }
 
        copy_v2_v2(kcd->mval, kcd->curr.mval);
+
+       return true;
 }
 
 /* update active knife edge/vert pointers */
@@ -1819,12 +1871,13 @@ static int knife_update_active(KnifeTool_OpData *kcd)
        /* view matrix may have changed, reproject */
        knife_project_v2(kcd, kcd->prev.co, kcd->prev.mval);
 
-       if (kcd->angle_snapping != ANGLE_FREE && kcd->mode == MODE_DRAGGING)
-               knife_snap_angle(kcd);
+       if (kcd->angle_snapping != ANGLE_FREE && kcd->mode == MODE_DRAGGING) {
+               kcd->is_angle_snapping = knife_snap_angle(kcd);
+       }
+       else {
+               kcd->is_angle_snapping = false;
+       }
 
-       /* XXX knife_snap_angle updates the view coordinate mouse values to constrained angles,
-        * which current mouse values are set to current mouse values are then used
-        * for vertex and edge snap detection, without regard to the exact angle constraint */
        kcd->curr.vert = knife_find_closest_vert(kcd, kcd->curr.co, kcd->curr.cage, &kcd->curr.bmface, &kcd->curr.is_space);
 
        if (!kcd->curr.vert) {
@@ -2236,7 +2289,7 @@ static bool knife_verts_edge_in_face(KnifeVert *v1, KnifeVert *v2, BMFace *f)
                return true;
        if (l1 && l2) {
                /* Can have case where v1 and v2 are on shared chain between two faces.
-                * BM_face_legal_splits does visibility and self-intersection tests,
+                * BM_face_splits_check_legal does visibility and self-intersection tests,
                 * but it is expensive and maybe a bit buggy, so use a simple
                 * "is the midpoint in the face" test */
                mid_v3_v3v3(mid, v1->co, v2->co);