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