merge with/from trunk at r35190
[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_windowmanager_types.h"
41 #include "DNA_object_types.h"
42
43 #include "MEM_guardedalloc.h"
44
45 #include "PIL_time.h"
46
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_kdopbvh.h"
56 #include "BLI_smallhash.h"
57
58 #include "BKE_blender.h"
59 #include "BKE_context.h"
60 #include "BKE_depsgraph.h"
61 #include "BKE_scene.h"
62 #include "BKE_mesh.h"
63 #include "BKE_tessmesh.h"
64 #include "BKE_depsgraph.h"
65
66 #include "BIF_gl.h"
67 #include "BIF_glutil.h" /* for paint cursor */
68
69 #include "IMB_imbuf_types.h"
70
71 #include "ED_screen.h"
72 #include "ED_space_api.h"
73 #include "ED_view3d.h"
74 #include "ED_mesh.h"
75
76 #include "RNA_access.h"
77 #include "RNA_define.h"
78
79 #include "UI_interface.h"
80
81 #include "WM_api.h"
82 #include "WM_types.h"
83
84 #include "mesh_intern.h"
85 #include "editbmesh_bvh.h"
86
87 #define MAXGROUP        30
88
89 /* knifetool operator */
90 typedef struct KnifeVert {
91         BMVert *v; /*non-NULL if this is an original vert*/
92         ListBase edges;
93
94         float co[3], sco[3]; /*sco is screen coordinates*/
95         short flag, draw, isface;
96 } KnifeVert;
97
98 typedef struct Ref {
99         struct Ref *next, *prev;
100         void *ref;
101 } Ref;
102
103 typedef struct KnifeEdge {
104         KnifeVert *v1, *v2;
105         BMFace *basef; /*face to restrict face fill to*/
106         ListBase faces;
107         int draw;
108         
109         BMEdge *e, *oe; /*non-NULL if this is an original edge*/
110 } KnifeEdge;
111
112 #define KMAXDIST        12      /*max mouse distance from edge before not detecting it*/
113 #define MARK            4
114 #define DEL                     8
115
116 typedef struct BMEdgeHit {
117         KnifeEdge *kfe;
118         float hit[3];
119         float shit[3];
120         float l; /*lambda along line*/
121         BMVert *v; //set if snapped to a vert
122         BMFace *f;
123 } BMEdgeHit;
124
125 /* struct for properties used while drawing */
126 typedef struct knifetool_opdata {
127         ARegion *ar;            /* region that knifetool was activated in */
128         void *draw_handle;      /* for drawing preview loop */
129         ViewContext vc;
130         bContext *C;
131         
132         Object *ob;
133         BMEditMesh *em;
134         
135         MemArena *arena;
136
137         GHash *origvertmap;
138         GHash *origedgemap;
139         
140         GHash *kedgefacemap;
141         
142         BMBVHTree *bmbvh;
143
144         BLI_mempool *kverts;
145         BLI_mempool *kedges;
146         
147         float vthresh;
148         float ethresh;
149         
150         float vertco[3];
151         float prevco[3];
152         
153         /*used for drag-cutting*/
154         BMEdgeHit *linehits;
155         int totlinehit;
156         
157         /*if curedge is NULL, attach to curvert;
158           if curvert is NULL, attach to curbmface,
159           otherwise create null vert*/
160         KnifeEdge *curedge, *prevedge;
161         KnifeVert *curvert, *prevvert;
162         BMFace *curbmface, *prevbmface;
163
164         int totkedge, totkvert, cutnr;
165         
166         BLI_mempool *refs;
167         
168         float projmat[4][4];
169         int is_ortho, clipsta, clipend;
170         
171         enum {
172                 MODE_IDLE,
173                 MODE_DRAGGING,
174                 MODE_CONNECT,
175         } mode;
176 } knifetool_opdata;
177
178 static ListBase *knife_get_face_kedges(knifetool_opdata *kcd, BMFace *f);
179
180 void knife_project_v3(knifetool_opdata *kcd, float co[3], float sco[3])
181 {
182         if (kcd->is_ortho) {
183                 mul_v3_m4v3(sco, kcd->projmat, co);
184                 
185                 sco[0] = (float)(kcd->ar->winx/2.0f)+(kcd->ar->winx/2.0f)*sco[0];
186                 sco[1] = (float)(kcd->ar->winy/2.0f)+(kcd->ar->winy/2.0f)*sco[1];
187         } else
188                 view3d_project_float(kcd->ar, co, sco, kcd->projmat);
189 }
190
191 static KnifeEdge *new_knife_edge(knifetool_opdata *kcd)
192 {
193         kcd->totkedge++;
194         return BLI_mempool_calloc(kcd->kedges);
195 }
196
197 static KnifeVert *new_knife_vert(knifetool_opdata *kcd, float *co)
198 {
199         KnifeVert *kfv = BLI_mempool_calloc(kcd->kverts);
200         
201         kcd->totkvert++;
202         
203         copy_v3_v3(kfv->co, co);
204         copy_v3_v3(kfv->sco, co);
205
206         knife_project_v3(kcd, kfv->co, kfv->sco);
207
208         return kfv;
209 }
210
211 /*get a KnifeVert wrapper for an existing BMVert*/
212 static KnifeVert *get_bm_knife_vert(knifetool_opdata *kcd, BMVert *v)
213 {
214         KnifeVert *kfv = BLI_ghash_lookup(kcd->origvertmap, v);
215         
216         if (!kfv) {
217                 kfv = new_knife_vert(kcd, v->co);
218                 kfv->v = v;
219                 BLI_ghash_insert(kcd->origvertmap, v, kfv);
220         }
221         
222         return kfv;
223 }
224
225 /*get a KnifeEdge wrapper for an existing BMEdge*/
226 static KnifeEdge *get_bm_knife_edge(knifetool_opdata *kcd, BMEdge *e)
227 {
228         KnifeEdge *kfe = BLI_ghash_lookup(kcd->origedgemap, e);
229         if (!kfe) {
230                 Ref *ref;
231                 BMIter iter;
232                 BMFace *f;
233                 
234                 kfe = new_knife_edge(kcd);
235                 kfe->e = e;
236                 kfe->v1 = get_bm_knife_vert(kcd, e->v1);
237                 kfe->v2 = get_bm_knife_vert(kcd, e->v2);
238                 
239                 ref = BLI_mempool_calloc(kcd->refs);
240                 ref->ref = kfe;
241                 BLI_addtail(&kfe->v1->edges, ref);
242
243                 ref = BLI_mempool_calloc(kcd->refs);
244                 ref->ref = kfe;
245                 BLI_addtail(&kfe->v2->edges, ref);
246                 
247                 BLI_ghash_insert(kcd->origedgemap, e, kfe);
248                 
249                 BM_ITER(f, &iter, kcd->em->bm, BM_FACES_OF_EDGE, e) {
250                         ref = BLI_mempool_calloc(kcd->refs);
251                         ref->ref = f;
252                         BLI_addtail(&kfe->faces, ref);
253                         
254                         /*ensures the kedges lst for this f is initialized,
255                           it automatically adds kfe by itself*/
256                         knife_get_face_kedges(kcd, f);
257                 }
258         }
259         
260         return kfe;
261 }
262
263 static void knife_start_cut(knifetool_opdata *kcd)
264 {
265         kcd->prevedge = kcd->curedge;
266         kcd->prevvert = kcd->curvert;
267         kcd->prevbmface = kcd->curbmface;
268         kcd->cutnr++;
269         
270         copy_v3_v3(kcd->prevco, kcd->vertco);
271 }
272
273 static Ref *find_ref(ListBase *lb, void *ref)
274 {
275         Ref *ref1;
276         
277         for (ref1=lb->first; ref1; ref1=ref1->next) {
278                 if (ref1->ref == ref)
279                         return ref1;
280         }
281         
282         return NULL;
283 }
284
285 static ListBase *knife_get_face_kedges(knifetool_opdata *kcd, BMFace *f)
286 {
287         ListBase *lst = BLI_ghash_lookup(kcd->kedgefacemap, f);
288         
289         if (!lst) {
290                 BMIter iter;
291                 BMEdge *e;
292                 
293                 lst = BLI_memarena_alloc(kcd->arena, sizeof(ListBase));
294                 lst->first = lst->last = NULL;
295                 
296                 BM_ITER(e, &iter, kcd->em->bm, BM_EDGES_OF_FACE, f) {
297                         Ref *ref = BLI_mempool_calloc(kcd->refs);
298                         ref->ref = get_bm_knife_edge(kcd, e);
299                         BLI_addtail(lst, ref);
300                 }
301                 
302                 BLI_ghash_insert(kcd->kedgefacemap, f, lst);
303         }
304         
305         return lst;
306 }
307
308 /*finds the proper face to restrict face fill to*/
309 void knife_find_basef(knifetool_opdata *kcd, KnifeEdge *kfe)
310 {
311         if (!kfe->basef) {
312                 Ref *r1, *r2, *r3, *r4;
313                 
314                 if (kfe->v1->isface || kfe->v2->isface) {
315                         if (kfe->v2->isface)
316                                 kfe->basef = kcd->curbmface;
317                         else 
318                                 kfe->basef = kcd->prevbmface;
319                 } else {                
320                         for (r1=kfe->v1->edges.first; r1 && !kfe->basef; r1=r1->next) {
321                                 KnifeEdge *ke1 = r1->ref;
322                                 for (r2=ke1->faces.first; r2 && !kfe->basef; r2=r2->next) {
323                                         for (r3=kfe->v2->edges.first; r3 && !kfe->basef; r3=r3->next) {
324                                                 KnifeEdge *ke2 = r3->ref;
325                                         
326                                                 for (r4=ke2->faces.first; r4 && !kfe->basef; r4=r4->next) {
327                                                         if (r2->ref == r4->ref) {
328                                                                 kfe->basef = r2->ref;
329                                                         }
330                                                 }       
331                                         }
332                                 }
333                         }
334                 }
335                 /*ok, at this point kfe->basef should be set if any valid possibility
336                   exists*/
337         }
338 }
339
340 static KnifeVert *knife_split_edge(knifetool_opdata *kcd, KnifeEdge *kfe, float co[3], KnifeEdge **newkfe_out)
341 {
342         KnifeEdge *newkfe = new_knife_edge(kcd);
343         ListBase *lst;
344         Ref *ref;
345         
346         newkfe->v1 = kfe->v1;
347         newkfe->v2 = new_knife_vert(kcd, co);
348         newkfe->v2->draw = 1;
349         newkfe->basef = kfe->basef;
350         
351         ref = find_ref(&kfe->v1->edges, kfe);
352         BLI_remlink(&kfe->v1->edges, ref);
353         
354         kfe->v1 = newkfe->v2;
355         BLI_addtail(&kfe->v1->edges, ref);
356         
357         for (ref=kfe->faces.first; ref; ref=ref->next) {
358                 Ref *ref2 = BLI_mempool_calloc(kcd->refs);
359                 
360                 /*add kedge ref to bm faces*/
361                 lst = knife_get_face_kedges(kcd, ref->ref);
362                 ref2->ref = newkfe;
363                 BLI_addtail(lst, ref2);
364
365                 ref2 = BLI_mempool_calloc(kcd->refs);
366                 ref2->ref = ref->ref;
367                 BLI_addtail(&newkfe->faces, ref2);
368         }
369
370         ref = BLI_mempool_calloc(kcd->refs);
371         ref->ref = newkfe;
372         BLI_addtail(&newkfe->v1->edges, ref);
373
374         ref = BLI_mempool_calloc(kcd->refs);
375         ref->ref = newkfe;
376         BLI_addtail(&newkfe->v2->edges, ref);
377         
378         newkfe->draw = kfe->draw;
379         newkfe->e = kfe->e;
380         
381         *newkfe_out = newkfe;
382                         
383         return newkfe->v2;
384 }
385
386 static void knife_edge_append_face(knifetool_opdata *kcd, KnifeEdge *kfe, BMFace *f)
387 {
388         ListBase *lst = knife_get_face_kedges(kcd, f);
389         Ref *ref = BLI_mempool_calloc(kcd->refs);
390         
391         ref->ref = kfe;
392         BLI_addtail(lst, ref);
393         
394         ref = BLI_mempool_calloc(kcd->refs);
395         ref->ref = f;
396         BLI_addtail(&kfe->faces, ref);
397 }
398
399 static void knife_copy_edge_facelist(knifetool_opdata *kcd, KnifeEdge *dest, KnifeEdge *source) 
400 {
401         Ref *ref, *ref2;
402         
403         for (ref2 = source->faces.first; ref2; ref2=ref2->next) {
404                 ListBase *lst = knife_get_face_kedges(kcd, ref2->ref);
405                 
406                 /*add new edge to face knife edge list*/
407                 ref = BLI_mempool_calloc(kcd->refs);
408                 ref->ref = dest;
409                 BLI_addtail(lst, ref);
410                 
411                 /*add face to new edge's face list*/
412                 ref = BLI_mempool_calloc(kcd->refs);
413                 ref->ref = ref2->ref;
414                 BLI_addtail(&dest->faces, ref);
415         }
416 }
417
418 static void knife_add_single_cut(knifetool_opdata *kcd)
419 {
420         KnifeEdge *kfe = new_knife_edge(kcd), *kfe2 = NULL, *kfe3 = NULL;
421         Ref *ref;
422         
423         if (kcd->prevvert && kcd->prevvert == kcd->curvert)
424                 return;
425         if (kcd->prevedge && kcd->prevedge == kcd->curedge)
426                 return;
427         
428         if (kcd->prevvert) {
429                 kfe->v1 = kcd->prevvert;
430         } else if (kcd->prevedge) {
431                 kfe->v1 = knife_split_edge(kcd, kcd->prevedge, kcd->prevco, &kfe2);
432         } else {
433                 kfe->v1 = new_knife_vert(kcd, kcd->prevco);
434                 kfe->v1->draw = 1;
435                 kfe->v1->isface = 1;
436         }
437         
438         if (kcd->curvert) {
439                 kfe->v2 = kcd->curvert;
440         } else if (kcd->curedge) {
441                 kfe->v2 = knife_split_edge(kcd, kcd->curedge, kcd->vertco, &kfe3);
442                 
443                 kcd->curvert = kfe->v2;
444         } else {
445                 kfe->v2 = new_knife_vert(kcd, kcd->vertco);
446                 kfe->v2->draw = 1;
447                 kfe->v2->isface = 1;
448
449                 kcd->curvert = kfe->v2;
450         }
451         
452         knife_find_basef(kcd, kfe);
453         
454         kfe->draw = 1;
455         
456         ref = BLI_mempool_calloc(kcd->refs);
457         ref->ref = kfe; 
458         BLI_addtail(&kfe->v1->edges, ref);
459
460         ref = BLI_mempool_calloc(kcd->refs);
461         ref->ref = kfe;
462         BLI_addtail(&kfe->v2->edges, ref);      
463         
464         if (kfe->basef && !find_ref(&kfe->faces, kfe->basef))
465                 knife_edge_append_face(kcd, kfe, kfe->basef);
466
467         /*sanity check to make sure we're in the right edge/face lists*/
468         if (kcd->curbmface) {
469                 if (!find_ref(&kfe->faces, kcd->curbmface)) {
470                         knife_edge_append_face(kcd, kfe, kcd->curbmface);
471                 }
472
473                 if (kcd->prevbmface && kcd->prevbmface != kcd->curbmface) {
474                         if (!find_ref(&kfe->faces, kcd->prevbmface)) {
475                                 knife_edge_append_face(kcd, kfe, kcd->prevbmface);
476                         }
477                 }
478         }
479                 
480         /*set up for next cut*/
481         kcd->prevbmface = kcd->curbmface;
482         kcd->prevvert = kcd->curvert;
483         kcd->prevedge = kcd->curedge;
484         copy_v3_v3(kcd->prevco, kcd->vertco);
485 }
486
487 static int verge_linehit(const void *vlh1, const void *vlh2)
488 {
489         const BMEdgeHit *lh1=vlh1, *lh2=vlh2;
490
491         if (lh1->l < lh2->l) return -1;
492         else if (lh1->l > lh2->l) return 1;
493         else return 0;
494 }
495
496 static void knife_add_cut(knifetool_opdata *kcd)
497 {
498         BMEditMesh *em = kcd->em;
499         BMesh *bm = em->bm;
500         knifetool_opdata oldkcd = *kcd;
501         
502         if (kcd->linehits) {
503                 BMEdgeHit *lh, *lastlh, *firstlh;
504                 int i;
505                 
506                 qsort(kcd->linehits, kcd->totlinehit, sizeof(BMEdgeHit), verge_linehit);
507                 
508                 lh = kcd->linehits;
509                 lastlh = firstlh = NULL;
510                 for (i=0; i<kcd->totlinehit; i++, (lastlh=lh), lh++) {
511                         BMFace *f = lastlh ? lastlh->f : lh->f;
512                         
513                         if (lastlh && len_v3v3(lastlh->hit, lh->hit) == 0.0f) {
514                                 if (!firstlh)
515                                         firstlh = lastlh;
516                                 continue;
517                         } else if (lastlh && firstlh) {
518                                 if (firstlh->v || lastlh->v) {
519                                         KnifeVert *kfv = firstlh->v ? firstlh->v : lastlh->v;
520                                         
521                                         kcd->prevvert = kfv;
522                                         copy_v3_v3(kcd->prevco, firstlh->hit);
523                                         kcd->prevedge = NULL;
524                                         kcd->prevbmface = f;
525                                 }
526                                 lastlh = firstlh = NULL;
527                         }
528                         
529                         if (!lastlh && len_v3v3(kcd->prevco, lh->hit) < FLT_EPSILON*10)
530                                 continue;
531                         
532                         kcd->curedge = lh->kfe;
533                         kcd->curbmface = lh->f;
534                         kcd->curvert = lh->v;
535                         copy_v3_v3(kcd->vertco, lh->hit);
536
537                         knife_add_single_cut(kcd);
538                 }
539                 
540                 kcd->curbmface = oldkcd.curbmface;
541                 kcd->curvert = oldkcd.curvert;
542                 kcd->curedge = oldkcd.curedge;
543                 copy_v3_v3(kcd->vertco, oldkcd.vertco);
544                 
545                 knife_add_single_cut(kcd);
546                 
547                 MEM_freeN(kcd->linehits);
548                 kcd->linehits = NULL;
549                 kcd->totlinehit = 0;
550         } else {
551                 knife_add_single_cut(kcd);
552         }
553 }
554
555 static void knife_finish_cut(knifetool_opdata *kcd)
556 {
557
558 }
559
560 /* modal loop selection drawing callback */
561 static void knifetool_draw(const bContext *C, ARegion *ar, void *arg)
562 {
563         knifetool_opdata *kcd = arg;
564         
565         glDisable(GL_DEPTH_TEST);
566
567         glPushMatrix();
568         glMultMatrixf(kcd->ob->obmat);
569         
570         if (kcd->mode == MODE_DRAGGING) {
571                 glColor3f(0.1, 0.1, 0.1);
572                 glLineWidth(2.0);
573                 
574                 glBegin(GL_LINES);
575                 glVertex3fv(kcd->prevco);       
576                 glVertex3fv(kcd->vertco);
577                 glEnd();
578                 
579                 glLineWidth(1.0);       
580         }
581         
582         if (kcd->curedge) {
583                 glColor3f(0.5, 0.3, 0.15);
584                 glLineWidth(2.0);
585                 
586                 glBegin(GL_LINES);
587                 glVertex3fv(kcd->curedge->v1->co);      
588                 glVertex3fv(kcd->curedge->v2->co);
589                 glEnd();
590                 
591                 glLineWidth(1.0);
592         } else if (kcd->curvert) {
593                 glColor3f(0.8, 0.2, 0.1);
594                 glPointSize(9);
595                 
596                 glBegin(GL_POINTS);
597                 glVertex3fv(kcd->vertco);
598                 glEnd();
599         }
600         
601         if (kcd->curbmface) {           
602                 glColor3f(0.1, 0.8, 0.05);
603                 glPointSize(7);
604                 
605                 glBegin(GL_POINTS);
606                 glVertex3fv(kcd->vertco);
607                 glEnd();
608         }
609         
610         if (kcd->totlinehit > 0) {
611                 BMEdgeHit *lh;
612                 int i;
613                 
614                 glEnable(GL_BLEND);
615                 glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
616                 
617                 /*draw any snapped verts first*/
618                 glColor4f(0.8, 0.2, 0.1, 0.4);
619                 glPointSize(9);
620                 glBegin(GL_POINTS);
621                 lh = kcd->linehits;
622                 for (i=0; i<kcd->totlinehit; i++, lh++) {
623                         float sv1[3], sv2[3];
624                         
625                         knife_project_v3(kcd, lh->kfe->v1->co, sv1);
626                         knife_project_v3(kcd, lh->kfe->v2->co, sv2);
627                         
628                         if (len_v2v2(lh->shit, sv1) < kcd->vthresh/4) {
629                                 copy_v3_v3(lh->hit, lh->kfe->v1->co);
630                                 glVertex3fv(lh->hit);
631                                 lh->v = lh->kfe->v1;
632                         } else if (len_v2v2(lh->shit, sv2) < kcd->vthresh/4) {
633                                 copy_v3_v3(lh->hit, lh->kfe->v2->co);
634                                 glVertex3fv(lh->hit);
635                                 lh->v = lh->kfe->v2;
636                         }
637                 }
638                 glEnd();
639                 
640                 /*now draw the rest*/
641                 glColor4f(0.1, 0.8, 0.05, 0.4);
642                 glPointSize(5);
643                 glBegin(GL_POINTS);
644                 lh = kcd->linehits;
645                 for (i=0; i<kcd->totlinehit; i++, lh++) {
646                         glVertex3fv(lh->hit);
647                 }
648                 glEnd();
649                 glDisable(GL_BLEND);
650         }
651         
652         if (kcd->totkedge > 0) {
653                 BLI_mempool_iter iter;
654                 KnifeEdge *kfe;
655                 
656                 glLineWidth(1.0);
657                 glBegin(GL_LINES);
658
659                 BLI_mempool_iternew(kcd->kedges, &iter);
660                 for (kfe=BLI_mempool_iterstep(&iter); kfe; kfe=BLI_mempool_iterstep(&iter)) {
661                         if (!kfe->draw)
662                                 continue;
663                                 
664                         glColor3f(0.2, 0.2, 0.2);
665                         
666                         glVertex3fv(kfe->v1->co);
667                         glVertex3fv(kfe->v2->co);
668                 }
669                 
670                 glEnd();                
671                 glLineWidth(1.0);       
672         }
673
674         if (kcd->totkvert > 0) {
675                 BLI_mempool_iter iter;
676                 KnifeVert *kfv;
677                 
678                 glPointSize(4.0);
679                                 
680                 glBegin(GL_POINTS);
681                 BLI_mempool_iternew(kcd->kverts, &iter);
682                 for (kfv=BLI_mempool_iterstep(&iter); kfv; kfv=BLI_mempool_iterstep(&iter)) {
683                         if (!kfv->draw)
684                                 continue;
685                                 
686                         glColor3f(0.6, 0.1, 0.2);
687                         
688                         glVertex3fv(kfv->co);
689                 }
690                 
691                 glEnd();                
692         }
693
694         glPopMatrix();
695         glEnable(GL_DEPTH_TEST);
696 }
697
698 void _print_smhash(SmallHash *hash)
699 {
700         int i, linecol=79, c=0;
701         
702         printf("{");
703         for (i=0; i<hash->size; i++) {
704                 if (hash->table[i].val == CELL_UNUSED) {
705                         printf("--u-");
706                 } else if (hash->table[i].val == CELL_FREE) {
707                         printf("--f-");
708                 } else  {
709                         printf("%2x", (intptr_t)hash->table[i].key);
710                 }
711                 
712                 if (i != hash->size-1)
713                         printf(", ");
714                 
715                 c += 6;
716                 
717                 if (c >= linecol) {
718                         printf("\n ");
719                         c = 0;
720                 }
721         }
722         
723         fflush(stdout);
724 }
725
726 BMEdgeHit *knife_edge_tri_isect(knifetool_opdata *kcd, BMBVHTree *bmtree, float v1[3], 
727                               float v2[3], float v3[3], SmallHash *ehash, bglMats *mats, int *count)
728 {
729         BVHTree *tree2 = BLI_bvhtree_new(3, FLT_EPSILON*4, 8, 8), *tree = BMBVH_BVHTree(bmtree);
730         BMEdgeHit *edges = NULL;
731         BLI_array_declare(edges);
732         BVHTreeOverlap *results, *result;
733         BMLoop **ls;
734         float cos[9], uv[3], lambda;
735         int tot=0, i, j;
736         
737         copy_v3_v3(cos, v1);
738         copy_v3_v3(cos+3, v2);
739         copy_v3_v3(cos+6, v3);
740         
741         BLI_bvhtree_insert(tree2, 0, cos, 3);
742         BLI_bvhtree_balance(tree2);
743         
744         result = results = BLI_bvhtree_overlap(tree, tree2, &tot);
745         
746         for (i=0; i<tot; i++, result++) {
747                 float p[3];
748                 
749                 ls = (BMLoop**)kcd->em->looptris[result->indexA];
750                 
751                 for (j=0; j<3; j++) {
752                         BMLoop *l1 = ls[j];     
753                         ListBase *lst = knife_get_face_kedges(kcd, l1->f);
754                         Ref *ref;
755                         
756                         for (ref=lst->first; ref; ref=ref->next) {                      
757                                 KnifeEdge *kfe = ref->ref;
758                                 
759                                 if (isect_line_tri_v3(kfe->v1->co, kfe->v2->co, v1, v2, v3, &lambda, uv)) {
760                                         float no[3], view[3], sp[3];
761                                         
762                                         sub_v3_v3v3(p, kfe->v2->co, kfe->v1->co);
763                                         mul_v3_fl(p, lambda);
764                                         add_v3_v3(p, kfe->v1->co);
765                                         
766                                         knife_project_v3(kcd, p, sp);
767                                         view3d_unproject(mats, view, sp[0], sp[1], 0.0f);
768                                         mul_m4_v3(kcd->ob->imat, view);
769
770                                         sub_v3_v3v3(view, p, view);
771                                         normalize_v3(view);;
772         
773                                         copy_v3_v3(no, view);
774                                         mul_v3_fl(no, -0.0003);
775                                         
776                                         /*go backwards toward view a bit*/
777                                         add_v3_v3(p, no);
778                                         
779                                         if (!BMBVH_RayCast(bmtree, p, no, NULL) && !BLI_smallhash_haskey(ehash, (intptr_t)kfe)) {
780                                                 BMEdgeHit hit;
781                                                 
782                                                 hit.kfe = kfe;
783                                                 hit.v = NULL;
784                                                 
785                                                 knife_find_basef(kcd, kfe);
786                                                 hit.f = kfe->basef;
787                                                 
788                                                 copy_v3_v3(hit.hit, p);
789                                                 knife_project_v3(kcd, hit.hit, hit.shit);
790                                                 
791                                                 BLI_array_append(edges, hit);
792                                                 BLI_smallhash_insert(ehash, (intptr_t)kfe, NULL);
793                                         }
794                                 }
795                         }
796                 }
797         }
798         
799         if (results)
800                 MEM_freeN(results);
801         
802         *count = BLI_array_count(edges);
803         return edges;
804 }
805
806 void knife_bgl_get_mats(knifetool_opdata *kcd, bglMats *mats)
807 {
808         bgl_get_mats(mats);
809         //copy_m4_m4(mats->modelview, kcd->vc.rv3d->viewmat);
810         //copy_m4_m4(mats->projection, kcd->vc.rv3d->winmat);
811 }
812
813 /*finds (visible) edges that intersects the current screen drag line*/
814 static void knife_find_line_hits(knifetool_opdata *kcd)
815 {
816         bglMats mats;
817         BMEdgeHit *e1, *e2;
818         SmallHash hash, *ehash = &hash;
819         float v1[3], v2[3], v3[3], v4[4], s1[3], s2[3], view[3];
820         int i, c1, c2;
821         
822         knife_bgl_get_mats(kcd, &mats);
823         
824         if (kcd->linehits) {
825                 MEM_freeN(kcd->linehits);
826                 kcd->linehits = NULL;
827                 kcd->totlinehit = 0;
828         }
829         
830         /*project screen line's 3d coordinates back into 2d*/
831         knife_project_v3(kcd, kcd->prevco, s1);
832         knife_project_v3(kcd, kcd->vertco, s2);
833         
834         if (len_v2v2(s1, s2) < 1)
835                 return;
836
837         /*unproject screen line*/
838         view3d_unproject(&mats, v1, s1[0], s1[1], 0.0f);
839         view3d_unproject(&mats, v2, s2[0], s2[1], 0.0f);
840         view3d_unproject(&mats, v3, s1[0], s1[1], 1.0f-FLT_EPSILON);
841         view3d_unproject(&mats, v4, s2[0], s2[1], 1.0f-FLT_EPSILON);
842         
843         mul_m4_v3(kcd->ob->imat, v1);
844         mul_m4_v3(kcd->ob->imat, v2);
845         mul_m4_v3(kcd->ob->imat, v3);
846         mul_m4_v3(kcd->ob->imat, v4);
847         
848         sub_v3_v3v3(view, v4, v1);
849         normalize_v3(view);
850         
851         BLI_smallhash_init(ehash);
852         
853         /*test two triangles of sceen line's plane*/
854         e1 = knife_edge_tri_isect(kcd, kcd->bmbvh, v1, v2, v3, ehash, &mats, &c1);
855         e2 = knife_edge_tri_isect(kcd, kcd->bmbvh, v1, v3, v4, ehash, &mats, &c2);
856         if (c1 && c2) {
857                 e1 = MEM_reallocN(e1, sizeof(BMEdgeHit)*(c1+c2));
858                 memcpy(e1+c1, e2, sizeof(BMEdgeHit)*c2);
859                 MEM_freeN(e2);
860         } else if (c2) {
861                 e1 = e2;
862         }
863         
864         kcd->linehits = e1;
865         kcd->totlinehit = c1+c2;
866
867         /*find position along screen line, used for sorting*/
868         for (i=0; i<kcd->totlinehit; i++) {
869                 BMEdgeHit *lh = e1+i;
870                 
871                 lh->l = len_v2v2(lh->shit, s1) / len_v2v2(s2, s1);
872         }
873         
874         BLI_smallhash_release(ehash);
875 }
876
877 static BMFace *knife_find_closest_face(knifetool_opdata *kcd, float co[3])
878 {
879         BMFace *f;
880         bglMats mats;
881         float origin[3], ray[3];
882         float mval[2];
883         int dist = KMAXDIST; 
884         
885         knife_bgl_get_mats(kcd, &mats);
886
887         mval[0] = kcd->vc.mval[0]; mval[1] = kcd->vc.mval[1];
888         
889         /*unproject to find view ray*/
890         view3d_unproject(&mats, origin, mval[0], mval[1], 0.0f);
891
892         sub_v3_v3v3(ray, origin, kcd->vc.rv3d->viewinv[3]);
893         normalize_v3(ray);
894         
895         /*transform into object space*/
896         mul_m4_v3(kcd->ob->imat, origin);
897         mul_m4_v3(kcd->ob->imat, ray);
898         
899         f = BMBVH_RayCast(kcd->bmbvh, origin, ray, co);
900         if (!f) {
901                 /*try to use backbuffer selection method if ray casting failed*/
902                 f = EDBM_findnearestface(&kcd->vc, &dist);
903                 
904                 /*cheat for now; just put in the origin instead 
905                   of a true coordinate on the face*/
906                 copy_v3_v3(co, origin);
907         }
908         
909         //copy_v3_v3(co, origin);
910         
911         return f;
912 }
913
914 /*find the 2d screen space density of vertices within a radius.  used to scale snapping
915   distance for picking edges/verts.*/
916 static int knife_sample_screen_density(knifetool_opdata *kcd, float radius)
917 {
918         BMFace *f;
919         float co[3], sco[3];
920         
921         f = knife_find_closest_face(kcd, co);
922         
923         if (f) {
924                 ListBase *lst;
925                 Ref *ref;
926                 KnifeVert *curv = NULL;
927                 float dis;
928                 int c = 0;
929                 
930                 knife_project_v3(kcd, co, sco);
931                 
932                 lst = knife_get_face_kedges(kcd, f);
933                 for (ref=lst->first; ref; ref=ref->next) {
934                         KnifeEdge *kfe = ref->ref;
935                         int i;
936                         
937                         for (i=0; i<2; i++) {
938                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
939                                 
940                                 knife_project_v3(kcd, kfv->co, kfv->sco);
941                                 
942                                 dis = len_v2v2(kfv->sco, sco);
943                                 if (dis < radius) {
944                                         if(kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
945                                                 float vec[3];
946                                                 
947                                                 copy_v3_v3(vec, kfv->co);
948                                                 mul_m4_v3(kcd->vc.obedit->obmat, vec);
949                         
950                                                 if(view3d_test_clipping(kcd->vc.rv3d, vec, 1)==0) {
951                                                         c++;
952                                                 }
953                                         } else {
954                                                 c++;
955                                         }
956                                 }
957                         }
958                 }
959                 
960                 return c;
961         }
962                 
963         return 0;
964 }
965
966 /*returns snapping distance for edges/verts, scaled by the density of the
967   surrounding mesh (in screen space)*/
968 static float knife_snap_size(knifetool_opdata *kcd, float maxsize)
969 {
970         float density = (float)knife_sample_screen_density(kcd, maxsize*2.0f);
971         
972         density = MAX2(density, 1);
973         
974         return MIN2(maxsize / (density*0.5f), maxsize);
975 }
976
977 /*p is closest point on edge to the mouse cursor*/
978 static KnifeEdge *knife_find_closest_edge(knifetool_opdata *kcd, float p[3], BMFace **fptr)
979 {
980         BMFace *f;
981         float co[3], sco[3], maxdist = knife_snap_size(kcd, kcd->ethresh);
982         
983         f = knife_find_closest_face(kcd, co);
984         /*set p to co, in case we don't find anything, means a face cut*/
985         copy_v3_v3(p, co);
986
987         if (f) {
988                 KnifeEdge *cure = NULL;
989                 ListBase *lst;
990                 Ref *ref;
991                 float dis, curdis=FLT_MAX;
992                 
993                 knife_project_v3(kcd, co, sco);
994                 
995                 /*look through all edges associated with this face*/
996                 lst = knife_get_face_kedges(kcd, f);
997                 for (ref=lst->first; ref; ref=ref->next) {
998                         KnifeEdge *kfe = ref->ref;
999                         
1000                         /*project edge vertices into screen space*/
1001                         knife_project_v3(kcd, kfe->v1->co, kfe->v1->sco);
1002                         knife_project_v3(kcd, kfe->v2->co, kfe->v2->sco);
1003
1004                         dis = dist_to_line_segment_v2(sco, kfe->v1->sco, kfe->v2->sco);
1005                         if (dis < curdis && dis < maxdist) {
1006                                 if(kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1007                                         float labda_PdistVL2Dfl(float *v1, float *v2, float *v3);
1008                                         float labda= labda_PdistVL2Dfl(sco, kfe->v1->sco, kfe->v2->sco);
1009                                         float vec[3];
1010                 
1011                                         vec[0]= kfe->v1->co[0] + labda*(kfe->v2->co[0] - kfe->v1->co[0]);
1012                                         vec[1]= kfe->v1->co[1] + labda*(kfe->v2->co[1] - kfe->v1->co[1]);
1013                                         vec[2]= kfe->v1->co[2] + labda*(kfe->v2->co[2] - kfe->v1->co[2]);
1014                                         mul_m4_v3(kcd->vc.obedit->obmat, vec);
1015                 
1016                                         if(view3d_test_clipping(kcd->vc.rv3d, vec, 1)==0) {
1017                                                 cure = kfe;
1018                                                 curdis = dis;
1019                                         }
1020                                 } else {
1021                                         cure = kfe;
1022                                         curdis = dis;                           
1023                                 }
1024                         }
1025                 }
1026                 
1027                 if (fptr)
1028                         *fptr = f;
1029                 
1030                 if (cure && p) {
1031                         closest_to_line_segment_v3(p, co, cure->v1->co, cure->v2->co);
1032                 }
1033                 
1034                 return cure;
1035         }
1036                 
1037         if (fptr)
1038                 *fptr = NULL;
1039         
1040         return NULL;
1041 }
1042
1043 /*find a vertex near the mouse cursor, if it exists*/
1044 static KnifeVert *knife_find_closest_vert(knifetool_opdata *kcd, float p[3], BMFace **fptr)
1045 {
1046         BMFace *f;
1047         float co[3], sco[3], maxdist = knife_snap_size(kcd, kcd->vthresh);
1048         
1049         f = knife_find_closest_face(kcd, co);
1050         /*set p to co, in case we don't find anything, means a face cut*/
1051         copy_v3_v3(p, co);
1052         
1053         if (f) {
1054                 ListBase *lst;
1055                 Ref *ref;
1056                 KnifeVert *curv = NULL;
1057                 float dis, curdis=FLT_MAX;
1058                 
1059                 knife_project_v3(kcd, co, sco);
1060                 
1061                 lst = knife_get_face_kedges(kcd, f);
1062                 for (ref=lst->first; ref; ref=ref->next) {
1063                         KnifeEdge *kfe = ref->ref;
1064                         int i;
1065                         
1066                         for (i=0; i<2; i++) {
1067                                 KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
1068                                 
1069                                 knife_project_v3(kcd, kfv->co, kfv->sco);
1070                                 
1071                                 dis = len_v2v2(kfv->sco, sco);
1072                                 if (dis < curdis && dis < maxdist) {
1073                                         if(kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
1074                                                 float vec[3];
1075                                                 
1076                                                 copy_v3_v3(vec, kfv->co);
1077                                                 mul_m4_v3(kcd->vc.obedit->obmat, vec);
1078                         
1079                                                 if(view3d_test_clipping(kcd->vc.rv3d, vec, 1)==0) {
1080                                                         curv = kfv;
1081                                                         curdis = dis;
1082                                                 }
1083                                         } else {
1084                                                 curv = kfv;
1085                                                 curdis = dis;                           
1086                                         }
1087                                 }
1088                         }
1089                 }
1090                 
1091                 if (fptr)
1092                         *fptr = f;
1093                 
1094                 if (curv && p) {
1095                         copy_v3_v3(p, curv->co);
1096                 }
1097                 
1098                 return curv;
1099         }
1100                 
1101         if (fptr)
1102                 *fptr = NULL;
1103         
1104         return NULL;
1105 }
1106
1107 /*update active knife edge/vert pointers*/
1108 static int knife_update_active(knifetool_opdata *kcd)
1109 {
1110         kcd->curvert = NULL; kcd->curedge = NULL; kcd->curbmface = NULL;
1111         
1112         kcd->curvert = knife_find_closest_vert(kcd, kcd->vertco, &kcd->curbmface);
1113         if (!kcd->curvert)
1114                 kcd->curedge = knife_find_closest_edge(kcd, kcd->vertco, &kcd->curbmface);
1115         
1116         if (kcd->mode == MODE_DRAGGING) {
1117                 knife_find_line_hits(kcd);
1118         }
1119         return 1;
1120 }
1121
1122 #define VERT_ON_EDGE    8
1123 #define VERT_ORIG               16
1124 #define FACE_FLIP               32
1125
1126 /*use edgenet to fill faces.  this is a bit annoying and convoluted.*/
1127 void knifenet_fill_faces(knifetool_opdata *kcd)
1128 {
1129         BLI_mempool_iter iter;
1130         BMOperator bmop;
1131         BMesh *bm = kcd->em->bm;
1132         BMOIter siter;
1133         BMIter bmiter;
1134         BMFace *f;
1135         BMEdge *e;
1136         KnifeVert *kfv;
1137         KnifeEdge *kfe;
1138         float (*vertcos)[3] = NULL;
1139         void **blocks = NULL;
1140         BLI_array_declare(blocks);
1141         BLI_array_declare(vertcos);
1142         float *w = NULL;
1143         BLI_array_declare(w);
1144         
1145         BMO_push(bm, NULL);
1146         
1147         BM_ITER(f, &bmiter, bm, BM_FACES_OF_MESH, NULL) {
1148                 BMINDEX_SET(f, 0);
1149         }
1150
1151         /*assign a bit flag to each face.  adjacent
1152           faces cannot share the same bit flag, nor can
1153           diagonally adjacent faces*/
1154         BM_ITER(f, &bmiter, bm, BM_FACES_OF_MESH, NULL) {
1155                 BMIter bmiter2;
1156                 BMLoop *l;
1157                 int group = 0, ok=0;
1158                 
1159                 while (!ok) {
1160                         ok = 1;
1161                         BM_ITER(l, &bmiter2, bm, BM_LOOPS_OF_FACE, f) {
1162                                 BMLoop *l2 = l->radial_next;
1163                                 while (l2 != l) {
1164                                         BMLoop *l3;
1165                                         BMIter bmiter3;
1166                                         
1167                                         if (l2->f == l->f) {
1168                                                 l2 = l2->radial_next;
1169                                                 continue;
1170                                         }
1171                                         
1172                                         if (BMINDEX_GET(l2->f) == (1<<group) && group <= MAXGROUP) {
1173                                                 group++;
1174                                                 ok = 0;
1175                                         } else if (BMINDEX_GET(l2->f) == (1<<group)) {
1176                                                 printf("yeek! ran out of groups! 1\n");
1177                                         }
1178
1179                                         BM_ITER(l3, &bmiter3, bm, BM_LOOPS_OF_FACE, l2->f) {
1180                                                 BMLoop *l4 = l3->radial_next;
1181                                                 
1182                                                 do {
1183                                                         if (l4->f == l->f) {
1184                                                                 l4 = l4->radial_next;
1185                                                                 continue;
1186                                                         }
1187                                                         
1188                                                         if (BMINDEX_GET(l4->f) == (1<<group) && group <= MAXGROUP) {
1189                                                                 group++;
1190                                                                 ok = 0;
1191                                                         } else if (BMINDEX_GET(l4->f) == (1<<group)) {
1192                                                                 printf("yeek! ran out of groups! 2`\n");
1193                                                         }
1194                                                         
1195                                                         l4 = l4->radial_next;
1196                                                 } while (l4 != l3);
1197                                         }
1198                                         
1199                                         l2 = l2->radial_next;
1200                                 }
1201                         }
1202                 }
1203                 
1204                 BMINDEX_SET(f, (1<<group));
1205         }
1206
1207         /*turn knife verts into real verts, as necassary*/
1208         BLI_mempool_iternew(kcd->kverts, &iter);
1209         for (kfv=BLI_mempool_iterstep(&iter); kfv; kfv=BLI_mempool_iterstep(&iter)) {
1210                 if (!kfv->v) {
1211                         kfv->v = BM_Make_Vert(bm, kfv->co, NULL);
1212                         kfv->flag = 1;
1213                 } else {
1214                         kfv->flag = 0;
1215                         BMO_SetFlag(bm, kfv->v, VERT_ORIG);
1216                 }
1217
1218                 BMO_SetFlag(bm, kfv->v, MARK);
1219         }
1220
1221         BMO_InitOpf(bm, &bmop, "edgenet_fill use_restrict=%i", 1);
1222
1223         /*turn knife edges into real edges, and assigns bit masks representing
1224           the faces they are adjacent too*/
1225         BLI_mempool_iternew(kcd->kedges, &iter);
1226         for (kfe=BLI_mempool_iterstep(&iter); kfe; kfe=BLI_mempool_iterstep(&iter)) {
1227                 int group = 0;
1228
1229                 if (!kfe->v1 || !kfe->v2)
1230                         continue;
1231                 
1232                 if (kfe->e) {
1233                         BM_ITER(f, &bmiter, bm, BM_FACES_OF_EDGE, kfe->e) {
1234                                 group |= BMINDEX_GET(f);
1235
1236                                 if (kfe->v1->v != kfe->e->v1 || kfe->v2->v != kfe->e->v2) {
1237                                         BMO_SetFlag(bm, f, DEL);
1238                                 }
1239                         }
1240
1241                         kfe->oe = kfe->e;
1242
1243                         if (kfe->v1->v != kfe->e->v1 || kfe->v2->v != kfe->e->v2) {
1244                                 BMO_SetFlag(bm, kfe->e, DEL);
1245                                 BMO_ClearFlag(bm, kfe->e, MARK);
1246                                 
1247                                 if (kfe->v1->v != kfe->e->v1)
1248                                         BMO_SetFlag(bm, kfe->v1->v, VERT_ON_EDGE);
1249                                 if (kfe->v2->v != kfe->e->v2)
1250                                         BMO_SetFlag(bm, kfe->v2->v, VERT_ON_EDGE);
1251
1252                                 kfe->e = NULL;
1253                         }
1254                 }
1255                 
1256                 if (!kfe->e) {
1257                         kfe->e = BM_Make_Edge(bm, kfe->v1->v, kfe->v2->v, NULL, 0);
1258                 }
1259                 
1260                 BMO_SetFlag(bm, kfe->e, MARK);
1261                 
1262                 if (kfe->basef) {
1263                         BMEdge *e;
1264                         BM_ITER(e, &bmiter, bm, BM_EDGES_OF_FACE, kfe->basef) {
1265                                 BMO_SetFlag(bm, e, MARK);                       
1266                         }
1267
1268                         BMO_SetFlag(bm, kfe->basef, DEL);
1269                         group |= BMINDEX_GET(kfe->basef);
1270                 } 
1271                 
1272                 if (!group) {
1273                         Ref *ref;
1274                         
1275                         for (ref=kfe->faces.first; ref; ref=ref->next) {
1276                                 kfe->basef = ref->ref;
1277                                 group |= BMINDEX_GET(ref->ref); 
1278                         }
1279                 }
1280
1281                 if (group)
1282                         BMO_Insert_MapInt(bm, &bmop, "restrict", kfe->e, group);
1283                 else
1284                         printf("yeek!\n");
1285         }
1286         
1287         /*not sure why this is needed, sanity check to make sure del'd edges are not
1288           marked as well*/
1289         BM_ITER(e, &bmiter, bm, BM_EDGES_OF_MESH, NULL) {
1290                 if (BMO_TestFlag(bm, e, DEL))
1291                         BMO_ClearFlag(bm, e, MARK);
1292         }
1293
1294         BM_ITER(f, &bmiter, bm, BM_FACES_OF_MESH, NULL) {
1295                 BMIter eiter;
1296                 
1297                 if (!BMO_TestFlag(bm, f, DEL))
1298                         continue;
1299                 
1300                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_FACE, f) {
1301                         BMIter liter;
1302                         BMLoop *l;
1303                         
1304                         BMO_SetFlag(bm, e, MARK);
1305                         
1306                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
1307                                 BMINDEX_SET(e, BMINDEX_GET(e)|BMINDEX_GET(l->f));
1308                         }
1309                 }
1310         }
1311
1312         BMO_Flag_To_Slot(bm, &bmop, "edges", MARK, BM_EDGE);
1313         BMO_Flag_To_Slot(bm, &bmop, "excludefaces", DEL, BM_FACE);
1314         
1315         /*execute the edgenet fill operator.  it will restrict filled faces to edges
1316           belonging to the same group (note edges can belong to multiple groups, using
1317           bitmasks)*/
1318         BMO_Exec_Op(bm, &bmop);
1319         BMO_Flag_Buffer(bm, &bmop, "faceout", MARK, BM_FACE);
1320         
1321         BM_Compute_Normals(bm);
1322         
1323         //void interp_weights_poly_v3(float *w,float v[][3], int n, float *co)
1324         
1325         /* interpolate customdata */
1326         
1327         /*first deal with interpolating vertices that lie on original edges*/   
1328         BLI_mempool_iternew(kcd->kedges, &iter);
1329         for (kfe=BLI_mempool_iterstep(&iter); kfe; kfe=BLI_mempool_iterstep(&iter)) {
1330                 BMLoop *l1, *l2;
1331                 float fac, w[2];
1332                 void *blocks[2];
1333                 
1334                 if (!kfe->oe)
1335                         continue;
1336                 
1337                 BM_ITER(l1, &bmiter, bm, BM_LOOPS_OF_EDGE, kfe->oe) {
1338                         BMLoop *l2 = NULL;
1339                         BMIter liter;
1340                         int i, j;
1341                         
1342                         BM_ITER(l2, &liter, bm, BM_LOOPS_OF_EDGE, kfe->e) {
1343                                 if (!BM_Vert_In_Edge(kfe->e, l2->next->v)) {
1344                                         l2 = l2->prev;
1345                                 }
1346                                 
1347                                 if (!BMO_InMap(bm, &bmop, "faceout_groupmap", l2->f))
1348                                         continue;
1349                                 
1350                                 if (BMINDEX_GET(l1->f) == BMO_Get_MapInt(bm, &bmop, "faceout_groupmap", l2->f))
1351                                         break;  
1352                         }
1353                         
1354                         if (!l2)
1355                                 continue;
1356                         
1357                         if (dot_v3v3(l1->f->no, l2->f->no) < 0.0f) {
1358                                 BMO_SetFlag(bm, l2->f, FACE_FLIP);
1359                         }
1360                         
1361                         for (i=0; i<2; i++) {
1362                                 if (i)
1363                                         l2 = l2->next;
1364                                 
1365                                 fac = len_v3v3(kfe->oe->v1->co, l2->v->co) / (len_v3v3(kfe->oe->v1->co, kfe->oe->v2->co)+FLT_EPSILON);
1366                                 
1367                                 if (kfe->oe->v1 == l1->v) {
1368                                         w[0] = 1.0-fac;
1369                                         w[1] = fac;
1370                                 } else {
1371                                         w[0] = fac;
1372                                         w[1] = 1.0-fac;
1373                                 }
1374                                 
1375                                 if (l1->e == kfe->oe) {
1376                                         blocks[0] = l1->head.data;
1377                                         blocks[1] = l1->next->head.data;
1378                                 } else {
1379                                         blocks[0] = l1->prev->head.data;
1380                                         blocks[1] = l1->head.data;
1381                                 }
1382                                 
1383                                 BM_Copy_Attributes(bm, bm, l1->f, l2->f);
1384                                 CustomData_bmesh_interp(&bm->ldata, blocks, w, NULL, 2, l2->head.data);
1385                         }
1386                 }
1387         }
1388         
1389         /*ensure normals are correct*/
1390         BM_ITER(f, &bmiter, bm, BM_FACES_OF_MESH, NULL) {
1391                 if (BMO_TestFlag(bm, f, FACE_FLIP)) {
1392                         BM_flip_normal(bm, f);
1393                 }
1394         }
1395
1396         /*now deal with interior vertex interpolation
1397           still kindof buggy*/
1398         BMO_ITER(f, &siter, bm, &bmop, "faceout_groupmap", BM_FACE) {
1399                 BMLoop *l1, *l2;
1400                 BMFace *f2; 
1401                 BMIter liter1, liter2;
1402                 int group = *(int*)BMO_IterMapVal(&siter);
1403                 
1404                 BM_ITER(l1, &liter1, bm, BM_LOOPS_OF_FACE, f) {
1405                         float co[3], hit[3];
1406                         float dir[3];
1407                         int i;
1408                         
1409                         if (BMO_TestFlag(bm, l1->v, VERT_ORIG) || BMO_TestFlag(bm, l1->v, VERT_ON_EDGE))
1410                                 continue;
1411                         
1412                         copy_v3_v3(co, l1->v->co);
1413                         copy_v3_v3(dir, l1->v->no);
1414                         mul_v3_fl(dir, 0.001f);
1415                         
1416                         add_v3_v3(co, dir);
1417                         copy_v3_v3(dir, l1->v->no);
1418                         mul_v3_fl(dir, -1.0);
1419                         
1420                         f2 = BMBVH_RayCast(kcd->bmbvh, co, dir, hit);
1421                         if (!f2) {
1422                                 printf("eek!!\n");
1423                                 continue;
1424                         }
1425                         
1426                         BLI_array_empty(vertcos);
1427                         BLI_array_empty(blocks);
1428                         BLI_array_empty(w);
1429                         BM_ITER(l2, &liter2, bm, BM_LOOPS_OF_FACE, f2) {
1430                                 BLI_array_growone(vertcos);
1431                                 BLI_array_append(blocks, l2->head.data);
1432
1433                                 copy_v3_v3(vertcos[BLI_array_count(vertcos)-1], l2->v->co);
1434                                 BLI_array_append(w, 0.0f);
1435                         }
1436                         
1437                         BM_Copy_Attributes(bm, bm, f2, f);
1438
1439                         interp_weights_poly_v3(w, vertcos, f2->len, l1->v->co);
1440                         CustomData_bmesh_interp(&bm->ldata, blocks, w, NULL, BLI_array_count(blocks), l1->head.data);
1441                 }
1442         }
1443
1444         BMO_Finish_Op(bm, &bmop);
1445
1446         /*delete left over faces*/
1447         BMO_CallOpf(bm, "del geom=%ff context=%i", DEL, DEL_ONLYFACES);
1448         BMO_CallOpf(bm, "del geom=%fe context=%i", DEL, DEL_EDGES);
1449
1450         BMO_pop(bm);
1451 }
1452
1453 /*called on tool confirmation*/
1454 static void knifetool_finish(bContext *C, wmOperator *op)
1455 {
1456         knifetool_opdata *kcd= op->customdata;
1457         
1458         knifenet_fill_faces(kcd);
1459 }
1460
1461 /*copied from paint_image.c*/
1462 static int project_knife_view_clip(View3D *v3d, RegionView3D *rv3d, float *clipsta, float *clipend)
1463 {
1464         int orth= get_view3d_cliprange(v3d, rv3d, clipsta, clipend);
1465
1466         if (orth) { /* only needed for ortho */
1467                 float fac = 2.0f / ((*clipend) - (*clipsta));
1468                 *clipsta *= fac;
1469                 *clipend *= fac;
1470         }
1471
1472         return orth;
1473 }
1474
1475 void knife_recalc_projmat(knifetool_opdata *kcd)
1476 {
1477         ARegion *ar = CTX_wm_region(kcd->C);
1478         
1479         if (!ar)
1480                 return;
1481         
1482         invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
1483         view3d_get_object_project_mat(ar->regiondata, kcd->ob, kcd->projmat);
1484         //mul_m4_m4m4(kcd->projmat, kcd->vc.rv3d->viewmat, kcd->vc.rv3d->winmat);
1485         
1486         kcd->is_ortho = project_knife_view_clip(kcd->vc.v3d, kcd->vc.rv3d, 
1487                                                 &kcd->clipsta, &kcd->clipend);
1488 }
1489
1490 /* called when modal loop selection is done... */
1491 static void knifetool_exit (bContext *C, wmOperator *op)
1492 {
1493         knifetool_opdata *kcd= op->customdata;
1494         
1495         if (!kcd)
1496                 return;
1497                 
1498         /* deactivate the extra drawing stuff in 3D-View */
1499         ED_region_draw_cb_exit(kcd->ar->type, kcd->draw_handle);
1500         
1501         /* free the custom data */
1502         BLI_mempool_destroy(kcd->refs);
1503         BLI_mempool_destroy(kcd->kverts);
1504         BLI_mempool_destroy(kcd->kedges);
1505
1506         BLI_ghash_free(kcd->origedgemap, NULL, NULL);
1507         BLI_ghash_free(kcd->origvertmap, NULL, NULL);
1508         BLI_ghash_free(kcd->kedgefacemap, NULL, NULL);
1509         
1510         BMBVH_FreeBVH(kcd->bmbvh);
1511         BLI_memarena_free(kcd->arena);
1512         
1513         /* tag for redraw */
1514         ED_region_tag_redraw(kcd->ar);
1515
1516         /* destroy kcd itself */
1517         MEM_freeN(kcd);
1518         op->customdata= NULL;                   
1519 }
1520
1521 /* called when modal loop selection gets set up... */
1522 static int knifetool_init (bContext *C, wmOperator *op, int do_cut)
1523 {
1524         knifetool_opdata *kcd;
1525         
1526         /* alloc new customdata */
1527         kcd= op->customdata= MEM_callocN(sizeof(knifetool_opdata), "knifetool Modal Op Data");
1528         
1529         /* assign the drawing handle for drawing preview line... */
1530         kcd->ar= CTX_wm_region(C);
1531         kcd->C = C;
1532         kcd->draw_handle= ED_region_draw_cb_activate(kcd->ar->type, knifetool_draw, kcd, REGION_DRAW_POST_VIEW);
1533         em_setup_viewcontext(C, &kcd->vc);
1534
1535         kcd->ob = CTX_data_edit_object(C);
1536         kcd->em= ((Mesh *)kcd->ob->data)->edit_btmesh;
1537         kcd->bmbvh = BMBVH_NewBVH(kcd->em);
1538         kcd->arena = BLI_memarena_new(1<<15, "knife");
1539         kcd->vthresh = KMAXDIST-1;
1540         kcd->ethresh = KMAXDIST;
1541         
1542         knife_recalc_projmat(kcd);
1543         
1544         ED_region_tag_redraw(kcd->ar);
1545         
1546         kcd->refs = BLI_mempool_create(sizeof(Ref), 1, 2048, 0, 0);
1547         kcd->kverts = BLI_mempool_create(sizeof(KnifeVert), 1, 512, 0, 1);
1548         kcd->kedges = BLI_mempool_create(sizeof(KnifeEdge), 1, 512, 0, 1);
1549         
1550         kcd->origedgemap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origedgemap");
1551         kcd->origvertmap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origvertmap");
1552         kcd->kedgefacemap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origvertmap");
1553
1554         return 1;
1555 }
1556
1557 static int knifetool_cancel (bContext *C, wmOperator *op)
1558 {
1559         /* this is just a wrapper around exit() */
1560         knifetool_exit(C, op);
1561         return OPERATOR_CANCELLED;
1562 }
1563
1564 static int knifetool_invoke (bContext *C, wmOperator *op, wmEvent *evt)
1565 {
1566         knifetool_opdata *kcd;
1567
1568         view3d_operator_needs_opengl(C);
1569
1570         if (!knifetool_init(C, op, 0))
1571                 return OPERATOR_CANCELLED;
1572         
1573         /* add a modal handler for this operator - handles loop selection */
1574         WM_event_add_modal_handler(C, op);
1575
1576         kcd = op->customdata;
1577         kcd->vc.mval[0] = evt->mval[0];
1578         kcd->vc.mval[1] = evt->mval[1];
1579         
1580         return OPERATOR_RUNNING_MODAL;
1581 }
1582
1583 static int knifetool_modal (bContext *C, wmOperator *op, wmEvent *event)
1584 {
1585         Object *obedit;
1586         knifetool_opdata *kcd= op->customdata;
1587         
1588         if (!C) {
1589                 return OPERATOR_FINISHED;
1590         }
1591         
1592         obedit = CTX_data_edit_object(C);
1593         if (!obedit || obedit->type != OB_MESH || ((Mesh*)obedit->data)->edit_btmesh != kcd->em)
1594                 return OPERATOR_FINISHED;
1595
1596         view3d_operator_needs_opengl(C);
1597
1598         switch (event->type) {
1599                 case ESCKEY:
1600                 case RETKEY: /* confirm */ // XXX hardcoded
1601                         if (event->val == KM_RELEASE) {
1602                                 if (kcd->mode == MODE_DRAGGING && event->type == ESCKEY) {
1603                                         kcd->mode = MODE_IDLE;
1604                                         ED_region_tag_redraw(kcd->ar);                                  
1605                                 } else {                                
1606                                         /* finish */
1607                                         ED_region_tag_redraw(kcd->ar);
1608                                         
1609                                         knifetool_finish(C, op);
1610                                         knifetool_exit(C, op);
1611                                         
1612                                         return OPERATOR_FINISHED;
1613                                 }
1614                         }
1615                         
1616                         ED_region_tag_redraw(kcd->ar);
1617                         return OPERATOR_RUNNING_MODAL;
1618                 case LEFTMOUSE:
1619                         knife_recalc_projmat(kcd);
1620                         if (event->val != KM_RELEASE)
1621                                 break;
1622                         
1623                         if (kcd->mode == MODE_DRAGGING) {
1624                                 knife_add_cut(kcd);
1625                                 if (!event->ctrl) {
1626                                         knife_finish_cut(kcd);
1627                                         kcd->mode = MODE_IDLE;
1628                                 }
1629                         } else {
1630                                 knife_start_cut(kcd);
1631                                 kcd->mode = MODE_DRAGGING;
1632                         }
1633
1634                         ED_region_tag_redraw(kcd->ar);
1635                         return OPERATOR_RUNNING_MODAL;
1636                 case LEFTCTRLKEY:
1637                 case RIGHTCTRLKEY:
1638                         knife_recalc_projmat(kcd);
1639                         
1640                         if (event->val == KM_RELEASE) {
1641                                 knife_finish_cut(kcd);
1642                                 kcd->mode = MODE_IDLE;
1643                         }
1644                         
1645                         ED_region_tag_redraw(kcd->ar);
1646                         return OPERATOR_RUNNING_MODAL;
1647                 case MOUSEMOVE: { /* mouse moved somewhere to select another loop */
1648                         knife_recalc_projmat(kcd);
1649                         kcd->vc.mval[0] = event->mval[0];
1650                         kcd->vc.mval[1] = event->mval[1];
1651                         
1652                         if (knife_update_active(kcd))                                   
1653                                 ED_region_tag_redraw(kcd->ar);
1654                         
1655                         break;
1656                 /*block undo*/
1657                 case ZKEY:
1658                         if (event->ctrl)
1659                                 return OPERATOR_RUNNING_MODAL;
1660                 }       
1661                 case KKEY:
1662                         if (!event->ctrl && !event->alt && !event->shift)
1663                                 return OPERATOR_RUNNING_MODAL;
1664         }
1665         
1666         /* keep going until the user confirms */
1667         return OPERATOR_PASS_THROUGH;
1668 }
1669
1670 void MESH_OT_knifetool (wmOperatorType *ot)
1671 {
1672         /* description */
1673         ot->name= "Knife Topology Tool";
1674         ot->idname= "MESH_OT_knifetool";
1675         ot->description= "Cut new topology";
1676         
1677         /* callbacks */
1678         ot->invoke= knifetool_invoke;
1679         ot->modal= knifetool_modal;
1680         ot->cancel= knifetool_cancel;
1681         ot->poll= ED_operator_editmesh_view3d;
1682         
1683         /* flags */
1684         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO|OPTYPE_BLOCKING;
1685 }