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