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