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