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