Fix T44492: knife tool should cut across a split edge.
[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         float *co11, *co12, *co21, *co22;
1325
1326         co11 = e1->v1->co;
1327         co12 = e1->v2->co;
1328         co21 = e2->v1->co;
1329         co22 = e2->v2->co;
1330         if ((equals_v3v3(co11, co21) && equals_v3v3(co12, co22)) ||
1331             (equals_v3v3(co11, co22) && equals_v3v3(co12, co21)))
1332                 return true;
1333         else
1334                 return false;
1335 }
1336
1337 /* Callback used in point_is_visible to exclude hits on the faces that are the same
1338  * as or contain the hitting element (which is in user_data).
1339  * Also (see T44492) want to exclude hits on faces that butt up to the hitting element
1340  * (e.g., when you double an edge by an edge split).
1341  */
1342 static bool bm_ray_cast_cb_elem_not_in_face_check(BMFace *f, void *user_data)
1343 {
1344         bool ans;
1345         BMEdge *e, *e2;
1346         BMIter iter;
1347
1348         switch (((BMElem *)user_data)->head.htype) {
1349                 case BM_FACE:
1350                         ans = (BMFace *)user_data != f;
1351                         break;
1352                 case BM_EDGE:
1353                         e = (BMEdge *)user_data;
1354                         ans = !BM_edge_in_face(e, f);
1355                         if (ans) {
1356                                 /* Is it a boundary edge, coincident with a split edge? */
1357                                 if (BM_edge_face_count(e) == 1) {
1358                                         BM_ITER_ELEM(e2, &iter, f, BM_EDGES_OF_FACE) {
1359                                                 if (coinciding_edges(e, e2)) {
1360                                                         ans = false;
1361                                                         break;
1362                                                 }
1363                                         }
1364                                 }
1365                         }
1366                         break;
1367                 case BM_VERT:
1368                         ans = !BM_vert_in_face((BMVert *)user_data, f);
1369                         break;
1370                 default:
1371                         ans = true;
1372                         break;
1373         }
1374         return ans;
1375 }
1376
1377
1378 /**
1379  * Check if \a p is visible (not clipped, not occluded by another face).
1380  * s in screen projection of p.
1381  *
1382  * \param ele_test  Optional vert/edge/face to use when \a p is on the surface of the geometry,
1383  * intersecting faces matching this face (or connected when an vert/edge) will be ignored.
1384  */
1385 static bool point_is_visible(
1386         KnifeTool_OpData *kcd, const float p[3], const float s[2], bglMats *mats,
1387         BMElem *ele_test)
1388 {
1389         BMFace *f_hit;
1390
1391         /* If box clipping on, make sure p is not clipped */
1392         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING &&
1393             ED_view3d_clipping_test(kcd->vc.rv3d, p, true))
1394         {
1395                 return false;
1396         }
1397
1398         /* If not cutting through, make sure no face is in front of p */
1399         if (!kcd->cut_through) {
1400                 float dist;
1401                 float view[3], p_ofs[3];
1402
1403                 /* TODO: I think there's a simpler way to get the required raycast ray */
1404                 ED_view3d_unproject(mats, view, s[0], s[1], 0.0f);
1405
1406                 mul_m4_v3(kcd->ob->imat, view);
1407
1408                 /* make p_ofs a little towards view, so ray doesn't hit p's face. */
1409                 sub_v3_v3(view, p);
1410                 dist = normalize_v3(view);
1411                 copy_v3_v3(p_ofs, p);
1412
1413                 /* avoid projecting behind the viewpoint */
1414                 if (kcd->is_ortho && (kcd->vc.rv3d->persp != RV3D_CAMOB)) {
1415                         dist = kcd->vc.v3d->far * 2.0f;
1416                 }
1417
1418                 if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1419                         float view_clip[2][3];
1420                         /* note: view_clip[0] should never get clipped */
1421                         copy_v3_v3(view_clip[0], p_ofs);
1422                         madd_v3_v3v3fl(view_clip[1], p_ofs, view, dist);
1423
1424                         if (clip_segment_v3_plane_n(view_clip[0], view_clip[1], kcd->vc.rv3d->clip_local, 6)) {
1425                                 dist = len_v3v3(p_ofs, view_clip[1]);
1426                         }
1427                 }
1428
1429                 /* see if there's a face hit between p1 and the view */
1430                 if (ele_test) {
1431                         f_hit = BKE_bmbvh_ray_cast_filter(
1432                                     kcd->bmbvh, p_ofs, view, KNIFE_FLT_EPS, &dist, NULL, NULL,
1433                                     bm_ray_cast_cb_elem_not_in_face_check, ele_test);
1434                 }
1435                 else {
1436                         f_hit = BKE_bmbvh_ray_cast(
1437                                     kcd->bmbvh, p_ofs, view, KNIFE_FLT_EPS, &dist, NULL, NULL);
1438                 }
1439
1440                 if (f_hit) {
1441                         return false;
1442                 }
1443         }
1444
1445         return true;
1446 }
1447
1448 /* Clip the line (v1, v2) to planes perpendicular to it and distances d from
1449  * the closest point on the line to the origin */
1450 static void clip_to_ortho_planes(float v1[3], float v2[3], float d)
1451 {
1452         float closest[3];
1453         const float origin[3] = {0.0f, 0.0f, 0.0f};
1454
1455         closest_to_line_v3(closest, origin, v1, v2);
1456         dist_ensure_v3_v3fl(v1, closest, d);
1457         dist_ensure_v3_v3fl(v2, closest, d);
1458 }
1459
1460 static void set_linehit_depth(KnifeTool_OpData *kcd, KnifeLineHit *lh)
1461 {
1462         lh->m = dot_m4_v3_row_z(kcd->vc.rv3d->persmatob, lh->cagehit);
1463 }
1464
1465 /* Finds visible (or all, if cutting through) edges that intersects the current screen drag line */
1466 static void knife_find_line_hits(KnifeTool_OpData *kcd)
1467 {
1468         bglMats mats;
1469         SmallHash faces, kfes, kfvs;
1470         float v1[3], v2[3], v3[3], v4[3], s1[2], s2[2];
1471         BVHTree *planetree, *tree;
1472         BVHTreeOverlap *results, *result;
1473         BMLoop **ls;
1474         BMFace *f;
1475         KnifeEdge *kfe;
1476         KnifeVert *v;
1477         ListBase *lst;
1478         Ref *ref;
1479         KnifeLineHit *linehits = NULL;
1480         BLI_array_declare(linehits);
1481         SmallHashIter hiter;
1482         KnifeLineHit hit;
1483         void *val;
1484         void **val_p;
1485         float plane_cos[12];
1486         float s[2], se1[2], se2[2], sint[2];
1487         float r1[3], r2[3];
1488         float d, d1, d2, lambda;
1489         float vert_tol, vert_tol_sq;
1490         float line_tol, line_tol_sq;
1491         float face_tol, face_tol_sq;
1492         int isect_kind;
1493         unsigned int tot;
1494         int i;
1495         const bool use_hit_prev = true;
1496         const bool use_hit_curr = (kcd->is_drag_hold == false);
1497
1498         bgl_get_mats(&mats);
1499
1500         if (kcd->linehits) {
1501                 MEM_freeN(kcd->linehits);
1502                 kcd->linehits = NULL;
1503                 kcd->totlinehit = 0;
1504         }
1505
1506         copy_v3_v3(v1, kcd->prev.cage);
1507         copy_v3_v3(v2, kcd->curr.cage);
1508
1509         /* project screen line's 3d coordinates back into 2d */
1510         knife_project_v2(kcd, v1, s1);
1511         knife_project_v2(kcd, v2, s2);
1512
1513         if (kcd->is_interactive) {
1514                 if (len_squared_v2v2(s1, s2) < 1.0f) {
1515                         return;
1516                 }
1517         }
1518         else {
1519                 if (len_squared_v2v2(s1, s2) < KNIFE_FLT_EPS_SQUARED) {
1520                         return;
1521                 }
1522         }
1523
1524         /* unproject screen line */
1525         ED_view3d_win_to_segment(kcd->ar, kcd->vc.v3d, s1, v1, v3, true);
1526         ED_view3d_win_to_segment(kcd->ar, kcd->vc.v3d, s2, v2, v4, true);
1527
1528         mul_m4_v3(kcd->ob->imat, v1);
1529         mul_m4_v3(kcd->ob->imat, v2);
1530         mul_m4_v3(kcd->ob->imat, v3);
1531         mul_m4_v3(kcd->ob->imat, v4);
1532
1533         /* numeric error, 'v1' -> 'v2', 'v2' -> 'v4' can end up being ~2000 units apart in otho mode
1534          * (from ED_view3d_win_to_segment_clip() above)
1535          * this gives precision error; rather then solving properly
1536          * (which may involve using doubles everywhere!),
1537          * limit the distance between these points */
1538         if (kcd->is_ortho && (kcd->vc.rv3d->persp != RV3D_CAMOB)) {
1539                 if (kcd->ortho_extent == 0.0f)
1540                         calc_ortho_extent(kcd);
1541                 clip_to_ortho_planes(v1, v3, kcd->ortho_extent + 10.0f);
1542                 clip_to_ortho_planes(v2, v4, kcd->ortho_extent + 10.0f);
1543         }
1544
1545         /* First use bvh tree to find faces, knife edges, and knife verts that might
1546          * intersect the cut plane with rays v1-v3 and v2-v4.
1547          * This deduplicates the candidates before doing more expensive intersection tests. */
1548
1549         tree = BKE_bmbvh_tree_get(kcd->bmbvh);
1550         planetree = BLI_bvhtree_new(4, FLT_EPSILON * 4, 8, 8);
1551         copy_v3_v3(plane_cos + 0, v1);
1552         copy_v3_v3(plane_cos + 3, v2);
1553         copy_v3_v3(plane_cos + 6, v3);
1554         copy_v3_v3(plane_cos + 9, v4);
1555         BLI_bvhtree_insert(planetree, 0, plane_cos, 4);
1556         BLI_bvhtree_balance(planetree);
1557
1558         results = BLI_bvhtree_overlap(tree, planetree, &tot);
1559         if (!results) {
1560                 BLI_bvhtree_free(planetree);
1561                 return;
1562         }
1563
1564         BLI_smallhash_init(&faces);
1565         BLI_smallhash_init(&kfes);
1566         BLI_smallhash_init(&kfvs);
1567
1568         for (i = 0, result = results; i < tot; i++, result++) {
1569                 ls = (BMLoop **)kcd->em->looptris[result->indexA];
1570                 f = ls[0]->f;
1571                 set_lowest_face_tri(kcd, f, result->indexA);
1572
1573                 /* occlude but never cut unselected faces (when only_select is used) */
1574                 if (kcd->only_select && !BM_elem_flag_test(f, BM_ELEM_SELECT)) {
1575                         continue;
1576                 }
1577                 /* for faces, store index of lowest hit looptri in hash */
1578                 if (BLI_smallhash_haskey(&faces, (uintptr_t)f)) {
1579                         continue;
1580                 }
1581                 /* don't care what the value is except that it is non-NULL, for iterator */
1582                 BLI_smallhash_insert(&faces, (uintptr_t)f, f);
1583
1584                 lst = knife_get_face_kedges(kcd, f);
1585                 for (ref = lst->first; ref; ref = ref->next) {
1586                         kfe = ref->ref;
1587                         if (BLI_smallhash_haskey(&kfes, (uintptr_t)kfe))
1588                                 continue;
1589                         BLI_smallhash_insert(&kfes, (uintptr_t)kfe, kfe);
1590                         v = kfe->v1;
1591                         BLI_smallhash_reinsert(&kfvs, (uintptr_t)v, v);
1592                         v = kfe->v2;
1593                         BLI_smallhash_reinsert(&kfvs, (uintptr_t)v, v);
1594                 }
1595         }
1596
1597         /* Now go through the candidates and find intersections */
1598         /* These tolerances, in screen space, are for intermediate hits, as ends are already snapped to screen */
1599
1600         vert_tol = KNIFE_FLT_EPS_PX_VERT;
1601         line_tol = KNIFE_FLT_EPS_PX_EDGE;
1602         face_tol = KNIFE_FLT_EPS_PX_FACE;
1603
1604         vert_tol_sq = vert_tol * vert_tol;
1605         line_tol_sq = line_tol * line_tol;
1606         face_tol_sq = face_tol * face_tol;
1607
1608         /* Assume these tolerances swamp floating point rounding errors in calculations below */
1609
1610         /* first look for vertex hits */
1611         for (val_p = BLI_smallhash_iternew_p(&kfvs, &hiter, (uintptr_t *)&v); val_p;
1612              val_p = BLI_smallhash_iternext_p(&hiter, (uintptr_t *)&v))
1613         {
1614                 KnifeEdge *kfe_hit = NULL;
1615
1616                 knife_project_v2(kcd, v->cageco, s);
1617                 d = dist_squared_to_line_segment_v2(s, s1, s2);
1618                 if ((d <= vert_tol_sq) &&
1619                     (point_is_visible(kcd, v->cageco, s, &mats, bm_elem_from_knife_vert(v, &kfe_hit))))
1620                 {
1621                         memset(&hit, 0, sizeof(hit));
1622                         hit.v = v;
1623
1624                         /* If this isn't from an existing BMVert, it may have been added to a BMEdge originally.
1625                                  * knowing if the hit comes from an edge is important for edge-in-face checks later on
1626                                  * see: #knife_add_single_cut -> #knife_verts_edge_in_face, T42611 */
1627                         if (kfe_hit) {
1628                                 hit.kfe = kfe_hit;
1629                         }
1630
1631                         copy_v3_v3(hit.hit, v->co);
1632                         copy_v3_v3(hit.cagehit, v->cageco);
1633                         copy_v2_v2(hit.schit, s);
1634                         set_linehit_depth(kcd, &hit);
1635                         BLI_array_append(linehits, hit);
1636                 }
1637                 else {
1638                         /* note that these vertes aren't used */
1639                         *val_p = NULL;
1640                 }
1641         }
1642
1643         /* now edge hits; don't add if a vertex at end of edge should have hit */
1644         for (val = BLI_smallhash_iternew(&kfes, &hiter, (uintptr_t *)&kfe); val;
1645              val = BLI_smallhash_iternext(&hiter, (uintptr_t *)&kfe))
1646         {
1647                 int kfe_verts_in_cut;
1648                 /* if we intersect both verts, don't attempt to intersect the edge */
1649
1650                 kfe_verts_in_cut = (BLI_smallhash_lookup(&kfvs, (intptr_t)kfe->v1) != NULL) +
1651                                    (BLI_smallhash_lookup(&kfvs, (intptr_t)kfe->v2) != NULL);
1652
1653                 if (kfe_verts_in_cut == 2) {
1654                         continue;
1655                 }
1656
1657                 knife_project_v2(kcd, kfe->v1->cageco, se1);
1658                 knife_project_v2(kcd, kfe->v2->cageco, se2);
1659                 isect_kind = (kfe_verts_in_cut) ? -1 : isect_seg_seg_v2_point(s1, s2, se1, se2, sint);
1660                 if (isect_kind == -1) {
1661                         /* isect_seg_seg_v2 doesn't do tolerance test around ends of s1-s2 */
1662                         closest_to_line_segment_v2(sint, s1, se1, se2);
1663                         if (len_squared_v2v2(sint, s1) <= line_tol_sq)
1664                                 isect_kind = 1;
1665                         else {
1666                                 closest_to_line_segment_v2(sint, s2, se1, se2);
1667                                 if (len_squared_v2v2(sint, s2) <= line_tol_sq)
1668                                         isect_kind = 1;
1669                         }
1670                 }
1671                 if (isect_kind == 1) {
1672                         d1 = len_v2v2(sint, se1);
1673                         d2 = len_v2v2(se2, se1);
1674                         if (!(d1 <= line_tol || d2 <= line_tol || fabsf(d1 - d2) <= line_tol)) {
1675                                 float p_cage[3], p_cage_tmp[3];
1676                                 lambda = d1 / d2;
1677                                 /* Can't just interpolate between ends of kfe because
1678                                  * that doesn't work with perspective transformation.
1679                                  * Need to find 3d intersection of ray through sint */
1680                                 knife_input_ray_segment(kcd, sint, 1.0f, r1, r2);
1681                                 isect_kind = isect_line_line_v3(kfe->v1->cageco, kfe->v2->cageco, r1, r2, p_cage, p_cage_tmp);
1682                                 if (isect_kind >= 1 && point_is_visible(kcd, p_cage, sint, &mats, bm_elem_from_knife_edge(kfe))) {
1683                                         memset(&hit, 0, sizeof(hit));
1684                                         if (kcd->snap_midpoints) {
1685                                                 /* choose intermediate point snap too */
1686                                                 mid_v3_v3v3(p_cage, kfe->v1->cageco, kfe->v2->cageco);
1687                                                 mid_v2_v2v2(sint, se1, se2);
1688                                                 lambda = 0.5f;
1689                                         }
1690                                         hit.kfe = kfe;
1691                                         transform_point_by_seg_v3(
1692                                                 hit.hit, p_cage,
1693                                                 kfe->v1->co, kfe->v2->co,
1694                                                 kfe->v1->cageco, kfe->v2->cageco);
1695                                         copy_v3_v3(hit.cagehit, p_cage);
1696                                         copy_v2_v2(hit.schit, sint);
1697                                         hit.perc = lambda;
1698                                         set_linehit_depth(kcd, &hit);
1699                                         BLI_array_append(linehits, hit);
1700                                 }
1701                         }
1702                 }
1703         }
1704         /* now face hits; don't add if a vertex or edge in face should have hit */
1705         for (val = BLI_smallhash_iternew(&faces, &hiter, (uintptr_t *)&f); val;
1706              val = BLI_smallhash_iternext(&hiter, (uintptr_t *)&f))
1707         {
1708                 float p[3], p_cage[3];
1709
1710                 if (use_hit_prev && knife_ray_intersect_face(kcd, s1, v1, v3, f, face_tol_sq, p, p_cage)) {
1711                         if (point_is_visible(kcd, p_cage, s1, &mats, (BMElem *)f)) {
1712                                 memset(&hit, 0, sizeof(hit));
1713                                 hit.f = f;
1714                                 copy_v3_v3(hit.hit, p);
1715                                 copy_v3_v3(hit.cagehit, p_cage);
1716                                 copy_v2_v2(hit.schit, s1);
1717                                 set_linehit_depth(kcd, &hit);
1718                                 BLI_array_append(linehits, hit);
1719                         }
1720                 }
1721
1722                 if (use_hit_curr && knife_ray_intersect_face(kcd, s2, v2, v4, f, face_tol_sq, p, p_cage)) {
1723                         if (point_is_visible(kcd, p_cage, s2, &mats, (BMElem *)f)) {
1724                                 memset(&hit, 0, sizeof(hit));
1725                                 hit.f = f;
1726                                 copy_v3_v3(hit.hit, p);
1727                                 copy_v3_v3(hit.cagehit, p_cage);
1728                                 copy_v2_v2(hit.schit, s2);
1729                                 set_linehit_depth(kcd, &hit);
1730                                 BLI_array_append(linehits, hit);
1731                         }
1732                 }
1733         }
1734
1735         kcd->linehits = linehits;
1736         kcd->totlinehit = BLI_array_count(linehits);
1737
1738         /* find position along screen line, used for sorting */
1739         for (i = 0; i < kcd->totlinehit; i++) {
1740                 KnifeLineHit *lh = kcd->linehits + i;
1741
1742                 lh->l = len_v2v2(lh->schit, s1) / len_v2v2(s2, s1);
1743         }
1744
1745         BLI_smallhash_release(&faces);
1746         BLI_smallhash_release(&kfes);
1747         BLI_smallhash_release(&kfvs);
1748         BLI_bvhtree_free(planetree);
1749         if (results)
1750                 MEM_freeN(results);
1751 }
1752
1753 static void knife_input_ray_segment(KnifeTool_OpData *kcd, const float mval[2], const float ofs,
1754                                     float r_origin[3], float r_origin_ofs[3])
1755 {
1756         bglMats mats;
1757
1758         bgl_get_mats(&mats);
1759
1760         /* unproject to find view ray */
1761         ED_view3d_unproject(&mats, r_origin,     mval[0], mval[1], 0.0f);
1762         ED_view3d_unproject(&mats, r_origin_ofs, mval[0], mval[1], ofs);
1763
1764         /* transform into object space */
1765         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat); 
1766
1767         mul_m4_v3(kcd->ob->imat, r_origin);
1768         mul_m4_v3(kcd->ob->imat, r_origin_ofs);
1769 }
1770
1771 static BMFace *knife_find_closest_face(KnifeTool_OpData *kcd, float co[3], float cageco[3], bool *is_space)
1772 {
1773         BMFace *f;
1774         float dist = KMAXDIST;
1775         float origin[3];
1776         float origin_ofs[3];
1777         float ray[3];
1778
1779         /* unproject to find view ray */
1780         knife_input_ray_segment(kcd, kcd->curr.mval, 1.0f, origin, origin_ofs);
1781         sub_v3_v3v3(ray, origin_ofs, origin);
1782
1783         f = BKE_bmbvh_ray_cast(kcd->bmbvh, origin, ray, 0.0f, NULL, co, cageco);
1784
1785         if (f && kcd->only_select && BM_elem_flag_test(f, BM_ELEM_SELECT) == 0) {
1786                 f = NULL;
1787         }
1788
1789         if (is_space)
1790                 *is_space = !f;
1791
1792         if (!f) {
1793                 if (kcd->is_interactive) {
1794                         /* try to use backbuffer selection method if ray casting failed */
1795                         f = EDBM_face_find_nearest(&kcd->vc, &dist);
1796
1797                         /* cheat for now; just put in the origin instead
1798                          * of a true coordinate on the face.
1799                          * This just puts a point 1.0f infront of the view. */
1800                         add_v3_v3v3(co, origin, ray);
1801                 }
1802         }
1803
1804         return f;
1805 }
1806
1807 /* find the 2d screen space density of vertices within a radius.  used to scale snapping
1808  * distance for picking edges/verts.*/
1809 static int knife_sample_screen_density(KnifeTool_OpData *kcd, const float radius)
1810 {
1811         BMFace *f;
1812         bool is_space;
1813         float co[3], cageco[3], sco[2];
1814
1815         BLI_assert(kcd->is_interactive == true);
1816
1817         f = knife_find_closest_face(kcd, co, cageco, &is_space);
1818
1819         if (f && !is_space) {
1820                 const float radius_sq = radius * radius;
1821                 ListBase *lst;
1822                 Ref *ref;
1823                 float dis_sq;
1824                 int c = 0;
1825
1826                 knife_project_v2(kcd, cageco, sco);
1827
1828                 lst = knife_get_face_kedges(kcd, f);
1829                 for (ref = lst->first; ref; ref = ref->next) {
1830                         KnifeEdge *kfe = ref->ref;
1831                         int i;
1832
1833                         for (i = 0; i < 2; i++) {
1834                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1835
1836                                 knife_project_v2(kcd, kfv->cageco, kfv->sco);
1837
1838                                 dis_sq = len_squared_v2v2(kfv->sco, sco);
1839                                 if (dis_sq < radius_sq) {
1840                                         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1841                                                 if (ED_view3d_clipping_test(kcd->vc.rv3d, kfv->cageco, true) == 0) {
1842                                                         c++;
1843                                                 }
1844                                         }
1845                                         else {
1846                                                 c++;
1847                                         }
1848                                 }
1849                         }
1850                 }
1851
1852                 return c;
1853         }
1854
1855         return 0;
1856 }
1857
1858 /* returns snapping distance for edges/verts, scaled by the density of the
1859  * surrounding mesh (in screen space)*/
1860 static float knife_snap_size(KnifeTool_OpData *kcd, float maxsize)
1861 {
1862         float density;
1863
1864         if (kcd->is_interactive) {
1865                 density = (float)knife_sample_screen_density(kcd, maxsize * 2.0f);
1866         }
1867         else {
1868                 density = 1.0f;
1869         }
1870
1871         if (density < 1.0f)
1872                 density = 1.0f;
1873
1874         return min_ff(maxsize / (density * 0.5f), maxsize);
1875 }
1876
1877 /* p is closest point on edge to the mouse cursor */
1878 static KnifeEdge *knife_find_closest_edge(KnifeTool_OpData *kcd, float p[3], float cagep[3],
1879                                           BMFace **fptr, bool *is_space)
1880 {
1881         BMFace *f;
1882         float co[3], cageco[3], sco[2];
1883         float maxdist = knife_snap_size(kcd, kcd->ethresh);
1884
1885         if (kcd->ignore_vert_snapping)
1886                 maxdist *= 0.5f;
1887
1888         f = knife_find_closest_face(kcd, co, cageco, NULL);
1889         *is_space = !f;
1890
1891         kcd->curr.bmface = f;
1892
1893         if (f) {
1894                 const float maxdist_sq = maxdist * maxdist;
1895                 KnifeEdge *cure = NULL;
1896                 float cur_cagep[3];
1897                 ListBase *lst;
1898                 Ref *ref;
1899                 float dis_sq, curdis_sq = FLT_MAX;
1900
1901                 /* set p to co, in case we don't find anything, means a face cut */
1902                 copy_v3_v3(p, co);
1903                 copy_v3_v3(cagep, cageco);
1904
1905                 knife_project_v2(kcd, cageco, sco);
1906
1907                 /* look through all edges associated with this face */
1908                 lst = knife_get_face_kedges(kcd, f);
1909                 for (ref = lst->first; ref; ref = ref->next) {
1910                         KnifeEdge *kfe = ref->ref;
1911                         float test_cagep[3];
1912                         float lambda;
1913
1914                         /* project edge vertices into screen space */
1915                         knife_project_v2(kcd, kfe->v1->cageco, kfe->v1->sco);
1916                         knife_project_v2(kcd, kfe->v2->cageco, kfe->v2->sco);
1917
1918                         /* check if we're close enough and calculate 'lambda' */
1919                         if (kcd->is_angle_snapping) {
1920                         /* if snapping, check we're in bounds */
1921                                 float sco_snap[2];
1922                                 isect_line_line_v2_point(kfe->v1->sco, kfe->v2->sco, kcd->prev.mval, kcd->curr.mval, sco_snap);
1923                                 lambda = line_point_factor_v2(sco_snap, kfe->v1->sco, kfe->v2->sco);
1924
1925                                 /* be strict about angle-snapping within edge */
1926                                 if ((lambda < 0.0f - KNIFE_FLT_EPSBIG) || (lambda > 1.0f + KNIFE_FLT_EPSBIG)) {
1927                                         continue;
1928                                 }
1929
1930                                 dis_sq = len_squared_v2v2(sco, sco_snap);
1931                                 if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
1932                                         /* we already have 'lambda' */
1933                                 }
1934                                 else {
1935                                         continue;
1936                                 }
1937                         }
1938                         else {
1939                                 dis_sq = dist_squared_to_line_segment_v2(sco, kfe->v1->sco, kfe->v2->sco);
1940                                 if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
1941                                         lambda = line_point_factor_v2(sco, kfe->v1->sco, kfe->v2->sco);
1942                                 }
1943                                 else {
1944                                         continue;
1945                                 }
1946                         }
1947
1948                         /* now we have 'lambda' calculated (in screen-space) */
1949                         knife_interp_v3_v3v3(kcd, test_cagep, kfe->v1->cageco, kfe->v2->cageco, lambda);
1950
1951                         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1952                                 /* check we're in the view */
1953                                 if (ED_view3d_clipping_test(kcd->vc.rv3d, test_cagep, true)) {
1954                                         continue;
1955                                 }
1956                         }
1957
1958                         cure = kfe;
1959                         curdis_sq = dis_sq;
1960                         copy_v3_v3(cur_cagep, test_cagep);
1961                 }
1962
1963                 if (fptr)
1964                         *fptr = f;
1965
1966                 if (cure) {
1967                         if (!kcd->ignore_edge_snapping || !(cure->e)) {
1968                                 KnifeVert *edgesnap = NULL;
1969
1970                                 if (kcd->snap_midpoints) {
1971                                         mid_v3_v3v3(p, cure->v1->co, cure->v2->co);
1972                                         mid_v3_v3v3(cagep, cure->v1->cageco, cure->v2->cageco);
1973                                 }
1974                                 else {
1975                                         float lambda = line_point_factor_v3(cur_cagep, cure->v1->cageco, cure->v2->cageco);
1976                                         copy_v3_v3(cagep, cur_cagep);
1977                                         interp_v3_v3v3(p, cure->v1->co, cure->v2->co, lambda);
1978                                 }
1979
1980                                 /* update mouse coordinates to the snapped-to edge's screen coordinates
1981                                  * this is important for angle snap, which uses the previous mouse position */
1982                                 edgesnap = new_knife_vert(kcd, p, cagep);
1983                                 kcd->curr.mval[0] = edgesnap->sco[0];
1984                                 kcd->curr.mval[1] = edgesnap->sco[1];
1985
1986                         }
1987                         else {
1988                                 return NULL;
1989                         }
1990                 }
1991
1992                 return cure;
1993         }
1994
1995         if (fptr)
1996                 *fptr = NULL;
1997
1998         return NULL;
1999 }
2000
2001 /* find a vertex near the mouse cursor, if it exists */
2002 static KnifeVert *knife_find_closest_vert(KnifeTool_OpData *kcd, float p[3], float cagep[3], BMFace **fptr,
2003                                           bool *is_space)
2004 {
2005         BMFace *f;
2006         float co[3], cageco[3], sco[2], maxdist = knife_snap_size(kcd, kcd->vthresh);
2007
2008         if (kcd->ignore_vert_snapping)
2009                 maxdist *= 0.5f;
2010
2011         f = knife_find_closest_face(kcd, co, cageco, is_space);
2012
2013         kcd->curr.bmface = f;
2014
2015         if (f) {
2016                 const float maxdist_sq = maxdist * maxdist;
2017                 ListBase *lst;
2018                 Ref *ref;
2019                 KnifeVert *curv = NULL;
2020                 float dis_sq, curdis_sq = FLT_MAX;
2021
2022                 /* set p to co, in case we don't find anything, means a face cut */
2023                 copy_v3_v3(p, co);
2024                 copy_v3_v3(cagep, cageco);
2025
2026                 knife_project_v2(kcd, cageco, sco);
2027
2028                 lst = knife_get_face_kedges(kcd, f);
2029                 for (ref = lst->first; ref; ref = ref->next) {
2030                         KnifeEdge *kfe = ref->ref;
2031                         int i;
2032
2033                         for (i = 0; i < 2; i++) {
2034                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
2035
2036                                 knife_project_v2(kcd, kfv->cageco, kfv->sco);
2037
2038                                 /* be strict about angle snapping, the vertex needs to be very close to the angle, or we ignore */
2039                                 if (kcd->is_angle_snapping) {
2040                                         if (dist_squared_to_line_segment_v2(kfv->sco, kcd->prev.mval, kcd->curr.mval) > KNIFE_FLT_EPSBIG) {
2041                                                 continue;
2042                                         }
2043                                 }
2044
2045                                 dis_sq = len_squared_v2v2(kfv->sco, sco);
2046                                 if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
2047                                         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
2048                                                 if (ED_view3d_clipping_test(kcd->vc.rv3d, kfv->cageco, true) == 0) {
2049                                                         curv = kfv;
2050                                                         curdis_sq = dis_sq;
2051                                                 }
2052                                         }
2053                                         else {
2054                                                 curv = kfv;
2055                                                 curdis_sq = dis_sq;
2056                                         }
2057                                 }
2058                         }
2059                 }
2060
2061                 if (!kcd->ignore_vert_snapping || !(curv && curv->v)) {
2062                         if (fptr)
2063                                 *fptr = f;
2064
2065                         if (curv) {
2066                                 copy_v3_v3(p, curv->co);
2067                                 copy_v3_v3(cagep, curv->cageco);
2068
2069                                 /* update mouse coordinates to the snapped-to vertex's screen coordinates
2070                                  * this is important for angle snap, which uses the previous mouse position */
2071                                 kcd->curr.mval[0] = curv->sco[0];
2072                                 kcd->curr.mval[1] = curv->sco[1];
2073                         }
2074
2075                         return curv;
2076                 }
2077                 else {
2078                         if (fptr)
2079                                 *fptr = f;
2080
2081                         return NULL;
2082                 }
2083         }
2084
2085         if (fptr)
2086                 *fptr = NULL;
2087
2088         return NULL;
2089 }
2090
2091 /* update both kcd->curr.mval and kcd->mval to snap to required angle */
2092 static bool knife_snap_angle(KnifeTool_OpData *kcd)
2093 {
2094         float dx, dy;
2095         float w, abs_tan;
2096
2097         dx = kcd->curr.mval[0] - kcd->prev.mval[0];
2098         dy = kcd->curr.mval[1] - kcd->prev.mval[1];
2099         if (dx == 0.0f && dy == 0.0f)
2100                 return false;
2101
2102         if (dx == 0.0f) {
2103                 kcd->angle_snapping = ANGLE_90;
2104                 kcd->curr.mval[0] = kcd->prev.mval[0];
2105         }
2106
2107         w = dy / dx;
2108         abs_tan = fabsf(w);
2109         if (abs_tan <= 0.4142f) { /* tan(22.5 degrees) = 0.4142 */
2110                 kcd->angle_snapping = ANGLE_0;
2111                 kcd->curr.mval[1] = kcd->prev.mval[1];
2112         }
2113         else if (abs_tan < 2.4142f) { /* tan(67.5 degrees) = 2.4142 */
2114                 if (w > 0) {
2115                         kcd->angle_snapping = ANGLE_45;
2116                         kcd->curr.mval[1] = kcd->prev.mval[1] + dx;
2117                 }
2118                 else {
2119                         kcd->angle_snapping = ANGLE_135;
2120                         kcd->curr.mval[1] = kcd->prev.mval[1] - dx;
2121                 }
2122         }
2123         else {
2124                 kcd->angle_snapping = ANGLE_90;
2125                 kcd->curr.mval[0] = kcd->prev.mval[0];
2126         }
2127
2128         copy_v2_v2(kcd->mval, kcd->curr.mval);
2129
2130         return true;
2131 }
2132
2133 /* update active knife edge/vert pointers */
2134 static int knife_update_active(KnifeTool_OpData *kcd)
2135 {
2136         knife_pos_data_clear(&kcd->curr);
2137         copy_v2_v2(kcd->curr.mval, kcd->mval);
2138
2139         /* view matrix may have changed, reproject */
2140         knife_project_v2(kcd, kcd->prev.cage, kcd->prev.mval);
2141
2142         if (kcd->angle_snapping != ANGLE_FREE && kcd->mode == MODE_DRAGGING) {
2143                 kcd->is_angle_snapping = knife_snap_angle(kcd);
2144         }
2145         else {
2146                 kcd->is_angle_snapping = false;
2147         }
2148
2149         kcd->curr.vert = knife_find_closest_vert(kcd, kcd->curr.co, kcd->curr.cage, &kcd->curr.bmface, &kcd->curr.is_space);
2150
2151         if (!kcd->curr.vert &&
2152             /* no edge snapping while dragging (edges are too sticky when cuts are immediate) */
2153             !kcd->is_drag_hold)
2154         {
2155                 kcd->curr.edge = knife_find_closest_edge(kcd, kcd->curr.co, kcd->curr.cage,
2156                                                          &kcd->curr.bmface, &kcd->curr.is_space);
2157         }
2158
2159         /* if no hits are found this would normally default to (0, 0, 0) so instead
2160          * get a point at the mouse ray closest to the previous point.
2161          * Note that drawing lines in `free-space` isn't properly supported
2162          * but theres no guarantee (0, 0, 0) has any geometry either - campbell */
2163         if (kcd->curr.vert == NULL && kcd->curr.edge == NULL && kcd->curr.bmface == NULL) {
2164                 float origin[3];
2165                 float origin_ofs[3];
2166
2167                 knife_input_ray_segment(kcd, kcd->curr.mval, 1.0f, origin, origin_ofs);
2168
2169                 if (!isect_line_plane_v3(kcd->curr.cage, origin, origin_ofs, kcd->prev.cage, kcd->proj_zaxis)) {
2170                         copy_v3_v3(kcd->curr.cage, kcd->prev.cage);
2171
2172                         /* should never fail! */
2173                         BLI_assert(0);
2174                 }
2175         }
2176
2177         if (kcd->mode == MODE_DRAGGING) {
2178                 knife_find_line_hits(kcd);
2179         }
2180         return 1;
2181 }
2182
2183 static int sort_verts_by_dist_cb(void *co_p, const void *cur_a_p, const void *cur_b_p)
2184 {
2185         const KnifeVert *cur_a = ((const Ref *)cur_a_p)->ref;
2186         const KnifeVert *cur_b = ((const Ref *)cur_b_p)->ref;
2187         const float *co = co_p;
2188         const float a_sq = len_squared_v3v3(co, cur_a->co);
2189         const float b_sq = len_squared_v3v3(co, cur_b->co);
2190
2191         if      (a_sq < b_sq) return -1;
2192         else if (a_sq > b_sq) return  1;
2193         else                  return  0;
2194 }
2195
2196 /* The chain so far goes from an instantiated vertex to kfv (some may be reversed).
2197  * If possible, complete the chain to another instantiated vertex and return 1, else return 0.
2198  * The visited hash says which KnifeVert's have already been tried, not including kfv. */
2199 static bool find_chain_search(KnifeTool_OpData *kcd, KnifeVert *kfv, ListBase *fedges, SmallHash *visited,
2200                               ListBase *chain)
2201 {
2202         Ref *r;
2203         KnifeEdge *kfe;
2204         KnifeVert *kfv_other;
2205
2206         if (kfv->v)
2207                 return true;
2208
2209         BLI_smallhash_insert(visited, (uintptr_t)kfv, NULL);
2210         /* Try all possible next edges. Could either go through fedges
2211          * (all the KnifeEdges for the face being cut) or could go through
2212          * kve->edges and restrict to cutting face and uninstantiated edges.
2213          * Not clear which is better. Let's do the first. */
2214         for (r = fedges->first; r; r = r->next) {
2215                 kfe = r->ref;
2216                 kfv_other = NULL;
2217                 if (kfe->v1 == kfv)
2218                         kfv_other = kfe->v2;
2219                 else if (kfe->v2 == kfv)
2220                         kfv_other = kfe->v1;
2221                 if (kfv_other && !BLI_smallhash_haskey(visited, (uintptr_t)kfv_other)) {
2222                         knife_append_list(kcd, chain, kfe);
2223                         if (find_chain_search(kcd, kfv_other, fedges, visited, chain))
2224                                 return true;
2225                         BLI_remlink(chain, chain->last);
2226                 }
2227         }
2228         return false;
2229 }
2230
2231 static ListBase *find_chain_from_vertex(KnifeTool_OpData *kcd, KnifeEdge *kfe, BMVert *v, ListBase *fedges)
2232 {
2233         SmallHash visited_, *visited = &visited_;
2234         ListBase *ans;
2235         bool found;
2236
2237         ans = knife_empty_list(kcd);
2238         knife_append_list(kcd, ans, kfe);
2239         found = false;
2240         BLI_smallhash_init(visited);
2241         if (kfe->v1->v == v) {
2242                 BLI_smallhash_insert(visited, (uintptr_t)(kfe->v1), NULL);
2243                 found = find_chain_search(kcd, kfe->v2, fedges, visited, ans);
2244         }
2245         else {
2246                 BLI_assert(kfe->v2->v == v);
2247                 BLI_smallhash_insert(visited, (uintptr_t)(kfe->v2), NULL);
2248                 found = find_chain_search(kcd, kfe->v1, fedges, visited, ans);
2249         }
2250
2251         BLI_smallhash_release(visited);
2252
2253         if (found)
2254                 return ans;
2255         else
2256                 return NULL;
2257 }
2258
2259 /* Find a chain in fedges from one instantiated vertex to another.
2260  * Remove the edges in the chain from fedges and return a separate list of the chain. */
2261 static ListBase *find_chain(KnifeTool_OpData *kcd, ListBase *fedges)
2262 {
2263         Ref *r, *ref;
2264         KnifeEdge *kfe;
2265         BMVert *v1, *v2;
2266         ListBase *ans;
2267
2268         ans = NULL;
2269
2270         for (r = fedges->first; r; r = r->next) {
2271                 kfe = r->ref;
2272                 v1 = kfe->v1->v;
2273                 v2 = kfe->v2->v;
2274                 if (v1 && v2) {
2275                         ans = knife_empty_list(kcd);
2276                         knife_append_list(kcd, ans, kfe);
2277                         break;
2278                 }
2279                 if (v1)
2280                         ans = find_chain_from_vertex(kcd, kfe, v1, fedges);
2281                 else if (v2)
2282                         ans = find_chain_from_vertex(kcd, kfe, v2, fedges);
2283                 if (ans)
2284                         break;
2285         }
2286         if (ans) {
2287                 BLI_assert(!BLI_listbase_is_empty(ans));
2288                 for (r = ans->first; r; r = r->next) {
2289                         ref = find_ref(fedges, r->ref);
2290                         BLI_assert(ref != NULL);
2291                         BLI_remlink(fedges, ref);
2292                 }
2293         }
2294         return ans;
2295 }
2296
2297 /* The hole so far goes from kfvfirst to kfv (some may be reversed).
2298  * If possible, complete the hole back to kfvfirst and return 1, else return 0.
2299  * The visited hash says which KnifeVert's have already been tried, not including kfv or kfvfirst. */
2300 static bool find_hole_search(KnifeTool_OpData *kcd, KnifeVert *kfvfirst, KnifeVert *kfv, ListBase *fedges,
2301                              SmallHash *visited, ListBase *hole)
2302 {
2303         Ref *r;
2304         KnifeEdge *kfe, *kfelast;
2305         KnifeVert *kfv_other;
2306
2307         if (kfv == kfvfirst)
2308                 return true;
2309
2310         BLI_smallhash_insert(visited, (uintptr_t)kfv, NULL);
2311         kfelast = ((Ref *)hole->last)->ref;
2312         for (r = fedges->first; r; r = r->next) {
2313                 kfe = r->ref;
2314                 if (kfe == kfelast)
2315                         continue;
2316                 if (kfe->v1->v || kfe->v2->v)
2317                         continue;
2318                 kfv_other = NULL;
2319                 if (kfe->v1 == kfv)
2320                         kfv_other = kfe->v2;
2321                 else if (kfe->v2 == kfv)
2322                         kfv_other = kfe->v1;
2323                 if (kfv_other && !BLI_smallhash_haskey(visited, (uintptr_t)kfv_other)) {
2324                         knife_append_list(kcd, hole, kfe);
2325                         if (find_hole_search(kcd, kfvfirst, kfv_other, fedges, visited, hole))
2326                                 return true;
2327                         BLI_remlink(hole, hole->last);
2328                 }
2329         }
2330         return false;
2331 }
2332
2333 /* Find a hole (simple cycle with no instantiated vertices).
2334  * Remove the edges in the cycle from fedges and return a separate list of the cycle */
2335 static ListBase *find_hole(KnifeTool_OpData *kcd, ListBase *fedges)
2336 {
2337         ListBase *ans;
2338         Ref *r, *ref;
2339         KnifeEdge *kfe;
2340         SmallHash visited_, *visited = &visited_;
2341         bool found;
2342
2343         ans = NULL;
2344         found = false;
2345
2346         for (r = fedges->first; r && !found; r = r->next) {
2347                 kfe = r->ref;
2348                 if (kfe->v1->v || kfe->v2->v || kfe->v1 == kfe->v2)
2349                         continue;
2350
2351                 BLI_smallhash_init(visited);
2352                 ans = knife_empty_list(kcd);
2353                 knife_append_list(kcd, ans, kfe);
2354
2355                 found = find_hole_search(kcd, kfe->v1, kfe->v2, fedges, visited, ans);
2356
2357                 BLI_smallhash_release(visited);
2358         }
2359
2360         if (found) {
2361                 for (r = ans->first; r; r = r->next) {
2362                         kfe = r->ref;
2363                         ref = find_ref(fedges, r->ref);
2364                         if (ref)
2365                                 BLI_remlink(fedges, ref);
2366                 }
2367                 return ans;
2368         }
2369         else {
2370                 return NULL;
2371         }
2372 }
2373
2374 /* Try to find "nice" diagonals - short, and far apart from each other.
2375  * If found, return true and make a 'main chain' going across f which uses
2376  * the two diagonals and one part of the hole, and a 'side chain' that
2377  * completes the hole. */
2378 static bool find_hole_chains(KnifeTool_OpData *kcd, ListBase *hole, BMFace *f, ListBase **mainchain,
2379                              ListBase **sidechain)
2380 {
2381         float (*fco)[2], (*hco)[2];
2382         BMVert **fv;
2383         KnifeVert **hv;
2384         KnifeEdge **he;
2385         Ref *r;
2386         KnifeVert *kfv, *kfvother;
2387         KnifeEdge *kfe;
2388         ListBase *chain;
2389         BMVert *v;
2390         BMIter iter;
2391         int nh, nf, i, j, k, m, ax, ay, sep = 0 /* Quite warnings */, bestsep;
2392         int besti[2], bestj[2];
2393         float dist_sq, dist_best_sq;
2394
2395         nh = BLI_listbase_count(hole);
2396         nf = f->len;
2397         if (nh < 2 || nf < 3)
2398                 return false;
2399
2400         /* Gather 2d projections of hole and face vertex coordinates.
2401          * Use best-axis projection - not completely accurate, maybe revisit */
2402         axis_dominant_v3(&ax, &ay, f->no);
2403         hco = BLI_memarena_alloc(kcd->arena, nh * sizeof(float[2]));
2404         fco = BLI_memarena_alloc(kcd->arena, nf * sizeof(float[2]));
2405         hv = BLI_memarena_alloc(kcd->arena, nh * sizeof(KnifeVert *));
2406         fv = BLI_memarena_alloc(kcd->arena, nf * sizeof(BMVert *));
2407         he = BLI_memarena_alloc(kcd->arena, nh * sizeof(KnifeEdge *));
2408
2409         i = 0;
2410         kfv = NULL;
2411         kfvother = NULL;
2412         for (r = hole->first; r; r = r->next) {
2413                 kfe = r->ref;
2414                 he[i] = kfe;
2415                 if (kfvother == NULL) {
2416                         kfv = kfe->v1;
2417                 }
2418                 else {
2419                         kfv = kfvother;
2420                         BLI_assert(kfv == kfe->v1 || kfv == kfe->v2);
2421                 }
2422                 hco[i][0] = kfv->co[ax];
2423                 hco[i][1] = kfv->co[ay];
2424                 hv[i] = kfv;
2425                 kfvother = (kfe->v1 == kfv) ? kfe->v2 : kfe->v1;
2426                 i++;
2427         }
2428
2429         j = 0;
2430         BM_ITER_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
2431                 fco[j][0] = v->co[ax];
2432                 fco[j][1] = v->co[ay];
2433                 fv[j] = v;
2434                 j++;
2435         }
2436
2437         /* For first diagonal  (m == 0), want shortest length.
2438          * For second diagonal (m == 1), want max separation of index of hole
2439          * vertex from the hole vertex used in the first diagonal, and from there
2440          * want the one with shortest length not to the same vertex as the first diagonal. */
2441         for (m = 0; m < 2; m++) {
2442                 besti[m] = -1;
2443                 bestj[m] = -1;
2444                 dist_best_sq = FLT_MAX;
2445                 bestsep = 0;
2446                 for (i = 0; i < nh; i++) {
2447                         if (m == 1) {
2448                                 if (i == besti[0])
2449                                         continue;
2450                                 sep = (i + nh - besti[0]) % nh;
2451                                 sep = MIN2(sep, nh - sep);
2452                                 if (sep < bestsep)
2453                                         continue;
2454                                 dist_best_sq = FLT_MAX;
2455                         }
2456                         for (j = 0; j < nf; j++) {
2457                                 bool ok;
2458
2459                                 if (m == 1 && j == bestj[0])
2460                                         continue;
2461                                 dist_sq = len_squared_v2v2(hco[i], fco[j]);
2462                                 if (dist_sq > dist_best_sq)
2463                                         continue;
2464
2465                                 ok = true;
2466                                 for (k = 0; k < nh && ok; k++) {
2467                                         if (k == i || (k + 1) % nh == i)
2468                                                 continue;
2469                                         if (isect_line_line_v2(hco[i], fco[j], hco[k], hco[(k + 1) % nh]))
2470                                                 ok = false;
2471                                 }
2472                                 if (!ok)
2473                                         continue;
2474                                 for (k = 0; k < nf && ok; k++) {
2475                                         if (k == j || (k + 1) % nf == j)
2476                                                 continue;
2477                                         if (isect_line_line_v2(hco[i], fco[j], fco[k], fco[(k + 1) % nf]))
2478                                                 ok = false;
2479                                 }
2480                                 if (ok) {
2481                                         besti[m] = i;
2482                                         bestj[m] = j;
2483                                         if (m == 1)
2484                                                 bestsep = sep;
2485                                         dist_best_sq = dist_sq;
2486                                 }
2487                         }
2488                 }
2489         }
2490
2491         if (besti[0] != -1 && besti[1] != -1) {
2492                 BLI_assert(besti[0] != besti[1] && bestj[0] != bestj[1]);
2493                 kfe = new_knife_edge(kcd);
2494                 kfe->v1 = get_bm_knife_vert(kcd, fv[bestj[0]]);
2495                 kfe->v2 = hv[besti[0]];
2496                 chain = knife_empty_list(kcd);
2497                 knife_append_list(kcd, chain, kfe);
2498                 for (i = besti[0]; i != besti[1]; i = (i + 1) % nh) {
2499                         knife_append_list(kcd, chain, he[i]);
2500                 }
2501                 kfe = new_knife_edge(kcd);
2502                 kfe->v1 = hv[besti[1]];
2503                 kfe->v2 = get_bm_knife_vert(kcd, fv[bestj[1]]);
2504                 knife_append_list(kcd, chain, kfe);
2505                 *mainchain = chain;
2506
2507                 chain = knife_empty_list(kcd);
2508                 for (i = besti[1]; i != besti[0]; i = (i + 1) % nh) {
2509                         knife_append_list(kcd, chain, he[i]);
2510                 }
2511                 *sidechain = chain;
2512
2513                 return true;
2514         }
2515         else {
2516                 return false;
2517         }
2518 }
2519
2520 static bool knife_verts_edge_in_face(KnifeVert *v1, KnifeVert *v2, BMFace *f)
2521 {
2522         bool v1_inside, v2_inside;
2523         bool v1_inface, v2_inface;
2524         BMLoop *l1, *l2;
2525
2526         if (!f || !v1 || !v2)
2527                 return false;
2528
2529         l1 = v1->v ? BM_face_vert_share_loop(f, v1->v) : NULL;
2530         l2 = v2->v ? BM_face_vert_share_loop(f, v2->v) : NULL;
2531
2532         if ((l1 && l2) && BM_loop_is_adjacent(l1, l2)) {
2533                 /* boundary-case, always false to avoid edge-in-face checks below */
2534                 return false;
2535         }
2536
2537         /* find out if v1 and v2, if set, are part of the face */
2538         v1_inface = (l1 != NULL);
2539         v2_inface = (l2 != NULL);
2540
2541         /* BM_face_point_inside_test uses best-axis projection so this isn't most accurate test... */
2542         v1_inside = v1_inface ? false : BM_face_point_inside_test(f, v1->co);
2543         v2_inside = v2_inface ? false : BM_face_point_inside_test(f, v2->co);
2544         if ((v1_inface && v2_inside) ||
2545             (v2_inface && v1_inside) ||
2546             (v1_inside && v2_inside))
2547         {
2548                 return true;
2549         }
2550
2551         if (v1_inface && v2_inface) {
2552                 float mid[3];
2553                 /* Can have case where v1 and v2 are on shared chain between two faces.
2554                  * BM_face_splits_check_legal does visibility and self-intersection tests,
2555                  * but it is expensive and maybe a bit buggy, so use a simple
2556                  * "is the midpoint in the face" test */
2557                 mid_v3_v3v3(mid, v1->co, v2->co);
2558                 return BM_face_point_inside_test(f, mid);
2559         }
2560         return false;
2561 }
2562
2563 static bool knife_edge_in_face(KnifeEdge *kfe, BMFace *f)
2564 {
2565         return knife_verts_edge_in_face(kfe->v1, kfe->v2, f);
2566 }
2567
2568 /* Split face f with KnifeEdges on chain.  f remains as one side, the face formed is put in *newface.
2569  * The new face will be on the left side of the chain as viewed from the normal-out side of f. */
2570 static void knife_make_chain_cut(KnifeTool_OpData *kcd, BMFace *f, ListBase *chain, BMFace **r_f_new)
2571 {
2572         BMesh *bm = kcd->em->bm;
2573         KnifeEdge *kfe, *kfelast;
2574         BMVert *v1, *v2;
2575         BMLoop *l_v1, *l_v2;
2576         BMFace *f_new;
2577         Ref *ref;
2578         KnifeVert *kfv, *kfvprev;
2579         BMLoop *l_new, *l_iter;
2580         int i;
2581         int nco = BLI_listbase_count(chain) - 1;
2582         float (*cos)[3] = BLI_array_alloca(cos, nco);
2583         KnifeVert **kverts = BLI_array_alloca(kverts, nco);
2584
2585         kfe = ((Ref *)chain->first)->ref;
2586         v1 = kfe->v1->v ? kfe->v1->v : kfe->v2->v;
2587         kfelast = ((Ref *)chain->last)->ref;
2588         v2 = kfelast->v2->v ? kfelast->v2->v : kfelast->v1->v;
2589         BLI_assert(v1 != NULL && v2 != NULL);
2590         kfvprev = kfe->v1->v == v1 ? kfe->v1 : kfe->v2;
2591         for (ref = chain->first, i = 0; i < nco && ref != chain->last; ref = ref->next, i++) {
2592                 kfe = ref->ref;
2593                 BLI_assert(kfvprev == kfe->v1 || kfvprev == kfe->v2);
2594                 kfv = kfe->v1 == kfvprev ? kfe->v2 : kfe->v1;
2595                 copy_v3_v3(cos[i], kfv->co);
2596                 kverts[i] = kfv;
2597                 kfvprev = kfv;
2598         }
2599         BLI_assert(i == nco);
2600         l_new = NULL;
2601
2602         if ((l_v1 = BM_face_vert_share_loop(f, v1)) &&
2603             (l_v2 = BM_face_vert_share_loop(f, v2)))
2604         {
2605                 if (nco == 0) {
2606                         /* Want to prevent creating two-sided polygons */
2607                         if (v1 == v2 || BM_edge_exists(v1, v2)) {
2608                                 f_new = NULL;
2609                         }
2610                         else {
2611                                 f_new = BM_face_split(bm, f, l_v1, l_v2, &l_new, NULL, true);
2612                         }
2613                 }
2614                 else {
2615                         f_new = BM_face_split_n(bm, f, l_v1, l_v2, cos, nco, &l_new, NULL);
2616                         if (f_new) {
2617                                 /* Now go through lnew chain matching up chain kv's and assign real v's to them */
2618                                 for (l_iter = l_new->next, i = 0; i < nco; l_iter = l_iter->next, i++) {
2619                                         BLI_assert(equals_v3v3(cos[i], l_iter->v->co));
2620                                         if (kcd->select_result) {
2621                                                 BM_edge_select_set(bm, l_iter->e, true);
2622                                         }
2623                                         kverts[i]->v = l_iter->v;
2624                                 }
2625                         }
2626                 }
2627         }
2628         else {
2629                 f_new = NULL;
2630         }
2631
2632         /* the select chain above doesnt account for the first loop */
2633         if (kcd->select_result) {
2634                 if (l_new) {
2635                         BM_edge_select_set(bm, l_new->e, true);
2636                 }
2637         }
2638         else if (f_new) {
2639                 BM_elem_select_copy(bm, bm, f_new, f);
2640         }
2641
2642         *r_f_new = f_new;
2643 }
2644
2645 static void knife_make_face_cuts(KnifeTool_OpData *kcd, BMFace *f, ListBase *kfedges)
2646 {
2647         BMesh *bm = kcd->em->bm;
2648         KnifeEdge *kfe;
2649         BMFace *fnew, *fnew2, *fhole;
2650         ListBase *chain, *hole, *sidechain;
2651         Ref *ref, *refnext;
2652         int count, oldcount;
2653
2654         oldcount = BLI_listbase_count(kfedges);
2655         while ((chain = find_chain(kcd, kfedges)) != NULL) {
2656                 ListBase fnew_kfedges;
2657                 knife_make_chain_cut(kcd, f, chain, &fnew);
2658                 if (!fnew) {
2659                         return;
2660                 }
2661
2662                 /* Move kfedges to fnew_kfedges if they are now in fnew.
2663                  * The chain edges were removed already */
2664                 BLI_listbase_clear(&fnew_kfedges);
2665                 for (ref = kfedges->first; ref; ref = refnext) {
2666                         kfe = ref->ref;
2667                         refnext = ref->next;
2668                         if (knife_edge_in_face(kfe, fnew)) {
2669                                 BLI_remlink(kfedges, ref);
2670                                 kfe->basef = fnew;
2671                                 BLI_addtail(&fnew_kfedges, ref);
2672                         }
2673                         else if (!knife_edge_in_face(kfe, f)) {
2674                                 /* Concave ngon's - this edge might not be in either faces, T41730 */
2675                                 BLI_remlink(kfedges, ref);
2676                         }
2677                 }
2678                 if (fnew_kfedges.first)
2679                         knife_make_face_cuts(kcd, fnew, &fnew_kfedges);
2680
2681                 /* find_chain should always remove edges if it returns true,
2682                  * but guard against infinite loop anyway */
2683                 count = BLI_listbase_count(kfedges);
2684                 if (count >= oldcount) {
2685                         BLI_assert(!"knife find_chain infinite loop");
2686                         return;
2687                 }
2688                 oldcount = count;
2689         }
2690
2691         while ((hole = find_hole(kcd, kfedges)) != NULL) {
2692                 if (find_hole_chains(kcd, hole, f, &chain, &sidechain)) {
2693                         ListBase fnew_kfedges, fnew2_kfedges;
2694
2695                         /* chain goes across f and sidechain comes back
2696                          * from the second last vertex to the second vertex.
2697                          */
2698                         knife_make_chain_cut(kcd, f, chain, &fnew);
2699                         if (!fnew) {
2700                                 BLI_assert(!"knife failed hole cut");
2701                                 return;
2702                         }
2703                         kfe = ((Ref *)sidechain->first)->ref;
2704                         if (knife_edge_in_face(kfe, f)) {
2705                                 knife_make_chain_cut(kcd, f, sidechain, &fnew2);
2706                                 if (fnew2 == NULL) {
2707                                         return;
2708                                 }
2709                                 fhole = f;
2710                         }
2711                         else if (knife_edge_in_face(kfe, fnew)) {
2712                                 knife_make_chain_cut(kcd, fnew, sidechain, &fnew2);
2713                                 if (fnew2 == NULL) {
2714                                         return;
2715                                 }
2716                                 fhole = fnew2;
2717                         }
2718                         else {
2719                                 /* shouldn't happen except in funny edge cases */
2720                                 return;
2721                         }
2722                         BM_face_kill(bm, fhole);
2723                         /* Move kfedges to either fnew or fnew2 if appropriate.
2724                          * The hole edges were removed already */
2725                         BLI_listbase_clear(&fnew_kfedges);
2726                         BLI_listbase_clear(&fnew2_kfedges);
2727                         for (ref = kfedges->first; ref; ref = refnext) {
2728                                 kfe = ref->ref;
2729                                 refnext = ref->next;
2730                                 if (knife_edge_in_face(kfe, fnew)) {
2731                                         BLI_remlink(kfedges, ref);
2732                                         kfe->basef = fnew;
2733                                         BLI_addtail(&fnew_kfedges, ref);
2734                                 }
2735                                 else if (knife_edge_in_face(kfe, fnew2)) {
2736                                         BLI_remlink(kfedges, ref);
2737                                         kfe->basef = fnew2;
2738                                         BLI_addtail(&fnew2_kfedges, ref);
2739                                 }
2740                         }
2741                         /* We'll skip knife edges that are in the newly formed hole.
2742                          * (Maybe we shouldn't have made a hole in the first place?) */
2743                         if (fnew != fhole && fnew_kfedges.first)
2744                                 knife_make_face_cuts(kcd, fnew, &fnew_kfedges);
2745                         if (fnew2 != fhole && fnew2_kfedges.first)
2746                                 knife_make_face_cuts(kcd, fnew2, &fnew2_kfedges);
2747                         if (f == fhole)
2748                                 break;
2749                         /* find_hole should always remove edges if it returns true,
2750                          * but guard against infinite loop anyway */
2751                         count = BLI_listbase_count(kfedges);
2752                         if (count >= oldcount) {
2753                                 BLI_assert(!"knife find_hole infinite loop");
2754                                 return;
2755                         }
2756                         oldcount = count;
2757                 }
2758         }
2759 }
2760
2761 /* Use the network of KnifeEdges and KnifeVerts accumulated to make real BMVerts and BMEdedges */
2762 static void knife_make_cuts(KnifeTool_OpData *kcd)
2763 {
2764         BMesh *bm = kcd->em->bm;
2765         KnifeEdge *kfe;
2766         KnifeVert *kfv;
2767         BMFace *f;
2768         BMEdge *e, *enew;
2769         ListBase *lst;
2770         Ref *ref;
2771         float pct;
2772         SmallHashIter hiter;
2773         BLI_mempool_iter iter;
2774         SmallHash fhash_, *fhash = &fhash_;
2775         SmallHash ehash_, *ehash = &ehash_;
2776
2777         BLI_smallhash_init(fhash);
2778         BLI_smallhash_init(ehash);
2779
2780         /* put list of cutting edges for a face into fhash, keyed by face */
2781         BLI_mempool_iternew(kcd->kedges, &iter);
2782         for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
2783
2784                 /* select edges that lie directly on the cut */
2785                 if (kcd->select_result) {
2786                         if (kfe->e && kfe->is_cut) {
2787                                 BM_edge_select_set(bm, kfe->e, true);
2788                         }
2789                 }
2790
2791                 f = kfe->basef;
2792                 if (!f || kfe->e)
2793                         continue;
2794                 lst = BLI_smallhash_lookup(fhash, (uintptr_t)f);
2795                 if (!lst) {
2796                         lst = knife_empty_list(kcd);
2797                         BLI_smallhash_insert(fhash, (uintptr_t)f, lst);
2798                 }
2799                 knife_append_list(kcd, lst, kfe);
2800         }
2801
2802         /* put list of splitting vertices for an edge into ehash, keyed by edge */
2803         BLI_mempool_iternew(kcd->kverts, &iter);
2804         for (kfv = BLI_mempool_iterstep(&iter); kfv; kfv = BLI_mempool_iterstep(&iter)) {
2805                 if (kfv->v)
2806                         continue;  /* already have a BMVert */
2807                 for (ref = kfv->edges.first; ref; ref = ref->next) {
2808                         kfe = ref->ref;
2809                         e = kfe->e;
2810                         if (!e)
2811                                 continue;
2812                         lst = BLI_smallhash_lookup(ehash, (uintptr_t)e);
2813                         if (!lst) {
2814                                 lst = knife_empty_list(kcd);
2815                                 BLI_smallhash_insert(ehash, (uintptr_t)e, lst);
2816                         }
2817                         /* there can be more than one kfe in kfv's list with same e */
2818                         if (!find_ref(lst, kfv))
2819                                 knife_append_list(kcd, lst, kfv);
2820                 }
2821         }
2822
2823         /* split bmesh edges where needed */
2824         for (lst = BLI_smallhash_iternew(ehash, &hiter, (uintptr_t *)&e); lst;
2825              lst = BLI_smallhash_iternext(&hiter, (uintptr_t *)&e))
2826         {
2827                 BLI_listbase_sort_r(lst, e->v1->co, sort_verts_by_dist_cb);
2828
2829                 for (ref = lst->first; ref; ref = ref->next) {
2830                         kfv = ref->ref;
2831                         pct = line_point_factor_v3(kfv->co, e->v1->co, e->v2->co);
2832                         kfv->v = BM_edge_split(bm, e, e->v1, &enew, pct);
2833                 }
2834         }
2835
2836         if (kcd->only_select) {
2837                 EDBM_flag_disable_all(kcd->em, BM_ELEM_SELECT);
2838         }
2839
2840         /* do cuts for each face */
2841         for (lst = BLI_smallhash_iternew(fhash, &hiter, (uintptr_t *)&f); lst;
2842              lst = BLI_smallhash_iternext(&hiter, (uintptr_t *)&f))
2843         {
2844                 knife_make_face_cuts(kcd, f, lst);
2845         }
2846
2847         BLI_smallhash_release(fhash);
2848         BLI_smallhash_release(ehash);
2849 }
2850
2851 /* called on tool confirmation */
2852 static void knifetool_finish_ex(KnifeTool_OpData *kcd)
2853 {
2854         knife_make_cuts(kcd);
2855
2856         EDBM_selectmode_flush(kcd->em);
2857         EDBM_mesh_normals_update(kcd->em);
2858         EDBM_update_generic(kcd->em, true, true);
2859
2860         /* re-tessellating makes this invalid, dont use again by accident */
2861         knifetool_free_bmbvh(kcd);
2862 }
2863 static void knifetool_finish(wmOperator *op)
2864 {
2865         KnifeTool_OpData *kcd = op->customdata;
2866         knifetool_finish_ex(kcd);
2867 }
2868
2869 static void knife_recalc_projmat(KnifeTool_OpData *kcd)
2870 {
2871         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
2872         ED_view3d_ob_project_mat_get(kcd->ar->regiondata, kcd->ob, kcd->projmat);
2873         invert_m4_m4(kcd->projmat_inv, kcd->projmat);
2874
2875         copy_v3_v3(kcd->proj_zaxis, kcd->vc.rv3d->viewinv[2]);
2876         mul_mat3_m4_v3(kcd->ob->imat, kcd->proj_zaxis);
2877         normalize_v3(kcd->proj_zaxis);
2878
2879         kcd->is_ortho = ED_view3d_clip_range_get(kcd->vc.v3d, kcd->vc.rv3d,
2880                                                  &kcd->clipsta, &kcd->clipend, true);
2881 }
2882
2883 /* called when modal loop selection is done... */
2884 static void knifetool_exit_ex(bContext *C, KnifeTool_OpData *kcd)
2885 {
2886         if (!kcd)
2887                 return;
2888
2889         if (kcd->is_interactive) {
2890                 WM_cursor_modal_restore(CTX_wm_window(C));
2891
2892                 /* deactivate the extra drawing stuff in 3D-View */
2893                 ED_region_draw_cb_exit(kcd->ar->type, kcd->draw_handle);
2894         }
2895
2896         /* free the custom data */
2897         BLI_mempool_destroy(kcd->refs);
2898         BLI_mempool_destroy(kcd->kverts);
2899         BLI_mempool_destroy(kcd->kedges);
2900
2901         BLI_ghash_free(kcd->origedgemap, NULL, NULL);
2902         BLI_ghash_free(kcd->origvertmap, NULL, NULL);
2903         BLI_ghash_free(kcd->kedgefacemap, NULL, NULL);
2904         BLI_ghash_free(kcd->facetrimap, NULL, NULL);
2905
2906         BLI_memarena_free(kcd->arena);
2907
2908         /* tag for redraw */
2909         ED_region_tag_redraw(kcd->ar);
2910
2911         knifetool_free_bmbvh(kcd);
2912
2913         if (kcd->linehits)
2914                 MEM_freeN(kcd->linehits);
2915
2916         /* destroy kcd itself */
2917         MEM_freeN(kcd);
2918 }
2919 static void knifetool_exit(bContext *C, wmOperator *op)
2920 {
2921         KnifeTool_OpData *kcd = op->customdata;
2922         knifetool_exit_ex(C, kcd);
2923         op->customdata = NULL;
2924 }
2925
2926 static void knifetool_update_mval(KnifeTool_OpData *kcd, const float mval[2])
2927 {
2928         knife_recalc_projmat(kcd);
2929         copy_v2_v2(kcd->mval, mval);
2930
2931         if (knife_update_active(kcd)) {
2932                 ED_region_tag_redraw(kcd->ar);
2933         }
2934 }
2935
2936 static void knifetool_update_mval_i(KnifeTool_OpData *kcd, const int mval_i[2])
2937 {
2938         float mval[2] = {UNPACK2(mval_i)};
2939         knifetool_update_mval(kcd, mval);
2940 }
2941
2942 static void knifetool_init_bmbvh(KnifeTool_OpData *kcd)
2943 {
2944         BM_mesh_elem_index_ensure(kcd->em->bm, BM_VERT);
2945
2946         kcd->cagecos = (const float (*)[3])BKE_editmesh_vertexCos_get(kcd->em, kcd->scene, NULL);
2947
2948         kcd->bmbvh = BKE_bmbvh_new_from_editmesh(
2949                 kcd->em,
2950                 BMBVH_RETURN_ORIG |
2951                 ((kcd->only_select && kcd->cut_through) ? BMBVH_RESPECT_SELECT : BMBVH_RESPECT_HIDDEN),
2952                 kcd->cagecos, false);
2953 }
2954
2955 static void knifetool_free_bmbvh(KnifeTool_OpData *kcd)
2956 {
2957         if (kcd->bmbvh) {
2958                 BKE_bmbvh_free(kcd->bmbvh);
2959                 kcd->bmbvh = NULL;
2960         }
2961
2962         if (kcd->cagecos) {
2963                 MEM_freeN((void *)kcd->cagecos);
2964                 kcd->cagecos = NULL;
2965         }
2966 }
2967
2968 /* called when modal loop selection gets set up... */
2969 static void knifetool_init(bContext *C, KnifeTool_OpData *kcd,
2970                            const bool only_select, const bool cut_through, const bool is_interactive)
2971 {
2972         Scene *scene = CTX_data_scene(C);
2973         Object *obedit = CTX_data_edit_object(C);
2974
2975         /* assign the drawing handle for drawing preview line... */
2976         kcd->scene = scene;
2977         kcd->ob = obedit;
2978         kcd->ar = CTX_wm_region(C);
2979
2980         em_setup_viewcontext(C, &kcd->vc);
2981
2982         kcd->em = BKE_editmesh_from_object(kcd->ob);
2983
2984         /* cut all the way through the mesh if use_occlude_geometry button not pushed */
2985         kcd->is_interactive = is_interactive;
2986         kcd->cut_through = cut_through;
2987         kcd->only_select = only_select;
2988
2989         knifetool_init_bmbvh(kcd);
2990
2991         kcd->arena = BLI_memarena_new(MEM_SIZE_OPTIMAL(1 << 15), "knife");
2992         kcd->vthresh = KMAXDIST - 1;
2993         kcd->ethresh = KMAXDIST;
2994
2995         knife_recalc_projmat(kcd);
2996
2997         ED_region_tag_redraw(kcd->ar);
2998
2999         kcd->refs = BLI_mempool_create(sizeof(Ref), 0, 2048, 0);
3000         kcd->kverts = BLI_mempool_create(sizeof(KnifeVert), 0, 512, BLI_MEMPOOL_ALLOW_ITER);
3001         kcd->kedges = BLI_mempool_create(sizeof(KnifeEdge), 0, 512, BLI_MEMPOOL_ALLOW_ITER);
3002
3003         kcd->origedgemap = BLI_ghash_ptr_new("knife origedgemap");
3004         kcd->origvertmap = BLI_ghash_ptr_new("knife origvertmap");
3005         kcd->kedgefacemap = BLI_ghash_ptr_new("knife kedgefacemap");
3006         kcd->facetrimap = BLI_ghash_ptr_new("knife facetrimap");
3007
3008         /* can't usefully select resulting edges in face mode */
3009         kcd->select_result = (kcd->em->selectmode != SCE_SELECT_FACE);
3010
3011         knife_pos_data_clear(&kcd->curr);
3012         knife_pos_data_clear(&kcd->prev);
3013
3014         if (is_interactive) {
3015                 kcd->draw_handle = ED_region_draw_cb_activate(kcd->ar->type, knifetool_draw, kcd, REGION_DRAW_POST_VIEW);
3016
3017                 knife_init_colors(&kcd->colors);
3018         }
3019 }
3020
3021 static void knifetool_cancel(bContext *C, wmOperator *op)
3022 {
3023         /* this is just a wrapper around exit() */
3024         knifetool_exit(C, op);
3025 }
3026
3027 static int knifetool_invoke(bContext *C, wmOperator *op, const wmEvent *event)
3028 {
3029         const bool only_select = RNA_boolean_get(op->ptr, "only_selected");
3030         const bool cut_through = !RNA_boolean_get(op->ptr, "use_occlude_geometry");
3031
3032         KnifeTool_OpData *kcd;
3033
3034         if (only_select) {
3035                 Object *obedit = CTX_data_edit_object(C);
3036                 BMEditMesh *em = BKE_editmesh_from_object(obedit);
3037                 if (em->bm->totfacesel == 0) {
3038                         BKE_report(op->reports, RPT_ERROR, "Selected faces required");
3039                         return OPERATOR_CANCELLED;
3040                 }
3041         }
3042
3043         view3d_operator_needs_opengl(C);
3044
3045         /* alloc new customdata */
3046         kcd = op->customdata = MEM_callocN(sizeof(KnifeTool_OpData), __func__);
3047
3048         knifetool_init(C, kcd, only_select, cut_through, true);
3049
3050         /* add a modal handler for this operator - handles loop selection */
3051         WM_cursor_modal_set(CTX_wm_window(C), BC_KNIFECURSOR);
3052         WM_event_add_modal_handler(C, op);
3053
3054         knifetool_update_mval_i(kcd, event->mval);
3055
3056         knife_update_header(C, kcd);
3057
3058         return OPERATOR_RUNNING_MODAL;
3059 }
3060
3061 enum {
3062         KNF_MODAL_CANCEL = 1,
3063         KNF_MODAL_CONFIRM,
3064         KNF_MODAL_MIDPOINT_ON,
3065         KNF_MODAL_MIDPOINT_OFF,
3066         KNF_MODAL_NEW_CUT,
3067         KNF_MODEL_IGNORE_SNAP_ON,
3068         KNF_MODEL_IGNORE_SNAP_OFF,
3069         KNF_MODAL_ADD_CUT,
3070         KNF_MODAL_ANGLE_SNAP_TOGGLE,
3071         KNF_MODAL_CUT_THROUGH_TOGGLE,
3072         KNF_MODAL_PANNING,
3073         KNF_MODAL_ADD_CUT_CLOSED,
3074 };
3075
3076 wmKeyMap *knifetool_modal_keymap(wmKeyConfig *keyconf)
3077 {
3078         static EnumPropertyItem modal_items[] = {
3079                 {KNF_MODAL_CANCEL, "CANCEL", 0, "Cancel", ""},
3080                 {KNF_MODAL_CONFIRM, "CONFIRM", 0, "Confirm", ""},
3081                 {KNF_MODAL_MIDPOINT_ON, "SNAP_MIDPOINTS_ON", 0, "Snap To Midpoints On", ""},
3082                 {KNF_MODAL_MIDPOINT_OFF, "SNAP_MIDPOINTS_OFF", 0, "Snap To Midpoints Off", ""},
3083                 {KNF_MODEL_IGNORE_SNAP_ON, "IGNORE_SNAP_ON", 0, "Ignore Snapping On", ""},
3084                 {KNF_MODEL_IGNORE_SNAP_OFF, "IGNORE_SNAP_OFF", 0, "Ignore Snapping Off", ""},
3085                 {KNF_MODAL_ANGLE_SNAP_TOGGLE, "ANGLE_SNAP_TOGGLE", 0, "Toggle Angle Snapping", ""},
3086                 {KNF_MODAL_CUT_THROUGH_TOGGLE, "CUT_THROUGH_TOGGLE", 0, "Toggle Cut Through", ""},
3087                 {KNF_MODAL_NEW_CUT, "NEW_CUT", 0, "End Current Cut", ""},
3088            &nbs