source/blender/editors/mesh/editmesh_loop.c

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