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