Added a new slot type, that maps geometric elements to
[blender.git] / source / blender / editors / mesh / editmesh_loop.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) 2004 by Blender Foundation.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): none yet.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29
30 /*
31
32 editmesh_loop: tools with own drawing subloops, select, knife, subdiv
33
34 */
35
36 #include <stdlib.h>
37 #include <string.h>
38 #include <math.h>
39
40 #include "MEM_guardedalloc.h"
41
42
43 #include "DNA_mesh_types.h"
44 #include "DNA_meshdata_types.h"
45 #include "DNA_object_types.h"
46 #include "DNA_scene_types.h"
47 #include "DNA_screen_types.h"
48 #include "DNA_view3d_types.h"
49
50 #include "BLI_blenlib.h"
51 #include "BLI_arithb.h"
52 #include "BLI_editVert.h"
53 #include "BLI_ghash.h"
54
55 #include "BKE_context.h"
56 #include "BKE_depsgraph.h"
57 #include "BKE_displist.h"
58 #include "BKE_global.h"
59 #include "BKE_library.h"
60 #include "BKE_mesh.h"
61 #include "BKE_object.h"
62 #include "BKE_utildefines.h"
63
64 #include "PIL_time.h"
65
66 #include "BIF_gl.h"
67
68 #include "RNA_access.h"
69 #include "RNA_define.h"
70
71 #include "WM_api.h"
72 #include "WM_types.h"
73
74 #include "ED_mesh.h"
75 #include "ED_screen.h"
76 #include "ED_view3d.h"
77
78 #include "mesh_intern.h"
79 #include "bmesh.h"
80
81 /* **** XXX ******** */
82 static void BIF_undo_push() {}
83 static void BIF_undo() {}
84 static void error() {}
85 static int qtest() {return 0;}
86 /* **** XXX ******** */
87
88
89 /* New LoopCut */
90 static void edgering_sel(EditMesh *em, EditEdge *startedge, int select, int previewlines)
91 {
92         EditEdge *eed;
93         EditFace *efa;
94         EditVert *v[2][2];
95         float co[2][3];
96         int looking= 1,i;
97         
98         /* in eed->f1 we put the valence (amount of faces in edge) */
99         /* in eed->f2 we put tagged flag as correct loop */
100         /* in efa->f1 we put tagged flag as correct to select */
101
102         for(eed= em->edges.first; eed; eed= eed->next) {
103                 eed->f1= 0;
104                 eed->f2= 0;
105         }
106         for(efa= em->faces.first; efa; efa= efa->next) {
107                 efa->f1= 0;
108                 if(efa->h==0) {
109                         efa->e1->f1++;
110                         efa->e2->f1++;
111                         efa->e3->f1++;
112                         if(efa->e4) efa->e4->f1++;
113                 }
114         }
115         
116         // tag startedge OK
117         startedge->f2= 1;
118         
119         while(looking) {
120                 looking= 0;
121                 
122                 for(efa= em->faces.first; efa; efa= efa->next) {
123                         if(efa->e4 && efa->f1==0 && efa->h == 0) {      // not done quad
124                                 if(efa->e1->f1<=2 && efa->e2->f1<=2 && efa->e3->f1<=2 && efa->e4->f1<=2) { // valence ok
125
126                                         // if edge tagged, select opposing edge and mark face ok
127                                         if(efa->e1->f2) {
128                                                 efa->e3->f2= 1;
129                                                 efa->f1= 1;
130                                                 looking= 1;
131                                         }
132                                         else if(efa->e2->f2) {
133                                                 efa->e4->f2= 1;
134                                                 efa->f1= 1;
135                                                 looking= 1;
136                                         }
137                                         if(efa->e3->f2) {
138                                                 efa->e1->f2= 1;
139                                                 efa->f1= 1;
140                                                 looking= 1;
141                                         }
142                                         if(efa->e4->f2) {
143                                                 efa->e2->f2= 1;
144                                                 efa->f1= 1;
145                                                 looking= 1;
146                                         }
147                                 }
148                         }
149                 }
150         }
151         
152         if(previewlines > 0 && select == 0){
153 // XXX                  persp(PERSP_VIEW);
154 // XXX                  glPushMatrix();
155 // XXX                  mymultmatrix(obedit->obmat);
156
157                         for(efa= em->faces.first; efa; efa= efa->next) {
158                                 if(efa->v4 == NULL) {  continue; }
159                                 if(efa->h == 0){
160                                         if(efa->e1->f2 == 1){
161                                                 if(efa->e1->h == 1 || efa->e3->h == 1 )
162                                                         continue;
163                                                 
164                                                 v[0][0] = efa->v1;
165                                                 v[0][1] = efa->v2;
166                                                 v[1][0] = efa->v4;
167                                                 v[1][1] = efa->v3;
168                                         } else if(efa->e2->f2 == 1){
169                                                 if(efa->e2->h == 1 || efa->e4->h == 1)
170                                                         continue;
171                                                 v[0][0] = efa->v2;
172                                                 v[0][1] = efa->v3;
173                                                 v[1][0] = efa->v1;
174                                                 v[1][1] = efa->v4;                                      
175                                         } else { continue; }
176                                                                                   
177                                         for(i=1;i<=previewlines;i++){
178                                                 co[0][0] = (v[0][1]->co[0] - v[0][0]->co[0])*(i/((float)previewlines+1))+v[0][0]->co[0];
179                                                 co[0][1] = (v[0][1]->co[1] - v[0][0]->co[1])*(i/((float)previewlines+1))+v[0][0]->co[1];
180                                                 co[0][2] = (v[0][1]->co[2] - v[0][0]->co[2])*(i/((float)previewlines+1))+v[0][0]->co[2];
181
182                                                 co[1][0] = (v[1][1]->co[0] - v[1][0]->co[0])*(i/((float)previewlines+1))+v[1][0]->co[0];
183                                                 co[1][1] = (v[1][1]->co[1] - v[1][0]->co[1])*(i/((float)previewlines+1))+v[1][0]->co[1];
184                                                 co[1][2] = (v[1][1]->co[2] - v[1][0]->co[2])*(i/((float)previewlines+1))+v[1][0]->co[2];                                        
185                                                 glColor3ub(255, 0, 255);
186                                                 glBegin(GL_LINES);      
187                                                 glVertex3f(co[0][0],co[0][1],co[0][2]);
188                                                 glVertex3f(co[1][0],co[1][1],co[1][2]);
189                                                 glEnd();
190                                         }
191                                 }
192                         }
193                         glPopMatrix();   
194         } else {        
195         
196         /* (de)select the edges */
197                 for(eed= em->edges.first; eed; eed= eed->next) {
198                 if(eed->f2) EM_select_edge(eed, select);
199                 }
200         }
201 }
202 void CutEdgeloop(Object *obedit, EditMesh *em, int numcuts)
203 {
204         ViewContext vc; // XXX
205         EditEdge *nearest=NULL, *eed;
206         float fac;
207         int keys = 0, holdnum=0, selectmode, dist;
208         short mvalo[2] = {0,0}, mval[2] = {0, 0};
209         short event=0, val, choosing=1, cancel=0, cuthalf = 0, smooth=0;
210         short hasHidden = 0;
211         char msg[128];
212         
213         selectmode = em->selectmode;
214                 
215         if(em->selectmode & SCE_SELECT_FACE){
216                 em->selectmode =  SCE_SELECT_EDGE;
217                 EM_selectmode_set(em);    
218         }
219         
220         
221         BIF_undo_push("Loopcut Begin");
222         while(choosing && !cancel){
223 // XXX          getmouseco_areawin(mval);
224                 if (mval[0] != mvalo[0] || mval[1] != mvalo[1]) {
225                         mvalo[0] = mval[0];
226                         mvalo[1] = mval[1];
227                         dist= 50;
228                         nearest = findnearestedge(&vc, &dist);  // returns actual distance in dist
229 //                      scrarea_do_windraw(curarea);    // after findnearestedge, backbuf!
230                         
231                         sprintf(msg,"Number of Cuts: %d",numcuts);
232                         if(smooth){
233                                 sprintf(msg,"%s (S)mooth: on",msg);
234                         } else {
235                                 sprintf(msg,"%s (S)mooth: off",msg);
236                         }
237                         
238 //                      headerprint(msg);
239                         /* Need to figure preview */
240                         if(nearest){
241                                 edgering_sel(em, nearest, 0, numcuts);
242                          }   
243 // XXX                  screen_swapbuffers();
244                         
245                 /* backbuffer refresh for non-apples (no aux) */
246 #ifndef __APPLE__
247 // XXX                  if(G.vd->drawtype>OB_WIRE && (G.vd->flag & V3D_ZBUF_SELECT)) {
248 //                              backdrawview3d(0);
249 //                      }
250 #endif
251                 }
252                 else PIL_sleep_ms(10);  // idle         
253                 
254                 
255                 while(qtest()) 
256                 {
257                         val=0;
258 // XXX                  event= extern_qread(&val);
259                         if(val && (event ==  MOUSEX || event == MOUSEY)){ ; } 
260                         else if(val && ((event==LEFTMOUSE || event==RETKEY) || (event == MIDDLEMOUSE || event==PADENTER)))
261                         {
262                                 if(event == MIDDLEMOUSE){
263                                         cuthalf = 1;
264                                 }
265                                 if (nearest==NULL)
266                                         cancel = 1;
267                                 choosing=0;
268                                 mvalo[0] = -1;
269                         }
270                         else if(val && (event==ESCKEY || event==RIGHTMOUSE ))
271                         {
272                                 choosing=0;
273                                 cancel = 1;
274                                 mvalo[0] = -1;
275                         }
276                         else if(val && (event==PADPLUSKEY || event==WHEELUPMOUSE))
277                         {
278                                 numcuts++;
279                                 mvalo[0] = -1;
280                         }
281                         else if(val && (event==PADMINUS || event==WHEELDOWNMOUSE))
282                         {
283                                 if(numcuts > 1){
284                                         numcuts--;
285                                         mvalo[0] = -1;
286                                 } 
287                         }
288                         else if(val && event==SKEY)
289                         {
290                                 if(smooth){smooth=0;} 
291                                 else { smooth=1; }
292                                 mvalo[0] = -1;
293                         }
294                         
295                         else if(val){
296                                 holdnum = -1;
297                                 switch(event){
298                                         case PAD9:
299                                         case NINEKEY:
300                                                 holdnum = 9; break;
301                                         case PAD8:
302                                         case EIGHTKEY:
303                                                 holdnum = 8;break;
304                                         case PAD7:
305                                         case SEVENKEY:
306                                                 holdnum = 7;break;
307                                         case PAD6:
308                                         case SIXKEY:
309                                                 holdnum = 6;break;
310                                         case PAD5:
311                                         case FIVEKEY:
312                                                 holdnum = 5;break;
313                                         case PAD4:
314                                         case FOURKEY:
315                                                 holdnum = 4;break;
316                                         case PAD3:
317                                         case THREEKEY:
318                                                 holdnum = 3; break;
319                                         case PAD2:
320                                         case TWOKEY:
321                                                 holdnum = 2;break;
322                                         case PAD1:
323                                         case ONEKEY:
324                                                 holdnum = 1; break;
325                                         case PAD0:
326                                         case ZEROKEY:
327                                                 holdnum = 0;break;      
328                                         case BACKSPACEKEY:
329                                                 holdnum = -2;break;                     
330                                 }
331                                 if(holdnum >= 0 && numcuts*10 < 130){
332                                         if(keys == 0){  // first level numeric entry
333                                                         if(holdnum > 0){
334                                                                         numcuts = holdnum;
335                                                                         keys++;         
336                                                         }
337                                         } else if(keys > 0){//highrt level numeric entry
338                                                         numcuts *= 10;
339                                                         numcuts += holdnum;
340                                                         keys++;         
341                                         }
342                                 } else if (holdnum == -2){// backspace
343                                         if (keys > 1){
344                                                 numcuts /= 10;          
345                                                 keys--;
346                                         } else {
347                                                 numcuts=1;
348                                                 keys = 0;
349                                         }
350                                 }
351                                 mvalo[0] = -1;
352                                 break;
353                         }  // End Numeric Entry                                         
354                 }  //End while(qtest())
355         }   // End Choosing
356
357         if(cancel){
358                 return;   
359         }
360         /* clean selection */
361         for(eed=em->edges.first; eed; eed = eed->next){
362                 EM_select_edge(eed,0);
363         }
364         /* select edge ring */
365         edgering_sel(em, nearest, 1, 0);
366         
367         /* now cut the loops */
368         if(smooth){
369                 fac= 1.0f;
370 // XXX          if(fbutton(&fac, 0.0f, 5.0f, 10, 10, "Smooth:")==0) return;
371                 fac= 0.292f*fac;                        
372                 esubdivideflag(obedit, em, SELECT,fac,B_SMOOTH,numcuts,SUBDIV_SELECT_LOOPCUT);
373         } else {
374                 esubdivideflag(obedit, em, SELECT,0,0,numcuts,SUBDIV_SELECT_LOOPCUT);
375         }
376         /* if this was a single cut, enter edgeslide mode */
377         if(numcuts == 1 && hasHidden == 0){
378                 if(cuthalf)
379                         EdgeSlide(em, 1,0.0);
380                 else {
381                         if(EdgeSlide(em, 0,0.0) == -1){
382                                 BIF_undo();
383                         }
384                 }
385         }
386         
387         if(em->selectmode !=  selectmode){
388                 em->selectmode = selectmode;
389                 EM_selectmode_set(em);
390         }       
391         
392 //      DAG_object_flush_update(scene, obedit, OB_RECALC_DATA);
393         return;
394 }
395
396
397 /* *************** LOOP SELECT ************* */
398 #if 0
399 static short edgeFaces(EditMesh *em, EditEdge *e)
400 {
401         EditFace *search=NULL;
402         short count = 0;
403         
404         search = em->faces.first;
405         while(search){
406                 if((search->e1 == e || search->e2 == e) || (search->e3 == e || search->e4 == e)) 
407                         count++;
408                 search = search->next;
409         }
410         return count;   
411 }
412 #endif
413
414
415
416 /*   ***************** TRAIL ************************
417
418 Read a trail of mouse coords and return them as an array of CutCurve structs
419 len returns number of mouse coords read before commiting with RETKEY   
420 It is up to the caller to free the block when done with it,
421
422 XXX Is only used here, so local inside this file (ton)
423  */
424
425 #define TRAIL_POLYLINE 1 /* For future use, They don't do anything yet */
426 #define TRAIL_FREEHAND 2
427 #define TRAIL_MIXED    3 /* (1|2) */
428 #define TRAIL_AUTO     4 
429 #define TRAIL_MIDPOINTS 8
430
431 typedef struct CutCurve {
432         float  x; 
433         float  y;
434 } CutCurve;
435
436
437 /* ******************************************************************** */
438 /* Knife Subdivide Tool.  Subdivides edges intersected by a mouse trail
439         drawn by user.
440         
441         Currently mapped to KKey when in MeshEdit mode.
442         Usage:
443                 Hit Shift K, Select Centers or Exact
444                 Hold LMB down to draw path, hit RETKEY.
445                 ESC cancels as expected.
446    
447         Contributed by Robert Wenzlaff (Det. Thorn).
448
449     2.5 revamp:
450     - non modal (no menu before cutting)
451     - exit on mouse release
452     - polygon/segment drawing can become handled by WM cb later
453
454 */
455
456 #define KNIFE_EXACT             1
457 #define KNIFE_MIDPOINT  2
458 #define KNIFE_MULTICUT  3
459
460 static EnumPropertyItem knife_items[]= {
461         {KNIFE_EXACT, "EXACT", "Exact", ""},
462         {KNIFE_MIDPOINT, "MIDPOINTS", "Midpoints", ""},
463         {KNIFE_MULTICUT, "MULTICUT", "Multicut", ""},
464         {0, NULL, NULL}
465 };
466
467 /* seg_intersect() Determines if and where a mouse trail intersects an EditEdge */
468
469 static float seg_intersect(EditEdge *e, CutCurve *c, int len, char mode, struct GHash *gh)
470 {
471 #define MAXSLOPE 100000
472         float  x11, y11, x12=0, y12=0, x2max, x2min, y2max;
473         float  y2min, dist, lastdist=0, xdiff2, xdiff1;
474         float  m1, b1, m2, b2, x21, x22, y21, y22, xi;
475         float  yi, x1min, x1max, y1max, y1min, perc=0; 
476         float  *scr;
477         float  threshold = 0.0;
478         int  i;
479         
480         //threshold = 0.000001; /*tolerance for vertex intersection*/
481         // XXX  threshold = scene->toolsettings->select_thresh / 100;
482         
483         /* Get screen coords of verts */
484         scr = BLI_ghash_lookup(gh, e->v1);
485         x21=scr[0];
486         y21=scr[1];
487         
488         scr = BLI_ghash_lookup(gh, e->v2);
489         x22=scr[0];
490         y22=scr[1];
491         
492         xdiff2=(x22-x21);  
493         if (xdiff2) {
494                 m2=(y22-y21)/xdiff2;
495                 b2= ((x22*y21)-(x21*y22))/xdiff2;
496         }
497         else {
498                 m2=MAXSLOPE;  /* Verticle slope  */
499                 b2=x22;      
500         }
501         
502         /*check for *exact* vertex intersection first*/
503         if(mode!=KNIFE_MULTICUT){
504                 for (i=0; i<len; i++){
505                         if (i>0){
506                                 x11=x12;
507                                 y11=y12;
508                         }
509                         else {
510                                 x11=c[i].x;
511                                 y11=c[i].y;
512                         }
513                         x12=c[i].x;
514                         y12=c[i].y;
515                         
516                         /*test e->v1*/
517                         if((x11 == x21 && y11 == y21) || (x12 == x21 && y12 == y21)){
518                                 e->v1->f1 = 1;
519                                 perc = 0;
520                                 return(perc);
521                         }
522                         /*test e->v2*/
523                         else if((x11 == x22 && y11 == y22) || (x12 == x22 && y12 == y22)){
524                                 e->v2->f1 = 1;
525                                 perc = 0;
526                                 return(perc);
527                         }
528                 }
529         }
530         
531         /*now check for edge interesect (may produce vertex intersection as well)*/
532         for (i=0; i<len; i++){
533                 if (i>0){
534                         x11=x12;
535                         y11=y12;
536                 }
537                 else {
538                         x11=c[i].x;
539                         y11=c[i].y;
540                 }
541                 x12=c[i].x;
542                 y12=c[i].y;
543                 
544                 /* Perp. Distance from point to line */
545                 if (m2!=MAXSLOPE) dist=(y12-m2*x12-b2);/* /sqrt(m2*m2+1); Only looking for */
546                         /* change in sign.  Skip extra math */  
547                 else dist=x22-x12;      
548                 
549                 if (i==0) lastdist=dist;
550                 
551                 /* if dist changes sign, and intersect point in edge's Bound Box*/
552                 if ((lastdist*dist)<=0){
553                         xdiff1=(x12-x11); /* Equation of line between last 2 points */
554                         if (xdiff1){
555                                 m1=(y12-y11)/xdiff1;
556                                 b1= ((x12*y11)-(x11*y12))/xdiff1;
557                         }
558                         else{
559                                 m1=MAXSLOPE;
560                                 b1=x12;
561                         }
562                         x2max=MAX2(x21,x22)+0.001; /* prevent missed edges   */
563                         x2min=MIN2(x21,x22)-0.001; /* due to round off error */
564                         y2max=MAX2(y21,y22)+0.001;
565                         y2min=MIN2(y21,y22)-0.001;
566                         
567                         /* Found an intersect,  calc intersect point */
568                         if (m1==m2){ /* co-incident lines */
569                                 /* cut at 50% of overlap area*/
570                                 x1max=MAX2(x11, x12);
571                                 x1min=MIN2(x11, x12);
572                                 xi= (MIN2(x2max,x1max)+MAX2(x2min,x1min))/2.0;  
573                                 
574                                 y1max=MAX2(y11, y12);
575                                 y1min=MIN2(y11, y12);
576                                 yi= (MIN2(y2max,y1max)+MAX2(y2min,y1min))/2.0;
577                         }                       
578                         else if (m2==MAXSLOPE){ 
579                                 xi=x22;
580                                 yi=m1*x22+b1;
581                         }
582                         else if (m1==MAXSLOPE){ 
583                                 xi=x12;
584                                 yi=m2*x12+b2;
585                         }
586                         else {
587                                 xi=(b1-b2)/(m2-m1);
588                                 yi=(b1*m2-m1*b2)/(m2-m1);
589                         }
590                         
591                         /* Intersect inside bounding box of edge?*/
592                         if ((xi>=x2min)&&(xi<=x2max)&&(yi<=y2max)&&(yi>=y2min)){
593                                 /*test for vertex intersect that may be 'close enough'*/
594                                 if(mode!=KNIFE_MULTICUT){
595                                         if(xi <= (x21 + threshold) && xi >= (x21 - threshold)){
596                                                 if(yi <= (y21 + threshold) && yi >= (y21 - threshold)){
597                                                         e->v1->f1 = 1;
598                                                         perc = 0;
599                                                         break;
600                                                 }
601                                         }
602                                         if(xi <= (x22 + threshold) && xi >= (x22 - threshold)){
603                                                 if(yi <= (y22 + threshold) && yi >= (y22 - threshold)){
604                                                         e->v2->f1 = 1;
605                                                         perc = 0;
606                                                         break;
607                                                 }
608                                         }
609                                 }
610                                 if ((m2<=1.0)&&(m2>=-1.0)) perc = (xi-x21)/(x22-x21);   
611                                 else perc=(yi-y21)/(y22-y21); /*lower slope more accurate*/
612                                 //isect=32768.0*(perc+0.0000153); /* Percentage in 1/32768ths */
613                                 
614                                 break;
615                         }
616                 }       
617                 lastdist=dist;
618         }
619         return(perc);
620
621
622
623 static float bm_seg_intersect(BMEdge *e, CutCurve *c, int len, char mode,
624                               struct GHash *gh, int *isected)
625 {
626 #define MAXSLOPE 100000
627         float  x11, y11, x12=0, y12=0, x2max, x2min, y2max;
628         float  y2min, dist, lastdist=0, xdiff2, xdiff1;
629         float  m1, b1, m2, b2, x21, x22, y21, y22, xi;
630         float  yi, x1min, x1max, y1max, y1min, perc=0; 
631         float  *scr;
632         float  threshold = 0.0;
633         int  i;
634         
635         //threshold = 0.000001; /*tolerance for vertex intersection*/
636         // XXX  threshold = scene->toolsettings->select_thresh / 100;
637         
638         /* Get screen coords of verts */
639         scr = BLI_ghash_lookup(gh, e->v1);
640         x21=scr[0];
641         y21=scr[1];
642         
643         scr = BLI_ghash_lookup(gh, e->v2);
644         x22=scr[0];
645         y22=scr[1];
646         
647         xdiff2=(x22-x21);  
648         if (xdiff2) {
649                 m2=(y22-y21)/xdiff2;
650                 b2= ((x22*y21)-(x21*y22))/xdiff2;
651         }
652         else {
653                 m2=MAXSLOPE;  /* Verticle slope  */
654                 b2=x22;      
655         }
656
657         *isected = 0;
658
659         /*check for *exact* vertex intersection first*/
660         if(mode!=KNIFE_MULTICUT){
661                 for (i=0; i<len; i++){
662                         if (i>0){
663                                 x11=x12;
664                                 y11=y12;
665                         }
666                         else {
667                                 x11=c[i].x;
668                                 y11=c[i].y;
669                         }
670                         x12=c[i].x;
671                         y12=c[i].y;
672                         
673                         /*test e->v1*/
674                         if((x11 == x21 && y11 == y21) || (x12 == x21 && y12 == y21)){
675                                 perc = 0;
676                                 *isected = 1;
677                                 return(perc);
678                         }
679                         /*test e->v2*/
680                         else if((x11 == x22 && y11 == y22) || (x12 == x22 && y12 == y22)){
681                                 perc = 0;
682                                 *isected = 2;
683                                 return(perc);
684                         }
685                 }
686         }
687         
688         /*now check for edge interesect (may produce vertex intersection as well)*/
689         for (i=0; i<len; i++){
690                 if (i>0){
691                         x11=x12;
692                         y11=y12;
693                 }
694                 else {
695                         x11=c[i].x;
696                         y11=c[i].y;
697                 }
698                 x12=c[i].x;
699                 y12=c[i].y;
700                 
701                 /* Perp. Distance from point to line */
702                 if (m2!=MAXSLOPE) dist=(y12-m2*x12-b2);/* /sqrt(m2*m2+1); Only looking for */
703                         /* change in sign.  Skip extra math */  
704                 else dist=x22-x12;      
705                 
706                 if (i==0) lastdist=dist;
707                 
708                 /* if dist changes sign, and intersect point in edge's Bound Box*/
709                 if ((lastdist*dist)<=0){
710                         xdiff1=(x12-x11); /* Equation of line between last 2 points */
711                         if (xdiff1){
712                                 m1=(y12-y11)/xdiff1;
713                                 b1= ((x12*y11)-(x11*y12))/xdiff1;
714                         }
715                         else{
716                                 m1=MAXSLOPE;
717                                 b1=x12;
718                         }
719                         x2max=MAX2(x21,x22)+0.001; /* prevent missed edges   */
720                         x2min=MIN2(x21,x22)-0.001; /* due to round off error */
721                         y2max=MAX2(y21,y22)+0.001;
722                         y2min=MIN2(y21,y22)-0.001;
723                         
724                         /* Found an intersect,  calc intersect point */
725                         if (m1==m2){ /* co-incident lines */
726                                 /* cut at 50% of overlap area*/
727                                 x1max=MAX2(x11, x12);
728                                 x1min=MIN2(x11, x12);
729                                 xi= (MIN2(x2max,x1max)+MAX2(x2min,x1min))/2.0;  
730                                 
731                                 y1max=MAX2(y11, y12);
732                                 y1min=MIN2(y11, y12);
733                                 yi= (MIN2(y2max,y1max)+MAX2(y2min,y1min))/2.0;
734                         }                       
735                         else if (m2==MAXSLOPE){ 
736                                 xi=x22;
737                                 yi=m1*x22+b1;
738                         }
739                         else if (m1==MAXSLOPE){ 
740                                 xi=x12;
741                                 yi=m2*x12+b2;
742                         }
743                         else {
744                                 xi=(b1-b2)/(m2-m1);
745                                 yi=(b1*m2-m1*b2)/(m2-m1);
746                         }
747                         
748                         /* Intersect inside bounding box of edge?*/
749                         if ((xi>=x2min)&&(xi<=x2max)&&(yi<=y2max)&&(yi>=y2min)){
750                                 /*test for vertex intersect that may be 'close enough'*/
751                                 if(mode!=KNIFE_MULTICUT){
752                                         if(xi <= (x21 + threshold) && xi >= (x21 - threshold)){
753                                                 if(yi <= (y21 + threshold) && yi >= (y21 - threshold)){
754                                                         *isected = 1;
755                                                         perc = 0;
756                                                         break;
757                                                 }
758                                         }
759                                         if(xi <= (x22 + threshold) && xi >= (x22 - threshold)){
760                                                 if(yi <= (y22 + threshold) && yi >= (y22 - threshold)){
761                                                         *isected = 2;
762                                                         perc = 0;
763                                                         break;
764                                                 }
765                                         }
766                                 }
767                                 if ((m2<=1.0)&&(m2>=-1.0)) perc = (xi-x21)/(x22-x21);   
768                                 else perc=(yi-y21)/(y22-y21); /*lower slope more accurate*/
769                                 //isect=32768.0*(perc+0.0000153); /* Percentage in 1/32768ths */
770                                 
771                                 break;
772                         }
773                 }       
774                 lastdist=dist;
775         }
776         return(perc);
777
778
779 #define MAX_CUTS 256
780
781 static int knife_cut_exec(bContext *C, wmOperator *op)
782 {
783         Object *obedit= CTX_data_edit_object(C);
784         EditMesh *em= ((Mesh *)obedit->data)->edit_mesh, *em2;
785         BMesh *bm;
786         ARegion *ar= CTX_wm_region(C);
787         BMVert *bv;
788         BMIter iter;
789         BMEdge **edges = NULL, *be;
790         BMOperator bmop;
791         CutCurve curve[MAX_CUTS];
792         struct GHash *gh;
793         float isect=0.0;
794         float  *scr, co[4], *percents = NULL;
795         int len=0, isected, flag, i;
796         short numcuts=1, mode= RNA_int_get(op->ptr, "type");
797         
798         if (EM_nvertices_selected(em) < 2) {
799                 error("No edges are selected to operate on");
800                 return OPERATOR_CANCELLED;;
801         }
802
803         /* get the cut curve */
804         RNA_BEGIN(op->ptr, itemptr, "path") {
805                 
806                 RNA_float_get_array(&itemptr, "loc", (float *)&curve[len]);
807                 len++;
808                 if(len>= MAX_CUTS) break;
809         }
810         RNA_END;
811         
812         if(len<2) return OPERATOR_CANCELLED;
813         
814         bm = editmesh_to_bmesh(em);
815
816         /*the floating point coordinates of verts in screen space will be stored in a hash table according to the vertices pointer*/
817         gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
818         for(bv=BMIter_New(&iter, bm, BM_VERTS, NULL);bv;bv=BMIter_Step(&iter)){
819                 scr = MEM_mallocN(sizeof(float)*2, "Vertex Screen Coordinates");
820                 VECCOPY(co, bv->co);
821                 co[3]= 1.0;
822                 Mat4MulVec4fl(obedit->obmat, co);
823                 project_float(ar, co, scr);
824                 BLI_ghash_insert(gh, bv, scr);
825         }
826         
827         BMO_Init_Op(&bmop, BMOP_ESUBDIVIDE);
828         
829         i = 0;
830         /*store percentage of edge cut for KNIFE_EXACT here.*/
831         for (be=BMIter_New(&iter, bm, BM_EDGES, NULL); be; be=BMIter_Step(&iter)) {
832                 if( BM_Is_Selected(bm, be) ) {
833                         isect= bm_seg_intersect(be, curve, len, mode, gh, &isected);
834                         
835                         if (isect != 0.0f) {
836                                 if (mode != KNIFE_MULTICUT) {
837                                         BMO_Insert_MapFloat(bm, &bmop, 
838                                                BMOP_ESUBDIVIDE_PERCENT_EDGEMAP,
839                                                be, isect);
840
841                                 }
842                                 BMO_SetFlag(bm, be, 1);
843                         }
844                 }
845         }
846         
847         BMO_Flag_To_Slot(bm, &bmop, BMOP_ESUBDIVIDE_EDGES, 1, BM_EDGE);
848
849         BMO_Set_Int(&bmop, BMOP_ESUBDIVIDE_NUMCUTS, numcuts);
850         flag = B_KNIFE;
851         if (mode == KNIFE_MIDPOINT) numcuts = 1;
852         BMO_Set_Int(&bmop, BMOP_ESUBDIVIDE_FLAG, flag);
853         BMO_Set_Float(&bmop, BMOP_ESUBDIVIDE_RADIUS, 0);
854         BMO_Set_Int(&bmop, BMOP_ESUBDIVIDE_SELACTION, SUBDIV_SELECT_ORIG);
855         
856         BMO_Exec_Op(bm, &bmop);
857         BMO_Finish_Op(bm, &bmop);
858         
859         V_FREE(edges);
860         V_FREE(percents);
861
862         //if (mode==KNIFE_MIDPOINT) esubdivideflag(obedit, em, SELECT, 0, B_KNIFE, 1, SUBDIV_SELECT_ORIG);
863         //else if (mode==KNIFE_MULTICUT) esubdivideflag(obedit, em, SELECT, 0, B_KNIFE, numcuts, SUBDIV_SELECT_ORIG);
864         //else esubdivideflag(obedit, em, SELECT, 0, B_KNIFE|B_PERCENTSUBD, 1, SUBDIV_SELECT_ORIG);
865         
866         BLI_ghash_free(gh, NULL, (GHashValFreeFP)MEM_freeN);
867
868         free_editMesh(em);
869
870         em2 = bmesh_to_editmesh(bm);
871         *em = *em2;
872         
873         MEM_freeN(em2);
874         BM_Free_Mesh(bm);
875         
876         return OPERATOR_FINISHED;
877 }
878
879
880 void MESH_OT_knife_cut(wmOperatorType *ot)
881 {
882         PropertyRNA *prop;
883         
884         ot->name= "Knife Cut";
885         ot->idname= "MESH_OT_knife_cut";
886         
887         ot->invoke= WM_gesture_lines_invoke;
888         ot->modal= WM_gesture_lines_modal;
889         ot->exec= knife_cut_exec;
890         
891         ot->poll= ED_operator_editmesh;
892         
893         /* flags */
894         ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO;
895         
896         RNA_def_enum(ot->srna, "type", knife_items, KNIFE_EXACT, "Type", "");
897         prop= RNA_def_property(ot->srna, "path", PROP_COLLECTION, PROP_NONE);
898         RNA_def_property_struct_runtime(prop, &RNA_OperatorMousePath);
899         
900         /* internal */
901         RNA_def_int(ot->srna, "cursor", BC_KNIFECURSOR, 0, INT_MAX, "Cursor", "", 0, INT_MAX);
902 }
903
904 /* ******************************************************* */
905