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