dfd18e208fb4794739419de822bb10c938f6219a
[blender.git] / source / blender / src / 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 NaN Holding BV.
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_depsgraph.h"
56 #include "BKE_displist.h"
57 #include "BKE_global.h"
58 #include "BKE_library.h"
59 #include "BKE_mesh.h"
60 #include "BKE_object.h"
61 #include "BKE_utildefines.h"
62
63 #ifdef WITH_VERSE
64 #include "BKE_verse.h"
65 #endif
66
67 #include "BIF_cursors.h"
68 #include "BIF_editmesh.h"
69 #include "BIF_gl.h"
70 #include "BIF_glutil.h"
71 #include "BIF_graphics.h"
72 #include "BIF_interface.h"
73 #include "BIF_mywindow.h"
74 #include "BIF_screen.h"
75 #include "BIF_space.h"
76 #include "BIF_toolbox.h"
77
78 #ifdef WITH_VERSE
79 #include "BIF_verse.h"
80 #endif
81
82 #include "BSE_view.h"
83 #include "BSE_edit.h"
84 #include "BSE_drawview.h"
85
86 #include "BDR_drawobject.h"
87 #include "BDR_editobject.h"
88 #include "PIL_time.h"
89
90 #include "mydevice.h"
91 #include "blendef.h"
92
93 #include "editmesh.h"
94
95 /* next 2 includes for knife tool... shouldnt be! (ton) */
96 #include "GHOST_C-api.h"
97 #include "winlay.h"
98
99
100 /* New LoopCut */
101 static void edgering_sel(EditEdge *startedge, int select, int previewlines)
102 {
103         EditMesh *em = G.editMesh;
104         EditEdge *eed;
105         EditFace *efa;
106         EditVert *v[2][2];
107         float co[2][3];
108         int looking= 1,i;
109         
110         /* in eed->f1 we put the valence (amount of faces in edge) */
111         /* in eed->f2 we put tagged flag as correct loop */
112         /* in efa->f1 we put tagged flag as correct to select */
113
114         for(eed= em->edges.first; eed; eed= eed->next) {
115                 eed->f1= 0;
116                 eed->f2= 0;
117         }
118         for(efa= em->faces.first; efa; efa= efa->next) {
119                 efa->f1= 0;
120                 if(efa->h==0) {
121                         efa->e1->f1++;
122                         efa->e2->f1++;
123                         efa->e3->f1++;
124                         if(efa->e4) efa->e4->f1++;
125                 }
126         }
127         
128         // tag startedge OK
129         startedge->f2= 1;
130         
131         while(looking) {
132                 looking= 0;
133                 
134                 for(efa= em->faces.first; efa; efa= efa->next) {
135                         if(efa->e4 && efa->f1==0 && efa->h == 0) {      // not done quad
136                                 if(efa->e1->f1<=2 && efa->e2->f1<=2 && efa->e3->f1<=2 && efa->e4->f1<=2) { // valence ok
137
138                                         // if edge tagged, select opposing edge and mark face ok
139                                         if(efa->e1->f2) {
140                                                 efa->e3->f2= 1;
141                                                 efa->f1= 1;
142                                                 looking= 1;
143                                         }
144                                         else if(efa->e2->f2) {
145                                                 efa->e4->f2= 1;
146                                                 efa->f1= 1;
147                                                 looking= 1;
148                                         }
149                                         if(efa->e3->f2) {
150                                                 efa->e1->f2= 1;
151                                                 efa->f1= 1;
152                                                 looking= 1;
153                                         }
154                                         if(efa->e4->f2) {
155                                                 efa->e2->f2= 1;
156                                                 efa->f1= 1;
157                                                 looking= 1;
158                                         }
159                                 }
160                         }
161                 }
162         }
163         
164         if(previewlines > 0 && select == 0){
165                         persp(PERSP_VIEW);
166                         glPushMatrix();
167                         mymultmatrix(G.obedit->obmat);
168                         //glColor3ub(0, 255, 255);
169                         //glBegin(GL_LINES);                    
170                         //glVertex3f(nearest->v1->co[0],nearest->v1->co[1],nearest->v1->co[2]);
171                         //glVertex3f(nearest->v2->co[0],nearest->v2->co[1],nearest->v2->co[2]);
172                         //glEnd();
173                         for(efa= em->faces.first; efa; efa= efa->next) {
174                                 if(efa->v4 == NULL) {  continue; }
175                                 if(efa->h == 0){
176                                         if(efa->e1->f2 == 1){
177                                                 if(efa->e1->h == 1 || efa->e3->h == 1 )
178                                                         continue;
179                                                 
180                                                 v[0][0] = efa->v1;
181                                                 v[0][1] = efa->v2;
182                                                 v[1][0] = efa->v4;
183                                                 v[1][1] = efa->v3;
184                                         } else if(efa->e2->f2 == 1){
185                                                 if(efa->e2->h == 1 || efa->e4->h == 1)
186                                                         continue;
187                                                 v[0][0] = efa->v2;
188                                                 v[0][1] = efa->v3;
189                                                 v[1][0] = efa->v1;
190                                                 v[1][1] = efa->v4;                                      
191                                         } else { continue; }
192                                                                                   
193                                         for(i=1;i<=previewlines;i++){
194                                                 co[0][0] = (v[0][1]->co[0] - v[0][0]->co[0])*(i/((float)previewlines+1))+v[0][0]->co[0];
195                                                 co[0][1] = (v[0][1]->co[1] - v[0][0]->co[1])*(i/((float)previewlines+1))+v[0][0]->co[1];
196                                                 co[0][2] = (v[0][1]->co[2] - v[0][0]->co[2])*(i/((float)previewlines+1))+v[0][0]->co[2];
197
198                                                 co[1][0] = (v[1][1]->co[0] - v[1][0]->co[0])*(i/((float)previewlines+1))+v[1][0]->co[0];
199                                                 co[1][1] = (v[1][1]->co[1] - v[1][0]->co[1])*(i/((float)previewlines+1))+v[1][0]->co[1];
200                                                 co[1][2] = (v[1][1]->co[2] - v[1][0]->co[2])*(i/((float)previewlines+1))+v[1][0]->co[2];                                        
201                                                 glColor3ub(255, 0, 255);
202                                                 glBegin(GL_LINES);      
203                                                 glVertex3f(co[0][0],co[0][1],co[0][2]);
204                                                 glVertex3f(co[1][0],co[1][1],co[1][2]);
205                                                 glEnd();
206                                         }
207                                 }
208                         }
209                         glPopMatrix();   
210         } else {        
211         
212         /* (de)select the edges */
213                 for(eed= em->edges.first; eed; eed= eed->next) {
214                 if(eed->f2) EM_select_edge(eed, select);
215                 }
216         }
217 }
218 void CutEdgeloop(int numcuts)
219 {
220         EditMesh *em = G.editMesh;
221         EditEdge *nearest=NULL, *eed;
222         float fac;
223         int keys = 0, holdnum=0, selectmode, dist;
224         short mvalo[2] = {0,0}, mval[2];
225         short event, val, choosing=1, cancel=0, cuthalf = 0, smooth=0;
226         short hasHidden = 0;
227         char msg[128];
228         
229         selectmode = G.scene->selectmode;
230                 
231         if(G.scene->selectmode & SCE_SELECT_FACE){
232                 G.scene->selectmode =  SCE_SELECT_EDGE;
233                 EM_selectmode_set();      
234         }
235         
236         
237         BIF_undo_push("Loopcut Begin");
238         while(choosing && !cancel){
239                 getmouseco_areawin(mval);
240                 if (mval[0] != mvalo[0] || mval[1] != mvalo[1]) {
241                         mvalo[0] = mval[0];
242                         mvalo[1] = mval[1];
243                         dist= 50;
244                         nearest = findnearestedge(&dist);       // returns actual distance in dist
245                         scrarea_do_windraw(curarea);    // after findnearestedge, backbuf!
246                         
247                         sprintf(msg,"Number of Cuts: %d",numcuts);
248                         if(smooth){
249                                 sprintf(msg,"%s (S)mooth: on",msg);
250                         } else {
251                                 sprintf(msg,"%s (S)mooth: off",msg);
252                         }
253                         
254                         headerprint(msg);
255                         /* Need to figure preview */
256                         if(nearest){
257                                 edgering_sel(nearest, 0, numcuts);
258                          }   
259                         screen_swapbuffers();
260                         
261                 /* backbuffer refresh for non-apples (no aux) */
262 #ifndef __APPLE__
263                         if(G.vd->drawtype>OB_WIRE && (G.vd->flag & V3D_ZBUF_SELECT)) {
264                                 backdrawview3d(0);
265                         }
266 #endif
267                 }
268                 else PIL_sleep_ms(10);  // idle         
269                 
270                 
271                 while(qtest()) 
272                 {
273                         val=0;
274                         event= extern_qread(&val);
275                         if(val && (event ==  MOUSEX || event == MOUSEY)){ ; } 
276                         else if(val && ((event==LEFTMOUSE || event==RETKEY) || (event == MIDDLEMOUSE || event==PADENTER)))
277                         {
278                                 if(event == MIDDLEMOUSE){
279                                         cuthalf = 1;
280                                 }
281                                 if (nearest==NULL)
282                                         cancel = 1;
283                                 choosing=0;
284                                 mvalo[0] = -1;
285                         }
286                         else if(val && (event==ESCKEY || event==RIGHTMOUSE ))
287                         {
288                                 choosing=0;
289                                 cancel = 1;
290                                 mvalo[0] = -1;
291                         }
292                         else if(val && (event==PADPLUSKEY || event==WHEELUPMOUSE))
293                         {
294                                 numcuts++;
295                                 mvalo[0] = -1;
296                         }
297                         else if(val && (event==PADMINUS || event==WHEELDOWNMOUSE))
298                         {
299                                 if(numcuts > 1){
300                                         numcuts--;
301                                         mvalo[0] = -1;
302                                 } 
303                         }
304                         else if(val && event==SKEY)
305                         {
306                                 if(smooth){smooth=0;} 
307                                 else { smooth=1; }
308                                 mvalo[0] = -1;
309                         }
310                         
311                         else if(val){
312                                 holdnum = -1;
313                                 switch(event){
314                                         case PAD9:
315                                         case NINEKEY:
316                                                 holdnum = 9; break;
317                                         case PAD8:
318                                         case EIGHTKEY:
319                                                 holdnum = 8;break;
320                                         case PAD7:
321                                         case SEVENKEY:
322                                                 holdnum = 7;break;
323                                         case PAD6:
324                                         case SIXKEY:
325                                                 holdnum = 6;break;
326                                         case PAD5:
327                                         case FIVEKEY:
328                                                 holdnum = 5;break;
329                                         case PAD4:
330                                         case FOURKEY:
331                                                 holdnum = 4;break;
332                                         case PAD3:
333                                         case THREEKEY:
334                                                 holdnum = 3; break;
335                                         case PAD2:
336                                         case TWOKEY:
337                                                 holdnum = 2;break;
338                                         case PAD1:
339                                         case ONEKEY:
340                                                 holdnum = 1; break;
341                                         case PAD0:
342                                         case ZEROKEY:
343                                                 holdnum = 0;break;      
344                                         case BACKSPACEKEY:
345                                                 holdnum = -2;break;                     
346                                 }
347                                 if(holdnum >= 0 && numcuts*10 < 130){
348                                         if(keys == 0){  // first level numeric entry
349                                                         if(holdnum > 0){
350                                                                         numcuts = holdnum;
351                                                                         keys++;         
352                                                         }
353                                         } else if(keys > 0){//highrt level numeric entry
354                                                         numcuts *= 10;
355                                                         numcuts += holdnum;
356                                                         keys++;         
357                                         }
358                                 } else if (holdnum == -2){// backspace
359                                         if (keys > 1){
360                                                 numcuts /= 10;          
361                                                 keys--;
362                                         } else {
363                                                 numcuts=1;
364                                                 keys = 0;
365                                         }
366                                 }
367                                 mvalo[0] = -1;
368                                 break;
369                         }  // End Numeric Entry                                         
370                 }  //End while(qtest())
371         }   // End Choosing
372         scrarea_queue_winredraw(curarea);
373
374         if(cancel){
375                 return;   
376         }
377         /* clean selection */
378         for(eed=em->edges.first; eed; eed = eed->next){
379                 EM_select_edge(eed,0);
380         }
381         /* select edge ring */
382         edgering_sel(nearest, 1, 0);
383         
384         /* now cut the loops */
385         if(smooth){
386                 fac= 1.0f;
387                 if(fbutton(&fac, 0.0f, 5.0f, 10, 10, "Smooth:")==0) return;
388                 fac= 0.292f*fac;                        
389                 esubdivideflag(SELECT,fac,B_SMOOTH,numcuts,SUBDIV_SELECT_LOOPCUT);
390         } else {
391                 esubdivideflag(SELECT,0,0,numcuts,SUBDIV_SELECT_LOOPCUT);
392         }
393         /* if this was a single cut, enter edgeslide mode */
394         if(numcuts == 1 && hasHidden == 0){
395                 if(cuthalf)
396                         EdgeSlide(1,0.0);
397                 else {
398                         if(EdgeSlide(0,0.0) == -1){
399                                 BIF_undo();
400                         }
401                 }
402         }
403         
404         if(G.scene->selectmode !=  selectmode){
405                 G.scene->selectmode = selectmode;
406                 EM_selectmode_set();
407         }       
408         
409         DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
410 #ifdef WITH_VERSE
411         if(G.editMesh->vnode)
412                 sync_all_verseverts_with_editverts((VNode*)G.editMesh->vnode);
413 #endif
414         scrarea_queue_headredraw(curarea);
415         scrarea_queue_winredraw(curarea);
416         return;
417 }
418
419
420 /* *************** LOOP SELECT ************* */
421 #if 0
422 static short edgeFaces(EditEdge *e)
423 {
424         EditMesh *em = G.editMesh;
425         EditFace *search=NULL;
426         short count = 0;
427         
428         search = em->faces.first;
429         while(search){
430                 if((search->e1 == e || search->e2 == e) || (search->e3 == e || search->e4 == e)) 
431                         count++;
432                 search = search->next;
433         }
434         return count;   
435 }
436 #endif
437
438 /* this utility function checks to see if 2 edit edges share a face,
439         returns 1 if they do
440         returns 0 if they do not, or if the function is passed the same edge 2 times
441 */
442 short sharesFace(EditEdge* e1, EditEdge* e2)
443 {
444         EditMesh *em = G.editMesh;
445         EditFace *search=NULL;
446         
447         search = em->faces.first;
448         if (e1 == e2){
449                 return 0 ;
450         }
451         while(search){
452                 if(
453                         ((search->e1 == e1 || search->e2 == e1) || (search->e3 == e1 || search->e4 == e1)) &&
454                         ((search->e1 == e2 || search->e2 == e2) || (search->e3 == e2 || search->e4 == e2))
455                         ) {
456                         return 1;
457                 }
458                 search = search->next;
459         }
460         return 0;
461 }
462
463
464 /*   ***************** TRAIL ************************
465
466 Read a trail of mouse coords and return them as an array of CutCurve structs
467 len returns number of mouse coords read before commiting with RETKEY   
468 It is up to the caller to free the block when done with it,
469
470 XXX Is only used here, so local inside this file (ton)
471  */
472
473 #define TRAIL_POLYLINE 1 /* For future use, They don't do anything yet */
474 #define TRAIL_FREEHAND 2
475 #define TRAIL_MIXED    3 /* (1|2) */
476 #define TRAIL_AUTO     4 
477 #define TRAIL_MIDPOINTS 8
478
479 typedef struct CutCurve {
480         float  x; 
481         float  y;
482 } CutCurve;
483
484 static CutCurve *get_mouse_trail(int *len, char mode, char cutmode, struct GHash *gh)
485 {
486         CutCurve *curve,*temp;
487         EditVert *snapvert;
488         float *scr, mval[2]={0.0,0.0}, lastx=0, lasty=0, lockx=0, locky=0;
489         int i=0, j, blocks=1, lasti=0;
490         int dist, tolerance;
491         short event, val, qual, vsnap=0, ldown=0, restart=0, rubberband=0;
492         short mval1[2], lockaxis=0, oldmode; 
493         
494         *len=0;
495         tolerance = 75;
496         
497         curve=(CutCurve *)MEM_callocN(1024*sizeof(CutCurve), "MouseTrail");
498
499         if (!curve) {
500                 printf("failed to allocate memory in get_mouse_trail()\n");
501                 return(NULL);
502         }
503         mywinset(curarea->win);
504         
505         
506         if(cutmode != KNIFE_MULTICUT){ 
507                 /*redraw backbuffer if in zbuffered selection mode but not vertex selection*/
508                 if(G.vd->drawtype>OB_WIRE && (G.vd->flag & V3D_ZBUF_SELECT)) {
509                         oldmode = G.scene->selectmode;
510                         G.scene->selectmode = SCE_SELECT_VERTEX;
511                         backdrawview3d(0);
512                         G.scene->selectmode = oldmode;
513                 }
514                 glDrawBuffer(GL_FRONT);
515                 headerprint("(LMB) draw, (Ctrl held while drawing) snap to vertex, (MMB) constrain to x/y screen axis, (Enter) cut "
516                                         "(with Ctrl to select cut line), (Esc) cancel");
517         }
518         else{
519                 glDrawBuffer(GL_FRONT);
520                 headerprint("(LMB) draw, (MMB) constrain to x/y screen axis, (Enter) cut (with Ctrl to select cut line), (Esc) cancel");
521         }
522         bglFlush();
523         
524         persp(PERSP_WIN);
525         
526         glColor3ub(255, 0, 255);
527         
528         while(TRUE) {
529                 
530                 event=extern_qread(&val);       /* Enter or RMB indicates finish */
531                 if(val) {
532                         if(event==RETKEY || event==PADENTER) break;
533                 }
534                 
535                 if( event==ESCKEY || event==RIGHTMOUSE ) {
536                         if (curve) MEM_freeN(curve);
537                         *len=0;
538                         bglFlush();
539                         glDrawBuffer(GL_BACK);
540                         return(NULL);
541                 }       
542                 
543                 if (rubberband)  { /* rubberband mode, undraw last rubberband */
544                         glLineWidth(2.0);
545                         sdrawXORline((int)curve[i-1].x, (int)curve[i-1].y,(int)mval[0],(int) mval[1]); 
546                         glLineWidth(1.0);
547                         glFlush();
548                         rubberband=0;
549                 }
550                 
551                 /*handle vsnap*/
552                 vsnap = 0;
553                 if(cutmode != KNIFE_MULTICUT){
554                         qual = get_qual();
555                         if(qual & LR_CTRLKEY) vsnap = 1;
556                 }
557                 
558                 if(vsnap){ 
559                         persp(PERSP_VIEW);
560                         dist = tolerance;
561                         snapvert = findnearestvert(&dist, SELECT, 0);
562                         glColor3ub(255, 0, 255);
563                         glDrawBuffer(GL_FRONT);
564                         persp(PERSP_WIN);
565                         if(snapvert && (dist < tolerance)){
566                                 scr = BLI_ghash_lookup(gh, snapvert);
567                                 mval[0] = scr[0];
568                                 mval[1] = scr[1];
569                         }
570                         else{ 
571                                 getmouseco_areawin(mval1);
572                                 mval[0] = (float)mval1[0];
573                                 mval[1] = (float)mval1[1];
574                         }
575                 }
576                 
577                 else{
578                         getmouseco_areawin(mval1);
579                         mval[0] = (float)mval1[0];
580                         mval[1] = (float)mval1[1];
581                 }
582                 
583                 
584                 if (lockaxis==1) mval[1]=locky;
585                 if (lockaxis==2) mval[0]=lockx;
586                 
587                 if ( ((i==0) || (mval[0]!=curve[i-1].x) || (mval[1]!=curve[i-1].y))
588                         && (get_mbut() & L_MOUSE) ){ /* record changes only, if LMB down */
589                         
590                         lastx=curve[i].x=mval[0];
591                         lasty=curve[i].y=mval[1];
592                         
593                         lockaxis=0;
594                         
595                         i++; 
596                         
597                         ldown=1;
598                         if (restart) { 
599                                 for(j=1;j<i;j++) sdrawXORline((int)curve[j-1].x, (int)curve[j-1].y, (int)curve[j].x, (int)curve[j].y);
600                                 if (rubberband) sdrawXORline((int)curve[j].x, (int)curve[j].y, (int)mval[0], (int)mval[1]);
601                                 glFlush();
602                                 rubberband=0;
603                                 lasti=i=0;
604                                 restart=0;
605                                 ldown=0;
606                         }
607                 }
608                 
609                 if ((event==MIDDLEMOUSE)&&(get_mbut()&M_MOUSE)&&(i)){/*MMB Down*/
610                 /*determine which axis to lock to, or clear if locked */
611                         if (lockaxis) lockaxis=0;
612                         else if (abs(curve[i-1].x-mval[0]) > abs(curve[i-1].y-mval[1])) lockaxis=1;
613                         else lockaxis=2;
614                         
615                         if (lockaxis) {
616                                 lockx=lastx;
617                                 locky=lasty;
618                         }
619                 }
620                 
621                 if ((i>1)&&(i!=lasti)) {  /*Draw recorded part of curve */
622                         sdrawline((int)curve[i-2].x, (int)curve[i-2].y, (int)curve[i-1].x, (int)curve[i-1].y);
623                         bglFlush();
624                 }
625                 
626                 if ((i==lasti)&&(i>0)) { /*Draw rubberband */
627                         glLineWidth(2.0);
628                         sdrawXORline((int)curve[i-1].x, (int)curve[i-1].y,(int)mval[0], (int)mval[1]);
629                         glLineWidth(1.0);
630                         bglFlush();
631                         rubberband=1;
632                 }
633                 lasti=i;
634
635                 if (i>=blocks*1024) { /* reallocate data if out of room */
636                         temp=curve;
637                         curve=(CutCurve *)MEM_callocN((blocks+1)*1024*sizeof(CutCurve), "MouseTrail");
638                         if (!curve) {
639                                 printf("failed to re-allocate memory in get_mouse_trail()\n");
640                                 return(NULL);
641                         }
642                         memcpy(curve, temp, blocks*1024*sizeof(CutCurve));
643                         blocks++;
644                         MEM_freeN(temp);
645                 }
646         }
647
648         bglFlush();
649         glDrawBuffer(GL_BACK);
650         persp(PERSP_VIEW);
651
652         *len=i;
653
654         return(curve);
655 }
656
657
658
659
660 /* ******************************************************************** */
661 /* Knife Subdivide Tool.  Subdivides edges intersected by a mouse trail
662         drawn by user.
663         
664         Currently mapped to KKey when in MeshEdit mode.
665         Usage:
666                 Hit Shift K, Select Centers or Exact
667                 Hold LMB down to draw path, hit RETKEY.
668                 ESC cancels as expected.
669    
670         Contributed by Robert Wenzlaff (Det. Thorn).
671 */
672
673 /* prototype */
674 static float seg_intersect(struct EditEdge * e, CutCurve *c, int len, char mode, struct GHash *gh);
675
676 void KnifeSubdivide(char mode)
677 {
678         EditMesh *em = G.editMesh;
679         EditEdge *eed;
680         EditVert *eve;
681         CutCurve *curve;                
682         Window *win;
683         
684         struct GHash *gh;
685         int oldcursor, len=0;
686         float isect=0.0;
687         short numcuts=1;
688         float  *scr, co[4];
689         
690         if (G.obedit==0) return;
691
692         if (EM_nvertices_selected() < 2) {
693                 error("No edges are selected to operate on");
694                 return;
695         }
696
697         if (mode==KNIFE_PROMPT) {
698                 short val= pupmenu("Cut Type %t|Exact Line%x1|Midpoints%x2|Multicut%x3");
699                 if(val<1) return;
700                 mode = val;     // warning, mode is char, pupmenu returns -1 with ESC
701         }
702
703         if(mode == KNIFE_MULTICUT) {
704                 if(button(&numcuts, 2, 128, "Number of Cuts:")==0) return;
705         }
706
707         /* Set a knife cursor here */
708         oldcursor=get_cursor();
709         
710         win=winlay_get_active_window();
711         
712         SetBlenderCursor(BC_KNIFECURSOR);
713         
714         for(eed=em->edges.first; eed; eed= eed->next) eed->tmp.fp = 0.0; /*store percentage of edge cut for KNIFE_EXACT here.*/
715         
716         /*the floating point coordinates of verts in screen space will be stored in a hash table according to the vertices pointer*/
717         gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
718         for(eve=em->verts.first; eve; eve=eve->next){
719                 scr = MEM_mallocN(sizeof(float)*2, "Vertex Screen Coordinates");
720                 VECCOPY(co, eve->co);
721                 co[3]= 1.0;
722                 Mat4MulVec4fl(G.obedit->obmat, co);
723                 project_float(co,scr);
724                 BLI_ghash_insert(gh, eve, scr);
725                 eve->f1 = 0; /*store vertex intersection flag here*/
726         
727         }
728         
729         curve=get_mouse_trail(&len, TRAIL_MIXED, mode, gh);
730         
731         if (curve && len && mode){
732                 eed= em->edges.first;           
733                 while(eed) {    
734                         if( eed->v1->f & eed->v2->f & SELECT ){         // NOTE: uses vertex select, subdiv doesnt do edges yet
735                                 isect=seg_intersect(eed, curve, len, mode, gh);
736                                 if (isect) eed->f2= 1;
737                                 else eed->f2=0;
738                                 eed->tmp.fp= isect;
739                                 //printf("isect=%i\n", isect);
740                         }
741                         else {
742                                 eed->f2=0;
743                                 eed->f1=0;
744                         }
745                         eed= eed->next;
746                 }
747                 
748                 if(mode==KNIFE_EXACT) esubdivideflag(SELECT, 0, B_KNIFE|B_PERCENTSUBD,1,SUBDIV_SELECT_ORIG);
749                 else if (mode==KNIFE_MIDPOINT) esubdivideflag(SELECT, 0, B_KNIFE,1,SUBDIV_SELECT_ORIG);
750                 else if (mode==KNIFE_MULTICUT) esubdivideflag(SELECT, 0, B_KNIFE,numcuts,SUBDIV_SELECT_ORIG);
751
752                 eed=em->edges.first;
753                 while(eed){
754                         eed->f2=0;
755                         eed->f1=0;
756                         eed=eed->next;
757                 }       
758         }
759         /* Return to old cursor and flags...*/
760         
761         addqueue(curarea->win,  REDRAW, 0);
762         window_set_cursor(win, oldcursor);
763         BLI_ghash_free(gh, NULL, (GHashValFreeFP)MEM_freeN);
764         if (curve) MEM_freeN(curve);
765
766 #ifdef WITH_VERSE
767         if(G.editMesh->vnode)
768                 sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
769 #endif
770
771         BIF_undo_push("Knife");
772 }
773
774 /* seg_intersect() Determines if and where a mouse trail intersects an EditEdge */
775
776 static float seg_intersect(EditEdge *e, CutCurve *c, int len, char mode, struct GHash *gh)
777 {
778 #define MAXSLOPE 100000
779         float  x11, y11, x12=0, y12=0, x2max, x2min, y2max;
780         float  y2min, dist, lastdist=0, xdiff2, xdiff1;
781         float  m1, b1, m2, b2, x21, x22, y21, y22, xi;
782         float  yi, x1min, x1max, y1max, y1min, perc=0; 
783         float  *scr;
784         float  threshold;
785         int  i;
786         
787         //threshold = 0.000001; /*tolerance for vertex intersection*/
788         threshold = G.scene->toolsettings->select_thresh / 100;
789         
790         /* Get screen coords of verts */
791         scr = BLI_ghash_lookup(gh, e->v1);
792         x21=scr[0];
793         y21=scr[1];
794         
795         scr = BLI_ghash_lookup(gh, e->v2);
796         x22=scr[0];
797         y22=scr[1];
798         
799         xdiff2=(x22-x21);  
800         if (xdiff2) {
801                 m2=(y22-y21)/xdiff2;
802                 b2= ((x22*y21)-(x21*y22))/xdiff2;
803         }
804         else {
805                 m2=MAXSLOPE;  /* Verticle slope  */
806                 b2=x22;      
807         }
808         
809         /*check for *exact* vertex intersection first*/
810         if(mode!=KNIFE_MULTICUT){
811                 for (i=0; i<len; i++){
812                         if (i>0){
813                                 x11=x12;
814                                 y11=y12;
815                         }
816                         else {
817                                 x11=c[i].x;
818                                 y11=c[i].y;
819                         }
820                         x12=c[i].x;
821                         y12=c[i].y;
822                         
823                         /*test e->v1*/
824                         if((x11 == x21 && y11 == y21) || (x12 == x21 && y12 == y21)){
825                                 e->v1->f1 = 1;
826                                 perc = 0;
827                                 return(perc);
828                         }
829                         /*test e->v2*/
830                         else if((x11 == x22 && y11 == y22) || (x12 == x22 && y12 == y22)){
831                                 e->v2->f1 = 1;
832                                 perc = 0;
833                                 return(perc);
834                         }
835                 }
836         }
837         
838         /*now check for edge interesect (may produce vertex intersection as well)*/
839         for (i=0; i<len; i++){
840                 if (i>0){
841                         x11=x12;
842                         y11=y12;
843                 }
844                 else {
845                         x11=c[i].x;
846                         y11=c[i].y;
847                 }
848                 x12=c[i].x;
849                 y12=c[i].y;
850                 
851                 /* Perp. Distance from point to line */
852                 if (m2!=MAXSLOPE) dist=(y12-m2*x12-b2);/* /sqrt(m2*m2+1); Only looking for */
853                                                        /* change in sign.  Skip extra math */   
854                 else dist=x22-x12;      
855                 
856                 if (i==0) lastdist=dist;
857                 
858                 /* if dist changes sign, and intersect point in edge's Bound Box*/
859                 if ((lastdist*dist)<=0){
860                         xdiff1=(x12-x11); /* Equation of line between last 2 points */
861                         if (xdiff1){
862                                 m1=(y12-y11)/xdiff1;
863                                 b1= ((x12*y11)-(x11*y12))/xdiff1;
864                         }
865                         else{
866                                 m1=MAXSLOPE;
867                                 b1=x12;
868                         }
869                         x2max=MAX2(x21,x22)+0.001; /* prevent missed edges   */
870                         x2min=MIN2(x21,x22)-0.001; /* due to round off error */
871                         y2max=MAX2(y21,y22)+0.001;
872                         y2min=MIN2(y21,y22)-0.001;
873                         
874                         /* Found an intersect,  calc intersect point */
875                         if (m1==m2){ /* co-incident lines */
876                                                 /* cut at 50% of overlap area*/
877                                 x1max=MAX2(x11, x12);
878                                 x1min=MIN2(x11, x12);
879                                 xi= (MIN2(x2max,x1max)+MAX2(x2min,x1min))/2.0;  
880                                 
881                                 y1max=MAX2(y11, y12);
882                                 y1min=MIN2(y11, y12);
883                                 yi= (MIN2(y2max,y1max)+MAX2(y2min,y1min))/2.0;
884                         }                       
885                         else if (m2==MAXSLOPE){ 
886                                 xi=x22;
887                                 yi=m1*x22+b1;
888                         }
889                         else if (m1==MAXSLOPE){ 
890                                 xi=x12;
891                                 yi=m2*x12+b2;
892                         }
893                         else {
894                                 xi=(b1-b2)/(m2-m1);
895                                 yi=(b1*m2-m1*b2)/(m2-m1);
896                         }
897                         
898                         /* Intersect inside bounding box of edge?*/
899                         if ((xi>=x2min)&&(xi<=x2max)&&(yi<=y2max)&&(yi>=y2min)){
900                                 /*test for vertex intersect that may be 'close enough'*/
901                                 if(mode!=KNIFE_MULTICUT){
902                                         if(xi <= (x21 + threshold) && xi >= (x21 - threshold)){
903                                                 if(yi <= (y21 + threshold) && yi >= (y21 - threshold)){
904                                                         e->v1->f1 = 1;
905                                                         perc = 0;
906                                                         break;
907                                                 }
908                                         }
909                                         if(xi <= (x22 + threshold) && xi >= (x22 - threshold)){
910                                                 if(yi <= (y22 + threshold) && yi >= (y22 - threshold)){
911                                                         e->v2->f1 = 1;
912                                                         perc = 0;
913                                                         break;
914                                                 }
915                                         }
916                                 }
917                                 if ((m2<=1.0)&&(m2>=-1.0)) perc = (xi-x21)/(x22-x21);   
918                                 else perc=(yi-y21)/(y22-y21); /*lower slope more accurate*/
919                                 //isect=32768.0*(perc+0.0000153); /* Percentage in 1/32768ths */
920                                 break;
921                         }
922                 }       
923                 lastdist=dist;
924         }
925         return(perc);
926
927
928 void LoopMenu() /* Called by KKey */
929 {
930         short ret;
931         
932         ret=pupmenu("Loop/Cut Menu %t|Loop Cut (CTRL-R)%x2|"
933                                 "Knife (Exact) %x3|Knife (Midpoints)%x4|Knife (Multicut)%x5");
934                                 
935         switch (ret){
936                 case 2:
937                         CutEdgeloop(1);
938                         break;
939                 case 3: 
940                         KnifeSubdivide(KNIFE_EXACT);
941                         break;
942                 case 4:
943                         KnifeSubdivide(KNIFE_MIDPOINT);
944                         break;
945                 case 5:
946                         KnifeSubdivide(KNIFE_MULTICUT);
947                         break;
948         }
949
950 }
951