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