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