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