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