source/blender/editors/mesh/editmesh_knife.c

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