source/blender/editors/mesh/editmesh_knife.c

   1 /*
   2  * ***** BEGIN GPL LICENSE BLOCK *****
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software Foundation,
  16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  17  *
  18  * The Original Code is Copyright (C) 2007 Blender Foundation.
  19  * All rights reserved.
  20  *
  21  *
  22  * Contributor(s): Joseph Eagar, Joshua Leung, Howard Trickey,
  23  *                 Campbell Barton
  24  *
  25  * ***** END GPL LICENSE BLOCK *****
  26  */
  27
  28 /** \file blender/editors/mesh/editmesh_knife.c
  29  *  \ingroup edmesh
  30  */
  31
  32 #ifdef _MSC_VER
  33 #  define _USE_MATH_DEFINES
  34 #endif
  35
  36 #include "MEM_guardedalloc.h"
  37
  38 #include "BLI_listbase.h"
  39 #include "BLI_string.h"
  40 #include "BLI_array.h"
  41 #include "BLI_linklist.h"
  42 #include "BLI_math.h"
  43 #include "BLI_smallhash.h"
  44 #include "BLI_memarena.h"
  45
  46 #include "BLF_translation.h"
  47
  48 #include "BKE_DerivedMesh.h"
  49 #include "BKE_context.h"
  50 #include "BKE_editmesh.h"
  51 #include "BKE_editmesh_bvh.h"
  52
  53 #include "BIF_gl.h"
  54 #include "BIF_glutil.h" /* for paint cursor */
  55
  56 #include "ED_screen.h"
  57 #include "ED_space_api.h"
  58 #include "ED_view3d.h"
  59 #include "ED_mesh.h"
  60
  61 #include "WM_api.h"
  62 #include "WM_types.h"
  63
  64 #include "DNA_object_types.h"
  65 #include "UI_resources.h"
  66
  67 #include "RNA_access.h"
  68 #include "RNA_define.h"
  69
  70 #include "mesh_intern.h"  /* own include */
  71
  72 /* this code here is kindof messy. . .I might need to eventually rework it - joeedh */
  73
  74 #define KMAXDIST    10  /* max mouse distance from edge before not detecting it */
  75
  76 #define KNIFE_FLT_EPS          0.00001f
  77 #define KNIFE_FLT_EPS_SQUARED  (KNIFE_FLT_EPS * KNIFE_FLT_EPS)
  78
  79 typedef struct KnifeColors {
  80         unsigned char line[3];
  81         unsigned char edge[3];
  82         unsigned char curpoint[3];
  83         unsigned char curpoint_a[4];
  84         unsigned char point[3];
  85         unsigned char point_a[4];
  86 } KnifeColors;
  87
  88 /* knifetool operator */
  89 typedef struct KnifeVert {
  90         BMVert *v; /* non-NULL if this is an original vert */
  91         ListBase edges;
  92         ListBase faces;
  93
  94         float co[3], cageco[3], sco[3]; /* sco is screen coordinates for cageco */
  95         bool is_face, in_space;
  96         bool draw;
  97 } KnifeVert;
  98
  99 typedef struct Ref {
 100         struct Ref *next, *prev;
 101         void *ref;
 102 } Ref;
 103
 104 typedef struct KnifeEdge {
 105         KnifeVert *v1, *v2;
 106         BMFace *basef; /* face to restrict face fill to */
 107         ListBase faces;
 108
 109         BMEdge *e /* , *e_old */; /* non-NULL if this is an original edge */
 110         bool draw;
 111 } KnifeEdge;
 112
 113 typedef struct BMEdgeHit {
 114         KnifeEdge *kfe;
 115         float hit[3], cagehit[3];
 116         float realhit[3]; /* used in midpoint mode */
 117         float schit[3];
 118         float l; /* lambda along cut line */
 119         float perc; /* lambda along hit line */
 120         KnifeVert *v; /* set if snapped to a vert */
 121         BMFace *f;
 122 } BMEdgeHit;
 123
 124 typedef struct KnifePosData {
 125         float co[3];
 126         float cage[3];
 127
 128         /* At most one of vert, edge, or bmface should be non-NULL,
 129          * saying whether the point is snapped to a vertex, edge, or in a face.
 130          * If none are set, this point is in space and is_space should be true. */
 131         KnifeVert *vert;
 132         KnifeEdge *edge;
 133         BMFace *bmface;
 134         bool is_space;
 135
 136         float mval[2]; /* mouse screen position (may be non-integral if snapped to something) */
 137 } KnifePosData;
 138
 139 /* struct for properties used while drawing */
 140 typedef struct KnifeTool_OpData {
 141         ARegion *ar;        /* region that knifetool was activated in */
 142         void *draw_handle;  /* for drawing preview loop */
 143         ViewContext vc;     /* note: _don't_ use 'mval', instead use the one we define below */
 144         float mval[2];      /* mouse value with snapping applied */
 145         //bContext *C;
 146
 147         Object *ob;
 148         BMEditMesh *em;
 149
 150         MemArena *arena;
 151
 152         GHash *origvertmap;
 153         GHash *origedgemap;
 154
 155         GHash *kedgefacemap;
 156
 157         BMBVHTree *bmbvh;
 158
 159         BLI_mempool *kverts;
 160         BLI_mempool *kedges;
 161
 162         float vthresh;
 163         float ethresh;
 164
 165         /* used for drag-cutting */
 166         BMEdgeHit *linehits;
 167         int totlinehit;
 168
 169         /* Data for mouse-position-derived data (cur) and previous click (prev) */
 170         KnifePosData curr, prev;
 171
 172         int totkedge, totkvert;
 173
 174         BLI_mempool *refs;
 175
 176         float projmat[4][4];
 177
 178         KnifeColors colors;
 179
 180         /* run by the UI or not */
 181         bool is_interactive;
 182
 183         /* operatpr options */
 184         bool cut_through;    /* preference, can be modified at runtime (that feature may go) */
 185         bool only_select;    /* set on initialization */
 186         bool select_result;  /* set on initialization */
 187
 188         bool is_ortho;
 189         float ortho_extent;
 190         float clipsta, clipend;
 191
 192         enum {
 193                 MODE_IDLE,
 194                 MODE_DRAGGING,
 195                 MODE_CONNECT,
 196                 MODE_PANNING
 197         } mode;
 198
 199         int prevmode;
 200         bool snap_midpoints, extend;
 201         bool ignore_edge_snapping;
 202         bool ignore_vert_snapping;
 203
 204         enum {
 205                 ANGLE_FREE,
 206                 ANGLE_0,
 207                 ANGLE_45,
 208                 ANGLE_90,
 209                 ANGLE_135
 210         } angle_snapping;
 211
 212         float (*cagecos)[3];
 213 } KnifeTool_OpData;
 214
 215 static ListBase *knife_get_face_kedges(KnifeTool_OpData *kcd, BMFace *f);
 216
 217 #if 0
 218 static void knife_input_ray_cast(KnifeTool_OpData *kcd, const float mval[2],
 219                                  float r_origin[3], float r_ray[3]);
 220 #endif
 221 static void knife_input_ray_segment(KnifeTool_OpData *kcd, const float mval[2], const float ofs,
 222                                     float r_origin[3], float r_dest[3]);
 223
 224 static void knife_update_header(bContext *C, KnifeTool_OpData *kcd)
 225 {
 226         #define HEADER_LENGTH 256
 227         char header[HEADER_LENGTH];
 228
 229         BLI_snprintf(header, HEADER_LENGTH, IFACE_("LMB: define cut lines, Return/Spacebar: confirm, Esc or RMB: cancel, "
 230                                                    "E: new cut, Ctrl: midpoint snap (%s), Shift: ignore snap (%s), "
 231                                                    "C: angle constrain (%s), Z: cut through (%s)"),
 232                      kcd->snap_midpoints ? IFACE_("On") : IFACE_("Off"),
 233                      kcd->ignore_edge_snapping ?  IFACE_("On") : IFACE_("Off"),
 234                      kcd->angle_snapping ? IFACE_("On") : IFACE_("Off"),
 235                      kcd->cut_through ? IFACE_("On") : IFACE_("Off"));
 236
 237         ED_area_headerprint(CTX_wm_area(C), header);
 238 }
 239
 240 #if 0
 241 BLI_INLINE int round_ftoi(float x)
 242 {
 243         return x > 0.0f ?  (int)(x + 0.5f) : (int)(x - 0.5f);
 244 }
 245 #endif
 246
 247 static void knife_project_v3(const KnifeTool_OpData *kcd, const float co[3], float sco[3])
 248 {
 249         ED_view3d_project_float_v3_m4(kcd->ar, co, sco, (float (*)[4])kcd->projmat);
 250 }
 251
 252 static void knife_pos_data_clear(KnifePosData *kpd)
 253 {
 254         zero_v3(kpd->co);
 255         zero_v3(kpd->cage);
 256         kpd->vert = NULL;
 257         kpd->edge = NULL;
 258         kpd->bmface = NULL;
 259         zero_v2(kpd->mval);
 260 }
 261
 262 static ListBase *knife_empty_list(KnifeTool_OpData *kcd)
 263 {
 264         ListBase *lst;
 265
 266         lst = BLI_memarena_alloc(kcd->arena, sizeof(ListBase));
 267         lst->first = lst->last = NULL;
 268         return lst;
 269 }
 270
 271 static void knife_append_list(KnifeTool_OpData *kcd, ListBase *lst, void *elem)
 272 {
 273         Ref *ref;
 274
 275         ref = BLI_mempool_calloc(kcd->refs);
 276         ref->ref = elem;
 277         BLI_addtail(lst, ref);
 278 }
 279
 280 static Ref *find_ref(ListBase *lb, void *ref)
 281 {
 282         Ref *ref1;
 283
 284         for (ref1 = lb->first; ref1; ref1 = ref1->next) {
 285                 if (ref1->ref == ref)
 286                         return ref1;
 287         }
 288
 289         return NULL;
 290 }
 291
 292 static KnifeEdge *new_knife_edge(KnifeTool_OpData *kcd)
 293 {
 294         kcd->totkedge++;
 295         return BLI_mempool_calloc(kcd->kedges);
 296 }
 297
 298 static void knife_add_to_vert_edges(KnifeTool_OpData *kcd, KnifeEdge *kfe)
 299 {
 300         knife_append_list(kcd, &kfe->v1->edges, kfe);
 301         knife_append_list(kcd, &kfe->v2->edges, kfe);
 302 }
 303
 304 /* Add faces of an edge to a KnifeVert's faces list.  No checks for dups. */
 305 static void knife_add_edge_faces_to_vert(KnifeTool_OpData *kcd, KnifeVert *kfv, BMEdge *e)
 306 {
 307         BMIter bmiter;
 308         BMFace *f;
 309
 310         BM_ITER_ELEM(f, &bmiter, e, BM_FACES_OF_EDGE) {
 311                 knife_append_list(kcd, &kfv->faces, f);
 312         }
 313 }
 314
 315 /* Find a face in common in the two faces lists.
 316  * If more than one, return the first; if none, return NULL */
 317 static BMFace *knife_find_common_face(ListBase *faces1, ListBase *faces2)
 318 {
 319         Ref *ref1, *ref2;
 320
 321         for (ref1 = faces1->first; ref1; ref1 = ref1->next) {
 322                 for (ref2 = faces2->first; ref2; ref2 = ref2->next) {
 323                         if (ref1->ref == ref2->ref)
 324                                 return (BMFace *)(ref1->ref);
 325                 }
 326         }
 327         return NULL;
 328 }
 329
 330 static KnifeVert *new_knife_vert(KnifeTool_OpData *kcd, const float co[3], float *cageco)
 331 {
 332         KnifeVert *kfv = BLI_mempool_calloc(kcd->kverts);
 333
 334         kcd->totkvert++;
 335
 336         copy_v3_v3(kfv->co, co);
 337         copy_v3_v3(kfv->cageco, cageco);
 338         copy_v3_v3(kfv->sco, co);
 339
 340         knife_project_v3(kcd, kfv->co, kfv->sco);
 341
 342         return kfv;
 343 }
 344
 345 /* get a KnifeVert wrapper for an existing BMVert */
 346 static KnifeVert *get_bm_knife_vert(KnifeTool_OpData *kcd, BMVert *v)
 347 {
 348         KnifeVert *kfv = BLI_ghash_lookup(kcd->origvertmap, v);
 349
 350         if (!kfv) {
 351                 BMIter bmiter;
 352                 BMFace *f;
 353
 354                 kfv = new_knife_vert(kcd, v->co, kcd->cagecos[BM_elem_index_get(v)]);
 355                 kfv->v = v;
 356                 BLI_ghash_insert(kcd->origvertmap, v, kfv);
 357                 BM_ITER_ELEM(f, &bmiter, v, BM_FACES_OF_VERT) {
 358                         knife_append_list(kcd, &kfv->faces, f);
 359                 }
 360         }
 361
 362         return kfv;
 363 }
 364
 365 /* get a KnifeEdge wrapper for an existing BMEdge */
 366 static KnifeEdge *get_bm_knife_edge(KnifeTool_OpData *kcd, BMEdge *e)
 367 {
 368         KnifeEdge *kfe = BLI_ghash_lookup(kcd->origedgemap, e);
 369         if (!kfe) {
 370                 BMIter bmiter;
 371                 BMFace *f;
 372
 373                 kfe = new_knife_edge(kcd);
 374                 kfe->e = e;
 375                 kfe->v1 = get_bm_knife_vert(kcd, e->v1);
 376                 kfe->v2 = get_bm_knife_vert(kcd, e->v2);
 377
 378                 knife_add_to_vert_edges(kcd, kfe);
 379
 380                 BLI_ghash_insert(kcd->origedgemap, e, kfe);
 381
 382                 BM_ITER_ELEM(f, &bmiter, e, BM_FACES_OF_EDGE) {
 383                         knife_append_list(kcd, &kfe->faces, f);
 384                 }
 385         }
 386
 387         return kfe;
 388 }
 389
 390 /* User has just clicked for first time or first time after a restart (E key).
 391  * Copy the current position data into prev. */
 392 static void knife_start_cut(KnifeTool_OpData *kcd)
 393 {
 394         kcd->prev = kcd->curr;
 395         kcd->curr.is_space = 0; /*TODO: why do we do this? */
 396
 397         if (kcd->prev.vert == NULL && kcd->prev.edge == NULL && is_zero_v3(kcd->prev.cage)) {
 398                 /* Make prevcage a point on the view ray to mouse closest to a point on model: choose vertex 0 */
 399                 float origin[3], origin_ofs[3];
 400                 BMVert *v0;
 401
 402                 knife_input_ray_segment(kcd, kcd->curr.mval, 1.0f, origin, origin_ofs);
 403                 v0 = BM_vert_at_index(kcd->em->bm, 0);
 404                 if (v0) {
 405                         closest_to_line_v3(kcd->prev.cage, v0->co, origin_ofs, origin);
 406                         copy_v3_v3(kcd->prev.co, kcd->prev.cage); /*TODO: do we need this? */
 407                         copy_v3_v3(kcd->curr.cage, kcd->prev.cage);
 408                         copy_v3_v3(kcd->curr.co, kcd->prev.co);
 409                 }
 410         }
 411 }
 412
 413 static ListBase *knife_get_face_kedges(KnifeTool_OpData *kcd, BMFace *f)
 414 {
 415         ListBase *lst = BLI_ghash_lookup(kcd->kedgefacemap, f);
 416
 417         if (!lst) {
 418                 BMIter bmiter;
 419                 BMEdge *e;
 420
 421                 lst = knife_empty_list(kcd);
 422
 423                 BM_ITER_ELEM(e, &bmiter, f, BM_EDGES_OF_FACE) {
 424                         knife_append_list(kcd, lst, get_bm_knife_edge(kcd, e));
 425                 }
 426
 427                 BLI_ghash_insert(kcd->kedgefacemap, f, lst);
 428         }
 429
 430         return lst;
 431 }
 432
 433 /* finds the proper face to restrict face fill to */
 434 static void knife_find_basef(KnifeEdge *kfe)
 435 {
 436         kfe->basef = knife_find_common_face(&kfe->v1->faces, &kfe->v2->faces);
 437 }
 438
 439 static void knife_edge_append_face(KnifeTool_OpData *kcd, KnifeEdge *kfe, BMFace *f)
 440 {
 441         knife_append_list(kcd, knife_get_face_kedges(kcd, f), kfe);
 442         knife_append_list(kcd, &kfe->faces, f);
 443 }
 444
 445 static KnifeVert *knife_split_edge(KnifeTool_OpData *kcd, KnifeEdge *kfe, float co[3], KnifeEdge **newkfe_out)
 446 {
 447         KnifeEdge *newkfe = new_knife_edge(kcd);
 448         Ref *ref;
 449         BMFace *f;
 450         float perc, cageco[3], l12;
 451
 452         l12 = len_v3v3(kfe->v1->co, kfe->v2->co);
 453         if (l12 < KNIFE_FLT_EPS) {
 454                 copy_v3_v3(cageco, kfe->v1->cageco);
 455         }
 456         else {
 457                 perc = len_v3v3(co, kfe->v1->co) / l12;
 458                 interp_v3_v3v3(cageco, kfe->v1->cageco, kfe->v2->cageco, perc);
 459         }
 460
 461         newkfe->v1 = kfe->v1;
 462         newkfe->v2 = new_knife_vert(kcd, co, cageco);
 463         newkfe->v2->draw = 1;
 464         if (kfe->e) {
 465                 knife_add_edge_faces_to_vert(kcd, newkfe->v2, kfe->e);
 466         }
 467         else {
 468                 /* kfe cuts across an existing face.
 469                  * If v1 and v2 are in multiple faces together (e.g., if they
 470                  * are in doubled polys) then this arbitrarily chooses one of them */
 471                 f = knife_find_common_face(&kfe->v1->faces, &kfe->v2->faces);
 472                 if (f)
 473                         knife_append_list(kcd, &newkfe->v2->faces, f);
 474         }
 475         newkfe->basef = kfe->basef;
 476
 477         ref = find_ref(&kfe->v1->edges, kfe);
 478         BLI_remlink(&kfe->v1->edges, ref);
 479
 480         kfe->v1 = newkfe->v2;
 481         BLI_addtail(&kfe->v1->edges, ref);
 482
 483         for (ref = kfe->faces.first; ref; ref = ref->next)
 484                 knife_edge_append_face(kcd, newkfe, ref->ref);
 485
 486         knife_add_to_vert_edges(kcd, newkfe);
 487
 488         newkfe->draw = kfe->draw;
 489         newkfe->e = kfe->e;
 490
 491         *newkfe_out = newkfe;
 492
 493         return newkfe->v2;
 494 }
 495
 496 /* Make a single KnifeEdge for cut from kcd->prev to kcd->curr.
 497  * and move cur data to prev. */
 498 static void knife_add_single_cut(KnifeTool_OpData *kcd)
 499 {
 500         KnifeEdge *kfe = new_knife_edge(kcd), *kfe2 = NULL, *kfe3 = NULL;
 501
 502         if (kcd->prev.vert && kcd->prev.vert == kcd->curr.vert)
 503                 return;
 504         if (kcd->prev.edge && kcd->prev.edge == kcd->curr.edge)
 505                 return;
 506
 507         kfe->draw = true;
 508
 509         if (kcd->prev.vert) {
 510                 kfe->v1 = kcd->prev.vert;
 511         }
 512         else if (kcd->prev.edge) {
 513                 kfe->v1 = knife_split_edge(kcd, kcd->prev.edge, kcd->prev.co, &kfe2);
 514         }
 515         else {
 516                 kfe->v1 = new_knife_vert(kcd, kcd->prev.co, kcd->prev.co);
 517                 kfe->v1->draw = kfe->draw = !kcd->prev.is_space;
 518                 kfe->v1->in_space = kcd->prev.is_space;
 519                 kfe->draw = !kcd->prev.is_space;
 520                 kfe->v1->is_face = true;
 521                 if (kfe->v1->draw && kcd->prev.bmface)
 522                         knife_append_list(kcd, &kfe->v1->faces, kcd->prev.bmface);
 523         }
 524
 525         if (kcd->curr.vert) {
 526                 kfe->v2 = kcd->curr.vert;
 527         }
 528         else if (kcd->curr.edge) {
 529                 kfe->v2 = knife_split_edge(kcd, kcd->curr.edge, kcd->curr.co, &kfe3);
 530                 kcd->curr.vert = kfe->v2;
 531         }
 532         else {
 533                 kfe->v2 = new_knife_vert(kcd, kcd->curr.co, kcd->curr.co);
 534                 kfe->v2->draw = !kcd->curr.is_space;
 535                 kfe->v2->is_face = true;
 536                 kfe->v2->in_space = kcd->curr.is_space;
 537                 if (kfe->v2->draw && kcd->curr.bmface)
 538                         knife_append_list(kcd, &kfe->v2->faces, kcd->curr.bmface);
 539
 540                 if (kcd->curr.is_space)
 541                         kfe->draw = false;
 542
 543                 kcd->curr.vert = kfe->v2;
 544         }
 545
 546         knife_find_basef(kfe);
 547
 548         knife_add_to_vert_edges(kcd, kfe);
 549
 550         if (kfe->basef && !find_ref(&kfe->faces, kfe->basef))
 551                 knife_edge_append_face(kcd, kfe, kfe->basef);
 552
 553         /* sanity check to make sure we're in the right edge/face lists */
 554         if (kcd->curr.bmface) {
 555                 if (!find_ref(&kfe->faces, kcd->curr.bmface)) {
 556                         knife_edge_append_face(kcd, kfe, kcd->curr.bmface);
 557                 }
 558
 559                 if (kcd->prev.bmface && kcd->prev.bmface != kcd->curr.bmface) {
 560                         if (!find_ref(&kfe->faces, kcd->prev.bmface)) {
 561                                 knife_edge_append_face(kcd, kfe, kcd->prev.bmface);
 562                         }
 563                 }
 564         }
 565
 566         /* set up for next cut */
 567         kcd->prev = kcd->curr;
 568 }
 569
 570 static int verge_linehit(const void *vlh1, const void *vlh2)
 571 {
 572         const BMEdgeHit *lh1 = vlh1, *lh2 = vlh2;
 573
 574         if      (lh1->l < lh2->l) return -1;
 575         else if (lh1->l > lh2->l) return 1;
 576         else return 0;
 577 }
 578
 579 /* If there's a linehit connected (same face) as testi in range [firsti, lasti], return the first such, else -1.
 580  * If testi is out of range, look for connection to f instead, if f is non-NULL */
 581 static int find_connected_linehit(KnifeTool_OpData *kcd, int testi, BMFace *f, int firsti, int lasti)
 582 {
 583         int i;
 584
 585         for (i = firsti; i <= lasti; i++) {
 586                 if (testi >= 0 && testi < kcd->totlinehit) {
 587                         if (knife_find_common_face(&kcd->linehits[testi].kfe->faces,
 588                                                    &kcd->linehits[i].kfe->faces))
 589                         {
 590                                 return i;
 591                         }
 592                 }
 593                 else if (f) {
 594                         if (find_ref(&kcd->linehits[i].kfe->faces, f))
 595                                 return i;
 596                 }
 597         }
 598         return -1;
 599 }
 600
 601 /* Sort in order of distance along cut line, but take care when distances are equal */
 602 static void knife_sort_linehits(KnifeTool_OpData *kcd)
 603 {
 604         int i, j, k, nexti, nsame;
 605
 606         qsort(kcd->linehits, kcd->totlinehit, sizeof(BMEdgeHit), verge_linehit);
 607
 608         /* for ranges of equal "l", swap if neccesary to make predecessor and
 609          * successor faces connected to the linehits at either end of the range */
 610         for (i = 0; i < kcd->totlinehit - 1; i = nexti) {
 611                 for (j = i + 1; j < kcd->totlinehit; j++) {
 612                         if (fabsf(kcd->linehits[j].l - kcd->linehits[i].l) > KNIFE_FLT_EPS)
 613                                 break;
 614                 }
 615                 nexti = j;
 616                 j--;
 617                 nsame = j - i;
 618                 if (nsame > 0) {
 619                         /* find something connected to predecessor of equal range */
 620                         k = find_connected_linehit(kcd, i - 1, kcd->prev.bmface, i, j);
 621                         if (k != -1) {
 622                                 if (k != i) {
 623                                         SWAP(BMEdgeHit, kcd->linehits[i], kcd->linehits[k]);
 624                                 }
 625                                 i++;
 626                                 nsame--;
 627                         }
 628                         if (nsame > 0) {
 629                                 /* find something connected to successor of equal range */
 630                                 k = find_connected_linehit(kcd, j + 1, kcd->curr.bmface, i, j);
 631                                 if (k != -1 && k != j) {
 632                                         SWAP(BMEdgeHit, kcd->linehits[j], kcd->linehits[k]);
 633                                 }
 634                         }
 635                         /* rest of same range doesn't matter because we won't connect them */
 636                 }
 637         }
 638 }
 639
 640 static void knife_add_single_cut_through(KnifeTool_OpData *kcd, KnifeVert *v1, KnifeVert *v2, BMFace *f)
 641 {
 642         KnifeEdge *kfenew;
 643
 644         kfenew = new_knife_edge(kcd);
 645         kfenew->basef = f;
 646         kfenew->v1 = v1;
 647         kfenew->v2 = v2;
 648         kfenew->draw = true;
 649
 650         knife_add_to_vert_edges(kcd, kfenew);
 651
 652         if (!find_ref(&kfenew->faces, f))
 653                 knife_edge_append_face(kcd, kfenew, f);
 654 }
 655
 656 static void knife_get_vert_faces(KnifeTool_OpData *kcd, KnifeVert *kfv, BMFace *facef, ListBase *lst)
 657 {
 658         BMIter bmiter;
 659         BMFace *f;
 660         Ref *r;
 661
 662         if (kfv->is_face && facef) {
 663                 knife_append_list(kcd, lst, facef);
 664         }
 665         else if (kfv->v) {
 666                 BM_ITER_ELEM (f, &bmiter, kfv->v, BM_FACES_OF_VERT) {
 667                         knife_append_list(kcd, lst, f);
 668                 }
 669         }
 670         else {
 671                 for (r = kfv->faces.first; r; r = r->next) {
 672                         knife_append_list(kcd, lst, r->ref);
 673                 }
 674         }
 675 }
 676
 677 static void knife_get_edge_faces(KnifeTool_OpData *kcd, KnifeEdge *kfe, ListBase *lst)
 678 {
 679         BMIter bmiter;
 680         BMFace *f;
 681
 682         if (kfe->e) {
 683                 BM_ITER_ELEM (f, &bmiter, kfe->e, BM_FACES_OF_EDGE) {
 684                         knife_append_list(kcd, lst, f);
 685                 }
 686         }
 687 }
 688
 689 /* BMESH_TODO: add more functionality to cut-through:
 690  *    - cutting "in face" (e.g., holes) should cut in all faces, not just visible one
 691  *    - perhaps improve O(n^2) algorithm used here */
 692 static void knife_cut_through(KnifeTool_OpData *kcd)
 693 {
 694         BMEdgeHit *lh, *lh2;
 695         BMFace *f;
 696         KnifeEdge *kfe, *kfe2, *kfe3;
 697         KnifeVert *v1, *v2, *firstv = NULL, *lastv = NULL;
 698         ListBase firstfaces = {NULL, NULL}, lastfaces = {NULL, NULL};
 699         Ref *r, *r2;
 700         KnifeEdge **splitkfe;
 701         int i, j;
 702
 703         if (!kcd->totlinehit) {
 704                 /* if no linehits then no interesting back face stuff to do */
 705                 knife_add_single_cut(kcd);
 706                 return;
 707         }
 708
 709         /* TODO: probably don't need to sort at all */
 710         qsort(kcd->linehits, kcd->totlinehit, sizeof(BMEdgeHit), verge_linehit);
 711         splitkfe = MEM_callocN(kcd->totlinehit * sizeof(KnifeEdge *), "knife_cut_through");
 712
 713         if (kcd->prev.vert) {
 714                 if (kcd->prev.vert == kcd->curr.vert)
 715                         return;
 716                 firstv = kcd->prev.vert;
 717                 knife_get_vert_faces(kcd, firstv, kcd->prev.bmface, &firstfaces);
 718         }
 719         else if (kcd->prev.edge) {
 720                 if (kcd->prev.edge == kcd->curr.edge)
 721                         return;
 722                 firstv = knife_split_edge(kcd, kcd->prev.edge, kcd->prev.co, &kfe3);
 723                 knife_get_edge_faces(kcd, kcd->prev.edge, &firstfaces);
 724         }
 725
 726         if (kcd->curr.vert) {
 727                 lastv = kcd->curr.vert;
 728                 knife_get_vert_faces(kcd, lastv, kcd->curr.bmface, &lastfaces);
 729         }
 730         else if (kcd->curr.edge) {
 731                 lastv = knife_split_edge(kcd, kcd->curr.edge, kcd->curr.co, &kfe3);
 732                 knife_get_edge_faces(kcd, kcd->curr.edge, &lastfaces);
 733         }
 734
 735         if (firstv) {
 736                 /* For each face incident to firstv,
 737                  * find the first following linehit (if any) sharing that face and connect */
 738                 for (r = firstfaces.first; r; r = r->next) {
 739                         bool found = false;
 740                         f = r->ref;
 741                         for (j = 0, lh2 = kcd->linehits; j < kcd->totlinehit && !found; j++, lh2++) {
 742                                 kfe2 = lh2->kfe;
 743                                 for (r2 = kfe2->faces.first; r2; r2 = r2->next) {
 744                                         if (r2->ref == f) {
 745                                                 v2 = splitkfe[j] ? kfe2->v1 : knife_split_edge(kcd, kfe2, lh2->hit, &splitkfe[j]);
 746                                                 knife_add_single_cut_through(kcd, firstv, v2, f);
 747                                                 found = true;
 748                                                 break;
 749                                         }
 750                                 }
 751                         }
 752                         if (!found && lastv) {
 753                                 for (r2 = lastfaces.first; r2; r2 = r2->next) {
 754                                         if (r2->ref == f) {
 755                                                 knife_add_single_cut_through(kcd, firstv, lastv, f);
 756                                                 break;
 757                                         }
 758                                 }
 759                         }
 760                 }
 761         }
 762
 763         for (i = 0, lh = kcd->linehits; i < kcd->totlinehit; i++, lh++) {
 764                 kfe = lh->kfe;
 765
 766                 /* For each face attached to edge for this linehit,
 767                  * find the first following linehit (if any) sharing that face and connect */
 768                 for (r = kfe->faces.first; r; r = r->next) {
 769                         bool found = false;
 770                         f = r->ref;
 771                         for (j = i + 1, lh2 = lh + 1; j < kcd->totlinehit && !found; j++, lh2++) {
 772                                 kfe2 = lh2->kfe;
 773                                 for (r2 = kfe2->faces.first; r2; r2 = r2->next) {
 774                                         if (r2->ref == f) {
 775                                                 v1 = splitkfe[i] ? kfe->v1 : knife_split_edge(kcd, kfe, lh->hit, &splitkfe[i]);
 776                                                 v2 = splitkfe[j] ? kfe2->v1 : knife_split_edge(kcd, kfe2, lh2->hit, &splitkfe[j]);
 777                                                 knife_add_single_cut_through(kcd, v1, v2, f);
 778                                                 found = true;
 779                                                 break;
 780                                         }
 781                                 }
 782                         }
 783                         if (!found && lastv) {
 784                                 for (r2 = lastfaces.first; r2; r2 = r2->next) {
 785                                         if (r2->ref == f) {
 786                                                 v1 = splitkfe[i] ? kfe->v1 : knife_split_edge(kcd, kfe, lh->hit, &splitkfe[i]);
 787                                                 knife_add_single_cut_through(kcd, v1, lastv, f);
 788                                                 break;
 789                                         }
 790                                 }
 791                         }
 792                 }
 793         }
 794
 795         MEM_freeN(splitkfe);
 796         MEM_freeN(kcd->linehits);
 797         kcd->linehits = NULL;
 798         kcd->totlinehit = 0;
 799
 800         /* set up for next cut */
 801         kcd->curr.vert = lastv;
 802         kcd->prev = kcd->curr;
 803 }
 804
 805 /* User has just left-clicked after the first time.
 806  * Add all knife cuts implied by line from prev to curr.
 807  * If that line crossed edges then kcd->linehits will be non-NULL. */
 808 static void knife_add_cut(KnifeTool_OpData *kcd)
 809 {
 810         KnifePosData savcur = kcd->curr;
 811
 812         if (kcd->cut_through) {
 813                 knife_cut_through(kcd);
 814         }
 815         else if (kcd->linehits) {
 816                 BMEdgeHit *lh, *lastlh, *firstlh;
 817                 int i;
 818
 819                 knife_sort_linehits(kcd);
 820
 821                 lh = kcd->linehits;
 822                 lastlh = firstlh = NULL;
 823                 for (i = 0; i < kcd->totlinehit; i++, (lastlh = lh), lh++) {
 824                         BMFace *f = lastlh ? lastlh->f : lh->f;
 825
 826                         if (lastlh && len_squared_v3v3(lastlh->hit, lh->hit) == 0.0f) {
 827                                 if (!firstlh)
 828                                         firstlh = lastlh;
 829                                 continue;
 830                         }
 831                         else if (lastlh && firstlh) {
 832                                 if (firstlh->v || lastlh->v) {
 833                                         KnifeVert *kfv = firstlh->v ? firstlh->v : lastlh->v;
 834
 835                                         kcd->prev.vert = kfv;
 836                                         copy_v3_v3(kcd->prev.co, firstlh->hit);
 837                                         copy_v3_v3(kcd->prev.cage, firstlh->cagehit);
 838                                         kcd->prev.edge = NULL;
 839                                         kcd->prev.bmface = f;
 840                                         /* TODO: should we set prev.in_space = 0 ? */
 841                                 }
 842                                 lastlh = firstlh = NULL;
 843                         }
 844
 845                         if (len_squared_v3v3(kcd->prev.cage, lh->realhit) < KNIFE_FLT_EPS_SQUARED)
 846                                 continue;
 847                         if (len_squared_v3v3(kcd->curr.cage, lh->realhit) < KNIFE_FLT_EPS_SQUARED)
 848                                 continue;
 849
 850                         /* first linehit may be down face parallel to view */
 851                         if (!lastlh && fabsf(lh->l) < KNIFE_FLT_EPS)
 852                                 continue;
 853
 854                         if (kcd->prev.is_space) {
 855                                 kcd->prev.is_space = 0;
 856                                 copy_v3_v3(kcd->prev.co, lh->hit);
 857                                 copy_v3_v3(kcd->prev.cage, lh->cagehit);
 858                                 kcd->prev.vert = NULL;
 859                                 kcd->prev.edge = lh->kfe;
 860                                 kcd->prev.bmface = lh->f;
 861                                 continue;
 862                         }
 863
 864                         kcd->curr.is_space = 0;
 865                         kcd->curr.edge = lh->kfe;
 866                         kcd->curr.bmface = lh->f;
 867                         kcd->curr.vert = lh->v;
 868                         copy_v3_v3(kcd->curr.co, lh->hit);
 869                         copy_v3_v3(kcd->curr.cage, lh->cagehit);
 870
 871                         /* don't draw edges down faces parallel to view */
 872                         if (lastlh && fabsf(lastlh->l - lh->l) < KNIFE_FLT_EPS) {
 873                                 kcd->prev = kcd->curr;
 874                                 continue;
 875                         }
 876
 877                         knife_add_single_cut(kcd);
 878                 }
 879
 880                 if (savcur.is_space) {
 881                         kcd->prev = savcur;
 882                 }
 883                 else {
 884                         kcd->curr = savcur;
 885                         knife_add_single_cut(kcd);
 886                 }
 887
 888                 MEM_freeN(kcd->linehits);
 889                 kcd->linehits = NULL;
 890                 kcd->totlinehit = 0;
 891         }
 892         else {
 893                 knife_add_single_cut(kcd);
 894         }
 895 }
 896
 897 static void knife_finish_cut(KnifeTool_OpData *UNUSED(kcd))
 898 {
 899
 900 }
 901
 902 static void knifetool_draw_angle_snapping(const KnifeTool_OpData *kcd)
 903 {
 904         bglMats mats;
 905         double u[3], u1[2], u2[2], v1[3], v2[3], dx, dy;
 906         double wminx, wminy, wmaxx, wmaxy;
 907
 908         /* make u the window coords of prevcage */
 909         view3d_get_transformation(kcd->ar, kcd->vc.rv3d, kcd->ob, &mats);
 910         gluProject(kcd->prev.cage[0], kcd->prev.cage[1], kcd->prev.cage[2],
 911                    mats.modelview, mats.projection, mats.viewport,
 912                    &u[0], &u[1], &u[2]);
 913
 914         /* make u1, u2 the points on window going through u at snap angle */
 915         wminx = kcd->ar->winrct.xmin;
 916         wmaxx = kcd->ar->winrct.xmin + kcd->ar->winx;
 917         wminy = kcd->ar->winrct.ymin;
 918         wmaxy = kcd->ar->winrct.ymin + kcd->ar->winy;
 919
 920         switch (kcd->angle_snapping) {
 921                 case ANGLE_0:
 922                         u1[0] = wminx;
 923                         u2[0] = wmaxx;
 924                         u1[1] = u2[1] = u[1];
 925                         break;
 926                 case ANGLE_90:
 927                         u1[0] = u2[0] = u[0];
 928                         u1[1] = wminy;
 929                         u2[1] = wmaxy;
 930                         break;
 931                 case ANGLE_45:
 932                         /* clip against left or bottom */
 933                         dx = u[0] - wminx;
 934                         dy = u[1] - wminy;
 935                         if (dy > dx) {
 936                                 u1[0] = wminx;
 937                                 u1[1] = u[1] - dx;
 938                         }
 939                         else {
 940                                 u1[0] = u[0] - dy;
 941                                 u1[1] = wminy;
 942                         }
 943                         /* clip against right or top */
 944                         dx = wmaxx - u[0];
 945                         dy = wmaxy - u[1];
 946                         if (dy > dx) {
 947                                 u2[0] = wmaxx;
 948                                 u2[1] = u[1] + dx;
 949                         }
 950                         else {
 951                                 u2[0] = u[0] + dy;
 952                                 u2[1] = wmaxy;
 953                         }
 954                         break;
 955                 case ANGLE_135:
 956                         /* clip against right or bottom */
 957                         dx = wmaxx - u[0];
 958                         dy = u[1] - wminy;
 959                         if (dy > dx) {
 960                                 u1[0] = wmaxx;
 961                                 u1[1] = u[1] - dx;
 962                         }
 963                         else {
 964                                 u1[0] = u[0] + dy;
 965                                 u1[1] = wminy;
 966                         }
 967                         /* clip against left or top */
 968                         dx = u[0] - wminx;
 969                         dy = wmaxy - u[1];
 970                         if (dy > dx) {
 971                                 u2[0] = wminx;
 972                                 u2[1] = u[1] + dx;
 973                         }
 974                         else {
 975                                 u2[0] = u[0] - dy;
 976                                 u2[1] = wmaxy;
 977                         }
 978                         break;
 979                 default:
 980                         return;
 981         }
 982
 983         /* unproject u1 and u2 back into object space */
 984         gluUnProject(u1[0], u1[1], 0.0,
 985                      mats.modelview, mats.projection, mats.viewport,
 986                      &v1[0], &v1[1], &v1[2]);
 987         gluUnProject(u2[0], u2[1], 0.0,
 988                      mats.modelview, mats.projection, mats.viewport,
 989                      &v2[0], &v2[1], &v2[2]);
 990
 991         UI_ThemeColor(TH_TRANSFORM);
 992         glLineWidth(2.0);
 993         glBegin(GL_LINES);
 994         glVertex3dv(v1);
 995         glVertex3dv(v2);
 996         glEnd();
 997 }
 998
 999 static void knife_init_colors(KnifeColors *colors)
