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