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