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