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