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