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