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