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