68e1389008d2cd95ad89f1c0c2935564a1b9476e
[blender.git] / source / blender / editors / mesh / knifetool.c
1 /**
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. 
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19  *
20  * The Original Code is Copyright (C) 2007 Blender Foundation.
21  * All rights reserved.
22  *
23  * 
24  * Contributor(s): Joseph Eagar, Joshua Leung
25  *
26  * ***** END GPL LICENSE BLOCK *****
27  */
28
29 #include <float.h>
30 #define _USE_MATH_DEFINES
31 #include <math.h>
32 #include <string.h>
33 #include <ctype.h>
34 #include <stdio.h>
35
36 #include "DNA_ID.h"
37 #include "DNA_screen_types.h"
38 #include "DNA_scene_types.h"
39 #include "DNA_userdef_types.h"
40 #include "DNA_object_types.h"
41
42 #include "MEM_guardedalloc.h"
43
44 #include "PIL_time.h"
45
46 #include "BLI_utildefines.h"
47 #include "BLI_blenlib.h"
48 #include "BLI_dynstr.h" /*for WM_operator_pystring */
49 #include "BLI_editVert.h"
50 #include "BLI_array.h"
51 #include "BLI_ghash.h"
52 #include "BLI_memarena.h"
53 #include "BLI_mempool.h"
54 #include "BLI_math.h"
55 #include "BLI_rand.h"
56 #include "BLI_kdopbvh.h"
57 #include "BLI_smallhash.h"
58 #include "BLI_scanfill.h"
59
60 #include "BKE_blender.h"
61 #include "BKE_context.h"
62 #include "BKE_depsgraph.h"
63 #include "BKE_scene.h"
64 #include "BKE_mesh.h"
65 #include "BKE_tessmesh.h"
66 #include "BKE_depsgraph.h"
67
68 #include "BIF_gl.h"
69 #include "BIF_glutil.h" /* for paint cursor */
70
71 #include "IMB_imbuf_types.h"
72
73 #include "ED_screen.h"
74 #include "ED_space_api.h"
75 #include "ED_view3d.h"
76 #include "ED_mesh.h"
77
78 #include "RNA_access.h"
79 #include "RNA_define.h"
80
81 #include "UI_interface.h"
82
83 #include "WM_api.h"
84 #include "WM_types.h"
85
86 #include "mesh_intern.h"
87 #include "editbmesh_bvh.h"
88
89 /* this code here is kindof messy. . .I might need to eventually rework it - joeedh*/
90
91 #define MAXGROUP        30
92 #define KMAXDIST        25      /*max mouse distance from edge before not detecting it*/
93
94 /* knifetool operator */
95 typedef struct KnifeVert {
96         BMVert *v; /*non-NULL if this is an original vert*/
97         ListBase edges;
98
99         float co[3], sco[3]; /*sco is screen coordinates*/
100         short flag, draw, isface, inspace;
101 } KnifeVert;
102
103 typedef struct Ref {
104         struct Ref *next, *prev;
105         void *ref;
106 } Ref;
107
108 typedef struct KnifeEdge {
109         KnifeVert *v1, *v2;
110         BMFace *basef; /*face to restrict face fill to*/
111         ListBase faces;
112         int draw;
113         
114         BMEdge *e, *oe; /*non-NULL if this is an original edge*/
115 } KnifeEdge;
116
117 typedef struct BMEdgeHit {
118         KnifeEdge *kfe;
119         float hit[3];
120         float realhit[3]; /*used in midpoint mode*/
121         float schit[3];
122         float l; /*lambda along 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];
153         float prevco[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         float clipsta, clipend;
173         
174         enum {
175                 MODE_IDLE,
176                 MODE_DRAGGING,
177                 MODE_CONNECT,
178                 MODE_PANNING,
179         } mode;
180         
181         int snap_midpoints, prevmode, extend;
182         int ignore_edge_snapping, ignore_vert_snapping;
183         
184         int is_space, prev_is_space; /*1 if current cut location, vertco, isn't on the mesh*/
185 } knifetool_opdata;
186
187 static ListBase *knife_get_face_kedges(knifetool_opdata *kcd, BMFace *f);
188
189 static void knife_project_v3(knifetool_opdata *kcd, float co[3], float sco[3])
190 {
191         if (kcd->is_ortho) {
192                 mul_v3_m4v3(sco, kcd->projmat, co);
193                 
194                 sco[0] = (float)(kcd->ar->winx/2.0f)+(kcd->ar->winx/2.0f)*sco[0];
195                 sco[1] = (float)(kcd->ar->winy/2.0f)+(kcd->ar->winy/2.0f)*sco[1];
196         } else
197                 view3d_project_float(kcd->ar, co, sco, kcd->projmat);
198 }
199
200 static KnifeEdge *new_knife_edge(knifetool_opdata *kcd)
201 {
202         kcd->totkedge++;
203         return BLI_mempool_calloc(kcd->kedges);
204 }
205
206 static KnifeVert *new_knife_vert(knifetool_opdata *kcd, float *co)
207 {
208         KnifeVert *kfv = BLI_mempool_calloc(kcd->kverts);
209         
210         kcd->totkvert++;
211         
212         copy_v3_v3(kfv->co, co);
213         copy_v3_v3(kfv->sco, co);
214
215         knife_project_v3(kcd, kfv->co, kfv->sco);
216
217         return kfv;
218 }
219
220 /*get a KnifeVert wrapper for an existing BMVert*/
221 static KnifeVert *get_bm_knife_vert(knifetool_opdata *kcd, BMVert *v)
222 {
223         KnifeVert *kfv = BLI_ghash_lookup(kcd->origvertmap, v);
224         
225         if (!kfv) {
226                 kfv = new_knife_vert(kcd, v->co);
227                 kfv->v = v;
228                 BLI_ghash_insert(kcd->origvertmap, v, kfv);
229         }
230         
231         return kfv;
232 }
233
234 /*get a KnifeEdge wrapper for an existing BMEdge*/
235 static KnifeEdge *get_bm_knife_edge(knifetool_opdata *kcd, BMEdge *e)
236 {
237         KnifeEdge *kfe = BLI_ghash_lookup(kcd->origedgemap, e);
238         if (!kfe) {
239                 Ref *ref;
240                 BMIter iter;
241                 BMFace *f;
242                 
243                 kfe = new_knife_edge(kcd);
244                 kfe->e = e;
245                 kfe->v1 = get_bm_knife_vert(kcd, e->v1);
246                 kfe->v2 = get_bm_knife_vert(kcd, e->v2);
247                 
248                 ref = BLI_mempool_calloc(kcd->refs);
249                 ref->ref = kfe;
250                 BLI_addtail(&kfe->v1->edges, ref);
251
252                 ref = BLI_mempool_calloc(kcd->refs);
253                 ref->ref = kfe;
254                 BLI_addtail(&kfe->v2->edges, ref);
255                 
256                 BLI_ghash_insert(kcd->origedgemap, e, kfe);
257                 
258                 BM_ITER(f, &iter, kcd->em->bm, BM_FACES_OF_EDGE, e) {
259                         ref = BLI_mempool_calloc(kcd->refs);
260                         ref->ref = f;
261                         BLI_addtail(&kfe->faces, ref);
262                         
263                         /*ensures the kedges lst for this f is initialized,
264                           it automatically adds kfe by itself*/
265                         knife_get_face_kedges(kcd, f);
266                 }
267         }
268         
269         return kfe;
270 }
271
272 static void knife_start_cut(knifetool_opdata *kcd)
273 {
274         kcd->prevedge = kcd->curedge;
275         kcd->prevvert = kcd->curvert;
276         kcd->prevbmface = kcd->curbmface;
277         kcd->cutnr++;
278         kcd->prev_is_space = kcd->is_space;
279         kcd->is_space = 0;
280         
281         copy_v3_v3(kcd->prevco, kcd->vertco);
282 }
283
284 static Ref *find_ref(ListBase *lb, void *ref)
285 {
286         Ref *ref1;
287         
288         for (ref1=lb->first; ref1; ref1=ref1->next) {
289                 if (ref1->ref == ref)
290                         return ref1;
291         }
292         
293         return NULL;
294 }
295
296 static ListBase *knife_get_face_kedges(knifetool_opdata *kcd, BMFace *f)
297 {
298         ListBase *lst = BLI_ghash_lookup(kcd->kedgefacemap, f);
299         
300         if (!lst) {
301                 BMIter iter;
302                 BMEdge *e;
303                 
304                 lst = BLI_memarena_alloc(kcd->arena, sizeof(ListBase));
305                 lst->first = lst->last = NULL;
306                 
307                 BM_ITER(e, &iter, kcd->em->bm, BM_EDGES_OF_FACE, f) {
308                         Ref *ref = BLI_mempool_calloc(kcd->refs);
309                         ref->ref = get_bm_knife_edge(kcd, e);
310                         BLI_addtail(lst, ref);
311                 }
312                 
313                 BLI_ghash_insert(kcd->kedgefacemap, f, lst);
314         }
315         
316         return lst;
317 }
318
319 /*finds the proper face to restrict face fill to*/
320 static void knife_find_basef(knifetool_opdata *kcd, KnifeEdge *kfe)
321 {
322         if (!kfe->basef) {
323                 Ref *r1, *r2, *r3, *r4;
324                 
325                 if (kfe->v1->isface || kfe->v2->isface) {
326                         if (kfe->v2->isface)
327                                 kfe->basef = kcd->curbmface;
328                         else 
329                                 kfe->basef = kcd->prevbmface;
330                 } else {                
331                         for (r1=kfe->v1->edges.first; r1 && !kfe->basef; r1=r1->next) {
332                                 KnifeEdge *ke1 = r1->ref;
333                                 for (r2=ke1->faces.first; r2 && !kfe->basef; r2=r2->next) {
334                                         for (r3=kfe->v2->edges.first; r3 && !kfe->basef; r3=r3->next) {
335                                                 KnifeEdge *ke2 = r3->ref;
336                                         
337                                                 for (r4=ke2->faces.first; r4 && !kfe->basef; r4=r4->next) {
338                                                         if (r2->ref == r4->ref) {
339                                                                 kfe->basef = r2->ref;
340                                                         }
341                                                 }       
342                                         }
343                                 }
344                         }
345                 }
346                 /*ok, at this point kfe->basef should be set if any valid possibility
347                   exists*/
348         }
349 }
350
351 static KnifeVert *knife_split_edge(knifetool_opdata *kcd, KnifeEdge *kfe, float co[3], KnifeEdge **newkfe_out)
352 {
353         KnifeEdge *newkfe = new_knife_edge(kcd);
354         ListBase *lst;
355         Ref *ref;
356         
357         newkfe->v1 = kfe->v1;
358         newkfe->v2 = new_knife_vert(kcd, co);
359         newkfe->v2->draw = 1;
360         newkfe->basef = kfe->basef;
361         
362         ref = find_ref(&kfe->v1->edges, kfe);
363         BLI_remlink(&kfe->v1->edges, ref);
364         
365         kfe->v1 = newkfe->v2;
366         BLI_addtail(&kfe->v1->edges, ref);
367         
368         for (ref=kfe->faces.first; ref; ref=ref->next) {
369                 Ref *ref2 = BLI_mempool_calloc(kcd->refs);
370                 
371                 /*add kedge ref to bm faces*/
372                 lst = knife_get_face_kedges(kcd, ref->ref);
373                 ref2->ref = newkfe;
374                 BLI_addtail(lst, ref2);
375
376                 ref2 = BLI_mempool_calloc(kcd->refs);
377                 ref2->ref = ref->ref;
378                 BLI_addtail(&newkfe->faces, ref2);
379         }
380
381         ref = BLI_mempool_calloc(kcd->refs);
382         ref->ref = newkfe;
383         BLI_addtail(&newkfe->v1->edges, ref);
384
385         ref = BLI_mempool_calloc(kcd->refs);
386         ref->ref = newkfe;
387         BLI_addtail(&newkfe->v2->edges, ref);
388         
389         newkfe->draw = kfe->draw;
390         newkfe->e = kfe->e;
391         
392         *newkfe_out = newkfe;
393                         
394         return newkfe->v2;
395 }
396
397 static void knife_edge_append_face(knifetool_opdata *kcd, KnifeEdge *kfe, BMFace *f)
398 {
399         ListBase *lst = knife_get_face_kedges(kcd, f);
400         Ref *ref = BLI_mempool_calloc(kcd->refs);
401         
402         ref->ref = kfe;
403         BLI_addtail(lst, ref);
404         
405         ref = BLI_mempool_calloc(kcd->refs);
406         ref->ref = f;
407         BLI_addtail(&kfe->faces, ref);
408 }
409
410 #if 0
411 static void knife_copy_edge_facelist(knifetool_opdata *kcd, KnifeEdge *dest, KnifeEdge *source) 
412 {
413         Ref *ref, *ref2;
414         
415         for (ref2 = source->faces.first; ref2; ref2=ref2->next) {
416                 ListBase *lst = knife_get_face_kedges(kcd, ref2->ref);
417                 
418                 /*add new edge to face knife edge list*/
419                 ref = BLI_mempool_calloc(kcd->refs);
420                 ref->ref = dest;
421                 BLI_addtail(lst, ref);
422                 
423                 /*add face to new edge's face list*/
424                 ref = BLI_mempool_calloc(kcd->refs);
425                 ref->ref = ref2->ref;
426                 BLI_addtail(&dest->faces, ref);
427         }
428 }
429 #endif
430
431 static void knife_add_single_cut(knifetool_opdata *kcd)
432 {
433         KnifeEdge *kfe = new_knife_edge(kcd), *kfe2 = NULL, *kfe3 = NULL;
434         Ref *ref;
435         
436         if (kcd->prevvert && kcd->prevvert == kcd->curvert)
437                 return;
438         if (kcd->prevedge && kcd->prevedge == kcd->curedge)
439                 return;
440         
441         kfe->draw = 1;
442
443         if (kcd->prevvert) {
444                 kfe->v1 = kcd->prevvert;
445         } else if (kcd->prevedge) {
446                 kfe->v1 = knife_split_edge(kcd, kcd->prevedge, kcd->prevco, &kfe2);
447         } else {
448                 kfe->v1 = new_knife_vert(kcd, kcd->prevco);
449                 kfe->v1->draw = kfe->draw = !kcd->prev_is_space;
450                 kfe->v1->inspace = kcd->prev_is_space;
451                 kfe->draw = !kcd->prev_is_space;
452                 kfe->v1->isface = 1;
453         }
454         
455         if (kcd->curvert) {
456                 kfe->v2 = kcd->curvert;
457         } else if (kcd->curedge) {
458                 kfe->v2 = knife_split_edge(kcd, kcd->curedge, kcd->vertco, &kfe3);
459         
460                 kcd->curvert = kfe->v2;
461         } else {
462                 kfe->v2 = new_knife_vert(kcd, kcd->vertco);
463                 kfe->v2->draw = !kcd->is_space;
464                 kfe->v2->isface = 1;
465                 kfe->v2->inspace = kcd->is_space;
466                 
467                 if (kcd->is_space)
468                         kfe->draw = 0;
469
470                 kcd->curvert = kfe->v2;
471         }
472         
473         knife_find_basef(kcd, kfe);
474         
475         ref = BLI_mempool_calloc(kcd->refs);
476         ref->ref = kfe; 
477         BLI_addtail(&kfe->v1->edges, ref);
478
479         ref = BLI_mempool_calloc(kcd->refs);
480         ref->ref = kfe;
481         BLI_addtail(&kfe->v2->edges, ref);      
482         
483         if (kfe->basef && !find_ref(&kfe->faces, kfe->basef))
484                 knife_edge_append_face(kcd, kfe, kfe->basef);
485
486         /*sanity check to make sure we're in the right edge/face lists*/
487         if (kcd->curbmface) {
488                 if (!find_ref(&kfe->faces, kcd->curbmface)) {
489                         knife_edge_append_face(kcd, kfe, kcd->curbmface);
490                 }
491
492                 if (kcd->prevbmface && kcd->prevbmface != kcd->curbmface) {
493                         if (!find_ref(&kfe->faces, kcd->prevbmface)) {
494                                 knife_edge_append_face(kcd, kfe, kcd->prevbmface);
495                         }
496                 }
497         }
498                 
499         /*set up for next cut*/
500         kcd->prevbmface = kcd->curbmface;
501         kcd->prevvert = kcd->curvert;
502         kcd->prevedge = kcd->curedge;
503         copy_v3_v3(kcd->prevco, kcd->vertco);
504         kcd->prev_is_space = kcd->is_space;
505 }
506
507 static int verge_linehit(const void *vlh1, const void *vlh2)
508 {
509         const BMEdgeHit *lh1=vlh1, *lh2=vlh2;
510
511         if (lh1->l < lh2->l) return -1;
512         else if (lh1->l > lh2->l) return 1;
513         else return 0;
514 }
515
516 static void knife_add_cut(knifetool_opdata *kcd)
517 {
518         BMEditMesh *em = kcd->em;
519         knifetool_opdata oldkcd = *kcd;
520         
521         if (kcd->linehits) {
522                 BMEdgeHit *lh, *lastlh, *firstlh;
523                 int i;
524                 
525                 qsort(kcd->linehits, kcd->totlinehit, sizeof(BMEdgeHit), verge_linehit);
526                 
527                 lh = kcd->linehits;
528                 lastlh = firstlh = NULL;
529                 for (i=0; i<kcd->totlinehit; i++, (lastlh=lh), lh++) {
530                         BMFace *f = lastlh ? lastlh->f : lh->f;
531                         
532                         if (lastlh && len_v3v3(lastlh->hit, lh->hit) == 0.0f) {
533                                 if (!firstlh)
534                                         firstlh = lastlh;
535                                 continue;
536                         } else if (lastlh && firstlh) {
537                                 if (firstlh->v || lastlh->v) {
538                                         KnifeVert *kfv = firstlh->v ? firstlh->v : lastlh->v;
539                                         
540                                         kcd->prevvert = kfv;
541                                         copy_v3_v3(kcd->prevco, firstlh->hit);
542                                         kcd->prevedge = NULL;
543                                         kcd->prevbmface = f;
544                                 }
545                                 lastlh = firstlh = NULL;
546                         }
547                         
548                         if (len_v3v3(kcd->prevco, lh->realhit) < FLT_EPSILON*80)
549                                 continue;
550                         if (len_v3v3(kcd->vertco, lh->realhit) < FLT_EPSILON*80)
551                                 continue;
552                         
553                         if (kcd->prev_is_space || kcd->is_space) {
554                                 kcd->prev_is_space = kcd->is_space = 0;
555                                 copy_v3_v3(kcd->prevco, lh->hit);
556                                 kcd->prevedge = lh->kfe;
557                                 kcd->curbmface = lh->f;
558                                 continue;
559                         }                       
560                         
561                         kcd->is_space = 0;
562                         kcd->curedge = lh->kfe;
563                         kcd->curbmface = lh->f;
564                         kcd->curvert = lh->v;
565                         copy_v3_v3(kcd->vertco, lh->hit);
566
567                         knife_add_single_cut(kcd);
568                 }
569                 
570                 kcd->curbmface = oldkcd.curbmface;
571                 kcd->curvert = oldkcd.curvert;
572                 kcd->curedge = oldkcd.curedge;
573                 kcd->is_space = oldkcd.is_space;
574                 copy_v3_v3(kcd->vertco, oldkcd.vertco);
575                 
576                 knife_add_single_cut(kcd);
577                 
578                 MEM_freeN(kcd->linehits);
579                 kcd->linehits = NULL;
580                 kcd->totlinehit = 0;
581         } else {
582                 knife_add_single_cut(kcd);
583         }
584 }
585
586 static void knife_finish_cut(knifetool_opdata *UNUSED(kcd))
587 {
588
589 }
590
591 /* modal loop selection drawing callback */
592 static void knifetool_draw(const bContext *UNUSED(C), ARegion *UNUSED(ar), void *arg)
593 {
594         knifetool_opdata *kcd = arg;
595         
596         glDisable(GL_DEPTH_TEST);
597         
598         glPolygonOffset(1.0f, 1.0f);
599         
600         glPushMatrix();
601         glMultMatrixf(kcd->ob->obmat);
602         
603         if (kcd->mode == MODE_DRAGGING) {
604                 glColor3f(0.1, 0.1, 0.1);
605                 glLineWidth(2.0);
606                 
607                 glBegin(GL_LINES);
608                 glVertex3fv(kcd->prevco);       
609                 glVertex3fv(kcd->vertco);
610                 glEnd();
611                 
612                 glLineWidth(1.0);       
613         }
614         
615         if (kcd->curedge) {
616                 glColor3f(0.5, 0.3, 0.15);
617                 glLineWidth(2.0);
618                 
619                 glBegin(GL_LINES);
620                 glVertex3fv(kcd->curedge->v1->co);      
621                 glVertex3fv(kcd->curedge->v2->co);
622                 glEnd();
623                 
624                 glLineWidth(1.0);
625         } else if (kcd->curvert) {
626                 glColor3f(0.8, 0.2, 0.1);
627                 glPointSize(11);
628                 
629                 glBegin(GL_POINTS);
630                 glVertex3fv(kcd->vertco);
631                 glEnd();
632         }
633         
634         if (kcd->curbmface) {           
635                 glColor3f(0.1, 0.8, 0.05);
636                 glPointSize(9);
637                 
638                 glBegin(GL_POINTS);
639                 glVertex3fv(kcd->vertco);
640                 glEnd();
641         }
642         
643         if (kcd->totlinehit > 0) {
644                 BMEdgeHit *lh;
645                 int i;
646                 
647                 glEnable(GL_BLEND);
648                 glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
649                 
650                 /*draw any snapped verts first*/
651                 glColor4f(0.8, 0.2, 0.1, 0.4);
652                 glPointSize(11);
653                 glBegin(GL_POINTS);
654                 lh = kcd->linehits;
655                 for (i=0; i<kcd->totlinehit; i++, lh++) {
656                         float sv1[3], sv2[3];
657                         
658                         knife_project_v3(kcd, lh->kfe->v1->co, sv1);
659                         knife_project_v3(kcd, lh->kfe->v2->co, sv2);
660                         knife_project_v3(kcd, lh->hit, lh->schit);
661                         
662                         if (len_v2v2(lh->schit, sv1) < kcd->vthresh/4) {
663                                 copy_v3_v3(lh->hit, lh->kfe->v1->co);
664                                 glVertex3fv(lh->hit);
665                                 lh->v = lh->kfe->v1;
666                         } else if (len_v2v2(lh->schit, sv2) < kcd->vthresh/4) {
667                                 copy_v3_v3(lh->hit, lh->kfe->v2->co);
668                                 glVertex3fv(lh->hit);
669                                 lh->v = lh->kfe->v2;
670                         }
671                 }
672                 glEnd();
673                 
674                 /*now draw the rest*/
675                 glColor4f(0.1, 0.8, 0.05, 0.4);
676                 glPointSize(7);
677                 glBegin(GL_POINTS);
678                 lh = kcd->linehits;
679                 for (i=0; i<kcd->totlinehit; i++, lh++) {
680                         glVertex3fv(lh->hit);
681                 }
682                 glEnd();
683                 glDisable(GL_BLEND);
684         }
685         
686         if (kcd->totkedge > 0) {
687                 BLI_mempool_iter iter;
688                 KnifeEdge *kfe;
689                 
690                 glLineWidth(1.0);
691                 glBegin(GL_LINES);
692
693                 BLI_mempool_iternew(kcd->kedges, &iter);
694                 for (kfe=BLI_mempool_iterstep(&iter); kfe; kfe=BLI_mempool_iterstep(&iter)) {
695                         if (!kfe->draw)
696                                 continue;
697                                 
698                         glColor3f(0.2, 0.2, 0.2);
699                         
700                         glVertex3fv(kfe->v1->co);
701                         glVertex3fv(kfe->v2->co);
702                 }
703                 
704                 glEnd();                
705                 glLineWidth(1.0);       
706         }
707
708         if (kcd->totkvert > 0) {
709                 BLI_mempool_iter iter;
710                 KnifeVert *kfv;
711                 
712                 glPointSize(5.0);
713                                 
714                 glBegin(GL_POINTS);
715                 BLI_mempool_iternew(kcd->kverts, &iter);
716                 for (kfv=BLI_mempool_iterstep(&iter); kfv; kfv=BLI_mempool_iterstep(&iter)) {
717                         if (!kfv->draw)
718                                 continue;
719                                 
720                         glColor3f(0.6, 0.1, 0.2);
721                         
722                         glVertex3fv(kfv->co);
723                 }
724                 
725                 glEnd();                
726         }
727
728         glPopMatrix();
729         glEnable(GL_DEPTH_TEST);
730 }
731
732 static void _print_smhash(SmallHash *hash)
733 {
734         int i, linecol=79, c=0;
735         
736         printf("{");
737         for (i=0; i<hash->size; i++) {
738                 if (hash->table[i].val == CELL_UNUSED) {
739                         printf("--u-");
740                 } else if (hash->table[i].val == CELL_FREE) {
741                         printf("--f-");
742                 } else  {
743                         printf("%2x", (unsigned int)hash->table[i].key);
744                 }
745                 
746                 if (i != hash->size-1)
747                         printf(", ");
748                 
749                 c += 6;
750                 
751                 if (c >= linecol) {
752                         printf("\n ");
753                         c = 0;
754                 }
755         }
756         
757         fflush(stdout);
758 }
759
760 static int kfe_vert_in_edge(KnifeEdge *e, KnifeVert *v) {
761         return e->v1 == v || e->v2 == v;
762 }
763
764 static int point_on_line(float p[3], float v1[3], float v2[3])
765 {
766         float d = dist_to_line_segment_v3(p, v1, v2);
767         if (d < 0.01) {
768                 d = len_v3v3(v1, v2);
769                 if (d == 0.0)
770                         return 0;
771                 
772                 d = len_v3v3(p, v1) / d;
773                 
774                 if (d >= -FLT_EPSILON*10 || d <= 1.0+FLT_EPSILON*10)
775                         return 1;
776         }
777         
778         return 0;
779 }
780
781 static BMEdgeHit *knife_edge_tri_isect(knifetool_opdata *kcd, BMBVHTree *bmtree, float v1[3], 
782                               float v2[3], float v3[3], SmallHash *ehash, bglMats *mats, int *count)
783 {
784         BVHTree *tree2 = BLI_bvhtree_new(3, FLT_EPSILON*4, 8, 8), *tree = BMBVH_BVHTree(bmtree);
785         BMEdgeHit *edges = NULL;
786         BLI_array_declare(edges);
787         BVHTreeOverlap *results, *result;
788         BMLoop **ls;
789         float cos[9], uv[3], lambda;
790         unsigned int tot=0;
791         int i, j;
792         
793         copy_v3_v3(cos, v1);
794         copy_v3_v3(cos+3, v2);
795         copy_v3_v3(cos+6, v3);
796         
797         BLI_bvhtree_insert(tree2, 0, cos, 3);
798         BLI_bvhtree_balance(tree2);
799         
800         result = results = BLI_bvhtree_overlap(tree, tree2, &tot);
801         
802         for (i=0; i<tot; i++, result++) {
803                 float p[3];
804                 
805                 ls = (BMLoop**)kcd->em->looptris[result->indexA];
806                 
807                 for (j=0; j<3; j++) {
808                         BMLoop *l1 = ls[j];
809                         BMFace *hitf;
810                         ListBase *lst = knife_get_face_kedges(kcd, l1->f);
811                         Ref *ref, *ref2;
812                         
813                         for (ref=lst->first; ref; ref=ref->next) {                      
814                                 KnifeEdge *kfe = ref->ref;
815                                 
816                                 if (kfe == kcd->curedge || kfe== kcd->prevedge)
817                                         continue;
818                                 
819                                 if (isect_line_tri_v3(kfe->v1->co, kfe->v2->co, v1, v2, v3, &lambda, uv)) {
820                                         float no[3], view[3], sp[3];
821                                         
822                                         sub_v3_v3v3(p, kfe->v2->co, kfe->v1->co);
823                                         mul_v3_fl(p, lambda);
824                                         add_v3_v3(p, kfe->v1->co);
825                                         
826                                         if (kcd->curedge && point_on_line(p, kcd->curedge->v1->co, kcd->curedge->v2->co))
827                                                 continue;
828                                         if (kcd->prevedge && point_on_line(p, kcd->prevedge->v1->co, kcd->prevedge->v2->co))
829                                                 continue;
830                                         if (kcd->curvert && len_v3v3(kcd->curvert->co, p) < FLT_EPSILON*50)
831                                                 continue;
832                                         if (kcd->prevvert && len_v3v3(kcd->prevvert->co, p) < FLT_EPSILON*50)
833                                                 continue;
834                                         if (len_v3v3(kcd->prevco, p) < FLT_EPSILON*50 || len_v3v3(kcd->vertco, p) < FLT_EPSILON*50)
835                                                 continue;
836
837                                         knife_project_v3(kcd, p, sp);
838                                         view3d_unproject(mats, view, sp[0], sp[1], 0.0f);
839                                         mul_m4_v3(kcd->ob->imat, view);
840
841                                         sub_v3_v3v3(view, p, view);
842                                         normalize_v3(view);;
843         
844                                         copy_v3_v3(no, view);
845                                         mul_v3_fl(no, -0.0003);
846                                         
847                                         /*go backwards toward view a bit*/
848                                         add_v3_v3(p, no);
849                                         
850                                         hitf = BMBVH_RayCast(bmtree, p, no, NULL);
851                                         for (ref2=kfe->faces.first; ref2; ref2=ref2->next) {
852                                                 if (ref2->ref == hitf)
853                                                         hitf = NULL;
854                                         }
855                                         
856                                         if (!hitf && !BLI_smallhash_haskey(ehash, (intptr_t)kfe)) {
857                                                 BMEdgeHit hit;
858                                                 
859                                                 if (len_v3v3(p, kcd->vertco) < FLT_EPSILON*50 || len_v3v3(p, kcd->prevco) < FLT_EPSILON*50)
860                                                         continue;
861                                                 
862                                                 hit.kfe = kfe;
863                                                 hit.v = NULL;
864                                                 
865                                                 knife_find_basef(kcd, kfe);
866                                                 hit.f = kfe->basef;
867                                                 
868                                                 copy_v3_v3(hit.realhit, p);
869                                                 
870                                                 if (kcd->snap_midpoints) {
871                                                         add_v3_v3v3(hit.hit, kfe->v1->co, kfe->v2->co);
872                                                         mul_v3_fl(hit.hit, 0.5f);
873                                                 } else {
874                                                         copy_v3_v3(hit.hit, p);
875                                                 }
876                                                 knife_project_v3(kcd, hit.hit, hit.schit);
877                                                 
878                                                 BLI_array_append(edges, hit);
879                                                 BLI_smallhash_insert(ehash, (intptr_t)kfe, NULL);
880                                         }
881                                 }
882                         }
883                 }
884         }
885         
886         if (results)
887                 MEM_freeN(results);
888         
889         BLI_bvhtree_free(tree2);
890         *count = BLI_array_count(edges);
891         
892         return edges;
893 }
894
895 static void knife_bgl_get_mats(knifetool_opdata *UNUSED(kcd), bglMats *mats)
896 {
897         bgl_get_mats(mats);
898         //copy_m4_m4(mats->modelview, kcd->vc.rv3d->viewmat);
899         //copy_m4_m4(mats->projection, kcd->vc.rv3d->winmat);
900 }
901
902 /*finds (visible) edges that intersects the current screen drag line*/
903 static void knife_find_line_hits(knifetool_opdata *kcd)
904 {
905         bglMats mats;
906         BMEdgeHit *e1, *e2;
907         SmallHash hash, *ehash = &hash;
908         float vec[3], v1[3], v2[3], v3[3], v4[4], s1[3], s2[3], view[3];
909         int i, c1, c2;
910         
911         knife_bgl_get_mats(kcd, &mats);
912         
913         if (kcd->linehits) {
914                 MEM_freeN(kcd->linehits);
915                 kcd->linehits = NULL;
916                 kcd->totlinehit = 0;
917         }
918         
919         copy_v3_v3(v1, kcd->prevco);
920         copy_v3_v3(v2, kcd->vertco);
921         
922         /*project screen line's 3d coordinates back into 2d*/
923         knife_project_v3(kcd, v1, s1);
924         knife_project_v3(kcd, v2, s2);
925         
926         if (len_v2v2(s1, s2) < 1)
927                 return; 
928
929         /*unproject screen line*/
930         viewline(kcd->ar, kcd->vc.v3d, s1, v1, v3);
931         viewline(kcd->ar, kcd->vc.v3d, s2, v2, v4);
932         
933         /*view3d_unproject(&mats, v1, s1[0], s1[1], 0.0f);
934         view3d_unproject(&mats, v2, s2[0], s2[1], 0.0f);
935         view3d_unproject(&mats, v3, s1[0], s1[1], 1.0f-FLT_EPSILON);
936         view3d_unproject(&mats, v4, s2[0], s2[1], 1.0f-FLT_EPSILON);*/
937         
938         mul_m4_v3(kcd->ob->imat, v1);
939         mul_m4_v3(kcd->ob->imat, v2);
940         mul_m4_v3(kcd->ob->imat, v3);
941         mul_m4_v3(kcd->ob->imat, v4);
942         
943         sub_v3_v3v3(vec, v2, v1);
944         normalize_v3(vec);
945         mul_v3_fl(vec, 0.01);
946         add_v3_v3(v1, vec);
947         add_v3_v3(v3, vec);
948
949         sub_v3_v3v3(vec, v4, v2);
950         normalize_v3(vec);
951         mul_v3_fl(vec, 0.01);
952         add_v3_v3(v4, vec);
953         add_v3_v3(v2, vec);
954         
955         sub_v3_v3v3(view, v4, v1);
956         normalize_v3(view);
957         
958         BLI_smallhash_init(ehash);
959         
960         /*test two triangles of sceen line's plane*/
961         e1 = knife_edge_tri_isect(kcd, kcd->bmbvh, v1, v2, v3, ehash, &mats, &c1);
962         e2 = knife_edge_tri_isect(kcd, kcd->bmbvh, v1, v3, v4, ehash, &mats, &c2);
963         if (c1 && c2) {
964                 e1 = MEM_reallocN(e1, sizeof(BMEdgeHit)*(c1+c2));
965                 memcpy(e1+c1, e2, sizeof(BMEdgeHit)*c2);
966                 MEM_freeN(e2);
967         } else if (c2) {
968                 e1 = e2;
969         }
970         
971         kcd->linehits = e1;
972         kcd->totlinehit = c1+c2;
973
974         /*find position along screen line, used for sorting*/
975         for (i=0; i<kcd->totlinehit; i++) {
976                 BMEdgeHit *lh = e1+i;
977                 
978                 lh->l = len_v2v2(lh->schit, s1) / len_v2v2(s2, s1);
979         }
980         
981         BLI_smallhash_release(ehash);
982 }
983
984 static BMFace *knife_find_closest_face(knifetool_opdata *kcd, float co[3], int *is_space)
985 {
986         BMFace *f;
987         bglMats mats;
988         float origin[3], ray[3];
989         float mval[2], imat[3][3];
990         int dist = KMAXDIST; 
991         
992         knife_bgl_get_mats(kcd, &mats);
993
994         mval[0] = kcd->vc.mval[0]; mval[1] = kcd->vc.mval[1];
995         
996         /*unproject to find view ray*/
997         view3d_unproject(&mats, origin, mval[0], mval[1], 0.0f);
998
999         sub_v3_v3v3(ray, origin, kcd->vc.rv3d->viewinv[3]);
1000         normalize_v3(ray);
1001         
1002         /*transform into object space*/
1003         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
1004         copy_m3_m4(imat, kcd->ob->obmat);
1005         invert_m3(imat);
1006         
1007         mul_m4_v3(kcd->ob->imat, origin);
1008         mul_m3_v3(imat, ray);
1009         
1010         copy_v3_v3(co, origin);
1011         add_v3_v3(co, ray);
1012
1013         f = BMBVH_RayCast(kcd->bmbvh, origin, ray, co);
1014         
1015         if (is_space)
1016                 *is_space = !f; 
1017         
1018         if (!f) {
1019                 /*try to use backbuffer selection method if ray casting failed*/
1020                 f = EDBM_findnearestface(&kcd->vc, &dist);
1021                 
1022                 /*cheat for now; just put in the origin instead 
1023                   of a true coordinate on the face*/
1024                 copy_v3_v3(co, origin);
1025                 add_v3_v3(co, ray);
1026         }
1027         
1028         return f;
1029 }
1030
1031 /*find the 2d screen space density of vertices within a radius.  used to scale snapping
1032   distance for picking edges/verts.*/
1033 static int knife_sample_screen_density(knifetool_opdata *kcd, float radius)
1034 {
1035         BMFace *f;
1036         int is_space;
1037         float co[3], sco[3];
1038         
1039         f = knife_find_closest_face(kcd, co, &is_space);
1040         
1041         if (f && !is_space) {
1042                 ListBase *lst;
1043                 Ref *ref;
1044                 KnifeVert *curv = NULL;
1045                 float dis;
1046                 int c = 0;
1047                 
1048                 knife_project_v3(kcd, co, sco);
1049                 
1050                 lst = knife_get_face_kedges(kcd, f);
1051                 for (ref=lst->first; ref; ref=ref->next) {
1052                         KnifeEdge *kfe = ref->ref;
1053                         int i;
1054                         
1055                         for (i=0; i<2; i++) {
1056                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1057                                 
1058                                 knife_project_v3(kcd, kfv->co, kfv->sco);
1059                                 
1060                                 dis = len_v2v2(kfv->sco, sco);
1061                                 if (dis < radius) {
1062                                         if(kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1063                                                 float vec[3];
1064                                                 
1065                                                 copy_v3_v3(vec, kfv->co);
1066                                                 mul_m4_v3(kcd->vc.obedit->obmat, vec);
1067                         
1068                                                 if(view3d_test_clipping(kcd->vc.rv3d, vec, 1)==0) {
1069                                                         c++;
1070                                                 }
1071                                         } else {
1072                                                 c++;
1073                                         }
1074                                 }
1075                         }
1076                 }
1077                 
1078                 return c;
1079         }
1080                 
1081         return 0;
1082 }
1083
1084 /*returns snapping distance for edges/verts, scaled by the density of the
1085   surrounding mesh (in screen space)*/
1086 static float knife_snap_size(knifetool_opdata *kcd, float maxsize)
1087 {
1088         float density = (float)knife_sample_screen_density(kcd, maxsize*2.0f);
1089         
1090         density = MAX2(density, 1);
1091         
1092         return MIN2(maxsize / (density*0.5f), maxsize);
1093 }
1094
1095 /*p is closest point on edge to the mouse cursor*/
1096 static KnifeEdge *knife_find_closest_edge(knifetool_opdata *kcd, float p[3], BMFace **fptr, int *is_space)
1097 {
1098         BMFace *f;
1099         float co[3], sco[3], maxdist = knife_snap_size(kcd, kcd->ethresh);
1100         
1101         if (kcd->ignore_vert_snapping)
1102                 maxdist *= 0.5;
1103
1104         f = knife_find_closest_face(kcd, co, NULL);
1105         *is_space = !f;
1106         
1107         /*set p to co, in case we don't find anything, means a face cut*/
1108         copy_v3_v3(p, co);
1109         kcd->curbmface = f;
1110         
1111         if (f) {
1112                 KnifeEdge *cure = NULL;
1113                 ListBase *lst;
1114                 Ref *ref;
1115                 float dis, curdis=FLT_MAX;
1116                 
1117                 knife_project_v3(kcd, co, sco);
1118                 
1119                 /*look through all edges associated with this face*/
1120                 lst = knife_get_face_kedges(kcd, f);
1121                 for (ref=lst->first; ref; ref=ref->next) {
1122                         KnifeEdge *kfe = ref->ref;
1123                         
1124                         /*project edge vertices into screen space*/
1125                         knife_project_v3(kcd, kfe->v1->co, kfe->v1->sco);
1126                         knife_project_v3(kcd, kfe->v2->co, kfe->v2->sco);
1127
1128                         dis = dist_to_line_segment_v2(sco, kfe->v1->sco, kfe->v2->sco);
1129                         if (dis < curdis && dis < maxdist) {
1130                                 if(kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1131                                         float labda= labda_PdistVL2Dfl(sco, kfe->v1->sco, kfe->v2->sco);
1132                                         float vec[3];
1133                 
1134                                         vec[0]= kfe->v1->co[0] + labda*(kfe->v2->co[0] - kfe->v1->co[0]);
1135                                         vec[1]= kfe->v1->co[1] + labda*(kfe->v2->co[1] - kfe->v1->co[1]);
1136                                         vec[2]= kfe->v1->co[2] + labda*(kfe->v2->co[2] - kfe->v1->co[2]);
1137                                         mul_m4_v3(kcd->vc.obedit->obmat, vec);
1138                 
1139                                         if(view3d_test_clipping(kcd->vc.rv3d, vec, 1)==0) {
1140                                                 cure = kfe;
1141                                                 curdis = dis;
1142                                         }
1143                                 } else {
1144                                         cure = kfe;
1145                                         curdis = dis;                           
1146                                 }
1147                         }
1148                 }
1149                 
1150                 if (fptr)
1151                         *fptr = f;
1152                 
1153                 if (cure && p) {
1154                         float d;
1155
1156                         if (!kcd->ignore_edge_snapping || !(cure->e)) {
1157                                 
1158                                 closest_to_line_segment_v3(p, sco, cure->v1->sco, cure->v2->sco);
1159                                 sub_v3_v3(p, cure->v1->sco);
1160                                 
1161                                 if (kcd->snap_midpoints) {
1162                                         d = 0.5f;       
1163                                 } else {
1164                                         d = len_v3v3(cure->v1->sco, cure->v2->sco);
1165                                         if (d != 0.0) {
1166                                                 d = len_v3(p) / d;
1167                                         }
1168                                 }
1169                                 
1170                                 interp_v3_v3v3(p, cure->v1->co, cure->v2->co, d);
1171                         } else {
1172                                 return NULL;
1173                         }
1174                 }
1175                 
1176                 return cure;
1177         }
1178                 
1179         if (fptr)
1180                 *fptr = NULL;
1181         
1182         return NULL;
1183 }
1184
1185 /*find a vertex near the mouse cursor, if it exists*/
1186 static KnifeVert *knife_find_closest_vert(knifetool_opdata *kcd, float p[3], BMFace **fptr, int *is_space)
1187 {
1188         BMFace *f;
1189         float co[3], sco[3], maxdist = knife_snap_size(kcd, kcd->vthresh);
1190         
1191         if (kcd->ignore_vert_snapping)
1192                 maxdist *= 0.5;
1193         
1194         f = knife_find_closest_face(kcd, co, is_space);
1195         
1196         /*set p to co, in case we don't find anything, means a face cut*/
1197         copy_v3_v3(p, co);
1198         kcd->curbmface = f;
1199         
1200         if (f) {
1201                 ListBase *lst;
1202                 Ref *ref;
1203                 KnifeVert *curv = NULL;
1204                 float dis, curdis=FLT_MAX;
1205                 
1206                 knife_project_v3(kcd, co, sco);
1207                 
1208                 lst = knife_get_face_kedges(kcd, f);
1209                 for (ref=lst->first; ref; ref=ref->next) {
1210                         KnifeEdge *kfe = ref->ref;
1211                         int i;
1212                         
1213                         for (i=0; i<2; i++) {
1214                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1215                                 
1216                                 knife_project_v3(kcd, kfv->co, kfv->sco);
1217                                 
1218                                 dis = len_v2v2(kfv->sco, sco);
1219                                 if (dis < curdis && dis < maxdist) {
1220                                         if(kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1221                                                 float vec[3];
1222                                                 
1223                                                 copy_v3_v3(vec, kfv->co);
1224                                                 mul_m4_v3(kcd->vc.obedit->obmat, vec);
1225                         
1226                                                 if(view3d_test_clipping(kcd->vc.rv3d, vec, 1)==0) {
1227                                                         curv = kfv;
1228                                                         curdis = dis;
1229                                                 }
1230                                         } else {
1231                                                 curv = kfv;
1232                                                 curdis = dis;                           
1233                                         }
1234                                 }
1235                         }
1236                 }
1237                 
1238                 if (!kcd->ignore_vert_snapping || !(curv && curv->v)) {
1239                         if (fptr)
1240                                 *fptr = f;
1241                 
1242                         if (curv && p) {
1243                                 copy_v3_v3(p, curv->co);
1244                         }
1245                         
1246                         return curv;
1247                 } else {
1248                         if (fptr)
1249                                 *fptr = f;
1250                         
1251                         return NULL;
1252                 }
1253         }
1254                 
1255         if (fptr)
1256                 *fptr = NULL;
1257         
1258         return NULL;
1259 }
1260
1261 /*update active knife edge/vert pointers*/
1262 static int knife_update_active(knifetool_opdata *kcd)
1263 {
1264         kcd->curvert = NULL; kcd->curedge = NULL; kcd->curbmface = NULL;
1265         
1266         kcd->curvert = knife_find_closest_vert(kcd, kcd->vertco, &kcd->curbmface, &kcd->is_space);
1267         if (!kcd->curvert) {
1268                 kcd->curedge = knife_find_closest_edge(kcd, kcd->vertco, &kcd->curbmface, &kcd->is_space);
1269         }
1270         
1271         if (kcd->mode == MODE_DRAGGING) {
1272                 knife_find_line_hits(kcd);
1273         }
1274         return 1;
1275 }
1276
1277 #define MARK                    4
1278 #define DEL                             8       
1279 #define VERT_ON_EDGE    16
1280 #define VERT_ORIG               32
1281 #define FACE_FLIP               64
1282 #define BOUNDARY                128
1283 #define FACE_NEW                256
1284
1285 typedef struct facenet_entry {
1286         struct facenet_entry *next, *prev;
1287         KnifeEdge *kfe;
1288 } facenet_entry;
1289
1290 static void rnd_offset_co(float co[3], float scale)
1291 {
1292         int i;
1293         
1294         for (i=0; i<3; i++) {
1295                 co[i] += (BLI_drand()-0.5)*scale;
1296         }
1297 }
1298
1299 static void remerge_faces(knifetool_opdata *kcd)
1300 {
1301         BMesh *bm = kcd->em->bm;
1302         SmallHash svisit, *visit=&svisit;
1303         BMIter iter;
1304         BMFace *f;
1305         BMFace **stack = NULL;
1306         BLI_array_declare(stack);
1307         BMFace **faces = NULL;
1308         BLI_array_declare(faces);
1309         BMOperator bmop;
1310         int idx;
1311         
1312         BMO_InitOpf(bm, &bmop, "beautify_fill faces=%ff constrain_edges=%fe", FACE_NEW, BOUNDARY);
1313         
1314         BMO_Exec_Op(bm, &bmop);
1315         BMO_Flag_Buffer(bm, &bmop, "geomout", FACE_NEW, BM_FACE);
1316         
1317         BMO_Finish_Op(bm, &bmop);
1318         
1319         BLI_smallhash_init(visit);
1320         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
1321                 BMIter eiter;
1322                 BMEdge *e;
1323                 BMFace *f2;
1324                 
1325                 if (!BMO_TestFlag(bm, f, FACE_NEW))
1326                         continue;
1327                 
1328                 if (BLI_smallhash_haskey(visit, (intptr_t)f))
1329                         continue;
1330                 
1331                 BLI_array_empty(stack);
1332                 BLI_array_empty(faces);
1333                 BLI_array_append(stack, f);
1334                 BLI_smallhash_insert(visit, (intptr_t)f, NULL);
1335                 
1336                 do {
1337                         f2 = BLI_array_pop(stack);
1338                         
1339                         BLI_array_append(faces, f2);
1340                         
1341                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_FACE, f2) {
1342                                 BMIter fiter;
1343                                 BMFace *f3;
1344                                 
1345                                 if (BMO_TestFlag(bm, e, BOUNDARY))
1346                                         continue;
1347                                 
1348                                 BM_ITER(f3, &fiter, bm, BM_FACES_OF_EDGE, e) {
1349                                         if (!BMO_TestFlag(bm, f3, FACE_NEW))
1350                                                 continue;
1351                                         if (BLI_smallhash_haskey(visit, (intptr_t)f3))
1352                                                 continue;
1353                                         
1354                                         BLI_smallhash_insert(visit, (intptr_t)f3, NULL);
1355                                         BLI_array_append(stack, f3);
1356                                 }
1357                         }       
1358                 } while (BLI_array_count(stack) > 0);
1359                 
1360                 if (BLI_array_count(faces) > 0) {
1361                         idx = BM_GetIndex(faces[0]);
1362                         
1363                         f2 = BM_Join_Faces(bm, faces, BLI_array_count(faces));
1364                         if (f2)  {
1365                                 BMO_SetFlag(bm, f2, FACE_NEW);
1366                                 BM_SetIndex(f2, idx);
1367                         }
1368                 }
1369         }
1370 }
1371
1372 /*use edgenet to fill faces.  this is a bit annoying and convoluted.*/
1373 static void knifenet_fill_faces(knifetool_opdata *kcd)
1374 {
1375         BMesh *bm = kcd->em->bm;
1376         BMIter bmiter;
1377         BLI_mempool_iter iter;
1378         BMFace *f;
1379         BMEdge *e;
1380         KnifeVert *kfv;
1381         KnifeEdge *kfe;
1382         facenet_entry *entry;
1383         ListBase *face_nets = MEM_callocN(sizeof(ListBase)*bm->totface, "face_nets");
1384         BMFace **faces = MEM_callocN(sizeof(BMFace*)*bm->totface, "faces knife");
1385         MemArena *arena = BLI_memarena_new(1<<16, "knifenet_fill_faces");
1386         SmallHash shash, shash2, *hash = &shash, *visited = &shash2;
1387         int i, j, k=0, totface=bm->totface;
1388         
1389         BMO_push(bm, NULL);
1390         bmesh_begin_edit(bm, BMOP_UNTAN_MULTIRES);
1391         
1392         i = 0;
1393         BM_ITER(f, &bmiter, bm, BM_FACES_OF_MESH, NULL) {
1394                 BM_SetIndex(f, i);
1395                 faces[i] = f;
1396                 i++;
1397         }
1398         
1399         BM_ITER(e, &bmiter, bm, BM_EDGES_OF_MESH, NULL) {
1400                 BMO_SetFlag(bm, e, BOUNDARY);
1401         }
1402
1403         /*turn knife verts into real verts, as necassary*/
1404         BLI_mempool_iternew(kcd->kverts, &iter);
1405         for (kfv=BLI_mempool_iterstep(&iter); kfv; kfv=BLI_mempool_iterstep(&iter)) {
1406                 if (!kfv->v) {
1407                         kfv->v = BM_Make_Vert(bm, kfv->co, NULL);
1408                         kfv->flag = 1;
1409                         BMO_SetFlag(bm, kfv->v, DEL);
1410                 } else {
1411                         kfv->flag = 0;
1412                         BMO_SetFlag(bm, kfv->v, VERT_ORIG);
1413                 }
1414
1415                 BMO_SetFlag(bm, kfv->v, MARK);
1416         }
1417         
1418         /*we want to only do changed faces.  first, go over new edges and add to
1419       face net lists.*/
1420         i=0; j=0; k=0;
1421         BLI_mempool_iternew(kcd->kedges, &iter);
1422         for (kfe=BLI_mempool_iterstep(&iter); kfe; kfe=BLI_mempool_iterstep(&iter)) {
1423                 Ref *ref;
1424                 if (!kfe->v1 || !kfe->v2 || kfe->v1->inspace || kfe->v2->inspace)
1425                         continue;
1426
1427                 i++;
1428
1429                 if (kfe->e && kfe->v1->v == kfe->e->v1 && kfe->v2->v == kfe->e->v2) {
1430                         kfe->oe = kfe->e;
1431                         continue;
1432                 }
1433                 
1434                 j++;
1435                 
1436                 if (kfe->e) {
1437                         kfe->oe = kfe->e;
1438
1439                         BMO_SetFlag(bm, kfe->e, DEL);
1440                         BMO_ClearFlag(bm, kfe->e, BOUNDARY);
1441                         kfe->e = NULL;
1442                 }
1443                 
1444                 kfe->e = BM_Make_Edge(bm, kfe->v1->v, kfe->v2->v, NULL, 1);
1445                 BMO_SetFlag(bm, kfe->e, BOUNDARY);
1446                 
1447                 for (ref=kfe->faces.first; ref; ref=ref->next) {
1448                         f = ref->ref;
1449                         
1450                         entry = BLI_memarena_alloc(arena, sizeof(*entry));
1451                         entry->kfe = kfe;
1452                         BLI_addtail(face_nets+BM_GetIndex(f), entry);
1453                 }
1454         }
1455         
1456         /*go over original edges, and add to faces with new geometry*/
1457         BLI_mempool_iternew(kcd->kedges, &iter);
1458         for (kfe=BLI_mempool_iterstep(&iter); kfe; kfe=BLI_mempool_iterstep(&iter)) {
1459                 Ref *ref;
1460                 
1461                 if (!kfe->v1 || !kfe->v2 || kfe->v1->inspace || kfe->v2->inspace)
1462                         continue;
1463                 if (!(kfe->oe && kfe->v1->v == kfe->oe->v1 && kfe->v2->v == kfe->oe->v2))
1464                         continue;
1465                 
1466                 k++;
1467                 
1468                 BMO_SetFlag(bm, kfe->e, BOUNDARY);
1469                 kfe->oe = kfe->e;
1470                 
1471                 for (ref=kfe->faces.first; ref; ref=ref->next) {
1472                         f = ref->ref;
1473                         
1474                         if (face_nets[BM_GetIndex(f)].first) {
1475                                 entry = BLI_memarena_alloc(arena, sizeof(*entry));
1476                                 entry->kfe = kfe;
1477                                 BLI_addtail(face_nets+BM_GetIndex(f), entry);
1478                         }
1479                 }
1480         }
1481         
1482         for (i=0; i<totface; i++) {
1483                 EditFace *efa;
1484                 EditVert *eve, *lasteve;
1485                 int j;
1486                 float rndscale = FLT_EPSILON*25;
1487                 
1488                 f = faces[i];
1489                 BLI_smallhash_init(hash);
1490                 
1491                 if (face_nets[i].first)
1492                         BMO_SetFlag(bm, f, DEL);
1493                 
1494                 BLI_begin_edgefill();
1495                 
1496                 for (entry=face_nets[i].first; entry; entry=entry->next) {
1497                         if (!BLI_smallhash_haskey(hash, (intptr_t)entry->kfe->v1)) {
1498                                 eve = BLI_addfillvert(entry->kfe->v1->v->co);
1499                                 eve->xs = 0;
1500                                 rnd_offset_co(eve->co, rndscale);
1501                                 eve->tmp.p = entry->kfe->v1->v;
1502                                 BLI_smallhash_insert(hash, (intptr_t)entry->kfe->v1, eve);
1503                         }
1504
1505                         if (!BLI_smallhash_haskey(hash, (intptr_t)entry->kfe->v2)) {
1506                                 eve = BLI_addfillvert(entry->kfe->v2->v->co);
1507                                 eve->xs = 0;
1508                                 rnd_offset_co(eve->co, rndscale);
1509                                 eve->tmp.p = entry->kfe->v2->v;
1510                                 BLI_smallhash_insert(hash, (intptr_t)entry->kfe->v2, eve);
1511                         }                                                
1512                 }
1513                 
1514                 for (j=0, entry=face_nets[i].first; entry; entry=entry->next, j++) {
1515                         EditEdge *eed;
1516
1517                         lasteve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v1);
1518                         eve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v2);
1519                         
1520                         eve->xs++;
1521                         lasteve->xs++;
1522                 }
1523                 
1524                 for (j=0, entry=face_nets[i].first; entry; entry=entry->next, j++) {
1525                         lasteve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v1);
1526                         eve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v2);
1527                         
1528                         if (eve->xs > 1 && lasteve->xs > 1) {
1529                                 BLI_addfilledge(lasteve, eve);
1530                                 
1531                                 BMO_ClearFlag(bm, entry->kfe->e->v1, DEL);
1532                                 BMO_ClearFlag(bm, entry->kfe->e->v2, DEL);
1533                         } else {
1534                                 if (lasteve->xs < 2)
1535                                         BLI_remlink(&fillvertbase, lasteve);
1536                                 if (eve->xs < 2)
1537                                         BLI_remlink(&fillvertbase, eve);
1538                         }
1539                 }
1540                 
1541                 BLI_edgefill(0);
1542                 
1543                 for (efa=fillfacebase.first; efa; efa=efa->next) {
1544                         BMVert *v1=efa->v3->tmp.p, *v2=efa->v2->tmp.p, *v3=efa->v1->tmp.p;
1545                         BMFace *f2;
1546                         BMLoop *l;
1547                         BMVert *verts[3] = {v1, v2, v3};
1548                         
1549                         if (v1 == v2 || v2 == v3 || v1 == v3)
1550                                 continue;       
1551                         if (BM_Face_Exists(bm, verts, 3, &f2))
1552                                 continue;
1553                 
1554                         f2 = BM_Make_QuadTri(bm, v1, v2, v3, NULL, NULL, 0);
1555                         BMO_SetFlag(bm, f2, FACE_NEW);
1556                         
1557                         l = bm_firstfaceloop(f2);
1558                         do {
1559                                 BMO_ClearFlag(bm, l->e, DEL);
1560                                 l = l->next;
1561                         } while (l != bm_firstfaceloop(f2));
1562         
1563                         BMO_ClearFlag(bm, f2, DEL);
1564                         BM_SetIndex(f2, i);
1565                         
1566                         BM_Face_UpdateNormal(bm, f2);
1567                         if (dot_v3v3(f->no, f2->no) < 0.0) {
1568                                 BM_flip_normal(bm, f2);
1569                         }
1570                 }
1571                 
1572                 BLI_end_edgefill();
1573                 BLI_smallhash_release(hash);
1574         }
1575         
1576         /* interpolate customdata */
1577         BM_ITER(f, &bmiter, bm, BM_FACES_OF_MESH, NULL) {
1578                 BMLoop *l1;
1579                 BMFace *f2; 
1580                 BMIter liter1;
1581                 
1582                 if (!BMO_TestFlag(bm, f, FACE_NEW))
1583                         continue;
1584                 
1585                 f2 = faces[BM_GetIndex(f)];
1586                 if (BM_GetIndex(f) < 0 || BM_GetIndex(f) >= totface) {
1587                         printf("eek!!\n");
1588                 }
1589
1590                 BM_Copy_Attributes(bm, bm, f2, f);
1591                 
1592                 BM_ITER(l1, &liter1, bm, BM_LOOPS_OF_FACE, f) {
1593                         BM_loop_interp_from_face(bm, l1, f2, 1, 1);
1594                 }
1595         }
1596         
1597         /*merge triangles back into faces*/
1598         remerge_faces(kcd);
1599
1600         /*delete left over faces*/
1601         BMO_CallOpf(bm, "del geom=%ff context=%i", DEL, DEL_ONLYFACES);
1602         BMO_CallOpf(bm, "del geom=%fe context=%i", DEL, DEL_EDGES);
1603         BMO_CallOpf(bm, "del geom=%fv context=%i", DEL, DEL_VERTS);
1604
1605         if (face_nets) 
1606                 MEM_freeN(face_nets);
1607         if (faces)
1608                 MEM_freeN(faces);
1609         BLI_memarena_free(arena);
1610         BLI_smallhash_release(hash);    
1611         
1612         BMO_ClearStack(bm); /*remerge_faces sometimes raises errors, so make sure to clear them*/
1613
1614         bmesh_end_edit(bm, BMOP_UNTAN_MULTIRES);
1615         BMO_pop(bm);
1616 }
1617
1618 /*called on tool confirmation*/
1619 static void knifetool_finish(bContext *C, wmOperator *op)
1620 {
1621         knifetool_opdata *kcd= op->customdata;
1622         
1623         knifenet_fill_faces(kcd);
1624         
1625         DAG_id_tag_update(kcd->ob->data, OB_RECALC_DATA);
1626         WM_event_add_notifier(C, NC_GEOM|ND_DATA, kcd->ob->data);
1627 }
1628
1629 /*copied from paint_image.c*/
1630 static int project_knife_view_clip(View3D *v3d, RegionView3D *rv3d, float *clipsta, float *clipend)
1631 {
1632         int orth= get_view3d_cliprange(v3d, rv3d, clipsta, clipend);
1633
1634         if (orth) { /* only needed for ortho */
1635                 float fac = 2.0f / ((*clipend) - (*clipsta));
1636                 *clipsta *= fac;
1637                 *clipend *= fac;
1638         }
1639
1640         return orth;
1641 }
1642
1643 static void knife_recalc_projmat(knifetool_opdata *kcd)
1644 {
1645         ARegion *ar = CTX_wm_region(kcd->C);
1646         
1647         if (!ar)
1648                 return;
1649         
1650         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
1651         view3d_get_object_project_mat(ar->regiondata, kcd->ob, kcd->projmat);
1652         //mul_m4_m4m4(kcd->projmat, kcd->vc.rv3d->viewmat, kcd->vc.rv3d->winmat);
1653         
1654         kcd->is_ortho = project_knife_view_clip(kcd->vc.v3d, kcd->vc.rv3d, 
1655                                                 &kcd->clipsta, &kcd->clipend);
1656 }
1657
1658 /* called when modal loop selection is done... */
1659 static void knifetool_exit (bContext *UNUSED(C), wmOperator *op)
1660 {
1661         knifetool_opdata *kcd= op->customdata;
1662         
1663         if (!kcd)
1664                 return;
1665                 
1666         /* deactivate the extra drawing stuff in 3D-View */
1667         ED_region_draw_cb_exit(kcd->ar->type, kcd->draw_handle);
1668         
1669         /* free the custom data */
1670         BLI_mempool_destroy(kcd->refs);
1671         BLI_mempool_destroy(kcd->kverts);
1672         BLI_mempool_destroy(kcd->kedges);
1673
1674         BLI_ghash_free(kcd->origedgemap, NULL, NULL);
1675         BLI_ghash_free(kcd->origvertmap, NULL, NULL);
1676         BLI_ghash_free(kcd->kedgefacemap, NULL, NULL);
1677         
1678         BMBVH_FreeBVH(kcd->bmbvh);
1679         BLI_memarena_free(kcd->arena);
1680         
1681         /* tag for redraw */
1682         ED_region_tag_redraw(kcd->ar);
1683
1684         /* destroy kcd itself */
1685         MEM_freeN(kcd);
1686         op->customdata= NULL;                   
1687 }
1688
1689 /* called when modal loop selection gets set up... */
1690 static int knifetool_init (bContext *C, wmOperator *op, int UNUSED(do_cut))
1691 {
1692         knifetool_opdata *kcd;
1693         
1694         /* alloc new customdata */
1695         kcd= op->customdata= MEM_callocN(sizeof(knifetool_opdata), "knifetool Modal Op Data");
1696         
1697         /* assign the drawing handle for drawing preview line... */
1698         kcd->ar= CTX_wm_region(C);
1699         kcd->C = C;
1700         kcd->draw_handle= ED_region_draw_cb_activate(kcd->ar->type, knifetool_draw, kcd, REGION_DRAW_POST_VIEW);
1701         em_setup_viewcontext(C, &kcd->vc);
1702
1703         kcd->ob = CTX_data_edit_object(C);
1704         kcd->em= ((Mesh *)kcd->ob->data)->edit_btmesh;
1705         kcd->bmbvh = BMBVH_NewBVH(kcd->em);
1706         kcd->arena = BLI_memarena_new(1<<15, "knife");
1707         kcd->vthresh = KMAXDIST-1;
1708         kcd->ethresh = KMAXDIST;
1709         
1710         kcd->extend = 1;
1711         
1712         knife_recalc_projmat(kcd);
1713         
1714         ED_region_tag_redraw(kcd->ar);
1715         
1716         kcd->refs = BLI_mempool_create(sizeof(Ref), 1, 2048, 0, 0);
1717         kcd->kverts = BLI_mempool_create(sizeof(KnifeVert), 1, 512, 0, 1);
1718         kcd->kedges = BLI_mempool_create(sizeof(KnifeEdge), 1, 512, 0, 1);
1719         
1720         kcd->origedgemap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origedgemap");
1721         kcd->origvertmap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origvertmap");
1722         kcd->kedgefacemap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origvertmap");
1723
1724         return 1;
1725 }
1726
1727 static int knifetool_cancel (bContext *C, wmOperator *op)
1728 {
1729         /* this is just a wrapper around exit() */
1730         knifetool_exit(C, op);
1731         return OPERATOR_CANCELLED;
1732 }
1733
1734 static int knifetool_invoke (bContext *C, wmOperator *op, wmEvent *evt)
1735 {
1736         knifetool_opdata *kcd;
1737
1738         view3d_operator_needs_opengl(C);
1739
1740         if (!knifetool_init(C, op, 0))
1741                 return OPERATOR_CANCELLED;
1742         
1743         /* add a modal handler for this operator - handles loop selection */
1744         WM_event_add_modal_handler(C, op);
1745
1746         kcd = op->customdata;
1747         kcd->vc.mval[0] = evt->mval[0];
1748         kcd->vc.mval[1] = evt->mval[1];
1749         
1750         return OPERATOR_RUNNING_MODAL;
1751 }
1752
1753 enum {
1754         KNF_MODAL_CANCEL=1,
1755         KNF_MODAL_CONFIRM,
1756         KNF_MODAL_MIDPOINT_ON,
1757         KNF_MODAL_MIDPOINT_OFF,
1758         KNF_MODAL_NEW_CUT,
1759         KNF_MODEL_IGNORE_SNAP_ON,
1760         KNF_MODEL_IGNORE_SNAP_OFF,
1761         KNF_MODAL_ADD_CUT,
1762 };
1763
1764 wmKeyMap* knifetool_modal_keymap(wmKeyConfig *keyconf)
1765 {
1766         static EnumPropertyItem modal_items[] = {
1767         {KNF_MODAL_CANCEL, "CANCEL", 0, "Cancel", ""},
1768         {KNF_MODAL_CONFIRM, "CONFIRM", 0, "Confirm", ""},
1769         {KNF_MODAL_MIDPOINT_ON, "SNAP_MIDPOINTS_ON", 0, "Snap To Midpoints On", ""},
1770         {KNF_MODAL_MIDPOINT_OFF, "SNAP_MIDPOINTS_OFF", 0, "Snap To Midpoints Off", ""},
1771         {KNF_MODEL_IGNORE_SNAP_ON, "IGNORE_SNAP_ON", 0, "Ignore Snapping On", ""},
1772         {KNF_MODEL_IGNORE_SNAP_OFF, "IGNORE_SNAP_OFF", 0, "Ignore Snapping Off", ""},
1773         {KNF_MODAL_NEW_CUT, "NEW_CUT", 0, "End Current Cut", ""},
1774         {KNF_MODAL_ADD_CUT, "ADD_CUT", 0, "Add Cut", ""},
1775
1776         {0, NULL, 0, NULL, NULL}};
1777         
1778         wmKeyMap *keymap= WM_modalkeymap_get(keyconf, "Knife Tool Modal Map");
1779         
1780         /* this function is called for each spacetype, only needs to add map once */
1781         if(keymap) return NULL;
1782         
1783         keymap= WM_modalkeymap_add(keyconf, "Knife Tool Modal Map", modal_items);
1784         
1785         /* items for modal map */
1786         WM_modalkeymap_add_item(keymap, ESCKEY,    KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
1787         WM_modalkeymap_add_item(keymap, LEFTMOUSE, KM_PRESS, KM_ANY, 0, KNF_MODAL_ADD_CUT);
1788         WM_modalkeymap_add_item(keymap, RIGHTMOUSE, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
1789         WM_modalkeymap_add_item(keymap, RETKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
1790         WM_modalkeymap_add_item(keymap, PADENTER, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
1791         WM_modalkeymap_add_item(keymap, EKEY, KM_PRESS, 0, 0, KNF_MODAL_NEW_CUT);
1792
1793         WM_modalkeymap_add_item(keymap, LEFTCTRLKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_MIDPOINT_ON);
1794         WM_modalkeymap_add_item(keymap, LEFTCTRLKEY, KM_RELEASE, KM_ANY, 0, KNF_MODAL_MIDPOINT_OFF);
1795         WM_modalkeymap_add_item(keymap, RIGHTCTRLKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_MIDPOINT_ON);
1796         WM_modalkeymap_add_item(keymap, RIGHTCTRLKEY, KM_RELEASE, KM_ANY, 0, KNF_MODAL_MIDPOINT_OFF);
1797
1798         WM_modalkeymap_add_item(keymap, LEFTSHIFTKEY, KM_PRESS, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_ON);
1799         WM_modalkeymap_add_item(keymap, LEFTSHIFTKEY, KM_RELEASE, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_OFF);
1800         WM_modalkeymap_add_item(keymap, RIGHTSHIFTKEY, KM_PRESS, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_ON);
1801         WM_modalkeymap_add_item(keymap, RIGHTSHIFTKEY, KM_RELEASE, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_OFF);
1802         
1803         WM_modalkeymap_assign(keymap, "MESH_OT_knifetool");
1804         
1805         return keymap;
1806 }
1807
1808 static int knifetool_modal (bContext *C, wmOperator *op, wmEvent *event)
1809 {
1810         Object *obedit;
1811         knifetool_opdata *kcd= op->customdata;
1812         
1813         if (!C) {
1814                 return OPERATOR_FINISHED;
1815         }
1816         
1817         obedit = CTX_data_edit_object(C);
1818         if (!obedit || obedit->type != OB_MESH || ((Mesh*)obedit->data)->edit_btmesh != kcd->em) {
1819                 knifetool_exit(C, op);
1820                 return OPERATOR_FINISHED;
1821         }
1822
1823         view3d_operator_needs_opengl(C);
1824         
1825         if (kcd->mode == MODE_PANNING)
1826                 kcd->mode = kcd->prevmode;
1827         
1828         /* handle modal keymap */
1829         if (event->type == EVT_MODAL_MAP) {
1830                 switch (event->val) {
1831                         case KNF_MODAL_CANCEL:
1832                                 /* finish */
1833                                 ED_region_tag_redraw(kcd->ar);
1834                                 
1835                                 knifetool_exit(C, op);
1836                                 
1837                                 return OPERATOR_CANCELLED;
1838                         case KNF_MODAL_CONFIRM:
1839                                 /* finish */
1840                                 ED_region_tag_redraw(kcd->ar);
1841                                 
1842                                 knifetool_finish(C, op);
1843                                 knifetool_exit(C, op);
1844                                 
1845                                 return OPERATOR_FINISHED;
1846                         case KNF_MODAL_MIDPOINT_ON:
1847                                 ED_region_tag_redraw(kcd->ar);
1848                                 kcd->snap_midpoints = 1;
1849                                 break;
1850                         case KNF_MODAL_MIDPOINT_OFF:
1851                                 ED_region_tag_redraw(kcd->ar);
1852                                 kcd->snap_midpoints = 0;
1853                                 break;
1854                         case KNF_MODEL_IGNORE_SNAP_ON:
1855                                 ED_region_tag_redraw(kcd->ar);
1856                                 kcd->ignore_vert_snapping = kcd->ignore_edge_snapping = 1;
1857                                 break;
1858                         case KNF_MODEL_IGNORE_SNAP_OFF:
1859                                 ED_region_tag_redraw(kcd->ar);
1860                                 kcd->ignore_vert_snapping = kcd->ignore_edge_snapping = 0;
1861                                 break;
1862                         case KNF_MODAL_NEW_CUT:
1863                                 ED_region_tag_redraw(kcd->ar);
1864                                 knife_finish_cut(kcd);
1865                                 kcd->mode = MODE_IDLE;
1866                                 break;
1867                         case KNF_MODAL_ADD_CUT:
1868                                 knife_recalc_projmat(kcd);
1869
1870                                 if (kcd->mode == MODE_DRAGGING) {
1871                                         knife_add_cut(kcd);
1872                                         if (!kcd->extend) {
1873                                                 knife_finish_cut(kcd);
1874                                                 kcd->mode = MODE_IDLE;
1875                                         }
1876                                 } else if (kcd->mode != MODE_PANNING) {
1877                                         knife_start_cut(kcd);
1878                                         kcd->mode = MODE_DRAGGING;
1879                                 }
1880                 
1881                                 ED_region_tag_redraw(kcd->ar);
1882                                 break;
1883                         }
1884         } else { /*non-modal-mapped events*/
1885                 switch (event->type) {
1886                         case WHEELUPMOUSE:
1887                         case WHEELDOWNMOUSE:
1888                                 return OPERATOR_PASS_THROUGH;
1889                         case MIDDLEMOUSE:
1890                                 if (event->val != KM_RELEASE) {
1891                                         if (kcd->mode != MODE_PANNING)
1892                                                 kcd->prevmode = kcd->mode;
1893                                         kcd->mode = MODE_PANNING;
1894                                 } else {
1895                                         kcd->mode = kcd->prevmode;
1896                                 }
1897                                 
1898                                 ED_region_tag_redraw(kcd->ar);
1899                                 return OPERATOR_PASS_THROUGH;
1900                                 
1901                         case MOUSEMOVE:  /* mouse moved somewhere to select another loop */
1902                                 if (kcd->mode != MODE_PANNING) {
1903                                         knife_recalc_projmat(kcd);
1904                                         kcd->vc.mval[0] = event->mval[0];
1905                                         kcd->vc.mval[1] = event->mval[1];
1906                                         
1907                                         if (knife_update_active(kcd))                                   
1908                                                 ED_region_tag_redraw(kcd->ar);
1909                                 }
1910         
1911                                 break;
1912                 }
1913         }
1914         
1915         /* keep going until the user confirms */
1916         return OPERATOR_RUNNING_MODAL;
1917 }
1918
1919 void MESH_OT_knifetool (wmOperatorType *ot)
1920 {
1921         /* description */
1922         ot->name= "Knife Topology Tool";
1923         ot->idname= "MESH_OT_knifetool";
1924         ot->description= "Cut new topology";
1925         
1926         /* callbacks */
1927         ot->invoke= knifetool_invoke;
1928         ot->modal= knifetool_modal;
1929         ot->cancel= knifetool_cancel;
1930         ot->poll= ED_operator_editmesh_view3d;
1931         
1932         /* flags */
1933         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO|OPTYPE_BLOCKING;
1934 }