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