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