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