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