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