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