source/blender/bmesh/operators/subdivideop.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. 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  * Contributor(s): Joseph Eagar.
  24  *
  25  * ***** END GPL LICENSE BLOCK *****
  26  */
  27
  28 #include "MEM_guardedalloc.h"
  29
  30 #include "BKE_utildefines.h"
  31 #include "BKE_tessmesh.h"
  32
  33 #include "BLI_math.h"
  34 #include "BLI_rand.h"
  35 #include "BLI_ghash.h"
  36 #include "BLI_array.h"
  37 #include "BLI_utildefines.h"
  38
  39 #include "DNA_object_types.h"
  40
  41 #include "ED_mesh.h"
  42
  43 #include "bmesh.h"
  44 #include "bmesh_private.h"
  45
  46 #include "mesh_intern.h"
  47 #include "subdivideop.h"
  48
  49 #include <stdio.h>
  50 #include <stdlib.h>
  51 #include <string.h>
  52 #include <math.h>
  53
  54 /*flags for all elements share a common bitfield space*/
  55 #define SUBD_SPLIT      1
  56
  57 #define EDGE_PERCENT    2
  58
  59 /*I don't think new faces are flagged, currently, but
  60   better safe than sorry.*/
  61 #define FACE_NEW        4
  62 #define FACE_CUSTOMFILL 8
  63 #define ELE_INNER       16
  64 #define ELE_SPLIT       32
  65 #define ELE_CONNECT     64
  66
  67 /*stuff for the flag paramter.  note that
  68   what used to live in "beauty" and
  69   in "seltype" live here.  still have to
  70   convert the beauty flags over, which
  71   is why it starts at 128 (to avoid
  72   collision).*/
  73 #define SELTYPE_INNER   128
  74
  75 /*
  76 NOTE: beauty has been renamed to flag!
  77 */
  78
  79 /*generic subdivision rules:
  80
  81   * two selected edges in a face should make a link
  82     between them.
  83
  84   * one edge should do, what? make pretty topology, or just
  85     split the edge only?
  86 */
  87
  88 #if 0 //misc. code, maps a parametric coordinate to a fractal line
  89 float lastrnd[3], vec2[3] = {0.0f, 0.0f, 0.0f};
  90 int seed = BLI_rand();
  91 int d, i, j, dp, lvl, wid;
  92 float df;
  93
  94 BLI_srandom(seed);
  95
  96 wid = (params->numcuts+2);
  97 dp = perc*wid;
  98 wid /= 2;
  99 d = lvl = 0;
 100 while (1) {
 101         if (d > dp) {
 102                 d -= wid;
 103         } else if (d < dp) {
 104                 d += wid;
 105         } else {
 106                 break;
 107         }
 108
 109
 110         wid = MAX2((wid/2), 1);
 111         lvl++;
 112 }
 113
 114 zero_v3(vec1);
 115 df = 1.0f;
 116 for (i=0; i<lvl; i++, df /= 4.0f) {
 117         int tot = (1<<i);
 118
 119         lastrnd[0] = BLI_drand()-0.5f;
 120         lastrnd[1] = BLI_drand()-0.5f;
 121         lastrnd[2] = BLI_drand()-0.5f;
 122         for (j=0; j<tot; j++) {
 123                 float a, b, rnd[3], rnd2[3];
 124
 125                 rnd[0] = BLI_drand()-0.5f;
 126                 rnd[1] = BLI_drand()-0.5f;
 127                 rnd[2] = BLI_drand()-0.5f;
 128
 129                 a = (float)j*(float)((float)params->numcuts/(float)tot);
 130                 b = (float)(j+1)*(float)((float)params->numcuts/(float)tot);
 131                 if (d >= a && d <= b) {
 132                         interp_v3_v3v3(rnd2, lastrnd, rnd, (((float)d)-a)/(b-a));
 133                         mul_v3_fl(rnd2, df);
 134                         add_v3_v3(vec1, rnd2);
 135                 }
 136
 137                 copy_v3_v3(lastrnd, rnd);
 138         }
 139 }
 140 #endif
 141 /*connects face with smallest len, which I think should always be correct for
 142   edge subdivision*/
 143 static BMEdge *connect_smallest_face(BMesh *bm, BMVert *v1, BMVert *v2, BMFace **nf) {
 144         BMIter iter, iter2;
 145         BMVert *v;
 146         BMLoop *nl;
 147         BMFace *face, *curf = NULL;
 148
 149         /*this isn't the best thing in the world.  it doesn't handle cases where there's
 150           multiple faces yet.  that might require a convexity test to figure out which
 151           face is "best," and who knows what for non-manifold conditions.*/
 152         for (face = BMIter_New(&iter, bm, BM_FACES_OF_VERT, v1); face; face=BMIter_Step(&iter)) {
 153                 for (v=BMIter_New(&iter2, bm, BM_VERTS_OF_FACE, face); v; v=BMIter_Step(&iter2)) {
 154                         if (v == v2) {
 155                                 if (!curf || face->len < curf->len) curf = face;
 156                         }
 157                 }
 158         }
 159
 160         if (curf) {
 161                 face = BM_Split_Face(bm, curf, v1, v2, &nl, NULL);
 162
 163                 if (nf) *nf = face;
 164                 return nl ? nl->e : NULL;
 165         }
 166
 167         return NULL;
 168 }
 169 /* calculates offset for co, based on fractal, sphere or smooth settings  */
 170 static void alter_co(BMesh *bm, BMVert *v, BMEdge *UNUSED(origed), subdparams *params, float perc,
 171                      BMVert *vsta, BMVert *vend)
 172 {
 173         float vec1[3], fac;
 174         float *co=NULL, *origco=NULL;
 175         int i, totlayer = CustomData_number_of_layers(&bm->vdata, CD_SHAPEKEY);
 176
 177         BM_Vert_UpdateAllNormals(bm, v);
 178
 179         origco = CustomData_bmesh_get_n(&bm->vdata, v->head.data, CD_SHAPEKEY, params->origkey);
 180         sub_v3_v3v3(vec1, origco, v->co);
 181
 182         for (i=0; i<totlayer; i++) {
 183                 co = CustomData_bmesh_get_n(&bm->vdata, v->head.data, CD_SHAPEKEY, i);
 184                 sub_v3_v3(co, vec1);
 185         }
 186
 187         for (i=0; i<totlayer; i++) {
 188                 co = CustomData_bmesh_get_n(&bm->vdata, v->head.data, CD_SHAPEKEY, i);
 189
 190                 if(params->beauty & B_SMOOTH) {
 191                         /* we calculate an offset vector vec1[], to be added to *co */
 192                         float len, fac, nor[3], nor1[3], nor2[3], smooth=params->smooth;
 193
 194                         sub_v3_v3v3(nor, vsta->co, vend->co);
 195                         len= 0.5f*normalize_v3(nor);
 196
 197                         copy_v3_v3(nor1, vsta->no);
 198                         copy_v3_v3(nor2, vend->no);
 199
 200                         /* cosine angle */
 201                         fac= nor[0]*nor1[0] + nor[1]*nor1[1] + nor[2]*nor1[2] ;
 202
 203                         vec1[0]= fac*nor1[0];
 204                         vec1[1]= fac*nor1[1];
 205                         vec1[2]= fac*nor1[2];
 206
 207                         /* cosine angle */
 208                         fac= -nor[0]*nor2[0] - nor[1]*nor2[1] - nor[2]*nor2[2] ;
 209
 210                         vec1[0]+= fac*nor2[0];
 211                         vec1[1]+= fac*nor2[1];
 212                         vec1[2]+= fac*nor2[2];
 213
 214                         /* falloff for multi subdivide */
 215                         smooth *= sqrt(fabs(1.0f - 2.0f*fabs(perc)));
 216
 217                         vec1[0]*= smooth*len;
 218                         vec1[1]*= smooth*len;
 219                         vec1[2]*= smooth*len;
 220
 221                         co[0] += vec1[0];
 222                         co[1] += vec1[1];
 223                         co[2] += vec1[2];
 224                 }
 225                 else if(params->beauty & B_SPHERE) { /* subdivide sphere */
 226                         normalize_v3(co);
 227                         co[0]*= params->smooth;
 228                         co[1]*= params->smooth;
 229                         co[2]*= params->smooth;
 230                 }
 231
 232                 if(params->beauty & B_FRACTAL) {
 233                         float len = len_v3v3(vsta->co, vend->co);
 234                         float vec2[3] = {0.0f, 0.0f, 0.0f}, co2[3];
 235
 236                         fac= params->fractal*len;
 237
 238                         add_v3_v3(vec2, vsta->no);
 239                         add_v3_v3(vec2, vend->no);
 240                         mul_v3_fl(vec2, 0.5f);
 241
 242                         add_v3_v3v3(co2, v->co, params->off);
 243                         vec1[0] = fac*(BLI_gTurbulence(1.0, co2[0], co2[1], co2[2], 15, 0, 1)-0.5f);
 244                         vec1[1] = fac*(BLI_gTurbulence(1.0, co2[0], co2[1], co2[2], 15, 0, 1)-0.5f);
 245                         vec1[2] = fac*(BLI_gTurbulence(1.0, co2[0], co2[1], co2[2], 15, 0, 1)-0.5f);
 246
 247                         mul_v3_v3(vec2, vec1);
 248
 249                         /*add displacement*/
 250                         add_v3_v3v3(co, co, vec2);
 251                 }
 252         }
 253 }
 254
 255 /* assumes in the edge is the correct interpolated vertices already */
 256 /* percent defines the interpolation, rad and flag are for special options */
 257 /* results in new vertex with correct coordinate, vertex normal and weight group info */
 258 static BMVert *bm_subdivide_edge_addvert(BMesh *bm, BMEdge *edge,BMEdge *oedge,
 259                                         subdparams *params, float percent,
 260                                         float percent2,
 261                                         BMEdge **out,BMVert *vsta,BMVert *vend)
 262 {
 263         BMVert *ev;
 264
 265         ev = BM_Split_Edge(bm, edge->v1, edge, out, percent);
 266
 267         BMO_SetFlag(bm, ev, ELE_INNER);
 268
 269         /* offset for smooth or sphere or fractal */
 270         alter_co(bm, ev, oedge, params, percent2, vsta, vend);
 271
 272 #if 0 //TODO
 273         /* clip if needed by mirror modifier */
 274         if (edge->v1->f2) {
 275                 if ( edge->v1->f2 & edge->v2->f2 & 1) {
 276                         co[0]= 0.0f;
 277                 }
 278                 if ( edge->v1->f2 & edge->v2->f2 & 2) {
 279                         co[1]= 0.0f;
 280                 }
 281                 if ( edge->v1->f2 & edge->v2->f2 & 4) {
 282                         co[2]= 0.0f;
 283                 }
 284         }
 285 #endif
 286
 287         return ev;
 288 }
 289
 290 static BMVert *subdivideedgenum(BMesh *bm, BMEdge *edge, BMEdge *oedge,
 291                                 int curpoint, int totpoint, subdparams *params,
 292                                 BMEdge **newe, BMVert *vsta, BMVert *vend)
 293 {
 294         BMVert *ev;
 295         float percent, percent2 = 0.0f;
 296
 297         if (BMO_TestFlag(bm, edge, EDGE_PERCENT) && totpoint == 1)
 298                 percent = BMO_Get_MapFloat(bm, params->op,
 299                                         "edgepercents", edge);
 300         else {
 301                 percent= 1.0f/(float)(totpoint+1-curpoint);
 302                 percent2 = (float)(curpoint+1) / (float)(totpoint+1);
 303
 304         }
 305
 306         ev= bm_subdivide_edge_addvert(bm, edge, oedge, params, percent,
 307                                       percent2, newe, vsta, vend);
 308         return ev;
 309 }
 310
 311 static void bm_subdivide_multicut(BMesh *bm, BMEdge *edge, subdparams *params,
 312                                   BMVert *vsta, BMVert *vend) {
 313         BMEdge *eed = edge, *newe, temp = *edge;
 314         BMVert *v, ov1=*edge->v1, ov2=*edge->v2, *v1=edge->v1, *v2=edge->v2;
 315         int i, numcuts = params->numcuts;
 316
 317         temp.v1 = &ov1;
 318         temp.v2 = &ov2;
 319
 320         for(i=0;i<numcuts;i++) {
 321                 v = subdivideedgenum(bm, eed, &temp, i, params->numcuts, params,
 322                                      &newe, vsta, vend);
 323
 324                 BMO_SetFlag(bm, v, SUBD_SPLIT);
 325                 BMO_SetFlag(bm, eed, SUBD_SPLIT);
 326                 BMO_SetFlag(bm, newe, SUBD_SPLIT);
 327
 328                 BMO_SetFlag(bm, v, ELE_SPLIT);
 329                 BMO_SetFlag(bm, eed, ELE_SPLIT);
 330                 BMO_SetFlag(bm, newe, SUBD_SPLIT);
 331
 332                 CHECK_ELEMENT(bm, v);
 333                 if (v->e) CHECK_ELEMENT(bm, v->e);
 334                 if (v->e && v->e->l) CHECK_ELEMENT(bm, v->e->l->f);
 335         }
 336
 337         alter_co(bm, v1, &temp, params, 0, &ov1, &ov2);
 338         alter_co(bm, v2, &temp, params, 1.0, &ov1, &ov2);
 339 }
 340
 341 /*note: the patterns are rotated as necassary to
 342   match the input geometry.  they're based on the
 343   pre-split state of the  face*/
 344
 345 /*
 346
 347 v3---------v2
 348 |          |
 349 |          |
 350 |          |
 351 |          |
 352 v4---v0---v1
 353
 354 */
 355 static void quad_1edge_split(BMesh *bm, BMFace *UNUSED(face),
 356                           BMVert **verts, subdparams *params) {
 357         BMFace *nf;
 358         int i, add, numcuts = params->numcuts;
 359
 360         /*if it's odd, the middle face is a quad, otherwise it's a triangle*/
 361         if (numcuts % 2==0) {
 362                 add = 2;
 363                 for (i=0; i<numcuts; i++) {
 364                         if (i == numcuts/2) add -= 1;
 365                         connect_smallest_face(bm, verts[i], verts[numcuts+add],
 366                                            &nf);
 367                 }
 368         } else {
 369                 add = 2;
 370                 for (i=0; i<numcuts; i++) {
 371                         connect_smallest_face(bm, verts[i], verts[numcuts+add],
 372                                            &nf);
 373                         if (i == numcuts/2) {
 374                                 add -= 1;
 375                                 connect_smallest_face(bm, verts[i],
 376                                                    verts[numcuts+add],
 377                                                    &nf);
 378                         }
 379                 }
 380
 381         }
 382 }
 383
 384 static subdpattern quad_1edge = {
 385         {1, 0, 0, 0},
 386         quad_1edge_split,
 387         4,
 388 };
 389
 390
 391 /*
 392 v6--------v5
 393 |          |
 394 |          |v4s
 395 |          |v3s
 396 |   s  s   |
 397 v7-v0--v1-v2
 398
 399 */
 400 static void quad_2edge_split_path(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
 401                           subdparams *params)
 402 {
 403         BMFace *nf;
 404         int i, numcuts = params->numcuts;
 405
 406         for (i=0; i<numcuts; i++) {
 407                 connect_smallest_face(bm, verts[i], verts[numcuts+(numcuts-i)],
 408                                    &nf);
 409         }
 410         connect_smallest_face(bm, verts[numcuts*2+3], verts[numcuts*2+1], &nf);
 411 }
 412
 413 static subdpattern quad_2edge_path = {
 414         {1, 1, 0, 0},
 415         quad_2edge_split_path,
 416         4,
 417 };
 418
 419 /*
 420 v6--------v5
 421 |          |
 422 |          |v4s
 423 |          |v3s
 424 |   s  s   |
 425 v7-v0--v1-v2
 426
 427 */
 428 static void quad_2edge_split_innervert(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
 429                           subdparams *params)
 430 {
 431         BMFace *nf;
 432         BMVert *v, *lastv;
 433         BMEdge *e, *ne, olde;
 434         int i, numcuts = params->numcuts;
 435
 436         lastv = verts[numcuts];
 437
 438         for (i=numcuts-1; i>=0; i--) {
 439                 e = connect_smallest_face(bm, verts[i], verts[numcuts+(numcuts-i)],
 440                                    &nf);
 441
 442                 olde = *e;
 443                 v = bm_subdivide_edge_addvert(bm, e, &olde, params, 0.5f, 0.5f, &ne, e->v1, e->v2);
 444
 445                 if (i != numcuts-1)
 446                         connect_smallest_face(bm, lastv, v, &nf);
 447
 448                 lastv = v;
 449         }
 450
 451         connect_smallest_face(bm, lastv, verts[numcuts*2+2], &nf);
 452 }
 453
 454 static subdpattern quad_2edge_innervert = {
 455         {1, 1, 0, 0},
 456         quad_2edge_split_innervert,
 457         4,
 458 };
 459
 460 /*
 461 v6--------v5
 462 |          |
 463 |          |v4s
 464 |          |v3s
 465 |   s  s   |
 466 v7-v0--v1-v2
 467
 468 */
 469 static void quad_2edge_split_fan(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
 470                           subdparams *params)
 471 {
 472         BMFace *nf;
 473         // BMVert *v;
 474         BMVert *lastv;
 475         // BMEdge *e, *ne;
 476         int i, numcuts = params->numcuts;
 477
 478         lastv = verts[2];
 479
 480         for (i=0; i<numcuts; i++) {
 481                 connect_smallest_face(bm, verts[i], verts[numcuts*2+2], &nf);
 482                 connect_smallest_face(bm, verts[numcuts+(numcuts-i)],
 483                         verts[numcuts*2+2], &nf);
 484         }
 485 }
 486
 487 static subdpattern quad_2edge_fan = {
 488         {1, 1, 0, 0},
 489         quad_2edge_split_fan,
 490         4,
 491 };
 492
 493 /*  s   s
 494 v8--v7--v6-v5
 495 |          |
 496 |          v4 s
 497 |          |
 498 |          v3 s
 499 |   s  s   |
 500 v9-v0--v1-v2
 501
 502 */
 503 static void quad_3edge_split(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
 504                           subdparams *params)
 505 {
 506         BMFace *nf;
 507         int i, add=0, numcuts = params->numcuts;
 508
 509         for (i=0; i<numcuts; i++) {
 510                 if (i == numcuts/2) {
 511                         if (numcuts % 2 != 0) {
 512                                 connect_smallest_face(bm, verts[numcuts-i-1+add],
 513                                                  verts[i+numcuts+1], &nf);
 514                         }
 515                         add = numcuts*2+2;
 516                 }
 517                 connect_smallest_face(bm, verts[numcuts-i-1+add],
 518                                      verts[i+numcuts+1], &nf);
 519         }
 520
 521         for (i=0; i<numcuts/2+1; i++) {
 522                 connect_smallest_face(bm, verts[i],verts[(numcuts-i)+numcuts*2+1],
 523                                    &nf);
 524         }
 525 }
 526
 527 static subdpattern quad_3edge = {
 528         {1, 1, 1, 0},
 529         quad_3edge_split,
 530         4,
 531 };
 532
 533 /*
 534
 535            v8--v7-v6--v5
 536            |     s    |
 537            |v9 s     s|v4
 538 first line |          |   last line
 539            |v10s s   s|v3
 540            v11-v0--v1-v2
 541
 542            it goes from bottom up
 543 */
 544 static void quad_4edge_subdivide(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
 545                           subdparams *params)
 546 {
 547         BMFace *nf;
 548         BMVert *v, *v1, *v2;
 549         BMEdge *e, *ne, temp;
 550         BMVert **lines;
 551         int numcuts = params->numcuts;
 552         int i, j, a, b, s=numcuts+2 /* , totv=numcuts*4+4 */;
 553
 554         lines = MEM_callocN(sizeof(BMVert*)*(numcuts+2)*(numcuts+2),
 555                                      "q_4edge_split");
 556         /*build a 2-dimensional array of verts,
 557           containing every vert (and all new ones)
 558           in the face.*/
 559
 560         /*first line*/
 561         for (i=0; i<numcuts+2; i++) {
 562                 lines[i] = verts[numcuts*3+2+(numcuts-i+1)];
 563         }
 564
 565         /*last line*/
 566         for (i=0; i<numcuts+2; i++) {
 567                 lines[(s-1)*s+i] = verts[numcuts+i];
 568         }
 569
 570         /*first and last members of middle lines*/
 571         for (i=0; i<numcuts; i++) {
 572                 a = i;
 573                 b = numcuts + 1 + numcuts + 1 + (numcuts - i - 1);
 574
 575                 e = connect_smallest_face(bm, verts[a], verts[b], &nf);
 576                 if (!e)
 577                         continue;
 578
 579                 BMO_SetFlag(bm, e, ELE_INNER);
 580                 BMO_SetFlag(bm, nf, ELE_INNER);
 581
 582
 583                 v1 = lines[(i+1)*s] = verts[a];
 584                 v2 = lines[(i+1)*s + s-1] = verts[b];
 585
 586                 temp = *e;
 587                 for (a=0; a<numcuts; a++) {
 588                         v = subdivideedgenum(bm, e, &temp, a, numcuts, params, &ne,
 589                                             v1, v2);
 590                         if (!v)
 591                                 bmesh_error();
 592
 593                         BMO_SetFlag(bm, ne, ELE_INNER);
 594                         lines[(i+1)*s+a+1] = v;
 595                 }
 596         }
 597
 598         for (i=1; i<numcuts+2; i++) {
 599                 for (j=1; j<numcuts+1; j++) {
 600                         a = i*s + j;
 601                         b = (i-1)*s + j;
 602                         e = connect_smallest_face(bm, lines[a], lines[b], &nf);
 603                         if (!e)
 604                                 continue;
 605
 606                         BMO_SetFlag(bm, e, ELE_INNER);
 607                         BMO_SetFlag(bm, nf, ELE_INNER);
 608                 }
 609         }
 610
 611         MEM_freeN(lines);
 612 }
 613
 614 /*    v3
 615      / \
 616     /   \
 617    /     \
 618   /       \
 619  /         \
 620 v4--v0--v1--v2
 621     s    s
 622 */
 623 static void tri_1edge_split(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
 624                           subdparams *params)
 625 {
 626         BMFace *nf;
 627         int i, numcuts = params->numcuts;
 628
 629         for (i=0; i<numcuts; i++) {
 630                 connect_smallest_face(bm, verts[i], verts[numcuts+1], &nf);
 631         }
 632 }
 633
 634 static subdpattern tri_1edge = {
 635         {1, 0, 0},
 636         tri_1edge_split,
 637         3,
 638 };
 639
 640 /*     v5
 641       / \
 642  s v6/---\ v4 s
 643     / \ / \
 644 sv7/---v---\ v3 s
 645   /  \/  \/ \
 646  v8--v0--v1--v2
 647     s    s
 648 */
 649 static void tri_3edge_subdivide(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
 650                           subdparams *params)
 651 {
 652         BMFace *nf;
 653         BMEdge *e, *ne, temp;
 654         BMVert ***lines, *v, ov1, ov2;
 655         void *stackarr[1];
 656         int i, j, a, b, numcuts = params->numcuts;
 657
 658         /*number of verts in each line*/
 659         lines = MEM_callocN(sizeof(void*)*(numcuts+2), "triangle vert table");
 660
 661         lines[0] = (BMVert**) stackarr;
 662         lines[0][0] = verts[numcuts*2+1];
 663
 664         lines[1+numcuts] = MEM_callocN(sizeof(void*)*(numcuts+2),
 665                                        "triangle vert table 2");
 666         for (i=0; i<numcuts; i++) {
 667                 lines[1+numcuts][1+i] = verts[i];
 668         }
 669         lines[1+numcuts][0] = verts[numcuts*3+2];
 670         lines[1+numcuts][1+numcuts] = verts[numcuts];
 671
 672         for (i=0; i<numcuts; i++) {
 673                 lines[i+1] = MEM_callocN(sizeof(void*)*(2+i),
 674                                        "triangle vert table row");
 675                 a = numcuts*2 + 2 + i;
 676                 b = numcuts + numcuts - i;
 677                 e = connect_smallest_face(bm, verts[a], verts[b], &nf);
 678                 if (!e) goto cleanup;
 679
 680                 BMO_SetFlag(bm, e, ELE_INNER);
 681                 BMO_SetFlag(bm, nf, ELE_INNER);
 682
 683                 lines[i+1][0] = verts[a];
 684                 lines[i+1][1+i] = verts[b];
 685
 686                 temp = *e;
 687                 ov1 = *verts[a];
 688                 ov2 = *verts[b];
 689                 temp.v1 = &ov1;
 690                 temp.v2 = &ov2;
 691                 for (j=0; j<i; j++) {
 692                         v = subdivideedgenum(bm, e, &temp, j, i, params, &ne,
 693                                              verts[a], verts[b]);
 694                         lines[i+1][j+1] = v;
 695
 696                         BMO_SetFlag(bm, ne, ELE_INNER);
 697                 }
 698         }
 699
 700
 701 /*     v5
 702       / \
 703  s v6/---\ v4 s
 704     / \ / \
 705 sv7/---v---\ v3 s
 706   /  \/  \/ \
 707  v8--v0--v1--v2
 708     s    s
 709 */
 710         for (i=1; i<numcuts+1; i++) {
 711                 for (j=0; j<i; j++) {
 712                         e= connect_smallest_face(bm, lines[i][j], lines[i+1][j+1],
 713                                            &nf);
 714
 715                         BMO_SetFlag(bm, e, ELE_INNER);
 716                         BMO_SetFlag(bm, nf, ELE_INNER);
 717
 718                         e= connect_smallest_face(bm,lines[i][j+1],lines[i+1][j+1],
 719                                            &nf);
 720
 721                         BMO_SetFlag(bm, e, ELE_INNER);
 722                         BMO_SetFlag(bm, nf, ELE_INNER);
 723                 }
 724         }
 725
 726 cleanup:
 727         for (i=1; i<numcuts+2; i++) {
 728                 if (lines[i]) MEM_freeN(lines[i]);
 729         }
 730
 731         MEM_freeN(lines);
 732 }
 733
 734 static subdpattern tri_3edge = {
 735         {1, 1, 1},
 736         tri_3edge_subdivide,
 737         3,
 738 };
 739
 740
 741 static subdpattern quad_4edge = {
 742         {1, 1, 1, 1},
 743         quad_4edge_subdivide,
 744         4,
 745 };
 746
 747 static subdpattern *patterns[] = {
 748         NULL, //quad single edge pattern is inserted here
 749         NULL, //quad corner vert pattern is inserted here
 750         NULL, //tri single edge pattern is inserted here
 751         NULL,
 752         &quad_3edge,
 753         NULL,
 754 };
 755
 756 #define PLEN    (sizeof(patterns) / sizeof(void*))
 757
 758 typedef struct subd_facedata {
 759         BMVert *start; subdpattern *pat;
 760         int totedgesel; //only used if pat was NULL, e.g. no pattern was found
 761         BMFace *face;
 762 } subd_facedata;
 763
 764 void esubdivide_exec(BMesh *bmesh, BMOperator *op)
 765 {
 766         BMOpSlot *einput;
 767         subdpattern *pat;
 768         subdparams params;
 769         subd_facedata *facedata = NULL;
 770         BMIter viter, fiter, liter;
 771         BMVert *v, **verts = NULL;
 772         BMEdge *edge, **edges = NULL;
 773         BMLoop *nl, *l, **splits = NULL, **loops = NULL;
 774         BMFace *face;
 775         BLI_array_declare(splits);
 776         BLI_array_declare(loops);
 777         BLI_array_declare(facedata);
 778         BLI_array_declare(edges);
 779         BLI_array_declare(verts);
 780         float smooth, fractal;
 781         int beauty, cornertype, singleedge, gridfill;
 782         int skey, seed, i, j, matched, a, b, numcuts, totesel;
 783
 784         BMO_Flag_Buffer(bmesh, op, "edges", SUBD_SPLIT, BM_EDGE);
 785
 786         numcuts = BMO_Get_Int(op, "numcuts");
 787         seed = BMO_Get_Int(op, "seed");
 788         smooth = BMO_Get_Float(op, "smooth");
 789         fractal = BMO_Get_Float(op, "fractal");
 790         beauty = BMO_Get_Int(op, "beauty");
 791         cornertype = BMO_Get_Int(op, "quadcornertype");
 792         singleedge = BMO_Get_Int(op, "singleedge");
 793         gridfill = BMO_Get_Int(op, "gridfill");
 794
 795         BLI_srandom(seed);
 796
 797         patterns[1] = NULL;
 798         //straight cut is patterns[1] == NULL
 799         switch (cornertype) {
 800                 case SUBD_PATH:
 801                         patterns[1] = &quad_2edge_path;
 802                         break;
 803                 case SUBD_INNERVERT:
 804                         patterns[1] = &quad_2edge_innervert;
 805                         break;
 806                 case SUBD_FAN:
 807                         patterns[1] = &quad_2edge_fan;
 808                         break;
 809         }
 810
 811         if (singleedge) {
 812                 patterns[0] = &quad_1edge;
 813                 patterns[2] = &tri_1edge;
 814         } else {
 815                 patterns[0] = NULL;
 816                 patterns[2] = NULL;
 817         }
 818
 819         if (gridfill) {
 820                 patterns[3] = &quad_4edge;
 821                 patterns[5] = &tri_3edge;
 822         } else {
 823                 patterns[3] = NULL;
 824                 patterns[5] = NULL;
 825         }
 826
 827         /*add a temporary shapekey layer to store displacements on current geometry*/
 828         BM_add_data_layer(bmesh, &bmesh->vdata, CD_SHAPEKEY);
 829         skey = CustomData_number_of_layers(&bmesh->vdata, CD_SHAPEKEY)-1;
 830
 831         BM_ITER(v, &viter, bmesh, BM_VERTS_OF_MESH, NULL) {
 832                 float *co = CustomData_bmesh_get_n(&bmesh->vdata, v->head.data, CD_SHAPEKEY, skey);
 833                 copy_v3_v3(co, v->co);
 834         }
 835
 836         /*first go through and tag edges*/
 837         BMO_Flag_To_Slot(bmesh, op, "edges",
 838                  SUBD_SPLIT, BM_EDGE);
 839
 840         params.numcuts = numcuts;
 841         params.op = op;
 842         params.smooth = smooth;
 843         params.seed = seed;
 844         params.fractal = fractal;
 845         params.beauty = beauty;
 846         params.origkey = skey;
 847         params.off[0] = BLI_drand()*200.0f;
 848         params.off[1] = BLI_drand()*200.0f;
 849         params.off[2] = BLI_drand()*200.0f;
 850
 851         BMO_Mapping_To_Flag(bmesh, op, "custompatterns",
 852                             FACE_CUSTOMFILL);
 853
 854         BMO_Mapping_To_Flag(bmesh, op, "edgepercents",
 855                             EDGE_PERCENT);
 856
 857         for (face=BMIter_New(&fiter, bmesh, BM_FACES_OF_MESH, NULL);
 858              face; face=BMIter_Step(&fiter)) {
 859                 BMEdge *e1 = NULL, *e2 = NULL;
 860                 float vec1[3], vec2[3];
 861
 862                 /*figure out which pattern to use*/
 863
 864                 BLI_array_empty(edges);
 865                 BLI_array_empty(verts);
 866                 matched = 0;
 867
 868                 i = 0;
 869                 totesel = 0;
 870                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
 871                      nl; nl=BMIter_Step(&liter)) {
 872                         BLI_array_growone(edges);
 873                         BLI_array_growone(verts);
 874                         edges[i] = nl->e;
 875                         verts[i] = nl->v;
 876
 877                         if (BMO_TestFlag(bmesh, edges[i], SUBD_SPLIT)) {
 878                                 if (!e1) e1 = edges[i];
 879                                 else e2 = edges[i];
 880
 881                                 totesel++;
 882                         }
 883
 884                         i++;
 885                 }
 886
 887                 /*make sure the two edges have a valid angle to each other*/
 888                 if (totesel == 2 && (e1->v1 == e2->v1 || e1->v1 == e2->v2
 889                                      || e1->v2 == e2->v1 || e1->v2 == e2->v1)) {
 890                         float angle;
 891
 892                         sub_v3_v3v3(vec1, e1->v2->co, e1->v1->co);
 893                         sub_v3_v3v3(vec2, e2->v2->co, e2->v1->co);
 894                         normalize_v3(vec1);
 895                         normalize_v3(vec2);
 896
 897                         angle = INPR(vec1, vec2);
 898                         angle = ABS(angle);
 899                         if (ABS(angle-1.0) < 0.01)
 900                                 totesel = 0;
 901                 }
 902
 903                 if (BMO_TestFlag(bmesh, face, FACE_CUSTOMFILL)) {
 904                         pat = BMO_Get_MapData(bmesh, op,
 905                                     "custompatterns", face);
 906                         for (i=0; i<pat->len; i++) {
 907                                 matched = 1;
 908                                 for (j=0; j<pat->len; j++) {
 909                                         a = (j + i) % pat->len;
 910                                         if ((!!BMO_TestFlag(bmesh, edges[a], SUBD_SPLIT))
 911                                                 != (!!pat->seledges[j])) {
 912                                                         matched = 0;
 913                                                         break;
 914                                         }
 915                                 }
 916                                 if (matched) {
 917                                         BLI_array_growone(facedata);
 918                                         b = BLI_array_count(facedata)-1;
 919                                         facedata[b].pat = pat;
 920                                         facedata[b].start = verts[i];
 921                                         facedata[b].face = face;
 922                                         facedata[b].totedgesel = totesel;
 923                                         BMO_SetFlag(bmesh, face, SUBD_SPLIT);
 924                                         break;
 925                                 }
 926                         }
 927
 928                         /*obvously don't test for other patterns matching*/
 929                         continue;
 930                 }
 931
 932                 for (i=0; i<PLEN; i++) {
 933                         pat = patterns[i];
 934                         if (!pat) continue;
 935
 936                         if (pat->len == face->len) {
 937                                 for (a=0; a<pat->len; a++) {
 938                                         matched = 1;
 939                                         for (b=0; b<pat->len; b++) {
 940                                                 j = (b + a) % pat->len;
 941                                                 if ((!!BMO_TestFlag(bmesh, edges[j], SUBD_SPLIT))
 942                                                         != (!!pat->seledges[b])) {
 943                                                                 matched = 0;
 944                                                                 break;
 945                                                 }
 946                                         }
 947                                         if (matched) break;
 948                                 }
 949                                 if (matched) {
 950                                         BLI_array_growone(facedata);
 951                                         j = BLI_array_count(facedata) - 1;
 952
 953                                         BMO_SetFlag(bmesh, face, SUBD_SPLIT);
 954
 955                                         facedata[j].pat = pat;
 956                                         facedata[j].start = verts[a];
 957                                         facedata[j].face = face;
 958                                         facedata[j].totedgesel = totesel;
 959                                         break;
 960                                 }
 961                         }
 962
 963                 }
 964
 965                 if (!matched && totesel) {
 966                         BLI_array_growone(facedata);
 967                         j = BLI_array_count(facedata) - 1;
 968
 969                         BMO_SetFlag(bmesh, face, SUBD_SPLIT);
 970                         facedata[j].totedgesel = totesel;
 971                         facedata[j].face = face;
 972                 }
 973         }
 974
 975         einput = BMO_GetSlot(op, "edges");
 976
 977         /*go through and split edges*/
 978         for (i=0; i<einput->len; i++) {
 979                 edge = ((BMEdge**)einput->data.p)[i];
 980                 bm_subdivide_multicut(bmesh, edge, &params, edge->v1, edge->v2);
 981         }
 982
 983         i = 0;
 984         for (i=0; i<BLI_array_count(facedata); i++) {
 985                 face = facedata[i].face;
 986
 987                 /*figure out which pattern to use*/
 988                 BLI_array_empty(verts);
 989
 990                 pat = facedata[i].pat;
 991
 992                 if (!pat && facedata[i].totedgesel == 2) {
 993                         int vlen;
 994
 995                         /*ok, no pattern.  we still may be able to do something.*/
 996                         BLI_array_empty(loops);
 997                         BLI_array_empty(splits);
 998
 999                         /*for case of two edges, connecting them shouldn't be too hard*/
1000                         BM_ITER(l, &liter, bmesh, BM_LOOPS_OF_FACE, face) {
1001                                 BLI_array_growone(loops);
1002                                 loops[BLI_array_count(loops)-1] = l;
1003                         }
1004
1005                         vlen = BLI_array_count(loops);
1006
1007                         /*find the boundary of one of the split edges*/
1008                         for (a=1; a<vlen; a++) {
1009                                 if (!BMO_TestFlag(bmesh, loops[a-1]->v, ELE_INNER)
1010                                     && BMO_TestFlag(bmesh, loops[a]->v, ELE_INNER))
1011                                         break;
1012                         }
1013
1014                         if (BMO_TestFlag(bmesh, loops[(a+numcuts+1)%vlen]->v, ELE_INNER)) {
1015                                 b = (a+numcuts+1)%vlen;
1016                         } else {
1017                                 /*find the boundary of the other edge.*/
1018                                 for (j=0; j<vlen; j++) {
1019                                         b = (j + a + numcuts + 1) % vlen;
1020                                         if (!BMO_TestFlag(bmesh, loops[b==0 ? vlen-1 : b-1]->v, ELE_INNER)
1021                                             && BMO_TestFlag(bmesh, loops[b]->v, ELE_INNER))
1022                                                 break;
1023                                 }
1024                         }
1025
1026                         b += numcuts - 1;
1027
1028                         for (j=0; j<numcuts; j++) {
1029                                 BLI_array_growone(splits);
1030                                 splits[BLI_array_count(splits)-1] = loops[a];
1031
1032                                 BLI_array_growone(splits);
1033                                 splits[BLI_array_count(splits)-1] = loops[b];
1034
1035                                 b = (b-1) % vlen;
1036                                 a = (a+1) % vlen;
1037                         }
1038
1039                         //BM_LegalSplits(bmesh, face, splits, BLI_array_count(splits)/2);
1040
1041                         for (j=0; j<BLI_array_count(splits)/2; j++) {
1042                                 if (splits[j*2]) {
1043                                         BMFace *nf;
1044
1045                                         nf = BM_Split_Face(bmesh, face, splits[j*2]->v, splits[j*2+1]->v, &nl, NULL);
1046                                 }
1047                         }
1048
1049                         continue;
1050                 } else if (!pat) {
1051                         continue;
1052                 }
1053
1054                 j = a = 0;
1055                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
1056                      nl; nl=BMIter_Step(&liter)) {
1057                         if (nl->v == facedata[i].start) {
1058                                 a = j+1;
1059                                 break;
1060                         }
1061                         j++;
1062                 }
1063
1064                 for (j=0; j<face->len; j++) {
1065                         BLI_array_growone(verts);
1066                 }
1067
1068                 j = 0;
1069                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
1070                      nl; nl=BMIter_Step(&liter)) {
1071                         b = (j-a+face->len) % face->len;
1072                         verts[b] = nl->v;
1073                         j += 1;
1074                 }
1075
1076                 CHECK_ELEMENT(bmesh, face);
1077                 pat->connectexec(bmesh, face, verts, &params);
1078         }
1079
1080         /*copy original-geometry displacements to current coordinates*/
1081         BM_ITER(v, &viter, bmesh, BM_VERTS_OF_MESH, NULL) {
1082                 float *co = CustomData_bmesh_get_n(&bmesh->vdata, v->head.data, CD_SHAPEKEY, skey);
1083                 copy_v3_v3(v->co, co);
1084         }
1085
1086         BM_free_data_layer_n(bmesh, &bmesh->vdata, CD_SHAPEKEY, skey);
1087
1088         if (facedata) BLI_array_free(facedata);
1089         if (edges) BLI_array_free(edges);
1090         if (verts) BLI_array_free(verts);
1091         BLI_array_free(splits);
1092         BLI_array_free(loops);
1093
1094         BMO_Flag_To_Slot(bmesh, op, "outinner",
1095                          ELE_INNER, BM_ALL);
1096         BMO_Flag_To_Slot(bmesh, op, "outsplit",
1097                          ELE_SPLIT, BM_ALL);
1098
1099         BMO_Flag_To_Slot(bmesh, op, "geomout",
1100                          ELE_INNER|ELE_SPLIT|SUBD_SPLIT, BM_ALL);
1101 }
1102
1103 /*editmesh-emulating function*/
1104 void BM_esubdivideflag(Object *UNUSED(obedit), BMesh *bm, int flag, float smooth,
1105                float fractal, int beauty, int numcuts,
1106                int seltype, int cornertype, int singleedge,
1107                int gridfill, int seed)
1108 {
1109         BMOperator op;
1110
1111         BMO_InitOpf(bm, &op, "esubd edges=%he smooth=%f fractal=%f "
1112                              "beauty=%d numcuts=%d quadcornertype=%d singleedge=%d "
1113                              "gridfill=%d seed=%d",
1114                              flag, smooth, fractal, beauty, numcuts,
1115                              cornertype, singleedge, gridfill, seed);
1116
1117         BMO_Exec_Op(bm, &op);
1118
1119         if (seltype == SUBDIV_SELECT_INNER) {
1120                 BMOIter iter;
1121                 BMHeader *ele;
1122                 // int i;
1123
1124                 ele = BMO_IterNew(&iter, bm, &op, "outinner", BM_EDGE|BM_VERT);
1125                 for (; ele; ele=BMO_IterStep(&iter)) {
1126                         BM_Select(bm, ele, 1);
1127                 }
1128         } else if (seltype == SUBDIV_SELECT_LOOPCUT) {
1129                 BMOIter iter;
1130                 BMHeader *ele;
1131                 // int i;
1132
1133                 /*deselect input*/
1134                 BM_clear_flag_all(bm, BM_SELECT);
1135
1136                 ele = BMO_IterNew(&iter, bm, &op, "outinner", BM_EDGE|BM_VERT);
1137                 for (; ele; ele=BMO_IterStep(&iter)) {
1138                         BM_Select(bm, ele, 1);
1139
1140                         if (ele->type == BM_VERT) {
1141                                 BMEdge *e;
1142                                 BMIter eiter;
1143
1144                                 BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, ele) {
1145                                         if (!BM_TestHFlag(e, BM_SELECT) && BM_TestHFlag(e->v1, BM_SELECT)
1146                                                                                                         && BM_TestHFlag(e->v2, BM_SELECT)) {
1147                                                 BM_SetHFlag(e, BM_SELECT);
1148                                                 bm->totedgesel += 1;
1149                                         } else if (BM_TestHFlag(e, BM_SELECT) && (!BM_TestHFlag(e->v1, BM_SELECT)
1150                                                                                                                   || !BM_TestHFlag(e->v2, BM_SELECT))) {
1151                                                 BM_ClearHFlag(e, BM_SELECT);
1152                                                 bm->totedgesel -= 1;
1153                                         }
1154                                 }
1155                         }
1156                 }
1157         }
1158
1159         BMO_Finish_Op(bm, &op);
1160 }
1161
1162 void esplit_exec(BMesh *bm, BMOperator *op)
1163 {
1164         BMOIter siter;
1165         BMEdge *e;
1166         subdparams params;
1167         int skey;
1168
1169         params.numcuts = BMO_GetSlot(op, "numcuts")->data.i;
1170         params.op = op;
1171
1172         BM_add_data_layer(bm, &bm->vdata, CD_SHAPEKEY);
1173         skey = CustomData_number_of_layers(&bm->vdata, CD_SHAPEKEY)-1;
1174
1175         params.origkey = skey;
1176
1177         /*go through and split edges*/
1178         BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
1179                 bm_subdivide_multicut(bm, e, &params, e->v1, e->v2);
1180         }
1181
1182         BMO_Flag_To_Slot(bm, op, "outsplit",
1183                          ELE_SPLIT, BM_ALL);
1184
1185         BM_free_data_layer_n(bm, &bm->vdata, CD_SHAPEKEY, skey);
1186 }