fix for bug in ED_view3d_project_float that only effected the 'Rip' tool.
[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
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 #define _USE_MATH_DEFINES
28
29
30 #include "MEM_guardedalloc.h"
31
32 #include "BLI_blenlib.h"
33 #include "BLI_array.h"
34 #include "BLI_math.h"
35 #include "BLI_rand.h"
36 #include "BLI_smallhash.h"
37 #include "BLI_scanfill.h"
38 #include "BLI_memarena.h"
39
40 #include "BKE_DerivedMesh.h"
41 #include "BKE_context.h"
42 #include "BKE_depsgraph.h"
43
44 #include "BIF_gl.h"
45 #include "BIF_glutil.h" /* for paint cursor */
46
47
48 #include "ED_screen.h"
49 #include "ED_space_api.h"
50 #include "ED_view3d.h"
51 #include "ED_mesh.h"
52
53 #include "WM_api.h"
54 #include "WM_types.h"
55
56 #include "DNA_scene_types.h"
57 #include "DNA_mesh_types.h"
58 #include "DNA_object_types.h"
59 #include "BKE_tessmesh.h"
60
61 #include "mesh_intern.h"
62
63 /* this code here is kindof messy. . .I might need to eventually rework it - joeedh */
64
65 #define MAXGROUP        30
66 #define KMAXDIST        10      /* max mouse distance from edge before not detecting it */
67
68 /* knifetool operator */
69 typedef struct KnifeVert {
70         BMVert *v; /* non-NULL if this is an original vert */
71         ListBase edges;
72
73         float co[3], cageco[3], sco[3]; /* sco is screen coordinates for cageco */
74         short flag, draw, isface, inspace;
75 } KnifeVert;
76
77 typedef struct Ref {
78         struct Ref *next, *prev;
79         void *ref;
80 } Ref;
81
82 typedef struct KnifeEdge {
83         KnifeVert *v1, *v2;
84         BMFace *basef; /* face to restrict face fill to */
85         ListBase faces;
86         int draw;
87         
88         BMEdge *e, *oe; /* non-NULL if this is an original edge */
89 } KnifeEdge;
90
91 typedef struct BMEdgeHit {
92         KnifeEdge *kfe;
93         float hit[3], cagehit[3];
94         float realhit[3]; /* used in midpoint mode */
95         float schit[3];
96         float l; /* lambda along cut line */
97         float perc; /* lambda along hit line */
98         KnifeVert *v; /* set if snapped to a vert */
99         BMFace *f;
100 } BMEdgeHit;
101
102 /* struct for properties used while drawing */
103 typedef struct knifetool_opdata {
104         ARegion *ar;            /* region that knifetool was activated in */
105         void *draw_handle;      /* for drawing preview loop */
106         ViewContext vc;
107         bContext *C;
108         
109         Object *ob;
110         BMEditMesh *em;
111         
112         MemArena *arena;
113
114         GHash *origvertmap;
115         GHash *origedgemap;
116         
117         GHash *kedgefacemap;
118         
119         BMBVHTree *bmbvh;
120
121         BLI_mempool *kverts;
122         BLI_mempool *kedges;
123         
124         float vthresh;
125         float ethresh;
126         
127         float vertco[3], vertcage[3];
128         float prevco[3], prevcage[3];
129         
130         /* used for drag-cutting */
131         BMEdgeHit *linehits;
132         int totlinehit;
133         
134         /* if curedge is NULL, attach to curvert;
135          * if curvert is NULL, attach to curbmface,
136          * otherwise create null vert */
137         KnifeEdge *curedge, *prevedge;
138         KnifeVert *curvert, *prevvert;
139         BMFace *curbmface, *prevbmface;
140
141         int totkedge, totkvert, cutnr;
142         
143         BLI_mempool *refs;
144         
145         float projmat[4][4];
146         int is_ortho;
147         int cut_through;
148         float clipsta, clipend;
149         
150         enum {
151                 MODE_IDLE,
152                 MODE_DRAGGING,
153                 MODE_CONNECT,
154                 MODE_PANNING
155         } mode;
156         
157         int snap_midpoints, prevmode, extend;
158         int ignore_edge_snapping, ignore_vert_snapping;
159         int prevmval[2];
160         
161         enum {
162                 ANGLE_FREE,
163                 ANGLE_0,
164                 ANGLE_45,
165                 ANGLE_90,
166                 ANGLE_135
167         } angle_snapping;
168
169         int is_space, prev_is_space; /*1 if current cut location, vertco, isn't on the mesh */
170         float (*cagecos)[3];
171 } knifetool_opdata;
172
173 static ListBase *knife_get_face_kedges(knifetool_opdata *kcd, BMFace *f);
174
175 static void knife_input_ray_cast(knifetool_opdata *kcd, const int mval_i[2],
176                                  float r_origin[3], float r_ray[3]);
177
178 static void knife_project_v3(knifetool_opdata *kcd, const float co[3], float sco[3])
179 {
180         ED_view3d_project_float_v3(kcd->ar, co, sco, kcd->projmat);
181 }
182
183 static ListBase *knife_empty_list(knifetool_opdata *kcd)
184 {
185         ListBase *lst;
186
187         lst = BLI_memarena_alloc(kcd->arena, sizeof(ListBase));
188         lst->first = lst->last = NULL;
189         return lst;
190 }
191
192 static void knife_append_list(knifetool_opdata *kcd, ListBase *lst, void *elem)
193 {
194         Ref *ref;
195
196         ref = BLI_mempool_calloc(kcd->refs);
197         ref->ref = elem;
198         BLI_addtail(lst, ref);
199 }
200
201 static KnifeEdge *new_knife_edge(knifetool_opdata *kcd)
202 {
203         kcd->totkedge++;
204         return BLI_mempool_calloc(kcd->kedges);
205 }
206
207 static void knife_add_to_vert_edges(knifetool_opdata *kcd, KnifeEdge* kfe)
208 {
209         knife_append_list(kcd, &kfe->v1->edges, kfe);
210         knife_append_list(kcd, &kfe->v2->edges, kfe);
211 }
212
213 static KnifeVert *new_knife_vert(knifetool_opdata *kcd, float *co, float *cageco)
214 {
215         KnifeVert *kfv = BLI_mempool_calloc(kcd->kverts);
216         
217         kcd->totkvert++;
218         
219         copy_v3_v3(kfv->co, co);
220         copy_v3_v3(kfv->cageco, cageco);
221         copy_v3_v3(kfv->sco, co);
222
223         knife_project_v3(kcd, kfv->co, kfv->sco);
224
225         return kfv;
226 }
227
228 /* get a KnifeVert wrapper for an existing BMVert */
229 static KnifeVert *get_bm_knife_vert(knifetool_opdata *kcd, BMVert *v)
230 {
231         KnifeVert *kfv = BLI_ghash_lookup(kcd->origvertmap, v);
232         
233         if (!kfv) {
234                 kfv = new_knife_vert(kcd, v->co, kcd->cagecos[BM_elem_index_get(v)]);
235                 kfv->v = v;
236                 BLI_ghash_insert(kcd->origvertmap, v, kfv);
237         }
238         
239         return kfv;
240 }
241
242 /* get a KnifeEdge wrapper for an existing BMEdge */
243 static KnifeEdge *get_bm_knife_edge(knifetool_opdata *kcd, BMEdge *e)
244 {
245         KnifeEdge *kfe = BLI_ghash_lookup(kcd->origedgemap, e);
246         if (!kfe) {
247                 BMIter iter;
248                 BMFace *f;
249                 
250                 kfe = new_knife_edge(kcd);
251                 kfe->e = e;
252                 kfe->v1 = get_bm_knife_vert(kcd, e->v1);
253                 kfe->v2 = get_bm_knife_vert(kcd, e->v2);
254
255                 knife_add_to_vert_edges(kcd, kfe);
256                 
257                 BLI_ghash_insert(kcd->origedgemap, e, kfe);
258                 
259                 BM_ITER(f, &iter, kcd->em->bm, BM_FACES_OF_EDGE, e) {
260                         knife_append_list(kcd, &kfe->faces, f);
261                         
262                         /* ensures the kedges lst for this f is initialized,
263                          * it automatically adds kfe by itself */
264                         knife_get_face_kedges(kcd, f);
265                 }
266         }
267         
268         return kfe;
269 }
270
271 static void knife_start_cut(knifetool_opdata *kcd)
272 {
273         kcd->prevedge = kcd->curedge;
274         kcd->prevvert = kcd->curvert;
275         kcd->prevbmface = kcd->curbmface;
276         kcd->cutnr++;
277         kcd->prev_is_space = kcd->is_space;
278         kcd->is_space = 0;
279         kcd->prevmval[0] = kcd->vc.mval[0];
280         kcd->prevmval[1] = kcd->vc.mval[1];
281         
282         copy_v3_v3(kcd->prevco, kcd->vertco);
283         copy_v3_v3(kcd->prevcage, kcd->vertcage);
284
285         if (kcd->prevvert == NULL && kcd->prevedge == NULL && is_zero_v3(kcd->prevcage)) {
286                 /* Make prevcage a point on the view ray to mouse closest to a point on model: choose vertex 0 */
287                 float origin[3], ray[3], co[3];
288                 BMVert *v0;
289
290                 knife_input_ray_cast(kcd, kcd->vc.mval, origin, ray);
291                 add_v3_v3v3(co, origin, ray);
292                 v0 = BM_vert_at_index(kcd->em->bm, 0);
293                 if (v0) {
294                         closest_to_line_v3(kcd->prevcage, v0->co, co, origin);
295                         copy_v3_v3(kcd->prevco, kcd->prevcage);
296                         copy_v3_v3(kcd->vertcage, kcd->prevcage);
297                         copy_v3_v3(kcd->vertco, kcd->prevco);
298                 }
299         }
300 }
301
302 static Ref *find_ref(ListBase *lb, void *ref)
303 {
304         Ref *ref1;
305         
306         for (ref1 = lb->first; ref1; ref1 = ref1->next) {
307                 if (ref1->ref == ref)
308                         return ref1;
309         }
310         
311         return NULL;
312 }
313
314 static ListBase *knife_get_face_kedges(knifetool_opdata *kcd, BMFace *f)
315 {
316         ListBase *lst = BLI_ghash_lookup(kcd->kedgefacemap, f);
317         
318         if (!lst) {
319                 BMIter iter;
320                 BMEdge *e;
321                 
322                 lst = knife_empty_list(kcd);
323                 
324                 BM_ITER(e, &iter, kcd->em->bm, BM_EDGES_OF_FACE, f) {
325                         knife_append_list(kcd, lst, get_bm_knife_edge(kcd, e));
326                 }
327                 
328                 BLI_ghash_insert(kcd->kedgefacemap, f, lst);
329         }
330         
331         return lst;
332 }
333
334 /* finds the proper face to restrict face fill to */
335 static void knife_find_basef(knifetool_opdata *kcd, KnifeEdge *kfe)
336 {
337         if (!kfe->basef) {
338                 Ref *r1, *r2, *r3, *r4;
339                 
340                 if (kfe->v1->isface || kfe->v2->isface) {
341                         if (kfe->v2->isface)
342                                 kfe->basef = kcd->curbmface;
343                         else 
344                                 kfe->basef = kcd->prevbmface;
345                 }
346                 else {
347                         for (r1 = kfe->v1->edges.first; r1 && !kfe->basef; r1 = r1->next) {
348                                 KnifeEdge *ke1 = r1->ref;
349                                 for (r2 = ke1->faces.first; r2 && !kfe->basef; r2 = r2->next) {
350                                         for (r3 = kfe->v2->edges.first; r3 && !kfe->basef; r3 = r3->next) {
351                                                 KnifeEdge *ke2 = r3->ref;
352                                         
353                                                 for (r4 = ke2->faces.first; r4 && !kfe->basef; r4 = r4->next) {
354                                                         if (r2->ref == r4->ref) {
355                                                                 kfe->basef = r2->ref;
356                                                         }
357                                                 }       
358                                         }
359                                 }
360                         }
361                 }
362                 /* ok, at this point kfe->basef should be set if any valid possibility exists */
363         }
364 }
365
366 static void knife_edge_append_face(knifetool_opdata *kcd, KnifeEdge *kfe, BMFace *f)
367 {
368         knife_append_list(kcd, knife_get_face_kedges(kcd, f), kfe);
369         knife_append_list(kcd, &kfe->faces, f);
370 }
371
372 static KnifeVert *knife_split_edge(knifetool_opdata *kcd, KnifeEdge *kfe, float co[3], KnifeEdge **newkfe_out)
373 {
374         KnifeEdge *newkfe = new_knife_edge(kcd);
375         Ref *ref;
376         float perc, cageco[3];
377         
378         perc = len_v3v3(co, kfe->v1->co) / len_v3v3(kfe->v1->co, kfe->v2->co);
379         interp_v3_v3v3(cageco, kfe->v1->cageco, kfe->v2->cageco, perc);
380         
381         newkfe->v1 = kfe->v1;
382         newkfe->v2 = new_knife_vert(kcd, co, cageco);
383         newkfe->v2->draw = 1;
384         newkfe->basef = kfe->basef;
385         
386         ref = find_ref(&kfe->v1->edges, kfe);
387         BLI_remlink(&kfe->v1->edges, ref);
388         
389         kfe->v1 = newkfe->v2;
390         BLI_addtail(&kfe->v1->edges, ref);
391         
392         for (ref = kfe->faces.first; ref; ref = ref->next)
393                 knife_edge_append_face(kcd, newkfe, ref->ref);
394
395         knife_add_to_vert_edges(kcd, newkfe);
396         
397         newkfe->draw = kfe->draw;
398         newkfe->e = kfe->e;
399         
400         *newkfe_out = newkfe;
401                         
402         return newkfe->v2;
403 }
404
405 static void knife_add_single_cut(knifetool_opdata *kcd)
406 {
407         KnifeEdge *kfe = new_knife_edge(kcd), *kfe2 = NULL, *kfe3 = NULL;
408         
409         if (kcd->prevvert && kcd->prevvert == kcd->curvert)
410                 return;
411         if (kcd->prevedge && kcd->prevedge == kcd->curedge)
412                 return;
413         
414         kfe->draw = 1;
415
416         if (kcd->prevvert) {
417                 kfe->v1 = kcd->prevvert;
418         }
419         else if (kcd->prevedge) {
420                 kfe->v1 = knife_split_edge(kcd, kcd->prevedge, kcd->prevco, &kfe2);
421         }
422         else {
423                 kfe->v1 = new_knife_vert(kcd, kcd->prevco, kcd->prevco);
424                 kfe->v1->draw = kfe->draw = !kcd->prev_is_space;
425                 kfe->v1->inspace = kcd->prev_is_space;
426                 kfe->draw = !kcd->prev_is_space;
427                 kfe->v1->isface = 1;
428         }
429         
430         if (kcd->curvert) {
431                 kfe->v2 = kcd->curvert;
432         }
433         else if (kcd->curedge) {
434                 kfe->v2 = knife_split_edge(kcd, kcd->curedge, kcd->vertco, &kfe3);
435         
436                 kcd->curvert = kfe->v2;
437         }
438         else {
439                 kfe->v2 = new_knife_vert(kcd, kcd->vertco, kcd->vertco);
440                 kfe->v2->draw = !kcd->is_space;
441                 kfe->v2->isface = 1;
442                 kfe->v2->inspace = kcd->is_space;
443                 
444                 if (kcd->is_space)
445                         kfe->draw = 0;
446
447                 kcd->curvert = kfe->v2;
448         }
449         
450         knife_find_basef(kcd, kfe);
451         
452         knife_add_to_vert_edges(kcd, kfe);
453         
454         if (kfe->basef && !find_ref(&kfe->faces, kfe->basef))
455                 knife_edge_append_face(kcd, kfe, kfe->basef);
456
457         /* sanity check to make sure we're in the right edge/face lists */
458         if (kcd->curbmface) {
459                 if (!find_ref(&kfe->faces, kcd->curbmface)) {
460                         knife_edge_append_face(kcd, kfe, kcd->curbmface);
461                 }
462
463                 if (kcd->prevbmface && kcd->prevbmface != kcd->curbmface) {
464                         if (!find_ref(&kfe->faces, kcd->prevbmface)) {
465                                 knife_edge_append_face(kcd, kfe, kcd->prevbmface);
466                         }
467                 }
468         }
469                 
470         /* set up for next cut */
471         kcd->prevbmface = kcd->curbmface;
472         kcd->prevvert = kcd->curvert;
473         kcd->prevedge = kcd->curedge;
474         copy_v3_v3(kcd->prevco, kcd->vertco);
475         copy_v3_v3(kcd->prevcage, kcd->vertcage);
476         kcd->prev_is_space = kcd->is_space;
477         kcd->prevmval[0] = kcd->vc.mval[0];
478         kcd->prevmval[1] = kcd->vc.mval[1];
479 }
480
481 static int verge_linehit(const void *vlh1, const void *vlh2)
482 {
483         const BMEdgeHit *lh1 = vlh1, *lh2 = vlh2;
484
485         if (lh1->l < lh2->l) return -1;
486         else if (lh1->l > lh2->l) return 1;
487         else return 0;
488 }
489
490 static void knife_add_single_cut_through(knifetool_opdata *kcd,
491         KnifeVert *v1, KnifeVert *v2, BMFace *f)
492 {
493         KnifeEdge *kfenew;
494
495         kfenew = new_knife_edge(kcd);
496         kfenew->draw = 1;
497         kfenew->basef = f;
498         kfenew->v1 = v1;
499         kfenew->v2 = v2;
500         kfenew->draw = 1;
501
502         knife_add_to_vert_edges(kcd, kfenew);
503
504         if (!find_ref(&kfenew->faces, f))
505                 knife_edge_append_face(kcd, kfenew, f);
506 }
507
508 static void knife_get_vert_faces(knifetool_opdata *kcd, KnifeVert* kfv, BMFace *facef, ListBase *lst)
509 {
510         BMIter bmiter;
511         BMFace *f;
512
513         if (kfv->isface && facef) {
514                 knife_append_list(kcd, lst, facef);
515         }
516         else if (kfv->v) {
517                 BMesh *bm = kcd->em->bm;
518                 BM_ITER(f, &bmiter, bm, BM_FACES_OF_VERT, kfv->v) {
519                         knife_append_list(kcd, lst, f);
520                 }
521         }
522 }
523
524 static void knife_get_edge_faces(knifetool_opdata *kcd, KnifeEdge* kfe, ListBase *lst)
525 {
526         BMIter bmiter;
527         BMFace *f;
528
529         if (kfe->e) {
530                 BMesh *bm = kcd->em->bm;
531                 BM_ITER(f, &bmiter, bm, BM_FACES_OF_EDGE, kfe->e) {
532                         knife_append_list(kcd, lst, f);
533                 }
534         }
535 }
536
537 /* BMESH_TODO: add more functionality to cut-through:
538  *    - cutting "in face" (e.g., holes) should cut in all faces, not just visible one
539  *    - perhaps improve O(n^2) algorithm used here */
540 static void knife_cut_through(knifetool_opdata *kcd)
541 {
542         BMEdgeHit *lh, *lh2;
543         BMFace *f;
544         KnifeEdge *kfe, *kfe2, *kfe3;
545         KnifeVert *v1, *v2, *firstv = NULL, *lastv = NULL;
546         ListBase firstfaces = {NULL, NULL}, lastfaces = { NULL, NULL};
547         Ref *r, *r2;
548         KnifeEdge **splitkfe;
549         int i, j, found;
550
551         if (!kcd->totlinehit) {
552                 /* if no linehits then no interesting back face stuff to do */
553                 knife_add_single_cut(kcd);
554                 return;
555         }
556
557         qsort(kcd->linehits, kcd->totlinehit, sizeof(BMEdgeHit), verge_linehit);
558         splitkfe = MEM_callocN(kcd->totlinehit * sizeof(KnifeEdge *), "knife_cut_through");
559
560         if (kcd->prevvert) {
561                 if (kcd->prevvert == kcd->curvert)
562                         return;
563                 firstv = kcd->prevvert;
564                 knife_get_vert_faces(kcd, firstv, kcd->prevbmface, &firstfaces);
565         }
566         else if (kcd->prevedge) {
567                 if (kcd->prevedge == kcd->curedge)
568                         return;
569                 firstv = knife_split_edge(kcd, kcd->prevedge, kcd->prevco, &kfe3);
570                 knife_get_edge_faces(kcd, kcd->prevedge, &firstfaces);
571         }
572
573         if (kcd->curvert) {
574                 lastv = kcd->curvert;
575                 knife_get_vert_faces(kcd, lastv, kcd->curbmface, &lastfaces);
576         }
577         else if (kcd->curedge) {
578                 lastv = knife_split_edge(kcd, kcd->curedge, kcd->vertco, &kfe3);
579                 knife_get_edge_faces(kcd, kcd->curedge, &lastfaces);
580         }
581
582         if (firstv) {
583                 /* For each face incident to firstv,
584                  * find the first following linehit (if any) sharing that face and connect */
585                 for (r = firstfaces.first; r; r = r->next ) {
586                         f = r->ref;
587                         found = 0;
588                         for (j = 0, lh2 = kcd->linehits; j < kcd->totlinehit; j++, lh2++) {
589                                 kfe2 = lh2->kfe;
590                                 for (r2 = kfe2->faces.first; r2; r2 = r2->next) {
591                                         if (r2->ref == f) {
592                                                 v2 = splitkfe[j] ? kfe2->v1 : knife_split_edge(kcd, kfe2, lh2->hit, &splitkfe[j]);
593                                                 knife_add_single_cut_through(kcd, firstv, v2, f);
594                                                 found = 1;
595                                                 break;
596                                         }
597                                 }
598                         }
599                         if (!found && lastv) {
600                                 for (r2 = lastfaces.first; r2; r2 = r2->next) {
601                                         if (r2->ref == f) {
602                                                 knife_add_single_cut_through(kcd, firstv, lastv, f);
603                                                 break;
604                                         }
605                                 }
606                         }
607                 }
608         }
609
610         for (i = 0, lh = kcd->linehits; i < kcd->totlinehit; i++, lh++) {
611                 kfe = lh->kfe;
612
613                 /* For each face attached to edge for this linehit,
614                  * find the first following linehit (if any) sharing that face and connect */
615                 for (r = kfe->faces.first; r; r = r->next) {
616                         f = r->ref;
617                         found = 0;
618                         for (j = i + 1, lh2 = lh + 1; j < kcd->totlinehit; j++, lh2++) {
619                                 kfe2 = lh2->kfe;
620                                 for (r2 = kfe2->faces.first; r2; r2 = r2->next) {
621                                         if (r2->ref == f) {
622                                                 v1 = splitkfe[i]? kfe->v1 : knife_split_edge(kcd, kfe, lh->hit, &splitkfe[i]);
623                                                 v2 = splitkfe[j]? kfe2->v1 : knife_split_edge(kcd, kfe2, lh2->hit, &splitkfe[j]);
624                                                 knife_add_single_cut_through(kcd, v1, v2, f);
625                                                 found = 1;
626                                                 break;
627                                         }
628                                 }
629                         }
630                         if (!found && lastv) {
631                                 for (r2 = lastfaces.first; r2; r2 = r2->next) {
632                                         if (r2->ref == f) {
633                                                 v1 = splitkfe[i]? kfe->v1 : knife_split_edge(kcd, kfe, lh->hit, &splitkfe[i]);
634                                                 knife_add_single_cut_through(kcd, v1, lastv, f);
635                                                 break;
636                                         }
637                                 }
638                         }
639                 }
640         }
641
642         MEM_freeN(splitkfe);
643         MEM_freeN(kcd->linehits);
644         kcd->linehits = NULL;
645         kcd->totlinehit = 0;
646
647         /* set up for next cut */
648         kcd->prevbmface = kcd->curbmface;
649         kcd->prevvert = kcd->curvert;
650         kcd->prevedge = kcd->curedge;
651         copy_v3_v3(kcd->prevco, kcd->vertco);
652         copy_v3_v3(kcd->prevcage, kcd->vertcage);
653         kcd->prev_is_space = kcd->is_space;
654         kcd->prevmval[0] = kcd->vc.mval[0];
655         kcd->prevmval[1] = kcd->vc.mval[1];
656 }
657
658 static void knife_add_cut(knifetool_opdata *kcd)
659 {
660         /* BMEditMesh *em = kcd->em;*/ /* UNUSED */
661         knifetool_opdata oldkcd = *kcd;
662         
663         if (kcd->cut_through) {
664                 knife_cut_through(kcd);
665         }
666         else if (kcd->linehits) {
667                 BMEdgeHit *lh, *lastlh, *firstlh;
668                 int i;
669                 
670                 qsort(kcd->linehits, kcd->totlinehit, sizeof(BMEdgeHit), verge_linehit);
671                 
672                 lh = kcd->linehits;
673                 lastlh = firstlh = NULL;
674                 for (i = 0; i < kcd->totlinehit; i++, (lastlh = lh), lh++) {
675                         BMFace *f = lastlh ? lastlh->f : lh->f;
676                         
677                         if (lastlh && len_v3v3(lastlh->hit, lh->hit) == 0.0f) {
678                                 if (!firstlh)
679                                         firstlh = lastlh;
680                                 continue;
681                         }
682                         else if (lastlh && firstlh) {
683                                 if (firstlh->v || lastlh->v) {
684                                         KnifeVert *kfv = firstlh->v ? firstlh->v : lastlh->v;
685                                         
686                                         kcd->prevvert = kfv;
687                                         copy_v3_v3(kcd->prevco, firstlh->hit);
688                                         copy_v3_v3(kcd->prevcage, firstlh->cagehit);
689                                         kcd->prevedge = NULL;
690                                         kcd->prevbmface = f;
691                                 }
692                                 lastlh = firstlh = NULL;
693                         }
694                         
695                         if (len_v3v3(kcd->prevcage, lh->realhit) < FLT_EPSILON * 80)
696                                 continue;
697                         if (len_v3v3(kcd->vertcage, lh->realhit) < FLT_EPSILON * 80)
698                                 continue;
699                         
700                         if (kcd->prev_is_space) {
701                                 kcd->prev_is_space = 0;
702                                 copy_v3_v3(kcd->prevco, lh->hit);
703                                 copy_v3_v3(kcd->prevcage, lh->cagehit);
704                                 kcd->prevedge = lh->kfe;
705                                 kcd->prevbmface = lh->f;
706                                 continue;
707                         }                       
708                         
709                         kcd->is_space = 0;
710                         kcd->curedge = lh->kfe;
711                         kcd->curbmface = lh->f;
712                         kcd->curvert = lh->v;
713                         copy_v3_v3(kcd->vertco, lh->hit);
714                         copy_v3_v3(kcd->vertcage, lh->cagehit);
715
716                         knife_add_single_cut(kcd);
717                 }
718                 
719                 if (oldkcd.is_space) {
720                         kcd->prevbmface = oldkcd.curbmface;
721                         kcd->prevvert = oldkcd.curvert;
722                         kcd->prevedge = oldkcd.curedge;
723                         copy_v3_v3(kcd->prevco, oldkcd.vertco);
724                         copy_v3_v3(kcd->prevcage, oldkcd.vertcage);
725                         kcd->prev_is_space = oldkcd.is_space;
726                 } else {
727                         kcd->curbmface = oldkcd.curbmface;
728                         kcd->curvert = oldkcd.curvert;
729                         kcd->curedge = oldkcd.curedge;
730                         kcd->is_space = oldkcd.is_space;
731                         copy_v3_v3(kcd->vertco, oldkcd.vertco);
732                         copy_v3_v3(kcd->vertcage, oldkcd.vertcage);
733                         
734                         knife_add_single_cut(kcd);
735                 }
736                 
737                 MEM_freeN(kcd->linehits);
738                 kcd->linehits = NULL;
739                 kcd->totlinehit = 0;
740         }
741         else {
742                 knife_add_single_cut(kcd);
743         }
744 }
745
746 static void knife_finish_cut(knifetool_opdata *UNUSED(kcd))
747 {
748
749 }
750
751 static void knifetool_draw_angle_snapping(knifetool_opdata *kcd)
752 {
753         bglMats mats;
754         double u[3], u1[2], u2[2], v1[3], v2[3], dx, dy;
755         double wminx, wminy, wmaxx, wmaxy;
756
757         /* make u the window coords of prevcage */
758         view3d_get_transformation(kcd->ar, kcd->vc.rv3d, kcd->ob, &mats);
759         gluProject(kcd->prevcage[0], kcd->prevcage[1], kcd->prevcage[2],
760                 mats.modelview, mats.projection, mats.viewport,
761                 &u[0], &u[1], &u[2]);
762
763         /* make u1, u2 the points on window going through u at snap angle */
764         wminx = kcd->ar->winrct.xmin;
765         wmaxx = kcd->ar->winrct.xmin + kcd->ar->winx;
766         wminy = kcd->ar->winrct.ymin;
767         wmaxy = kcd->ar->winrct.ymin + kcd->ar->winy;
768
769         switch (kcd->angle_snapping) {
770                 case ANGLE_0:
771                         u1[0] = wminx;
772                         u2[0] = wmaxx;
773                         u1[1] = u2[1] = u[1];
774                         break;
775                 case ANGLE_90:
776                         u1[0] = u2[0] = u[0];
777                         u1[1] = wminy;
778                         u2[1] = wmaxy;
779                         break;
780                 case ANGLE_45:
781                         /* clip against left or bottom */
782                         dx = u[0] - wminx;
783                         dy = u[1] - wminy;
784                         if (dy > dx) {
785                                 u1[0] = wminx;
786                                 u1[1] = u[1] - dx;
787                         }
788                         else {
789                                 u1[0] = u[0] - dy;
790                                 u1[1] = wminy;
791                         }
792                         /* clip against right or top */
793                         dx = wmaxx - u[0];
794                         dy = wmaxy - u[1];
795                         if (dy > dx) {
796                                 u2[0] = wmaxx;
797                                 u2[1] = u[1] + dx;
798                         }
799                         else {
800                                 u2[0] = u[0] + dy;
801                                 u2[1] = wmaxy;
802                         }
803                         break;
804                 case ANGLE_135:
805                         /* clip against right or bottom */
806                         dx = wmaxx - u[0];
807                         dy = u[1] - wminy;
808                         if (dy > dx) {
809                                 u1[0] = wmaxx;
810                                 u1[1] = u[1] - dx;
811                         }
812                         else {
813                                 u1[0] = u[0] + dy;
814                                 u1[1] = wminy;
815                         }
816                         /* clip against left or top */
817                         dx = u[0] - wminx;
818                         dy = wmaxy - u[1];
819                         if (dy > dx) {
820                                 u2[0] = wminx;
821                                 u2[1] = u[1] + dx;
822                         }
823                         else {
824                                 u2[0] = u[0] - dy;
825                                 u2[1] = wmaxy;
826                         }
827                         break;
828                 default:
829                         return;
830         }
831
832         /* unproject u1 and u2 back into object space */
833         gluUnProject(u1[0], u1[1], 0.0,
834                 mats.modelview, mats.projection, mats.viewport,
835                 &v1[0], &v1[1], &v1[2]);
836         gluUnProject(u2[0], u2[1], 0.0,
837                 mats.modelview, mats.projection, mats.viewport,
838                 &v2[0], &v2[1], &v2[2]);
839
840         glColor3f(0.6, 0.6, 0.6);
841         glLineWidth(2.0);
842         glBegin(GL_LINES);
843         glVertex3dv(v1);
844         glVertex3dv(v2);
845         glEnd();
846 }
847
848 /* modal loop selection drawing callback */
849 static void knifetool_draw(const bContext *UNUSED(C), ARegion *UNUSED(ar), void *arg)
850 {
851         knifetool_opdata *kcd = arg;
852         
853         glDisable(GL_DEPTH_TEST);
854         
855         glPolygonOffset(1.0f, 1.0f);
856         
857         glPushMatrix();
858         glMultMatrixf(kcd->ob->obmat);
859         
860         if (kcd->mode == MODE_DRAGGING) {
861                 if (kcd->angle_snapping != ANGLE_FREE)
862                         knifetool_draw_angle_snapping(kcd);
863
864                 glColor3f(0.1, 0.1, 0.1);
865                 glLineWidth(2.0);
866                 
867                 glBegin(GL_LINES);
868                 glVertex3fv(kcd->prevcage);
869                 glVertex3fv(kcd->vertcage);
870                 glEnd();
871                 
872                 glLineWidth(1.0);
873         }
874         
875         if (kcd->curedge) {
876                 glColor3f(0.5, 0.3, 0.15);
877                 glLineWidth(2.0);
878                 
879                 glBegin(GL_LINES);
880                 glVertex3fv(kcd->curedge->v1->cageco);
881                 glVertex3fv(kcd->curedge->v2->cageco);
882                 glEnd();
883                 
884                 glLineWidth(1.0);
885         }
886         else if (kcd->curvert) {
887                 glColor3f(0.8, 0.2, 0.1);
888                 glPointSize(11);
889                 
890                 glBegin(GL_POINTS);
891                 glVertex3fv(kcd->vertcage);
892                 glEnd();
893         }
894         
895         if (kcd->curbmface) {           
896                 glColor3f(0.1, 0.8, 0.05);
897                 glPointSize(9);
898                 
899                 glBegin(GL_POINTS);
900                 glVertex3fv(kcd->vertcage);
901                 glEnd();
902         }
903         
904         if (kcd->totlinehit > 0) {
905                 BMEdgeHit *lh;
906                 int i;
907                 
908                 glEnable(GL_BLEND);
909                 glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
910                 
911                 /* draw any snapped verts first */
912                 glColor4f(0.8, 0.2, 0.1, 0.4);
913                 glPointSize(11);
914                 glBegin(GL_POINTS);
915                 lh = kcd->linehits;
916                 for (i = 0; i < kcd->totlinehit; i++, lh++) {
917                         float sv1[3], sv2[3];
918                         
919                         knife_project_v3(kcd, lh->kfe->v1->cageco, sv1);
920                         knife_project_v3(kcd, lh->kfe->v2->cageco, sv2);
921                         knife_project_v3(kcd, lh->cagehit, lh->schit);
922                         
923                         if (len_v2v2(lh->schit, sv1) < kcd->vthresh / 4.0f) {
924                                 copy_v3_v3(lh->cagehit, lh->kfe->v1->cageco);
925                                 glVertex3fv(lh->cagehit);
926                                 lh->v = lh->kfe->v1;
927                         }
928                         else if (len_v2v2(lh->schit, sv2) < kcd->vthresh / 4.0f) {
929                                 copy_v3_v3(lh->cagehit, lh->kfe->v2->cageco);
930                                 glVertex3fv(lh->cagehit);
931                                 lh->v = lh->kfe->v2;
932                         }
933                 }
934                 glEnd();
935                 
936                 /* now draw the rest */
937                 glColor4f(0.1, 0.8, 0.05, 0.4);
938                 glPointSize(7);
939                 glBegin(GL_POINTS);
940                 lh = kcd->linehits;
941                 for (i = 0; i < kcd->totlinehit; i++, lh++) {
942                         glVertex3fv(lh->cagehit);
943                 }
944                 glEnd();
945                 glDisable(GL_BLEND);
946         }
947         
948         if (kcd->totkedge > 0) {
949                 BLI_mempool_iter iter;
950                 KnifeEdge *kfe;
951                 
952                 glLineWidth(1.0);
953                 glBegin(GL_LINES);
954
955                 BLI_mempool_iternew(kcd->kedges, &iter);
956                 for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
957                         if (!kfe->draw)
958                                 continue;
959                                 
960                         glColor3f(0.2, 0.2, 0.2);
961                         
962                         glVertex3fv(kfe->v1->cageco);
963                         glVertex3fv(kfe->v2->cageco);
964                 }
965                 
966                 glEnd();
967                 glLineWidth(1.0);
968         }
969
970         if (kcd->totkvert > 0) {
971                 BLI_mempool_iter iter;
972                 KnifeVert *kfv;
973                 
974                 glPointSize(5.0);
975                                 
976                 glBegin(GL_POINTS);
977                 BLI_mempool_iternew(kcd->kverts, &iter);
978                 for (kfv = BLI_mempool_iterstep(&iter); kfv; kfv = BLI_mempool_iterstep(&iter)) {
979                         if (!kfv->draw)
980                                 continue;
981                                 
982                         glColor3f(0.6, 0.1, 0.2);
983                         
984                         glVertex3fv(kfv->cageco);
985                 }
986                 
987                 glEnd();
988         }
989
990         glPopMatrix();
991         glEnable(GL_DEPTH_TEST);
992 }
993
994 /* do we need to keep these functions? - campbell */
995
996 static int UNUSED_FUNCTION(kfe_vert_in_edge)(KnifeEdge *e, KnifeVert *v)
997 {
998         return e->v1 == v || e->v2 == v;
999 }
1000
1001 static int UNUSED_FUNCTION(point_on_line)(float p[3], float v1[3], float v2[3])
1002 {
1003         float d = dist_to_line_segment_v3(p, v1, v2);
1004         if (d < 0.01) {
1005                 d = len_v3v3(v1, v2);
1006                 if (d == 0.0)
1007                         return 0;
1008                 
1009                 d = len_v3v3(p, v1) / d;
1010                 
1011                 if (d >= -FLT_EPSILON * 10 || d <= 1.0 + FLT_EPSILON * 10)
1012                         return 1;
1013         }
1014         
1015         return 0;
1016 }
1017
1018 static float len_v3_tri_side_max(const float v1[3], const float v2[3], const float v3[3])
1019 {
1020         const float s1 = len_v3v3(v1, v2);
1021         const float s2 = len_v3v3(v2, v3);
1022         const float s3 = len_v3v3(v3, v1);
1023
1024         return MAX3(s1, s2, s3);
1025 }
1026
1027 static BMEdgeHit *knife_edge_tri_isect(knifetool_opdata *kcd, BMBVHTree *bmtree,
1028                                        const float v1[3],  const float v2[3], const float v3[3],
1029                                        SmallHash *ehash, bglMats *mats, int *count)
1030 {
1031         BVHTree *tree2 = BLI_bvhtree_new(3, FLT_EPSILON * 4, 8, 8), *tree = BMBVH_BVHTree(bmtree);
1032         BMEdgeHit *edges = NULL;
1033         BLI_array_declare(edges);
1034         BVHTreeOverlap *results, *result;
1035         BMLoop **ls;
1036         float cos[9], uv[3], lambda;
1037         unsigned int tot = 0;
1038         int i, j;
1039         
1040         /* for comparing distances, error of intersection depends on triangle scale.
1041          * need to scale down before squaring for accurate comparison */
1042         const float depsilon = 50 * FLT_EPSILON * len_v3_tri_side_max(v1, v2, v3);
1043         const float depsilon_squared = depsilon * depsilon;
1044
1045         copy_v3_v3(cos + 0, v1);
1046         copy_v3_v3(cos + 3, v2);
1047         copy_v3_v3(cos + 6, v3);
1048
1049         BLI_bvhtree_insert(tree2, 0, cos, 3);
1050         BLI_bvhtree_balance(tree2);
1051         
1052         result = results = BLI_bvhtree_overlap(tree, tree2, &tot);
1053         
1054         for (i = 0; i < tot; i++, result++) {
1055                 float p[3];
1056                 
1057                 ls = (BMLoop **)kcd->em->looptris[result->indexA];
1058                 
1059                 for (j = 0; j < 3; j++) {
1060                         BMLoop *l1 = ls[j];
1061                         BMFace *hitf;
1062                         ListBase *lst = knife_get_face_kedges(kcd, l1->f);
1063                         Ref *ref;
1064                         
1065                         for (ref = lst->first; ref; ref = ref->next) {
1066                                 KnifeEdge *kfe = ref->ref;
1067                                 
1068                                 //if (kfe == kcd->curedge || kfe == kcd->prevedge)
1069                                 //      continue;
1070                                 
1071                                 if (isect_line_tri_v3(kfe->v1->cageco, kfe->v2->cageco, v1, v2, v3, &lambda, uv)) {
1072                                         float no[3], view[3], sp[3];
1073                                         
1074                                         interp_v3_v3v3(p, kfe->v1->cageco, kfe->v2->cageco, lambda);
1075                                         
1076                                         if (kcd->curvert && len_squared_v3v3(kcd->curvert->cageco, p) < depsilon_squared)
1077                                                 continue;
1078                                         if (kcd->prevvert && len_squared_v3v3(kcd->prevvert->cageco, p) < depsilon_squared)
1079                                                 continue;
1080                                         if ( len_squared_v3v3(kcd->prevcage, p) < depsilon_squared ||
1081                                              len_squared_v3v3(kcd->vertcage, p) < depsilon_squared)
1082                                         {
1083                                                 continue;
1084                                         }
1085
1086                                         knife_project_v3(kcd, p, sp);
1087                                         view3d_unproject(mats, view, sp[0], sp[1], 0.0f);
1088                                         mul_m4_v3(kcd->ob->imat, view);
1089
1090                                         if (kcd->cut_through) {
1091                                                 hitf = FALSE;
1092                                         }
1093                                         else {
1094                                                 /* check if this point is visible in the viewport */
1095                                                 sub_v3_v3(view, p);
1096                                                 normalize_v3(view);
1097
1098                                                 copy_v3_v3(no, view);
1099                                                 mul_v3_fl(no, 0.003);
1100
1101                                                 /* go towards view a bit */
1102                                                 add_v3_v3(p, no);
1103
1104                                                 /* ray cast */
1105                                                 hitf = BMBVH_RayCast(bmtree, p, no, NULL, NULL);
1106                                         }
1107                                         
1108                                         /* ok, if visible add the new point */
1109                                         if (!hitf && !BLI_smallhash_haskey(ehash, (intptr_t)kfe)) {
1110                                                 BMEdgeHit hit;
1111                                                 
1112                                                 if ( len_squared_v3v3(p, kcd->vertco) < depsilon_squared ||
1113                                                      len_squared_v3v3(p, kcd->prevco) < depsilon_squared)
1114                                                 {
1115                                                         continue;
1116                                                 }
1117                                                 
1118                                                 hit.kfe = kfe;
1119                                                 hit.v = NULL;
1120                                                 
1121                                                 knife_find_basef(kcd, kfe);
1122                                                 hit.f = kfe->basef;
1123                                                 hit.perc = len_v3v3(p, kfe->v1->cageco) / len_v3v3(kfe->v1->cageco, kfe->v2->cageco);
1124                                                 copy_v3_v3(hit.cagehit, p);
1125                                                 
1126                                                 interp_v3_v3v3(p, kfe->v1->co, kfe->v2->co, hit.perc);
1127                                                 copy_v3_v3(hit.realhit, p);
1128                                                 
1129                                                 /* BMESH_TODO: should also snap to vertices */
1130                                                 if (kcd->snap_midpoints) {
1131                                                         float perc = hit.perc;
1132
1133                                                         /* select the closest from the edge endpoints or the midpoint */
1134                                                         if (perc < 0.25f) {
1135                                                                 perc = 0.0f;
1136                                                         }
1137                                                         else if (perc < 0.75f) {
1138                                                                 perc = 0.5f;
1139                                                         }
1140                                                         else {
1141                                                                 perc = 1.0f;
1142                                                         }
1143                                                         
1144                                                         interp_v3_v3v3(hit.hit, kfe->v1->co, kfe->v2->co, perc);
1145                                                         interp_v3_v3v3(hit.cagehit, kfe->v1->cageco, kfe->v2->cageco, perc);
1146                                                 }
1147                                                 else {
1148                                                         copy_v3_v3(hit.hit, p);
1149                                                 }
1150                                                 knife_project_v3(kcd, hit.cagehit, hit.schit);
1151                                                 
1152                                                 BLI_array_append(edges, hit);
1153                                                 BLI_smallhash_insert(ehash, (intptr_t)kfe, NULL);
1154                                         }
1155                                 }
1156                         }
1157                 }
1158         }
1159         
1160         if (results)
1161                 MEM_freeN(results);
1162         
1163         BLI_bvhtree_free(tree2);
1164         *count = BLI_array_count(edges);
1165         
1166         return edges;
1167 }
1168
1169 static void knife_bgl_get_mats(knifetool_opdata *UNUSED(kcd), bglMats *mats)
1170 {
1171         bgl_get_mats(mats);
1172         //copy_m4_m4(mats->modelview, kcd->vc.rv3d->viewmat);
1173         //copy_m4_m4(mats->projection, kcd->vc.rv3d->winmat);
1174 }
1175
1176 /* Finds visible (or all, if cutting through) edges that intersects the current screen drag line */
1177 static void knife_find_line_hits(knifetool_opdata *kcd)
1178 {
1179         bglMats mats;
1180         BMEdgeHit *e1, *e2;
1181         SmallHash hash, *ehash = &hash;
1182         float v1[3], v2[3], v3[3], v4[4], s1[3], s2[3];
1183         int i, c1, c2;
1184                 
1185         knife_bgl_get_mats(kcd, &mats);
1186         
1187         if (kcd->linehits) {
1188                 MEM_freeN(kcd->linehits);
1189                 kcd->linehits = NULL;
1190                 kcd->totlinehit = 0;
1191         }
1192         
1193         copy_v3_v3(v1, kcd->prevcage);
1194         copy_v3_v3(v2, kcd->vertcage);
1195         
1196         /* project screen line's 3d coordinates back into 2d */
1197         knife_project_v3(kcd, v1, s1);
1198         knife_project_v3(kcd, v2, s2);
1199         
1200         if (len_v2v2(s1, s2) < 1)
1201                 return;
1202
1203         /* unproject screen line */
1204         ED_view3d_win_to_segment_clip(kcd->ar, kcd->vc.v3d, s1, v1, v3);
1205         ED_view3d_win_to_segment_clip(kcd->ar, kcd->vc.v3d, s2, v2, v4);
1206                 
1207         mul_m4_v3(kcd->ob->imat, v1);
1208         mul_m4_v3(kcd->ob->imat, v2);
1209         mul_m4_v3(kcd->ob->imat, v3);
1210         mul_m4_v3(kcd->ob->imat, v4);
1211         
1212         BLI_smallhash_init(ehash);
1213         
1214         /* test two triangles of sceen line's plane */
1215         e1 = knife_edge_tri_isect(kcd, kcd->bmbvh, v1, v2, v3, ehash, &mats, &c1);
1216         e2 = knife_edge_tri_isect(kcd, kcd->bmbvh, v2, v3, v4, ehash, &mats, &c2);
1217         if (c1 && c2) {
1218                 e1 = MEM_reallocN(e1, sizeof(BMEdgeHit) * (c1 + c2));
1219                 memcpy(e1 + c1, e2, sizeof(BMEdgeHit) * c2);
1220                 MEM_freeN(e2);
1221         }
1222         else if (c2) {
1223                 e1 = e2;
1224         }
1225         
1226         kcd->linehits = e1;
1227         kcd->totlinehit = c1 + c2;
1228
1229         /* find position along screen line, used for sorting */
1230         for (i = 0; i < kcd->totlinehit; i++) {
1231                 BMEdgeHit *lh = e1 + i;
1232                 
1233                 lh->l = len_v2v2(lh->schit, s1) / len_v2v2(s2, s1);
1234         }
1235         
1236         BLI_smallhash_release(ehash);
1237 }
1238
1239 static void knife_input_ray_cast(knifetool_opdata *kcd, const int mval_i[2],
1240                                  float r_origin[3], float r_ray[3])
1241 {
1242         bglMats mats;
1243         float mval[2], imat[3][3];
1244
1245         knife_bgl_get_mats(kcd, &mats);
1246
1247         mval[0] = (float)mval_i[0];
1248         mval[1] = (float)mval_i[1];
1249
1250         /* unproject to find view ray */
1251         view3d_unproject(&mats, r_origin, mval[0], mval[1], 0.0f);
1252
1253         if (kcd->is_ortho) {
1254                 negate_v3_v3(r_ray, kcd->vc.rv3d->viewinv[2]);
1255         }
1256         else {
1257                 sub_v3_v3v3(r_ray, r_origin, kcd->vc.rv3d->viewinv[3]);
1258         }
1259         normalize_v3(r_ray);
1260
1261         /* transform into object space */
1262         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
1263         copy_m3_m4(imat, kcd->ob->obmat);
1264         invert_m3(imat);
1265
1266         mul_m4_v3(kcd->ob->imat, r_origin);
1267         mul_m3_v3(imat, r_ray);
1268 }
1269
1270
1271 static BMFace *knife_find_closest_face(knifetool_opdata *kcd, float co[3], float cageco[3], int *is_space)
1272 {
1273         BMFace *f;
1274         int dist = KMAXDIST;
1275         float origin[3];
1276         float ray[3];
1277         
1278         /* unproject to find view ray */
1279         knife_input_ray_cast(kcd, kcd->vc.mval, origin, ray);
1280         add_v3_v3v3(co, origin, ray);
1281
1282         f = BMBVH_RayCast(kcd->bmbvh, origin, ray, co, cageco);
1283         
1284         if (is_space)
1285                 *is_space = !f;
1286         
1287         if (!f) {
1288                 /* try to use backbuffer selection method if ray casting failed */
1289                 f = EDBM_findnearestface(&kcd->vc, &dist);
1290                 
1291                 /* cheat for now; just put in the origin instead
1292                  * of a true coordinate on the face.
1293                  * This just puts a point 1.0f infront of the view. */
1294                 add_v3_v3v3(co, origin, ray);
1295         }
1296         
1297         return f;
1298 }
1299
1300 /* find the 2d screen space density of vertices within a radius.  used to scale snapping
1301  * distance for picking edges/verts.*/
1302 static int knife_sample_screen_density(knifetool_opdata *kcd, float radius)
1303 {
1304         BMFace *f;
1305         int is_space;
1306         float co[3], cageco[3], sco[3];
1307         
1308         f = knife_find_closest_face(kcd, co, cageco, &is_space);
1309         
1310         if (f && !is_space) {
1311                 ListBase *lst;
1312                 Ref *ref;
1313                 float dis;
1314                 int c = 0;
1315                 
1316                 knife_project_v3(kcd, cageco, sco);
1317                 
1318                 lst = knife_get_face_kedges(kcd, f);
1319                 for (ref = lst->first; ref; ref = ref->next) {
1320                         KnifeEdge *kfe = ref->ref;
1321                         int i;
1322                         
1323                         for (i = 0; i < 2; i++) {
1324                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1325                                 
1326                                 knife_project_v3(kcd, kfv->cageco, kfv->sco);
1327                                 
1328                                 dis = len_v2v2(kfv->sco, sco);
1329                                 if (dis < radius) {
1330                                         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1331                                                 float vec[3];
1332                                                 
1333                                                 copy_v3_v3(vec, kfv->cageco);
1334                                                 mul_m4_v3(kcd->vc.obedit->obmat, vec);
1335                         
1336                                                 if (ED_view3d_clipping_test(kcd->vc.rv3d, vec, TRUE) == 0) {
1337                                                         c++;
1338                                                 }
1339                                         }
1340                                         else {
1341                                                 c++;
1342                                         }
1343                                 }
1344                         }
1345                 }
1346                 
1347                 return c;
1348         }
1349                 
1350         return 0;
1351 }
1352
1353 /* returns snapping distance for edges/verts, scaled by the density of the
1354  * surrounding mesh (in screen space)*/
1355 static float knife_snap_size(knifetool_opdata *kcd, float maxsize)
1356 {
1357         float density = (float)knife_sample_screen_density(kcd, maxsize * 2.0f);
1358         
1359         density = MAX2(density, 1);
1360         
1361         return MIN2(maxsize / (density * 0.5f), maxsize);
1362 }
1363
1364 /* p is closest point on edge to the mouse cursor */
1365 static KnifeEdge *knife_find_closest_edge(knifetool_opdata *kcd, float p[3], float cagep[3], BMFace **fptr, int *is_space)
1366 {
1367         BMFace *f;
1368         float co[3], cageco[3], sco[3], maxdist = knife_snap_size(kcd, kcd->ethresh);
1369         
1370         if (kcd->ignore_vert_snapping)
1371                 maxdist *= 0.5;
1372
1373         f = knife_find_closest_face(kcd, co, cageco, NULL);
1374         *is_space = !f;
1375         
1376         /* set p to co, in case we don't find anything, means a face cut */
1377         copy_v3_v3(p, co);
1378         copy_v3_v3(cagep, cageco);
1379         
1380         kcd->curbmface = f;
1381         
1382         if (f) {
1383                 KnifeEdge *cure = NULL;
1384                 ListBase *lst;
1385                 Ref *ref;
1386                 float dis, curdis = FLT_MAX;
1387                 
1388                 knife_project_v3(kcd, cageco, sco);
1389                 
1390                 /* look through all edges associated with this face */
1391                 lst = knife_get_face_kedges(kcd, f);
1392                 for (ref = lst->first; ref; ref = ref->next) {
1393                         KnifeEdge *kfe = ref->ref;
1394                         
1395                         /* project edge vertices into screen space */
1396                         knife_project_v3(kcd, kfe->v1->cageco, kfe->v1->sco);
1397                         knife_project_v3(kcd, kfe->v2->cageco, kfe->v2->sco);
1398
1399                         dis = dist_to_line_segment_v2(sco, kfe->v1->sco, kfe->v2->sco);
1400                         if (dis < curdis && dis < maxdist) {
1401                                 if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1402                                         float labda = labda_PdistVL2Dfl(sco, kfe->v1->sco, kfe->v2->sco);
1403                                         float vec[3];
1404                 
1405                                         vec[0] = kfe->v1->cageco[0] + labda*(kfe->v2->cageco[0] - kfe->v1->cageco[0]);
1406                                         vec[1] = kfe->v1->cageco[1] + labda*(kfe->v2->cageco[1] - kfe->v1->cageco[1]);
1407                                         vec[2] = kfe->v1->cageco[2] + labda*(kfe->v2->cageco[2] - kfe->v1->cageco[2]);
1408                                         mul_m4_v3(kcd->vc.obedit->obmat, vec);
1409                 
1410                                         if (ED_view3d_clipping_test(kcd->vc.rv3d, vec, TRUE) == 0) {
1411                                                 cure = kfe;
1412                                                 curdis = dis;
1413                                         }
1414                                 }
1415                                 else {
1416                                         cure = kfe;
1417                                         curdis = dis;
1418                                 }
1419                         }
1420                 }
1421                 
1422                 if (fptr)
1423                         *fptr = f;
1424                 
1425                 if (cure && p) {
1426                         if (!kcd->ignore_edge_snapping || !(cure->e)) {
1427                                 if (kcd->snap_midpoints) {
1428                                         mid_v3_v3v3(p, cure->v1->co, cure->v2->co);
1429                                         mid_v3_v3v3(cagep, cure->v1->cageco, cure->v2->cageco);
1430                                 }
1431                                 else {
1432                                         float d;
1433                                         
1434                                         closest_to_line_segment_v3(cagep, cageco, cure->v1->cageco, cure->v2->cageco);
1435                                         d = len_v3v3(cagep, cure->v1->cageco) / len_v3v3(cure->v1->cageco, cure->v2->cageco);
1436                                         interp_v3_v3v3(p, cure->v1->co, cure->v2->co, d);
1437                                 }
1438                         }
1439                         else {
1440                                 return NULL;
1441                         }
1442                 }
1443                 
1444                 return cure;
1445         }
1446                 
1447         if (fptr)
1448                 *fptr = NULL;
1449         
1450         return NULL;
1451 }
1452
1453 /* find a vertex near the mouse cursor, if it exists */
1454 static KnifeVert *knife_find_closest_vert(knifetool_opdata *kcd, float p[3], float cagep[3], BMFace **fptr, int *is_space)
1455 {
1456         BMFace *f;
1457         float co[3], cageco[3], sco[3], maxdist = knife_snap_size(kcd, kcd->vthresh);
1458         
1459         if (kcd->ignore_vert_snapping)
1460                 maxdist *= 0.5;
1461         
1462         f = knife_find_closest_face(kcd, co, cageco, is_space);
1463         
1464         /* set p to co, in case we don't find anything, means a face cut */
1465         copy_v3_v3(p, co);
1466         copy_v3_v3(cagep, p);
1467         kcd->curbmface = f;
1468         
1469         if (f) {
1470                 ListBase *lst;
1471                 Ref *ref;
1472                 KnifeVert *curv = NULL;
1473                 float dis, curdis = FLT_MAX;
1474                 
1475                 knife_project_v3(kcd, cageco, sco);
1476                 
1477                 lst = knife_get_face_kedges(kcd, f);
1478                 for (ref = lst->first; ref; ref = ref->next) {
1479                         KnifeEdge *kfe = ref->ref;
1480                         int i;
1481                         
1482                         for (i = 0; i < 2; i++) {
1483                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1484                                 
1485                                 knife_project_v3(kcd, kfv->cageco, kfv->sco);
1486                                 
1487                                 dis = len_v2v2(kfv->sco, sco);
1488                                 if (dis < curdis && dis < maxdist) {
1489                                         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1490                                                 float vec[3];
1491                                                 
1492                                                 copy_v3_v3(vec, kfv->cageco);
1493                                                 mul_m4_v3(kcd->vc.obedit->obmat, vec);
1494                         
1495                                                 if (ED_view3d_clipping_test(kcd->vc.rv3d, vec, TRUE) == 0) {
1496                                                         curv = kfv;
1497                                                         curdis = dis;
1498                                                 }
1499                                         }
1500                                         else {
1501                                                 curv = kfv;
1502                                                 curdis = dis;
1503                                         }
1504                                 }
1505                         }
1506                 }
1507                 
1508                 if (!kcd->ignore_vert_snapping || !(curv && curv->v)) {
1509                         if (fptr)
1510                                 *fptr = f;
1511                 
1512                         if (curv && p) {
1513                                 copy_v3_v3(p, curv->co);
1514                                 copy_v3_v3(cagep, curv->cageco);
1515                         }
1516                         
1517                         return curv;
1518                 }
1519                 else {
1520                         if (fptr)
1521                                 *fptr = f;
1522                         
1523                         return NULL;
1524                 }
1525         }
1526                 
1527         if (fptr)
1528                 *fptr = NULL;
1529         
1530         return NULL;
1531 }
1532
1533 static void knife_snap_angle(knifetool_opdata *kcd)
1534 {
1535         int dx, dy;
1536         float w, abs_tan;
1537
1538         dx = kcd->vc.mval[0] - kcd->prevmval[0];
1539         dy = kcd->vc.mval[1] - kcd->prevmval[1];
1540         if (dx == 0 || dy == 0)
1541                 return;
1542
1543         w = (float)dy / (float)dx;
1544         abs_tan = fabsf(w);
1545         if (abs_tan <= 0.4142f) { /* tan(22.5 degrees) = 0.4142 */      
1546                 kcd->angle_snapping = ANGLE_0;
1547                 kcd->vc.mval[1] = kcd->prevmval[1];
1548         }
1549         else if (abs_tan < 2.4142f) { /* tan(67.5 degrees) = 2.4142 */
1550                 if (w > 0) {
1551                         kcd->angle_snapping = ANGLE_45;
1552                         kcd->vc.mval[1] = kcd->prevmval[1] + dx;
1553                 }
1554                 else {
1555                         kcd->angle_snapping = ANGLE_135;
1556                         kcd->vc.mval[1] = kcd->prevmval[1] - dx;
1557                 }
1558         }
1559         else {
1560                 kcd->angle_snapping = ANGLE_90;
1561                 kcd->vc.mval[0] = kcd->prevmval[0];
1562         }
1563 }
1564
1565 /* update active knife edge/vert pointers */
1566 static int knife_update_active(knifetool_opdata *kcd)
1567 {
1568         if (kcd->angle_snapping != ANGLE_FREE && kcd->mode == MODE_DRAGGING)
1569                 knife_snap_angle(kcd);
1570
1571         kcd->curvert = NULL; kcd->curedge = NULL; kcd->curbmface = NULL;
1572         
1573         kcd->curvert = knife_find_closest_vert(kcd, kcd->vertco, kcd->vertcage, &kcd->curbmface, &kcd->is_space);
1574         if (!kcd->curvert) {
1575                 kcd->curedge = knife_find_closest_edge(kcd, kcd->vertco, kcd->vertcage, &kcd->curbmface, &kcd->is_space);
1576         }
1577         
1578         /* if no hits are found this would normally default to (0,0,0) so instead
1579          * get a point at the mouse ray closest to the previous point.
1580          * Note that drawing lines in `free-space` isn't properly supported
1581          * but theres no guarantee (0,0,0) has any geometry either - campbell */
1582         if (kcd->curvert == NULL && kcd->curedge == NULL) {
1583                         float origin[3], ray[3], co[3];
1584
1585                         knife_input_ray_cast(kcd, kcd->vc.mval, origin, ray);
1586                         add_v3_v3v3(co, origin, ray);
1587
1588                         closest_to_line_v3(kcd->vertcage, kcd->prevcage, co, origin);
1589         }
1590
1591         if (kcd->mode == MODE_DRAGGING) {
1592                 knife_find_line_hits(kcd);
1593         }
1594         return 1;
1595 }
1596
1597 #define MARK                    4
1598 #define DEL                             8       
1599 #define VERT_ON_EDGE    16
1600 #define VERT_ORIG               32
1601 #define FACE_FLIP               64
1602 #define BOUNDARY                128
1603 #define FACE_NEW                256
1604
1605 typedef struct facenet_entry {
1606         struct facenet_entry *next, *prev;
1607         KnifeEdge *kfe;
1608 } facenet_entry;
1609
1610 static void rnd_offset_co(float co[3], float scale)
1611 {
1612         int i;
1613         
1614         for (i = 0; i < 3; i++) {
1615                 co[i] += (BLI_drand()-0.5)*scale;
1616         }
1617 }
1618
1619 static void remerge_faces(knifetool_opdata *kcd)
1620 {
1621         BMesh *bm = kcd->em->bm;
1622         SmallHash svisit, *visit = &svisit;
1623         BMIter iter;
1624         BMFace *f;
1625         BMFace **stack = NULL;
1626         BLI_array_declare(stack);
1627         BMFace **faces = NULL;
1628         BLI_array_declare(faces);
1629         BMOperator bmop;
1630         int idx;
1631         
1632         BMO_op_initf(bm, &bmop, "beautify_fill faces=%ff constrain_edges=%fe", FACE_NEW, BOUNDARY);
1633         
1634         BMO_op_exec(bm, &bmop);
1635         BMO_slot_buffer_flag_enable(bm, &bmop, "geomout", FACE_NEW, BM_FACE);
1636         
1637         BMO_op_finish(bm, &bmop);
1638         
1639         BLI_smallhash_init(visit);
1640         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
1641                 BMIter eiter;
1642                 BMEdge *e;
1643                 BMFace *f2;
1644                 
1645                 if (!BMO_elem_flag_test(bm, f, FACE_NEW))
1646                         continue;
1647                 
1648                 if (BLI_smallhash_haskey(visit, (intptr_t)f))
1649                         continue;
1650                 
1651                 BLI_array_empty(stack);
1652                 BLI_array_empty(faces);
1653                 BLI_array_append(stack, f);
1654                 BLI_smallhash_insert(visit, (intptr_t)f, NULL);
1655                 
1656                 do {
1657                         f2 = BLI_array_pop(stack);
1658                         
1659                         BLI_array_append(faces, f2);
1660                         
1661                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_FACE, f2) {
1662                                 BMIter fiter;
1663                                 BMFace *f3;
1664                                 
1665                                 if (BMO_elem_flag_test(bm, e, BOUNDARY))
1666                                         continue;
1667                                 
1668                                 BM_ITER(f3, &fiter, bm, BM_FACES_OF_EDGE, e) {
1669                                         if (!BMO_elem_flag_test(bm, f3, FACE_NEW))
1670                                                 continue;
1671                                         if (BLI_smallhash_haskey(visit, (intptr_t)f3))
1672                                                 continue;
1673                                         
1674                                         BLI_smallhash_insert(visit, (intptr_t)f3, NULL);
1675                                         BLI_array_append(stack, f3);
1676                                 }
1677                         }       
1678                 } while (BLI_array_count(stack) > 0);
1679                 
1680                 if (BLI_array_count(faces) > 0) {
1681                         idx = BM_elem_index_get(faces[0]);
1682                         
1683                         f2 = BM_faces_join(bm, faces, BLI_array_count(faces));
1684                         if (f2) {
1685                                 BMO_elem_flag_enable(bm, f2, FACE_NEW);
1686                                 BM_elem_index_set(f2, idx); /* set_dirty! */ /* BMESH_TODO, check if this is valid or not */
1687                         }
1688                 }
1689         }
1690         /* BMESH_TODO, check if the code above validates the indices */
1691         /* bm->elem_index_dirty &= ~BM_FACE; */
1692         bm->elem_index_dirty |= BM_FACE;
1693
1694         BLI_smallhash_release(visit);
1695
1696         BLI_array_free(stack);
1697         BLI_array_free(faces);
1698 }
1699
1700 /* use edgenet to fill faces.  this is a bit annoying and convoluted.*/
1701 static void knifenet_fill_faces(knifetool_opdata *kcd)
1702 {
1703         BMesh *bm = kcd->em->bm;
1704         BMIter bmiter;
1705         BLI_mempool_iter iter;
1706         BMFace *f;
1707         BMEdge *e;
1708         KnifeVert *kfv;
1709         KnifeEdge *kfe;
1710         facenet_entry *entry;
1711         ListBase *face_nets = MEM_callocN(sizeof(ListBase) * bm->totface, "face_nets");
1712         BMFace **faces = MEM_callocN(sizeof(BMFace *) * bm->totface, "faces knife");
1713         MemArena *arena = BLI_memarena_new(1 << 16, "knifenet_fill_faces");
1714         SmallHash shash;
1715         int i, j, k = 0, totface = bm->totface;
1716         
1717         BMO_push(bm, NULL);
1718         bmesh_edit_begin(bm, BMO_OP_FLAG_UNTAN_MULTIRES);
1719
1720         /* BMESH_TODO this should be valid now, leaving here until we can ensure this - campbell */
1721         i = 0;
1722         BM_ITER(f, &bmiter, bm, BM_FACES_OF_MESH, NULL) {
1723                 BM_elem_index_set(f, i); /* set_inline */
1724                 faces[i] = f;
1725                 i++;
1726         }
1727         bm->elem_index_dirty &= ~BM_FACE;
1728         
1729         BM_ITER(e, &bmiter, bm, BM_EDGES_OF_MESH, NULL) {
1730                 BMO_elem_flag_enable(bm, e, BOUNDARY);
1731         }
1732
1733         /* turn knife verts into real verts, as necessary */
1734         BLI_mempool_iternew(kcd->kverts, &iter);
1735         for (kfv = BLI_mempool_iterstep(&iter); kfv; kfv = BLI_mempool_iterstep(&iter)) {
1736                 if (!kfv->v) {
1737                         /* shouldn't we be at least copying the normal? - if not some comment here should explain why - campbell */
1738                         kfv->v = BM_vert_create(bm, kfv->co, NULL);
1739                         kfv->flag = 1;
1740                         BMO_elem_flag_enable(bm, kfv->v, DEL);
1741                 }
1742                 else {
1743                         kfv->flag = 0;
1744                         BMO_elem_flag_enable(bm, kfv->v, VERT_ORIG);
1745                 }
1746
1747                 BMO_elem_flag_enable(bm, kfv->v, MARK);
1748         }
1749         
1750         /* we want to only do changed faces.  first, go over new edges and add to
1751      * face net lists.*/
1752         i = j = k = 0;
1753         BLI_mempool_iternew(kcd->kedges, &iter);
1754         for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
1755                 Ref *ref;
1756                 if (!kfe->v1 || !kfe->v2 || kfe->v1->inspace || kfe->v2->inspace)
1757                         continue;
1758
1759                 i++;
1760
1761                 if (kfe->e && kfe->v1->v == kfe->e->v1 && kfe->v2->v == kfe->e->v2) {
1762                         kfe->oe = kfe->e;
1763                         continue;
1764                 }
1765                 
1766                 j++;
1767                 
1768                 if (kfe->e) {
1769                         kfe->oe = kfe->e;
1770
1771                         BMO_elem_flag_enable(bm, kfe->e, DEL);
1772                         BMO_elem_flag_disable(bm, kfe->e, BOUNDARY);
1773                         kfe->e = NULL;
1774                 }
1775                 
1776                 kfe->e = BM_edge_create(bm, kfe->v1->v, kfe->v2->v, NULL, TRUE);
1777                 BMO_elem_flag_enable(bm, kfe->e, BOUNDARY);
1778                 
1779                 for (ref = kfe->faces.first; ref; ref = ref->next) {
1780                         f = ref->ref;
1781                         
1782                         entry = BLI_memarena_alloc(arena, sizeof(*entry));
1783                         entry->kfe = kfe;
1784                         BLI_addtail(face_nets + BM_elem_index_get(f), entry);
1785                 }
1786         }
1787         
1788         /* go over original edges, and add to faces with new geometry */
1789         BLI_mempool_iternew(kcd->kedges, &iter);
1790         for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
1791                 Ref *ref;
1792                 
1793                 if (!kfe->v1 || !kfe->v2 || kfe->v1->inspace || kfe->v2->inspace)
1794                         continue;
1795                 if (!(kfe->oe && kfe->v1->v == kfe->oe->v1 && kfe->v2->v == kfe->oe->v2))
1796                         continue;
1797                 
1798                 k++;
1799                 
1800                 BMO_elem_flag_enable(bm, kfe->e, BOUNDARY);
1801                 kfe->oe = kfe->e;
1802                 
1803                 for (ref = kfe->faces.first; ref; ref = ref->next) {
1804                         f = ref->ref;
1805                         
1806                         if (face_nets[BM_elem_index_get(f)].first) {
1807                                 entry = BLI_memarena_alloc(arena, sizeof(*entry));
1808                                 entry->kfe = kfe;
1809                                 BLI_addtail(face_nets + BM_elem_index_get(f), entry);
1810                         }
1811                 }
1812         }
1813         
1814         for (i = 0; i < totface; i++) {
1815                 SmallHash *hash = &shash;
1816                 ScanFillFace *efa;
1817                 ScanFillVert *eve, *lasteve;
1818                 int j;
1819                 float rndscale = FLT_EPSILON * 25;
1820                 
1821                 f = faces[i];
1822                 BLI_smallhash_init(hash);
1823                 
1824                 if (face_nets[i].first)
1825                         BMO_elem_flag_enable(bm, f, DEL);
1826                 
1827                 BLI_begin_edgefill();
1828                 
1829                 for (entry = face_nets[i].first; entry; entry = entry->next) {
1830                         if (!BLI_smallhash_haskey(hash, (intptr_t)entry->kfe->v1)) {
1831                                 eve = BLI_addfillvert(entry->kfe->v1->v->co);
1832                                 eve->poly_nr = 0;
1833                                 rnd_offset_co(eve->co, rndscale);
1834                                 eve->tmp.p = entry->kfe->v1->v;
1835                                 BLI_smallhash_insert(hash, (intptr_t)entry->kfe->v1, eve);
1836                         }
1837
1838                         if (!BLI_smallhash_haskey(hash, (intptr_t)entry->kfe->v2)) {
1839                                 eve = BLI_addfillvert(entry->kfe->v2->v->co);
1840                                 eve->poly_nr = 0;
1841                                 rnd_offset_co(eve->co, rndscale);
1842                                 eve->tmp.p = entry->kfe->v2->v;
1843                                 BLI_smallhash_insert(hash, (intptr_t)entry->kfe->v2, eve);
1844                         }                                                
1845                 }
1846                 
1847                 for (j = 0, entry = face_nets[i].first; entry; entry = entry->next, j++) {
1848                         lasteve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v1);
1849                         eve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v2);
1850                         
1851                         eve->poly_nr++;
1852                         lasteve->poly_nr++;
1853                 }
1854                 
1855                 for (j = 0, entry = face_nets[i].first; entry; entry = entry->next, j++) {
1856                         lasteve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v1);
1857                         eve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v2);
1858                         
1859                         if (eve->poly_nr > 1 && lasteve->poly_nr > 1) {
1860                                 ScanFillEdge *eed;
1861                                 eed = BLI_addfilledge(lasteve, eve);
1862                                 if (entry->kfe->oe)
1863                                         eed->f = FILLBOUNDARY;  /* mark as original boundary edge */
1864                                 
1865                                 BMO_elem_flag_disable(bm, entry->kfe->e->v1, DEL);
1866                                 BMO_elem_flag_disable(bm, entry->kfe->e->v2, DEL);
1867                         }
1868                         else {
1869                                 if (lasteve->poly_nr < 2)
1870                                         BLI_remlink(&fillvertbase, lasteve);
1871                                 if (eve->poly_nr < 2)
1872                                         BLI_remlink(&fillvertbase, eve);
1873                         }
1874                 }
1875                 
1876                 BLI_edgefill(0);
1877                 
1878                 for (efa = fillfacebase.first; efa; efa = efa->next) {
1879                         BMVert *v1 = efa->v3->tmp.p, *v2 = efa->v2->tmp.p, *v3 = efa->v1->tmp.p;
1880                         BMFace *f2;
1881                         BMLoop *l_iter;
1882                         BMVert *verts[3] = {v1, v2, v3};
1883                         
1884                         if (v1 == v2 || v2 == v3 || v1 == v3)
1885                                 continue;
1886                         if (BM_face_exists(bm, verts, 3, &f2))
1887                                 continue;
1888                 
1889                         f2 = BM_face_create_quad_tri(bm,
1890                                                   v1, v2, v3, NULL,
1891                                                   NULL, FALSE);
1892
1893                         BMO_elem_flag_enable(bm, f2, FACE_NEW);
1894                         
1895                         l_iter = BM_FACE_FIRST_LOOP(f2);
1896                         do {
1897                                 BMO_elem_flag_disable(bm, l_iter->e, DEL);
1898                         } while ((l_iter = l_iter->next) != BM_FACE_FIRST_LOOP(f2));
1899         
1900                         BMO_elem_flag_disable(bm, f2, DEL);
1901                         BM_elem_index_set(f2, i); /* set_dirty! */ /* note, not 100% sure this is dirty? need to check */
1902
1903                         BM_face_normal_update(bm, f2);
1904                         if (dot_v3v3(f->no, f2->no) < 0.0f) {
1905                                 BM_face_normal_flip(bm, f2);
1906                         }
1907                 }
1908                 
1909                 BLI_end_edgefill();
1910                 BLI_smallhash_release(hash);
1911         }
1912         bm->elem_index_dirty |= BM_FACE;
1913         
1914         /* interpolate customdata */
1915         BM_ITER(f, &bmiter, bm, BM_FACES_OF_MESH, NULL) {
1916                 BMLoop *l1;
1917                 BMFace *f2;
1918                 BMIter liter1;
1919
1920                 if (!BMO_elem_flag_test(bm, f, FACE_NEW))
1921                         continue;
1922                 
1923                 f2 = faces[BM_elem_index_get(f)];
1924                 if (BM_elem_index_get(f) < 0 || BM_elem_index_get(f) >= totface) {
1925                         fprintf(stderr, "%s: face index out of range! (bmesh internal error)\n", __func__);
1926                 }
1927
1928                 BM_elem_attrs_copy(bm, bm, f2, f);
1929                 
1930                 BM_ITER(l1, &liter1, bm, BM_LOOPS_OF_FACE, f) {
1931                         BM_loop_interp_from_face(bm, l1, f2, TRUE, TRUE);
1932                 }
1933         }
1934
1935         /* merge triangles back into faces */
1936         remerge_faces(kcd);
1937
1938         /* delete left over faces */
1939         BMO_op_callf(bm, "del geom=%ff context=%i", DEL, DEL_ONLYFACES);
1940         BMO_op_callf(bm, "del geom=%fe context=%i", DEL, DEL_EDGES);
1941         BMO_op_callf(bm, "del geom=%fv context=%i", DEL, DEL_VERTS);
1942
1943         if (face_nets) 
1944                 MEM_freeN(face_nets);
1945         if (faces)
1946                 MEM_freeN(faces);
1947         BLI_memarena_free(arena);
1948         
1949         BMO_error_clear(bm); /* remerge_faces sometimes raises errors, so make sure to clear them */
1950
1951         bmesh_edit_end(bm, BMO_OP_FLAG_UNTAN_MULTIRES);
1952         BMO_pop(bm);
1953 }
1954
1955 /* called on tool confirmation */
1956 static void knifetool_finish(bContext *C, wmOperator *op)
1957 {
1958         knifetool_opdata *kcd = op->customdata;
1959         
1960         knifenet_fill_faces(kcd);
1961         
1962         DAG_id_tag_update(kcd->ob->data, OB_RECALC_DATA);
1963         WM_event_add_notifier(C, NC_GEOM|ND_DATA, kcd->ob->data);
1964 }
1965
1966 /* copied from paint_image.c */
1967 static int project_knife_view_clip(View3D *v3d, RegionView3D *rv3d, float *clipsta, float *clipend)
1968 {
1969         int orth = ED_view3d_clip_range_get(v3d, rv3d, clipsta, clipend);
1970
1971         if (orth) { /* only needed for ortho */
1972                 float fac = 2.0f / ((*clipend) - (*clipsta));
1973                 *clipsta *= fac;
1974                 *clipend *= fac;
1975         }
1976
1977         return orth;
1978 }
1979
1980 static void knife_recalc_projmat(knifetool_opdata *kcd)
1981 {
1982         ARegion *ar = CTX_wm_region(kcd->C);
1983         
1984         if (!ar)
1985                 return;
1986         
1987         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
1988         ED_view3d_ob_project_mat_get(ar->regiondata, kcd->ob, kcd->projmat);
1989         //mult_m4_m4m4(kcd->projmat, kcd->vc.rv3d->winmat, kcd->vc.rv3d->viewmat);
1990         
1991         kcd->is_ortho = project_knife_view_clip(kcd->vc.v3d, kcd->vc.rv3d, 
1992                                                 &kcd->clipsta, &kcd->clipend);
1993 }
1994
1995 /* called when modal loop selection is done... */
1996 static void knifetool_exit (bContext *UNUSED(C), wmOperator *op)
1997 {
1998         knifetool_opdata *kcd = op->customdata;
1999         
2000         if (!kcd)
2001                 return;
2002         
2003         /* deactivate the extra drawing stuff in 3D-View */
2004         ED_region_draw_cb_exit(kcd->ar->type, kcd->draw_handle);
2005         
2006         /* free the custom data */
2007         BLI_mempool_destroy(kcd->refs);
2008         BLI_mempool_destroy(kcd->kverts);
2009         BLI_mempool_destroy(kcd->kedges);
2010
2011         BLI_ghash_free(kcd->origedgemap, NULL, NULL);
2012         BLI_ghash_free(kcd->origvertmap, NULL, NULL);
2013         BLI_ghash_free(kcd->kedgefacemap, NULL, NULL);
2014         
2015         BMBVH_FreeBVH(kcd->bmbvh);
2016         BLI_memarena_free(kcd->arena);
2017         
2018         /* tag for redraw */
2019         ED_region_tag_redraw(kcd->ar);
2020
2021         if (kcd->cagecos)
2022                 MEM_freeN(kcd->cagecos);
2023
2024         /* destroy kcd itself */
2025         MEM_freeN(kcd);
2026         op->customdata = NULL;
2027 }
2028
2029 static void cage_mapped_verts_callback(void *userData, int index, float *co, 
2030         float *UNUSED(no_f), short *UNUSED(no_s))
2031 {
2032         void **data = userData;
2033         BMEditMesh *em = data[0];
2034         float (*cagecos)[3] = data[1];
2035         SmallHash *hash = data[2];
2036         
2037         if (index >= 0 && index < em->bm->totvert && !BLI_smallhash_haskey(hash, index)) {
2038                 BLI_smallhash_insert(hash, index, NULL);
2039                 copy_v3_v3(cagecos[index], co);
2040         }
2041 }
2042
2043 /* called when modal loop selection gets set up... */
2044 static int knifetool_init(bContext *C, wmOperator *op, int UNUSED(do_cut))
2045 {
2046         knifetool_opdata *kcd;
2047         Scene *scene = CTX_data_scene(C);
2048         Object *obedit = CTX_data_edit_object(C);
2049         DerivedMesh *cage, *final;
2050         SmallHash shash;
2051         void *data[3];
2052         
2053         /* alloc new customdata */
2054         kcd = op->customdata = MEM_callocN(sizeof(knifetool_opdata), "knifetool Modal Op Data");
2055         
2056         /* assign the drawing handle for drawing preview line... */
2057         kcd->ob = obedit;
2058         kcd->ar = CTX_wm_region(C);
2059         kcd->C = C;
2060         kcd->draw_handle = ED_region_draw_cb_activate(kcd->ar->type, knifetool_draw, kcd, REGION_DRAW_POST_VIEW);
2061         em_setup_viewcontext(C, &kcd->vc);
2062
2063         kcd->em = BMEdit_FromObject(kcd->ob);
2064
2065         BM_mesh_elem_index_ensure(kcd->em->bm, BM_VERT);
2066
2067         cage = editbmesh_get_derived_cage_and_final(scene, obedit, kcd->em, &final, CD_MASK_DERIVEDMESH);
2068         kcd->cagecos = MEM_callocN(sizeof(float) * 3 * kcd->em->bm->totvert, "knife cagecos");
2069         data[0] = kcd->em;
2070         data[1] = kcd->cagecos;
2071         data[2] = &shash;
2072         
2073         BLI_smallhash_init(&shash);
2074         cage->foreachMappedVert(cage, cage_mapped_verts_callback, data);
2075         BLI_smallhash_release(&shash);
2076         
2077         kcd->bmbvh = BMBVH_NewBVH(kcd->em, BMBVH_USE_CAGE|BMBVH_RETURN_ORIG, scene, obedit);
2078         kcd->arena = BLI_memarena_new(1 << 15, "knife");
2079         kcd->vthresh = KMAXDIST - 1;
2080         kcd->ethresh = KMAXDIST;
2081         
2082         kcd->extend = 1;
2083         
2084         knife_recalc_projmat(kcd);
2085         
2086         ED_region_tag_redraw(kcd->ar);
2087         
2088         kcd->refs = BLI_mempool_create(sizeof(Ref), 1, 2048, 0);
2089         kcd->kverts = BLI_mempool_create(sizeof(KnifeVert), 1, 512, BLI_MEMPOOL_ALLOW_ITER);
2090         kcd->kedges = BLI_mempool_create(sizeof(KnifeEdge), 1, 512, BLI_MEMPOOL_ALLOW_ITER);
2091         
2092         kcd->origedgemap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origedgemap");
2093         kcd->origvertmap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origvertmap");
2094         kcd->kedgefacemap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origvertmap");
2095
2096         /* cut all the way through the mesh if use_occlude_geometry button not pushed */
2097         kcd->cut_through = !(kcd->vc.v3d->flag & V3D_ZBUF_SELECT);
2098
2099         return 1;
2100 }
2101
2102 static int knifetool_cancel (bContext *C, wmOperator *op)
2103 {
2104         /* this is just a wrapper around exit() */
2105         knifetool_exit(C, op);
2106         return OPERATOR_CANCELLED;
2107 }
2108
2109 static int knifetool_invoke (bContext *C, wmOperator *op, wmEvent *evt)
2110 {
2111         knifetool_opdata *kcd;
2112
2113         view3d_operator_needs_opengl(C);
2114
2115         if (!knifetool_init(C, op, 0))
2116                 return OPERATOR_CANCELLED;
2117         
2118         /* add a modal handler for this operator - handles loop selection */
2119         WM_event_add_modal_handler(C, op);
2120
2121         kcd = op->customdata;
2122         kcd->vc.mval[0] = evt->mval[0];
2123         kcd->vc.mval[1] = evt->mval[1];
2124         
2125         return OPERATOR_RUNNING_MODAL;
2126 }
2127
2128 enum {
2129         KNF_MODAL_CANCEL = 1,
2130         KNF_MODAL_CONFIRM,
2131         KNF_MODAL_MIDPOINT_ON,
2132         KNF_MODAL_MIDPOINT_OFF,
2133         KNF_MODAL_NEW_CUT,
2134         KNF_MODEL_IGNORE_SNAP_ON,
2135         KNF_MODEL_IGNORE_SNAP_OFF,
2136         KNF_MODAL_ADD_CUT,
2137         KNF_MODAL_ANGLE_SNAP_TOGGLE
2138 };
2139
2140 wmKeyMap* knifetool_modal_keymap(wmKeyConfig *keyconf)
2141 {
2142         static EnumPropertyItem modal_items[] = {
2143         {KNF_MODAL_CANCEL, "CANCEL", 0, "Cancel", ""},
2144         {KNF_MODAL_CONFIRM, "CONFIRM", 0, "Confirm", ""},
2145         {KNF_MODAL_MIDPOINT_ON, "SNAP_MIDPOINTS_ON", 0, "Snap To Midpoints On", ""},
2146         {KNF_MODAL_MIDPOINT_OFF, "SNAP_MIDPOINTS_OFF", 0, "Snap To Midpoints Off", ""},
2147         {KNF_MODEL_IGNORE_SNAP_ON, "IGNORE_SNAP_ON", 0, "Ignore Snapping On", ""},
2148         {KNF_MODEL_IGNORE_SNAP_OFF, "IGNORE_SNAP_OFF", 0, "Ignore Snapping Off", ""},
2149         {KNF_MODAL_ANGLE_SNAP_TOGGLE, "ANGLE_SNAP_TOGGLE", 0, "Toggle Angle Snapping", ""},
2150         {KNF_MODAL_NEW_CUT, "NEW_CUT", 0, "End Current Cut", ""},
2151         {KNF_MODAL_ADD_CUT, "ADD_CUT", 0, "Add Cut", ""},
2152
2153         {0, NULL, 0, NULL, NULL}};
2154         
2155         wmKeyMap *keymap = WM_modalkeymap_get(keyconf, "Knife Tool Modal Map");
2156         
2157         /* this function is called for each spacetype, only needs to add map once */
2158         if (keymap) return NULL;
2159         
2160         keymap = WM_modalkeymap_add(keyconf, "Knife Tool Modal Map", modal_items);
2161         
2162         /* items for modal map */
2163         WM_modalkeymap_add_item(keymap, ESCKEY,    KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
2164         WM_modalkeymap_add_item(keymap, LEFTMOUSE, KM_PRESS, KM_ANY, 0, KNF_MODAL_ADD_CUT);
2165         WM_modalkeymap_add_item(keymap, RIGHTMOUSE, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
2166         WM_modalkeymap_add_item(keymap, RETKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
2167         WM_modalkeymap_add_item(keymap, PADENTER, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
2168         WM_modalkeymap_add_item(keymap, EKEY, KM_PRESS, 0, 0, KNF_MODAL_NEW_CUT);
2169
2170         WM_modalkeymap_add_item(keymap, LEFTCTRLKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_MIDPOINT_ON);
2171         WM_modalkeymap_add_item(keymap, LEFTCTRLKEY, KM_RELEASE, KM_ANY, 0, KNF_MODAL_MIDPOINT_OFF);
2172         WM_modalkeymap_add_item(keymap, RIGHTCTRLKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_MIDPOINT_ON);
2173         WM_modalkeymap_add_item(keymap, RIGHTCTRLKEY, KM_RELEASE, KM_ANY, 0, KNF_MODAL_MIDPOINT_OFF);
2174
2175         WM_modalkeymap_add_item(keymap, LEFTSHIFTKEY, KM_PRESS, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_ON);
2176         WM_modalkeymap_add_item(keymap, LEFTSHIFTKEY, KM_RELEASE, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_OFF);
2177         WM_modalkeymap_add_item(keymap, RIGHTSHIFTKEY, KM_PRESS, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_ON);
2178         WM_modalkeymap_add_item(keymap, RIGHTSHIFTKEY, KM_RELEASE, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_OFF);
2179         
2180         WM_modalkeymap_add_item(keymap, CKEY, KM_PRESS, 0, 0, KNF_MODAL_ANGLE_SNAP_TOGGLE);
2181
2182         WM_modalkeymap_assign(keymap, "MESH_OT_knifetool");
2183         
2184         return keymap;
2185 }
2186
2187 static int knifetool_modal (bContext *C, wmOperator *op, wmEvent *event)
2188 {
2189         Object *obedit;
2190         knifetool_opdata *kcd = op->customdata;
2191         
2192         if (!C) {
2193                 return OPERATOR_FINISHED;
2194         }
2195         
2196         obedit = CTX_data_edit_object(C);
2197         if (!obedit || obedit->type != OB_MESH || BMEdit_FromObject(obedit) != kcd->em) {
2198                 knifetool_exit(C, op);
2199                 return OPERATOR_FINISHED;
2200         }
2201
2202         view3d_operator_needs_opengl(C);
2203         
2204         if (kcd->mode == MODE_PANNING)
2205                 kcd->mode = kcd->prevmode;
2206         
2207         /* handle modal keymap */
2208         if (event->type == EVT_MODAL_MAP) {
2209                 switch (event->val) {
2210                         case KNF_MODAL_CANCEL:
2211                                 /* finish */
2212                                 ED_region_tag_redraw(kcd->ar);
2213                                 
2214                                 knifetool_exit(C, op);
2215                                 
2216                                 return OPERATOR_CANCELLED;
2217                         case KNF_MODAL_CONFIRM:
2218                                 /* finish */
2219                                 ED_region_tag_redraw(kcd->ar);
2220                                 
2221                                 knifetool_finish(C, op);
2222                                 knifetool_exit(C, op);
2223                                 
2224                                 return OPERATOR_FINISHED;
2225                         case KNF_MODAL_MIDPOINT_ON:
2226                                 kcd->snap_midpoints = 1;
2227
2228                                 knife_recalc_projmat(kcd);
2229                                 knife_update_active(kcd);
2230                                 ED_region_tag_redraw(kcd->ar);
2231                                 break;
2232                         case KNF_MODAL_MIDPOINT_OFF:
2233                                 kcd->snap_midpoints = 0;
2234
2235                                 knife_recalc_projmat(kcd);
2236                                 knife_update_active(kcd);
2237                                 ED_region_tag_redraw(kcd->ar);
2238                                 break;
2239                         case KNF_MODEL_IGNORE_SNAP_ON:
2240                                 ED_region_tag_redraw(kcd->ar);
2241                                 kcd->ignore_vert_snapping = kcd->ignore_edge_snapping = 1;
2242                                 break;
2243                         case KNF_MODEL_IGNORE_SNAP_OFF:
2244                                 ED_region_tag_redraw(kcd->ar);
2245                                 kcd->ignore_vert_snapping = kcd->ignore_edge_snapping = 0;
2246                                 break;
2247                         case KNF_MODAL_ANGLE_SNAP_TOGGLE:
2248                                 kcd->angle_snapping = !kcd->angle_snapping;
2249                                 break;
2250                         case KNF_MODAL_NEW_CUT:
2251                                 ED_region_tag_redraw(kcd->ar);
2252                                 knife_finish_cut(kcd);
2253                                 kcd->mode = MODE_IDLE;
2254                                 break;
2255                         case KNF_MODAL_ADD_CUT:
2256                                 knife_recalc_projmat(kcd);
2257
2258                                 if (kcd->mode == MODE_DRAGGING) {
2259                                         knife_add_cut(kcd);
2260                                         if (!kcd->extend) {
2261                                                 knife_finish_cut(kcd);
2262                                                 kcd->mode = MODE_IDLE;
2263                                         }
2264                                 }
2265                                 else if (kcd->mode != MODE_PANNING) {
2266                                         knife_start_cut(kcd);
2267                                         kcd->mode = MODE_DRAGGING;
2268                                 }
2269                 
2270                                 ED_region_tag_redraw(kcd->ar);
2271                                 break;
2272                         }
2273         }
2274         else { /* non-modal-mapped events */
2275                 switch (event->type) {
2276                         case WHEELUPMOUSE:
2277                         case WHEELDOWNMOUSE:
2278                                 return OPERATOR_PASS_THROUGH;
2279                         case MIDDLEMOUSE:
2280                                 if (event->val != KM_RELEASE) {
2281                                         if (kcd->mode != MODE_PANNING)
2282                                                 kcd->prevmode = kcd->mode;
2283                                         kcd->mode = MODE_PANNING;
2284                                 }
2285                                 else {
2286                                         kcd->mode = kcd->prevmode;
2287                                 }
2288                                 
2289                                 ED_region_tag_redraw(kcd->ar);
2290                                 return OPERATOR_PASS_THROUGH;
2291                                 
2292                         case MOUSEMOVE:  /* mouse moved somewhere to select another loop */
2293                                 if (kcd->mode != MODE_PANNING) {
2294                                         knife_recalc_projmat(kcd);
2295                                         kcd->vc.mval[0] = event->mval[0];
2296                                         kcd->vc.mval[1] = event->mval[1];
2297                                         
2298                                         if (knife_update_active(kcd))                                   
2299                                                 ED_region_tag_redraw(kcd->ar);
2300                                 }
2301         
2302                                 break;
2303                 }
2304         }
2305         
2306         /* keep going until the user confirms */
2307         return OPERATOR_RUNNING_MODAL;
2308 }
2309
2310 void MESH_OT_knifetool (wmOperatorType *ot)
2311 {
2312         /* description */
2313         ot->name = "Knife Topology Tool";
2314         ot->idname = "MESH_OT_knifetool";
2315         ot->description = "Cut new topology";
2316         
2317         /* callbacks */
2318         ot->invoke = knifetool_invoke;
2319         ot->modal = knifetool_modal;
2320         ot->cancel = knifetool_cancel;
2321         ot->poll = ED_operator_editmesh_view3d;
2322         
2323         /* flags */
2324         ot->flag = OPTYPE_REGISTER|OPTYPE_UNDO|OPTYPE_BLOCKING;
2325 }