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