remove unused vars
[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;*/ /*UNUSED*/
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                 float dis;
1045                 int c = 0;
1046                 
1047                 knife_project_v3(kcd, co, sco);
1048                 
1049                 lst = knife_get_face_kedges(kcd, f);
1050                 for (ref=lst->first; ref; ref=ref->next) {
1051                         KnifeEdge *kfe = ref->ref;
1052                         int i;
1053                         
1054                         for (i=0; i<2; i++) {
1055                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1056                                 
1057                                 knife_project_v3(kcd, kfv->co, kfv->sco);
1058                                 
1059                                 dis = len_v2v2(kfv->sco, sco);
1060                                 if (dis < radius) {
1061                                         if(kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1062                                                 float vec[3];
1063                                                 
1064                                                 copy_v3_v3(vec, kfv->co);
1065                                                 mul_m4_v3(kcd->vc.obedit->obmat, vec);
1066                         
1067                                                 if(view3d_test_clipping(kcd->vc.rv3d, vec, 1)==0) {
1068                                                         c++;
1069                                                 }
1070                                         } else {
1071                                                 c++;
1072                                         }
1073                                 }
1074                         }
1075                 }
1076                 
1077                 return c;
1078         }
1079                 
1080         return 0;
1081 }
1082
1083 /*returns snapping distance for edges/verts, scaled by the density of the
1084   surrounding mesh (in screen space)*/
1085 static float knife_snap_size(knifetool_opdata *kcd, float maxsize)
1086 {
1087         float density = (float)knife_sample_screen_density(kcd, maxsize*2.0f);
1088         
1089         density = MAX2(density, 1);
1090         
1091         return MIN2(maxsize / (density*0.5f), maxsize);
1092 }
1093
1094 /*p is closest point on edge to the mouse cursor*/
1095 static KnifeEdge *knife_find_closest_edge(knifetool_opdata *kcd, float p[3], BMFace **fptr, int *is_space)
1096 {
1097         BMFace *f;
1098         float co[3], sco[3], maxdist = knife_snap_size(kcd, kcd->ethresh);
1099         
1100         if (kcd->ignore_vert_snapping)
1101                 maxdist *= 0.5;
1102
1103         f = knife_find_closest_face(kcd, co, NULL);
1104         *is_space = !f;
1105         
1106         /*set p to co, in case we don't find anything, means a face cut*/
1107         copy_v3_v3(p, co);
1108         kcd->curbmface = f;
1109         
1110         if (f) {
1111                 KnifeEdge *cure = NULL;
1112                 ListBase *lst;
1113                 Ref *ref;
1114                 float dis, curdis=FLT_MAX;
1115                 
1116                 knife_project_v3(kcd, co, sco);
1117                 
1118                 /*look through all edges associated with this face*/
1119                 lst = knife_get_face_kedges(kcd, f);
1120                 for (ref=lst->first; ref; ref=ref->next) {
1121                         KnifeEdge *kfe = ref->ref;
1122                         
1123                         /*project edge vertices into screen space*/
1124                         knife_project_v3(kcd, kfe->v1->co, kfe->v1->sco);
1125                         knife_project_v3(kcd, kfe->v2->co, kfe->v2->sco);
1126
1127                         dis = dist_to_line_segment_v2(sco, kfe->v1->sco, kfe->v2->sco);
1128                         if (dis < curdis && dis < maxdist) {
1129                                 if(kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1130                                         float labda= labda_PdistVL2Dfl(sco, kfe->v1->sco, kfe->v2->sco);
1131                                         float vec[3];
1132                 
1133                                         vec[0]= kfe->v1->co[0] + labda*(kfe->v2->co[0] - kfe->v1->co[0]);
1134                                         vec[1]= kfe->v1->co[1] + labda*(kfe->v2->co[1] - kfe->v1->co[1]);
1135                                         vec[2]= kfe->v1->co[2] + labda*(kfe->v2->co[2] - kfe->v1->co[2]);
1136                                         mul_m4_v3(kcd->vc.obedit->obmat, vec);
1137                 
1138                                         if(view3d_test_clipping(kcd->vc.rv3d, vec, 1)==0) {
1139                                                 cure = kfe;
1140                                                 curdis = dis;
1141                                         }
1142                                 } else {
1143                                         cure = kfe;
1144                                         curdis = dis;                           
1145                                 }
1146                         }
1147                 }
1148                 
1149                 if (fptr)
1150                         *fptr = f;
1151                 
1152                 if (cure && p) {
1153                         float d;
1154
1155                         if (!kcd->ignore_edge_snapping || !(cure->e)) {
1156                                 
1157                                 closest_to_line_segment_v3(p, sco, cure->v1->sco, cure->v2->sco);
1158                                 sub_v3_v3(p, cure->v1->sco);
1159                                 
1160                                 if (kcd->snap_midpoints) {
1161                                         d = 0.5f;       
1162                                 } else {
1163                                         d = len_v3v3(cure->v1->sco, cure->v2->sco);
1164                                         if (d != 0.0) {
1165                                                 d = len_v3(p) / d;
1166                                         }
1167                                 }
1168                                 
1169                                 interp_v3_v3v3(p, cure->v1->co, cure->v2->co, d);
1170                         } else {
1171                                 return NULL;
1172                         }
1173                 }
1174                 
1175                 return cure;
1176         }
1177                 
1178         if (fptr)
1179                 *fptr = NULL;
1180         
1181         return NULL;
1182 }
1183
1184 /*find a vertex near the mouse cursor, if it exists*/
1185 static KnifeVert *knife_find_closest_vert(knifetool_opdata *kcd, float p[3], BMFace **fptr, int *is_space)
1186 {
1187         BMFace *f;
1188         float co[3], sco[3], maxdist = knife_snap_size(kcd, kcd->vthresh);
1189         
1190         if (kcd->ignore_vert_snapping)
1191                 maxdist *= 0.5;
1192         
1193         f = knife_find_closest_face(kcd, co, is_space);
1194         
1195         /*set p to co, in case we don't find anything, means a face cut*/
1196         copy_v3_v3(p, co);
1197         kcd->curbmface = f;
1198         
1199         if (f) {
1200                 ListBase *lst;
1201                 Ref *ref;
1202                 KnifeVert *curv = NULL;
1203                 float dis, curdis=FLT_MAX;
1204                 
1205                 knife_project_v3(kcd, co, sco);
1206                 
1207                 lst = knife_get_face_kedges(kcd, f);
1208                 for (ref=lst->first; ref; ref=ref->next) {
1209                         KnifeEdge *kfe = ref->ref;
1210                         int i;
1211                         
1212                         for (i=0; i<2; i++) {
1213                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1214                                 
1215                                 knife_project_v3(kcd, kfv->co, kfv->sco);
1216                                 
1217                                 dis = len_v2v2(kfv->sco, sco);
1218                                 if (dis < curdis && dis < maxdist) {
1219                                         if(kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1220                                                 float vec[3];
1221                                                 
1222                                                 copy_v3_v3(vec, kfv->co);
1223                                                 mul_m4_v3(kcd->vc.obedit->obmat, vec);
1224                         
1225                                                 if(view3d_test_clipping(kcd->vc.rv3d, vec, 1)==0) {
1226                                                         curv = kfv;
1227                                                         curdis = dis;
1228                                                 }
1229                                         } else {
1230                                                 curv = kfv;
1231                                                 curdis = dis;                           
1232                                         }
1233                                 }
1234                         }
1235                 }
1236                 
1237                 if (!kcd->ignore_vert_snapping || !(curv && curv->v)) {
1238                         if (fptr)
1239                                 *fptr = f;
1240                 
1241                         if (curv && p) {
1242                                 copy_v3_v3(p, curv->co);
1243                         }
1244                         
1245                         return curv;
1246                 } else {
1247                         if (fptr)
1248                                 *fptr = f;
1249                         
1250                         return NULL;
1251                 }
1252         }
1253                 
1254         if (fptr)
1255                 *fptr = NULL;
1256         
1257         return NULL;
1258 }
1259
1260 /*update active knife edge/vert pointers*/
1261 static int knife_update_active(knifetool_opdata *kcd)
1262 {
1263         kcd->curvert = NULL; kcd->curedge = NULL; kcd->curbmface = NULL;
1264         
1265         kcd->curvert = knife_find_closest_vert(kcd, kcd->vertco, &kcd->curbmface, &kcd->is_space);
1266         if (!kcd->curvert) {
1267                 kcd->curedge = knife_find_closest_edge(kcd, kcd->vertco, &kcd->curbmface, &kcd->is_space);
1268         }
1269         
1270         if (kcd->mode == MODE_DRAGGING) {
1271                 knife_find_line_hits(kcd);
1272         }
1273         return 1;
1274 }
1275
1276 #define MARK                    4
1277 #define DEL                             8       
1278 #define VERT_ON_EDGE    16
1279 #define VERT_ORIG               32
1280 #define FACE_FLIP               64
1281 #define BOUNDARY                128
1282 #define FACE_NEW                256
1283
1284 typedef struct facenet_entry {
1285         struct facenet_entry *next, *prev;
1286         KnifeEdge *kfe;
1287 } facenet_entry;
1288
1289 static void rnd_offset_co(float co[3], float scale)
1290 {
1291         int i;
1292         
1293         for (i=0; i<3; i++) {
1294                 co[i] += (BLI_drand()-0.5)*scale;
1295         }
1296 }
1297
1298 static void remerge_faces(knifetool_opdata *kcd)
1299 {
1300         BMesh *bm = kcd->em->bm;
1301         SmallHash svisit, *visit=&svisit;
1302         BMIter iter;
1303         BMFace *f;
1304         BMFace **stack = NULL;
1305         BLI_array_declare(stack);
1306         BMFace **faces = NULL;
1307         BLI_array_declare(faces);
1308         BMOperator bmop;
1309         int idx;
1310         
1311         BMO_InitOpf(bm, &bmop, "beautify_fill faces=%ff constrain_edges=%fe", FACE_NEW, BOUNDARY);
1312         
1313         BMO_Exec_Op(bm, &bmop);
1314         BMO_Flag_Buffer(bm, &bmop, "geomout", FACE_NEW, BM_FACE);
1315         
1316         BMO_Finish_Op(bm, &bmop);
1317         
1318         BLI_smallhash_init(visit);
1319         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
1320                 BMIter eiter;
1321                 BMEdge *e;
1322                 BMFace *f2;
1323                 
1324                 if (!BMO_TestFlag(bm, f, FACE_NEW))
1325                         continue;
1326                 
1327                 if (BLI_smallhash_haskey(visit, (intptr_t)f))
1328                         continue;
1329                 
1330                 BLI_array_empty(stack);
1331                 BLI_array_empty(faces);
1332                 BLI_array_append(stack, f);
1333                 BLI_smallhash_insert(visit, (intptr_t)f, NULL);
1334                 
1335                 do {
1336                         f2 = BLI_array_pop(stack);
1337                         
1338                         BLI_array_append(faces, f2);
1339                         
1340                         BM_ITER(e, &eiter, bm, BM_EDGES_OF_FACE, f2) {
1341                                 BMIter fiter;
1342                                 BMFace *f3;
1343                                 
1344                                 if (BMO_TestFlag(bm, e, BOUNDARY))
1345                                         continue;
1346                                 
1347                                 BM_ITER(f3, &fiter, bm, BM_FACES_OF_EDGE, e) {
1348                                         if (!BMO_TestFlag(bm, f3, FACE_NEW))
1349                                                 continue;
1350                                         if (BLI_smallhash_haskey(visit, (intptr_t)f3))
1351                                                 continue;
1352                                         
1353                                         BLI_smallhash_insert(visit, (intptr_t)f3, NULL);
1354                                         BLI_array_append(stack, f3);
1355                                 }
1356                         }       
1357                 } while (BLI_array_count(stack) > 0);
1358                 
1359                 if (BLI_array_count(faces) > 0) {
1360                         idx = BM_GetIndex(faces[0]);
1361                         
1362                         f2 = BM_Join_Faces(bm, faces, BLI_array_count(faces));
1363                         if (f2)  {
1364                                 BMO_SetFlag(bm, f2, FACE_NEW);
1365                                 BM_SetIndex(f2, idx);
1366                         }
1367                 }
1368         }
1369 }
1370
1371 /*use edgenet to fill faces.  this is a bit annoying and convoluted.*/
1372 static void knifenet_fill_faces(knifetool_opdata *kcd)
1373 {
1374         BMesh *bm = kcd->em->bm;
1375         BMIter bmiter;
1376         BLI_mempool_iter iter;
1377         BMFace *f;
1378         BMEdge *e;
1379         KnifeVert *kfv;
1380         KnifeEdge *kfe;
1381         facenet_entry *entry;
1382         ListBase *face_nets = MEM_callocN(sizeof(ListBase)*bm->totface, "face_nets");
1383         BMFace **faces = MEM_callocN(sizeof(BMFace*)*bm->totface, "faces knife");
1384         MemArena *arena = BLI_memarena_new(1<<16, "knifenet_fill_faces");
1385         SmallHash shash, *hash = &shash;
1386         /* SmallHash shash2, *visited = &shash2; */ /*UNUSED*/
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                         lasteve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v1);
1516                         eve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v2);
1517                         
1518                         eve->xs++;
1519                         lasteve->xs++;
1520                 }
1521                 
1522                 for (j=0, entry=face_nets[i].first; entry; entry=entry->next, j++) {
1523                         lasteve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v1);
1524                         eve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v2);
1525                         
1526                         if (eve->xs > 1 && lasteve->xs > 1) {
1527                                 BLI_addfilledge(lasteve, eve);
1528                                 
1529                                 BMO_ClearFlag(bm, entry->kfe->e->v1, DEL);
1530                                 BMO_ClearFlag(bm, entry->kfe->e->v2, DEL);
1531                         } else {
1532                                 if (lasteve->xs < 2)
1533                                         BLI_remlink(&fillvertbase, lasteve);
1534                                 if (eve->xs < 2)
1535                                         BLI_remlink(&fillvertbase, eve);
1536                         }
1537                 }
1538                 
1539                 BLI_edgefill(0);
1540                 
1541                 for (efa=fillfacebase.first; efa; efa=efa->next) {
1542                         BMVert *v1=efa->v3->tmp.p, *v2=efa->v2->tmp.p, *v3=efa->v1->tmp.p;
1543                         BMFace *f2;
1544                         BMLoop *l;
1545                         BMVert *verts[3] = {v1, v2, v3};
1546                         
1547                         if (v1 == v2 || v2 == v3 || v1 == v3)
1548                                 continue;       
1549                         if (BM_Face_Exists(bm, verts, 3, &f2))
1550                                 continue;
1551                 
1552                         f2 = BM_Make_QuadTri(bm, v1, v2, v3, NULL, NULL, 0);
1553                         BMO_SetFlag(bm, f2, FACE_NEW);
1554                         
1555                         l = bm_firstfaceloop(f2);
1556                         do {
1557                                 BMO_ClearFlag(bm, l->e, DEL);
1558                                 l = l->next;
1559                         } while (l != bm_firstfaceloop(f2));
1560         
1561                         BMO_ClearFlag(bm, f2, DEL);
1562                         BM_SetIndex(f2, i);
1563                         
1564                         BM_Face_UpdateNormal(bm, f2);
1565                         if (dot_v3v3(f->no, f2->no) < 0.0) {
1566                                 BM_flip_normal(bm, f2);
1567                         }
1568                 }
1569                 
1570                 BLI_end_edgefill();
1571                 BLI_smallhash_release(hash);
1572         }
1573         
1574         /* interpolate customdata */
1575         BM_ITER(f, &bmiter, bm, BM_FACES_OF_MESH, NULL) {
1576                 BMLoop *l1;
1577                 BMFace *f2; 
1578                 BMIter liter1;
1579                 
1580                 if (!BMO_TestFlag(bm, f, FACE_NEW))
1581                         continue;
1582                 
1583                 f2 = faces[BM_GetIndex(f)];
1584                 if (BM_GetIndex(f) < 0 || BM_GetIndex(f) >= totface) {
1585                         printf("eek!!\n");
1586                 }
1587
1588                 BM_Copy_Attributes(bm, bm, f2, f);
1589                 
1590                 BM_ITER(l1, &liter1, bm, BM_LOOPS_OF_FACE, f) {
1591                         BM_loop_interp_from_face(bm, l1, f2, 1, 1);
1592                 }
1593         }
1594         
1595         /*merge triangles back into faces*/
1596         remerge_faces(kcd);
1597
1598         /*delete left over faces*/
1599         BMO_CallOpf(bm, "del geom=%ff context=%i", DEL, DEL_ONLYFACES);
1600         BMO_CallOpf(bm, "del geom=%fe context=%i", DEL, DEL_EDGES);
1601         BMO_CallOpf(bm, "del geom=%fv context=%i", DEL, DEL_VERTS);
1602
1603         if (face_nets) 
1604                 MEM_freeN(face_nets);
1605         if (faces)
1606                 MEM_freeN(faces);
1607         BLI_memarena_free(arena);
1608         BLI_smallhash_release(hash);    
1609         
1610         BMO_ClearStack(bm); /*remerge_faces sometimes raises errors, so make sure to clear them*/
1611
1612         bmesh_end_edit(bm, BMOP_UNTAN_MULTIRES);
1613         BMO_pop(bm);
1614 }
1615
1616 /*called on tool confirmation*/
1617 static void knifetool_finish(bContext *C, wmOperator *op)
1618 {
1619         knifetool_opdata *kcd= op->customdata;
1620         
1621         knifenet_fill_faces(kcd);
1622         
1623         DAG_id_tag_update(kcd->ob->data, OB_RECALC_DATA);
1624         WM_event_add_notifier(C, NC_GEOM|ND_DATA, kcd->ob->data);
1625 }
1626
1627 /*copied from paint_image.c*/
1628 static int project_knife_view_clip(View3D *v3d, RegionView3D *rv3d, float *clipsta, float *clipend)
1629 {
1630         int orth= get_view3d_cliprange(v3d, rv3d, clipsta, clipend);
1631
1632         if (orth) { /* only needed for ortho */
1633                 float fac = 2.0f / ((*clipend) - (*clipsta));
1634                 *clipsta *= fac;
1635                 *clipend *= fac;
1636         }
1637
1638         return orth;
1639 }
1640
1641 static void knife_recalc_projmat(knifetool_opdata *kcd)
1642 {
1643         ARegion *ar = CTX_wm_region(kcd->C);
1644         
1645         if (!ar)
1646                 return;
1647         
1648         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
1649         view3d_get_object_project_mat(ar->regiondata, kcd->ob, kcd->projmat);
1650         //mul_m4_m4m4(kcd->projmat, kcd->vc.rv3d->viewmat, kcd->vc.rv3d->winmat);
1651         
1652         kcd->is_ortho = project_knife_view_clip(kcd->vc.v3d, kcd->vc.rv3d, 
1653                                                 &kcd->clipsta, &kcd->clipend);
1654 }
1655
1656 /* called when modal loop selection is done... */
1657 static void knifetool_exit (bContext *UNUSED(C), wmOperator *op)
1658 {
1659         knifetool_opdata *kcd= op->customdata;
1660         
1661         if (!kcd)
1662                 return;
1663                 
1664         /* deactivate the extra drawing stuff in 3D-View */
1665         ED_region_draw_cb_exit(kcd->ar->type, kcd->draw_handle);
1666         
1667         /* free the custom data */
1668         BLI_mempool_destroy(kcd->refs);
1669         BLI_mempool_destroy(kcd->kverts);
1670         BLI_mempool_destroy(kcd->kedges);
1671
1672         BLI_ghash_free(kcd->origedgemap, NULL, NULL);
1673         BLI_ghash_free(kcd->origvertmap, NULL, NULL);
1674         BLI_ghash_free(kcd->kedgefacemap, NULL, NULL);
1675         
1676         BMBVH_FreeBVH(kcd->bmbvh);
1677         BLI_memarena_free(kcd->arena);
1678         
1679         /* tag for redraw */
1680         ED_region_tag_redraw(kcd->ar);
1681
1682         /* destroy kcd itself */
1683         MEM_freeN(kcd);
1684         op->customdata= NULL;                   
1685 }
1686
1687 /* called when modal loop selection gets set up... */
1688 static int knifetool_init (bContext *C, wmOperator *op, int UNUSED(do_cut))
1689 {
1690         knifetool_opdata *kcd;
1691         
1692         /* alloc new customdata */
1693         kcd= op->customdata= MEM_callocN(sizeof(knifetool_opdata), "knifetool Modal Op Data");
1694         
1695         /* assign the drawing handle for drawing preview line... */
1696         kcd->ar= CTX_wm_region(C);
1697         kcd->C = C;
1698         kcd->draw_handle= ED_region_draw_cb_activate(kcd->ar->type, knifetool_draw, kcd, REGION_DRAW_POST_VIEW);
1699         em_setup_viewcontext(C, &kcd->vc);
1700
1701         kcd->ob = CTX_data_edit_object(C);
1702         kcd->em= ((Mesh *)kcd->ob->data)->edit_btmesh;
1703         kcd->bmbvh = BMBVH_NewBVH(kcd->em);
1704         kcd->arena = BLI_memarena_new(1<<15, "knife");
1705         kcd->vthresh = KMAXDIST-1;
1706         kcd->ethresh = KMAXDIST;
1707         
1708         kcd->extend = 1;
1709         
1710         knife_recalc_projmat(kcd);
1711         
1712         ED_region_tag_redraw(kcd->ar);
1713         
1714         kcd->refs = BLI_mempool_create(sizeof(Ref), 1, 2048, 0, 0);
1715         kcd->kverts = BLI_mempool_create(sizeof(KnifeVert), 1, 512, 0, 1);
1716         kcd->kedges = BLI_mempool_create(sizeof(KnifeEdge), 1, 512, 0, 1);
1717         
1718         kcd->origedgemap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origedgemap");
1719         kcd->origvertmap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origvertmap");
1720         kcd->kedgefacemap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origvertmap");
1721
1722         return 1;
1723 }
1724
1725 static int knifetool_cancel (bContext *C, wmOperator *op)
1726 {
1727         /* this is just a wrapper around exit() */
1728         knifetool_exit(C, op);
1729         return OPERATOR_CANCELLED;
1730 }
1731
1732 static int knifetool_invoke (bContext *C, wmOperator *op, wmEvent *evt)
1733 {
1734         knifetool_opdata *kcd;
1735
1736         view3d_operator_needs_opengl(C);
1737
1738         if (!knifetool_init(C, op, 0))
1739                 return OPERATOR_CANCELLED;
1740         
1741         /* add a modal handler for this operator - handles loop selection */
1742         WM_event_add_modal_handler(C, op);
1743
1744         kcd = op->customdata;
1745         kcd->vc.mval[0] = evt->mval[0];
1746         kcd->vc.mval[1] = evt->mval[1];
1747         
1748         return OPERATOR_RUNNING_MODAL;
1749 }
1750
1751 enum {
1752         KNF_MODAL_CANCEL=1,
1753         KNF_MODAL_CONFIRM,
1754         KNF_MODAL_MIDPOINT_ON,
1755         KNF_MODAL_MIDPOINT_OFF,
1756         KNF_MODAL_NEW_CUT,
1757         KNF_MODEL_IGNORE_SNAP_ON,
1758         KNF_MODEL_IGNORE_SNAP_OFF,
1759         KNF_MODAL_ADD_CUT,
1760 };
1761
1762 wmKeyMap* knifetool_modal_keymap(wmKeyConfig *keyconf)
1763 {
1764         static EnumPropertyItem modal_items[] = {
1765         {KNF_MODAL_CANCEL, "CANCEL", 0, "Cancel", ""},
1766         {KNF_MODAL_CONFIRM, "CONFIRM", 0, "Confirm", ""},
1767         {KNF_MODAL_MIDPOINT_ON, "SNAP_MIDPOINTS_ON", 0, "Snap To Midpoints On", ""},
1768         {KNF_MODAL_MIDPOINT_OFF, "SNAP_MIDPOINTS_OFF", 0, "Snap To Midpoints Off", ""},
1769         {KNF_MODEL_IGNORE_SNAP_ON, "IGNORE_SNAP_ON", 0, "Ignore Snapping On", ""},
1770         {KNF_MODEL_IGNORE_SNAP_OFF, "IGNORE_SNAP_OFF", 0, "Ignore Snapping Off", ""},
1771         {KNF_MODAL_NEW_CUT, "NEW_CUT", 0, "End Current Cut", ""},
1772         {KNF_MODAL_ADD_CUT, "ADD_CUT", 0, "Add Cut", ""},
1773
1774         {0, NULL, 0, NULL, NULL}};
1775         
1776         wmKeyMap *keymap= WM_modalkeymap_get(keyconf, "Knife Tool Modal Map");
1777         
1778         /* this function is called for each spacetype, only needs to add map once */
1779         if(keymap) return NULL;
1780         
1781         keymap= WM_modalkeymap_add(keyconf, "Knife Tool Modal Map", modal_items);
1782         
1783         /* items for modal map */
1784         WM_modalkeymap_add_item(keymap, ESCKEY,    KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
1785         WM_modalkeymap_add_item(keymap, LEFTMOUSE, KM_PRESS, KM_ANY, 0, KNF_MODAL_ADD_CUT);
1786         WM_modalkeymap_add_item(keymap, RIGHTMOUSE, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
1787         WM_modalkeymap_add_item(keymap, RETKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
1788         WM_modalkeymap_add_item(keymap, PADENTER, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
1789         WM_modalkeymap_add_item(keymap, EKEY, KM_PRESS, 0, 0, KNF_MODAL_NEW_CUT);
1790
1791         WM_modalkeymap_add_item(keymap, LEFTCTRLKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_MIDPOINT_ON);
1792         WM_modalkeymap_add_item(keymap, LEFTCTRLKEY, KM_RELEASE, KM_ANY, 0, KNF_MODAL_MIDPOINT_OFF);
1793         WM_modalkeymap_add_item(keymap, RIGHTCTRLKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_MIDPOINT_ON);
1794         WM_modalkeymap_add_item(keymap, RIGHTCTRLKEY, KM_RELEASE, KM_ANY, 0, KNF_MODAL_MIDPOINT_OFF);
1795
1796         WM_modalkeymap_add_item(keymap, LEFTSHIFTKEY, KM_PRESS, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_ON);
1797         WM_modalkeymap_add_item(keymap, LEFTSHIFTKEY, KM_RELEASE, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_OFF);
1798         WM_modalkeymap_add_item(keymap, RIGHTSHIFTKEY, KM_PRESS, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_ON);
1799         WM_modalkeymap_add_item(keymap, RIGHTSHIFTKEY, KM_RELEASE, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_OFF);
1800         
1801         WM_modalkeymap_assign(keymap, "MESH_OT_knifetool");
1802         
1803         return keymap;
1804 }
1805
1806 static int knifetool_modal (bContext *C, wmOperator *op, wmEvent *event)
1807 {
1808         Object *obedit;
1809         knifetool_opdata *kcd= op->customdata;
1810         
1811         if (!C) {
1812                 return OPERATOR_FINISHED;
1813         }
1814         
1815         obedit = CTX_data_edit_object(C);
1816         if (!obedit || obedit->type != OB_MESH || ((Mesh*)obedit->data)->edit_btmesh != kcd->em) {
1817                 knifetool_exit(C, op);
1818                 return OPERATOR_FINISHED;
1819         }
1820
1821         view3d_operator_needs_opengl(C);
1822         
1823         if (kcd->mode == MODE_PANNING)
1824                 kcd->mode = kcd->prevmode;
1825         
1826         /* handle modal keymap */
1827         if (event->type == EVT_MODAL_MAP) {
1828                 switch (event->val) {
1829                         case KNF_MODAL_CANCEL:
1830                                 /* finish */
1831                                 ED_region_tag_redraw(kcd->ar);
1832                                 
1833                                 knifetool_exit(C, op);
1834                                 
1835                                 return OPERATOR_CANCELLED;
1836                         case KNF_MODAL_CONFIRM:
1837                                 /* finish */
1838                                 ED_region_tag_redraw(kcd->ar);
1839                                 
1840                                 knifetool_finish(C, op);
1841                                 knifetool_exit(C, op);
1842                                 
1843                                 return OPERATOR_FINISHED;
1844                         case KNF_MODAL_MIDPOINT_ON:
1845                                 ED_region_tag_redraw(kcd->ar);
1846                                 kcd->snap_midpoints = 1;
1847                                 break;
1848                         case KNF_MODAL_MIDPOINT_OFF:
1849                                 ED_region_tag_redraw(kcd->ar);
1850                                 kcd->snap_midpoints = 0;
1851                                 break;
1852                         case KNF_MODEL_IGNORE_SNAP_ON:
1853                                 ED_region_tag_redraw(kcd->ar);
1854                                 kcd->ignore_vert_snapping = kcd->ignore_edge_snapping = 1;
1855                                 break;
1856                         case KNF_MODEL_IGNORE_SNAP_OFF:
1857                                 ED_region_tag_redraw(kcd->ar);
1858                                 kcd->ignore_vert_snapping = kcd->ignore_edge_snapping = 0;
1859                                 break;
1860                         case KNF_MODAL_NEW_CUT:
1861                                 ED_region_tag_redraw(kcd->ar);
1862                                 knife_finish_cut(kcd);
1863                                 kcd->mode = MODE_IDLE;
1864                                 break;
1865                         case KNF_MODAL_ADD_CUT:
1866                                 knife_recalc_projmat(kcd);
1867
1868                                 if (kcd->mode == MODE_DRAGGING) {
1869                                         knife_add_cut(kcd);
1870                                         if (!kcd->extend) {
1871                                                 knife_finish_cut(kcd);
1872                                                 kcd->mode = MODE_IDLE;
1873                                         }
1874                                 } else if (kcd->mode != MODE_PANNING) {
1875                                         knife_start_cut(kcd);
1876                                         kcd->mode = MODE_DRAGGING;
1877                                 }
1878                 
1879                                 ED_region_tag_redraw(kcd->ar);
1880                                 break;
1881                         }
1882         } else { /*non-modal-mapped events*/
1883                 switch (event->type) {
1884                         case WHEELUPMOUSE:
1885                         case WHEELDOWNMOUSE:
1886                                 return OPERATOR_PASS_THROUGH;
1887                         case MIDDLEMOUSE:
1888                                 if (event->val != KM_RELEASE) {
1889                                         if (kcd->mode != MODE_PANNING)
1890                                                 kcd->prevmode = kcd->mode;
1891                                         kcd->mode = MODE_PANNING;
1892                                 } else {
1893                                         kcd->mode = kcd->prevmode;
1894                                 }
1895                                 
1896                                 ED_region_tag_redraw(kcd->ar);
1897                                 return OPERATOR_PASS_THROUGH;
1898                                 
1899                         case MOUSEMOVE:  /* mouse moved somewhere to select another loop */
1900                                 if (kcd->mode != MODE_PANNING) {
1901                                         knife_recalc_projmat(kcd);
1902                                         kcd->vc.mval[0] = event->mval[0];
1903                                         kcd->vc.mval[1] = event->mval[1];
1904                                         
1905                                         if (knife_update_active(kcd))                                   
1906                                                 ED_region_tag_redraw(kcd->ar);
1907                                 }
1908         
1909                                 break;
1910                 }
1911         }
1912         
1913         /* keep going until the user confirms */
1914         return OPERATOR_RUNNING_MODAL;
1915 }
1916
1917 void MESH_OT_knifetool (wmOperatorType *ot)
1918 {
1919         /* description */
1920         ot->name= "Knife Topology Tool";
1921         ot->idname= "MESH_OT_knifetool";
1922         ot->description= "Cut new topology";
1923         
1924         /* callbacks */
1925         ot->invoke= knifetool_invoke;
1926         ot->modal= knifetool_modal;
1927         ot->cancel= knifetool_cancel;
1928         ot->poll= ED_operator_editmesh_view3d;
1929         
1930         /* flags */
1931         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO|OPTYPE_BLOCKING;
1932 }