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