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