ba0067faaaa4f90d45a94137cd6dbebbe1190ae7
[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(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 || kcd->is_space) {
701                                 kcd->prev_is_space = kcd->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->curbmface = 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                 kcd->curbmface = oldkcd.curbmface;
720                 kcd->curvert = oldkcd.curvert;
721                 kcd->curedge = oldkcd.curedge;
722                 kcd->is_space = oldkcd.is_space;
723                 copy_v3_v3(kcd->vertco, oldkcd.vertco);
724                 copy_v3_v3(kcd->vertcage, oldkcd.vertcage);
725                 
726                 knife_add_single_cut(kcd);
727                 
728                 MEM_freeN(kcd->linehits);
729                 kcd->linehits = NULL;
730                 kcd->totlinehit = 0;
731         }
732         else {
733                 knife_add_single_cut(kcd);
734         }
735 }
736
737 static void knife_finish_cut(knifetool_opdata *UNUSED(kcd))
738 {
739
740 }
741
742 static void knifetool_draw_angle_snapping(knifetool_opdata *kcd)
743 {
744         bglMats mats;
745         double u[3], u1[2], u2[2], v1[3], v2[3], dx, dy;
746         double wminx, wminy, wmaxx, wmaxy;
747
748         /* make u the window coords of prevcage */
749         view3d_get_transformation(kcd->ar, kcd->vc.rv3d, kcd->ob, &mats);
750         gluProject(kcd->prevcage[0], kcd->prevcage[1], kcd->prevcage[2],
751                 mats.modelview, mats.projection, mats.viewport,
752                 &u[0], &u[1], &u[2]);
753
754         /* make u1, u2 the points on window going through u at snap angle */
755         wminx = kcd->ar->winrct.xmin;
756         wmaxx = kcd->ar->winrct.xmin + kcd->ar->winx;
757         wminy = kcd->ar->winrct.ymin;
758         wmaxy = kcd->ar->winrct.ymin + kcd->ar->winy;
759
760         switch (kcd->angle_snapping) {
761                 case ANGLE_0:
762                         u1[0] = wminx;
763                         u2[0] = wmaxx;
764                         u1[1] = u2[1] = u[1];
765                         break;
766                 case ANGLE_90:
767                         u1[0] = u2[0] = u[0];
768                         u1[1] = wminy;
769                         u2[1] = wmaxy;
770                         break;
771                 case ANGLE_45:
772                         /* clip against left or bottom */
773                         dx = u[0] - wminx;
774                         dy = u[1] - wminy;
775                         if (dy > dx) {
776                                 u1[0] = wminx;
777                                 u1[1] = u[1] - dx;
778                         }
779                         else {
780                                 u1[0] = u[0] - dy;
781                                 u1[1] = wminy;
782                         }
783                         /* clip against right or top */
784                         dx = wmaxx - u[0];
785                         dy = wmaxy - u[1];
786                         if (dy > dx) {
787                                 u2[0] = wmaxx;
788                                 u2[1] = u[1] + dx;
789                         }
790                         else {
791                                 u2[0] = u[0] + dy;
792                                 u2[1] = wmaxy;
793                         }
794                         break;
795                 case ANGLE_135:
796                         /* clip against right or bottom */
797                         dx = wmaxx - u[0];
798                         dy = u[1] - wminy;
799                         if (dy > dx) {
800                                 u1[0] = wmaxx;
801                                 u1[1] = u[1] - dx;
802                         }
803                         else {
804                                 u1[0] = u[0] + dy;
805                                 u1[1] = wminy;
806                         }
807                         /* clip against left or top */
808                         dx = u[0] - wminx;
809                         dy = wmaxy - u[1];
810                         if (dy > dx) {
811                                 u2[0] = wminx;
812                                 u2[1] = u[1] + dx;
813                         }
814                         else {
815                                 u2[0] = u[0] - dy;
816                                 u2[1] = wmaxy;
817                         }
818                         break;
819                 default:
820                         return;
821         }
822
823         /* unproject u1 and u2 back into object space */
824         gluUnProject(u1[0], u1[1], 0.0,
825                 mats.modelview, mats.projection, mats.viewport,
826                 &v1[0], &v1[1], &v1[2]);
827         gluUnProject(u2[0], u2[1], 0.0,
828                 mats.modelview, mats.projection, mats.viewport,
829                 &v2[0], &v2[1], &v2[2]);
830
831         glColor3f(0.6, 0.6, 0.6);
832         glLineWidth(2.0);
833         glBegin(GL_LINES);
834         glVertex3dv(v1);
835         glVertex3dv(v2);
836         glEnd();
837 }
838
839 /* modal loop selection drawing callback */
840 static void knifetool_draw(const bContext *UNUSED(C), ARegion *UNUSED(ar), void *arg)
841 {
842         knifetool_opdata *kcd = arg;
843         
844         glDisable(GL_DEPTH_TEST);
845         
846         glPolygonOffset(1.0f, 1.0f);
847         
848         glPushMatrix();
849         glMultMatrixf(kcd->ob->obmat);
850         
851         if (kcd->mode == MODE_DRAGGING) {
852                 if (kcd->angle_snapping != ANGLE_FREE)
853                         knifetool_draw_angle_snapping(kcd);
854
855                 glColor3f(0.1, 0.1, 0.1);
856                 glLineWidth(2.0);
857                 
858                 glBegin(GL_LINES);
859                 glVertex3fv(kcd->prevcage);
860                 glVertex3fv(kcd->vertcage);
861                 glEnd();
862                 
863                 glLineWidth(1.0);
864         }
865         
866         if (kcd->curedge) {
867                 glColor3f(0.5, 0.3, 0.15);
868                 glLineWidth(2.0);
869                 
870                 glBegin(GL_LINES);
871                 glVertex3fv(kcd->curedge->v1->cageco);
872                 glVertex3fv(kcd->curedge->v2->cageco);
873                 glEnd();
874                 
875                 glLineWidth(1.0);
876         }
877         else if (kcd->curvert) {
878                 glColor3f(0.8, 0.2, 0.1);
879                 glPointSize(11);
880                 
881                 glBegin(GL_POINTS);
882                 glVertex3fv(kcd->vertcage);
883                 glEnd();
884         }
885         
886         if (kcd->curbmface) {           
887                 glColor3f(0.1, 0.8, 0.05);
888                 glPointSize(9);
889                 
890                 glBegin(GL_POINTS);
891                 glVertex3fv(kcd->vertcage);
892                 glEnd();
893         }
894         
895         if (kcd->totlinehit > 0) {
896                 BMEdgeHit *lh;
897                 int i;
898                 
899                 glEnable(GL_BLEND);
900                 glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
901                 
902                 /* draw any snapped verts first */
903                 glColor4f(0.8, 0.2, 0.1, 0.4);
904                 glPointSize(11);
905                 glBegin(GL_POINTS);
906                 lh = kcd->linehits;
907                 for (i = 0; i < kcd->totlinehit; i++, lh++) {
908                         float sv1[3], sv2[3];
909                         
910                         knife_project_v3(kcd, lh->kfe->v1->cageco, sv1);
911                         knife_project_v3(kcd, lh->kfe->v2->cageco, sv2);
912                         knife_project_v3(kcd, lh->cagehit, lh->schit);
913                         
914                         if (len_v2v2(lh->schit, sv1) < kcd->vthresh / 4.0f) {
915                                 copy_v3_v3(lh->cagehit, lh->kfe->v1->cageco);
916                                 glVertex3fv(lh->cagehit);
917                                 lh->v = lh->kfe->v1;
918                         }
919                         else if (len_v2v2(lh->schit, sv2) < kcd->vthresh / 4.0f) {
920                                 copy_v3_v3(lh->cagehit, lh->kfe->v2->cageco);
921                                 glVertex3fv(lh->cagehit);
922                                 lh->v = lh->kfe->v2;
923                         }
924                 }
925                 glEnd();
926                 
927                 /* now draw the rest */
928                 glColor4f(0.1, 0.8, 0.05, 0.4);
929                 glPointSize(7);
930                 glBegin(GL_POINTS);
931                 lh = kcd->linehits;
932                 for (i = 0; i < kcd->totlinehit; i++, lh++) {
933                         glVertex3fv(lh->cagehit);
934                 }
935                 glEnd();
936                 glDisable(GL_BLEND);
937         }
938         
939         if (kcd->totkedge > 0) {
940                 BLI_mempool_iter iter;
941                 KnifeEdge *kfe;
942                 
943                 glLineWidth(1.0);
944                 glBegin(GL_LINES);
945
946                 BLI_mempool_iternew(kcd->kedges, &iter);
947                 for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
948                         if (!kfe->draw)
949                                 continue;
950                                 
951                         glColor3f(0.2, 0.2, 0.2);
952                         
953                         glVertex3fv(kfe->v1->cageco);
954                         glVertex3fv(kfe->v2->cageco);
955                 }
956                 
957                 glEnd();
958                 glLineWidth(1.0);
959         }
960
961         if (kcd->totkvert > 0) {
962                 BLI_mempool_iter iter;
963                 KnifeVert *kfv;
964                 
965                 glPointSize(5.0);
966                                 
967                 glBegin(GL_POINTS);
968                 BLI_mempool_iternew(kcd->kverts, &iter);
969                 for (kfv = BLI_mempool_iterstep(&iter); kfv; kfv = BLI_mempool_iterstep(&iter)) {
970                         if (!kfv->draw)
971                                 continue;
972                                 
973                         glColor3f(0.6, 0.1, 0.2);
974                         
975                         glVertex3fv(kfv->cageco);
976                 }
977                 
978                 glEnd();
979         }
980
981         glPopMatrix();
982         glEnable(GL_DEPTH_TEST);
983 }
984
985 /* do we need to keep these functions? - campbell */
986
987 static int UNUSED_FUNCTION(kfe_vert_in_edge)(KnifeEdge *e, KnifeVert *v)
988 {
989         return e->v1 == v || e->v2 == v;
990 }
991
992 static int UNUSED_FUNCTION(point_on_line)(float p[3], float v1[3], float v2[3])
993 {
994         float d = dist_to_line_segment_v3(p, v1, v2);
995         if (d < 0.01) {
996                 d = len_v3v3(v1, v2);
997                 if (d == 0.0)
998                         return 0;
999                 
1000                 d = len_v3v3(p, v1) / d;
1001                 
1002                 if (d >= -FLT_EPSILON * 10 || d <= 1.0 + FLT_EPSILON * 10)
1003                         return 1;
1004         }
1005         
1006         return 0;
1007 }
1008
1009 static float len_v3_tri_side_max(const float v1[3], const float v2[3], const float v3[3])
1010 {
1011         const float s1 = len_v3v3(v1, v2);
1012         const float s2 = len_v3v3(v2, v3);
1013         const float s3 = len_v3v3(v3, v1);
1014
1015         return MAX3(s1, s2, s3);
1016 }
1017
1018 static BMEdgeHit *knife_edge_tri_isect(knifetool_opdata *kcd, BMBVHTree *bmtree,
1019                                        const float v1[3],  const float v2[3], const float v3[3],
1020                                        SmallHash *ehash, bglMats *mats, int *count)
1021 {
1022         BVHTree *tree2 = BLI_bvhtree_new(3, FLT_EPSILON * 4, 8, 8), *tree = BMBVH_BVHTree(bmtree);
1023         BMEdgeHit *edges = NULL;
1024         BLI_array_declare(edges);
1025         BVHTreeOverlap *results, *result;
1026         BMLoop **ls;
1027         float cos[9], uv[3], lambda;
1028         unsigned int tot = 0;
1029         int i, j;
1030         
1031         /* for comparing distances, error of intersection depends on triangle scale.
1032          * need to scale down before squaring for accurate comparison */
1033         const float depsilon = 50 * FLT_EPSILON * len_v3_tri_side_max(v1, v2, v3);
1034         const float depsilon_squared = depsilon * depsilon;
1035
1036         copy_v3_v3(cos + 0, v1);
1037         copy_v3_v3(cos + 3, v2);
1038         copy_v3_v3(cos + 6, v3);
1039
1040         BLI_bvhtree_insert(tree2, 0, cos, 3);
1041         BLI_bvhtree_balance(tree2);
1042         
1043         result = results = BLI_bvhtree_overlap(tree, tree2, &tot);
1044         
1045         for (i = 0; i < tot; i++, result++) {
1046                 float p[3];
1047                 
1048                 ls = (BMLoop **)kcd->em->looptris[result->indexA];
1049                 
1050                 for (j = 0; j < 3; j++) {
1051                         BMLoop *l1 = ls[j];
1052                         BMFace *hitf;
1053                         ListBase *lst = knife_get_face_kedges(kcd, l1->f);
1054                         Ref *ref;
1055                         
1056                         for (ref = lst->first; ref; ref = ref->next) {
1057                                 KnifeEdge *kfe = ref->ref;
1058                                 
1059                                 //if (kfe == kcd->curedge || kfe == kcd->prevedge)
1060                                 //      continue;
1061                                 
1062                                 if (isect_line_tri_v3(kfe->v1->cageco, kfe->v2->cageco, v1, v2, v3, &lambda, uv)) {
1063                                         float no[3], view[3], sp[3];
1064                                         
1065                                         interp_v3_v3v3(p, kfe->v1->cageco, kfe->v2->cageco, lambda);
1066                                         
1067                                         if (kcd->curvert && len_squared_v3v3(kcd->curvert->cageco, p) < depsilon_squared)
1068                                                 continue;
1069                                         if (kcd->prevvert && len_squared_v3v3(kcd->prevvert->cageco, p) < depsilon_squared)
1070                                                 continue;
1071                                         if ( len_squared_v3v3(kcd->prevcage, p) < depsilon_squared ||
1072                                              len_squared_v3v3(kcd->vertcage, p) < depsilon_squared)
1073                                         {
1074                                                 continue;
1075                                         }
1076
1077                                         knife_project_v3(kcd, p, sp);
1078                                         view3d_unproject(mats, view, sp[0], sp[1], 0.0f);
1079                                         mul_m4_v3(kcd->ob->imat, view);
1080
1081                                         if (kcd->cut_through) {
1082                                                 hitf = FALSE;
1083                                         }
1084                                         else {
1085                                                 /* check if this point is visible in the viewport */
1086                                                 sub_v3_v3(view, p);
1087                                                 normalize_v3(view);
1088
1089                                                 copy_v3_v3(no, view);
1090                                                 mul_v3_fl(no, 0.003);
1091
1092                                                 /* go towards view a bit */
1093                                                 add_v3_v3(p, no);
1094
1095                                                 /* ray cast */
1096                                                 hitf = BMBVH_RayCast(bmtree, p, no, NULL, NULL);
1097                                         }
1098                                         
1099                                         /* ok, if visible add the new point */
1100                                         if (!hitf && !BLI_smallhash_haskey(ehash, (intptr_t)kfe)) {
1101                                                 BMEdgeHit hit;
1102                                                 
1103                                                 if ( len_squared_v3v3(p, kcd->vertco) < depsilon_squared ||
1104                                                      len_squared_v3v3(p, kcd->prevco) < depsilon_squared)
1105                                                 {
1106                                                         continue;
1107                                                 }
1108                                                 
1109                                                 hit.kfe = kfe;
1110                                                 hit.v = NULL;
1111                                                 
1112                                                 knife_find_basef(kcd, kfe);
1113                                                 hit.f = kfe->basef;
1114                                                 hit.perc = len_v3v3(p, kfe->v1->cageco) / len_v3v3(kfe->v1->cageco, kfe->v2->cageco);
1115                                                 copy_v3_v3(hit.cagehit, p);
1116                                                 
1117                                                 interp_v3_v3v3(p, kfe->v1->co, kfe->v2->co, hit.perc);
1118                                                 copy_v3_v3(hit.realhit, p);
1119                                                 
1120                                                 /* BMESH_TODO: should also snap to vertices */
1121                                                 if (kcd->snap_midpoints) {
1122                                                         float perc = hit.perc;
1123
1124                                                         /* select the closest from the edge endpoints or the midpoint */
1125                                                         if (perc < 0.25f) {
1126                                                                 perc = 0.0f;
1127                                                         }
1128                                                         else if (perc < 0.75f) {
1129                                                                 perc = 0.5f;
1130                                                         }
1131                                                         else {
1132                                                                 perc = 1.0f;
1133                                                         }
1134                                                         
1135                                                         interp_v3_v3v3(hit.hit, kfe->v1->co, kfe->v2->co, perc);
1136                                                         interp_v3_v3v3(hit.cagehit, kfe->v1->cageco, kfe->v2->cageco, perc);
1137                                                 }
1138                                                 else {
1139                                                         copy_v3_v3(hit.hit, p);
1140                                                 }
1141                                                 knife_project_v3(kcd, hit.cagehit, hit.schit);
1142                                                 
1143                                                 BLI_array_append(edges, hit);
1144                                                 BLI_smallhash_insert(ehash, (intptr_t)kfe, NULL);
1145                                         }
1146                                 }
1147                         }
1148                 }
1149         }
1150         
1151         if (results)
1152                 MEM_freeN(results);
1153         
1154         BLI_bvhtree_free(tree2);
1155         *count = BLI_array_count(edges);
1156         
1157         return edges;
1158 }
1159
1160 static void knife_bgl_get_mats(knifetool_opdata *UNUSED(kcd), bglMats *mats)
1161 {
1162         bgl_get_mats(mats);
1163         //copy_m4_m4(mats->modelview, kcd->vc.rv3d->viewmat);
1164         //copy_m4_m4(mats->projection, kcd->vc.rv3d->winmat);
1165 }
1166
1167 /* Finds visible (or all, if cutting through) edges that intersects the current screen drag line */
1168 static void knife_find_line_hits(knifetool_opdata *kcd)
1169 {
1170         bglMats mats;
1171         BMEdgeHit *e1, *e2;
1172         SmallHash hash, *ehash = &hash;
1173         float v1[3], v2[3], v3[3], v4[4], s1[3], s2[3];
1174         int i, c1, c2;
1175                 
1176         knife_bgl_get_mats(kcd, &mats);
1177         
1178         if (kcd->linehits) {
1179                 MEM_freeN(kcd->linehits);
1180                 kcd->linehits = NULL;
1181                 kcd->totlinehit = 0;
1182         }
1183         
1184         copy_v3_v3(v1, kcd->prevcage);
1185         copy_v3_v3(v2, kcd->vertcage);
1186         
1187         /* project screen line's 3d coordinates back into 2d */
1188         knife_project_v3(kcd, v1, s1);
1189         knife_project_v3(kcd, v2, s2);
1190         
1191         if (len_v2v2(s1, s2) < 1)
1192                 return;
1193
1194         /* unproject screen line */
1195         ED_view3d_win_to_segment_clip(kcd->ar, kcd->vc.v3d, s1, v1, v3);
1196         ED_view3d_win_to_segment_clip(kcd->ar, kcd->vc.v3d, s2, v2, v4);
1197                 
1198         mul_m4_v3(kcd->ob->imat, v1);
1199         mul_m4_v3(kcd->ob->imat, v2);
1200         mul_m4_v3(kcd->ob->imat, v3);
1201         mul_m4_v3(kcd->ob->imat, v4);
1202         
1203         BLI_smallhash_init(ehash);
1204         
1205         /* test two triangles of sceen line's plane */
1206         e1 = knife_edge_tri_isect(kcd, kcd->bmbvh, v1, v2, v3, ehash, &mats, &c1);
1207         e2 = knife_edge_tri_isect(kcd, kcd->bmbvh, v2, v3, v4, ehash, &mats, &c2);
1208         if (c1 && c2) {
1209                 e1 = MEM_reallocN(e1, sizeof(BMEdgeHit) * (c1 + c2));
1210                 memcpy(e1 + c1, e2, sizeof(BMEdgeHit) * c2);
1211                 MEM_freeN(e2);
1212         }
1213         else if (c2) {
1214                 e1 = e2;
1215         }
1216         
1217         kcd->linehits = e1;
1218         kcd->totlinehit = c1 + c2;
1219
1220         /* find position along screen line, used for sorting */
1221         for (i = 0; i < kcd->totlinehit; i++) {
1222                 BMEdgeHit *lh = e1 + i;
1223                 
1224                 lh->l = len_v2v2(lh->schit, s1) / len_v2v2(s2, s1);
1225         }
1226         
1227         BLI_smallhash_release(ehash);
1228 }
1229
1230 static void knife_input_ray_cast(knifetool_opdata *kcd, const int mval_i[2],
1231                                  float r_origin[3], float r_ray[3])
1232 {
1233         bglMats mats;
1234         float mval[2], imat[3][3];
1235
1236         knife_bgl_get_mats(kcd, &mats);
1237
1238         mval[0] = (float)mval_i[0];
1239         mval[1] = (float)mval_i[1];
1240
1241         /* unproject to find view ray */
1242         view3d_unproject(&mats, r_origin, mval[0], mval[1], 0.0f);
1243
1244         if (kcd->is_ortho) {
1245                 negate_v3_v3(r_ray, kcd->vc.rv3d->viewinv[2]);
1246         }
1247         else {
1248                 sub_v3_v3v3(r_ray, r_origin, kcd->vc.rv3d->viewinv[3]);
1249         }
1250         normalize_v3(r_ray);
1251
1252         /* transform into object space */
1253         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
1254         copy_m3_m4(imat, kcd->ob->obmat);
1255         invert_m3(imat);
1256
1257         mul_m4_v3(kcd->ob->imat, r_origin);
1258         mul_m3_v3(imat, r_ray);
1259 }
1260
1261
1262 static BMFace *knife_find_closest_face(knifetool_opdata *kcd, float co[3], float cageco[3], int *is_space)
1263 {
1264         BMFace *f;
1265         int dist = KMAXDIST;
1266         float origin[3];
1267         float ray[3];
1268         
1269         /* unproject to find view ray */
1270         knife_input_ray_cast(kcd, kcd->vc.mval, origin, ray);
1271         add_v3_v3v3(co, origin, ray);
1272
1273         f = BMBVH_RayCast(kcd->bmbvh, origin, ray, co, cageco);
1274         
1275         if (is_space)
1276                 *is_space = !f;
1277         
1278         if (!f) {
1279                 /* try to use backbuffer selection method if ray casting failed */
1280                 f = EDBM_findnearestface(&kcd->vc, &dist);
1281                 
1282                 /* cheat for now; just put in the origin instead
1283                  * of a true coordinate on the face.
1284                  * This just puts a point 1.0f infront of the view. */
1285                 add_v3_v3v3(co, origin, ray);
1286         }
1287         
1288         return f;
1289 }
1290
1291 /* find the 2d screen space density of vertices within a radius.  used to scale snapping
1292  * distance for picking edges/verts.*/
1293 static int knife_sample_screen_density(knifetool_opdata *kcd, float radius)
1294 {
1295         BMFace *f;
1296         int is_space;
1297         float co[3], cageco[3], sco[3];
1298         
1299         f = knife_find_closest_face(kcd, co, cageco, &is_space);
1300         
1301         if (f && !is_space) {
1302                 ListBase *lst;
1303                 Ref *ref;
1304                 float dis;
1305                 int c = 0;
1306                 
1307                 knife_project_v3(kcd, cageco, sco);
1308                 
1309                 lst = knife_get_face_kedges(kcd, f);
1310                 for (ref = lst->first; ref; ref = ref->next) {
1311                         KnifeEdge *kfe = ref->ref;
1312                         int i;
1313                         
1314                         for (i = 0; i < 2; i++) {
1315                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1316                                 
1317                                 knife_project_v3(kcd, kfv->cageco, kfv->sco);
1318                                 
1319                                 dis = len_v2v2(kfv->sco, sco);
1320                                 if (dis < radius) {
1321                                         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1322                                                 float vec[3];
1323                                                 
1324                                                 copy_v3_v3(vec, kfv->cageco);
1325                                                 mul_m4_v3(kcd->vc.obedit->obmat, vec);
1326                         
1327                                                 if (ED_view3d_clipping_test(kcd->vc.rv3d, vec, TRUE) == 0) {
1328                                                         c++;
1329                                                 }
1330                                         }
1331                                         else {
1332                                                 c++;
1333                                         }
1334                                 }
1335                         }
1336                 }
1337                 
1338                 return c;
1339         }
1340                 
1341         return 0;
1342 }
1343
1344 /* returns snapping distance for edges/verts, scaled by the density of the
1345  * surrounding mesh (in screen space)*/
1346 static float knife_snap_size(knifetool_opdata *kcd, float maxsize)
1347 {
1348         float density = (float)knife_sample_screen_density(kcd, maxsize * 2.0f);
1349         
1350         density = MAX2(density, 1);
1351         
1352         return MIN2(maxsize / (density * 0.5f), maxsize);
1353 }
1354
1355 /* p is closest point on edge to the mouse cursor */
1356 static KnifeEdge *knife_find_closest_edge(knifetool_opdata *kcd, float p[3], float cagep[3], BMFace **fptr, int *is_space)
1357 {
1358         BMFace *f;
1359         float co[3], cageco[3], sco[3], maxdist = knife_snap_size(kcd, kcd->ethresh);
1360         
1361         if (kcd->ignore_vert_snapping)
1362                 maxdist *= 0.5;
1363
1364         f = knife_find_closest_face(kcd, co, cageco, NULL);
1365         *is_space = !f;
1366         
1367         /* set p to co, in case we don't find anything, means a face cut */
1368         copy_v3_v3(p, co);
1369         copy_v3_v3(cagep, cageco);
1370         
1371         kcd->curbmface = f;
1372         
1373         if (f) {
1374                 KnifeEdge *cure = NULL;
1375                 ListBase *lst;
1376                 Ref *ref;
1377                 float dis, curdis = FLT_MAX;
1378                 
1379                 knife_project_v3(kcd, cageco, sco);
1380                 
1381                 /* look through all edges associated with this face */
1382                 lst = knife_get_face_kedges(kcd, f);
1383                 for (ref = lst->first; ref; ref = ref->next) {
1384                         KnifeEdge *kfe = ref->ref;
1385                         
1386                         /* project edge vertices into screen space */
1387                         knife_project_v3(kcd, kfe->v1->cageco, kfe->v1->sco);
1388                         knife_project_v3(kcd, kfe->v2->cageco, kfe->v2->sco);
1389
1390                         dis = dist_to_line_segment_v2(sco, kfe->v1->sco, kfe->v2->sco);
1391                         if (dis < curdis && dis < maxdist) {
1392                                 if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1393                                         float labda = labda_PdistVL2Dfl(sco, kfe->v1->sco, kfe->v2->sco);
1394                                         float vec[3];
1395                 
1396                                         vec[0] = kfe->v1->cageco[0] + labda*(kfe->v2->cageco[0] - kfe->v1->cageco[0]);
1397                                         vec[1] = kfe->v1->cageco[1] + labda*(kfe->v2->cageco[1] - kfe->v1->cageco[1]);
1398                                         vec[2] = kfe->v1->cageco[2] + labda*(kfe->v2->cageco[2] - kfe->v1->cageco[2]);
1399                                         mul_m4_v3(kcd->vc.obedit->obmat, vec);
1400                 
1401                                         if (ED_view3d_clipping_test(kcd->vc.rv3d, vec, TRUE) == 0) {
1402                                                 cure = kfe;
1403                                                 curdis = dis;
1404                                         }
1405                                 }
1406                                 else {
1407                                         cure = kfe;
1408                                         curdis = dis;
1409                                 }
1410                         }
1411                 }
1412                 
1413                 if (fptr)
1414                         *fptr = f;
1415                 
1416                 if (cure && p) {
1417                         if (!kcd->ignore_edge_snapping || !(cure->e)) {
1418                                 if (kcd->snap_midpoints) {
1419                                         mid_v3_v3v3(p, cure->v1->co, cure->v2->co);
1420                                         mid_v3_v3v3(cagep, cure->v1->cageco, cure->v2->cageco);
1421                                 }
1422                                 else {
1423                                         float d;
1424                                         
1425                                         closest_to_line_segment_v3(cagep, cageco, cure->v1->cageco, cure->v2->cageco);
1426                                         d = len_v3v3(cagep, cure->v1->cageco) / len_v3v3(cure->v1->cageco, cure->v2->cageco);
1427                                         interp_v3_v3v3(p, cure->v1->co, cure->v2->co, d);
1428                                 }
1429                         }
1430                         else {
1431                                 return NULL;
1432                         }
1433                 }
1434                 
1435                 return cure;
1436         }
1437                 
1438         if (fptr)
1439                 *fptr = NULL;
1440         
1441         return NULL;
1442 }
1443
1444 /* find a vertex near the mouse cursor, if it exists */
1445 static KnifeVert *knife_find_closest_vert(knifetool_opdata *kcd, float p[3], float cagep[3], BMFace **fptr, int *is_space)
1446 {
1447         BMFace *f;
1448         float co[3], cageco[3], sco[3], maxdist = knife_snap_size(kcd, kcd->vthresh);
1449         
1450         if (kcd->ignore_vert_snapping)
1451                 maxdist *= 0.5;
1452         
1453         f = knife_find_closest_face(kcd, co, cageco, is_space);
1454         
1455         /* set p to co, in case we don't find anything, means a face cut */
1456         copy_v3_v3(p, co);
1457         copy_v3_v3(cagep, p);
1458         kcd->curbmface = f;
1459         
1460         if (f) {
1461                 ListBase *lst;
1462                 Ref *ref;
1463                 KnifeVert *curv = NULL;
1464                 float dis, curdis = FLT_MAX;
1465                 
1466                 knife_project_v3(kcd, cageco, sco);
1467                 
1468                 lst = knife_get_face_kedges(kcd, f);
1469                 for (ref = lst->first; ref; ref = ref->next) {
1470                         KnifeEdge *kfe = ref->ref;
1471                         int i;
1472                         
1473                         for (i = 0; i < 2; i++) {
1474                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1475                                 
1476                                 knife_project_v3(kcd, kfv->cageco, kfv->sco);
1477                                 
1478                                 dis = len_v2v2(kfv->sco, sco);
1479                                 if (dis < curdis && dis < maxdist) {
1480                                         if (kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1481                                                 float vec[3];
1482                                                 
1483                                                 copy_v3_v3(vec, kfv->cageco);
1484                                                 mul_m4_v3(kcd->vc.obedit->obmat, vec);
1485                         
1486                                                 if (ED_view3d_clipping_test(kcd->vc.rv3d, vec, TRUE) == 0) {
1487                                                         curv = kfv;
1488                                                         curdis = dis;
1489                                                 }
1490                                         }
1491                                         else {
1492                                                 curv = kfv;
1493                                                 curdis = dis;
1494                                         }
1495                                 }
1496                         }
1497                 }
1498                 
1499                 if (!kcd->ignore_vert_snapping || !(curv && curv->v)) {
1500                         if (fptr)
1501                                 *fptr = f;
1502                 
1503                         if (curv && p) {
1504                                 copy_v3_v3(p, curv->co);
1505                                 copy_v3_v3(cagep, curv->cageco);
1506                         }
1507                         
1508                         return curv;
1509                 }
1510                 else {
1511                         if (fptr)
1512                                 *fptr = f;
1513                         
1514                         return NULL;
1515                 }
1516         }
1517                 
1518         if (fptr)
1519                 *fptr = NULL;
1520         
1521         return NULL;
1522 }
1523
1524 static void knife_snap_angle(knifetool_opdata *kcd)
1525 {
1526         int dx, dy;
1527         float w, abs_tan;
1528
1529         dx = kcd->vc.mval[0] - kcd->prevmval[0];
1530         dy = kcd->vc.mval[1] - kcd->prevmval[1];
1531         if (dx == 0 || dy == 0)
1532                 return;
1533
1534         w = (float)dy / (float)dx;
1535         abs_tan = fabsf(w);
1536         if (abs_tan <= 0.4142f) { /* tan(22.5 degrees) = 0.4142 */      
1537                 kcd->angle_snapping = ANGLE_0;
1538                 kcd->vc.mval[1] = kcd->prevmval[1];
1539         }
1540         else if (abs_tan < 2.4142f) { /* tan(67.5 degrees) = 2.4142 */
1541                 if (w > 0) {
1542                         kcd->angle_snapping = ANGLE_45;
1543                         kcd->vc.mval[1] = kcd->prevmval[1] + dx;
1544                 }
1545                 else {
1546                         kcd->angle_snapping = ANGLE_135;
1547                         kcd->vc.mval[1] = kcd->prevmval[1] - dx;
1548                 }
1549         }
1550         else {
1551                 kcd->angle_snapping = ANGLE_90;
1552                 kcd->vc.mval[0] = kcd->prevmval[0];
1553         }
1554 }
1555
1556 /* update active knife edge/vert pointers */
1557 static int knife_update_active(knifetool_opdata *kcd)
1558 {
1559         if (kcd->angle_snapping != ANGLE_FREE && kcd->mode == MODE_DRAGGING)
1560                 knife_snap_angle(kcd);
1561
1562         kcd->curvert = NULL; kcd->curedge = NULL; kcd->curbmface = NULL;
1563         
1564         kcd->curvert = knife_find_closest_vert(kcd, kcd->vertco, kcd->vertcage, &kcd->curbmface, &kcd->is_space);
1565         if (!kcd->curvert) {
1566                 kcd->curedge = knife_find_closest_edge(kcd, kcd->vertco, kcd->vertcage, &kcd->curbmface, &kcd->is_space);
1567         }
1568         
1569         /* if no hits are found this would normally default to (0,0,0) so instead
1570          * get a point at the mouse ray closest to the previous point.
1571          * Note that drawing lines in `free-space` isn't properly supported
1572          * but theres no guarantee (0,0,0) has any geometry either - campell */
1573         if (kcd->curvert == NULL && kcd->curedge == NULL) {
1574                         float origin[3], ray[3], co[3];
1575
1576                         knife_input_ray_cast(kcd, kcd->vc.mval, origin, ray);
1577                         add_v3_v3v3(co, origin, ray);
1578
1579                         closest_to_line_v3(kcd->vertcage, kcd->prevcage, co, origin);
1580         }
1581
1582         if (kcd->mode == MODE_DRAGGING) {
1583                 knife_find_line_hits(kcd);
1584         }
1585         return 1;
1586 }
1587
1588 #define MARK                    4
1589 #define DEL                             8       
1590 #define VERT_ON_EDGE    16
1591 #define VERT_ORIG               32
1592 #define FACE_FLIP               64
1593 #define BOUNDARY                128
1594 #define FACE_NEW                256
1595
1596 typedef struct facenet_entry {
1597         struct facenet_entry *next, *prev;
1598         KnifeEdge *kfe;
1599 } facenet_entry;
1600
1601 static void rnd_offset_co(float co[3], float scale)
1602 {
1603         int i;
1604         
1605         for (i = 0; i < 3; i++) {
1606                 co[i] += (BLI_drand()-0.5)*scale;
1607         }
1608 }
1609
1610 static void remerge_faces(knifetool_opdata *kcd)
1611 {
1612         BMesh *bm = kcd->em->bm;
1613         SmallHash svisit, *visit = &svisit;
1614         BMIter iter;
1615         BMFace *f;
1616         BMFace **stack = NULL;
1617         BLI_array_declare(stack);
1618         BMFace **faces = NULL;
1619         BLI_array_declare(faces);
1620         BMOperator bmop;
1621         int idx;
1622         
1623         BMO_op_initf(bm, &bmop, "beautify_fill faces=%ff constrain_edges=%fe", FACE_NEW, BOUNDARY);
1624         
1625         BMO_op_exec(bm, &bmop);
1626         BMO_slot_buffer_flag_enable(bm, &bmop, "geomout", FACE_NEW, BM_FACE);
1627         
1628         BMO_op_finish(bm, &bmop);
1629         
1630         BLI_smallhash_init(visit);
1631         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
1632                 BMIter eiter;
1633                 BMEdge *e;
1634                 BMFace *f2;
1635                 
1636                 if (!BMO_elem_flag_test(bm, f, FACE_NEW))
1637                         continue;
1638                 
1639                 if (BLI_smallhash_haskey(visit, (intptr_t)f))
1640                         continue;
1641                 
1642                 BLI_array_empty(stack);
1643                 BLI_array_empty(faces);
1644                 BLI_array_append(stack, f);
1645                 BLI_smallhash_insert(visit, (intptr_t)f, NULL);
1646                 
1647                 do {
1648                         f2 = BLI_array_pop(stack);
1649                         
1650                         BLI_array_append(faces, f2);
1651                         
1652                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_FACE, f2) {
1653                                 BMIter fiter;
1654                                 BMFace *f3;
1655                                 
1656                                 if (BMO_elem_flag_test(bm, e, BOUNDARY))
1657                                         continue;
1658                                 
1659                                 BM_ITER(f3, &fiter, bm, BM_FACES_OF_EDGE, e) {
1660                                         if (!BMO_elem_flag_test(bm, f3, FACE_NEW))
1661                                                 continue;
1662                                         if (BLI_smallhash_haskey(visit, (intptr_t)f3))
1663                                                 continue;
1664                                         
1665                                         BLI_smallhash_insert(visit, (intptr_t)f3, NULL);
1666                                         BLI_array_append(stack, f3);
1667                                 }
1668                         }       
1669                 } while (BLI_array_count(stack) > 0);
1670                 
1671                 if (BLI_array_count(faces) > 0) {
1672                         idx = BM_elem_index_get(faces[0]);
1673                         
1674                         f2 = BM_faces_join(bm, faces, BLI_array_count(faces));
1675                         if (f2) {
1676                                 BMO_elem_flag_enable(bm, f2, FACE_NEW);
1677                                 BM_elem_index_set(f2, idx); /* set_dirty! */ /* BMESH_TODO, check if this is valid or not */
1678                         }
1679                 }
1680         }
1681         /* BMESH_TODO, check if the code above validates the indices */
1682         /* bm->elem_index_dirty &= ~BM_FACE; */
1683         bm->elem_index_dirty |= BM_FACE;
1684
1685         BLI_smallhash_release(visit);
1686
1687         BLI_array_free(stack);
1688         BLI_array_free(faces);
1689 }
1690
1691 /* use edgenet to fill faces.  this is a bit annoying and convoluted.*/
1692 static void knifenet_fill_faces(knifetool_opdata *kcd)
1693 {
1694         BMesh *bm = kcd->em->bm;
1695         BMIter bmiter;
1696         BLI_mempool_iter iter;
1697         BMFace *f;
1698         BMEdge *e;
1699         KnifeVert *kfv;
1700         KnifeEdge *kfe;
1701         facenet_entry *entry;
1702         ListBase *face_nets = MEM_callocN(sizeof(ListBase) * bm->totface, "face_nets");
1703         BMFace **faces = MEM_callocN(sizeof(BMFace *) * bm->totface, "faces knife");
1704         MemArena *arena = BLI_memarena_new(1 << 16, "knifenet_fill_faces");
1705         SmallHash shash;
1706         int i, j, k = 0, totface = bm->totface;
1707         
1708         BMO_push(bm, NULL);
1709         bmesh_edit_begin(bm, BMO_OP_FLAG_UNTAN_MULTIRES);
1710
1711         /* BMESH_TODO this should be valid now, leaving here until we can ensure this - campbell */
1712         i = 0;
1713         BM_ITER(f, &bmiter, bm, BM_FACES_OF_MESH, NULL) {
1714                 BM_elem_index_set(f, i); /* set_inline */
1715                 faces[i] = f;
1716                 i++;
1717         }
1718         bm->elem_index_dirty &= ~BM_FACE;
1719         
1720         BM_ITER(e, &bmiter, bm, BM_EDGES_OF_MESH, NULL) {
1721                 BMO_elem_flag_enable(bm, e, BOUNDARY);
1722         }
1723
1724         /* turn knife verts into real verts, as necessary */
1725         BLI_mempool_iternew(kcd->kverts, &iter);
1726         for (kfv = BLI_mempool_iterstep(&iter); kfv; kfv = BLI_mempool_iterstep(&iter)) {
1727                 if (!kfv->v) {
1728                         /* shouldn't we be at least copying the normal? - if not some comment here should explain why - campbell */
1729                         kfv->v = BM_vert_create(bm, kfv->co, NULL);
1730                         kfv->flag = 1;
1731                         BMO_elem_flag_enable(bm, kfv->v, DEL);
1732                 }
1733                 else {
1734                         kfv->flag = 0;
1735                         BMO_elem_flag_enable(bm, kfv->v, VERT_ORIG);
1736                 }
1737
1738                 BMO_elem_flag_enable(bm, kfv->v, MARK);
1739         }
1740         
1741         /* we want to only do changed faces.  first, go over new edges and add to
1742      * face net lists.*/
1743         i = j = k = 0;
1744         BLI_mempool_iternew(kcd->kedges, &iter);
1745         for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
1746                 Ref *ref;
1747                 if (!kfe->v1 || !kfe->v2 || kfe->v1->inspace || kfe->v2->inspace)
1748                         continue;
1749
1750                 i++;
1751
1752                 if (kfe->e && kfe->v1->v == kfe->e->v1 && kfe->v2->v == kfe->e->v2) {
1753                         kfe->oe = kfe->e;
1754                         continue;
1755                 }
1756                 
1757                 j++;
1758                 
1759                 if (kfe->e) {
1760                         kfe->oe = kfe->e;
1761
1762                         BMO_elem_flag_enable(bm, kfe->e, DEL);
1763                         BMO_elem_flag_disable(bm, kfe->e, BOUNDARY);
1764                         kfe->e = NULL;
1765                 }
1766                 
1767                 kfe->e = BM_edge_create(bm, kfe->v1->v, kfe->v2->v, NULL, TRUE);
1768                 BMO_elem_flag_enable(bm, kfe->e, BOUNDARY);
1769                 
1770                 for (ref = kfe->faces.first; ref; ref = ref->next) {
1771                         f = ref->ref;
1772                         
1773                         entry = BLI_memarena_alloc(arena, sizeof(*entry));
1774                         entry->kfe = kfe;
1775                         BLI_addtail(face_nets + BM_elem_index_get(f), entry);
1776                 }
1777         }
1778         
1779         /* go over original edges, and add to faces with new geometry */
1780         BLI_mempool_iternew(kcd->kedges, &iter);
1781         for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
1782                 Ref *ref;
1783                 
1784                 if (!kfe->v1 || !kfe->v2 || kfe->v1->inspace || kfe->v2->inspace)
1785                         continue;
1786                 if (!(kfe->oe && kfe->v1->v == kfe->oe->v1 && kfe->v2->v == kfe->oe->v2))
1787                         continue;
1788                 
1789                 k++;
1790                 
1791                 BMO_elem_flag_enable(bm, kfe->e, BOUNDARY);
1792                 kfe->oe = kfe->e;
1793                 
1794                 for (ref = kfe->faces.first; ref; ref = ref->next) {
1795                         f = ref->ref;
1796                         
1797                         if (face_nets[BM_elem_index_get(f)].first) {
1798                                 entry = BLI_memarena_alloc(arena, sizeof(*entry));
1799                                 entry->kfe = kfe;
1800                                 BLI_addtail(face_nets + BM_elem_index_get(f), entry);
1801                         }
1802                 }
1803         }
1804         
1805         for (i = 0; i < totface; i++) {
1806                 SmallHash *hash = &shash;
1807                 ScanFillFace *efa;
1808                 ScanFillVert *eve, *lasteve;
1809                 int j;
1810                 float rndscale = FLT_EPSILON * 25;
1811                 
1812                 f = faces[i];
1813                 BLI_smallhash_init(hash);
1814                 
1815                 if (face_nets[i].first)
1816                         BMO_elem_flag_enable(bm, f, DEL);
1817                 
1818                 BLI_begin_edgefill();
1819                 
1820                 for (entry = face_nets[i].first; entry; entry = entry->next) {
1821                         if (!BLI_smallhash_haskey(hash, (intptr_t)entry->kfe->v1)) {
1822                                 eve = BLI_addfillvert(entry->kfe->v1->v->co);
1823                                 eve->poly_nr = 0;
1824                                 rnd_offset_co(eve->co, rndscale);
1825                                 eve->tmp.p = entry->kfe->v1->v;
1826                                 BLI_smallhash_insert(hash, (intptr_t)entry->kfe->v1, eve);
1827                         }
1828
1829                         if (!BLI_smallhash_haskey(hash, (intptr_t)entry->kfe->v2)) {
1830                                 eve = BLI_addfillvert(entry->kfe->v2->v->co);
1831                                 eve->poly_nr = 0;
1832                                 rnd_offset_co(eve->co, rndscale);
1833                                 eve->tmp.p = entry->kfe->v2->v;
1834                                 BLI_smallhash_insert(hash, (intptr_t)entry->kfe->v2, eve);
1835                         }                                                
1836                 }
1837                 
1838                 for (j = 0, entry = face_nets[i].first; entry; entry = entry->next, j++) {
1839                         lasteve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v1);
1840                         eve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v2);
1841                         
1842                         eve->poly_nr++;
1843                         lasteve->poly_nr++;
1844                 }
1845                 
1846                 for (j = 0, entry = face_nets[i].first; entry; entry = entry->next, j++) {
1847                         lasteve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v1);
1848                         eve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v2);
1849                         
1850                         if (eve->poly_nr > 1 && lasteve->poly_nr > 1) {
1851                                 ScanFillEdge *eed;
1852                                 eed = BLI_addfilledge(lasteve, eve);
1853                                 if (entry->kfe->oe)
1854                                         eed->f = FILLBOUNDARY;  /* mark as original boundary edge */
1855                                 
1856                                 BMO_elem_flag_disable(bm, entry->kfe->e->v1, DEL);
1857                                 BMO_elem_flag_disable(bm, entry->kfe->e->v2, DEL);
1858                         }
1859                         else {
1860                                 if (lasteve->poly_nr < 2)
1861                                         BLI_remlink(&fillvertbase, lasteve);
1862                                 if (eve->poly_nr < 2)
1863                                         BLI_remlink(&fillvertbase, eve);
1864                         }
1865                 }
1866                 
1867                 BLI_edgefill(0);
1868                 
1869                 for (efa = fillfacebase.first; efa; efa = efa->next) {
1870                         BMVert *v1 = efa->v3->tmp.p, *v2 = efa->v2->tmp.p, *v3 = efa->v1->tmp.p;
1871                         BMFace *f2;
1872                         BMLoop *l_iter;
1873                         BMVert *verts[3] = {v1, v2, v3};
1874                         
1875                         if (v1 == v2 || v2 == v3 || v1 == v3)
1876                                 continue;
1877                         if (BM_face_exists(bm, verts, 3, &f2))
1878                                 continue;
1879                 
1880                         f2 = BM_face_create_quad_tri(bm,
1881                                                   v1, v2, v3, NULL,
1882                                                   NULL, FALSE);
1883
1884                         BMO_elem_flag_enable(bm, f2, FACE_NEW);
1885                         
1886                         l_iter = BM_FACE_FIRST_LOOP(f2);
1887                         do {
1888                                 BMO_elem_flag_disable(bm, l_iter->e, DEL);
1889                         } while ((l_iter = l_iter->next) != BM_FACE_FIRST_LOOP(f2));
1890         
1891                         BMO_elem_flag_disable(bm, f2, DEL);
1892                         BM_elem_index_set(f2, i); /* set_dirty! */ /* note, not 100% sure this is dirty? need to check */
1893
1894                         BM_face_normal_update(bm, f2);
1895                         if (dot_v3v3(f->no, f2->no) < 0.0f) {
1896                                 BM_face_normal_flip(bm, f2);
1897                         }
1898                 }
1899                 
1900                 BLI_end_edgefill();
1901                 BLI_smallhash_release(hash);
1902         }
1903         bm->elem_index_dirty |= BM_FACE;
1904         
1905         /* interpolate customdata */
1906         BM_ITER(f, &bmiter, bm, BM_FACES_OF_MESH, NULL) {
1907                 BMLoop *l1;
1908                 BMFace *f2;
1909                 BMIter liter1;
1910
1911                 if (!BMO_elem_flag_test(bm, f, FACE_NEW))
1912                         continue;
1913                 
1914                 f2 = faces[BM_elem_index_get(f)];
1915                 if (BM_elem_index_get(f) < 0 || BM_elem_index_get(f) >= totface) {
1916                         fprintf(stderr, "%s: face index out of range! (bmesh internal error)\n", __func__);
1917                 }
1918
1919                 BM_elem_attrs_copy(bm, bm, f2, f);
1920                 
1921                 BM_ITER(l1, &liter1, bm, BM_LOOPS_OF_FACE, f) {
1922                         BM_loop_interp_from_face(bm, l1, f2, TRUE, TRUE);
1923                 }
1924         }
1925
1926         /* merge triangles back into faces */
1927         remerge_faces(kcd);
1928
1929         /* delete left over faces */
1930         BMO_op_callf(bm, "del geom=%ff context=%i", DEL, DEL_ONLYFACES);
1931         BMO_op_callf(bm, "del geom=%fe context=%i", DEL, DEL_EDGES);
1932         BMO_op_callf(bm, "del geom=%fv context=%i", DEL, DEL_VERTS);
1933
1934         if (face_nets) 
1935                 MEM_freeN(face_nets);
1936         if (faces)
1937                 MEM_freeN(faces);
1938         BLI_memarena_free(arena);
1939         
1940         BMO_error_clear(bm); /* remerge_faces sometimes raises errors, so make sure to clear them */
1941
1942         bmesh_edit_end(bm, BMO_OP_FLAG_UNTAN_MULTIRES);
1943         BMO_pop(bm);
1944 }
1945
1946 /* called on tool confirmation */
1947 static void knifetool_finish(bContext *C, wmOperator *op)
1948 {
1949         knifetool_opdata *kcd = op->customdata;
1950         
1951         knifenet_fill_faces(kcd);
1952         
1953         DAG_id_tag_update(kcd->ob->data, OB_RECALC_DATA);
1954         WM_event_add_notifier(C, NC_GEOM|ND_DATA, kcd->ob->data);
1955 }
1956
1957 /* copied from paint_image.c */
1958 static int project_knife_view_clip(View3D *v3d, RegionView3D *rv3d, float *clipsta, float *clipend)
1959 {
1960         int orth = ED_view3d_clip_range_get(v3d, rv3d, clipsta, clipend);
1961
1962         if (orth) { /* only needed for ortho */
1963                 float fac = 2.0f / ((*clipend) - (*clipsta));
1964                 *clipsta *= fac;
1965                 *clipend *= fac;
1966         }
1967
1968         return orth;
1969 }
1970
1971 static void knife_recalc_projmat(knifetool_opdata *kcd)
1972 {
1973         ARegion *ar = CTX_wm_region(kcd->C);
1974         
1975         if (!ar)
1976                 return;
1977         
1978         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
1979         ED_view3d_ob_project_mat_get(ar->regiondata, kcd->ob, kcd->projmat);
1980         //mult_m4_m4m4(kcd->projmat, kcd->vc.rv3d->winmat, kcd->vc.rv3d->viewmat);
1981         
1982         kcd->is_ortho = project_knife_view_clip(kcd->vc.v3d, kcd->vc.rv3d, 
1983                                                 &kcd->clipsta, &kcd->clipend);
1984 }
1985
1986 /* called when modal loop selection is done... */
1987 static void knifetool_exit (bContext *UNUSED(C), wmOperator *op)
1988 {
1989         knifetool_opdata *kcd = op->customdata;
1990         
1991         if (!kcd)
1992                 return;
1993         
1994         /* deactivate the extra drawing stuff in 3D-View */
1995         ED_region_draw_cb_exit(kcd->ar->type, kcd->draw_handle);
1996         
1997         /* free the custom data */
1998         BLI_mempool_destroy(kcd->refs);
1999         BLI_mempool_destroy(kcd->kverts);
2000         BLI_mempool_destroy(kcd->kedges);
2001
2002         BLI_ghash_free(kcd->origedgemap, NULL, NULL);
2003         BLI_ghash_free(kcd->origvertmap, NULL, NULL);
2004         BLI_ghash_free(kcd->kedgefacemap, NULL, NULL);
2005         
2006         BMBVH_FreeBVH(kcd->bmbvh);
2007         BLI_memarena_free(kcd->arena);
2008         
2009         /* tag for redraw */
2010         ED_region_tag_redraw(kcd->ar);
2011
2012         if (kcd->cagecos)
2013                 MEM_freeN(kcd->cagecos);
2014
2015         /* destroy kcd itself */
2016         MEM_freeN(kcd);
2017         op->customdata = NULL;
2018 }
2019
2020 static void cage_mapped_verts_callback(void *userData, int index, float *co, 
2021         float *UNUSED(no_f), short *UNUSED(no_s))
2022 {
2023         void **data = userData;
2024         BMEditMesh *em = data[0];
2025         float (*cagecos)[3] = data[1];
2026         SmallHash *hash = data[2];
2027         
2028         if (index >= 0 && index < em->bm->totvert && !BLI_smallhash_haskey(hash, index)) {
2029                 BLI_smallhash_insert(hash, index, NULL);
2030                 copy_v3_v3(cagecos[index], co);
2031         }
2032 }
2033
2034 /* called when modal loop selection gets set up... */
2035 static int knifetool_init(bContext *C, wmOperator *op, int UNUSED(do_cut))
2036 {
2037         knifetool_opdata *kcd;
2038         Scene *scene = CTX_data_scene(C);
2039         Object *obedit = CTX_data_edit_object(C);
2040         DerivedMesh *cage, *final;
2041         SmallHash shash;
2042         void *data[3];
2043         
2044         /* alloc new customdata */
2045         kcd = op->customdata = MEM_callocN(sizeof(knifetool_opdata), "knifetool Modal Op Data");
2046         
2047         /* assign the drawing handle for drawing preview line... */
2048         kcd->ob = obedit;
2049         kcd->ar = CTX_wm_region(C);
2050         kcd->C = C;
2051         kcd->draw_handle = ED_region_draw_cb_activate(kcd->ar->type, knifetool_draw, kcd, REGION_DRAW_POST_VIEW);
2052         em_setup_viewcontext(C, &kcd->vc);
2053
2054         kcd->em = ((Mesh *)kcd->ob->data)->edit_btmesh;
2055
2056         BM_mesh_elem_index_ensure(kcd->em->bm, BM_VERT);
2057
2058         cage = editbmesh_get_derived_cage_and_final(scene, obedit, kcd->em, &final, CD_MASK_DERIVEDMESH);
2059         kcd->cagecos = MEM_callocN(sizeof(float) * 3 * kcd->em->bm->totvert, "knife cagecos");
2060         data[0] = kcd->em;
2061         data[1] = kcd->cagecos;
2062         data[2] = &shash;
2063         
2064         BLI_smallhash_init(&shash);
2065         cage->foreachMappedVert(cage, cage_mapped_verts_callback, data);
2066         BLI_smallhash_release(&shash);
2067         
2068         kcd->bmbvh = BMBVH_NewBVH(kcd->em, BMBVH_USE_CAGE|BMBVH_RETURN_ORIG, scene, obedit);
2069         kcd->arena = BLI_memarena_new(1 << 15, "knife");
2070         kcd->vthresh = KMAXDIST - 1;
2071         kcd->ethresh = KMAXDIST;
2072         
2073         kcd->extend = 1;
2074         
2075         knife_recalc_projmat(kcd);
2076         
2077         ED_region_tag_redraw(kcd->ar);
2078         
2079         kcd->refs = BLI_mempool_create(sizeof(Ref), 1, 2048, FALSE, FALSE);
2080         kcd->kverts = BLI_mempool_create(sizeof(KnifeVert), 1, 512, FALSE, TRUE);
2081         kcd->kedges = BLI_mempool_create(sizeof(KnifeEdge), 1, 512, FALSE, TRUE);
2082         
2083         kcd->origedgemap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origedgemap");
2084         kcd->origvertmap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origvertmap");
2085         kcd->kedgefacemap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origvertmap");
2086
2087         /* cut all the way through the mesh if use_occlude_geometry button not pushed */
2088         kcd->cut_through = !(kcd->vc.v3d->flag & V3D_ZBUF_SELECT);
2089
2090         return 1;
2091 }
2092
2093 static int knifetool_cancel (bContext *C, wmOperator *op)
2094 {
2095         /* this is just a wrapper around exit() */
2096         knifetool_exit(C, op);
2097         return OPERATOR_CANCELLED;
2098 }
2099
2100 static int knifetool_invoke (bContext *C, wmOperator *op, wmEvent *evt)
2101 {
2102         knifetool_opdata *kcd;
2103
2104         view3d_operator_needs_opengl(C);
2105
2106         if (!knifetool_init(C, op, 0))
2107                 return OPERATOR_CANCELLED;
2108         
2109         /* add a modal handler for this operator - handles loop selection */
2110         WM_event_add_modal_handler(C, op);
2111
2112         kcd = op->customdata;
2113         kcd->vc.mval[0] = evt->mval[0];
2114         kcd->vc.mval[1] = evt->mval[1];
2115         
2116         return OPERATOR_RUNNING_MODAL;
2117 }
2118
2119 enum {
2120         KNF_MODAL_CANCEL = 1,
2121         KNF_MODAL_CONFIRM,
2122         KNF_MODAL_MIDPOINT_ON,
2123         KNF_MODAL_MIDPOINT_OFF,
2124         KNF_MODAL_NEW_CUT,
2125         KNF_MODEL_IGNORE_SNAP_ON,
2126         KNF_MODEL_IGNORE_SNAP_OFF,
2127         KNF_MODAL_ADD_CUT,
2128         KNF_MODAL_ANGLE_SNAP_TOGGLE
2129 };
2130
2131 wmKeyMap* knifetool_modal_keymap(wmKeyConfig *keyconf)
2132 {
2133         static EnumPropertyItem modal_items[] = {
2134         {KNF_MODAL_CANCEL, "CANCEL", 0, "Cancel", ""},
2135         {KNF_MODAL_CONFIRM, "CONFIRM", 0, "Confirm", ""},
2136         {KNF_MODAL_MIDPOINT_ON, "SNAP_MIDPOINTS_ON", 0, "Snap To Midpoints On", ""},
2137         {KNF_MODAL_MIDPOINT_OFF, "SNAP_MIDPOINTS_OFF", 0, "Snap To Midpoints Off", ""},
2138         {KNF_MODEL_IGNORE_SNAP_ON, "IGNORE_SNAP_ON", 0, "Ignore Snapping On", ""},
2139         {KNF_MODEL_IGNORE_SNAP_OFF, "IGNORE_SNAP_OFF", 0, "Ignore Snapping Off", ""},
2140         {KNF_MODAL_ANGLE_SNAP_TOGGLE, "ANGLE_SNAP_TOGGLE", 0, "Toggle Angle Snapping", ""},
2141         {KNF_MODAL_NEW_CUT, "NEW_CUT", 0, "End Current Cut", ""},
2142         {KNF_MODAL_ADD_CUT, "ADD_CUT", 0, "Add Cut", ""},
2143
2144         {0, NULL, 0, NULL, NULL}};
2145         
2146         wmKeyMap *keymap = WM_modalkeymap_get(keyconf, "Knife Tool Modal Map");
2147         
2148         /* this function is called for each spacetype, only needs to add map once */
2149         if (keymap) return NULL;
2150         
2151         keymap = WM_modalkeymap_add(keyconf, "Knife Tool Modal Map", modal_items);
2152         
2153         /* items for modal map */
2154         WM_modalkeymap_add_item(keymap, ESCKEY,    KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
2155         WM_modalkeymap_add_item(keymap, LEFTMOUSE, KM_PRESS, KM_ANY, 0, KNF_MODAL_ADD_CUT);
2156         WM_modalkeymap_add_item(keymap, RIGHTMOUSE, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
2157         WM_modalkeymap_add_item(keymap, RETKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
2158         WM_modalkeymap_add_item(keymap, PADENTER, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
2159         WM_modalkeymap_add_item(keymap, EKEY, KM_PRESS, 0, 0, KNF_MODAL_NEW_CUT);
2160
2161         WM_modalkeymap_add_item(keymap, LEFTCTRLKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_MIDPOINT_ON);
2162         WM_modalkeymap_add_item(keymap, LEFTCTRLKEY, KM_RELEASE, KM_ANY, 0, KNF_MODAL_MIDPOINT_OFF);
2163         WM_modalkeymap_add_item(keymap, RIGHTCTRLKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_MIDPOINT_ON);
2164         WM_modalkeymap_add_item(keymap, RIGHTCTRLKEY, KM_RELEASE, KM_ANY, 0, KNF_MODAL_MIDPOINT_OFF);
2165
2166         WM_modalkeymap_add_item(keymap, LEFTSHIFTKEY, KM_PRESS, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_ON);
2167         WM_modalkeymap_add_item(keymap, LEFTSHIFTKEY, KM_RELEASE, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_OFF);
2168         WM_modalkeymap_add_item(keymap, RIGHTSHIFTKEY, KM_PRESS, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_ON);
2169         WM_modalkeymap_add_item(keymap, RIGHTSHIFTKEY, KM_RELEASE, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_OFF);
2170         
2171         WM_modalkeymap_add_item(keymap, CKEY, KM_PRESS, 0, 0, KNF_MODAL_ANGLE_SNAP_TOGGLE);
2172
2173         WM_modalkeymap_assign(keymap, "MESH_OT_knifetool");
2174         
2175         return keymap;
2176 }
2177
2178 static int knifetool_modal (bContext *C, wmOperator *op, wmEvent *event)
2179 {
2180         Object *obedit;
2181         knifetool_opdata *kcd = op->customdata;
2182         
2183         if (!C) {
2184                 return OPERATOR_FINISHED;
2185         }
2186         
2187         obedit = CTX_data_edit_object(C);
2188         if (!obedit || obedit->type != OB_MESH || ((Mesh *)obedit->data)->edit_btmesh != kcd->em) {
2189                 knifetool_exit(C, op);
2190                 return OPERATOR_FINISHED;
2191         }
2192
2193         view3d_operator_needs_opengl(C);
2194         
2195         if (kcd->mode == MODE_PANNING)
2196                 kcd->mode = kcd->prevmode;
2197         
2198         /* handle modal keymap */
2199         if (event->type == EVT_MODAL_MAP) {
2200                 switch (event->val) {
2201                         case KNF_MODAL_CANCEL:
2202                                 /* finish */
2203                                 ED_region_tag_redraw(kcd->ar);
2204                                 
2205                                 knifetool_exit(C, op);
2206                                 
2207                                 return OPERATOR_CANCELLED;
2208                         case KNF_MODAL_CONFIRM:
2209                                 /* finish */
2210                                 ED_region_tag_redraw(kcd->ar);
2211                                 
2212                                 knifetool_finish(C, op);
2213                                 knifetool_exit(C, op);
2214                                 
2215                                 return OPERATOR_FINISHED;
2216                         case KNF_MODAL_MIDPOINT_ON:
2217                                 kcd->snap_midpoints = 1;
2218
2219                                 knife_recalc_projmat(kcd);
2220                                 knife_update_active(kcd);
2221                                 ED_region_tag_redraw(kcd->ar);
2222                                 break;
2223                         case KNF_MODAL_MIDPOINT_OFF:
2224                                 kcd->snap_midpoints = 0;
2225
2226                                 knife_recalc_projmat(kcd);
2227                                 knife_update_active(kcd);
2228                                 ED_region_tag_redraw(kcd->ar);
2229                                 break;
2230                         case KNF_MODEL_IGNORE_SNAP_ON:
2231                                 ED_region_tag_redraw(kcd->ar);
2232                                 kcd->ignore_vert_snapping = kcd->ignore_edge_snapping = 1;
2233                                 break;
2234                         case KNF_MODEL_IGNORE_SNAP_OFF:
2235                                 ED_region_tag_redraw(kcd->ar);
2236                                 kcd->ignore_vert_snapping = kcd->ignore_edge_snapping = 0;
2237                                 break;
2238                         case KNF_MODAL_ANGLE_SNAP_TOGGLE:
2239                                 kcd->angle_snapping = !kcd->angle_snapping;
2240                                 break;
2241                         case KNF_MODAL_NEW_CUT:
2242                                 ED_region_tag_redraw(kcd->ar);
2243                                 knife_finish_cut(kcd);
2244                                 kcd->mode = MODE_IDLE;
2245                                 break;
2246                         case KNF_MODAL_ADD_CUT:
2247                                 knife_recalc_projmat(kcd);
2248
2249                                 if (kcd->mode == MODE_DRAGGING) {
2250                                         knife_add_cut(kcd);
2251                                         if (!kcd->extend) {
2252                                                 knife_finish_cut(kcd);
2253                                                 kcd->mode = MODE_IDLE;
2254                                         }
2255                                 }
2256                                 else if (kcd->mode != MODE_PANNING) {
2257                                         knife_start_cut(kcd);
2258                                         kcd->mode = MODE_DRAGGING;
2259                                 }
2260                 
2261                                 ED_region_tag_redraw(kcd->ar);
2262                                 break;
2263                         }
2264         }
2265         else { /* non-modal-mapped events */
2266                 switch (event->type) {
2267                         case WHEELUPMOUSE:
2268                         case WHEELDOWNMOUSE:
2269                                 return OPERATOR_PASS_THROUGH;
2270                         case MIDDLEMOUSE:
2271                                 if (event->val != KM_RELEASE) {
2272                                         if (kcd->mode != MODE_PANNING)
2273                                                 kcd->prevmode = kcd->mode;
2274                                         kcd->mode = MODE_PANNING;
2275                                 }
2276                                 else {
2277                                         kcd->mode = kcd->prevmode;
2278                                 }
2279                                 
2280                                 ED_region_tag_redraw(kcd->ar);
2281                                 return OPERATOR_PASS_THROUGH;
2282                                 
2283                         case MOUSEMOVE:  /* mouse moved somewhere to select another loop */
2284                                 if (kcd->mode != MODE_PANNING) {
2285                                         knife_recalc_projmat(kcd);
2286                                         kcd->vc.mval[0] = event->mval[0];
2287                                         kcd->vc.mval[1] = event->mval[1];
2288                                         
2289                                         if (knife_update_active(kcd))                                   
2290                                                 ED_region_tag_redraw(kcd->ar);
2291                                 }
2292         
2293                                 break;
2294                 }
2295         }
2296         
2297         /* keep going until the user confirms */
2298         return OPERATOR_RUNNING_MODAL;
2299 }
2300
2301 void MESH_OT_knifetool (wmOperatorType *ot)
2302 {
2303         /* description */
2304         ot->name = "Knife Topology Tool";
2305         ot->idname = "MESH_OT_knifetool";
2306         ot->description = "Cut new topology";
2307         
2308         /* callbacks */
2309         ot->invoke = knifetool_invoke;
2310         ot->modal = knifetool_modal;
2311         ot->cancel = knifetool_cancel;
2312         ot->poll = ED_operator_editmesh_view3d;
2313         
2314         /* flags */
2315         ot->flag = OPTYPE_REGISTER|OPTYPE_UNDO|OPTYPE_BLOCKING;
2316 }