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