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