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