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