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