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