- remove calls to showkeypos from exit editmode functions, should be
[blender.git] / source / blender / src / editmesh_loop.c
1 /**
2  * $Id: 
3  *
4  * ***** BEGIN GPL/BL DUAL 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. The Blender
10  * Foundation also sells licenses for use in proprietary software under
11  * the Blender License.  See http://www.blender.org/BL/ for information
12  * about this.
13  *
14  * This program is distributed in the hope that it will be useful,
15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  * GNU General Public License for more details.
18  *
19  * You should have received a copy of the GNU General Public License
20  * along with this program; if not, write to the Free Software Foundation,
21  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
22  *
23  * The Original Code is Copyright (C) 2004 by NaN Holding BV.
24  * All rights reserved.
25  *
26  * The Original Code is: all of this file.
27  *
28  * Contributor(s): none yet.
29  *
30  * ***** END GPL/BL DUAL LICENSE BLOCK *****
31  */
32
33 /*
34
35 editmesh_loop: tools with own drawing subloops, select, knife, subdiv
36
37 */
38
39 #include <stdlib.h>
40 #include <string.h>
41 #include <math.h>
42
43 #include "MEM_guardedalloc.h"
44
45
46 #include "DNA_mesh_types.h"
47 #include "DNA_meshdata_types.h"
48 #include "DNA_object_types.h"
49 #include "DNA_scene_types.h"
50 #include "DNA_screen_types.h"
51 #include "DNA_view3d_types.h"
52
53 #include "BLI_blenlib.h"
54 #include "BLI_arithb.h"
55 #include "BLI_editVert.h"
56
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 "BIF_cursors.h"
65 #include "BIF_editmesh.h"
66 #include "BIF_gl.h"
67 #include "BIF_glutil.h"
68 #include "BIF_graphics.h"
69 #include "BIF_interface.h"
70 #include "BIF_mywindow.h"
71 #include "BIF_screen.h"
72 #include "BIF_space.h"
73 #include "BIF_toolbox.h"
74
75 #include "BSE_view.h"
76 #include "BSE_edit.h"
77 #include "BSE_drawview.h"
78
79 #include "BDR_drawobject.h"
80 #include "BDR_editobject.h"
81 #include "PIL_time.h"
82
83 #include "mydevice.h"
84 #include "blendef.h"
85
86 #include "editmesh.h"
87
88 /* next 2 includes for knife tool... shouldnt be! (ton) */
89 #include "GHOST_C-api.h"
90 #include "winlay.h"
91
92
93 /* New LoopCut */
94 static void edgering_sel(EditEdge *startedge, int select, int previewlines){
95         EditMesh *em = G.editMesh;
96         EditEdge *eed;
97         EditFace *efa;
98         int looking= 1,i;
99         float co[2][3];
100         EditVert *v[2][2];
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) {     // 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                 persp(PERSP_VIEW);
157                         glPushMatrix();
158                         mymultmatrix(G.obedit->obmat);
159                         //glColor3ub(0, 255, 255);
160                         //glBegin(GL_LINES);                    
161                         //glVertex3f(nearest->v1->co[0],nearest->v1->co[1],nearest->v1->co[2]);
162                         //glVertex3f(nearest->v2->co[0],nearest->v2->co[1],nearest->v2->co[2]);
163                         //glEnd();
164                         for(efa= em->faces.first; efa; efa= efa->next) {
165                 if(efa->v4 == NULL) {  continue; }
166                 if(efa->e1->f2 == 1){
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                     v[0][0] = efa->v2;
173                     v[0][1] = efa->v3;
174                     v[1][0] = efa->v1;
175                     v[1][1] = efa->v4;                    
176                 } else { continue; }
177                                       
178                         for(i=1;i<=previewlines;i++){
179                     co[0][0] = (v[0][1]->co[0] - v[0][0]->co[0])*(i/((float)previewlines+1))+v[0][0]->co[0];
180                     co[0][1] = (v[0][1]->co[1] - v[0][0]->co[1])*(i/((float)previewlines+1))+v[0][0]->co[1];
181                     co[0][2] = (v[0][1]->co[2] - v[0][0]->co[2])*(i/((float)previewlines+1))+v[0][0]->co[2];
182
183                     co[1][0] = (v[1][1]->co[0] - v[1][0]->co[0])*(i/((float)previewlines+1))+v[1][0]->co[0];
184                     co[1][1] = (v[1][1]->co[1] - v[1][0]->co[1])*(i/((float)previewlines+1))+v[1][0]->co[1];
185                     co[1][2] = (v[1][1]->co[2] - v[1][0]->co[2])*(i/((float)previewlines+1))+v[1][0]->co[2];                    
186                     glColor3ub(255, 0, 255);
187                                 glBegin(GL_LINES);      
188                                 glVertex3f(co[0][0],co[0][1],co[0][2]);
189                                 glVertex3f(co[1][0],co[1][1],co[1][2]);
190                                 glEnd();
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(int numcuts){
203     EditMesh *em = G.editMesh;
204     int keys = 0,holdnum=0;
205         short mvalo[2] = {0,0}, mval[2];
206         EditEdge* nearest,*eed;
207         short event,val,choosing=1,cancel=0,dist,cuthalf = 0;
208     char msg[128];
209     while(choosing){
210         getmouseco_areawin(mval);
211                 if (mval[0] != mvalo[0] || mval[1] != mvalo[1]) {
212
213                         mvalo[0] = mval[0];
214                         mvalo[1] = mval[1];
215
216                         dist= 50;
217                         nearest = findnearestedge(&dist);       // returns actual distance in dist
218                         scrarea_do_windraw(curarea);    // after findnearestedge, backbuf!        
219
220             sprintf(msg,"Number of Cuts: %d",numcuts);
221                 headerprint(msg);
222
223             /* Need to figure preview */
224             if(nearest){
225                     edgering_sel(nearest, 0, numcuts);
226              }   
227                         screen_swapbuffers();
228                         
229                 /* backbuffer refresh for non-apples (no aux) */
230 #ifndef __APPLE__
231                         if(G.vd->drawtype>OB_WIRE && (G.vd->flag & V3D_ZBUF_SELECT)) {
232                                 backdrawview3d(0);
233                         }
234 #endif
235                 }
236                 else PIL_sleep_ms(10);  // idle         
237                 while(qtest()) 
238                 {
239                         val=0;
240                         event= extern_qread(&val);
241                         if(val && ((event==LEFTMOUSE || event==RETKEY) || (event == MIDDLEMOUSE || event==PADENTER)))
242                         {
243                 if(event == MIDDLEMOUSE){
244                     cuthalf = 1;   
245                 }
246                                 if (nearest==NULL)
247                                         cancel = 1;
248                                 choosing=0;
249                                 break;
250                         }
251                         else if(val && (event==ESCKEY || event==RIGHTMOUSE ))
252                         {
253                                 choosing=0;
254                                 cancel = 1;
255                                 break;
256                         }
257                         else if(val && (event==PADPLUSKEY || event==WHEELUPMOUSE))
258                         {
259                                 numcuts++;
260                                 mvalo[0] = 0;mvalo[1] = 0;
261                                 break;
262                         }
263                         else if(val && (event==PADMINUS || event==WHEELDOWNMOUSE))
264                         {
265                 if(numcuts > 1){
266                                 numcuts--;
267                                 mvalo[0] = 0;mvalo[1] = 0;
268                                 break;
269                 } 
270                         }
271                         else if(val){
272                 holdnum = -1;
273                 switch(event){
274                         case PAD9:
275                         case NINEKEY:
276                                 holdnum = 9; break;
277                         case PAD8:
278                         case EIGHTKEY:
279                                 holdnum = 8; break;
280                         case PAD7:
281                         case SEVENKEY:
282                                 holdnum = 7; break;
283                         case PAD6:
284                         case SIXKEY:
285                                 holdnum = 6; break;
286                         case PAD5:
287                         case FIVEKEY:
288                                 holdnum = 5; break;
289                         case PAD4:
290                         case FOURKEY:
291                                 holdnum = 4; break;
292                         case PAD3:
293                         case THREEKEY:
294                                 holdnum = 3; break;
295                         case PAD2:
296                         case TWOKEY:
297                                 holdnum = 2; break;
298                         case PAD1:
299                         case ONEKEY:
300                                 holdnum = 1; break;
301                         case PAD0:
302                         case ZEROKEY:
303                                 holdnum = 0; break;     
304                     case BACKSPACEKEY:
305                                 holdnum = -2; break;                    
306                }
307                if(holdnum >= 0 && numcuts*10 < 130){
308                     if(keys == 0){  // first level numeric entry
309                             if(holdnum > 0){
310                                        numcuts = holdnum;
311                                        keys++;        
312                             }
313                     } else if(keys > 0){//highrt level numeric entry
314                             numcuts *= 10;
315                             numcuts += holdnum;
316                             keys++;        
317                     }
318                } else if (holdnum == -2){// backspace
319                   if (keys > 1){
320                       numcuts /= 10;        
321                       keys--;
322                   } else {
323                       numcuts=1;
324                       keys = 0;   
325                   }      
326                }
327                mvalo[0] = 0;mvalo[1] = 0;
328                PIL_sleep_ms(10);
329                break;
330             }
331                 }       
332     }
333     scrarea_do_windraw(curarea);
334     screen_swapbuffers();
335 #ifndef __APPLE__
336         if(G.vd->drawtype>OB_WIRE && (G.vd->flag & V3D_ZBUF_SELECT)) {
337                 backdrawview3d(0);
338         }
339 #endif    
340     if(cancel){
341         return;   
342     }
343     /* clean selection */
344     for(eed=em->edges.first; eed; eed = eed->next){
345         EM_select_edge(eed,0);   
346     }
347     /* select edge ring */
348         edgering_sel(nearest, 1, 0);
349         
350         /* now cut the loops */
351         esubdivideflag(SELECT,0,0,numcuts,1);
352         
353     force_draw(0);
354     makeDispList(G.obedit);
355     scrarea_queue_winredraw(curarea);
356         
357         /* if this was a single cut, enter edgeslide mode */
358         if(numcuts == 1){
359         if(cuthalf)
360             EdgeSlide(1,0.0);
361         else
362             EdgeSlide(0,0.0);       
363     }
364         
365     return;
366 }
367
368
369 /* *************** LOOP SELECT ************* */
370
371 static short edgeFaces(EditEdge *e){
372         EditMesh *em = G.editMesh;
373         EditFace *search=NULL;
374         short count = 0;
375         
376         search = em->faces.first;
377         while(search){
378                 if((search->e1 == e || search->e2 == e) || (search->e3 == e || search->e4 == e)) 
379                         count++;
380         search = search->next;
381         }
382         return count;   
383 }
384
385 /* this utility function checks to see if 2 edit edges share a face,
386         returns 1 if they do
387         returns 0 if they do not, or if the function is passed the same edge 2 times
388 */
389 short sharesFace(EditEdge* e1, EditEdge* e2)
390 {
391         EditMesh *em = G.editMesh;
392         EditFace *search=NULL;
393         search = em->faces.first;
394         if (e1 == e2){
395                 return 0 ;
396         }
397         while(search){
398                 if(
399                         ((search->e1 == e1 || search->e2 == e1) || (search->e3 == e1 || search->e4 == e1)) &&
400                         ((search->e1 == e2 || search->e2 == e2) || (search->e3 == e2 || search->e4 == e2))
401                         ) {
402                         return 1;
403                 }
404                 search = search->next;
405         }
406         return 0;
407 }
408
409
410 /*   ***************** TRAIL ************************
411
412 Read a trail of mouse coords and return them as an array of CutCurve structs
413 len returns number of mouse coords read before commiting with RETKEY   
414 It is up to the caller to free the block when done with it,
415
416 XXX Is only used here, so local inside this file (ton)
417  */
418
419 #define TRAIL_POLYLINE 1 /* For future use, They don't do anything yet */
420 #define TRAIL_FREEHAND 2
421 #define TRAIL_MIXED    3 /* (1|2) */
422 #define TRAIL_AUTO     4 
423 #define TRAIL_MIDPOINTS 8
424
425 typedef struct CutCurve {
426         short  x; 
427         short  y;
428 } CutCurve;
429
430 static CutCurve *get_mouse_trail(int *len, char mode){
431
432         CutCurve *curve,*temp;
433         short event, val, ldown=0, restart=0, rubberband=0;
434         short  mval[2], lockaxis=0, lockx=0, locky=0, lastx=0, lasty=0;
435         int i=0, j, blocks=1, lasti=0;
436         
437         *len=0;
438         curve=(CutCurve *)MEM_callocN(1024*sizeof(CutCurve), "MouseTrail");
439
440         if (!curve) {
441                 printf("failed to allocate memory in get_mouse_trail()\n");
442                 return(NULL);
443         }
444         mywinset(curarea->win);
445         glDrawBuffer(GL_FRONT);
446         
447         headerprint("LMB to draw, Enter to finish, ESC to abort.");
448
449         persp(PERSP_WIN);
450         
451         glColor3ub(200, 200, 0);
452         
453         while(TRUE) {
454                 
455                 event=extern_qread(&val);       /* Enter or RMB indicates finish */
456                 if(val) {
457                         if(event==RETKEY || event==PADENTER) break;
458                 }
459                 
460                 if( event==ESCKEY || event==RIGHTMOUSE ) {
461                         if (curve) MEM_freeN(curve);
462                         *len=0;
463                         glFlush();
464                         glDrawBuffer(GL_BACK);
465                         return(NULL);
466                         break;
467                 }       
468                 
469                 if (rubberband)  { /* rubberband mode, undraw last rubberband */
470                         glLineWidth(2.0);
471                         sdrawXORline(curve[i-1].x, curve[i-1].y,mval[0], mval[1]); 
472                         glLineWidth(1.0);
473                         glFlush();
474                         rubberband=0;
475                 }
476                 
477                 getmouseco_areawin(mval);
478                 
479                 if (lockaxis==1) mval[1]=locky;
480                 if (lockaxis==2) mval[0]=lockx;
481                 
482                 if ( ((i==0) || (mval[0]!=curve[i-1].x) || (mval[1]!=curve[i-1].y))
483                         && (get_mbut() & L_MOUSE) ){ /* record changes only, if LMB down */
484                         
485                         lastx=curve[i].x=mval[0];
486                         lasty=curve[i].y=mval[1];
487                         
488                         lockaxis=0;
489                         
490                         i++; 
491                         
492                         ldown=1;
493                         if (restart) { 
494                                 for(j=1;j<i;j++) sdrawXORline(curve[j-1].x, curve[j-1].y, curve[j].x, curve[j].y);
495                                 if (rubberband) sdrawXORline(curve[j].x, curve[j].y, mval[0], mval[1]);
496                                 glFlush();
497                                 rubberband=0;
498                                 lasti=i=0;
499                                 restart=0;
500                                 ldown=0;
501                         }
502                 }
503                 
504                 if ((event==MIDDLEMOUSE)&&(get_mbut()&M_MOUSE)&&(i)){/*MMB Down*/
505                 /*determine which axis to lock to, or clear if locked */
506                         if (lockaxis) lockaxis=0;
507                         else if (abs(curve[i-1].x-mval[0]) > abs(curve[i-1].y-mval[1])) lockaxis=1;
508                         else lockaxis=2;
509                         
510                         if (lockaxis) {
511                                 lockx=lastx;
512                                 locky=lasty;
513                         }
514                 }
515                 
516                 if ((i>1)&&(i!=lasti)) {  /*Draw recorded part of curve */
517                         sdrawline(curve[i-2].x, curve[i-2].y, curve[i-1].x, curve[i-1].y);
518                         glFlush();
519                 }
520                 
521                 if ((i==lasti)&&(i>0)) { /*Draw rubberband */
522                         glLineWidth(2.0);
523                         sdrawXORline(curve[i-1].x, curve[i-1].y,mval[0], mval[1]);
524                         glLineWidth(1.0);
525                         glFlush();
526                         rubberband=1;
527                 }
528                 lasti=i;
529
530                 if (i>=blocks*1024) { /* reallocate data if out of room */
531                         temp=curve;
532                         curve=(CutCurve *)MEM_callocN((blocks+1)*1024*sizeof(CutCurve), "MouseTrail");
533                         if (!curve) {
534                                 printf("failed to re-allocate memory in get_mouse_trail()\n");
535                                 return(NULL);
536                         }
537                         memcpy(curve, temp, blocks*1024*sizeof(CutCurve));
538                         blocks++;
539                         MEM_freeN(temp);
540                 }
541         }
542
543         glFlush();
544         glDrawBuffer(GL_BACK);
545         persp(PERSP_VIEW);
546
547         *len=i;
548
549         return(curve);
550 }
551
552
553
554
555 /* ******************************************************************** */
556 /* Knife Subdivide Tool.  Subdivides edges intersected by a mouse trail
557         drawn by user.
558         
559         Currently mapped to KKey when in MeshEdit mode.
560         Usage:
561                 Hit Shift K, Select Centers or Exact
562                 Hold LMB down to draw path, hit RETKEY.
563                 ESC cancels as expected.
564    
565         Contributed by Robert Wenzlaff (Det. Thorn).
566 */
567
568 /* prototype */
569 short seg_intersect(struct EditEdge * e, CutCurve *c, int len);
570
571 void KnifeSubdivide(char mode)
572 {
573         EditMesh *em = G.editMesh;
574         int oldcursor, len=0;
575         short isect=0;
576         CutCurve *curve;                
577         EditEdge *eed; 
578         Window *win;    
579         short numcuts=1;
580         
581         if (G.obedit==0) return;
582
583         if (EM_nvertices_selected() < 2) {
584                 error("No edges are selected to operate on");
585                 return;
586         }
587
588         if (mode==KNIFE_PROMPT) {
589                 short val= pupmenu("Cut Type %t|Exact Line%x1|Midpoints%x2|Multicut%x3");
590                 if(val<1) return;
591                 mode = val;     // warning, mode is char, pupmenu returns -1 with ESC
592         }
593
594     if(mode == KNIFE_MULTICUT) {
595         if(button(&numcuts, 2, 128, "Number of Cuts:")==0) return;
596     }
597
598         calc_meshverts_ext();  /*Update screen coords for current window */
599         
600         /* Set a knife cursor here */
601         oldcursor=get_cursor();
602
603         win=winlay_get_active_window();
604         
605         SetBlenderCursor(BC_KNIFECURSOR);
606         
607         curve=get_mouse_trail(&len, TRAIL_MIXED);
608         
609         if (curve && len && mode){
610                 eed= em->edges.first;           
611                 while(eed) {    
612                         if( eed->v1->f & eed->v2->f & SELECT ){         // NOTE: uses vertex select, subdiv doesnt do edges yet
613                                 isect=seg_intersect(eed, curve, len);
614                                 if (isect) eed->f2= 1;
615                                 else eed->f2=0;
616                                 eed->f1= isect;
617                                 //printf("isect=%i\n", isect);
618                         }
619                         else {
620                                 eed->f2=0;
621                                 eed->f1=0;
622                         }
623                         eed= eed->next;
624                 }
625                 
626                 if      (mode==KNIFE_EXACT)    esubdivideflag(1, 0, B_KNIFE|B_PERCENTSUBD,1,0);
627                 else if (mode==KNIFE_MIDPOINT) esubdivideflag(1, 0, B_KNIFE,1,0);
628                 else if (mode==KNIFE_MULTICUT) esubdivideflag(1, 0, B_KNIFE,numcuts,0);
629                         
630                 eed=em->edges.first;
631                 while(eed){
632                         eed->f2=0;
633                         eed->f1=0;
634                         eed=eed->next;
635                 }       
636         }
637         /* Return to old cursor and flags...*/
638         
639         addqueue(curarea->win,  REDRAW, 0);
640         window_set_cursor(win, oldcursor);
641         if (curve) MEM_freeN(curve);
642
643         BIF_undo_push("Knife");
644 }
645
646 /* seg_intersect() Determines if and where a mouse trail intersects an EditEdge */
647
648 short seg_intersect(EditEdge *e, CutCurve *c, int len){
649 #define MAXSLOPE 100000
650         short isect=0;
651         float  x11, y11, x12=0, y12=0, x2max, x2min, y2max;
652         float  y2min, dist, lastdist=0, xdiff2, xdiff1;
653         float  m1, b1, m2, b2, x21, x22, y21, y22, xi;
654         float  yi, x1min, x1max, y1max, y1min, perc=0; 
655         float  scr[2], co[4];
656         int  i;
657         
658         /* Get screen coords of verts (v->xs and v->ys clip if off screen */
659         VECCOPY(co, e->v1->co);
660         co[3]= 1.0;
661         Mat4MulVec4fl(G.obedit->obmat, co);
662         project_float(co, scr);
663         x21=scr[0];
664         y21=scr[1];
665         
666         VECCOPY(co, e->v2->co);
667         co[3]= 1.0;
668         Mat4MulVec4fl(G.obedit->obmat, co);
669         project_float(co, scr);
670         x22=scr[0];
671         y22=scr[1];
672         
673         xdiff2=(x22-x21);  
674         if (xdiff2) {
675                 m2=(y22-y21)/xdiff2;
676                 b2= ((x22*y21)-(x21*y22))/xdiff2;
677         }
678         else {
679                 m2=MAXSLOPE;  /* Verticle slope  */
680                 b2=x22;      
681         }
682         for (i=0; i<len; i++){
683                 if (i>0){
684                         x11=x12;
685                         y11=y12;
686                 }
687                 else {
688                         x11=c[i].x;
689                         y11=c[i].y;
690                 }
691                 x12=c[i].x;
692                 y12=c[i].y;
693
694                 /* Perp. Distance from point to line */
695                 if (m2!=MAXSLOPE) dist=(y12-m2*x12-b2);/* /sqrt(m2*m2+1); Only looking for */
696                                                        /* change in sign.  Skip extra math */   
697                 else dist=x22-x12;      
698                 
699                 if (i==0) lastdist=dist;
700                 
701                 /* if dist changes sign, and intersect point in edge's Bound Box*/
702                 if ((lastdist*dist)<=0){
703                         xdiff1=(x12-x11); /* Equation of line between last 2 points */
704                         if (xdiff1){
705                                 m1=(y12-y11)/xdiff1;
706                                 b1= ((x12*y11)-(x11*y12))/xdiff1;
707                         }
708                         else{
709                                 m1=MAXSLOPE;
710                                 b1=x12;
711                         }
712                         x2max=MAX2(x21,x22)+0.001; /* prevent missed edges   */
713                         x2min=MIN2(x21,x22)-0.001; /* due to round off error */
714                         y2max=MAX2(y21,y22)+0.001;
715                         y2min=MIN2(y21,y22)-0.001;
716                         
717                         /* Found an intersect,  calc intersect point */
718                         if (m1==m2){            /* co-incident lines */
719                                                 /* cut at 50% of overlap area*/
720                                 x1max=MAX2(x11, x12);
721                                 x1min=MIN2(x11, x12);
722                                 xi= (MIN2(x2max,x1max)+MAX2(x2min,x1min))/2.0;  
723                                 
724                                 y1max=MAX2(y11, y12);
725                                 y1min=MIN2(y11, y12);
726                                 yi= (MIN2(y2max,y1max)+MAX2(y2min,y1min))/2.0;
727                         }                       
728                         else if (m2==MAXSLOPE){ 
729                                 xi=x22;
730                                 yi=m1*x22+b1;
731                         }
732                         else if (m1==MAXSLOPE){ 
733                                 xi=x12;
734                                 yi=m2*x12+b2;
735                         }
736                         else {
737                                 xi=(b1-b2)/(m2-m1);
738                                 yi=(b1*m2-m1*b2)/(m2-m1);
739                         }
740                         
741                         /* Intersect inside bounding box of edge?*/
742                         if ((xi>=x2min)&&(xi<=x2max)&&(yi<=y2max)&&(yi>=y2min)){
743                                 if ((m2<=1.0)&&(m2>=-1.0)) perc = (xi-x21)/(x22-x21);   
744                                 else perc=(yi-y21)/(y22-y21); /*lower slope more accurate*/
745                                 isect=32768.0*(perc+0.0000153); /* Percentage in 1/32768ths */
746                                 break;
747                         }
748                 }       
749                 lastdist=dist;
750         }
751         return(isect);
752
753
754 void LoopMenu(){ /* Called by KKey */
755
756         short ret;
757         
758         ret=pupmenu("Loop/Cut Menu %t|Loop Cut (CTRL-R)%x2|"
759                                 "Knife (Exact) %x3|Knife (Midpoints)%x4|Knife (Multicut)%x5");
760                                 
761         switch (ret){
762                 case 2:
763                         CutEdgeloop(1);
764                         break;
765                 case 3: 
766                         KnifeSubdivide(KNIFE_EXACT);
767                         break;
768                 case 4:
769                         KnifeSubdivide(KNIFE_MIDPOINT);
770                         break;
771                 case 5:
772                         KnifeSubdivide(KNIFE_MULTICUT);
773                         break;
774         }
775
776 }
777