1000 {
1001         /* possible BMESH_TODO: add explicit themes or calculate these by
1002          * figuring out contrasting colors with grid / edges / verts
1003          * a la UI_make_axis_color */
1004         UI_GetThemeColor3ubv(TH_NURB_VLINE, colors->line);
1005         UI_GetThemeColor3ubv(TH_NURB_ULINE, colors->edge);
1006         UI_GetThemeColor3ubv(TH_HANDLE_SEL_VECT, colors->curpoint);
1007         UI_GetThemeColor3ubv(TH_HANDLE_SEL_VECT, colors->curpoint_a);
1008         colors->curpoint_a[3] = 102;
1009         UI_GetThemeColor3ubv(TH_ACTIVE_SPLINE, colors->point);
1010         UI_GetThemeColor3ubv(TH_ACTIVE_SPLINE, colors->point_a);
1011         colors->point_a[3] = 102;
1012 }
1013
1014 /* modal loop selection drawing callback */
1015 static void knifetool_draw(const bContext *C, ARegion *UNUSED(ar), void *arg)
1016 {
1017         View3D *v3d = CTX_wm_view3d(C);
1018         const KnifeTool_OpData *kcd = arg;
1019
1020         if (v3d->zbuf) glDisable(GL_DEPTH_TEST);
1021
1022         glPolygonOffset(1.0f, 1.0f);
1023
1024         glPushMatrix();
1025         glMultMatrixf(kcd->ob->obmat);
1026
1027         if (kcd->mode == MODE_DRAGGING) {
1028                 if (kcd->angle_snapping != ANGLE_FREE)
1029                         knifetool_draw_angle_snapping(kcd);
1030
1031                 glColor3ubv(kcd->colors.line);
1032
1033                 glLineWidth(2.0);
1034
1035                 glBegin(GL_LINES);
1036                 glVertex3fv(kcd->prev.cage);
1037                 glVertex3fv(kcd->curr.cage);
1038                 glEnd();
1039
1040                 glLineWidth(1.0);
1041         }
1042
1043         if (kcd->curr.edge) {
1044                 glColor3ubv(kcd->colors.edge);
1045                 glLineWidth(2.0);
1046
1047                 glBegin(GL_LINES);
1048                 glVertex3fv(kcd->curr.edge->v1->cageco);
1049                 glVertex3fv(kcd->curr.edge->v2->cageco);
1050                 glEnd();
1051
1052                 glLineWidth(1.0);
1053         }
1054         else if (kcd->curr.vert) {
1055                 glColor3ubv(kcd->colors.point);
1056                 glPointSize(11);
1057
1058                 glBegin(GL_POINTS);
1059                 glVertex3fv(kcd->curr.cage);
1060                 glEnd();
1061         }
1062
1063         if (kcd->curr.bmface) {
1064                 glColor3ubv(kcd->colors.curpoint);
1065                 glPointSize(9);
1066
1067                 glBegin(GL_POINTS);
1068                 glVertex3fv(kcd->curr.cage);
1069                 glEnd();
1070         }
1071
1072         if (kcd->totlinehit > 0) {
1073                 const float vthresh4 = kcd->vthresh / 4.0f;
1074                 const float vthresh4_sq = vthresh4 * vthresh4;
1075
1076                 BMEdgeHit *lh;
1077                 int i;
1078
1079                 glEnable(GL_BLEND);
1080                 glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
1081
1082                 /* draw any snapped verts first */
1083                 glColor4ubv(kcd->colors.point_a);
1084                 glPointSize(11);
1085                 glBegin(GL_POINTS);
1086                 lh = kcd->linehits;
1087                 for (i = 0; i < kcd->totlinehit; i++, lh++) {
1088                         float sv1[3], sv2[3];
1089
1090                         knife_project_v3(kcd, lh->kfe->v1->cageco, sv1);
1091                         knife_project_v3(kcd, lh->kfe->v2->cageco, sv2);
1092                         knife_project_v3(kcd, lh->cagehit, lh->schit);
1093
1094                         if (len_squared_v2v2(lh->schit, sv1) < vthresh4_sq) {
1095                                 copy_v3_v3(lh->cagehit, lh->kfe->v1->cageco);
1096                                 glVertex3fv(lh->cagehit);
1097                                 lh->v = lh->kfe->v1;
1098                         }
1099                         else if (len_squared_v2v2(lh->schit, sv2) < vthresh4_sq) {
1100                                 copy_v3_v3(lh->cagehit, lh->kfe->v2->cageco);
1101                                 glVertex3fv(lh->cagehit);
1102                                 lh->v = lh->kfe->v2;
1103                         }
1104                 }
1105                 glEnd();
1106
1107                 /* now draw the rest */
1108                 glColor4ubv(kcd->colors.curpoint_a);
1109                 glPointSize(7);
1110                 glBegin(GL_POINTS);
1111                 lh = kcd->linehits;
1112                 for (i = 0; i < kcd->totlinehit; i++, lh++) {
1113                         glVertex3fv(lh->cagehit);
1114                 }
1115                 glEnd();
1116                 glDisable(GL_BLEND);
1117         }
1118
1119         if (kcd->totkedge > 0) {
1120                 BLI_mempool_iter iter;
1121                 KnifeEdge *kfe;
1122
1123                 glLineWidth(1.0);
1124                 glBegin(GL_LINES);
1125
1126                 BLI_mempool_iternew(kcd->kedges, &iter);
1127                 for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
1128                         if (!kfe->draw)
1129                                 continue;
1130
1131                         glColor3ubv(kcd->colors.line);
1132
1133                         glVertex3fv(kfe->v1->cageco);
1134                         glVertex3fv(kfe->v2->cageco);
1135                 }
1136
1137                 glEnd();
1138                 glLineWidth(1.0);
1139         }
1140
1141         if (kcd->totkvert > 0) {
1142                 BLI_mempool_iter iter;
1143                 KnifeVert *kfv;
1144
1145                 glPointSize(5.0);
1146
1147                 glBegin(GL_POINTS);
1148                 BLI_mempool_iternew(kcd->kverts, &iter);
1149                 for (kfv = BLI_mempool_iterstep(&iter); kfv; kfv = BLI_mempool_iterstep(&iter)) {
1150                         if (!kfv->draw)
1151                                 continue;
1152
1153                         glColor3ubv(kcd->colors.point);
1154
1155                         glVertex3fv(kfv->cageco);
1156                 }
1157
1158                 glEnd();
1159         }
1160
1161         glPopMatrix();
1162
1163         if (v3d->zbuf) glEnable(GL_DEPTH_TEST);
1164 }
1165
1166 static float len_v3_tri_side_max(const float v1[3], const float v2[3], const float v3[3])
1167 {
1168         const float s1 = len_squared_v3v3(v1, v2);
1169         const float s2 = len_squared_v3v3(v2, v3);
1170         const float s3 = len_squared_v3v3(v3, v1);
1171
1172         return sqrtf(max_fff(s1, s2, s3));
1173 }
1174
1175 static BMEdgeHit *knife_edge_tri_isect(KnifeTool_OpData *kcd, BMBVHTree *bmtree,
1176                                        const float v1[3],  const float v2[3], const float v3[3],
1177                                        SmallHash *ehash, bglMats *mats, int *count)
1178 {
1179         BVHTree *tree2 = BLI_bvhtree_new(3, FLT_EPSILON * 4, 8, 8), *tree = BKE_bmbvh_tree_get(bmtree);
1180         BMEdgeHit *edges = NULL;
1181         BLI_array_declare(edges);
1182         BVHTreeOverlap *results, *result;
1183         BMLoop **ls;
1184         float cos[9], lambda;
1185         unsigned int tot = 0;
1186         int i;
1187
1188         /* for comparing distances, error of intersection depends on triangle scale.
1189          * need to scale down before squaring for accurate comparison */
1190         const float depsilon = (FLT_EPSILON / 2.0f) * len_v3_tri_side_max(v1, v2, v3);
1191         const float depsilon_sq = depsilon * depsilon;
1192
1193         copy_v3_v3(cos + 0, v1);
1194         copy_v3_v3(cos + 3, v2);
1195         copy_v3_v3(cos + 6, v3);
1196
1197         BLI_bvhtree_insert(tree2, 0, cos, 3);
1198         BLI_bvhtree_balance(tree2);
1199
1200         result = results = BLI_bvhtree_overlap(tree, tree2, &tot);
1201
1202         for (i = 0; i < tot; i++, result++) {
1203                 BMLoop *l1;
1204                 BMFace *f_hit;
1205                 ListBase *lst;
1206                 Ref *ref;
1207
1208                 ls = (BMLoop **)kcd->em->looptris[result->indexA];
1209
1210                 l1 = ls[0];
1211                 lst = knife_get_face_kedges(kcd, l1->f);
1212
1213                 for (ref = lst->first; ref; ref = ref->next) {
1214                         KnifeEdge *kfe = ref->ref;
1215
1216                         if (BLI_smallhash_haskey(ehash, (intptr_t)kfe)) {
1217                                 continue;  /* We already found a hit on this knife edge */
1218                         }
1219
1220                         if (isect_line_tri_v3(kfe->v1->cageco, kfe->v2->cageco, v1, v2, v3, &lambda, NULL)) {
1221                                 float p[3], no[3], view[3], sp[3];
1222
1223                                 interp_v3_v3v3(p, kfe->v1->cageco, kfe->v2->cageco, lambda);
1224
1225                                 if (kcd->curr.vert && len_squared_v3v3(kcd->curr.vert->cageco, p) < depsilon_sq) {
1226                                         continue;
1227                                 }
1228                                 if (kcd->prev.vert && len_squared_v3v3(kcd->prev.vert->cageco, p) < depsilon_sq) {
1229                                         continue;
1230                                 }
1231                                 if (len_squared_v3v3(kcd->prev.cage, p) < depsilon_sq ||
1232                                     len_squared_v3v3(kcd->curr.cage, p) < depsilon_sq)
1233                                 {
1234                                         continue;
1235                                 }
1236                                 if ((kcd->vc.rv3d->rflag & RV3D_CLIPPING) &&
1237                                     ED_view3d_clipping_test(kcd->vc.rv3d, p, true))
1238                                 {
1239                                         continue;
1240                                 }
1241
1242                                 knife_project_v3(kcd, p, sp);
1243                                 ED_view3d_unproject(mats, view, sp[0], sp[1], 0.0f);
1244                                 mul_m4_v3(kcd->ob->imat, view);
1245
1246                                 if (kcd->cut_through) {
1247                                         f_hit = NULL;
1248                                 }
1249                                 else {
1250                                         /* check if this point is visible in the viewport */
1251                                         float p1[3], lambda1;
1252
1253                                         /* if face isn't planer, p may be behind the current tesselated tri,
1254                                          * so move it onto that and then a little towards eye */
1255                                         if (isect_line_tri_v3(p, view, ls[0]->v->co, ls[1]->v->co, ls[2]->v->co, &lambda1, NULL)) {
1256                                                 interp_v3_v3v3(p1, p, view, lambda1);
1257                                         }
1258                                         else {
1259                                                 copy_v3_v3(p1, p);
1260                                         }
1261                                         sub_v3_v3(view, p1);
1262                                         normalize_v3(view);
1263
1264                                         copy_v3_v3(no, view);
1265                                         mul_v3_fl(no, 0.003);
1266
1267                                         /* go towards view a bit */
1268                                         add_v3_v3(p1, no);
1269
1270                                         /* ray cast */
1271                                         f_hit = BKE_bmbvh_ray_cast(bmtree, p1, no, NULL, NULL, NULL);
1272                                 }
1273
1274                                 /* ok, if visible add the new point */
1275                                 if (!f_hit && !BLI_smallhash_haskey(ehash, (intptr_t)kfe)) {
1276                                         BMEdgeHit hit;
1277
1278                                         if (len_squared_v3v3(p, kcd->curr.co) < depsilon_sq ||
1279                                             len_squared_v3v3(p, kcd->prev.co) < depsilon_sq)
1280                                         {
1281                                                 continue;
1282                                         }
1283
1284                                         hit.kfe = kfe;
1285                                         hit.v = NULL;
1286
1287                                         knife_find_basef(kfe);
1288                                         hit.f = kfe->basef;
1289                                         hit.perc = len_v3v3(p, kfe->v1->cageco) / len_v3v3(kfe->v1->cageco, kfe->v2->cageco);
1290                                         copy_v3_v3(hit.cagehit, p);
1291
1292                                         interp_v3_v3v3(p, kfe->v1->co, kfe->v2->co, hit.perc);
1293                                         copy_v3_v3(hit.realhit, p);
1294
1295                                         /* BMESH_TODO: should also snap to vertices */
1296                                         if (kcd->snap_midpoints) {
1297                                                 float perc = hit.perc;
1298
1299                                                 /* select the closest from the edge endpoints or the midpoint */
1300                                                 if (perc < 0.25f) {
1301                                                         perc = 0.0f;
1302                                                 }
1303                                                 else if (perc < 0.75f) {
1304                                                         perc = 0.5f;
1305                                                 }
1306                                                 else {
1307                                                         perc = 1.0f;
1308                                                 }
1309
1310                                                 interp_v3_v3v3(hit.hit, kfe->v1->co, kfe->v2->co, perc);
1311                                                 interp_v3_v3v3(hit.cagehit, kfe->v1->cageco, kfe->v2->cageco, perc);
1312                                         }
1313                                         else {
1314                                                 copy_v3_v3(hit.hit, p);
1315                                         }
1316                                         knife_project_v3(kcd, hit.cagehit, hit.schit);
1317
1318                                         BLI_array_append(edges, hit);
1319                                         BLI_smallhash_insert(ehash, (intptr_t)kfe, NULL);
1320                                 }
1321                         }
1322                 }
1323         }
1324
1325         if (results)
1326                 MEM_freeN(results);
1327
1328         BLI_bvhtree_free(tree2);
1329         *count = BLI_array_count(edges);
1330
1331         return edges;
1332 }
1333
1334 static void knife_bgl_get_mats(KnifeTool_OpData *UNUSED(kcd), bglMats *mats)
1335 {
1336         bgl_get_mats(mats);
1337         //copy_m4_m4(mats->modelview, kcd->vc.rv3d->viewmat);
1338         //copy_m4_m4(mats->projection, kcd->vc.rv3d->winmat);
1339 }
1340
1341 /* Calculate maximum excursion from (0,0,0) of mesh */
1342 static void calc_ortho_extent(KnifeTool_OpData *kcd)
1343 {
1344         BMIter iter;
1345         BMVert *v;
1346         BMesh *bm = kcd->em->bm;
1347         float max_xyz = 0.0f;
1348         int i;
1349
1350         BM_ITER_MESH(v, &iter, bm, BM_VERTS_OF_MESH) {
1351                 for (i = 0; i < 3; i++)
1352                         max_xyz = max_ff(max_xyz, fabs(v->co[i]));
1353         }
1354         kcd->ortho_extent = max_xyz;
1355 }
1356
1357 /* Clip the line (v1, v2) to planes perpendicular to it and distances d from
1358  * the closest point on the line to the origin */
1359 static void clip_to_ortho_planes(float v1[3], float v2[3], float d)
1360 {
1361         float closest[3];
1362         const float origin[3] = {0.0f, 0.0f, 0.0f};
1363
1364         closest_to_line_v3(closest, origin, v1, v2);
1365         dist_ensure_v3_v3fl(v1, closest, d);
1366         dist_ensure_v3_v3fl(v2, closest, d);
1367 }
1368
1369 /* Finds visible (or all, if cutting through) edges that intersects the current screen drag line */
1370 static void knife_find_line_hits(KnifeTool_OpData *kcd)
1371 {
1372         bglMats mats;
1373         BMEdgeHit *e1, *e2;
1374         SmallHash hash, *ehash = &hash;
1375         float v1[3], v2[3], v3[3], v4[4], s1[3], s2[3];
1376         int i, c1, c2;
1377
1378         knife_bgl_get_mats(kcd, &mats);
1379
1380         if (kcd->linehits) {
1381                 MEM_freeN(kcd->linehits);
1382                 kcd->linehits = NULL;
1383                 kcd->totlinehit = 0;
1384         }
1385
1386         copy_v3_v3(v1, kcd->prev.cage);
1387         copy_v3_v3(v2, kcd->curr.cage);
1388
1389         /* project screen line's 3d coordinates back into 2d */
1390         knife_project_v3(kcd, v1, s1);
1391         knife_project_v3(kcd, v2, s2);
1392
1393         if (len_squared_v2v2(s1, s2) < 1)
1394                 return;
1395
1396         /* unproject screen line */
1397         ED_view3d_win_to_segment_clip(kcd->ar, kcd->vc.v3d, s1, v1, v3);
1398         ED_view3d_win_to_segment_clip(kcd->ar, kcd->vc.v3d, s2, v2, v4);
1399
1400         mul_m4_v3(kcd->ob->imat, v1);
1401         mul_m4_v3(kcd->ob->imat, v2);
1402         mul_m4_v3(kcd->ob->imat, v3);
1403         mul_m4_v3(kcd->ob->imat, v4);
1404
1405         /* numeric error, 'v1' -> 'v2', 'v2' -> 'v4' can end up being ~2000 units apart in otho mode
1406          * (from ED_view3d_win_to_segment_clip() above)
1407          * this gives precision error in 'knife_edge_tri_isect', rather then solving properly
1408          * (which may involve using doubles everywhere!),
1409          * limit the distance between these points */
1410         if (kcd->is_ortho) {
1411                 if (kcd->ortho_extent == 0.0f)
1412                         calc_ortho_extent(kcd);
1413                 clip_to_ortho_planes(v1, v3, kcd->ortho_extent + 10.0f);
1414                 clip_to_ortho_planes(v2, v4, kcd->ortho_extent + 10.0f);
1415         }
1416
1417         BLI_smallhash_init(ehash);
1418
1419         /* test two triangles of sceen line's plane */
1420         e1 = knife_edge_tri_isect(kcd, kcd->bmbvh, v1, v2, v3, ehash, &mats, &c1);
1421         e2 = knife_edge_tri_isect(kcd, kcd->bmbvh, v2, v3, v4, ehash, &mats, &c2);
1422         if (c1 && c2) {
1423                 e1 = MEM_reallocN(e1, sizeof(BMEdgeHit) * (c1 + c2));
1424                 memcpy(e1 + c1, e2, sizeof(BMEdgeHit) * c2);
1425                 MEM_freeN(e2);
1426         }
1427         else if (c2) {
1428                 e1 = e2;
1429         }
1430
1431         kcd->linehits = e1;
1432         kcd->totlinehit = c1 + c2;
1433
1434         /* find position along screen line, used for sorting */
1435         for (i = 0; i < kcd->totlinehit; i++) {
1436                 BMEdgeHit *lh = e1 + i;
1437
1438                 lh->l = len_v2v2(lh->schit, s1) / len_v2v2(s2, s1);
1439         }
1440
1441         BLI_smallhash_release(ehash);
1442 }
1443
1444 /* this works but gives numeric problems [#33400] */
1445 #if 0
1446 static void knife_input_ray_cast(KnifeTool_OpData *kcd, const float mval[2],
1447                                  float r_origin[3], float r_ray[3])
1448 {
1449         bglMats mats;
1450         float imat[3][3];
1451
1452         knife_bgl_get_mats(kcd, &mats);
1453
1454         /* unproject to find view ray */
1455         ED_view3d_unproject(&mats, r_origin, mval[0], mval[1], 0.0f);
1456
1457         if (kcd->is_ortho) {
1458                 negate_v3_v3(r_ray, kcd->vc.rv3d->viewinv[2]);
1459         }
1460         else {
1461                 sub_v3_v3v3(r_ray, r_origin, kcd->vc.rv3d->viewinv[3]);
1462         }
1463         normalize_v3(r_ray);
1464
1465         /* transform into object space */
1466         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
1467         copy_m3_m4(imat, kcd->ob->obmat);
1468         invert_m3(imat);
1469
1470         mul_m4_v3(kcd->ob->imat, r_origin);
1471         mul_m3_v3(imat, r_ray);
1472 }
1473 #endif
1474
1475 static void knife_input_ray_segment(KnifeTool_OpData *kcd, const float mval[2], const float ofs,
1476                                     float r_origin[3], float r_origin_ofs[3])
1477 {
1478         bglMats mats;
1479
1480         knife_bgl_get_mats(kcd, &mats);
1481
1482         /* unproject to find view ray */
1483         ED_view3d_unproject(&mats, r_origin,     mval[0], mval[1], 0.0f);
1484         ED_view3d_unproject(&mats, r_origin_ofs, mval[0], mval[1], ofs);
1485
1486         /* transform into object space */
1487         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
1488
1489         mul_m4_v3(kcd->ob->imat, r_origin);
1490         mul_m4_v3(kcd->ob->imat, r_origin_ofs);
1491 }
1492
1493 static BMFace *knife_find_closest_face(KnifeTool_OpData *kcd, float co[3], float cageco[3], bool *is_space)
1494 {
1495         BMFace *f;
1496         float dist = KMAXDIST;
1497         float origin[3];
1498         float origin_ofs[3];
1499         float ray[3];
1500
1501         /* unproject to find view ray */
1502         knife_input_ray_segment(kcd, kcd->curr.mval, 1.0f, origin, origin_ofs);
1503         sub_v3_v3v3(ray, origin_ofs, origin);
1504
1505         f = BKE_bmbvh_ray_cast(kcd->bmbvh, origin, ray, NULL, co, cageco);
1506
1507         if (is_space)
1508                 *is_space = !f;
1509
1510         if (!f) {
1511                 if (kcd->is_interactive) {
1512                         /* try to use backbuffer selection method if ray casting failed */
1513                         f = EDBM_face_find_nearest(&kcd->vc, &dist);
1514
1515                         /* cheat for now; just put in the origin instead
1516                          * of a true coordinate on the face.
1517                          * This just puts a point 1.0f infront of the view. */
1518                         add_v3_v3v3(co, origin, ray);
1519                 }
1520         }
1521
1522         return f;
1523 }
1524
1525 /* find the 2d screen space density of vertices within a radius.  used to scale snapping
1526  * distance for picking edges/verts.*/
1527 static int knife_sample_screen_density(KnifeTool_OpData *kcd, const float radius)
1528 {
1529         BMFace *f;
1530         bool is_space;
1531         float co[3], cageco[3], sco[3];
1532
1533         BLI_assert(kcd->is_interactive == true);
1534
1535         f = knife_find_closest_face(kcd, co, cageco, &is_space);
1536
1537         if (f && !is_space) {
1538                 const float radius_sq = radius * radius;
1539                 ListBase *lst;
1540                 Ref *ref;
1541                 float dis_sq;
1542                 int c = 0;
1543
1544                 knife_project_v3(kcd, cageco, sco);
1545
1546                 lst = knife_get_face_kedges(kcd, f);
1547                 for (ref = lst->first; ref; ref = ref->next) {
1548                         KnifeEdge *kfe = ref->ref;
1549                         int i;
1550
1551                         for (i = 0; i < 2; i++) {
1552                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1553
1554                                 knife_project_v3(kcd, kfv->cageco, kfv->sco);
1555
1556                                 dis_sq = len_squared_v2v2(kfv->sco, sco);
1557                                 if (dis_sq < radius_sq) {
1558                                         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1559                                                 if (ED_view3d_clipping_test(kcd->vc.rv3d, kfv->cageco, true) == 0) {
1560                                                         c++;
1561                                                 }
1562                                         }
1563                                         else {
1564                                                 c++;
1565                                         }
1566                                 }
1567                         }
1568                 }
1569
1570                 return c;
1571         }
1572
1573         return 0;
1574 }
1575
1576 /* returns snapping distance for edges/verts, scaled by the density of the
1577  * surrounding mesh (in screen space)*/
1578 static float knife_snap_size(KnifeTool_OpData *kcd, float maxsize)
1579 {
1580         float density;
1581
1582         if (kcd->is_interactive) {
1583                 density = (float)knife_sample_screen_density(kcd, maxsize * 2.0f);
1584         }
1585         else {
1586                 density = 1.0f;
1587         }
1588
1589         if (density < 1.0f)
1590                 density = 1.0f;
1591
1592         return min_ff(maxsize / (density * 0.5f), maxsize);
1593 }
1594
1595 /* p is closest point on edge to the mouse cursor */
1596 static KnifeEdge *knife_find_closest_edge(KnifeTool_OpData *kcd, float p[3], float cagep[3], BMFace **fptr, bool *is_space)
1597 {
1598         BMFace *f;
1599         float co[3], cageco[3], sco[3], maxdist = knife_snap_size(kcd, kcd->ethresh);
1600
1601         if (kcd->ignore_vert_snapping)
1602                 maxdist *= 0.5f;
1603
1604         f = knife_find_closest_face(kcd, co, cageco, NULL);
1605         *is_space = !f;
1606
1607         /* set p to co, in case we don't find anything, means a face cut */
1608         copy_v3_v3(p, co);
1609         copy_v3_v3(cagep, cageco);
1610
1611         kcd->curr.bmface = f;
1612
1613         if (f) {
1614                 KnifeEdge *cure = NULL;
1615                 ListBase *lst;
1616                 Ref *ref;
1617                 float dis, curdis = FLT_MAX;
1618
1619                 knife_project_v3(kcd, cageco, sco);
1620
1621                 /* look through all edges associated with this face */
1622                 lst = knife_get_face_kedges(kcd, f);
1623                 for (ref = lst->first; ref; ref = ref->next) {
1624                         KnifeEdge *kfe = ref->ref;
1625
1626                         /* project edge vertices into screen space */
1627                         knife_project_v3(kcd, kfe->v1->cageco, kfe->v1->sco);
1628                         knife_project_v3(kcd, kfe->v2->cageco, kfe->v2->sco);
1629
1630                         dis = dist_to_line_segment_v2(sco, kfe->v1->sco, kfe->v2->sco);
1631                         if (dis < curdis && dis < maxdist) {
1632                                 if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1633                                         float lambda = line_point_factor_v2(sco, kfe->v1->sco, kfe->v2->sco);
1634                                         float vec[3];
1635
1636                                         interp_v3_v3v3(vec, kfe->v1->cageco, kfe->v2->cageco, lambda);
1637
1638                                         if (ED_view3d_clipping_test(kcd->vc.rv3d, vec, true) == 0) {
1639                                                 cure = kfe;
1640                                                 curdis = dis;
1641                                         }
1642                                 }
1643                                 else {
1644                                         cure = kfe;
1645                                         curdis = dis;
1646                                 }
1647                         }
1648                 }
1649
1650                 if (fptr)
1651                         *fptr = f;
1652
1653                 if (cure && p) {
1654                         if (!kcd->ignore_edge_snapping || !(cure->e)) {
1655                                 KnifeVert *edgesnap = NULL;
1656
1657                                 if (kcd->snap_midpoints) {
1658                                         mid_v3_v3v3(p, cure->v1->co, cure->v2->co);
1659                                         mid_v3_v3v3(cagep, cure->v1->cageco, cure->v2->cageco);
1660                                 }
1661                                 else {
1662                                         float d;
1663
1664                                         closest_to_line_segment_v3(cagep, cageco, cure->v1->cageco, cure->v2->cageco);
1665                                         d = len_v3v3(cagep, cure->v1->cageco) / len_v3v3(cure->v1->cageco, cure->v2->cageco);
1666                                         interp_v3_v3v3(p, cure->v1->co, cure->v2->co, d);
1667                                 }
1668
1669                                 /* update mouse coordinates to the snapped-to edge's screen coordinates
1670                                  * this is important for angle snap, which uses the previous mouse position */
1671                                 edgesnap = new_knife_vert(kcd, p, cagep);
1672                                 kcd->curr.mval[0] = edgesnap->sco[0];
1673                                 kcd->curr.mval[1] = edgesnap->sco[1];
1674
1675                         }
1676                         else {
1677                                 return NULL;
1678                         }
1679                 }
1680
1681                 return cure;
1682         }
1683
1684         if (fptr)
1685                 *fptr = NULL;
1686
1687         return NULL;
1688 }
1689
1690 /* find a vertex near the mouse cursor, if it exists */
1691 static KnifeVert *knife_find_closest_vert(KnifeTool_OpData *kcd, float p[3], float cagep[3], BMFace **fptr,
1692                                           bool *is_space)
1693 {
1694         BMFace *f;
1695         float co[3], cageco[3], sco[3], maxdist = knife_snap_size(kcd, kcd->vthresh);
1696
1697         if (kcd->ignore_vert_snapping)
1698                 maxdist *= 0.5f;
1699
1700         f = knife_find_closest_face(kcd, co, cageco, is_space);
1701
1702         /* set p to co, in case we don't find anything, means a face cut */
1703         copy_v3_v3(p, co);
1704         copy_v3_v3(cagep, p);
1705         kcd->curr.bmface = f;
1706
1707         if (f) {
1708                 const float maxdist_sq = maxdist * maxdist;
1709                 ListBase *lst;
1710                 Ref *ref;
1711                 KnifeVert *curv = NULL;
1712                 float dis_sq, curdis_sq = FLT_MAX;
1713
1714                 knife_project_v3(kcd, cageco, sco);
1715
1716                 lst = knife_get_face_kedges(kcd, f);
1717                 for (ref = lst->first; ref; ref = ref->next) {
1718                         KnifeEdge *kfe = ref->ref;
1719                         int i;
1720
1721                         for (i = 0; i < 2; i++) {
1722                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1723
1724                                 knife_project_v3(kcd, kfv->cageco, kfv->sco);
1725
1726                                 dis_sq = len_squared_v2v2(kfv->sco, sco);
1727                                 if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
1728                                         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1729                                                 if (ED_view3d_clipping_test(kcd->vc.rv3d, kfv->cageco, true) == 0) {
1730                                                         curv = kfv;
1731                                                         curdis_sq = dis_sq;
1732                                                 }
1733                                         }
1734                                         else {
1735                                                 curv = kfv;
1736                                                 curdis_sq = dis_sq;
1737                                         }
1738                                 }
1739                         }
1740                 }
1741
1742                 if (!kcd->ignore_vert_snapping || !(curv && curv->v)) {
1743                         if (fptr)
1744                                 *fptr = f;
1745
1746                         if (curv && p) {
1747                                 copy_v3_v3(p, curv->co);
1748                                 copy_v3_v3(cagep, curv->cageco);
1749
1750                                 /* update mouse coordinates to the snapped-to vertex's screen coordinates
1751                                  * this is important for angle snap, which uses the previous mouse position */
1752                                 kcd->curr.mval[0] = curv->sco[0];
1753                                 kcd->curr.mval[1] = curv->sco[1];
1754                         }
1755
1756                         return curv;
1757                 }
1758                 else {
1759                         if (fptr)
1760                                 *fptr = f;
1761
1762                         return NULL;
1763                 }
1764         }
1765
1766         if (fptr)
1767                 *fptr = NULL;
1768
1769         return NULL;
1770 }
1771
1772 /* update both kcd->curr.mval and kcd->mval to snap to required angle */
1773 static void knife_snap_angle(KnifeTool_OpData *kcd)
1774 {
1775         float dx, dy;
1776         float w, abs_tan;
1777
1778         dx = kcd->curr.mval[0] - kcd->prev.mval[0];
1779         dy = kcd->curr.mval[1] - kcd->prev.mval[1];
1780         if (dx == 0.0f && dy == 0.0f)
1781                 return;
1782
1783         if (dx == 0.0f) {
1784                 kcd->angle_snapping = ANGLE_90;
1785                 kcd->curr.mval[0] = kcd->prev.mval[0];
1786         }
1787
1788         w = dy / dx;
1789         abs_tan = fabsf(w);
1790         if (abs_tan <= 0.4142f) { /* tan(22.5 degrees) = 0.4142 */
1791                 kcd->angle_snapping = ANGLE_0;
1792                 kcd->curr.mval[1] = kcd->prev.mval[1];
1793         }
1794         else if (abs_tan < 2.4142f) { /* tan(67.5 degrees) = 2.4142 */
1795                 if (w > 0) {
1796                         kcd->angle_snapping = ANGLE_45;
1797                         kcd->curr.mval[1] = kcd->prev.mval[1] + dx;
1798                 }
1799                 else {
1800                         kcd->angle_snapping = ANGLE_135;
1801                         kcd->curr.mval[1] = kcd->prev.mval[1] - dx;
1802                 }
1803         }
1804         else {
1805                 kcd->angle_snapping = ANGLE_90;
1806                 kcd->curr.mval[0] = kcd->prev.mval[0];
1807         }
1808
1809         copy_v2_v2(kcd->mval, kcd->curr.mval);
1810 }
1811
1812 /* update active knife edge/vert pointers */
1813 static int knife_update_active(KnifeTool_OpData *kcd)
1814 {
1815         knife_pos_data_clear(&kcd->curr);
1816         copy_v2_v2(kcd->curr.mval, kcd->mval);
1817         if (kcd->angle_snapping != ANGLE_FREE && kcd->mode == MODE_DRAGGING)
1818                 knife_snap_angle(kcd);
1819
1820         /* XXX knife_snap_angle updates the view coordinate mouse values to constrained angles,
1821          * which current mouse values are set to current mouse values are then used
1822          * for vertex and edge snap detection, without regard to the exact angle constraint */
1823         kcd->curr.vert = knife_find_closest_vert(kcd, kcd->curr.co, kcd->curr.cage, &kcd->curr.bmface, &kcd->curr.is_space);
1824
1825         if (!kcd->curr.vert) {
1826                 kcd->curr.edge = knife_find_closest_edge(kcd, kcd->curr.co, kcd->curr.cage, &kcd->curr.bmface, &kcd->curr.is_space);
1827         }
1828
1829         /* if no hits are found this would normally default to (0, 0, 0) so instead
1830          * get a point at the mouse ray closest to the previous point.
1831          * Note that drawing lines in `free-space` isn't properly supported
1832          * but theres no guarantee (0, 0, 0) has any geometry either - campbell */
1833         if (kcd->curr.vert == NULL && kcd->curr.edge == NULL) {
1834                 float origin[3];
1835                 float origin_ofs[3];
1836
1837                 knife_input_ray_segment(kcd, kcd->curr.mval, 1.0f, origin, origin_ofs);
1838
1839                 closest_to_line_v3(kcd->curr.cage, kcd->prev.cage, origin_ofs, origin);
1840         }
1841
1842         if (kcd->mode == MODE_DRAGGING) {
1843                 knife_find_line_hits(kcd);
1844         }
1845         return 1;
1846 }
1847
1848 #define SCANFILL_CUTS 0
1849 #if SCANFILL_CUTS
1850
1851 #define MARK            4
1852 #define DEL             8
1853 #define VERT_ON_EDGE    16
1854 #define VERT_ORIG       32
1855 #define FACE_FLIP       64
1856 #define BOUNDARY        128
1857 #define FACE_NEW        256
1858
1859 typedef struct facenet_entry {
1860         struct facenet_entry *next, *prev;
1861         KnifeEdge *kfe;
1862 } facenet_entry;
1863
1864 static void rnd_offset_co(RNG *rng, float co[3], float scale)
1865 {
1866         int i;
1867
1868         for (i = 0; i < 3; i++) {
1869                 co[i] += (BLI_rng_get_float(rng) - 0.5) * scale;
1870         }
1871 }
1872
1873 static void remerge_faces(KnifeTool_OpData *kcd)
1874 {
1875         BMesh *bm = kcd->em->bm;
1876         SmallHash svisit, *visit = &svisit;
1877         BMIter iter;
1878         BMFace *f;
1879         BMFace **stack = NULL;
1880         BLI_array_declare(stack);
1881         BMFace **faces = NULL;
1882         BLI_array_declare(faces);
1883         BMOperator bmop;
1884         int idx;
1885
1886         BMO_op_initf(bm, &bmop, "beautify_fill faces=%ff edges=%Fe", FACE_NEW, BOUNDARY);
1887
1888         BMO_op_exec(bm, &bmop);
1889         BMO_slot_buffer_flag_enable(bm, &bmop, "geom.out", BM_FACE, FACE_NEW);
1890
1891         BMO_op_finish(bm, &bmop);
1892
1893         BLI_smallhash_init(visit);
1894         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
1895                 BMIter eiter;
1896                 BMEdge *e;
1897                 BMFace *f2;
1898
1899                 if (!BMO_elem_flag_test(bm, f, FACE_NEW))
1900                         continue;
1901
1902                 if (BLI_smallhash_haskey(visit, (intptr_t)f))
1903                         continue;
1904
1905                 BLI_array_empty(stack);
1906                 BLI_array_empty(faces);
1907                 BLI_array_append(stack, f);
1908                 BLI_smallhash_insert(visit, (intptr_t)f, NULL);
1909
1910                 do {
1911                         f2 = BLI_array_pop(stack);
1912
1913                         BLI_array_append(faces, f2);
1914
1915                         BM_ITER_ELEM (e, &eiter, f2, BM_EDGES_OF_FACE) {
1916                                 BMIter fiter;
1917                                 BMFace *f3;
1918
1919                                 if (BMO_elem_flag_test(bm, e, BOUNDARY))
1920                                         continue;
1921
1922                                 BM_ITER_ELEM (f3, &fiter, e, BM_FACES_OF_EDGE) {
1923                                         if (!BMO_elem_flag_test(bm, f3, FACE_NEW))
1924                                                 continue;
1925                                         if (BLI_smallhash_haskey(visit, (intptr_t)f3))
1926                                                 continue;
1927
1928                                         BLI_smallhash_insert(visit, (intptr_t)f3, NULL);
1929                                         BLI_array_append(stack, f3);
1930                                 }
1931                         }
1932                 } while (BLI_array_count(stack) > 0);
1933
1934                 if (BLI_array_count(faces) > 0) {
1935                         idx = BM_elem_index_get(faces[0]);
1936
1937                         f2 = BM_faces_join(bm, faces, BLI_array_count(faces), true);
1938                         if (f2) {
1939                                 BMO_elem_flag_enable(bm, f2, FACE_NEW);
1940                                 BM_elem_index_set(f2, idx); /* set_dirty! *//* BMESH_TODO, check if this is valid or not */
1941                         }
1942                 }
1943         }
1944         /* BMESH_TODO, check if the code above validates the indices */
1945         /* bm->elem_index_dirty &= ~BM_FACE; */
1946         bm->elem_index_dirty |= BM_FACE;
1947
1948         BLI_smallhash_release(visit);
1949
1950         BLI_array_free(stack);
1951         BLI_array_free(faces);
1952 }
1953
1954 /* use edgenet to fill faces.  this is a bit annoying and convoluted.*/
1955 static void knifenet_fill_faces(KnifeTool_OpData *kcd)
1956 {
1957         ScanFillContext sf_ctx;
1958         BMesh *bm = kcd->em->bm;
1959         BMIter bmiter;
1960         BLI_mempool_iter iter;
1961         BMFace *f;
1962         BMEdge *e;
1963         KnifeVert *kfv;
1964         KnifeEdge *kfe;
1965         facenet_entry *entry;
1966         ListBase *face_nets = MEM_callocN(sizeof(ListBase) * bm->totface, "face_nets");
1967         BMFace **faces = MEM_callocN(sizeof(BMFace *) * bm->totface, "faces knife");
1968         MemArena *arena = BLI_memarena_new(1 << 16, "knifenet_fill_faces");
1969         SmallHash shash;
1970         RNG *rng;
1971         int i, j, k = 0, totface = bm->totface;
1972
1973         BMO_push(bm, NULL);
1974         bmesh_edit_begin(bm, BMO_OPTYPE_FLAG_UNTAN_MULTIRES | BMO_OPTYPE_FLAG_NORMALS_CALC | BMO_OPTYPE_FLAG_SELECT_FLUSH);
1975
1976         /* BMESH_TODO this should be valid now, leaving here until we can ensure this - campbell */
1977         i = 0;
1978         BM_ITER_MESH (f, &bmiter, bm, BM_FACES_OF_MESH) {
1979                 BM_elem_index_set(f, i); /* set_inline */
1980                 faces[i] = f;
1981                 i++;
1982         }
1983         bm->elem_index_dirty &= ~BM_FACE;
1984
1985         BM_ITER_MESH (e, &bmiter, bm, BM_EDGES_OF_MESH) {
1986                 BMO_elem_flag_enable(bm, e, BOUNDARY);
1987         }
1988
1989         /* turn knife verts into real verts, as necessary */
1990         BLI_mempool_iternew(kcd->kverts, &iter);
1991         for (kfv = BLI_mempool_iterstep(&iter); kfv; kfv = BLI_mempool_iterstep(&iter)) {
1992                 if (!kfv->v) {
1993                         /* shouldn't we be at least copying the normal? - if not some comment here should explain why - campbell */
1994                         kfv->v = BM_vert_create(bm, kfv->co, NULL);
1995                         kfv->flag = 1;
1996                         BMO_elem_flag_enable(bm, kfv->v, DEL);
1997                 }
1998                 else {
1999                         kfv->flag = 0;
2000                         BMO_elem_flag_enable(bm, kfv->v, VERT_ORIG);
2001                 }
2002
2003                 BMO_elem_flag_enable(bm, kfv->v, MARK);
2004         }
2005
2006         /* we want to only do changed faces.  first, go over new edges and add to
2007          * face net lists.*/
2008         i = j = k = 0;
2009         BLI_mempool_iternew(kcd->kedges, &iter);
2010         for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
2011                 Ref *ref;
2012                 if (!kfe->v1 || !kfe->v2 || kfe->v1->inspace || kfe->v2->inspace)
2013                         continue;
2014
2015                 i++;
2016
2017                 if (kfe->e && kfe->v1->v == kfe->e->v1 && kfe->v2->v == kfe->e->v2) {
2018                         kfe->e_old = kfe->e;
2019                         continue;
2020                 }
2021
2022                 j++;
2023
2024                 if (kfe->e) {
2025                         kfe->e_old = kfe->e;
2026
2027                         BMO_elem_flag_enable(bm, kfe->e, DEL);
2028                         BMO_elem_flag_disable(bm, kfe->e, BOUNDARY);
2029                         kfe->e = NULL;
2030                 }
2031
2032                 kfe->e = BM_edge_create(bm, kfe->v1->v, kfe->v2->v, NULL, BM_CREATE_NO_DOUBLE);
2033                 BMO_elem_flag_enable(bm, kfe->e, BOUNDARY);
2034
2035                 for (ref = kfe->faces.first; ref; ref = ref->next) {
2036                         f = ref->ref;
2037
2038                         entry = BLI_memarena_alloc(arena, sizeof(*entry));
2039                         entry->kfe = kfe;
2040                         BLI_addtail(face_nets + BM_elem_index_get(f), entry);
2041                 }
2042         }
2043
2044         /* go over original edges, and add to faces with new geometry */
2045         BLI_mempool_iternew(kcd->kedges, &iter);
2046         for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
2047                 Ref *ref;
2048
2049                 if (!kfe->v1 || !kfe->v2 || kfe->v1->inspace || kfe->v2->inspace)
2050                         continue;
2051                 if (!(kfe->e_old && kfe->v1->v == kfe->e_old->v1 && kfe->v2->v == kfe->e_old->v2))
2052                         continue;
2053
2054                 k++;
2055
2056                 BMO_elem_flag_enable(bm, kfe->e, BOUNDARY);
2057                 kfe->e_old = kfe->e;
2058
2059                 for (ref = kfe->faces.first; ref; ref = ref->next) {
2060                         f = ref->ref;
2061
2062                         if (face_nets[BM_elem_index_get(f)].first) {
2063                                 entry = BLI_memarena_alloc(arena, sizeof(*entry));
2064                                 entry->kfe = kfe;
2065                                 BLI_addtail(face_nets + BM_elem_index_get(f), entry);
2066                         }
2067                 }
2068         }
2069
2070         rng = BLI_rng_new(0);
2071
2072         for (i = 0; i < totface; i++) {
2073                 SmallHash *hash = &shash;
2074                 ScanFillFace *sf_tri;
2075                 ScanFillVert *sf_vert, *sf_vert_last;
2076                 int j;
2077                 float rndscale = (KNIFE_FLT_EPS / 4.0f);
2078
2079                 f = faces[i];
2080                 BLI_smallhash_init(hash);
2081
2082                 if (face_nets[i].first)
2083                         BMO_elem_flag_enable(bm, f, DEL);
2084
2085                 BLI_scanfill_begin(&sf_ctx);
2086
2087                 for (entry = face_nets[i].first; entry; entry = entry->next) {
2088                         if (!BLI_smallhash_haskey(hash, (intptr_t)entry->kfe->v1)) {
2089                                 sf_vert = BLI_scanfill_vert_add(&sf_ctx, entry->kfe->v1->v->co);
2090                                 sf_vert->poly_nr = 0;
2091                                 rnd_offset_co(rng, sf_vert->co, rndscale);
2092                                 sf_vert->tmp.p = entry->kfe->v1->v;
2093                                 BLI_smallhash_insert(hash, (intptr_t)entry->kfe->v1, sf_vert);
2094                         }
2095
2096                         if (!BLI_smallhash_haskey(hash, (intptr_t)entry->kfe->v2)) {
2097                                 sf_vert = BLI_scanfill_vert_add(&sf_ctx, entry->kfe->v2->v->co);
2098                                 sf_vert->poly_nr = 0;
2099                                 rnd_offset_co(rng, sf_vert->co, rndscale);
2100                                 sf_vert->tmp.p = entry->kfe->v2->v;
2101                                 BLI_smallhash_insert(hash, (intptr_t)entry->kfe->v2, sf_vert);
2102                         }
2103                 }
2104
2105                 for (j = 0, entry = face_nets[i].first; entry; entry = entry->next, j++) {
2106                         sf_vert_last = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v1);
2107                         sf_vert = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v2);
2108
2109                         sf_vert->poly_nr++;
2110                         sf_vert_last->poly_nr++;
2111                 }
2112
2113                 for (j = 0, entry = face_nets[i].first; entry; entry = entry->next, j++) {
2114                         sf_vert_last = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v1);
2115                         sf_vert = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v2);
2116
2117                         if (sf_vert->poly_nr > 1 && sf_vert_last->poly_nr > 1) {
2118                                 ScanFillEdge *sf_edge;
2119                                 sf_edge = BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert);
2120                                 if (entry->kfe->e_old)
2121                                         sf_edge->f = SF_EDGE_BOUNDARY;  /* mark as original boundary edge */
2122
2123                                 BMO_elem_flag_disable(bm, entry->kfe->e->v1, DEL);
2124                                 BMO_elem_flag_disable(bm, entry->kfe->e->v2, DEL);
2125                         }
2126                         else {
2127                                 if (sf_vert_last->poly_nr < 2)
2128                                         BLI_remlink(&sf_ctx.fillvertbase, sf_vert_last);
2129                                 if (sf_vert->poly_nr < 2)
2130                                         BLI_remlink(&sf_ctx.fillvertbase, sf_vert);
2131                         }
2132                 }
2133
2134                 BLI_scanfill_calc(&sf_ctx, 0);
2135
2136                 for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
2137                         BMVert *v1 = sf_tri->v3->tmp.p, *v2 = sf_tri->v2->tmp.p, *v3 = sf_tri->v1->tmp.p;
2138                         BMFace *f2;
2139                         BMLoop *l_iter;
2140                         BMVert *verts[3] = {v1, v2, v3};
2141
2142                         if (v1 == v2 || v2 == v3 || v1 == v3)
2143                                 continue;
2144                         if (BM_face_exists(bm, verts, 3, &f2))
2145                                 continue;
2146
2147                         f2 = BM_face_create_quad_tri(bm,
2148                                                      v1, v2, v3, NULL,
2149                                                      NULL, false);
2150
2151                         BMO_elem_flag_enable(bm, f2, FACE_NEW);
2152
2153                         l_iter = BM_FACE_FIRST_LOOP(f2);
2154                         do {
2155                                 BMO_elem_flag_disable(bm, l_iter->e, DEL);
2156                         } while ((l_iter = l_iter->next) != BM_FACE_FIRST_LOOP(f2));
2157
2158                         BMO_elem_flag_disable(bm, f2, DEL);
2159                         BM_elem_index_set(f2, i); /* set_dirty! *//* note, not 100% sure this is dirty? need to check */
2160
2161                         BM_face_normal_update(f2);
2162                         if (dot_v3v3(f->no, f2->no) < 0.0f) {
2163                                 BM_face_normal_flip(bm, f2);
2164                         }
2165                 }
2166
2167                 BLI_scanfill_end(&sf_ctx);
2168                 BLI_smallhash_release(hash);
2169         }
2170         bm->elem_index_dirty |= BM_FACE;
2171
2172         /* interpolate customdata */
2173         BM_ITER_MESH (f, &bmiter, bm, BM_FACES_OF_MESH) {
2174                 BMLoop *l1;
2175                 BMFace *f2;
2176                 BMIter liter1;
2177
2178                 if (!BMO_elem_flag_test(bm, f, FACE_NEW))
2179                         continue;
2180
2181                 f2 = faces[BM_elem_index_get(f)];
2182                 if (BM_elem_index_get(f) < 0 || BM_elem_index_get(f) >= totface) {
2183                         fprintf(stderr, "%s: face index out of range! (bmesh internal error)\n", __func__);
2184                 }
2185
2186                 BM_elem_attrs_copy(bm, bm, f2, f);
2187
2188                 BM_ITER_ELEM (l1, &liter1, f, BM_LOOPS_OF_FACE) {
2189                         BM_loop_interp_from_face(bm, l1, f2, true, true);
2190                 }
2191         }
2192
2193         /* merge triangles back into faces */
2194         remerge_faces(kcd);
2195
2196         /* delete left over faces */
2197         BMO_op_callf(bm, BMO_FLAG_DEFAULTS, "delete geom=%ff context=%i", DEL, DEL_ONLYFACES);
2198         BMO_op_callf(bm, BMO_FLAG_DEFAULTS, "delete geom=%fe context=%i", DEL, DEL_EDGES);
2199         BMO_op_callf(bm, BMO_FLAG_DEFAULTS, "delete geom=%fv context=%i", DEL, DEL_VERTS);
2200
2201         if (face_nets)
2202                 MEM_freeN(face_nets);
2203         if (faces)
2204                 MEM_freeN(faces);
2205         BLI_memarena_free(arena);
2206         BLI_rng_free(rng);
2207
2208         BMO_error_clear(bm); /* remerge_faces sometimes raises errors, so make sure to clear them */
2209
2210         bmesh_edit_end(bm, BMO_OPTYPE_FLAG_UNTAN_MULTIRES | BMO_OPTYPE_FLAG_NORMALS_CALC | BMO_OPTYPE_FLAG_SELECT_FLUSH);
2211         BMO_pop(bm);
2212 }
2213
2214 #else  /* use direct (non-scanfill) method for cuts */
2215
2216 /* assuming v is on line ab, what fraction of the way is v from a to b? */
2217 static float frac_along(const float a[3], const float b[3], const float v[3])
2218 {
2219         float lab;
2220
2221         lab = len_v3v3(a, b);
2222         if (lab == 0.0f) {
2223                 return 0.0f;
2224         }
2225         else {
2226                 return len_v3v3(a, v) / lab;
2227         }
2228 }
2229
2230 /* sort list of kverts by fraction along edge e */
2231 static void sort_by_frac_along(ListBase *lst, BMEdge *e)
2232 {
2233         KnifeVert *vcur, *vprev;
2234         float *v1co, *v2co;
2235         Ref *cur = NULL, *prev = NULL, *next = NULL;
2236
2237         if (lst->first == lst->last)
2238                 return;
2239
2240         v1co = e->v1->co;
2241         v2co = e->v2->co;
2242
2243         for (cur = ((Ref *)lst->first)->next; cur; cur = next) {
2244                 next = cur->next;
2245                 prev = cur->prev;
2246
2247                 BLI_remlink(lst, cur);
2248
2249                 vcur = cur->ref;
2250                 while (prev) {
2251                         vprev = prev->ref;
2252                         if (frac_along(v1co, v2co, vprev->co) <= frac_along(v1co, v2co, vcur->co))
2253                                 break;
2254                         prev = prev->prev;
2255                 }
2256
2257                 BLI_insertlinkafter(lst, prev, cur);
2258         }
2259 }
2260
2261 /* The chain so far goes from an instantiated vertex to kfv (some may be reversed).
2262  * If possible, complete the chain to another instantiated vertex and return 1, else return 0.
2263  * The visited hash says which KnifeVert's have already been tried, not including kfv. */
2264 static bool find_chain_search(KnifeTool_OpData *kcd, KnifeVert *kfv, ListBase *fedges, SmallHash *visited,
2265                               ListBase *chain)
2266 {
2267         Ref *r;
2268         KnifeEdge *kfe;
2269         KnifeVert *kfv_other;
2270
2271         if (kfv->v)
2272                 return true;
2273
2274         BLI_smallhash_insert(visited, (uintptr_t)kfv, NULL);
2275         /* Try all possible next edges. Could either go through fedges
2276          * (all the KnifeEdges for the face being cut) or could go through
2277          * kve->edges and restrict to cutting face and uninstantiated edges.
2278          * Not clear which is better. Let's do the first. */
2279         for (r = fedges->first; r; r = r->next) {
2280                 kfe = r->ref;
2281                 kfv_other = NULL;
2282                 if (kfe->v1 == kfv)
2283                         kfv_other = kfe->v2;
2284                 else if (kfe->v2 == kfv)
2285                         kfv_other = kfe->v1;
2286                 if (kfv_other && !BLI_smallhash_haskey(visited, (uintptr_t)kfv_other)) {
2287                         knife_append_list(kcd, chain, kfe);
2288                         if (find_chain_search(kcd, kfv_other, fedges, visited, chain))
2289                                 return true;
2290                         BLI_remlink(chain, chain->last);
2291                 }
2292         }
2293         return false;
2294 }
2295
2296 static ListBase *find_chain_from_vertex(KnifeTool_OpData *kcd, KnifeEdge *kfe, BMVert *v, ListBase *fedges)
2297 {
2298         SmallHash visited_, *visited = &visited_;
2299         ListBase *ans;
2300         bool found;
2301
2302         ans = knife_empty_list(kcd);
2303         knife_append_list(kcd, ans, kfe);
2304         found = false;
2305         BLI_smallhash_init(visited);
2306         if (kfe->v1->v == v) {
2307                 BLI_smallhash_insert(visited, (uintptr_t)(kfe->v1), NULL);
2308                 found = find_chain_search(kcd, kfe->v2, fedges, visited, ans);
2309         }
2310         else {
2311                 BLI_assert(kfe->v2->v == v);
2312                 BLI_smallhash_insert(visited, (uintptr_t)(kfe->v2), NULL);
2313                 found = find_chain_search(kcd, kfe->v1, fedges, visited, ans);
2314         }
2315
2316         BLI_smallhash_release(visited);
2317
2318         if (found)
2319                 return ans;
2320         else
2321                 return NULL;
2322 }
2323
2324 /* Find a chain in fedges from one instantiated vertex to another.
2325  * Remove the edges in the chain from fedges and return a separate list of the chain. */
2326 static ListBase *find_chain(KnifeTool_OpData *kcd, ListBase *fedges)
2327 {
2328         Ref *r, *ref;
2329         KnifeEdge *kfe;
2330         BMVert *v1, *v2;
2331         ListBase *ans;
2332
2333         ans = NULL;
2334
2335         for (r = fedges->first; r; r = r->next) {
2336                 kfe = r->ref;
2337                 v1 = kfe->v1->v;
2338                 v2 = kfe->v2->v;
2339                 if (v1 && v2) {
2340                         ans = knife_empty_list(kcd);
2341                         knife_append_list(kcd, ans, kfe);
2342                         break;
2343                 }
2344                 if (v1)
2345                         ans = find_chain_from_vertex(kcd, kfe, v1, fedges);
2346                 else if (v2)
2347                         ans = find_chain_from_vertex(kcd, kfe, v2, fedges);
2348                 if (ans)
2349                         break;
2350         }
2351         if (ans) {
2352                 BLI_assert(BLI_countlist(ans) > 0);
2353                 for (r = ans->first; r; r = r->next) {
2354                         ref = find_ref(fedges, r->ref);
2355                         BLI_assert(ref != NULL);
2356                         BLI_remlink(fedges, ref);
2357                 }
2358         }
2359         return ans;
2360 }
2361
2362 /* The hole so far goes from kfvfirst to kfv (some may be reversed).
2363  * If possible, complete the hole back to kfvfirst and return 1, else return 0.
2364  * The visited hash says which KnifeVert's have already been tried, not including kfv or kfvfirst. */
2365 static bool find_hole_search(KnifeTool_OpData *kcd, KnifeVert *kfvfirst, KnifeVert *kfv, ListBase *fedges,
2366                              SmallHash *visited, ListBase *hole)
2367 {
2368         Ref *r;
2369         KnifeEdge *kfe, *kfelast;
2370         KnifeVert *kfv_other;
2371
2372         if (kfv == kfvfirst)
2373                 return true;
2374
2375         BLI_smallhash_insert(visited, (uintptr_t)kfv, NULL);
2376         kfelast = ((Ref *)hole->last)->ref;
2377         for (r = fedges->first; r; r = r->next) {
2378                 kfe = r->ref;
2379                 if (kfe == kfelast)
2380                         continue;
2381                 if (kfe->v1->v || kfe->v2->v)
2382                         continue;
2383                 kfv_other = NULL;
2384                 if (kfe->v1 == kfv)
2385                         kfv_other = kfe->v2;
2386                 else if (kfe->v2 == kfv)
2387                         kfv_other = kfe->v1;
2388                 if (kfv_other && !BLI_smallhash_haskey(visited, (uintptr_t)kfv_other)) {
2389                         knife_append_list(kcd, hole, kfe);
2390                         if (find_hole_search(kcd, kfvfirst, kfv_other, fedges, visited, hole))
2391                                 return true;
2392                         BLI_remlink(hole, hole->last);
2393                 }
2394         }
2395         return false;
2396 }
2397
2398 /* Find a hole (simple cycle with no instantiated vertices).
2399  * Remove the edges in the cycle from fedges and return a separate list of the cycle */
2400 static ListBase *find_hole(KnifeTool_OpData *kcd, ListBase *fedges)
2401 {
2402         ListBase *ans;
2403         Ref *r, *ref;
2404         KnifeEdge *kfe;
2405         SmallHash visited_, *visited = &visited_;
2406         bool found;
2407
2408         ans = NULL;
2409         found = false;
2410
2411         for (r = fedges->first; r && !found; r = r->next) {
2412                 kfe = r->ref;
2413                 if (kfe->v1->v || kfe->v2->v || kfe->v1 == kfe->v2)
2414                         continue;
2415
2416                 BLI_smallhash_init(visited);
2417                 ans = knife_empty_list(kcd);
2418                 knife_append_list(kcd, ans, kfe);
2419
2420                 found = find_hole_search(kcd, kfe->v1, kfe->v2, fedges, visited, ans);
2421
2422                 BLI_smallhash_release(visited);
2423         }
2424
2425         if (found) {
2426                 for (r = ans->first; r; r = r->next) {
2427                         kfe = r->ref;
2428                         ref = find_ref(fedges, r->ref);
2429                         if (ref)
2430                                 BLI_remlink(fedges, ref);
2431                 }
2432                 return ans;
2433         }
2434         else {
2435                 return NULL;
2436         }
2437 }
2438
2439 /* Try to find "nice" diagonals - short, and far apart from each other.
2440  * If found, return true and make a 'main chain' going across f which uses
2441  * the two diagonals and one part of the hole, and a 'side chain' that
2442  * completes the hole. */
2443 static bool find_hole_chains(KnifeTool_OpData *kcd, ListBase *hole, BMFace *f, ListBase **mainchain,
2444                              ListBase **sidechain)
2445 {
2446         float **fco, **hco;
2447         BMVert **fv;
2448         KnifeVert **hv;
2449         KnifeEdge **he;
2450         Ref *r;
2451         KnifeVert *kfv, *kfvother;
2452         KnifeEdge *kfe;
2453         ListBase *chain;
2454         BMVert *v;
2455         BMIter iter;
2456         int nh, nf, i, j, k, m, ax, ay, sep = 0 /* Quite warnings */, bestsep;
2457         int besti[2], bestj[2];
2458         float d, bestd;
2459
2460         nh = BLI_countlist(hole);
2461         nf = f->len;
2462         if (nh < 2 || nf < 3)
2463                 return false;
2464
2465         /* Gather 2d projections of hole and face vertex coordinates.
2466          * Use best-axis projection - not completely accurate, maybe revisit */
2467         axis_dominant_v3(&ax, &ay, f->no);
2468         hco = BLI_memarena_alloc(kcd->arena, nh * sizeof(float *));
2469         fco = BLI_memarena_alloc(kcd->arena, nf * sizeof(float *));
2470         hv = BLI_memarena_alloc(kcd->arena, nh * sizeof(KnifeVert *));
2471         fv = BLI_memarena_alloc(kcd->arena, nf * sizeof(BMVert *));
2472         he = BLI_memarena_alloc(kcd->arena, nh * sizeof(KnifeEdge *));
2473
2474         i = 0;
2475         kfv = NULL;
2476         kfvother = NULL;
2477         for (r = hole->first; r; r = r->next) {
2478                 kfe = r->ref;
2479                 he[i] = kfe;
2480                 if (kfvother == NULL) {
2481                         kfv = kfe->v1;
2482                 }
2483                 else {
2484                         kfv = kfvother;
2485                         BLI_assert(kfv == kfe->v1 || kfv == kfe->v2);
2486                 }
2487                 hco[i] = BLI_memarena_alloc(kcd->arena, 2 * sizeof(float));
2488                 hco[i][0] = kfv->co[ax];
2489                 hco[i][1] = kfv->co[ay];
2490                 hv[i] = kfv;
2491                 kfvother = (kfe->v1 == kfv) ? kfe->v2 : kfe->v1;
2492                 i++;
2493         }
2494
2495         j = 0;
2496         BM_ITER_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
2497                 fco[j] = BLI_memarena_alloc(kcd->arena, 2 * sizeof(float));
2498                 fco[j][0] = v->co[ax];
2499                 fco[j][1] = v->co[ay];
2500                 fv[j] = v;
2501                 j++;
2502         }
2503
2504         /* For first diagonal  (m == 0), want shortest length.
2505          * For second diagonal (m == 1), want max separation of index of hole
2506          * vertex from the hole vertex used in the first diagonal, and from there
2507          * want the one with shortest length not to the same vertex as the first diagonal. */
2508         for (m = 0; m < 2; m++) {
2509                 besti[m] = -1;
2510                 bestj[m] = -1;
2511                 bestd = FLT_MAX;
2512                 bestsep = 0;
2513                 for (i = 0; i < nh; i++) {
2514                         if (m == 1) {
2515                                 if (i == besti[0])
2516                                         continue;
2517                                 sep = (i + nh - besti[0]) % nh;
2518                                 sep = MIN2(sep, nh - sep);
2519                                 if (sep < bestsep)
2520                                         continue;
2521                                 bestd = FLT_MAX;
2522                         }
2523                         for (j = 0; j < nf; j++) {
2524                                 bool ok;
2525
2526                                 if (m == 1 && j == bestj[0])
2527                                         continue;
2528                                 d = len_squared_v2v2(hco[i], fco[j]);
2529                                 if (d > bestd)
2530                                         continue;
2531
2532                                 ok = true;
2533                                 for (k = 0; k < nh && ok; k++) {
2534                                         if (k == i || (k + 1) % nh == i)
2535                                                 continue;
2536                                         if (isect_line_line_v2(hco[i], fco[j], hco[k], hco[(k + 1) % nh]))
2537                                                 ok = false;
2538                                 }
2539                                 if (!ok)
2540                                         continue;
2541                                 for (k = 0; k < nf && ok; k++) {
2542                                         if (k == j || (k + 1) % nf == j)
2543                                                 continue;
2544                                         if (isect_line_line_v2(hco[i], fco[j], fco[k], fco[(k + 1) % nf]))
2545                                                 ok = false;
2546                                 }
2547                                 if (ok) {
2548                                         besti[m] = i;
2549                                         bestj[m] = j;
2550                                         if (m == 1)
2551                                                 bestsep = sep;
2552                                         bestd = d;
2553                                 }
2554                         }
2555                 }
2556         }
2557
2558         if (besti[0] != -1 && besti[1] != -1) {
2559                 BLI_assert(besti[0] != besti[1] && bestj[0] != bestj[1]);
2560                 kfe = new_knife_edge(kcd);
2561                 kfe->v1 = get_bm_knife_vert(kcd, fv[bestj[0]]);
2562                 kfe->v2 = hv[besti[0]];
2563                 chain = knife_empty_list(kcd);
2564                 knife_append_list(kcd, chain, kfe);
2565                 for (i = besti[0]; i != besti[1]; i = (i + 1) % nh) {
2566                         knife_append_list(kcd, chain, he[i]);
2567                 }
2568                 kfe = new_knife_edge(kcd);
2569                 kfe->v1 = hv[besti[1]];
2570                 kfe->v2 = get_bm_knife_vert(kcd, fv[bestj[1]]);
2571                 knife_append_list(kcd, chain, kfe);
2572                 *mainchain = chain;
2573
2574                 chain = knife_empty_list(kcd);
2575                 for (i = besti[1]; i != besti[0]; i = (i + 1) % nh) {
2576                         knife_append_list(kcd, chain, he[i]);
2577                 }
2578                 *sidechain = chain;
2579
2580                 return true;
2581         }
2582         else {
2583                 return false;
2584         }
2585 }
2586
2587 static bool knife_edge_in_face(KnifeTool_OpData *UNUSED(kcd), KnifeEdge *kfe, BMFace *f)
2588 {
2589         /* BMesh *bm = kcd->em->bm; */ /* UNUSED */
2590         BMVert *v1, *v2;
2591         BMLoop *l1, *l2, *l;
2592         float mid[3];
2593         BMIter iter;
2594         int v1inside, v2inside;
2595
2596         if (!f)
2597                 return false;
2598
2599         v1 = kfe->v1->v;
2600         v2 = kfe->v2->v;
2601         l1 = NULL;
2602         l2 = NULL;
2603
2604         /* find out if v1 and v2, if set, are part of the face */
2605         BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) {
2606                 if (v1 && l->v == v1)
2607                         l1 = l;
2608                 if (v2 && l->v == v2)
2609                         l2 = l;
2610         }
2611
2612         /* BM_face_point_inside_test uses best-axis projection so this isn't most accurate test... */
2613         v1inside = l1 ? 0 : BM_face_point_inside_test(f, kfe->v1->co);
2614         v2inside = l2 ? 0 : BM_face_point_inside_test(f, kfe->v2->co);
2615         if ((l1 && v2inside) || (l2 && v1inside) || (v1inside && v2inside))
2616                 return true;
2617         if (l1 && l2) {
2618                 /* Can have case where v1 and v2 are on shared chain between two faces.
2619                  * BM_face_legal_splits does visibility and self-intersection tests,
2620                  * but it is expensive and maybe a bit buggy, so use a simple
2621                  * "is the midpoint in the face" test */
2622                 mid_v3_v3v3(mid, kfe->v1->co, kfe->v2->co);
2623                 return BM_face_point_inside_test(f, mid);
2624         }
2625         return false;
2626 }
2627
2628 /* Split face f with KnifeEdges on chain.  f remains as one side, the face formed is put in *newface.
2629  * The new face will be on the left side of the chain as viewed from the normal-out side of f. */
2630 static void knife_make_chain_cut(KnifeTool_OpData *kcd, BMFace *f, ListBase *chain, BMFace **newface)
2631 {
2632         BMesh *bm = kcd->em->bm;
2633         KnifeEdge *kfe, *kfelast;
2634         BMVert *v1, *v2;
2635         BMFace *fnew;
2636         Ref *ref;
2637         KnifeVert *kfv, *kfvprev;
2638         BMLoop *lnew, *l_iter;
2639         int i;
2640         int nco = BLI_countlist(chain) - 1;
2641         float (*cos)[3] = BLI_array_alloca(cos, nco);
2642         KnifeVert **kverts = BLI_array_alloca(kverts, nco);
2643
2644         kfe = ((Ref *)chain->first)->ref;
2645         v1 = kfe->v1->v ? kfe->v1->v : kfe->v2->v;
2646         kfelast = ((Ref *)chain->last)->ref;
2647         v2 = kfelast->v2->v ? kfelast->v2->v : kfelast->v1->v;
2648         BLI_assert(v1 != NULL && v2 != NULL);
2649         kfvprev = kfe->v1->v == v1 ? kfe->v1 : kfe->v2;
2650         for (ref = chain->first, i = 0; i < nco && ref != chain->last; ref = ref->next, i++) {
2651                 kfe = ref->ref;
2652                 BLI_assert(kfvprev == kfe->v1 || kfvprev == kfe->v2);
2653                 kfv = kfe->v1 == kfvprev ? kfe->v2 : kfe->v1;
2654                 copy_v3_v3(cos[i], kfv->co);
2655                 kverts[i] = kfv;
2656                 kfvprev = kfv;
2657         }
2658         BLI_assert(i == nco);
2659         lnew = NULL;
2660         if (nco == 0) {
2661                 /* Want to prevent creating two-sided polygons */
2662                 if (BM_edge_exists(v1, v2)) {
2663                         *newface = NULL;
2664                 }
2665                 else {
2666                         *newface = BM_face_split(bm, f, v1, v2, &lnew, NULL, true);
2667                 }
2668         }
2669         else {
2670                 fnew = BM_face_split_n(bm, f, v1, v2, cos, nco, &lnew, NULL);
2671                 *newface = fnew;
2672
2673                 if (fnew) {
2674                         /* Now go through lnew chain matching up chain kv's and assign real v's to them */
2675                         for (l_iter = lnew->next, i = 0; i < nco; l_iter = l_iter->next, i++) {
2676                                 BLI_assert(equals_v3v3(cos[i], l_iter->v->co));
2677                                 if (kcd->select_result) {
2678                                         BM_edge_select_set(bm, l_iter->e, true);
2679                                 }
2680                                 kverts[i]->v = l_iter->v;
2681                         }
2682                 }
2683         }
2684
2685         /* the select chain above doesnt account for the first loop */
2686         if (kcd->select_result) {
2687                 if (lnew) {
2688                         BM_edge_select_set(bm, lnew->e, true);
2689                 }
2690         }
2691 }
2692
2693 static void knife_make_face_cuts(KnifeTool_OpData *kcd, BMFace *f, ListBase *kfedges)
2694 {
2695         BMesh *bm = kcd->em->bm;
2696         KnifeEdge *kfe;
2697         BMFace *fnew, *fnew2, *fhole;
2698         ListBase *chain, *hole, *sidechain;
2699         ListBase *fnew_kfedges, *fnew2_kfedges;
2700         Ref *ref, *refnext;
2701         int count, oldcount;
2702
2703         oldcount = BLI_countlist(kfedges);
2704         while ((chain = find_chain(kcd, kfedges)) != NULL) {
2705                 knife_make_chain_cut(kcd, f, chain, &fnew);
2706                 if (!fnew) {
2707                         return;
2708                 }
2709
2710                 /* Move kfedges to fnew_kfedges if they are now in fnew.
2711                  * The chain edges were removed already */
2712                 fnew_kfedges = knife_empty_list(kcd);
2713                 for (ref = kfedges->first; ref; ref = refnext) {
2714                         kfe = ref->ref;
2715                         refnext = ref->next;
2716                         if (knife_edge_in_face(kcd, kfe, fnew)) {
2717                                 BLI_remlink(kfedges, ref);
2718                                 kfe->basef = fnew;
2719                                 knife_append_list(kcd, fnew_kfedges, kfe);
2720                         }
2721                 }
2722                 if (fnew_kfedges->first)
2723                         knife_make_face_cuts(kcd, fnew, fnew_kfedges);
2724
2725                 /* find_chain should always remove edges if it returns true,
2726                  * but guard against infinite loop anyway */
2727                 count = BLI_countlist(kfedges);
2728                 if (count >= oldcount) {
2729                         BLI_assert(!"knife find_chain infinite loop");
2730                         return;
2731                 }
2732                 oldcount = count;
2733         }
2734
2735         while ((hole = find_hole(kcd, kfedges)) != NULL) {
2736                 if (find_hole_chains(kcd, hole, f, &chain, &sidechain)) {
2737                         /* chain goes across f and sidechain comes back
2738                          * from the second last vertex to the second vertex.
2739                          */
2740                         knife_make_chain_cut(kcd, f, chain, &fnew);
2741                         if (!fnew) {
2742                                 BLI_assert(!"knife failed hole cut");
2743                                 return;
2744                         }
2745                         kfe = ((Ref *)sidechain->first)->ref;
2746                         if (knife_edge_in_face(kcd, kfe, f)) {
2747                                 knife_make_chain_cut(kcd, f, sidechain, &fnew2);
2748                                 if (fnew2 == NULL) {
2749                                         return;
2750                                 }
2751                                 fhole = f;
2752                         }
2753                         else if (knife_edge_in_face(kcd, kfe, fnew)) {
2754                                 knife_make_chain_cut(kcd, fnew, sidechain, &fnew2);
2755                                 if (fnew2 == NULL) {
2756                                         return;
2757                                 }
2758                                 fhole = fnew2;
2759                         }
2760                         else {
2761                                 /* shouldn't happen except in funny edge cases */
2762                                 return;
2763                         }
2764                         BM_face_kill(bm, fhole);
2765                         /* Move kfedges to either fnew or fnew2 if appropriate.
2766                          * The hole edges were removed already */
2767                         fnew_kfedges = knife_empty_list(kcd);
2768                         fnew2_kfedges = knife_empty_list(kcd);
2769                         for (ref = kfedges->first; ref; ref = refnext) {
2770                                 kfe = ref->ref;
2771                                 refnext = ref->next;
2772                                 if (knife_edge_in_face(kcd, kfe, fnew)) {
2773                                         BLI_remlink(kfedges, ref);
2774                                         kfe->basef = fnew;
2775                                         knife_append_list(kcd, fnew_kfedges, kfe);
2776                                 }
2777                                 else if (knife_edge_in_face(kcd, kfe, fnew2)) {
2778                                         BLI_remlink(kfedges, ref);
2779                                         kfe->basef = fnew2;
2780                                         knife_append_list(kcd, fnew2_kfedges, kfe);
2781                                 }
2782                         }
2783                         /* We'll skip knife edges that are in the newly formed hole.
2784                          * (Maybe we shouldn't have made a hole in the first place?) */
2785                         if (fnew != fhole && fnew_kfedges->first)
2786                                 knife_make_face_cuts(kcd, fnew, fnew_kfedges);
2787                         if (fnew2 != fhole && fnew2_kfedges->first)
2788                                 knife_make_face_cuts(kcd, fnew2, fnew2_kfedges);
2789                         if (f == fhole)
2790                                 break;
2791                         /* find_hole should always remove edges if it returns true,
2792                          * but guard against infinite loop anyway */
2793                         count = BLI_countlist(kfedges);
2794                         if (count >= oldcount) {
2795                                 BLI_assert(!"knife find_hole infinite loop");
2796                                 return;
2797                         }
2798                         oldcount = count;
2799                 }
2800         }
2801 }
2802
2803 /* Use the network of KnifeEdges and KnifeVerts accumulated to make real BMVerts and BMEdedges */
2804 static void knife_make_cuts(KnifeTool_OpData *kcd)
2805 {
2806         BMesh *bm = kcd->em->bm;
2807         KnifeEdge *kfe;
2808         KnifeVert *kfv;
2809         BMFace *f;
2810         BMEdge *e, *enew;
2811         ListBase *lst;
2812         Ref *ref;
2813         float pct;
2814         SmallHashIter hiter;
2815         BLI_mempool_iter iter;
2816         SmallHash fhash_, *fhash = &fhash_;
2817         SmallHash ehash_, *ehash = &ehash_;
2818
2819         BLI_smallhash_init(fhash);
2820         BLI_smallhash_init(ehash);
2821
2822         /* put list of cutting edges for a face into fhash, keyed by face */
2823         BLI_mempool_iternew(kcd->kedges, &iter);
2824         for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
2825                 f = kfe->basef;
2826                 if (!f || kfe->e)
2827                         continue;
2828                 lst = BLI_smallhash_lookup(fhash, (uintptr_t)f);
2829                 if (!lst) {
2830                         lst = knife_empty_list(kcd);
2831                         BLI_smallhash_insert(fhash, (uintptr_t)f, lst);
2832                 }
2833                 knife_append_list(kcd, lst, kfe);
2834         }
2835
2836         /* put list of splitting vertices for an edge into ehash, keyed by edge */
2837         BLI_mempool_iternew(kcd->kverts, &iter);
2838         for (kfv = BLI_mempool_iterstep(&iter); kfv; kfv = BLI_mempool_iterstep(&iter)) {
2839                 if (kfv->v)
2840                         continue;  /* already have a BMVert */
2841                 for (ref = kfv->edges.first; ref; ref = ref->next) {
2842                         kfe = ref->ref;
2843                         e = kfe->e;
2844                         if (!e)
2845                                 continue;
2846                         lst = BLI_smallhash_lookup(ehash, (uintptr_t)e);
2847                         if (!lst) {
2848                                 lst = knife_empty_list(kcd);
2849                                 BLI_smallhash_insert(ehash, (uintptr_t)e, lst);
2850                         }
2851                         /* there can be more than one kfe in kfv's list with same e */
2852                         if (!find_ref(lst, kfv))
2853                                 knife_append_list(kcd, lst, kfv);
2854                 }
2855         }
2856
2857         /* split bmesh edges where needed */
2858         for (lst = BLI_smallhash_iternew(ehash, &hiter, (uintptr_t *)&e); lst;
2859              lst = BLI_smallhash_iternext(&hiter, (uintptr_t *)&e))
2860         {
2861                 sort_by_frac_along(lst, e);
2862                 for (ref = lst->first; ref; ref = ref->next) {
2863                         kfv = ref->ref;
2864                         pct = frac_along(e->v1->co, e->v2->co, kfv->co);
2865                         kfv->v = BM_edge_split(bm, e, e->v1, &enew, pct);
2866                 }
2867         }
2868
2869         if (kcd->only_select) {
2870                 EDBM_flag_disable_all(kcd->em, BM_ELEM_SELECT);
2871         }
2872
2873         /* do cuts for each face */
2874         for (lst = BLI_smallhash_iternew(fhash, &hiter, (uintptr_t *)&f); lst;
2875              lst = BLI_smallhash_iternext(&hiter, (uintptr_t *)&f))
2876         {
2877                 knife_make_face_cuts(kcd, f, lst);
2878         }
2879
2880         BLI_smallhash_release(fhash);
2881         BLI_smallhash_release(ehash);
2882 }
2883 #endif
2884
2885 /* called on tool confirmation */
2886 static void knifetool_finish_ex(KnifeTool_OpData *kcd)
2887 {
2888 #if SCANFILL_CUTS
2889         knifenet_fill_faces(kcd);
2890 #else
2891         knife_make_cuts(kcd);
2892 #endif
2893
2894         EDBM_mesh_normals_update(kcd->em);
2895         EDBM_update_generic(kcd->em, true, true);
2896 }
2897 static void knifetool_finish(wmOperator *op)
2898 {
2899         KnifeTool_OpData *kcd = op->customdata;
2900         knifetool_finish_ex(kcd);
2901 }
2902
2903 static void knife_recalc_projmat(KnifeTool_OpData *kcd)
2904 {
2905         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
2906         ED_view3d_ob_project_mat_get(kcd->ar->regiondata, kcd->ob, kcd->projmat);
2907         //mult_m4_m4m4(kcd->projmat, kcd->vc.rv3d->winmat, kcd->vc.rv3d->viewmat);
2908
2909         kcd->is_ortho = ED_view3d_clip_range_get(kcd->vc.v3d, kcd->vc.rv3d,
2910                                                  &kcd->clipsta, &kcd->clipend, true);
2911 }
2912
2913 /* called when modal loop selection is done... */
2914 static void knifetool_exit_ex(bContext *C, KnifeTool_OpData *kcd)
2915 {
2916         if (!kcd)
2917                 return;
2918
2919         if (kcd->is_interactive) {
2920                 WM_cursor_restore(CTX_wm_window(C));
2921
2922                 /* deactivate the extra drawing stuff in 3D-View */
2923                 ED_region_draw_cb_exit(kcd->ar->type, kcd->draw_handle);
2924         }
2925
2926         /* free the custom data */
2927         BLI_mempool_destroy(kcd->refs);
2928         BLI_mempool_destroy(kcd->kverts);
2929         BLI_mempool_destroy(kcd->kedges);
2930
2931         BLI_ghash_free(kcd->origedgemap, NULL, NULL);
2932         BLI_ghash_free(kcd->origvertmap, NULL, NULL);
2933         BLI_ghash_free(kcd->kedgefacemap, NULL, NULL);
2934
2935         BKE_bmbvh_free(kcd->bmbvh);
2936         BLI_memarena_free(kcd->arena);
2937
2938         /* tag for redraw */
2939         ED_region_tag_redraw(kcd->ar);
2940
2941         if (kcd->cagecos)
2942                 MEM_freeN(kcd->cagecos);
2943
2944         if (kcd->linehits)
2945                 MEM_freeN(kcd->linehits);
2946
2947         /* destroy kcd itself */
2948         MEM_freeN(kcd);
2949 }
2950 static void knifetool_exit(bContext *C, wmOperator *op)
2951 {
2952         KnifeTool_OpData *kcd = op->customdata;
2953         knifetool_exit_ex(C, kcd);
2954         op->customdata = NULL;
2955 }
2956
2957 static void knifetool_update_mval(KnifeTool_OpData *kcd, const float mval[2])
2958 {
2959         knife_recalc_projmat(kcd);
2960         copy_v2_v2(kcd->mval, mval);
2961
2962         if (knife_update_active(kcd)) {
2963                 ED_region_tag_redraw(kcd->ar);
2964         }
2965 }
2966
2967 static void knifetool_update_mval_i(KnifeTool_OpData *kcd, const int mval_i[2])
2968 {
2969         float mval[2] = {UNPACK2(mval_i)};
2970         knifetool_update_mval(kcd, mval);
2971 }
2972
2973 /* called when modal loop selection gets set up... */
2974 static void knifetool_init(bContext *C, KnifeTool_OpData *kcd,
2975                            const bool only_select, const bool cut_through, const bool is_interactive)
2976 {
2977         Scene *scene = CTX_data_scene(C);
2978         Object *obedit = CTX_data_edit_object(C);
2979
2980         /* assign the drawing handle for drawing preview line... */
2981         kcd->ob = obedit;
2982         kcd->ar = CTX_wm_region(C);
2983
2984         em_setup_viewcontext(C, &kcd->vc);
2985
2986         kcd->em = BKE_editmesh_from_object(kcd->ob);
2987
2988         BM_mesh_elem_index_ensure(kcd->em->bm, BM_VERT);
2989
2990         kcd->cagecos = BKE_editmesh_vertexCos_get(kcd->em, scene, NULL);
2991
2992         kcd->bmbvh = BKE_bmbvh_new(kcd->em,
2993                                   BMBVH_RETURN_ORIG |
2994                                   (only_select ? BMBVH_RESPECT_SELECT : BMBVH_RESPECT_HIDDEN),
2995                                   kcd->cagecos, false);
2996
2997         kcd->arena = BLI_memarena_new(1 << 15, "knife");
2998         kcd->vthresh = KMAXDIST - 1;
2999         kcd->ethresh = KMAXDIST;
3000
3001         kcd->extend = true;
3002
3003         knife_recalc_projmat(kcd);
3004
3005         ED_region_tag_redraw(kcd->ar);
3006
3007         kcd->refs = BLI_mempool_create(sizeof(Ref), 1, 2048, 0);
3008         kcd->kverts = BLI_mempool_create(sizeof(KnifeVert), 1, 512, BLI_MEMPOOL_ALLOW_ITER);
3009         kcd->kedges = BLI_mempool_create(sizeof(KnifeEdge), 1, 512, BLI_MEMPOOL_ALLOW_ITER);
3010
3011         kcd->origedgemap = BLI_ghash_ptr_new("knife origedgemap");
3012         kcd->origvertmap = BLI_ghash_ptr_new("knife origvertmap");
3013         kcd->kedgefacemap = BLI_ghash_ptr_new("knife origvertmap");
3014
3015         /* cut all the way through the mesh if use_occlude_geometry button not pushed */
3016         kcd->is_interactive = is_interactive;
3017         kcd->cut_through = cut_through;
3018         kcd->only_select = only_select;
3019
3020         /* can't usefully select resulting edges in face mode */
3021         kcd->select_result = (kcd->em->selectmode != SCE_SELECT_FACE);
3022
3023         knife_pos_data_clear(&kcd->curr);
3024         knife_pos_data_clear(&kcd->prev);
3025
3026         if (is_interactive) {
3027                 kcd->draw_handle = ED_region_draw_cb_activate(kcd->ar->type, knifetool_draw, kcd, REGION_DRAW_POST_VIEW);
3028
3029                 knife_init_colors(&kcd->colors);
3030         }
3031 }
3032
3033 static int knifetool_cancel(bContext *C, wmOperator *op)
3034 {
3035         /* this is just a wrapper around exit() */
3036         knifetool_exit(C, op);
3037         return OPERATOR_CANCELLED;
3038 }
3039
3040 static int knifetool_invoke(bContext *C, wmOperator *op, const wmEvent *event)
3041 {
3042         const bool only_select = RNA_boolean_get(op->ptr, "only_selected");
3043         const bool cut_through = !RNA_boolean_get(op->ptr, "use_occlude_geometry");
3044
3045         KnifeTool_OpData *kcd;
3046
3047         view3d_operator_needs_opengl(C);
3048
3049         /* alloc new customdata */
3050         kcd = op->customdata = MEM_callocN(sizeof(KnifeTool_OpData), __func__);
3051
3052         knifetool_init(C, kcd, only_select, cut_through, true);
3053
3054         /* add a modal handler for this operator - handles loop selection */
3055         WM_cursor_modal(CTX_wm_window(C),&nbs