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