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