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