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