Correct own error in knife edge-net cutting
[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         vert_tol = KNIFE_FLT_EPS_PX_VERT;
1625         line_tol = KNIFE_FLT_EPS_PX_EDGE;
1626         face_tol = KNIFE_FLT_EPS_PX_FACE;
1627
1628         vert_tol_sq = vert_tol * vert_tol;
1629         line_tol_sq = line_tol * line_tol;
1630         face_tol_sq = face_tol * face_tol;
1631
1632         /* Assume these tolerances swamp floating point rounding errors in calculations below */
1633
1634         /* first look for vertex hits */
1635         for (val_p = BLI_smallhash_iternew_p(&kfvs, &hiter, (uintptr_t *)&v); val_p;
1636              val_p = BLI_smallhash_iternext_p(&hiter, (uintptr_t *)&v))
1637         {
1638                 KnifeEdge *kfe_hit = NULL;
1639
1640                 knife_project_v2(kcd, v->cageco, s);
1641                 d = dist_squared_to_line_segment_v2(s, s1, s2);
1642                 if ((d <= vert_tol_sq) &&
1643                     (point_is_visible(kcd, v->cageco, s, &mats, bm_elem_from_knife_vert(v, &kfe_hit))))
1644                 {
1645                         memset(&hit, 0, sizeof(hit));
1646                         hit.v = v;
1647
1648                         /* If this isn't from an existing BMVert, it may have been added to a BMEdge originally.
1649                                  * knowing if the hit comes from an edge is important for edge-in-face checks later on
1650                                  * see: #knife_add_single_cut -> #knife_verts_edge_in_face, T42611 */
1651                         if (kfe_hit) {
1652                                 hit.kfe = kfe_hit;
1653                         }
1654
1655                         copy_v3_v3(hit.hit, v->co);
1656                         copy_v3_v3(hit.cagehit, v->cageco);
1657                         copy_v2_v2(hit.schit, s);
1658                         set_linehit_depth(kcd, &hit);
1659                         BLI_array_append(linehits, hit);
1660                 }
1661                 else {
1662                         /* note that these vertes aren't used */
1663                         *val_p = NULL;
1664                 }
1665         }
1666
1667         /* now edge hits; don't add if a vertex at end of edge should have hit */
1668         for (val = BLI_smallhash_iternew(&kfes, &hiter, (uintptr_t *)&kfe); val;
1669              val = BLI_smallhash_iternext(&hiter, (uintptr_t *)&kfe))
1670         {
1671                 int kfe_verts_in_cut;
1672                 /* if we intersect both verts, don't attempt to intersect the edge */
1673
1674                 kfe_verts_in_cut = (BLI_smallhash_lookup(&kfvs, (intptr_t)kfe->v1) != NULL) +
1675                                    (BLI_smallhash_lookup(&kfvs, (intptr_t)kfe->v2) != NULL);
1676
1677                 if (kfe_verts_in_cut == 2) {
1678                         continue;
1679                 }
1680
1681                 knife_project_v2(kcd, kfe->v1->cageco, se1);
1682                 knife_project_v2(kcd, kfe->v2->cageco, se2);
1683                 isect_kind = (kfe_verts_in_cut) ? -1 : isect_seg_seg_v2_point(s1, s2, se1, se2, sint);
1684                 if (isect_kind == -1) {
1685                         /* isect_seg_seg_v2_simple doesn't do tolerance test around ends of s1-s2 */
1686                         closest_to_line_segment_v2(sint, s1, se1, se2);
1687                         if (len_squared_v2v2(sint, s1) <= line_tol_sq)
1688                                 isect_kind = 1;
1689                         else {
1690                                 closest_to_line_segment_v2(sint, s2, se1, se2);
1691                                 if (len_squared_v2v2(sint, s2) <= line_tol_sq)
1692                                         isect_kind = 1;
1693                         }
1694                 }
1695                 if (isect_kind == 1) {
1696                         d1 = len_v2v2(sint, se1);
1697                         d2 = len_v2v2(se2, se1);
1698                         if (!(d1 <= line_tol || d2 <= line_tol || fabsf(d1 - d2) <= line_tol)) {
1699                                 float p_cage[3], p_cage_tmp[3];
1700                                 lambda = d1 / d2;
1701                                 /* Can't just interpolate between ends of kfe because
1702                                  * that doesn't work with perspective transformation.
1703                                  * Need to find 3d intersection of ray through sint */
1704                                 knife_input_ray_segment(kcd, sint, 1.0f, r1, r2);
1705                                 isect_kind = isect_line_line_v3(kfe->v1->cageco, kfe->v2->cageco, r1, r2, p_cage, p_cage_tmp);
1706                                 if (isect_kind >= 1 && point_is_visible(kcd, p_cage, sint, &mats, bm_elem_from_knife_edge(kfe))) {
1707                                         memset(&hit, 0, sizeof(hit));
1708                                         if (kcd->snap_midpoints) {
1709                                                 /* choose intermediate point snap too */
1710                                                 mid_v3_v3v3(p_cage, kfe->v1->cageco, kfe->v2->cageco);
1711                                                 mid_v2_v2v2(sint, se1, se2);
1712                                                 lambda = 0.5f;
1713                                         }
1714                                         hit.kfe = kfe;
1715                                         transform_point_by_seg_v3(
1716                                                 hit.hit, p_cage,
1717                                                 kfe->v1->co, kfe->v2->co,
1718                                                 kfe->v1->cageco, kfe->v2->cageco);
1719                                         copy_v3_v3(hit.cagehit, p_cage);
1720                                         copy_v2_v2(hit.schit, sint);
1721                                         hit.perc = lambda;
1722                                         set_linehit_depth(kcd, &hit);
1723                                         BLI_array_append(linehits, hit);
1724                                 }
1725                         }
1726                 }
1727         }
1728         /* now face hits; don't add if a vertex or edge in face should have hit */
1729         for (val = BLI_smallhash_iternew(&faces, &hiter, (uintptr_t *)&f); val;
1730              val = BLI_smallhash_iternext(&hiter, (uintptr_t *)&f))
1731         {
1732                 float p[3], p_cage[3];
1733
1734                 if (use_hit_prev && knife_ray_intersect_face(kcd, s1, v1, v3, f, face_tol_sq, p, p_cage)) {
1735                         if (point_is_visible(kcd, p_cage, s1, &mats, (BMElem *)f)) {
1736                                 memset(&hit, 0, sizeof(hit));
1737                                 hit.f = f;
1738                                 copy_v3_v3(hit.hit, p);
1739                                 copy_v3_v3(hit.cagehit, p_cage);
1740                                 copy_v2_v2(hit.schit, s1);
1741                                 set_linehit_depth(kcd, &hit);
1742                                 BLI_array_append(linehits, hit);
1743                         }
1744                 }
1745
1746                 if (use_hit_curr && knife_ray_intersect_face(kcd, s2, v2, v4, f, face_tol_sq, p, p_cage)) {
1747                         if (point_is_visible(kcd, p_cage, s2, &mats, (BMElem *)f)) {
1748                                 memset(&hit, 0, sizeof(hit));
1749                                 hit.f = f;
1750                                 copy_v3_v3(hit.hit, p);
1751                                 copy_v3_v3(hit.cagehit, p_cage);
1752                                 copy_v2_v2(hit.schit, s2);
1753                                 set_linehit_depth(kcd, &hit);
1754                                 BLI_array_append(linehits, hit);
1755                         }
1756                 }
1757         }
1758
1759         kcd->linehits = linehits;
1760         kcd->totlinehit = BLI_array_count(linehits);
1761
1762         /* find position along screen line, used for sorting */
1763         for (i = 0; i < kcd->totlinehit; i++) {
1764                 KnifeLineHit *lh = kcd->linehits + i;
1765
1766                 lh->l = len_v2v2(lh->schit, s1) / len_v2v2(s2, s1);
1767         }
1768
1769         BLI_smallhash_release(&faces);
1770         BLI_smallhash_release(&kfes);
1771         BLI_smallhash_release(&kfvs);
1772         BLI_bvhtree_free(planetree);
1773         if (results)
1774                 MEM_freeN(results);
1775 }
1776
1777 static void knife_input_ray_segment(KnifeTool_OpData *kcd, const float mval[2], const float ofs,
1778                                     float r_origin[3], float r_origin_ofs[3])
1779 {
1780         bglMats mats;
1781
1782         bgl_get_mats(&mats);
1783
1784         /* unproject to find view ray */
1785         ED_view3d_unproject(&mats, r_origin,     mval[0], mval[1], 0.0f);
1786         ED_view3d_unproject(&mats, r_origin_ofs, mval[0], mval[1], ofs);
1787
1788         /* transform into object space */
1789         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat); 
1790
1791         mul_m4_v3(kcd->ob->imat, r_origin);
1792         mul_m4_v3(kcd->ob->imat, r_origin_ofs);
1793 }
1794
1795 static BMFace *knife_find_closest_face(KnifeTool_OpData *kcd, float co[3], float cageco[3], bool *is_space)
1796 {
1797         BMFace *f;
1798         float dist = KMAXDIST;
1799         float origin[3];
1800         float origin_ofs[3];
1801         float ray[3], ray_normal[3];
1802
1803         /* unproject to find view ray */
1804         knife_input_ray_segment(kcd, kcd->curr.mval, 1.0f, origin, origin_ofs);
1805         sub_v3_v3v3(ray, origin_ofs, origin);
1806         normalize_v3_v3(ray_normal, ray);
1807
1808         f = BKE_bmbvh_ray_cast(kcd->bmbvh, origin, ray_normal, 0.0f, NULL, co, cageco);
1809
1810         if (f && kcd->only_select && BM_elem_flag_test(f, BM_ELEM_SELECT) == 0) {
1811                 f = NULL;
1812         }
1813
1814         if (is_space)
1815                 *is_space = !f;
1816
1817         if (!f) {
1818                 if (kcd->is_interactive) {
1819                         /* try to use backbuffer selection method if ray casting failed */
1820                         f = EDBM_face_find_nearest(&kcd->vc, &dist);
1821
1822                         /* cheat for now; just put in the origin instead
1823                          * of a true coordinate on the face.
1824                          * This just puts a point 1.0f infront of the view. */
1825                         add_v3_v3v3(co, origin, ray);
1826                 }
1827         }
1828
1829         return f;
1830 }
1831
1832 /* find the 2d screen space density of vertices within a radius.  used to scale snapping
1833  * distance for picking edges/verts.*/
1834 static int knife_sample_screen_density(KnifeTool_OpData *kcd, const float radius)
1835 {
1836         BMFace *f;
1837         bool is_space;
1838         float co[3], cageco[3], sco[2];
1839
1840         BLI_assert(kcd->is_interactive == true);
1841
1842         f = knife_find_closest_face(kcd, co, cageco, &is_space);
1843
1844         if (f && !is_space) {
1845                 const float radius_sq = radius * radius;
1846                 ListBase *lst;
1847                 Ref *ref;
1848                 float dis_sq;
1849                 int c = 0;
1850
1851                 knife_project_v2(kcd, cageco, sco);
1852
1853                 lst = knife_get_face_kedges(kcd, f);
1854                 for (ref = lst->first; ref; ref = ref->next) {
1855                         KnifeEdge *kfe = ref->ref;
1856                         int i;
1857
1858                         for (i = 0; i < 2; i++) {
1859                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1860
1861                                 knife_project_v2(kcd, kfv->cageco, kfv->sco);
1862
1863                                 dis_sq = len_squared_v2v2(kfv->sco, sco);
1864                                 if (dis_sq < radius_sq) {
1865                                         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1866                                                 if (ED_view3d_clipping_test(kcd->vc.rv3d, kfv->cageco, true) == 0) {
1867                                                         c++;
1868                                                 }
1869                                         }
1870                                         else {
1871                                                 c++;
1872                                         }
1873                                 }
1874                         }
1875                 }
1876
1877                 return c;
1878         }
1879
1880         return 0;
1881 }
1882
1883 /* returns snapping distance for edges/verts, scaled by the density of the
1884  * surrounding mesh (in screen space)*/
1885 static float knife_snap_size(KnifeTool_OpData *kcd, float maxsize)
1886 {
1887         float density;
1888
1889         if (kcd->is_interactive) {
1890                 density = (float)knife_sample_screen_density(kcd, maxsize * 2.0f);
1891         }
1892         else {
1893                 density = 1.0f;
1894         }
1895
1896         if (density < 1.0f)
1897                 density = 1.0f;
1898
1899         return min_ff(maxsize / (density * 0.5f), maxsize);
1900 }
1901
1902 /* p is closest point on edge to the mouse cursor */
1903 static KnifeEdge *knife_find_closest_edge(KnifeTool_OpData *kcd, float p[3], float cagep[3],
1904                                           BMFace **fptr, bool *is_space)
1905 {
1906         BMFace *f;
1907         float co[3], cageco[3], sco[2];
1908         float maxdist = knife_snap_size(kcd, kcd->ethresh);
1909
1910         if (kcd->ignore_vert_snapping)
1911                 maxdist *= 0.5f;
1912
1913         f = knife_find_closest_face(kcd, co, cageco, NULL);
1914         *is_space = !f;
1915
1916         kcd->curr.bmface = f;
1917
1918         if (f) {
1919                 const float maxdist_sq = maxdist * maxdist;
1920                 KnifeEdge *cure = NULL;
1921                 float cur_cagep[3];
1922                 ListBase *lst;
1923                 Ref *ref;
1924                 float dis_sq, curdis_sq = FLT_MAX;
1925
1926                 /* set p to co, in case we don't find anything, means a face cut */
1927                 copy_v3_v3(p, co);
1928                 copy_v3_v3(cagep, cageco);
1929
1930                 knife_project_v2(kcd, cageco, sco);
1931
1932                 /* look through all edges associated with this face */
1933                 lst = knife_get_face_kedges(kcd, f);
1934                 for (ref = lst->first; ref; ref = ref->next) {
1935                         KnifeEdge *kfe = ref->ref;
1936                         float test_cagep[3];
1937                         float lambda;
1938
1939                         /* project edge vertices into screen space */
1940                         knife_project_v2(kcd, kfe->v1->cageco, kfe->v1->sco);
1941                         knife_project_v2(kcd, kfe->v2->cageco, kfe->v2->sco);
1942
1943                         /* check if we're close enough and calculate 'lambda' */
1944                         if (kcd->is_angle_snapping) {
1945                         /* if snapping, check we're in bounds */
1946                                 float sco_snap[2];
1947                                 isect_line_line_v2_point(kfe->v1->sco, kfe->v2->sco, kcd->prev.mval, kcd->curr.mval, sco_snap);
1948                                 lambda = line_point_factor_v2(sco_snap, kfe->v1->sco, kfe->v2->sco);
1949
1950                                 /* be strict about angle-snapping within edge */
1951                                 if ((lambda < 0.0f - KNIFE_FLT_EPSBIG) || (lambda > 1.0f + KNIFE_FLT_EPSBIG)) {
1952                                         continue;
1953                                 }
1954
1955                                 dis_sq = len_squared_v2v2(sco, sco_snap);
1956                                 if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
1957                                         /* we already have 'lambda' */
1958                                 }
1959                                 else {
1960                                         continue;
1961                                 }
1962                         }
1963                         else {
1964                                 dis_sq = dist_squared_to_line_segment_v2(sco, kfe->v1->sco, kfe->v2->sco);
1965                                 if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
1966                                         lambda = line_point_factor_v2(sco, kfe->v1->sco, kfe->v2->sco);
1967                                 }
1968                                 else {
1969                                         continue;
1970                                 }
1971                         }
1972
1973                         /* now we have 'lambda' calculated (in screen-space) */
1974                         knife_interp_v3_v3v3(kcd, test_cagep, kfe->v1->cageco, kfe->v2->cageco, lambda);
1975
1976                         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1977                                 /* check we're in the view */
1978                                 if (ED_view3d_clipping_test(kcd->vc.rv3d, test_cagep, true)) {
1979                                         continue;
1980                                 }
1981                         }
1982
1983                         cure = kfe;
1984                         curdis_sq = dis_sq;
1985                         copy_v3_v3(cur_cagep, test_cagep);
1986                 }
1987
1988                 if (fptr)
1989                         *fptr = f;
1990
1991                 if (cure) {
1992                         if (!kcd->ignore_edge_snapping || !(cure->e)) {
1993                                 KnifeVert *edgesnap = NULL;
1994
1995                                 if (kcd->snap_midpoints) {
1996                                         mid_v3_v3v3(p, cure->v1->co, cure->v2->co);
1997                                         mid_v3_v3v3(cagep, cure->v1->cageco, cure->v2->cageco);
1998                                 }
1999                                 else {
2000                                         float lambda = line_point_factor_v3(cur_cagep, cure->v1->cageco, cure->v2->cageco);
2001                                         copy_v3_v3(cagep, cur_cagep);
2002                                         interp_v3_v3v3(p, cure->v1->co, cure->v2->co, lambda);
2003                                 }
2004
2005                                 /* update mouse coordinates to the snapped-to edge's screen coordinates
2006                                  * this is important for angle snap, which uses the previous mouse position */
2007                                 edgesnap = new_knife_vert(kcd, p, cagep);
2008                                 kcd->curr.mval[0] = edgesnap->sco[0];
2009                                 kcd->curr.mval[1] = edgesnap->sco[1];
2010
2011                         }
2012                         else {
2013                                 return NULL;
2014                         }
2015                 }
2016
2017                 return cure;
2018         }
2019
2020         if (fptr)
2021                 *fptr = NULL;
2022
2023         return NULL;
2024 }
2025
2026 /* find a vertex near the mouse cursor, if it exists */
2027 static KnifeVert *knife_find_closest_vert(KnifeTool_OpData *kcd, float p[3], float cagep[3], BMFace **fptr,
2028                                           bool *is_space)
2029 {
2030         BMFace *f;
2031         float co[3], cageco[3], sco[2], maxdist = knife_snap_size(kcd, kcd->vthresh);
2032
2033         if (kcd->ignore_vert_snapping)
2034                 maxdist *= 0.5f;
2035
2036         f = knife_find_closest_face(kcd, co, cageco, is_space);
2037
2038         kcd->curr.bmface = f;
2039
2040         if (f) {
2041                 const float maxdist_sq = maxdist * maxdist;
2042                 ListBase *lst;
2043                 Ref *ref;
2044                 KnifeVert *curv = NULL;
2045                 float dis_sq, curdis_sq = FLT_MAX;
2046
2047                 /* set p to co, in case we don't find anything, means a face cut */
2048                 copy_v3_v3(p, co);
2049                 copy_v3_v3(cagep, cageco);
2050
2051                 knife_project_v2(kcd, cageco, sco);
2052
2053                 lst = knife_get_face_kedges(kcd, f);
2054                 for (ref = lst->first; ref; ref = ref->next) {
2055                         KnifeEdge *kfe = ref->ref;
2056                         int i;
2057
2058                         for (i = 0; i < 2; i++) {
2059                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
2060
2061                                 knife_project_v2(kcd, kfv->cageco, kfv->sco);
2062
2063                                 /* be strict about angle snapping, the vertex needs to be very close to the angle, or we ignore */
2064                                 if (kcd->is_angle_snapping) {
2065                                         if (dist_squared_to_line_segment_v2(kfv->sco, kcd->prev.mval, kcd->curr.mval) > KNIFE_FLT_EPSBIG) {
2066                                                 continue;
2067                                         }
2068                                 }
2069
2070                                 dis_sq = len_squared_v2v2(kfv->sco, sco);
2071                                 if (dis_sq < curdis_sq && dis_sq < maxdist_sq) {
2072                                         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
2073                                                 if (ED_view3d_clipping_test(kcd->vc.rv3d, kfv->cageco, true) == 0) {
2074                                                         curv = kfv;
2075                                                         curdis_sq = dis_sq;
2076                                                 }
2077                                         }
2078                                         else {
2079                                                 curv = kfv;
2080                                                 curdis_sq = dis_sq;
2081                                         }
2082                                 }
2083                         }
2084                 }
2085
2086                 if (!kcd->ignore_vert_snapping || !(curv && curv->v)) {
2087                         if (fptr)
2088                                 *fptr = f;
2089
2090                         if (curv) {
2091                                 copy_v3_v3(p, curv->co);
2092                                 copy_v3_v3(cagep, curv->cageco);
2093
2094                                 /* update mouse coordinates to the snapped-to vertex's screen coordinates
2095                                  * this is important for angle snap, which uses the previous mouse position */
2096                                 kcd->curr.mval[0] = curv->sco[0];
2097                                 kcd->curr.mval[1] = curv->sco[1];
2098                         }
2099
2100                         return curv;
2101                 }
2102                 else {
2103                         if (fptr)
2104                                 *fptr = f;
2105
2106                         return NULL;
2107                 }
2108         }
2109
2110         if (fptr)
2111                 *fptr = NULL;
2112
2113         return NULL;
2114 }
2115
2116 /**
2117  * Snaps a 2d vector to an angle, relative to \a v_ref.
2118  */
2119 static float snap_v2_angle(float r[2], const float v[2], const float v_ref[2], float angle_snap)
2120 {
2121         float m2[2][2];
2122         float v_unit[2];
2123         float angle, angle_delta;
2124
2125         BLI_ASSERT_UNIT_V2(v_ref);
2126
2127         normalize_v2_v2(v_unit, v);
2128         angle = angle_signed_v2v2(v_unit, v_ref);
2129         angle_delta = (roundf(angle / angle_snap) * angle_snap) - angle;
2130         rotate_m2(m2, angle_delta);
2131
2132         mul_v2_m2v2(r, m2, v);
2133         return angle + angle_delta;
2134 }
2135
2136 /* update both kcd->curr.mval and kcd->mval to snap to required angle */
2137 static bool knife_snap_angle(KnifeTool_OpData *kcd)
2138 {
2139         const float dvec_ref[2] = {0.0f, 1.0f};
2140         float dvec[2], dvec_snap[2];
2141         float snap_step = DEG2RADF(45);
2142
2143         sub_v2_v2v2(dvec, kcd->curr.mval, kcd->prev.mval);
2144         if (is_zero_v2(dvec)) {
2145                 return false;
2146         }
2147
2148         kcd->angle = snap_v2_angle(dvec_snap, dvec, dvec_ref, snap_step);
2149
2150         add_v2_v2v2(kcd->curr.mval, kcd->prev.mval, dvec_snap);
2151
2152         copy_v2_v2(kcd->mval, kcd->curr.mval);
2153
2154         return true;
2155 }
2156
2157 /* update active knife edge/vert pointers */
2158 static int knife_update_active(KnifeTool_OpData *kcd)
2159 {
2160         knife_pos_data_clear(&kcd->curr);
2161         copy_v2_v2(kcd->curr.mval, kcd->mval);
2162
2163         /* view matrix may have changed, reproject */
2164         knife_project_v2(kcd, kcd->prev.cage, kcd->prev.mval);
2165
2166         if (kcd->angle_snapping && (kcd->mode == MODE_DRAGGING)) {
2167                 kcd->is_angle_snapping = knife_snap_angle(kcd);
2168         }
2169         else {
2170                 kcd->is_angle_snapping = false;
2171         }
2172
2173         kcd->curr.vert = knife_find_closest_vert(kcd, kcd->curr.co, kcd->curr.cage, &kcd->curr.bmface, &kcd->curr.is_space);
2174
2175         if (!kcd->curr.vert &&
2176             /* no edge snapping while dragging (edges are too sticky when cuts are immediate) */
2177             !kcd->is_drag_hold)
2178         {
2179                 kcd->curr.edge = knife_find_closest_edge(kcd, kcd->curr.co, kcd->curr.cage,
2180                                                          &kcd->curr.bmface, &kcd->curr.is_space);
2181         }
2182
2183         /* if no hits are found this would normally default to (0, 0, 0) so instead
2184          * get a point at the mouse ray closest to the previous point.
2185          * Note that drawing lines in `free-space` isn't properly supported
2186          * but theres no guarantee (0, 0, 0) has any geometry either - campbell */
2187         if (kcd->curr.vert == NULL && kcd->curr.edge == NULL && kcd->curr.bmface == NULL) {
2188                 float origin[3];
2189                 float origin_ofs[3];
2190
2191                 knife_input_ray_segment(kcd, kcd->curr.mval, 1.0f, origin, origin_ofs);
2192
2193                 if (!isect_line_plane_v3(kcd->curr.cage, origin, origin_ofs, kcd->prev.cage, kcd->proj_zaxis)) {
2194                         copy_v3_v3(kcd->curr.cage, kcd->prev.cage);
2195
2196                         /* should never fail! */
2197                         BLI_assert(0);
2198                 }
2199         }
2200
2201         if (kcd->mode == MODE_DRAGGING) {
2202                 knife_find_line_hits(kcd);
2203         }
2204         return 1;
2205 }
2206
2207 static int sort_verts_by_dist_cb(void *co_p, const void *cur_a_p, const void *cur_b_p)
2208 {
2209         const KnifeVert *cur_a = ((const Ref *)cur_a_p)->ref;
2210         const KnifeVert *cur_b = ((const Ref *)cur_b_p)->ref;
2211         const float *co = co_p;
2212         const float a_sq = len_squared_v3v3(co, cur_a->co);
2213         const float b_sq = len_squared_v3v3(co, cur_b->co);
2214
2215         if      (a_sq < b_sq) return -1;
2216         else if (a_sq > b_sq) return  1;
2217         else                  return  0;
2218 }
2219
2220 static bool knife_verts_edge_in_face(KnifeVert *v1, KnifeVert *v2, BMFace *f)
2221 {
2222         bool v1_inside, v2_inside;
2223         bool v1_inface, v2_inface;
2224         BMLoop *l1, *l2;
2225
2226         if (!f || !v1 || !v2)
2227                 return false;
2228
2229         l1 = v1->v ? BM_face_vert_share_loop(f, v1->v) : NULL;
2230         l2 = v2->v ? BM_face_vert_share_loop(f, v2->v) : NULL;
2231
2232         if ((l1 && l2) && BM_loop_is_adjacent(l1, l2)) {
2233                 /* boundary-case, always false to avoid edge-in-face checks below */
2234                 return false;
2235         }
2236
2237         /* find out if v1 and v2, if set, are part of the face */
2238         v1_inface = (l1 != NULL);
2239         v2_inface = (l2 != NULL);
2240
2241         /* BM_face_point_inside_test uses best-axis projection so this isn't most accurate test... */
2242         v1_inside = v1_inface ? false : BM_face_point_inside_test(f, v1->co);
2243         v2_inside = v2_inface ? false : BM_face_point_inside_test(f, v2->co);
2244         if ((v1_inface && v2_inside) ||
2245             (v2_inface && v1_inside) ||
2246             (v1_inside && v2_inside))
2247         {
2248                 return true;
2249         }
2250
2251         if (v1_inface && v2_inface) {
2252                 float mid[3];
2253                 /* Can have case where v1 and v2 are on shared chain between two faces.
2254                  * BM_face_splits_check_legal does visibility and self-intersection tests,
2255                  * but it is expensive and maybe a bit buggy, so use a simple
2256                  * "is the midpoint in the face" test */
2257                 mid_v3_v3v3(mid, v1->co, v2->co);
2258                 return BM_face_point_inside_test(f, mid);
2259         }
2260         return false;
2261 }
2262
2263 static void knife_make_face_cuts(KnifeTool_OpData *kcd, BMFace *f, ListBase *kfedges)
2264 {
2265         BMesh *bm = kcd->em->bm;
2266         KnifeEdge *kfe;
2267         Ref *ref;
2268         int edge_array_len = BLI_listbase_count(kfedges);
2269         bool ok;
2270         int i;
2271
2272         BMFace **face_arr;
2273         int face_arr_len;
2274
2275         BMEdge **edge_array = BLI_array_alloca(edge_array, edge_array_len);
2276
2277          /* point to knife edges we've created edges in, edge_array aligned */
2278         KnifeEdge **kfe_array = BLI_array_alloca(kfe_array, edge_array_len);
2279
2280         BLI_assert(BLI_gset_size(kcd->edgenet.edge_visit) == 0);
2281
2282         i = 0;
2283         for (ref = kfedges->first; ref; ref = ref->next) {
2284                 bool is_new_edge = false;
2285                 kfe = ref->ref;
2286
2287                 if (kfe->e == NULL) {
2288                         if (kfe->v1->v && kfe->v2->v) {
2289                                 kfe->e = BM_edge_exists(kfe->v1->v, kfe->v2->v);
2290                         }
2291                 }
2292
2293                 if (kfe->e) {
2294                         if (BM_edge_in_face(kfe->e, f)) {
2295                                 /* shouldn't happen, but in this case - just ignore */
2296                                 continue;
2297                         }
2298                 }
2299                 else {
2300                         if (kfe->v1->v == NULL) {
2301                                 kfe->v1->v = BM_vert_create(bm, kfe->v1->co, NULL, 0);
2302                         }
2303                         if (kfe->v2->v == NULL) {
2304                                 kfe->v2->v = BM_vert_create(bm, kfe->v2->co, NULL, 0);
2305                         }
2306                         BLI_assert(kfe->e == NULL);
2307                         kfe->e = BM_edge_create(bm, kfe->v1->v, kfe->v2->v, NULL, 0);
2308                         if (kfe->e) {
2309                                 if (kcd->select_result || BM_elem_flag_test(f, BM_ELEM_SELECT)) {
2310                                         BM_edge_select_set(bm, kfe->e, true);
2311                                 }
2312                                 is_new_edge = true;
2313                         }
2314                 }
2315
2316                 BLI_assert(kfe->e);
2317
2318                 if (BLI_gset_add(kcd->edgenet.edge_visit, kfe->e)) {
2319                         kfe_array[i] = is_new_edge ? kfe : 0;
2320                         edge_array[i] = kfe->e;
2321                         i += 1;
2322                 }
2323         }
2324
2325         if (i) {
2326                 const int edge_array_len_orig = i;
2327                 edge_array_len = i;
2328
2329 #ifdef USE_NET_ISLAND_CONNECT
2330                 unsigned int edge_array_holes_len;
2331                 BMEdge **edge_array_holes;
2332                 if (BM_face_split_edgenet_connect_islands(
2333                         bm, f,
2334                         edge_array, edge_array_len,
2335                         kcd->edgenet.arena,
2336                         &edge_array_holes, &edge_array_holes_len))
2337                 {
2338                         if (BM_elem_flag_test(f, BM_ELEM_SELECT)) {
2339                                 for (i = edge_array_len; i < edge_array_holes_len; i++) {
2340                                         BM_edge_select_set(bm, edge_array_holes[i], true);
2341                                 }
2342                         }
2343
2344                         edge_array_len = edge_array_holes_len;
2345                         edge_array = edge_array_holes;  /* owned by the arena */
2346                 }
2347 #endif
2348
2349                 ok = BM_face_split_edgenet(
2350                          bm, f, edge_array, edge_array_len,
2351                          &face_arr, &face_arr_len);
2352
2353                 if (ok) {
2354                         MEM_freeN(face_arr);
2355                 }
2356
2357                 /* remove dangling edges, not essential - but nice for users */
2358                 for (i = 0; i < edge_array_len_orig; i++) {
2359                         if (kfe_array[i]) {
2360                                 if (BM_edge_is_wire(kfe_array[i]->e)) {
2361                                         BM_edge_kill(bm, kfe_array[i]->e);
2362                                         kfe_array[i]->e = NULL;
2363                                 }
2364                         }
2365                 }
2366
2367
2368 #ifdef USE_NET_ISLAND_CONNECT
2369                 BLI_memarena_clear(kcd->edgenet.arena);
2370 #endif
2371         }
2372
2373         BLI_gset_clear(kcd->edgenet.edge_visit, NULL);
2374 }
2375
2376 /* Use the network of KnifeEdges and KnifeVerts accumulated to make real BMVerts and BMEdedges */
2377 static void knife_make_cuts(KnifeTool_OpData *kcd)
2378 {
2379         BMesh *bm = kcd->em->bm;
2380         KnifeEdge *kfe;
2381         KnifeVert *kfv;
2382         BMFace *f;
2383         BMEdge *e, *enew;
2384         ListBase *lst;
2385         Ref *ref;
2386         float pct;
2387         SmallHashIter hiter;
2388         BLI_mempool_iter iter;
2389         SmallHash fhash_, *fhash = &fhash_;
2390         SmallHash ehash_, *ehash = &ehash_;
2391
2392         BLI_smallhash_init(fhash);
2393         BLI_smallhash_init(ehash);
2394
2395         /* put list of cutting edges for a face into fhash, keyed by face */
2396         BLI_mempool_iternew(kcd->kedges, &iter);
2397         for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
2398
2399                 /* select edges that lie directly on the cut */
2400                 if (kcd->select_result) {
2401                         if (kfe->e && kfe->is_cut) {
2402                                 BM_edge_select_set(bm, kfe->e, true);
2403                         }
2404                 }
2405
2406                 f = kfe->basef;
2407                 if (!f || kfe->e)
2408                         continue;
2409                 lst = BLI_smallhash_lookup(fhash, (uintptr_t)f);
2410                 if (!lst) {
2411                         lst = knife_empty_list(kcd);
2412                         BLI_smallhash_insert(fhash, (uintptr_t)f, lst);
2413                 }
2414                 knife_append_list(kcd, lst, kfe);
2415         }
2416
2417         /* put list of splitting vertices for an edge into ehash, keyed by edge */
2418         BLI_mempool_iternew(kcd->kverts, &iter);
2419         for (kfv = BLI_mempool_iterstep(&iter); kfv; kfv = BLI_mempool_iterstep(&iter)) {
2420                 if (kfv->v)
2421                         continue;  /* already have a BMVert */
2422                 for (ref = kfv->edges.first; ref; ref = ref->next) {
2423                         kfe = ref->ref;
2424                         e = kfe->e;
2425                         if (!e)
2426                                 continue;
2427                         lst = BLI_smallhash_lookup(ehash, (uintptr_t)e);
2428                         if (!lst) {
2429                                 lst = knife_empty_list(kcd);
2430                                 BLI_smallhash_insert(ehash, (uintptr_t)e, lst);
2431                         }
2432                         /* there can be more than one kfe in kfv's list with same e */
2433                         if (!find_ref(lst, kfv))
2434                                 knife_append_list(kcd, lst, kfv);
2435                 }
2436         }
2437
2438         /* split bmesh edges where needed */
2439         for (lst = BLI_smallhash_iternew(ehash, &hiter, (uintptr_t *)&e); lst;
2440              lst = BLI_smallhash_iternext(&hiter, (uintptr_t *)&e))
2441         {
2442                 BLI_listbase_sort_r(lst, sort_verts_by_dist_cb, e->v1->co);
2443
2444                 for (ref = lst->first; ref; ref = ref->next) {
2445                         kfv = ref->ref;
2446                         pct = line_point_factor_v3(kfv->co, e->v1->co, e->v2->co);
2447                         kfv->v = BM_edge_split(bm, e, e->v1, &enew, pct);
2448                 }
2449         }
2450
2451         if (kcd->only_select) {
2452                 EDBM_flag_disable_all(kcd->em, BM_ELEM_SELECT);
2453         }
2454
2455         /* do cuts for each face */
2456         for (lst = BLI_smallhash_iternew(fhash, &hiter, (uintptr_t *)&f); lst;
2457              lst = BLI_smallhash_iternext(&hiter, (uintptr_t *)&f))
2458         {
2459                 knife_make_face_cuts(kcd, f, lst);
2460         }
2461
2462         BLI_smallhash_release(fhash);
2463         BLI_smallhash_release(ehash);
2464 }
2465
2466 /* called on tool confirmation */
2467 static void knifetool_finish_ex(KnifeTool_OpData *kcd)
2468 {
2469         knife_make_cuts(kcd);
2470
2471         EDBM_selectmode_flush(kcd->em);
2472         EDBM_mesh_normals_update(kcd->em);
2473         EDBM_update_generic(kcd->em, true, true);
2474
2475         /* re-tessellating makes this invalid, dont use again by accident */
2476         knifetool_free_bmbvh(kcd);
2477 }
2478 static void knifetool_finish(wmOperator *op)
2479 {
2480         KnifeTool_OpData *kcd = op->customdata;
2481         knifetool_finish_ex(kcd);
2482 }
2483
2484 static void knife_recalc_projmat(KnifeTool_OpData *kcd)
2485 {
2486         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
2487         ED_view3d_ob_project_mat_get(kcd->ar->regiondata, kcd->ob, kcd->projmat);
2488         invert_m4_m4(kcd->projmat_inv, kcd->projmat);
2489
2490         mul_v3_mat3_m4v3(kcd->proj_zaxis, kcd->ob->imat, kcd->vc.rv3d->viewinv[2]);
2491         normalize_v3(kcd->proj_zaxis);
2492
2493         kcd->is_ortho = ED_view3d_clip_range_get(kcd->vc.v3d, kcd->vc.rv3d,
2494                                                  &kcd->clipsta, &kcd->clipend, true);
2495 }
2496
2497 /* called when modal loop selection is done... */
2498 static void knifetool_exit_ex(bContext *C, KnifeTool_OpData *kcd)
2499 {
2500         if (!kcd)
2501                 return;
2502
2503         if (kcd->is_interactive) {
2504                 WM_cursor_modal_restore(CTX_wm_window(C));
2505
2506                 /* deactivate the extra drawing stuff in 3D-View */
2507                 ED_region_draw_cb_exit(kcd->ar->type, kcd->draw_handle);
2508         }
2509
2510         /* free the custom data */
2511         BLI_mempool_destroy(kcd->refs);
2512         BLI_mempool_destroy(kcd->kverts);
2513         BLI_mempool_destroy(kcd->kedges);
2514
2515         BLI_ghash_free(kcd->origedgemap, NULL, NULL);
2516         BLI_ghash_free(kcd->origvertmap, NULL, NULL);
2517         BLI_ghash_free(kcd->kedgefacemap, NULL, NULL);
2518         BLI_ghash_free(kcd->facetrimap, NULL, NULL);
2519
2520         BLI_memarena_free(kcd->arena);
2521 #ifdef USE_NET_ISLAND_CONNECT
2522         BLI_memarena_free(kcd->edgenet.arena);
2523 #endif
2524         BLI_gset_free(kcd->edgenet.edge_visit, NULL);
2525
2526         /* tag for redraw */
2527         ED_region_tag_redraw(kcd->ar);
2528
2529         knifetool_free_bmbvh(kcd);
2530
2531         if (kcd->linehits)
2532                 MEM_freeN(kcd->linehits);
2533
2534         /* destroy kcd itself */
2535         MEM_freeN(kcd);
2536 }
2537 static void knifetool_exit(bContext *C, wmOperator *op)
2538 {
2539         KnifeTool_OpData *kcd = op->customdata;
2540         knifetool_exit_ex(C, kcd);
2541         op->customdata = NULL;
2542 }
2543
2544 static void knifetool_update_mval(KnifeTool_OpData *kcd, const float mval[2])
2545 {
2546         knife_recalc_projmat(kcd);
2547         copy_v2_v2(kcd->mval, mval);
2548
2549         if (knife_update_active(kcd)) {
2550                 ED_region_tag_redraw(kcd->ar);
2551         }
2552 }
2553
2554 static void knifetool_update_mval_i(KnifeTool_OpData *kcd, const int mval_i[2])
2555 {
2556         float mval[2] = {UNPACK2(mval_i)};
2557         knifetool_update_mval(kcd, mval);
2558 }
2559
2560 static void knifetool_init_bmbvh(KnifeTool_OpData *kcd)
2561 {
2562         BM_mesh_elem_index_ensure(kcd->em->bm, BM_VERT);
2563
2564         kcd->cagecos = (const float (*)[3])BKE_editmesh_vertexCos_get(kcd->em, kcd->scene, NULL);
2565
2566         kcd->bmbvh = BKE_bmbvh_new_from_editmesh(
2567                 kcd->em,
2568                 BMBVH_RETURN_ORIG |
2569                 ((kcd->only_select && kcd->cut_through) ? BMBVH_RESPECT_SELECT : BMBVH_RESPECT_HIDDEN),
2570                 kcd->cagecos, false);
2571 }
2572
2573 static void knifetool_free_bmbvh(KnifeTool_OpData *kcd)
2574 {
2575         if (kcd->bmbvh) {
2576                 BKE_bmbvh_free(kcd->bmbvh);
2577                 kcd->bmbvh = NULL;
2578         }
2579
2580         if (kcd->cagecos) {
2581                 MEM_freeN((void *)kcd->cagecos);
2582                 kcd->cagecos = NULL;
2583         }
2584 }
2585
2586 /* called when modal loop selection gets set up... */
2587 static void knifetool_init(bContext *C, KnifeTool_OpData *kcd,
2588                            const bool only_select, const bool cut_through, const bool is_interactive)
2589 {
2590         Scene *scene = CTX_data_scene(C);
2591         Object *obedit = CTX_data_edit_object(C);
2592
2593         /* assign the drawing handle for drawing preview line... */
2594         kcd->scene = scene;
2595         kcd->ob = obedit;
2596         kcd->ar = CTX_wm_region(C);
2597
2598         em_setup_viewcontext(C, &kcd->vc);
2599
2600         kcd->em = BKE_editmesh_from_object(kcd->ob);
2601
2602         /* cut all the way through the mesh if use_occlude_geometry button not pushed */
2603         kcd->is_interactive = is_interactive;
2604         kcd->cut_through = cut_through;
2605         kcd->only_select = only_select;
2606
2607         knifetool_init_bmbvh(kcd);
2608
2609         kcd->arena = BLI_memarena_new(MEM_SIZE_OPTIMAL(1 << 15), "knife");
2610 #ifdef USE_NET_ISLAND_CONNECT
2611         kcd->edgenet.arena = BLI_memarena_new(MEM_SIZE_OPTIMAL(1 << 15), __func__);
2612 #endif
2613         kcd->edgenet.edge_visit = BLI_gset_ptr_new(__func__);
2614
2615         kcd->vthresh = KMAXDIST - 1;
2616         kcd->ethresh = KMAXDIST;
2617
2618         knife_recalc_projmat(kcd);
2619
2620         ED_region_tag_redraw(kcd->ar);
2621
2622         kcd->refs = BLI_mempool_create(sizeof(Ref), 0, 2048, 0);
2623         kcd->kverts = BLI_mempool_create(sizeof(KnifeVert), 0, 512, BLI_MEMPOOL_ALLOW_ITER);
2624         kcd->kedges = BLI_mempool_create(sizeof(KnifeEdge), 0, 512, BLI_MEMPOOL_ALLOW_ITER);
2625
2626         kcd->origedgemap = BLI_ghash_ptr_new("knife origedgemap");
2627         kcd->origvertmap = BLI_ghash_ptr_new("knife origvertmap");
2628         kcd->kedgefacemap = BLI_ghash_ptr_new("knife kedgefacemap");
2629         kcd->facetrimap = BLI_ghash_ptr_new("knife facetrimap");
2630
2631         /* can't usefully select resulting edges in face mode */
2632         kcd->select_result = (kcd->em->selectmode != SCE_SELECT_FACE);
2633
2634         knife_pos_data_clear(&kcd->curr);
2635         knife_pos_data_clear(&kcd->prev);
2636
2637         if (is_interactive) {
2638                 kcd->draw_handle = ED_region_draw_cb_activate(kcd->ar->type, knifetool_draw, kcd, REGION_DRAW_POST_VIEW);
2639
2640                 knife_init_colors(&kcd->colors);
2641         }
2642 }
2643
2644 static void knifetool_cancel(bContext *C, wmOperator *op)
2645 {
2646         /* this is just a wrapper around exit() */
2647         knifetool_exit(C, op);
2648 }
2649
2650 static int knifetool_invoke(bContext *C, wmOperator *op, const wmEvent *event)
2651 {
2652         const bool only_select = RNA_boolean_get(op->ptr, "only_selected");
2653         const bool cut_through = !RNA_boolean_get(op->ptr, "use_occlude_geometry");
2654
2655         KnifeTool_OpData *kcd;
2656
2657         if (only_select) {
2658                 Object *obedit = CTX_data_edit_object(C);
2659                 BMEditMesh *em = BKE_editmesh_from_object(obedit);
2660                 if (em->bm->totfacesel == 0) {
2661                         BKE_report(op->reports, RPT_ERROR, "Selected faces required");
2662                         return OPERATOR_CANCELLED;
2663                 }
2664         }
2665
2666         view3d_operator_needs_opengl(C);
2667
2668         /* alloc new customdata */
2669         kcd = op->customdata = MEM_callocN(sizeof(KnifeTool_OpData), __func__);
2670
2671         knifetool_init(C, kcd, only_select, cut_through, true);
2672
2673         op->flag |= OP_IS_MODAL_CURSOR_REGION;
2674
2675         /* add a modal handler for this operator - handles loop selection */
2676         WM_cursor_modal_set(CTX_wm_window(C), BC_KNIFECURSOR);
2677         WM_event_add_modal_handler(C, op);
2678
2679         knifetool_update_mval_i(kcd, event->mval);
2680
2681         knife_update_header(C, op, kcd);
2682
2683         return OPERATOR_RUNNING_MODAL;
2684 }
2685
2686 wmKeyMap *knifetool_modal_keymap(wmKeyConfig *keyconf)
2687 {
2688         static EnumPropertyItem modal_items[] = {
2689                 {KNF_MODAL_CANCEL, "CANCEL", 0, "Cancel", ""},
2690                 {KNF_MODAL_CONFIRM, "CONFIRM", 0, "Confirm", ""},
2691                 {KNF_MODAL_MIDPOINT_ON, "SNAP_MIDPOINTS_ON", 0, "Snap To Midpoints On", ""},
2692                 {KNF_MODAL_MIDPOINT_OFF, "SNAP_MIDPOINTS_OFF", 0, "Snap To Midpoints Off", ""},
2693                 {KNF_MODEL_IGNORE_SNAP_ON, "IGNORE_SNAP_ON", 0, "Ignore Snapping On", ""},
2694                 {KNF_MODEL_IGNORE_SNAP_OFF, "IGNORE_SNAP_OFF", 0, "Ignore Snapping Off", ""},
2695                 {KNF_MODAL_ANGLE_SNAP_TOGGLE, "ANGLE_SNAP_TOGGLE", 0, "Toggle Angle Snapping", ""},
2696                 {KNF_MODAL_CUT_THROUGH_TOGGLE, "CUT_THROUGH_TOGGLE", 0, "Toggle Cut Through", ""},
2697                 {KNF_MODAL_NEW_CUT, "NEW_CUT", 0, "End Current Cut", ""},
2698                 {KNF_MODAL_ADD_CUT, "ADD_CUT", 0, "Add Cut", ""},
2699                 {KNF_MODAL_PANNING, "PANNING", 0, "Panning", ""},
2700                 {0, NULL, 0, NULL, NULL}
2701         };
2702
2703         wmKeyMap *keymap = WM_modalkeymap_get(keyconf, "Knife Tool Modal Map");
2704
2705         /* this function is called for each spacetype, only needs to add map once */
2706         if (keymap && keymap->modal_items)
2707                 return NULL;
2708
2709         keymap = WM_modalkeymap_add(keyconf, "Knife Tool Modal Map", modal_items);
2710
2711         /* items for modal map */
2712         WM_modalkeymap_add_item(keymap, ESCKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_CANCEL);
2713         WM_modalkeymap_add_item(keymap, MIDDLEMOUSE, KM_ANY, KM_ANY, 0, KNF_MODAL_PANNING);
2714         WM_modalkeymap_add_item(keymap, LEFTMOUSE, KM_DBL_CLICK, KM_ANY, 0, KNF_MODAL_ADD_CUT_CLOSED);
2715         WM_modalkeymap_add_item(keymap, LEFTMOUSE, KM_ANY, KM_ANY, 0, KNF_MODAL_ADD_CUT);
2716         WM_modalkeymap_add_item(keymap, RIGHTMOUSE, KM_PRESS, KM_ANY, 0, KNF_MODAL_CANCEL);
2717         WM_modalkeymap_add_item(keymap, RETKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
2718         WM_modalkeymap_add_item(keymap, PADENTER, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
2719         WM_modalkeymap_add_item(keymap, SPACEKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
2720         WM_modalkeymap_add_item(keymap, EKEY, KM_PRESS, 0, 0, KNF_MODAL_NEW_CUT);
2721
2722         WM_modalkeymap_add_item(keymap, LEFTCTRLKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_MIDPOINT_ON);
2723         WM_modalkeymap_add_item(keymap, LEFTCTRLKEY, KM_RELEASE, KM_ANY, 0, KNF_MODAL_MIDPOINT_OFF);
2724         WM_modalkeymap_add_item(keymap, RIGHTCTRLKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_MIDPOINT_ON);
2725         WM_modalkeymap_add_item(keymap, RIGHTCTRLKEY, KM_RELEASE, KM_ANY, 0, KNF_MODAL_MIDPOINT_OFF);
2726
2727         WM_modalkeymap_add_item(keymap, LEFTSHIFTKEY, KM_PRESS, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_ON);
2728         WM_modalkeymap_add_item(keymap, LEFTSHIFTKEY, KM_RELEASE, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_OFF);
2729         WM_modalkeymap_add_item(keymap, RIGHTSHIFTKEY, KM_PRESS, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_ON);
2730         WM_modalkeymap_add_item(keymap, RIGHTSHIFTKEY, KM_RELEASE, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_OFF);
2731
2732         WM_modalkeymap_add_item(keymap, CKEY, KM_PRESS, 0, 0, KNF_MODAL_ANGLE_SNAP_TOGGLE);
2733         WM_modalkeymap_add_item(keymap, ZKEY, KM_PRESS, 0, 0, KNF_MODAL_CUT_THROUGH_TOGGLE);
2734
2735         WM_modalkeymap_assign(keymap, "MESH_OT_knife_tool");
2736
2737         return keymap;
2738 }
2739
2740 static int knifetool_modal(bContext *C, wmOperator *op, const wmEvent *event)
2741 {
2742         Object *obedit = CTX_data_edit_object(C);
2743         KnifeTool_OpData *kcd = op->customdata;
2744         bool do_refresh = false;
2745
2746         if (!obedit || obedit->type != OB_MESH || BKE_editmesh_from_object(obedit) != kcd->em) {
2747                 knifetool_exit(C, op);
2748                 ED_area_headerprint(CTX_wm_area(C), NULL);
2749                 return OPERATOR_FINISHED;
2750         }
2751
2752         em_setup_viewcontext(C, &kcd->vc);
2753         kcd->ar = kcd->vc.ar;
2754
2755         view3d_operator_needs_opengl(C);
2756         ED_view3d_init_mats_rv3d(obedit, kcd->vc.rv3d);  /* needed to initialize clipping */
2757
2758         if (kcd->mode == MODE_PANNING)
2759                 kcd->mode = kcd->prevmode;
2760
2761         /* handle modal keymap */
2762         if (event->type == EVT_MODAL_MAP) {
2763                 switch (event->val) {
2764                         case KNF_MODAL_CANCEL:
2765                                 /* finish */
2766                                 ED_region_tag_redraw(kcd->ar);
2767
2768                                 knifetool_exit(C, op);
2769                                 ED_area_headerprint(CTX_wm_area(C), NULL);
2770
2771                                 return OPERATOR_CANCELLED;
2772                         case KNF_MODAL_CONFIRM:
2773                                 /* finish */
2774                                 ED_region_tag_redraw(kcd->ar);
2775
2776                                 knifetool_finish(op);
2777                                 knifetool_exit(C, op);
2778                                 ED_area_headerprint(CTX_wm_area(C), NULL);
2779
2780                                 return OPERATOR_FINISHED;
2781                         case KNF_MODAL_MIDPOINT_ON:
2782                                 kcd->snap_midpoints = true;
2783
2784                                 knife_recalc_projmat(kcd);
2785                                 knife_update_active(kcd);
2786                                 knife_update_header(C, op, kcd);
2787                                 ED_region_tag_redraw(kcd->ar);
2788                                 do_refresh = true;
2789                                 break;
2790                         case KNF_MODAL_MIDPOINT_OFF:
2791                                 kcd->snap_midpoints = false;
2792
2793                                 knife_recalc_projmat(kcd);
2794                                 knife_update_active(kcd);
2795                                 knife_update_header(C, op, kcd);
2796                                 ED_region_tag_redraw(kcd->ar);
2797                                 do_refresh = true;
2798                                 break;
2799                         case KNF_MODEL_IGNORE_SNAP_ON:
2800                                 ED_region_tag_redraw(kcd->ar);
2801                                 kcd->ignore_vert_snapping = kcd->ignore_edge_snapping = true;
2802                                 knife_update_header(C, op, kcd);
2803                                 do_refresh = true;
2804                                 break;
2805                         case KNF_MODEL_IGNORE_SNAP_OFF:
2806                                 ED_region_tag_redraw(kcd->ar);
2807                                 kcd->ignore_vert_snapping = kcd->ignore_edge_snapping = false;
2808                                 knife_update_header(C, op, kcd);
2809                                 do_refresh = true;
2810                                 break;
2811                         case KNF_MODAL_ANGLE_SNAP_TOGGLE:
2812                                 kcd->angle_snapping = !kcd->angle_snapping;
2813                                 knife_update_header(C, op, kcd);
2814                                 do_refresh = true;
2815                                 break;
2816                         case KNF_MODAL_CUT_THROUGH_TOGGLE:
2817                                 kcd->cut_through = !kcd->cut_through;
2818                                 knife_update_header(C, op, kcd);
2819                                 do_refresh = true;
2820                                 break;
2821                         case KNF_MODAL_NEW_CUT:
2822                                 ED_region_tag_redraw(kcd->ar);
2823                                 knife_finish_cut(kcd);
2824                                 kcd->mode = MODE_IDLE;
2825                                 break;
2826                         case KNF_MODAL_ADD_CUT:
2827                                 knife_recalc_projmat(kcd);
2828
2829                                 /* get the value of the event which triggered this one */
2830                                 if (event->prevval != KM_RELEASE) {
2831                                         if (kcd->mode == MODE_DRAGGING) {
2832                                                 knife_add_cut(kcd);
2833                                         }
2834                                         else if (kcd->mode != MODE_PANNING) {
2835                                                 knife_start_cut(kcd);
2836                                                 kcd->mode = MODE_DRAGGING;
2837                                                 kcd->init = kcd->curr;
2838                                         }
2839
2840                                         /* freehand drawing is incompatible with cut-through */
2841                                         if (kcd->cut_through == false) {
2842                                                 kcd->is_drag_hold = true;
2843                                         }
2844                                 }
2845                                 else {
2846                                         kcd->is_drag_hold = false;
2847
2848                                         /* needed because the last face 'hit' is ignored when dragging */
2849                                         knifetool_update_mval(kcd, kcd->curr.mval);
2850                                 }
2851
2852                                 ED_region_tag_redraw(kcd->ar);
2853                                 break;
2854                         case KNF_MODAL_ADD_CUT_CLOSED:
2855                                 if (kcd->mode == MODE_DRAGGING) {
2856
2857                                         /* shouldn't be possible with default key-layout, just incase... */
2858                                         if (kcd->is_drag_hold) {
2859                                                 kcd->is_drag_hold = false;
2860                                                 knifetool_update_mval(kcd, kcd->curr.mval);
2861                                         }
2862
2863                                         kcd->prev = kcd->curr;
2864                                         kcd->curr = kcd->init;
2865
2866                                         knife_project_v2(kcd, kcd->curr.cage, kcd->curr.mval);
2867                                         knifetool_update_mval(kcd, kcd->curr.mval);
2868
2869                                         knife_add_cut(kcd);
2870
2871                                         /* KNF_MODAL_NEW_CUT */
2872                                         knife_finish_cut(kcd);
2873                                         kcd->mode = MODE_IDLE;
2874                                 }
2875                                 break;
2876                         case KNF_MODAL_PANNING:
2877                                 if (event->val != KM_RELEASE) {
2878                                         if (kcd->mode != MODE_PANNING) {
2879                                                 kcd->prevmode = kcd->mode;
2880                                                 kcd->mode = MODE_PANNING;
2881                                         }
2882                                 }
2883                                 else {
2884                                         kcd->mode = kcd->prevmode;
2885                                 }
2886
2887                                 ED_region_tag_redraw(kcd->ar);
2888                                 return OPERATOR_PASS_THROUGH;
2889                 }
2890         }
2891         else { /* non-modal-mapped events */
2892                 switch (event->type) {
2893                         case MOUSEPAN:
2894                         case MOUSEZOOM:
2895                         case MOUSEROTATE:
2896                         case WHEELUPMOUSE:
2897                         case WHEELDOWNMOUSE:
2898                                 return OPERATOR_PASS_THROUGH;
2899                         case MOUSEMOVE: /* mouse moved somewhere to select another loop */
2900                                 if (kcd->mode != MODE_PANNING) {
2901                                         knifetool_update_mval_i(kcd, event->mval);
2902
2903                                         if (kcd->is_drag_hold) {
2904                                                 if (kcd->totlinehit >= 2) {
2905                                                         knife_add_cut(kcd);
2906                                                 }
2907                                         }
2908                                 }
2909
2910                                 break;
2911                 }
2912         }
2913
2914         if (kcd->mode == MODE_DRAGGING) {
2915                 op->flag &= ~OP_IS_MODAL_CURSOR_REGION;
2916         }
2917         else {
2918                 op->flag |= OP_IS_MODAL_CURSOR_REGION;
2919         }
2920
2921         if (do_refresh) {
2922                 /* we don't really need to update mval,
2923                  * but this happens to be the best way to refresh at the moment */
2924                 knifetool_update_mval_i(kcd, event->mval);
2925         }
2926
2927         /* keep going until the user confirms */
2928         return OPERATOR_RUNNING_MODAL;
2929 }
2930
2931 void MESH_OT_knife_tool(wmOperatorType *ot)
2932 {
2933         /* description */
2934         ot->name = "Knife Topology Tool";
2935         ot->idname = "MESH_OT_knife_tool";
2936         ot->description = "Cut new topology";
2937
2938         /* callbacks */
2939         ot->invoke = knifetool_invoke;
2940         ot->modal = knifetool_modal;
2941         ot->cancel = knifetool_cancel;
2942         ot->poll = ED_operator_editmesh_view3d;
2943
2944         /* flags */
2945         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO | OPTYPE_BLOCKING;
2946
2947         RNA_def_boolean(ot->srna, "use_occlude_geometry", true, "Occlude Geometry", "Only cut the front most geometry");
2948         RNA_def_boolean(ot->srna, "only_selected", false, "Only Selected", "Only cut selected geometry");
2949 }
2950
2951
2952 /* -------------------------------------------------------------------- */
2953 /* Knife tool as a utility function
2954  * that can be used for internal slicing operations */
2955
2956 static bool edbm_mesh_knife_point_isect(LinkNode *polys, const float cent_ss[2])
2957 {
2958         LinkNode *p = polys;
2959         int isect = 0;
2960
2961         while (p) {
2962                 const float (*mval_fl)[2] = p->link;
2963                 const int mval_tot = MEM_allocN_len(mval_fl) / sizeof(*mval_fl);
2964                 isect += (int)isect_point_poly_v2(cent_ss, mval_fl, mval_tot - 1, false);
2965                 p = p->next;
2966         }
2967
2968         if (isect % 2) {
2969                 return true;
2970         }
2971         return false;
2972 }
2973
2974 /**
2975  * \param use_tag  When set, tag all faces inside the polylines.
2976  */
2977 void EDBM_mesh_knife(bContext *C, LinkNode *polys, bool use_tag, bool cut_through)
2978 {
2979         KnifeTool_OpData *kcd;
2980         bglMats mats;
2981
2982         view3d_operator_needs_opengl(C);
2983
2984         /* init */
2985         {
2986                 const bool only_select = false;
2987                 const bool is_interactive = false;  /* can enable for testing */
2988
2989                 kcd = MEM_callocN(sizeof(KnifeTool_OpData), __func__);
2990
2991                 knifetool_init(C, kcd, only_select, cut_through, is_interactive);
2992
2993                 kcd->ignore_edge_snapping = true;
2994                 kcd->ignore_vert_snapping = true;
2995
2996                 if (use_tag) {
2997                         BM_mesh_elem_hflag_enable_all(kcd->em->bm, BM_EDGE, BM_ELEM_TAG, false);
2998                 }
2999
3000                 if (kcd->cut_through == false) {
3001                         bgl_get_mats(&mats);
3002                 }
3003         }
3004
3005         /* execute */
3006         {
3007                 LinkNode *p = polys;
3008
3009                 knife_recalc_projmat(kcd);
3010
3011                 while (p) {
3012                         const float (*mval_fl)[2] = p->link;
3013                         const int mval_tot = MEM_allocN_len(mval_fl) / sizeof(*mval_fl);
3014                         int i;
3015
3016                         for (i = 0; i < mval_tot; i++) {
3017                                 knifetool_update_mval(kcd, mval_fl[i]);
3018                                 if (i == 0) {
3019                                         knife_start_cut(kcd);
3020                                         kcd->mode = MODE_DRAGGING;
3021                                 }
3022                                 else {
3023                                         knife_add_cut(kcd);
3024                                 }
3025                         }
3026                         knife_finish_cut(kcd);
3027                         kcd->mode = MODE_IDLE;
3028                         p = p->next;
3029                 }
3030         }
3031
3032         /* finish */
3033         {
3034                 knifetool_finish_ex(kcd);
3035
3036                 /* tag faces inside! */
3037                 if (use_tag) {
3038                         BMesh *bm = kcd->em->bm;
3039                         float projmat[4][4];
3040
3041                         BMEdge *e;
3042                         BMIter iter;
3043
3044                         bool keep_search;
3045
3046                         /* freed on knifetool_finish_ex, but we need again to check if points are visible */
3047                         if (kcd->cut_through == false) {
3048                                 knifetool_init_bmbvh(kcd);
3049                         }
3050
3051                         ED_view3d_ob_project_mat_get(kcd->ar->regiondata, kcd->ob, projmat);
3052
3053                         /* use face-loop tag to store if we have intersected */
3054 #define F_ISECT_IS_UNKNOWN(f)  BM_elem_flag_test(BM_FACE_FIRST_LOOP(f), BM_ELEM_TAG)
3055 #define F_ISECT_SET_UNKNOWN(f) BM_elem_flag_enable(BM_FACE_FIRST_LOOP(f), BM_ELEM_TAG)
3056 #define F_ISECT_SET_OUTSIDE(f) BM_elem_flag_disable(BM_FACE_FIRST_LOOP(f), BM_ELEM_TAG)
3057                         {
3058                                 BMFace *f;
3059                                 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
3060                                         F_ISECT_SET_UNKNOWN(f);
3061                                         BM_elem_flag_disable(f, BM_ELEM_TAG);
3062                                 }
3063                         }
3064
3065                         /* tag all faces linked to cut edges */
3066                         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
3067                                 /* check are we tagged?, then we are an original face */
3068                                 if (BM_elem_flag_test(e, BM_ELEM_TAG) == false) {
3069                                         BMFace *f;
3070                                         BMIter fiter;
3071                                         BM_ITER_ELEM (f, &fiter, e, BM_FACES_OF_EDGE) {
3072                                                 float cent[3], cent_ss[2];
3073                                                 BM_face_calc_point_in_face(f, cent);
3074                                                 knife_project_v2(kcd, cent, cent_ss);
3075                                                 if (edbm_mesh_knife_point_isect(polys, cent_ss)) {
3076                                                         BM_elem_flag_enable(f, BM_ELEM_TAG);
3077                                                 }
3078                                         }
3079                                 }
3080                         }
3081
3082                         /* expand tags for faces which are not cut, but are inside the polys */
3083                         do {
3084                                 BMFace *f;
3085                                 keep_search = false;
3086                                 BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
3087                                         if (BM_elem_flag_test(f, BM_ELEM_TAG) == false && (F_ISECT_IS_UNKNOWN(f))) {
3088                                                 /* am I connected to a tagged face via an un-tagged edge (ie, not across a cut) */
3089                                                 BMLoo