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