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