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