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