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