source/blender/bmesh/intern/bmesh_core.c

   1 /*
   2  * ***** BEGIN GPL LICENSE BLOCK *****
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software Foundation,
  16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  17  *
  18  * Contributor(s): Joseph Eagar, Geoffrey Bantle, Campbell Barton
  19  *
  20  * ***** END GPL LICENSE BLOCK *****
  21  */
  22
  23 /** \file blender/bmesh/intern/bmesh_core.c
  24  *  \ingroup bmesh
  25  *
  26  * Core BMesh functions for adding, removing BMesh elements.
  27  */
  28
  29 #include "MEM_guardedalloc.h"
  30
  31 #include "BLI_math_vector.h"
  32 #include "BLI_array.h"
  33 #include "BLI_alloca.h"
  34 #include "BLI_linklist_stack.h"
  35 #include "BLI_stackdefines.h"
  36
  37 #include "BLT_translation.h"
  38
  39 #include "BKE_DerivedMesh.h"
  40 #include "BKE_mesh.h"
  41
  42 #include "bmesh.h"
  43 #include "intern/bmesh_private.h"
  44
  45 /* use so valgrinds memcheck alerts us when undefined index is used.
  46  * TESTING ONLY! */
  47 // #define USE_DEBUG_INDEX_MEMCHECK
  48
  49 #ifdef USE_DEBUG_INDEX_MEMCHECK
  50 #define DEBUG_MEMCHECK_INDEX_INVALIDATE(ele)                                  \
  51         {                                                                         \
  52                 int undef_idx;                                                        \
  53                 BM_elem_index_set(ele, undef_idx); /* set_ok_invalid */               \
  54         } (void)0
  55
  56 #endif
  57
  58 /**
  59  * \brief Main function for creating a new vertex.
  60  */
  61 BMVert *BM_vert_create(
  62         BMesh *bm, const float co[3],
  63         const BMVert *v_example, const eBMCreateFlag create_flag)
  64 {
  65         BMVert *v = BLI_mempool_alloc(bm->vpool);
  66
  67         BLI_assert((v_example == NULL) || (v_example->head.htype == BM_VERT));
  68         BLI_assert(!(create_flag & 1));
  69
  70         /* --- assign all members --- */
  71         v->head.data = NULL;
  72
  73 #ifdef USE_DEBUG_INDEX_MEMCHECK
  74         DEBUG_MEMCHECK_INDEX_INVALIDATE(v)
  75 #else
  76         BM_elem_index_set(v, -1); /* set_ok_invalid */
  77 #endif
  78
  79         v->head.htype = BM_VERT;
  80         v->head.hflag = 0;
  81         v->head.api_flag = 0;
  82
  83         /* allocate flags */
  84         if (bm->use_toolflags) {
  85                 ((BMVert_OFlag *)v)->oflags = bm->vtoolflagpool ? BLI_mempool_calloc(bm->vtoolflagpool) : NULL;
  86         }
  87
  88         /* 'v->no' is handled by BM_elem_attrs_copy */
  89         if (co) {
  90                 copy_v3_v3(v->co, co);
  91         }
  92         else {
  93                 zero_v3(v->co);
  94         }
  95         /* 'v->no' set below */
  96
  97         v->e = NULL;
  98         /* --- done --- */
  99
 100
 101         /* disallow this flag for verts - its meaningless */
 102         BLI_assert((create_flag & BM_CREATE_NO_DOUBLE) == 0);
 103
 104         /* may add to middle of the pool */
 105         bm->elem_index_dirty |= BM_VERT;
 106         bm->elem_table_dirty |= BM_VERT;
 107
 108         bm->totvert++;
 109
 110         if (!(create_flag & BM_CREATE_SKIP_CD)) {
 111                 if (v_example) {
 112                         int *keyi;
 113
 114                         /* handles 'v->no' too */
 115                         BM_elem_attrs_copy(bm, bm, v_example, v);
 116
 117                         /* exception: don't copy the original shapekey index */
 118                         keyi = CustomData_bmesh_get(&bm->vdata, v->head.data, CD_SHAPE_KEYINDEX);
 119                         if (keyi) {
 120                                 *keyi = ORIGINDEX_NONE;
 121                         }
 122                 }
 123                 else {
 124                         CustomData_bmesh_set_default(&bm->vdata, &v->head.data);
 125                         zero_v3(v->no);
 126                 }
 127         }
 128         else {
 129                 if (v_example) {
 130                         copy_v3_v3(v->no, v_example->no);
 131                 }
 132                 else {
 133                         zero_v3(v->no);
 134                 }
 135         }
 136
 137         BM_CHECK_ELEMENT(v);
 138
 139         return v;
 140 }
 141
 142 /**
 143  * \brief Main function for creating a new edge.
 144  *
 145  * \note Duplicate edges are supported by the API however users should _never_ see them.
 146  * so unless you need a unique edge or know the edge won't exist, you should call with \a no_double = true
 147  */
 148 BMEdge *BM_edge_create(
 149         BMesh *bm, BMVert *v1, BMVert *v2,
 150         const BMEdge *e_example, const eBMCreateFlag create_flag)
 151 {
 152         BMEdge *e;
 153
 154         BLI_assert(v1 != v2);
 155         BLI_assert(v1->head.htype == BM_VERT && v2->head.htype == BM_VERT);
 156         BLI_assert((e_example == NULL) || (e_example->head.htype == BM_EDGE));
 157         BLI_assert(!(create_flag & 1));
 158
 159         if ((create_flag & BM_CREATE_NO_DOUBLE) && (e = BM_edge_exists(v1, v2)))
 160                 return e;
 161
 162         e = BLI_mempool_alloc(bm->epool);
 163
 164
 165         /* --- assign all members --- */
 166         e->head.data = NULL;
 167
 168 #ifdef USE_DEBUG_INDEX_MEMCHECK
 169         DEBUG_MEMCHECK_INDEX_INVALIDATE(e)
 170 #else
 171         BM_elem_index_set(e, -1); /* set_ok_invalid */
 172 #endif
 173
 174         e->head.htype = BM_EDGE;
 175         e->head.hflag = BM_ELEM_SMOOTH | BM_ELEM_DRAW;
 176         e->head.api_flag = 0;
 177
 178         /* allocate flags */
 179         if (bm->use_toolflags) {
 180                 ((BMEdge_OFlag *)e)->oflags = bm->etoolflagpool ? BLI_mempool_calloc(bm->etoolflagpool) : NULL;
 181         }
 182
 183         e->v1 = v1;
 184         e->v2 = v2;
 185         e->l = NULL;
 186
 187         memset(&e->v1_disk_link, 0, sizeof(BMDiskLink) * 2);
 188         /* --- done --- */
 189
 190
 191         bmesh_disk_edge_append(e, e->v1);
 192         bmesh_disk_edge_append(e, e->v2);
 193
 194         /* may add to middle of the pool */
 195         bm->elem_index_dirty |= BM_EDGE;
 196         bm->elem_table_dirty |= BM_EDGE;
 197
 198         bm->totedge++;
 199
 200         if (!(create_flag & BM_CREATE_SKIP_CD)) {
 201                 if (e_example) {
 202                         BM_elem_attrs_copy(bm, bm, e_example, e);
 203                 }
 204                 else {
 205                         CustomData_bmesh_set_default(&bm->edata, &e->head.data);
 206                 }
 207         }
 208
 209         BM_CHECK_ELEMENT(e);
 210
 211         return e;
 212 }
 213
 214 /**
 215  * \note In most cases a \a l_example should be NULL,
 216  * since this is a low level API and we shouldn't attempt to be clever and guess whats intended.
 217  * In cases where copying adjacent loop-data is useful, see #BM_face_copy_shared.
 218  */
 219 static BMLoop *bm_loop_create(
 220         BMesh *bm, BMVert *v, BMEdge *e, BMFace *f,
 221         const BMLoop *l_example, const eBMCreateFlag create_flag)
 222 {
 223         BMLoop *l = NULL;
 224
 225         l = BLI_mempool_alloc(bm->lpool);
 226
 227         BLI_assert((l_example == NULL) || (l_example->head.htype == BM_LOOP));
 228         BLI_assert(!(create_flag & 1));
 229
 230 #ifndef NDEBUG
 231         if (l_example) {
 232                 /* ensure passing a loop is either sharing the same vertex, or entirely disconnected
 233                  * use to catch mistake passing in loop offset-by-one. */
 234                 BLI_assert((v == l_example->v) || !ELEM(v, l_example->prev->v, l_example->next->v));
 235         }
 236 #endif
 237
 238         /* --- assign all members --- */
 239         l->head.data = NULL;
 240
 241 #ifdef USE_DEBUG_INDEX_MEMCHECK
 242         DEBUG_MEMCHECK_INDEX_INVALIDATE(l)
 243 #else
 244         BM_elem_index_set(l, -1); /* set_ok_invalid */
 245 #endif
 246
 247         l->head.htype = BM_LOOP;
 248         l->head.hflag = 0;
 249         l->head.api_flag = 0;
 250
 251         l->v = v;
 252         l->e = e;
 253         l->f = f;
 254
 255         l->radial_next = NULL;
 256         l->radial_prev = NULL;
 257         l->next = NULL;
 258         l->prev = NULL;
 259         /* --- done --- */
 260
 261         /* may add to middle of the pool */
 262         bm->elem_index_dirty |= BM_LOOP;
 263
 264         bm->totloop++;
 265
 266         if (!(create_flag & BM_CREATE_SKIP_CD)) {
 267                 if (l_example) {
 268                         /* no need to copy attrs, just handle customdata */
 269                         // BM_elem_attrs_copy(bm, bm, l_example, l);
 270                         CustomData_bmesh_free_block_data(&bm->ldata, l->head.data);
 271                         CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, l_example->head.data, &l->head.data);
 272                 }
 273                 else {
 274                         CustomData_bmesh_set_default(&bm->ldata, &l->head.data);
 275                 }
 276         }
 277
 278         return l;
 279 }
 280
 281 static BMLoop *bm_face_boundary_add(
 282         BMesh *bm, BMFace *f, BMVert *startv, BMEdge *starte,
 283         const eBMCreateFlag create_flag)
 284 {
 285 #ifdef USE_BMESH_HOLES
 286         BMLoopList *lst = BLI_mempool_calloc(bm->looplistpool);
 287 #endif
 288         BMLoop *l = bm_loop_create(bm, startv, starte, f, NULL /* starte->l */, create_flag);
 289
 290         bmesh_radial_loop_append(starte, l);
 291
 292 #ifdef USE_BMESH_HOLES
 293         lst->first = lst->last = l;
 294         BLI_addtail(&f->loops, lst);
 295 #else
 296         f->l_first = l;
 297 #endif
 298
 299         return l;
 300 }
 301
 302 BMFace *BM_face_copy(
 303         BMesh *bm_dst, BMesh *bm_src, BMFace *f,
 304         const bool copy_verts, const bool copy_edges)
 305 {
 306         BMVert **verts = BLI_array_alloca(verts, f->len);
 307         BMEdge **edges = BLI_array_alloca(edges, f->len);
 308         BMLoop *l_iter;
 309         BMLoop *l_first;
 310         BMLoop *l_copy;
 311         BMFace *f_copy;
 312         int i;
 313
 314         BLI_assert((bm_dst == bm_src) || (copy_verts && copy_edges));
 315
 316         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 317         i = 0;
 318         do {
 319                 if (copy_verts) {
 320                         verts[i] = BM_vert_create(bm_dst, l_iter->v->co, l_iter->v, BM_CREATE_NOP);
 321                 }
 322                 else {
 323                         verts[i] = l_iter->v;
 324                 }
 325                 i++;
 326         } while ((l_iter = l_iter->next) != l_first);
 327
 328         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 329         i = 0;
 330         do {
 331                 if (copy_edges) {
 332                         BMVert *v1, *v2;
 333
 334                         if (l_iter->e->v1 == verts[i]) {
 335                                 v1 = verts[i];
 336                                 v2 = verts[(i + 1) % f->len];
 337                         }
 338                         else {
 339                                 v2 = verts[i];
 340                                 v1 = verts[(i + 1) % f->len];
 341                         }
 342
 343                         edges[i] = BM_edge_create(bm_dst, v1, v2, l_iter->e, BM_CREATE_NOP);
 344                 }
 345                 else {
 346                         edges[i] = l_iter->e;
 347                 }
 348                 i++;
 349         } while ((l_iter = l_iter->next) != l_first);
 350
 351         f_copy = BM_face_create(bm_dst, verts, edges, f->len, NULL, BM_CREATE_SKIP_CD);
 352
 353         BM_elem_attrs_copy(bm_src, bm_dst, f, f_copy);
 354
 355         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 356         l_copy = BM_FACE_FIRST_LOOP(f_copy);
 357         do {
 358                 BM_elem_attrs_copy(bm_src, bm_dst, l_iter, l_copy);
 359                 l_copy = l_copy->next;
 360         } while ((l_iter = l_iter->next) != l_first);
 361
 362         return f_copy;
 363 }
 364
 365 /**
 366  * only create the face, since this calloc's the length is initialized to 0,
 367  * leave adding loops to the caller.
 368  *
 369  * \note, caller needs to handle customdata.
 370  */
 371 BLI_INLINE BMFace *bm_face_create__internal(BMesh *bm)
 372 {
 373         BMFace *f;
 374
 375         f = BLI_mempool_alloc(bm->fpool);
 376
 377
 378         /* --- assign all members --- */
 379         f->head.data = NULL;
 380 #ifdef USE_DEBUG_INDEX_MEMCHECK
 381         DEBUG_MEMCHECK_INDEX_INVALIDATE(f)
 382 #else
 383         BM_elem_index_set(f, -1); /* set_ok_invalid */
 384 #endif
 385
 386         f->head.htype = BM_FACE;
 387         f->head.hflag = 0;
 388         f->head.api_flag = 0;
 389
 390         /* allocate flags */
 391         if (bm->use_toolflags) {
 392                 ((BMFace_OFlag *)f)->oflags = bm->ftoolflagpool ? BLI_mempool_calloc(bm->ftoolflagpool) : NULL;
 393         }
 394
 395 #ifdef USE_BMESH_HOLES
 396         BLI_listbase_clear(&f->loops);
 397 #else
 398         f->l_first = NULL;
 399 #endif
 400         f->len = 0;
 401         /* caller must initialize */
 402         // zero_v3(f->no);
 403         f->mat_nr = 0;
 404         /* --- done --- */
 405
 406
 407         /* may add to middle of the pool */
 408         bm->elem_index_dirty |= BM_FACE;
 409         bm->elem_table_dirty |= BM_FACE;
 410
 411         bm->totface++;
 412
 413 #ifdef USE_BMESH_HOLES
 414         f->totbounds = 0;
 415 #endif
 416
 417         return f;
 418 }
 419
 420 /**
 421  * Main face creation function
 422  *
 423  * \param bm  The mesh
 424  * \param verts  A sorted array of verts size of len
 425  * \param edges  A sorted array of edges size of len
 426  * \param len  Length of the face
 427  * \param create_flag  Options for creating the face
 428  */
 429 BMFace *BM_face_create(
 430         BMesh *bm, BMVert **verts, BMEdge **edges, const int len,
 431         const BMFace *f_example, const eBMCreateFlag create_flag)
 432 {
 433         BMFace *f = NULL;
 434         BMLoop *l, *startl, *lastl;
 435         int i;
 436
 437         BLI_assert((f_example == NULL) || (f_example->head.htype == BM_FACE));
 438         BLI_assert(!(create_flag & 1));
 439
 440         if (len == 0) {
 441                 /* just return NULL for now */
 442                 return NULL;
 443         }
 444
 445         if (create_flag & BM_CREATE_NO_DOUBLE) {
 446                 /* Check if face already exists */
 447                 const bool is_overlap = BM_face_exists(verts, len, &f);
 448                 if (is_overlap) {
 449                         return f;
 450                 }
 451                 else {
 452                         BLI_assert(f == NULL);
 453                 }
 454         }
 455
 456         f = bm_face_create__internal(bm);
 457
 458         startl = lastl = bm_face_boundary_add(bm, f, verts[0], edges[0], create_flag);
 459
 460         for (i = 1; i < len; i++) {
 461                 l = bm_loop_create(bm, verts[i], edges[i], f, NULL /* edges[i]->l */, create_flag);
 462
 463                 bmesh_radial_loop_append(edges[i], l);
 464
 465                 l->prev = lastl;
 466                 lastl->next = l;
 467                 lastl = l;
 468         }
 469
 470         startl->prev = lastl;
 471         lastl->next = startl;
 472
 473         f->len = len;
 474
 475         if (!(create_flag & BM_CREATE_SKIP_CD)) {
 476                 if (f_example) {
 477                         BM_elem_attrs_copy(bm, bm, f_example, f);
 478                 }
 479                 else {
 480                         CustomData_bmesh_set_default(&bm->pdata, &f->head.data);
 481                         zero_v3(f->no);
 482                 }
 483         }
 484         else {
 485                 if (f_example) {
 486                         copy_v3_v3(f->no, f_example->no);
 487                 }
 488                 else {
 489                         zero_v3(f->no);
 490                 }
 491         }
 492
 493         BM_CHECK_ELEMENT(f);
 494
 495         return f;
 496 }
 497
 498 /**
 499  * Wrapper for #BM_face_create when you don't have an edge array
 500  */
 501 BMFace *BM_face_create_verts(
 502         BMesh *bm, BMVert **vert_arr, const int len,
 503         const BMFace *f_example, const eBMCreateFlag create_flag, const bool create_edges)
 504 {
 505         BMEdge **edge_arr = BLI_array_alloca(edge_arr, len);
 506
 507         if (create_edges) {
 508                 BM_edges_from_verts_ensure(bm, edge_arr, vert_arr, len);
 509         }
 510         else {
 511                 if (BM_edges_from_verts(edge_arr, vert_arr, len) == false) {
 512                         return NULL;
 513                 }
 514         }
 515
 516         return BM_face_create(bm, vert_arr, edge_arr, len, f_example, create_flag);
 517 }
 518
 519 #ifndef NDEBUG
 520
 521 /**
 522  * Check the element is valid.
 523  *
 524  * BMESH_TODO, when this raises an error the output is incredibly confusing.
 525  * need to have some nice way to print/debug what the heck's going on.
 526  */
 527 int bmesh_elem_check(void *element, const char htype)
 528 {
 529         BMHeader *head = element;
 530         enum {
 531                 IS_NULL                                     = (1 << 0),
 532                 IS_WRONG_TYPE                               = (1 << 1),
 533
 534                 IS_VERT_WRONG_EDGE_TYPE                     = (1 << 2),
 535
 536                 IS_EDGE_NULL_DISK_LINK                      = (1 << 3),
 537                 IS_EDGE_WRONG_LOOP_TYPE                     = (1 << 4),
 538                 IS_EDGE_WRONG_FACE_TYPE                     = (1 << 5),
 539                 IS_EDGE_NULL_RADIAL_LINK                    = (1 << 6),
 540                 IS_EDGE_ZERO_FACE_LENGTH                    = (1 << 7),
 541
 542                 IS_LOOP_WRONG_FACE_TYPE                     = (1 << 8),
 543                 IS_LOOP_WRONG_EDGE_TYPE                     = (1 << 9),
 544                 IS_LOOP_WRONG_VERT_TYPE                     = (1 << 10),
 545                 IS_LOOP_VERT_NOT_IN_EDGE                    = (1 << 11),
 546                 IS_LOOP_NULL_CYCLE_LINK                     = (1 << 12),
 547                 IS_LOOP_ZERO_FACE_LENGTH                    = (1 << 13),
 548                 IS_LOOP_WRONG_FACE_LENGTH                   = (1 << 14),
 549                 IS_LOOP_WRONG_RADIAL_LENGTH                 = (1 << 15),
 550
 551                 IS_FACE_NULL_LOOP                           = (1 << 16),
 552                 IS_FACE_WRONG_LOOP_FACE                     = (1 << 17),
 553                 IS_FACE_NULL_EDGE                           = (1 << 18),
 554                 IS_FACE_NULL_VERT                           = (1 << 19),
 555                 IS_FACE_LOOP_VERT_NOT_IN_EDGE               = (1 << 20),
 556                 IS_FACE_LOOP_WRONG_RADIAL_LENGTH            = (1 << 21),
 557                 IS_FACE_LOOP_WRONG_DISK_LENGTH              = (1 << 22),
 558                 IS_FACE_LOOP_DUPE_LOOP                      = (1 << 23),
 559                 IS_FACE_LOOP_DUPE_VERT                      = (1 << 24),
 560                 IS_FACE_LOOP_DUPE_EDGE                      = (1 << 25),
 561                 IS_FACE_WRONG_LENGTH                        = (1 << 26),
 562         } err = 0;
 563
 564         if (!element)
 565                 return IS_NULL;
 566
 567         if (head->htype != htype)
 568                 return IS_WRONG_TYPE;
 569
 570         switch (htype) {
 571                 case BM_VERT:
 572                 {
 573                         BMVert *v = element;
 574                         if (v->e && v->e->head.htype != BM_EDGE) {
 575                                 err |= IS_VERT_WRONG_EDGE_TYPE;
 576                         }
 577                         break;
 578                 }
 579                 case BM_EDGE:
 580                 {
 581                         BMEdge *e = element;
 582                         if (e->v1_disk_link.prev == NULL ||
 583                             e->v2_disk_link.prev == NULL ||
 584                             e->v1_disk_link.next == NULL ||
 585                             e->v2_disk_link.next == NULL)
 586                         {
 587                                 err |= IS_EDGE_NULL_DISK_LINK;
 588                         }
 589
 590                         if (e->l && e->l->head.htype != BM_LOOP) {
 591                                 err |= IS_EDGE_WRONG_LOOP_TYPE;
 592                         }
 593                         if (e->l && e->l->f->head.htype != BM_FACE) {
 594                                 err |= IS_EDGE_WRONG_FACE_TYPE;
 595                         }
 596                         if (e->l && (e->l->radial_next == NULL || e->l->radial_prev == NULL)) {
 597                                 err |= IS_EDGE_NULL_RADIAL_LINK;
 598                         }
 599                         if (e->l && e->l->f->len <= 0) {
 600                                 err |= IS_EDGE_ZERO_FACE_LENGTH;
 601                         }
 602                         break;
 603                 }
 604                 case BM_LOOP:
 605                 {
 606                         BMLoop *l = element, *l2;
 607                         int i;
 608
 609                         if (l->f->head.htype != BM_FACE) {
 610                                 err |= IS_LOOP_WRONG_FACE_TYPE;
 611                         }
 612                         if (l->e->head.htype != BM_EDGE) {
 613                                 err |= IS_LOOP_WRONG_EDGE_TYPE;
 614                         }
 615                         if (l->v->head.htype != BM_VERT) {
 616                                 err |= IS_LOOP_WRONG_VERT_TYPE;
 617                         }
 618                         if (!BM_vert_in_edge(l->e, l->v)) {
 619                                 fprintf(stderr, "%s: fatal bmesh error (vert not in edge)! (bmesh internal error)\n", __func__);
 620                                 err |= IS_LOOP_VERT_NOT_IN_EDGE;
 621                         }
 622
 623                         if (l->radial_next == NULL || l->radial_prev == NULL) {
 624                                 err |= IS_LOOP_NULL_CYCLE_LINK;
 625                         }
 626                         if (l->f->len <= 0) {
 627                                 err |= IS_LOOP_ZERO_FACE_LENGTH;
 628                         }
 629
 630                         /* validate boundary loop -- invalid for hole loops, of course,
 631                          * but we won't be allowing those for a while yet */
 632                         l2 = l;
 633                         i = 0;
 634                         do {
 635                                 if (i >= BM_NGON_MAX) {
 636                                         break;
 637                                 }
 638
 639                                 i++;
 640                         } while ((l2 = l2->next) != l);
 641
 642                         if (i != l->f->len || l2 != l) {
 643                                 err |= IS_LOOP_WRONG_FACE_LENGTH;
 644                         }
 645
 646                         if (!bmesh_radial_validate(bmesh_radial_length(l), l)) {
 647                                 err |= IS_LOOP_WRONG_RADIAL_LENGTH;
 648                         }
 649
 650                         break;
 651                 }
 652                 case BM_FACE:
 653                 {
 654                         BMFace *f = element;
 655                         BMLoop *l_iter;
 656                         BMLoop *l_first;
 657                         int len = 0;
 658
 659 #ifdef USE_BMESH_HOLES
 660                         if (!f->loops.first)
 661 #else
 662                         if (!f->l_first)
 663 #endif
 664                         {
 665                                 err |= IS_FACE_NULL_LOOP;
 666                         }
 667                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 668                         do {
 669                                 if (l_iter->f != f) {
 670                                         fprintf(stderr, "%s: loop inside one face points to another! (bmesh internal error)\n", __func__);
 671                                         err |= IS_FACE_WRONG_LOOP_FACE;
 672                                 }
 673
 674                                 if (!l_iter->e) {
 675                                         err |= IS_FACE_NULL_EDGE;
 676                                 }
 677                                 if (!l_iter->v) {
 678                                         err |= IS_FACE_NULL_VERT;
 679                                 }
 680                                 if (l_iter->e && l_iter->v) {
 681                                         if (!BM_vert_in_edge(l_iter->e, l_iter->v) ||
 682                                             !BM_vert_in_edge(l_iter->e, l_iter->next->v))
 683                                         {
 684                                                 err |= IS_FACE_LOOP_VERT_NOT_IN_EDGE;
 685                                         }
 686
 687                                         if (!bmesh_radial_validate(bmesh_radial_length(l_iter), l_iter)) {
 688                                                 err |= IS_FACE_LOOP_WRONG_RADIAL_LENGTH;
 689                                         }
 690
 691                                         if (bmesh_disk_count_ex(l_iter->v, 2) < 2) {
 692                                                 err |= IS_FACE_LOOP_WRONG_DISK_LENGTH;
 693                                         }
 694                                 }
 695
 696                                 /* check for duplicates */
 697                                 if (BM_ELEM_API_FLAG_TEST(l_iter, _FLAG_ELEM_CHECK)) {
 698                                         err |= IS_FACE_LOOP_DUPE_LOOP;
 699                                 }
 700                                 BM_ELEM_API_FLAG_ENABLE(l_iter, _FLAG_ELEM_CHECK);
 701                                 if (l_iter->v) {
 702                                         if (BM_ELEM_API_FLAG_TEST(l_iter->v, _FLAG_ELEM_CHECK)) {
 703                                                 err |= IS_FACE_LOOP_DUPE_VERT;
 704                                         }
 705                                         BM_ELEM_API_FLAG_ENABLE(l_iter->v, _FLAG_ELEM_CHECK);
 706                                 }
 707                                 if (l_iter->e) {
 708                                         if (BM_ELEM_API_FLAG_TEST(l_iter->e, _FLAG_ELEM_CHECK)) {
 709                                                 err |= IS_FACE_LOOP_DUPE_EDGE;
 710                                         }
 711                                         BM_ELEM_API_FLAG_ENABLE(l_iter->e, _FLAG_ELEM_CHECK);
 712                                 }
 713
 714                                 len++;
 715                         } while ((l_iter = l_iter->next) != l_first);
 716
 717                         /* cleanup duplicates flag */
 718                         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 719                         do {
 720                                 BM_ELEM_API_FLAG_DISABLE(l_iter, _FLAG_ELEM_CHECK);
 721                                 if (l_iter->v) {
 722                                         BM_ELEM_API_FLAG_DISABLE(l_iter->v, _FLAG_ELEM_CHECK);
 723                                 }
 724                                 if (l_iter->e) {
 725                                         BM_ELEM_API_FLAG_DISABLE(l_iter->e, _FLAG_ELEM_CHECK);
 726                                 }
 727                         } while ((l_iter = l_iter->next) != l_first);
 728
 729                         if (len != f->len) {
 730                                 err |= IS_FACE_WRONG_LENGTH;
 731                         }
 732                         break;
 733                 }
 734                 default:
 735                         BLI_assert(0);
 736                         break;
 737         }
 738
 739         BMESH_ASSERT(err == 0);
 740
 741         return err;
 742 }
 743
 744 #endif /* NDEBUG */
 745
 746 /**
 747  * low level function, only frees the vert,
 748  * doesn't change or adjust surrounding geometry
 749  */
 750 static void bm_kill_only_vert(BMesh *bm, BMVert *v)
 751 {
 752         bm->totvert--;
 753         bm->elem_index_dirty |= BM_VERT;
 754         bm->elem_table_dirty |= BM_VERT;
 755
 756         BM_select_history_remove(bm, v);
 757
 758         if (v->head.data)
 759                 CustomData_bmesh_free_block(&bm->vdata, &v->head.data);
 760
 761         if (bm->vtoolflagpool) {
 762                 BLI_mempool_free(bm->vtoolflagpool, ((BMVert_OFlag *)v)->oflags);
 763         }
 764         BLI_mempool_free(bm->vpool, v);
 765 }
 766
 767 /**
 768  * low level function, only frees the edge,
 769  * doesn't change or adjust surrounding geometry
 770  */
 771 static void bm_kill_only_edge(BMesh *bm, BMEdge *e)
 772 {
 773         bm->totedge--;
 774         bm->elem_index_dirty |= BM_EDGE;
 775         bm->elem_table_dirty |= BM_EDGE;
 776
 777         BM_select_history_remove(bm, (BMElem *)e);
 778
 779         if (e->head.data)
 780                 CustomData_bmesh_free_block(&bm->edata, &e->head.data);
 781
 782         if (bm->etoolflagpool) {
 783                 BLI_mempool_free(bm->etoolflagpool, ((BMEdge_OFlag *)e)->oflags);
 784         }
 785         BLI_mempool_free(bm->epool, e);
 786 }
 787
 788 /**
 789  * low level function, only frees the face,
 790  * doesn't change or adjust surrounding geometry
 791  */
 792 static void bm_kill_only_face(BMesh *bm, BMFace *f)
 793 {
 794         if (bm->act_face == f)
 795                 bm->act_face = NULL;
 796
 797         bm->totface--;
 798         bm->elem_index_dirty |= BM_FACE;
 799         bm->elem_table_dirty |= BM_FACE;
 800
 801         BM_select_history_remove(bm, (BMElem *)f);
 802
 803         if (f->head.data)
 804                 CustomData_bmesh_free_block(&bm->pdata, &f->head.data);
 805
 806         if (bm->ftoolflagpool) {
 807                 BLI_mempool_free(bm->ftoolflagpool, ((BMFace_OFlag *)f)->oflags);
 808         }
 809         BLI_mempool_free(bm->fpool, f);
 810 }
 811
 812 /**
 813  * low level function, only frees the loop,
 814  * doesn't change or adjust surrounding geometry
 815  */
 816 static void bm_kill_only_loop(BMesh *bm, BMLoop *l)
 817 {
 818         bm->totloop--;
 819         bm->elem_index_dirty |= BM_LOOP;
 820         if (l->head.data)
 821                 CustomData_bmesh_free_block(&bm->ldata, &l->head.data);
 822
 823         BLI_mempool_free(bm->lpool, l);
 824 }
 825
 826 /**
 827  * kills all edges associated with \a f, along with any other faces containing
 828  * those edges
 829  */
 830 void BM_face_edges_kill(BMesh *bm, BMFace *f)
 831 {
 832         BMEdge **edges = BLI_array_alloca(edges, f->len);
 833         BMLoop *l_iter;
 834         BMLoop *l_first;
 835         int i = 0;
 836
 837         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 838         do {
 839                 edges[i++] = l_iter->e;
 840         } while ((l_iter = l_iter->next) != l_first);
 841
 842         for (i = 0; i < f->len; i++) {
 843                 BM_edge_kill(bm, edges[i]);
 844         }
 845 }
 846
 847 /**
 848  * kills all verts associated with \a f, along with any other faces containing
 849  * those vertices
 850  */
 851 void BM_face_verts_kill(BMesh *bm, BMFace *f)
 852 {
 853         BMVert **verts = BLI_array_alloca(verts, f->len);
 854         BMLoop *l_iter;
 855         BMLoop *l_first;
 856         int i = 0;
 857
 858         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 859         do {
 860                 verts[i++] = l_iter->v;
 861         } while ((l_iter = l_iter->next) != l_first);
 862
 863         for (i = 0; i < f->len; i++) {
 864                 BM_vert_kill(bm, verts[i]);
 865         }
 866 }
 867
 868 /**
 869  * Kills \a f and its loops.
 870  */
 871 void BM_face_kill(BMesh *bm, BMFace *f)
 872 {
 873 #ifdef USE_BMESH_HOLES
 874         BMLoopList *ls, *ls_next;
 875 #endif
 876
 877 #ifdef NDEBUG
 878         /* check length since we may be removing degenerate faces */
 879         if (f->len >= 3) {
 880                 BM_CHECK_ELEMENT(f);
 881         }
 882 #endif
 883
 884 #ifdef USE_BMESH_HOLES
 885         for (ls = f->loops.first; ls; ls = ls_next)
 886 #else
 887         if (f->l_first)
 888 #endif
 889         {
 890                 BMLoop *l_iter, *l_next, *l_first;
 891
 892 #ifdef USE_BMESH_HOLES
 893                 ls_next = ls->next;
 894                 l_iter = l_first = ls->first;
 895 #else
 896                 l_iter = l_first = f->l_first;
 897 #endif
 898
 899                 do {
 900                         l_next = l_iter->next;
 901
 902                         bmesh_radial_loop_remove(l_iter->e, l_iter);
 903                         bm_kill_only_loop(bm, l_iter);
 904
 905                 } while ((l_iter = l_next) != l_first);
 906
 907 #ifdef USE_BMESH_HOLES
 908                 BLI_mempool_free(bm->looplistpool, ls);
 909 #endif
 910         }
 911
 912         bm_kill_only_face(bm, f);
 913 }
 914
 915 /**
 916  * A version of #BM_face_kill which removes edges and verts
 917  * which have no remaining connected geometry.
 918  */
 919 void BM_face_kill_loose(BMesh *bm, BMFace *f)
 920 {
 921 #ifdef USE_BMESH_HOLES
 922         BMLoopList *ls, *ls_next;
 923 #endif
 924
 925         BM_CHECK_ELEMENT(f);
 926
 927 #ifdef USE_BMESH_HOLES
 928         for (ls = f->loops.first; ls; ls = ls_next)
 929 #else
 930         if (f->l_first)
 931 #endif
 932         {
 933                 BMLoop *l_iter, *l_next, *l_first;
 934
 935 #ifdef USE_BMESH_HOLES
 936                 ls_next = ls->next;
 937                 l_iter = l_first = ls->first;
 938 #else
 939                 l_iter = l_first = f->l_first;
 940 #endif
 941
 942                 do {
 943                         BMEdge *e;
 944                         l_next = l_iter->next;
 945
 946                         e = l_iter->e;
 947                         bmesh_radial_loop_remove(e, l_iter);
 948                         bm_kill_only_loop(bm, l_iter);
 949
 950                         if (e->l == NULL) {
 951                                 BMVert *v1 = e->v1, *v2 = e->v2;
 952
 953                                 bmesh_disk_edge_remove(e, e->v1);
 954                                 bmesh_disk_edge_remove(e, e->v2);
 955                                 bm_kill_only_edge(bm, e);
 956
 957                                 if (v1->e == NULL) {
 958                                         bm_kill_only_vert(bm, v1);
 959                                 }
 960                                 if (v2->e == NULL) {
 961                                         bm_kill_only_vert(bm, v2);
 962                                 }
 963                         }
 964                 } while ((l_iter = l_next) != l_first);
 965
 966 #ifdef USE_BMESH_HOLES
 967                 BLI_mempool_free(bm->looplistpool, ls);
 968 #endif
 969         }
 970
 971         bm_kill_only_face(bm, f);
 972 }
 973
 974 /**
 975  * kills \a e and all faces that use it.
 976  */
 977 void BM_edge_kill(BMesh *bm, BMEdge *e)
 978 {
 979         while (e->l) {
 980                 BM_face_kill(bm, e->l->f);
 981         }
 982
 983         bmesh_disk_edge_remove(e, e->v1);
 984         bmesh_disk_edge_remove(e, e->v2);
 985
 986         bm_kill_only_edge(bm, e);
 987 }
 988
 989 /**
 990  * kills \a v and all edges that use it.
 991  */
 992 void BM_vert_kill(BMesh *bm, BMVert *v)
 993 {
 994         while (v->e) {
 995                 BM_edge_kill(bm, v->e);
 996         }
 997
 998         bm_kill_only_vert(bm, v);
 999 }
1000
1001 /********** private disk and radial cycle functions ********** */
1002
1003 /**
1004  * return the length of the face, should always equal \a l->f->len
1005  */
1006 static int UNUSED_FUNCTION(bm_loop_length)(BMLoop *l)
1007 {
1008         BMLoop *l_first = l;
1009         int i = 0;
1010
1011         do {
1012                 i++;
1013         } while ((l = l->next) != l_first);
1014
1015         return i;
1016 }
1017
1018 /**
1019  * \brief Loop Reverse
1020  *
1021  * Changes the winding order of a face from CW to CCW or vice versa.
1022  * This euler is a bit peculiar in comparison to others as it is its
1023  * own inverse.
1024  *
1025  * BMESH_TODO: reinsert validation code.
1026  *
1027  * \param cd_loop_mdisp_offset: Cached result of `CustomData_get_offset(&bm->ldata, CD_MDISPS)`.
1028  * \param use_loop_mdisp_flip: When set, flip the Z-depth of the mdisp,
1029  * (use when flipping normals, disable when mirroring, eg: symmetrize).
1030  *
1031  * \return Success
1032  */
1033 static bool bm_loop_reverse_loop(
1034         BMesh *bm, BMFace *f,
1035 #ifdef USE_BMESH_HOLES
1036         BMLoopList *lst,
1037 #endif
1038         const int cd_loop_mdisp_offset, const bool use_loop_mdisp_flip)
1039 {
1040
1041 #ifdef USE_BMESH_HOLES
1042         BMLoop *l_first = lst->first;
1043 #else
1044         BMLoop *l_first = f->l_first;
1045 #endif
1046
1047         const int len = f->len;
1048         BMLoop *l_iter;
1049         BMEdge **edar = BLI_array_alloca(edar, len);
1050         int i;
1051
1052         for (i = 0, l_iter = l_first; i < len; i++, l_iter = l_iter->next) {
1053                 bmesh_radial_loop_remove((edar[i] = l_iter->e), l_iter);
1054         }
1055
1056         /* actually reverse the loop */
1057         for (i = 0, l_iter = l_first; i < len; i++) {
1058                 BMLoop *oldnext = l_iter->next;
1059                 BMLoop *oldprev = l_iter->prev;
1060                 l_iter->next = oldprev;
1061                 l_iter->prev = oldnext;
1062                 l_iter = oldnext;
1063
1064                 if (cd_loop_mdisp_offset != -1) {
1065                         MDisps *md = BM_ELEM_CD_GET_VOID_P(l_iter, cd_loop_mdisp_offset);
1066                         BKE_mesh_mdisp_flip(md, use_loop_mdisp_flip);
1067                 }
1068         }
1069
1070         /* rebuild radial */
1071         for (i = 0, l_iter = l_first->prev; i < len; i++, l_iter = l_iter->prev) {
1072                 BLI_assert(BM_verts_in_edge(l_iter->v, l_iter->next->v, edar[i]));
1073                 l_iter->e = edar[i];
1074                 bmesh_radial_loop_append(l_iter->e, l_iter);
1075         }
1076
1077 #ifndef NDEBUG
1078         /* validate radial */
1079         for (i = 0, l_iter = l_first; i < len; i++, l_iter = l_iter->next) {
1080                 BM_CHECK_ELEMENT(l_iter);
1081                 BM_CHECK_ELEMENT(l_iter->e);
1082                 BM_CHECK_ELEMENT(l_iter->v);
1083                 BM_CHECK_ELEMENT(l_iter->f);
1084         }
1085
1086         BM_CHECK_ELEMENT(f);
1087 #endif
1088
1089         /* Loop indices are no more valid! */
1090         bm->elem_index_dirty |= BM_LOOP;
1091
1092         return true;
1093 }
1094
1095 /**
1096  * \brief Flip the faces direction
1097  */
1098 bool bmesh_loop_reverse(
1099         BMesh *bm, BMFace *f,
1100         const int cd_loop_mdisp_offset, const bool use_loop_mdisp_flip)
1101 {
1102 #ifdef USE_BMESH_HOLES
1103         return bm_loop_reverse_loop(bm, f, f->loops.first, cd_loop_mdisp_offset, use_loop_mdisp_flip);
1104 #else
1105         return bm_loop_reverse_loop(bm, f, cd_loop_mdisp_offset, use_loop_mdisp_flip);
1106 #endif
1107 }
1108
1109 static void bm_elements_systag_enable(void *veles, int tot, const char api_flag)
1110 {
1111         BMHeader **eles = veles;
1112         int i;
1113
1114         for (i = 0; i < tot; i++) {
1115                 BM_ELEM_API_FLAG_ENABLE((BMElemF *)eles[i], api_flag);
1116         }
1117 }
1118
1119 static void bm_elements_systag_disable(void *veles, int tot, const char api_flag)
1120 {
1121         BMHeader **eles = veles;
1122         int i;
1123
1124         for (i = 0; i < tot; i++) {
1125                 BM_ELEM_API_FLAG_DISABLE((BMElemF *)eles[i], api_flag);
1126         }
1127 }
1128
1129 static int bm_loop_systag_count_radial(BMLoop *l, const char api_flag)
1130 {
1131         BMLoop *l_iter = l;
1132         int i = 0;
1133         do {
1134                 i += BM_ELEM_API_FLAG_TEST(l_iter->f, api_flag) ? 1 : 0;
1135         } while ((l_iter = l_iter->radial_next) != l);
1136
1137         return i;
1138 }
1139
1140 static int UNUSED_FUNCTION(bm_vert_systag_count_disk)(BMVert *v, const char api_flag)
1141 {
1142         BMEdge *e = v->e;
1143         int i = 0;
1144
1145         if (!e)
1146                 return 0;
1147
1148         do {
1149                 i += BM_ELEM_API_FLAG_TEST(e, api_flag) ? 1 : 0;
1150         } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
1151
1152         return i;
1153 }
1154
1155 /**
1156  * Return true when the vertex is manifold,
1157  * attached to faces which are all flagged.
1158  */
1159 static bool bm_vert_is_manifold_flagged(BMVert *v, const char api_flag)
1160 {
1161         BMEdge *e = v->e;
1162
1163         if (!e)
1164                 return false;
1165
1166         do {
1167                 BMLoop *l = e->l;
1168
1169                 if (!l) {
1170                         return false;
1171                 }
1172
1173                 if (BM_edge_is_boundary(l->e)) {
1174                         return false;
1175                 }
1176
1177                 do {
1178                         if (!BM_ELEM_API_FLAG_TEST(l->f, api_flag))
1179                                 return false;
1180                 } while ((l = l->radial_next) != e->l);
1181         } while ((e = bmesh_disk_edge_next(e, v)) != v->e);
1182
1183         return true;
1184 }
1185
1186 /* Mid-level Topology Manipulation Functions */
1187
1188 /**
1189  * \brief Join Connected Faces
1190  *
1191  * Joins a collected group of faces into one. Only restriction on
1192  * the input data is that the faces must be connected to each other.
1193  *
1194  * \return The newly created combine BMFace.
1195  *
1196  * \note If a pair of faces share multiple edges,
1197  * the pair of faces will be joined at every edge.
1198  *
1199  * \note this is a generic, flexible join faces function,
1200  * almost everything uses this, including #BM_faces_join_pair
1201  */
1202 BMFace *BM_faces_join(BMesh *bm, BMFace **faces, int totface, const bool do_del)
1203 {
1204         BMFace *f, *f_new;
1205 #ifdef USE_BMESH_HOLES
1206         BMLoopList *lst;
1207         ListBase holes = {NULL, NULL};
1208 #endif
1209         BMLoop *l_iter;
1210         BMLoop *l_first;
1211         BMEdge **edges = NULL;
1212         BMEdge **deledges = NULL;
1213         BMVert **delverts = NULL;
1214         BLI_array_staticdeclare(edges,    BM_DEFAULT_NGON_STACK_SIZE);
1215         BLI_array_staticdeclare(deledges, BM_DEFAULT_NGON_STACK_SIZE);
1216         BLI_array_staticdeclare(delverts, BM_DEFAULT_NGON_STACK_SIZE);
1217         BMVert *v1 = NULL, *v2 = NULL;
1218         int i;
1219         const int cd_loop_mdisp_offset = CustomData_get_offset(&bm->ldata, CD_MDISPS);
1220
1221         if (UNLIKELY(!totface)) {
1222                 BMESH_ASSERT(0);
1223                 return NULL;
1224         }
1225
1226         if (totface == 1)
1227                 return faces[0];
1228
1229         bm_elements_systag_enable(faces, totface, _FLAG_JF);
1230
1231         for (i = 0; i < totface; i++) {
1232                 f = faces[i];
1233                 l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1234                 do {
1235                         int rlen = bm_loop_systag_count_radial(l_iter, _FLAG_JF);
1236
1237                         if (rlen > 2) {
1238                                 /* Input faces do not form a contiguous manifold region */
1239                                 goto error;
1240                         }
1241                         else if (rlen == 1) {
1242                                 BLI_array_append(edges, l_iter->e);
1243
1244                                 if (!v1) {
1245                                         v1 = l_iter->v;
1246                                         v2 = BM_edge_other_vert(l_iter->e, l_iter->v);
1247                                 }
1248                         }
1249                         else if (rlen == 2) {
1250                                 const bool d1 = bm_vert_is_manifold_flagged(l_iter->e->v1, _FLAG_JF);
1251                                 const bool d2 = bm_vert_is_manifold_flagged(l_iter->e->v2, _FLAG_JF);
1252
1253                                 if (!d1 && !d2 && !BM_ELEM_API_FLAG_TEST(l_iter->e, _FLAG_JF)) {
1254                                         /* don't remove an edge it makes up the side of another face
1255                                          * else this will remove the face as well - campbell */
1256                                         if (!BM_edge_face_count_is_over(l_iter->e, 2)) {
1257                                                 if (do_del) {
1258                                                         BLI_array_append(deledges, l_iter->e);
1259                                                 }
1260                                                 BM_ELEM_API_FLAG_ENABLE(l_iter->e, _FLAG_JF);
1261                                         }
1262                                 }
1263                                 else {
1264                                         if (d1 && !BM_ELEM_API_FLAG_TEST(l_iter->e->v1, _FLAG_JF)) {
1265                                                 if (do_del) {
1266                                                         BLI_array_append(delverts, l_iter->e->v1);
1267                                                 }
1268                                                 BM_ELEM_API_FLAG_ENABLE(l_iter->e->v1, _FLAG_JF);
1269                                         }
1270
1271                                         if (d2 && !BM_ELEM_API_FLAG_TEST(l_iter->e->v2, _FLAG_JF)) {
1272                                                 if (do_del) {
1273                                                         BLI_array_append(delverts, l_iter->e->v2);
1274                                                 }
1275                                                 BM_ELEM_API_FLAG_ENABLE(l_iter->e->v2, _FLAG_JF);
1276                                         }
1277                                 }
1278                         }
1279                 } while ((l_iter = l_iter->next) != l_first);
1280
1281 #ifdef USE_BMESH_HOLES
1282                 for (lst = f->loops.first; lst; lst = lst->next) {
1283                         if (lst == f->loops.first) {
1284                                 continue;
1285                         }
1286
1287                         BLI_remlink(&f->loops, lst);
1288                         BLI_addtail(&holes, lst);
1289                 }
1290 #endif
1291
1292         }
1293
1294         /* create region face */
1295         f_new = BLI_array_count(edges) ?
1296                 BM_face_create_ngon(bm, v1, v2, edges, BLI_array_count(edges), faces[0], BM_CREATE_NOP) : NULL;
1297         if (UNLIKELY(f_new == NULL)) {
1298                 /* Invalid boundary region to join faces */
1299                 goto error;
1300         }
1301
1302         /* copy over loop data */
1303         l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
1304         do {
1305                 BMLoop *l2 = l_iter->radial_next;
1306
1307                 do {
1308                         if (BM_ELEM_API_FLAG_TEST(l2->f, _FLAG_JF))
1309                                 break;
1310                         l2 = l2->radial_next;
1311                 } while (l2 != l_iter);
1312
1313                 if (l2 != l_iter) {
1314                         /* loops share an edge, shared vert depends on winding */
1315                         if (l2->v != l_iter->v) {
1316                                 l2 = l2->next;
1317                         }
1318                         BLI_assert(l_iter->v == l2->v);
1319
1320                         BM_elem_attrs_copy(bm, bm, l2, l_iter);
1321                 }
1322         } while ((l_iter = l_iter->next) != l_first);
1323
1324 #ifdef USE_BMESH_HOLES
1325         /* add holes */
1326         BLI_movelisttolist(&f_new->loops, &holes);
1327 #endif
1328
1329         /* update loop face pointer */
1330 #ifdef USE_BMESH_HOLES
1331         for (lst = f_new->loops.first; lst; lst = lst->next)
1332 #endif
1333         {
1334 #ifdef USE_BMESH_HOLES
1335                 l_iter = l_first = lst->first;
1336 #else
1337                 l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
1338 #endif
1339                 do {
1340                         l_iter->f = f_new;
1341                 } while ((l_iter = l_iter->next) != l_first);
1342         }
1343
1344         bm_elements_systag_disable(faces, totface, _FLAG_JF);
1345         BM_ELEM_API_FLAG_DISABLE(f_new, _FLAG_JF);
1346
1347         /* handle multi-res data */
1348         if (cd_loop_mdisp_offset != -1) {
1349                 float f_center[3];
1350                 float (*faces_center)[3] = BLI_array_alloca(faces_center, totface);
1351
1352                 BM_face_calc_center_mean(f_new, f_center);
1353                 for (i = 0; i < totface; i++) {
1354                         BM_face_calc_center_mean(faces[i], faces_center[i]);
1355                 }
1356
1357                 l_iter = l_first = BM_FACE_FIRST_LOOP(f_new);
1358                 do {
1359                         for (i = 0; i < totface; i++) {
1360                                 BM_loop_interp_multires_ex(bm, l_iter, faces[i], f_center, faces_center[i], cd_loop_mdisp_offset);
1361                         }
1362                 } while ((l_iter = l_iter->next) != l_first);
1363         }
1364
1365         /* delete old geometry */
1366         if (do_del) {
1367                 for (i = 0; i < BLI_array_count(deledges); i++) {
1368                         BM_edge_kill(bm, deledges[i]);
1369                 }
1370
1371                 for (i = 0; i < BLI_array_count(delverts); i++) {
1372                         BM_vert_kill(bm, delverts[i]);
1373                 }
1374         }
1375         else {
1376                 /* otherwise we get both old and new faces */
1377                 for (i = 0; i < totface; i++) {
1378                         BM_face_kill(bm, faces[i]);
1379                 }
1380         }
1381
1382         BLI_array_free(edges);
1383         BLI_array_free(deledges);
1384         BLI_array_free(delverts);
1385
1386         BM_CHECK_ELEMENT(f_new);
1387         return f_new;
1388
1389 error:
1390         bm_elements_systag_disable(faces, totface, _FLAG_JF);
1391         BLI_array_free(edges);
1392         BLI_array_free(deledges);
1393         BLI_array_free(delverts);
1394
1395         return NULL;
1396 }
1397
1398 static BMFace *bm_face_create__sfme(BMesh *bm, BMFace *f_example)
1399 {
1400         BMFace *f;
1401 #ifdef USE_BMESH_HOLES
1402         BMLoopList *lst;
1403 #endif
1404
1405         f = bm_face_create__internal(bm);
1406
1407 #ifdef USE_BMESH_HOLES
1408         lst = BLI_mempool_calloc(bm->looplistpool);
1409         BLI_addtail(&f->loops, lst);
1410 #endif
1411
1412 #ifdef USE_BMESH_HOLES
1413         f->totbounds = 1;
1414 #endif
1415
1416         BM_elem_attrs_copy(bm, bm, f_example, f);
1417
1418         return f;
1419 }
1420
1421 /**
1422  * \brief Split Face Make Edge (SFME)
1423  *
1424  * \warning this is a low level function, most likely you want to use #BM_face_split()
1425  *
1426  * Takes as input two vertices in a single face. An edge is created which divides the original face
1427  * into two distinct regions. One of the regions is assigned to the original face and it is closed off.
1428  * The second region has a new face assigned to it.
1429  *
1430  * \par Examples:
1431  * <pre>
1432  *     Before:               After:
1433  *      +--------+           +--------+
1434  *      |        |           |        |
1435  *      |        |           |   f1   |
1436  *     v1   f1   v2          v1======v2
1437  *      |        |           |   f2   |
1438  *      |        |           |        |
1439  *      +--------+           +--------+
1440  * </pre>
1441  *
1442  * \note the input vertices can be part of the same edge. This will
1443  * result in a two edged face. This is desirable for advanced construction
1444  * tools and particularly essential for edge bevel. Because of this it is
1445  * up to the caller to decide what to do with the extra edge.
1446  *
1447  * \note If \a holes is NULL, then both faces will lose
1448  * all holes from the original face.  Also, you cannot split between
1449  * a hole vert and a boundary vert; that case is handled by higher-
1450  * level wrapping functions (when holes are fully implemented, anyway).
1451  *
1452  * \note that holes represents which holes goes to the new face, and of
1453  * course this requires removing them from the existing face first, since
1454  * you cannot have linked list links inside multiple lists.
1455  *
1456  * \return A BMFace pointer
1457  */
1458 BMFace *bmesh_sfme(
1459         BMesh *bm, BMFace *f, BMLoop *l_v1, BMLoop *l_v2,
1460         BMLoop **r_l,
1461 #ifdef USE_BMESH_HOLES
1462         ListBase *holes,
1463 #endif
1464         BMEdge *e_example,
1465         const bool no_double)
1466 {
1467 #ifdef USE_BMESH_HOLES
1468         BMLoopList *lst, *lst2;
1469 #else
1470         int first_loop_f1;
1471 #endif
1472
1473         BMFace *f2;
1474         BMLoop *l_iter, *l_first;
1475         BMLoop *l_f1 = NULL, *l_f2 = NULL;
1476         BMEdge *e;
1477         BMVert *v1 = l_v1->v, *v2 = l_v2->v;
1478         int f1len, f2len;
1479
1480         BLI_assert(f == l_v1->f && f == l_v2->f);
1481
1482         /* allocate new edge between v1 and v2 */
1483         e = BM_edge_create(bm, v1, v2, e_example, no_double ? BM_CREATE_NO_DOUBLE : BM_CREATE_NOP);
1484
1485         f2 = bm_face_create__sfme(bm, f);
1486         l_f1 = bm_loop_create(bm, v2, e, f, l_v2, 0);
1487         l_f2 = bm_loop_create(bm, v1, e, f2, l_v1, 0);
1488
1489         l_f1->prev = l_v2->prev;
1490         l_f2->prev = l_v1->prev;
1491         l_v2->prev->next = l_f1;
1492         l_v1->prev->next = l_f2;
1493
1494         l_f1->next = l_v1;
1495         l_f2->next = l_v2;
1496         l_v1->prev = l_f1;
1497         l_v2->prev = l_f2;
1498
1499 #ifdef USE_BMESH_HOLES
1500         lst = f->loops.first;
1501         lst2 = f2->loops.first;
1502
1503         lst2->first = lst2->last = l_f2;
1504         lst->first = lst->last = l_f1;
1505 #else
1506         /* find which of the faces the original first loop is in */
1507         l_iter = l_first = l_f1;
1508         first_loop_f1 = 0;
1509         do {
1510                 if (l_iter == f->l_first)
1511                         first_loop_f1 = 1;
1512         } while ((l_iter = l_iter->next) != l_first);
1513
1514         if (first_loop_f1) {
1515                 /* original first loop was in f1, find a suitable first loop for f2
1516                  * which is as similar as possible to f1. the order matters for tools
1517                  * such as duplifaces. */
1518                 if (f->l_first->prev == l_f1)
1519                         f2->l_first = l_f2->prev;
1520                 else if (f->l_first->next == l_f1)
1521                         f2->l_first = l_f2->next;
1522                 else
1523                         f2->l_first = l_f2;
1524         }
1525         else {
1526                 /* original first loop was in f2, further do same as above */
1527                 f2->l_first = f->l_first;
1528
1529                 if (f->l_first->prev == l_f2)
1530                         f->l_first = l_f1->prev;
1531                 else if (f->l_first->next == l_f2)
1532                         f->l_first = l_f1->next;
1533                 else
1534                         f->l_first = l_f1;
1535         }
1536 #endif
1537
1538         /* validate both loop */
1539         /* I don't know how many loops are supposed to be in each face at this point! FIXME */
1540
1541         /* go through all of f2's loops and make sure they point to it properly */
1542         l_iter = l_first = BM_FACE_FIRST_LOOP(f2);
1543         f2len = 0;
1544         do {
1545                 l_iter->f = f2;
1546                 f2len++;
1547         } while ((l_iter = l_iter->next) != l_first);
1548
1549         /* link up the new loops into the new edges radial */
1550         bmesh_radial_loop_append(e, l_f1);
1551         bmesh_radial_loop_append(e, l_f2);
1552
1553         f2->len = f2len;
1554
1555         f1len = 0;
1556         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
1557         do {
1558                 f1len++;
1559         } while ((l_iter = l_iter->next) != l_first);
1560
1561         f->len = f1len;
1562
1563         if (r_l) *r_l = l_f2;
1564
1565 #ifdef USE_BMESH_HOLES
1566         if (holes) {
1567                 BLI_movelisttolist(&f2->loops, holes);
1568         }
1569         else {
1570                 /* this code is not significant until holes actually work */
1571                 //printf("warning: call to split face euler without holes argument; holes will be tossed.\n");
1572                 for (lst = f->loops.last; lst != f->loops.first; lst = lst2) {
1573                         lst2 = lst->prev;
1574                         BLI_mempool_free(bm->looplistpool, lst);
1575                 }
1576         }
1577 #endif
1578
1579         BM_CHECK_ELEMENT(e);
1580         BM_CHECK_ELEMENT(f);
1581         BM_CHECK_ELEMENT(f2);
1582
1583         return f2;
1584 }
1585
1586 /**
1587  * \brief Split Edge Make Vert (SEMV)
1588  *
1589  * Takes \a e edge and splits it into two, creating a new vert.
1590  * \a tv should be one end of \a e : the newly created edge
1591  * will be attached to that end and is returned in \a r_e.
1592  *
1593  * \par Examples:
1594  *
1595  * <pre>
1596  *                     E
1597  *     Before: OV-------------TV
1598  *                 E       RE
1599  *     After:  OV------NV-----TV
1600  * </pre>
1601  *
1602  * \return The newly created BMVert pointer.
1603  */
1604 BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **r_e)
1605 {
1606         BMLoop *l_next;
1607         BMEdge *e_new;
1608         BMVert *v_new, *v_old;
1609 #ifndef NDEBUG
1610         int valence1, valence2;
1611         bool edok;
1612         int i;
1613 #endif
1614
1615         BLI_assert(BM_vert_in_edge(e, tv) != false);
1616
1617         v_old = BM_edge_other_vert(e, tv);
1618
1619 #ifndef NDEBUG
1620         valence1 = bmesh_disk_count(v_old);
1621         valence2 = bmesh_disk_count(tv);
1622 #endif
1623
1624         /* order of 'e_new' verts should match 'e'
1625          * (so extruded faces don't flip) */
1626         v_new = BM_vert_create(bm, tv->co, tv, BM_CREATE_NOP);
1627         e_new = BM_edge_create(bm, tv, v_new, e, BM_CREATE_NOP);
1628
1629         bmesh_disk_edge_remove(e_new, tv);
1630         bmesh_disk_edge_remove(e_new, v_new);
1631
1632         bmesh_disk_vert_replace(e, v_new, tv);
1633
1634         /* add e_new to v_new's disk cycle */
1635         bmesh_disk_edge_append(e_new, v_new);
1636
1637         /* add e_new to tv's disk cycle */
1638         bmesh_disk_edge_append(e_new, tv);
1639
1640 #ifndef NDEBUG
1641         /* verify disk cycles */
1642         edok = bmesh_disk_validate(valence1, v_old->e, v_old);
1643         BMESH_ASSERT(edok != false);
1644         edok = bmesh_disk_validate(valence2, tv->e, tv);
1645         BMESH_ASSERT(edok != false);
1646         edok = bmesh_disk_validate(2, v_new->e, v_new);
1647         BMESH_ASSERT(edok != false);
1648 #endif
1649
1650         /* Split the radial cycle if present */
1651         l_next = e->l;
1652         e->l = NULL;
1653         if (l_next) {
1654                 BMLoop *l_new, *l;
1655 #ifndef NDEBUG
1656                 int radlen = bmesh_radial_length(l_next);
1657 #endif
1658                 bool is_first = true;
1659
1660                 /* Take the next loop. Remove it from radial. Split it. Append to appropriate radials */
1661                 while (l_next) {
1662                         l = l_next;
1663                         l->f->len++;
1664                         l_next = l_next != l_next->radial_next ? l_next->radial_next : NULL;
1665                         bmesh_radial_loop_unlink(l);
1666
1667                         l_new = bm_loop_create(bm, NULL, NULL, l->f, l, 0);
1668                         l_new->prev = l;
1669                         l_new->next = l->next;
1670                         l_new->prev->next = l_new;
1671                         l_new->next->prev = l_new;
1672                         l_new->v = v_new;
1673
1674                         /* assign the correct edge to the correct loop */
1675                         if (BM_verts_in_edge(l_new->v, l_new->next->v, e)) {
1676                                 l_new->e = e;
1677                                 l->e = e_new;
1678
1679                                 /* append l into e_new's rad cycle */
1680                                 if (is_first) {
1681                                         is_first = false;
1682                                         l->radial_next = l->radial_prev = NULL;
1683                                 }
1684
1685                                 bmesh_radial_loop_append(l_new->e, l_new);
1686                                 bmesh_radial_loop_append(l->e, l);
1687                         }
1688                         else if (BM_verts_in_edge(l_new->v, l_new->next->v, e_new)) {
1689                                 l_new->e = e_new;
1690                                 l->e = e;
1691
1692                                 /* append l into e_new's rad cycle */
1693                                 if (is_first) {
1694                                         is_first = false;
1695                                         l->radial_next = l->radial_prev = NULL;
1696                                 }
1697
1698                                 bmesh_radial_loop_append(l_new->e, l_new);
1699                                 bmesh_radial_loop_append(l->e, l);
1700                         }
1701
1702                 }
1703
1704 #ifndef NDEBUG
1705                 /* verify length of radial cycle */
1706                 edok = bmesh_radial_validate(radlen, e->l);
1707                 BMESH_ASSERT(edok != false);
1708                 edok = bmesh_radial_validate(radlen, e_new->l);
1709                 BMESH_ASSERT(edok != false);
1710
1711                 /* verify loop->v and loop->next->v pointers for e */
1712                 for (i = 0, l = e->l; i < radlen; i++, l = l->radial_next) {
1713                         BMESH_ASSERT(l->e == e);
1714                         //BMESH_ASSERT(l->radial_next == l);
1715                         BMESH_ASSERT(!(l->prev->e != e_new && l->next->e != e_new));
1716
1717                         edok = BM_verts_in_edge(l->v, l->next->v, e);
1718                         BMESH_ASSERT(edok != false);
1719                         BMESH_ASSERT(l->v != l->next->v);
1720                         BMESH_ASSERT(l->e != l->next->e);
1721
1722                         /* verify loop cycle for kloop->f */
1723                         BM_CHECK_ELEMENT(l);
1724                         BM_CHECK_ELEMENT(l->v);
1725                         BM_CHECK_ELEMENT(l->e);
1726                         BM_CHECK_ELEMENT(l->f);
1727                 }
1728                 /* verify loop->v and loop->next->v pointers for e_new */
1729                 for (i = 0, l = e_new->l; i < radlen; i++, l = l->radial_next) {
1730                         BMESH_ASSERT(l->e == e_new);
1731                         // BMESH_ASSERT(l->radial_next == l);
1732                         BMESH_ASSERT(!(l->prev->e != e && l->next->e != e));
1733                         edok = BM_verts_in_edge(l->v, l->next->v, e_new);
1734                         BMESH_ASSERT(edok != false);
1735                         BMESH_ASSERT(l->v != l->next->v);
1736                         BMESH_ASSERT(l->e != l->next->e);
1737
1738                         BM_CHECK_ELEMENT(l);
1739                         BM_CHECK_ELEMENT(l->v);
1740                         BM_CHECK_ELEMENT(l->e);
1741                         BM_CHECK_ELEMENT(l->f);
1742                 }
1743 #endif
1744         }
1745
1746         BM_CHECK_ELEMENT(e_new);
1747         BM_CHECK_ELEMENT(v_new);
1748         BM_CHECK_ELEMENT(v_old);
1749         BM_CHECK_ELEMENT(e);
1750         BM_CHECK_ELEMENT(tv);
1751
1752         if (r_e) *r_e = e_new;
1753         return v_new;
1754 }
1755
1756 /**
1757  * \brief Join Edge Kill Vert (JEKV)
1758  *
1759  * Takes an edge \a e_kill and pointer to one of its vertices \a v_kill
1760  * and collapses the edge on that vertex.
1761  *
1762  * \par Examples:
1763  *
1764  * <pre>
1765  *     Before:    e_old  e_kill
1766  *              +-------+-------+
1767  *              |       |       |
1768  *              v_old   v_kill  v_target
1769  *
1770  *     After:           e_old
1771  *              +---------------+
1772  *              |               |
1773  *              v_old           v_target
1774  * </pre>
1775  *
1776  * \par Restrictions:
1777  * KV is a vertex that must have a valance of exactly two. Furthermore
1778  * both edges in KV's disk cycle (OE and KE) must be unique (no double edges).
1779  *
1780  * \return The resulting edge, NULL for failure.
1781  *
1782  * \note This euler has the possibility of creating
1783  * faces with just 2 edges. It is up to the caller to decide what to do with
1784  * these faces.
1785  */
1786 BMEdge *bmesh_jekv(
1787         BMesh *bm, BMEdge *e_kill, BMVert *v_kill,
1788         const bool do_del, const bool check_edge_double,
1789         const bool kill_degenerate_faces)
1790 {
1791         BMEdge *e_old;
1792         BMVert *v_old, *v_target;
1793         BMLoop *l_kill;
1794 #ifndef NDEBUG
1795         int radlen, i;
1796         bool edok;
1797 #endif
1798
1799         BLI_assert(BM_vert_in_edge(e_kill, v_kill));
1800
1801         if (BM_vert_in_edge(e_kill, v_kill) == 0) {
1802                 return NULL;
1803         }
1804
1805         if (bmesh_disk_count_ex(v_kill, 3) == 2) {
1806 #ifndef NDEBUG
1807                 int valence1, valence2;
1808                 BMLoop *l;
1809 #endif
1810
1811                 e_old = bmesh_disk_edge_next(e_kill, v_kill);
1812                 v_target = BM_edge_other_vert(e_kill, v_kill);
1813                 v_old = BM_edge_other_vert(e_old, v_kill);
1814
1815                 /* check for double edges */
1816                 if (BM_verts_in_edge(v_kill, v_target, e_old)) {
1817                         return NULL;
1818                 }
1819                 else {
1820                         BMEdge *e_splice;
1821                         BLI_SMALLSTACK_DECLARE(faces_degenerate, BMFace *);
1822                         BMLoop *l_kill_next;
1823
1824 #ifndef NDEBUG
1825                         /* For verification later, count valence of 'v_old' and 'v_target' */
1826                         valence1 = bmesh_disk_count(v_old);
1827                         valence2 = bmesh_disk_count(v_target);
1828 #endif
1829
1830                         if (check_edge_double) {
1831                                 e_splice = BM_edge_exists(v_target, v_old);
1832                         }
1833
1834                         bmesh_disk_vert_replace(e_old, v_target, v_kill);
1835
1836                         /* remove e_kill from 'v_target's disk cycle */
1837                         bmesh_disk_edge_remove(e_kill, v_target);
1838
1839 #ifndef NDEBUG
1840                         /* deal with radial cycle of e_kill */
1841                         radlen = bmesh_radial_length(e_kill->l);
1842 #endif
1843                         if (e_kill->l) {
1844
1845
1846                                 /* fix the neighboring loops of all loops in e_kill's radial cycle */
1847                                 l_kill = e_kill->l;
1848                                 do {
1849                                         /* relink loops and fix vertex pointer */
1850                                         if (l_kill->next->v == v_kill) {
1851                                                 l_kill->next->v = v_target;
1852                                         }
1853
1854                                         l_kill->next->prev = l_kill->prev;
1855                                         l_kill->prev->next = l_kill->next;
1856                                         if (BM_FACE_FIRST_LOOP(l_kill->f) == l_kill) {
1857                                                 BM_FACE_FIRST_LOOP(l_kill->f) = l_kill->next;
1858                                         }
1859
1860                                         /* fix len attribute of face */
1861                                         l_kill->f->len--;
1862                                         if (kill_degenerate_faces) {
1863                                                 if (l_kill->f->len < 3) {
1864                                                         BLI_SMALLSTACK_PUSH(faces_degenerate, l_kill->f);
1865                                                 }
1866                                         }
1867                                         l_kill_next = l_kill->radial_next;
1868
1869                                         bm_kill_only_loop(bm, l_kill);
1870
1871                                 } while ((l_kill = l_kill_next) != e_kill->l);
1872                                 /* `e_kill->l` is invalid but the edge is freed next. */
1873 #ifndef NDEBUG
1874                                 /* Validate radial cycle of e_old */
1875                                 edok = bmesh_radial_validate(radlen, e_old->l);
1876                                 BMESH_ASSERT(edok != false);
1877 #endif
1878                         }
1879                         /* deallocate edge */
1880                         bm_kill_only_edge(bm, e_kill);
1881
1882                         /* deallocate vertex */
1883                         if (do_del) {
1884                                 bm_kill_only_vert(bm, v_kill);
1885                         }
1886                         else {
1887                                 v_kill->e = NULL;
1888                         }
1889
1890 #ifndef NDEBUG
1891                         /* Validate disk cycle lengths of 'v_old', 'v_target' are unchanged */
1892                         edok = bmesh_disk_validate(valence1, v_old->e, v_old);
1893                         BMESH_ASSERT(edok != false);
1894                         edok = bmesh_disk_validate(valence2, v_target->e, v_target);
1895                         BMESH_ASSERT(edok != false);
1896
1897                         /* Validate loop cycle of all faces attached to 'e_old' */
1898                         for (i = 0, l = e_old->l; i < radlen; i++, l = l->radial_next) {
1899                                 BMESH_ASSERT(l->e == e_old);
1900                                 edok = BM_verts_in_edge(l->v, l->next->v, e_old);
1901                                 BMESH_ASSERT(edok != false);
1902                                 edok = bmesh_loop_validate(l->f);
1903                                 BMESH_ASSERT(edok != false);
1904
1905                                 BM_CHECK_ELEMENT(l);
1906                                 BM_CHECK_ELEMENT(l->v);
1907                                 BM_CHECK_ELEMENT(l->e);
1908                                 BM_CHECK_ELEMENT(l->f);
1909                         }
1910 #endif
1911                         if (check_edge_double) {
1912                                 if (e_splice) {
1913                                         /* removes e_splice */
1914                                         BM_edge_splice(bm, e_old, e_splice);
1915                                 }
1916                         }
1917
1918                         if (kill_degenerate_faces) {
1919                                 BMFace *f_kill;
1920                                 while ((f_kill = BLI_SMALLSTACK_POP(faces_degenerate))) {
1921                                         BM_face_kill(bm, f_kill);
1922                                 }
1923                         }
1924
1925                         BM_CHECK_ELEMENT(v_old);
1926                         BM_CHECK_ELEMENT(v_target);
1927                         BM_CHECK_ELEMENT(e_old);
1928
1929                         return e_old;
1930                 }
1931         }
1932         return NULL;
1933 }
1934
1935 /**
1936  * \brief Join Vert Kill Edge (JVKE)
1937  *
1938  * Collapse an edge, merging surrounding data.
1939  *
1940  * Unlike #BM_vert_collapse_edge & #bmesh_jekv which only handle 2 valence verts,
1941  * this can handle any number of connected edges/faces.
1942  *
1943  * <pre>
1944  * Before: -> After:
1945  * +-+-+-+    +-+-+-+
1946  * | | | |    | \ / |
1947  * +-+-+-+    +--+--+
1948  * | | | |    | / \ |
1949  * +-+-+-+    +-+-+-+
1950  * </pre>
1951  */
1952 BMVert *bmesh_jvke(
1953         BMesh *bm, BMEdge *e_kill, BMVert *v_kill,
1954         const bool do_del, const bool check_edge_double,
1955         const bool kill_degenerate_faces)
1956 {
1957         BLI_SMALLSTACK_DECLARE(faces_degenerate, BMFace *);
1958         BMVert *v_target = BM_edge_other_vert(e_kill, v_kill);
1959
1960         BLI_assert(BM_vert_in_edge(e_kill, v_kill));
1961
1962         if (e_kill->l) {
1963                 BMLoop *l_kill, *l_first, *l_kill_next;
1964                 l_kill = l_first = e_kill->l;
1965                 do {
1966                         /* relink loops and fix vertex pointer */
1967                         if (l_kill->next->v == v_kill) {
1968                                 l_kill->next->v = v_target;
1969                         }
1970
1971                         l_kill->next->prev = l_kill->prev;
1972                         l_kill->prev->next = l_kill->next;
1973                         if (BM_FACE_FIRST_LOOP(l_kill->f) == l_kill) {
1974                                 BM_FACE_FIRST_LOOP(l_kill->f) = l_kill->next;
1975                         }
1976
1977                         /* fix len attribute of face */
1978                         l_kill->f->len--;
1979                         if (kill_degenerate_faces) {
1980                                 if (l_kill->f->len < 3) {
1981                                         BLI_SMALLSTACK_PUSH(faces_degenerate, l_kill->f);
1982                                 }
1983                         }
1984                         l_kill_next = l_kill->radial_next;
1985
1986                         bm_kill_only_loop(bm, l_kill);
1987
1988                 } while ((l_kill = l_kill_next) != l_first);
1989
1990                 e_kill->l = NULL;
1991         }
1992
1993         BM_edge_kill(bm, e_kill);
1994         BM_CHECK_ELEMENT(v_kill);
1995         BM_CHECK_ELEMENT(v_target);
1996
1997         if (v_target->e && v_kill->e) {
1998                 /* inline BM_vert_splice(bm, v_target, v_kill); */
1999                 BMEdge *e;
2000                 while ((e = v_kill->e)) {
2001                         BMEdge *e_target;
2002
2003                         if (check_edge_double) {
2004                                 e_target = BM_edge_exists(v_target, BM_edge_other_vert(e, v_kill));
2005                         }
2006
2007                         bmesh_edge_vert_swap(e, v_target, v_kill);
2008                         BLI_assert(e->v1 != e->v2);
2009
2010                         if (check_edge_double) {
2011                                 if (e_target) {
2012                                         BM_edge_splice(bm, e_target, e);
2013                                 }
2014                         }
2015                 }
2016         }
2017
2018         if (kill_degenerate_faces) {
2019                 BMFace *f_kill;
2020                 while ((f_kill = BLI_SMALLSTACK_POP(faces_degenerate))) {
2021                         BM_face_kill(bm, f_kill);
2022                 }
2023         }
2024
2025         if (do_del) {
2026                 BLI_assert(v_kill->e == NULL);
2027                 bm_kill_only_vert(bm, v_kill);
2028         }
2029
2030         return v_target;
2031 }
2032
2033 /**
2034  * \brief Join Face Kill Edge (JFKE)
2035  *
2036  * Takes two faces joined by a single 2-manifold edge and fuses them together.
2037  * The edge shared by the faces must not be connected to any other edges which have
2038  * Both faces in its radial cycle
2039  *
2040  * \par Examples:
2041  * <pre>
2042  *           A                   B
2043  *      +--------+           +--------+
2044  *      |        |           |        |
2045  *      |   f1   |           |   f1   |
2046  *     v1========v2 = Ok!    v1==V2==v3 == Wrong!
2047  *      |   f2   |           |   f2   |
2048  *      |        |           |        |
2049  *      +--------+           +--------+
2050  * </pre>
2051  *
2052  * In the example A, faces \a f1 and \a f2 are joined by a single edge,
2053  * and the euler can safely be used.
2054  * In example B however, \a f1 and \a f2 are joined by multiple edges and will produce an error.
2055  * The caller in this case should call #bmesh_jekv on the extra edges
2056  * before attempting to fuse \a f1 and \a f2.
2057  *
2058  * \note The order of arguments decides whether or not certain per-face attributes are present
2059  * in the resultant face. For instance vertex winding, material index, smooth flags, etc are inherited
2060  * from \a f1, not \a f2.
2061  *
2062  * \return A BMFace pointer
2063  */
2064 BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e)
2065 {
2066         BMLoop *l_iter, *l_f1 = NULL, *l_f2 = NULL;
2067         int newlen = 0, i, f1len = 0, f2len = 0;
2068         bool edok;
2069         /* can't join a face to itself */
2070         if (f1 == f2) {
2071                 return NULL;
2072         }
2073
2074         /* validate that edge is 2-manifold edge */
2075         if (!BM_edge_is_manifold(e)) {
2076                 return NULL;
2077         }
2078
2079         /* verify that e is in both f1 and f2 */
2080         f1len = f1->len;
2081         f2len = f2->len;
2082
2083         if (!((l_f1 = BM_face_edge_share_loop(f1, e)) &&
2084               (l_f2 = BM_face_edge_share_loop(f2, e))))
2085         {
2086                 return NULL;
2087         }
2088
2089         /* validate direction of f2's loop cycle is compatible */
2090         if (l_f1->v == l_f2->v) {
2091                 return NULL;
2092         }
2093
2094         /* validate that for each face, each vertex has another edge in its disk cycle that is
2095          * not e, and not shared. */
2096         if (BM_edge_in_face(l_f1->next->e, f2) ||
2097             BM_edge_in_face(l_f1->prev->e, f2) ||
2098             BM_edge_in_face(l_f2->next->e, f1) ||
2099             BM_edge_in_face(l_f2->prev->e, f1) )
2100         {
2101                 return NULL;
2102         }
2103
2104         /* validate only one shared edge */
2105         if (BM_face_share_edge_count(f1, f2) > 1) {
2106                 return NULL;
2107         }
2108
2109         /* validate no internal join */
2110         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < f1len; i++, l_iter = l_iter->next) {
2111                 BM_elem_flag_disable(l_iter->v, BM_ELEM_INTERNAL_TAG);
2112         }
2113         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f2); i < f2len; i++, l_iter = l_iter->next) {
2114                 BM_elem_flag_disable(l_iter->v, BM_ELEM_INTERNAL_TAG);
2115         }
2116
2117         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < f1len; i++, l_iter = l_iter->next) {
2118                 if (l_iter != l_f1) {
2119                         BM_elem_flag_enable(l_iter->v, BM_ELEM_INTERNAL_TAG);
2120                 }
2121         }
2122         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f2); i < f2len; i++, l_iter = l_iter->next) {
2123                 if (l_iter != l_f2) {
2124                         /* as soon as a duplicate is found, bail out */
2125                         if (BM_elem_flag_test(l_iter->v, BM_ELEM_INTERNAL_TAG)) {
2126                                 return NULL;
2127                         }
2128                 }
2129         }
2130
2131         /* join the two loop */
2132         l_f1->prev->next = l_f2->next;
2133         l_f2->next->prev = l_f1->prev;
2134
2135         l_f1->next->prev = l_f2->prev;
2136         l_f2->prev->next = l_f1->next;
2137
2138         /* if l_f1 was baseloop, make l_f1->next the base. */
2139         if (BM_FACE_FIRST_LOOP(f1) == l_f1)
2140                 BM_FACE_FIRST_LOOP(f1) = l_f1->next;
2141
2142         /* increase length of f1 */
2143         f1->len += (f2->len - 2);
2144
2145         /* make sure each loop points to the proper face */
2146         newlen = f1->len;
2147         for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f1); i < newlen; i++, l_iter = l_iter->next)
2148                 l_iter->f = f1;
2149
2150         /* remove edge from the disk cycle of its two vertices */
2151         bmesh_disk_edge_remove(l_f1->e, l_f1->e->v1);
2152         bmesh_disk_edge_remove(l_f1->e, l_f1->e->v2);
2153
2154         /* deallocate edge and its two loops as well as f2 */
2155         if (bm->etoolflagpool) {
2156                 BLI_mempool_free(bm->etoolflagpool, ((BMEdge_OFlag *)l_f1->e)->oflags);
2157         }
2158         BLI_mempool_free(bm->epool, l_f1->e);
2159         bm->totedge--;
2160         BLI_mempool_free(bm->lpool, l_f1);
2161         bm->totloop--;
2162         BLI_mempool_free(bm->lpool, l_f2);
2163         bm->totloop--;
2164         if (bm->ftoolflagpool) {
2165                 BLI_mempool_free(bm->ftoolflagpool, ((BMFace_OFlag *)f2)->oflags);
2166         }
2167         BLI_mempool_free(bm->fpool, f2);
2168         bm->totface--;
2169         /* account for both above */
2170         bm->elem_index_dirty |= BM_EDGE | BM_LOOP | BM_FACE;
2171
2172         BM_CHECK_ELEMENT(f1);
2173
2174         /* validate the new loop cycle */
2175         edok = bmesh_loop_validate(f1);
2176         BMESH_ASSERT(edok != false);
2177
2178         return f1;
2179 }
2180
2181 /**
2182  * Check if splicing vertices would create any double edges.
2183  *
2184  * \note assume caller will handle case where verts share an edge.
2185  */
2186 bool BM_vert_splice_check_double(BMVert *v_a, BMVert *v_b)
2187 {
2188         bool is_double = false;
2189
2190         BLI_assert(BM_edge_exists(v_a, v_b) == false);
2191
2192         if (v_a->e && v_b->e) {
2193                 BMEdge *e, *e_first;
2194
2195 #define VERT_VISIT _FLAG_WALK
2196
2197                 /* tag 'v_a' */
2198                 e = e_first = v_a->e;
2199                 do {
2200                         BMVert *v_other = BM_edge_other_vert(e, v_a);
2201                         BLI_assert(!BM_ELEM_API_FLAG_TEST(v_other, VERT_VISIT));
2202                         BM_ELEM_API_FLAG_ENABLE(v_other, VERT_VISIT);
2203                 } while ((e = BM_DISK_EDGE_NEXT(e, v_a)) != e_first);
2204
2205                 /* check 'v_b' connects to 'v_a' edges */
2206                 e = e_first = v_b->e;
2207                 do {
2208                         BMVert *v_other = BM_edge_other_vert(e, v_b);
2209                         if (BM_ELEM_API_FLAG_TEST(v_other, VERT_VISIT)) {
2210                                 is_double = true;
2211                                 break;
2212                         }
2213                 } while ((e = BM_DISK_EDGE_NEXT(e, v_b)) != e_first);
2214
2215                 /* cleanup */
2216                 e = e_first = v_a->e;
2217                 do {
2218                         BMVert *v_other = BM_edge_other_vert(e, v_a);
2219                         BLI_assert(BM_ELEM_API_FLAG_TEST(v_other, VERT_VISIT));
2220                         BM_ELEM_API_FLAG_DISABLE(v_other, VERT_VISIT);
2221                 } while ((e = BM_DISK_EDGE_NEXT(e, v_a)) != e_first);
2222
2223 #undef VERT_VISIT
2224
2225         }
2226
2227         return is_double;
2228 }
2229
2230 /**
2231  * \brief Splice Vert
2232  *
2233  * Merges two verts into one
2234  * (\a v_src into \a v_dst, removing \a v_src).
2235  *
2236  * \return Success
2237  *
2238  * \warning This doesn't work for collapsing edges,
2239  * where \a v and \a vtarget are connected by an edge
2240  * (assert checks for this case).
2241  */
2242 bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src)
2243 {
2244         BMEdge *e;
2245
2246         /* verts already spliced */
2247         if (v_src == v_dst) {
2248                 return false;
2249         }
2250
2251         BLI_assert(BM_vert_pair_share_face_check(v_src, v_dst) == false);
2252
2253         /* move all the edges from 'v_src' disk to 'v_dst' */
2254         while ((e = v_src->e)) {
2255                 bmesh_edge_vert_swap(e, v_dst, v_src);
2256                 BLI_assert(e->v1 != e->v2);
2257         }
2258
2259         BM_CHECK_ELEMENT(v_src);
2260         BM_CHECK_ELEMENT(v_dst);
2261
2262         /* 'v_src' is unused now, and can be killed */
2263         BM_vert_kill(bm, v_src);
2264
2265         return true;
2266 }
2267
2268
2269 /** \name BM_vert_separate, bmesh_vert_separate and friends
2270  * \{ */
2271
2272 /* BM_edge_face_count(e) >= 1 */
2273 BLI_INLINE bool bm_edge_supports_separate(const BMEdge *e)
2274 {
2275         return (e->l && e->l->radial_next != e->l);
2276 }
2277
2278 /**
2279  * \brief Separate Vert
2280  *
2281  * Separates all disjoint fans that meet at a vertex, making a unique
2282  * vertex for each region. returns an array of all resulting vertices.
2283  *
2284  * \note this is a low level function, bm_edge_separate needs to run on edges first
2285  * or, the faces sharing verts must not be sharing edges for them to split at least.
2286  *
2287  * \return Success
2288  */
2289 void bmesh_vert_separate(
2290         BMesh *bm, BMVert *v, BMVert ***r_vout, int *r_vout_len,
2291         const bool copy_select)
2292 {
2293         int v_edges_num = 0;
2294
2295         /* Detailed notes on array use since this is stack memory, we have to be careful */
2296
2297         /* newly created vertices, only use when 'r_vout' is set
2298          * (total size will be number of fans) */
2299         BLI_SMALLSTACK_DECLARE(verts_new, BMVert *);
2300         /* fill with edges from the face-fan, clearing on completion
2301          * (total size will be max fan edge count) */
2302         BLI_SMALLSTACK_DECLARE(edges, BMEdge *);
2303         /* temp store edges to walk over when filling 'edges',
2304          * (total size will be max radial edges of any edge) */
2305         BLI_SMALLSTACK_DECLARE(edges_search, BMEdge *);
2306
2307         /* number of resulting verts, include self */
2308         int verts_num = 1;
2309         /* track the total number of edges handled, so we know when we've found the last fan */
2310         int edges_found = 0;
2311
2312 #define EDGE_VISIT _FLAG_WALK
2313
2314         /* count and flag at once */
2315         if (v->e) {
2316                 BMEdge *e_first, *e_iter;
2317                 e_iter = e_first = v->e;
2318                 do {
2319                         v_edges_num += 1;
2320
2321                         BLI_assert(!BM_ELEM_API_FLAG_TEST(e_iter, EDGE_VISIT));
2322                         BM_ELEM_API_FLAG_ENABLE(e_iter, EDGE_VISIT);
2323                 } while ((e_iter = bmesh_disk_edge_next(e_iter, v)) != e_first);
2324         }
2325
2326         while (true) {
2327                 /* Considering only edges and faces incident on vertex v, walk
2328                  * the edges & collect in the 'edges' list for splitting */
2329
2330                 BMEdge *e = v->e;
2331                 BM_ELEM_API_FLAG_DISABLE(e, EDGE_VISIT);
2332
2333                 do {
2334                         BLI_assert(!BM_ELEM_API_FLAG_TEST(e, EDGE_VISIT));
2335                         BLI_SMALLSTACK_PUSH(edges, e);
2336                         edges_found += 1;
2337
2338                         if (e->l) {
2339                                 BMLoop *l_iter, *l_first;
2340                                 l_iter = l_first = e->l;
2341                                 do {
2342                                         BMLoop *l_adjacent = (l_iter->v == v) ? l_iter->prev : l_iter->next;
2343                                         BLI_assert(BM_vert_in_edge(l_adjacent->e, v));
2344                                         if (BM_ELEM_API_FLAG_TEST(l_adjacent->e, EDGE_VISIT)) {
2345                                                 BM_ELEM_API_FLAG_DISABLE(l_adjacent->e, EDGE_VISIT);
2346                                                 BLI_SMALLSTACK_PUSH(edges_search, l_adjacent->e);
2347                                         }
2348                                 } while ((l_iter = l_iter->radial_next) != l_first);
2349                         }
2350                 } while ((e = BLI_SMALLSTACK_POP(edges_search)));
2351
2352                 /* now we have all edges connected to 'v->e' */
2353
2354                 BLI_assert(edges_found <= v_edges_num);
2355
2356                 if (edges_found == v_edges_num) {
2357                         /* We're done! The remaining edges in 'edges' form the last fan,
2358                          * which can be left as is.
2359                          * if 'edges' were alloc'd it'd be freed here. */
2360                         break;
2361                 }
2362                 else {
2363                         BMVert *v_new;
2364
2365                         v_new = BM_vert_create(bm, v->co, v, BM_CREATE_NOP);
2366                         if (copy_select) {
2367                                 BM_elem_select_copy(bm, bm, v_new, v);
2368                         }
2369
2370                         while ((e = BLI_SMALLSTACK_POP(edges))) {
2371                                 bmesh_edge_vert_swap(e, v_new, v);
2372                         }
2373
2374                         if (r_vout) {
2375                                 BLI_SMALLSTACK_PUSH(verts_new, v_new);
2376                         }
2377                         verts_num += 1;
2378                 }
2379         }
2380
2381 #undef EDGE_VISIT
2382
2383         /* flags are clean now, handle return values */
2384
2385         if (r_vout_len != NULL) {
2386                 *r_vout_len = verts_num;
2387         }
2388
2389         if (r_vout != NULL) {
2390                 BMVert **verts;
2391
2392                 verts = MEM_mallocN(sizeof(BMVert *) * verts_num, __func__);
2393                 *r_vout = verts;
2394
2395                 verts[0] = v;
2396                 BLI_SMALLSTACK_AS_TABLE(verts_new, &verts[1]);
2397         }
2398 }
2399
2400 /**
2401  * Utility function for #BM_vert_separate
2402  *
2403  * Takes a list of edges, which have been split from their original.
2404  *
2405  * Any edges which failed to split off in #bmesh_vert_separate will be merged back into the original edge.
2406  *
2407  * \param edges_separate
2408  * A list-of-lists, each list is from a single original edge (the first edge is the original),
2409  * Check for duplicates (not just with the first) but between all.
2410  * This is O(n2) but radial edges are very rarely >2 and almost never >~10.
2411  *
2412  * \note typically its best to avoid creating the data in the first place,
2413  * but inspecting all loops connectivity is quite involved.
2414  *
2415  * \note this function looks like it could become slow,
2416  * but in common cases its only going to iterate a few times.
2417  */
2418 static void bmesh_vert_separate__cleanup(BMesh *bm, LinkNode *edges_separate)
2419 {
2420         do {
2421                 LinkNode *n_orig = edges_separate->link;
2422                 do {
2423                         BMEdge *e_orig = n_orig->link;
2424                         LinkNode *n_step = n_orig->next;
2425                         LinkNode *n_prev = n_orig;
2426                         do {
2427                                 BMEdge *e = n_step->link;
2428                                 BLI_assert(e != e_orig);
2429                                 if ((e->v1 == e_orig->v1) && (e->v2 == e_orig->v2)) {
2430                                         BM_edge_splice(bm, e_orig, e);
2431                                         n_prev->next = n_step->next;
2432                                         n_step = n_prev;
2433                                 }
2434                         } while ((void)
2435                                  (n_prev = n_step),
2436                                  (n_step = n_step->next));
2437
2438                 } while ((n_orig = n_orig->next) && n_orig->next);
2439         } while ((edges_separate = edges_separate->next));
2440 }
2441
2442 /**
2443  * High level function which wraps both #bmesh_vert_separate and #bmesh_edge_separate
2444  */
2445 void BM_vert_separate(
2446         BMesh *bm, BMVert *v,
2447         BMEdge **e_in, int e_in_len,
2448         const bool copy_select,
2449         BMVert ***r_vout, int *r_vout_len)
2450 {
2451         LinkNode *edges_separate = NULL;
2452         int i;
2453
2454         for (i = 0; i < e_in_len; i++) {
2455                 BMEdge *e = e_in[i];
2456                 if (bm_edge_supports_separate(e)) {
2457                         LinkNode *edges_orig = NULL;
2458                         do {
2459                                 BMLoop *l_sep = e->l;
2460                                 bmesh_edge_separate(bm, e, l_sep, copy_select);
2461                                 BLI_linklist_prepend_alloca(&edges_orig, l_sep->e);
2462                                 BLI_assert(e != l_sep->e);
2463                         } while (bm_edge_supports_separate(e));
2464                         BLI_linklist_prepend_alloca(&edges_orig, e);
2465                         BLI_linklist_prepend_alloca(&edges_separate, edges_orig);
2466                 }
2467         }
2468
2469         bmesh_vert_separate(bm, v, r_vout, r_vout_len, copy_select);
2470
2471         if (edges_separate) {
2472                 bmesh_vert_separate__cleanup(bm, edges_separate);
2473         }
2474 }
2475
2476
2477 /**
2478  * A version of #BM_vert_separate which takes a flag.
2479  */
2480 void BM_vert_separate_hflag(
2481         BMesh *bm, BMVert *v,
2482         const char hflag,
2483         const bool copy_select,
2484         BMVert ***r_vout, int *r_vout_len)
2485 {
2486         LinkNode *edges_separate = NULL;
2487         BMEdge *e_iter, *e_first;
2488
2489         e_iter = e_first = v->e;
2490         do {
2491                 if (BM_elem_flag_test(e_iter, hflag)) {
2492                         BMEdge *e = e_iter;
2493                         if (bm_edge_supports_separate(e)) {
2494                                 LinkNode *edges_orig = NULL;
2495                                 do {
2496                                         BMLoop *l_sep = e->l;
2497                                         bmesh_edge_separate(bm, e, l_sep, copy_select);
2498                                         /* trick to avoid looping over separated edges */
2499                                         if (edges_separate == NULL && edges_orig == NULL) {
2500                                                 e_first = l_sep->e;
2501                                         }
2502                                         BLI_linklist_prepend_alloca(&edges_orig, l_sep->e);
2503                                         BLI_assert(e != l_sep->e);
2504                                 } while (bm_edge_supports_separate(e));
2505                                 BLI_linklist_prepend_alloca(&edges_orig, e);
2506                                 BLI_linklist_prepend_alloca(&edges_separate, edges_orig);
2507                         }
2508                 }
2509         } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != e_first);
2510
2511         bmesh_vert_separate(bm, v, r_vout, r_vout_len, copy_select);
2512
2513         if (edges_separate) {
2514                 bmesh_vert_separate__cleanup(bm, edges_separate);
2515         }
2516 }
2517
2518 void BM_vert_separate_wire_hflag(
2519         BMesh *UNUSED(bm), BMVert *v_dst, BMVert *v_src,
2520         const char hflag)
2521 {
2522         LinkNode *edges_hflag = NULL;
2523         BMEdge *e_iter, *e_first;
2524
2525         e_iter = e_first = v_src->e;
2526         do {
2527                 if (BM_elem_flag_test(e_iter, hflag)) {
2528                         if (BM_edge_is_wire(e_iter)) {
2529                                 BLI_linklist_prepend_alloca(&edges_hflag, e_iter);
2530                         }
2531                 }
2532         } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_src)) != e_first);
2533
2534         if (edges_hflag) {
2535                 do {
2536                         e_iter = edges_hflag->link;
2537                         bmesh_disk_vert_replace(e_iter, v_dst, v_src);
2538                 } while ((edges_hflag = edges_hflag->next));
2539         }
2540 }
2541
2542 /** \} */
2543
2544
2545 /**
2546  * \brief Splice Edge
2547  *
2548  * Splice two unique edges which share the same two vertices into one edge.
2549  *  (\a e_src into \a e_dst, removing e_src).
2550  *
2551  * \return Success
2552  *
2553  * \note Edges must already have the same vertices.
2554  */
2555 bool BM_edge_splice(BMesh *bm, BMEdge *e_dst, BMEdge *e_src)
2556 {
2557         BMLoop *l;
2558
2559         if (!BM_vert_in_edge(e_src, e_dst->v1) || !BM_vert_in_edge(e_src, e_dst->v2)) {
2560                 /* not the same vertices can't splice */
2561
2562                 /* the caller should really make sure this doesn't happen ever
2563                  * so assert on release builds */
2564                 BLI_assert(0);
2565
2566                 return false;
2567         }
2568
2569         while (e_src->l) {
2570                 l = e_src->l;
2571                 BLI_assert(BM_vert_in_edge(e_dst, l->v));
2572                 BLI_assert(BM_vert_in_edge(e_dst, l->next->v));
2573                 bmesh_radial_loop_remove(e_src, l);
2574                 bmesh_radial_loop_append(e_dst, l);
2575         }
2576
2577         BLI_assert(bmesh_radial_length(e_src->l) == 0);
2578
2579         BM_CHECK_ELEMENT(e_src);
2580         BM_CHECK_ELEMENT(e_dst);
2581
2582         /* removes from disks too */
2583         BM_edge_kill(bm, e_src);
2584
2585         return true;
2586 }
2587
2588 /**
2589  * \brief Separate Edge
2590  *
2591  * Separates a single edge into two edge: the original edge and
2592  * a new edge that has only \a l_sep in its radial.
2593  *
2594  * \return Success
2595  *
2596  * \note Does nothing if \a l_sep is already the only loop in the
2597  * edge radial.
2598  */
2599 void bmesh_edge_separate(
2600         BMesh *bm, BMEdge *e, BMLoop *l_sep,
2601         const bool copy_select)
2602 {
2603         BMEdge *e_new;
2604 #ifndef NDEBUG
2605         const int radlen = bmesh_radial_length(e->l);
2606 #endif
2607
2608         BLI_assert(l_sep->e == e);
2609         BLI_assert(e->l);
2610
2611         if (BM_edge_is_boundary(e)) {
2612                 BLI_assert(0); /* no cut required */
2613                 return;
2614         }
2615
2616         if (l_sep == e->l) {
2617                 e->l = l_sep->radial_next;
2618         }
2619
2620         e_new = BM_edge_create(bm, e->v1, e->v2, e, BM_CREATE_NOP);
2621         bmesh_radial_loop_remove(e, l_sep);
2622         bmesh_radial_loop_append(e_new, l_sep);
2623         l_sep->e = e_new;
2624
2625         if (copy_select) {
2626                 BM_elem_select_copy(bm, bm, e_new, e);
2627         }
2628
2629         BLI_assert(bmesh_radial_length(e->l) == radlen - 1);
2630         BLI_assert(bmesh_radial_length(e_new->l) == 1);
2631
2632         BM_CHECK_ELEMENT(e_new);
2633         BM_CHECK_ELEMENT(e);
2634 }
2635
2636 /**
2637  * \brief Un-glue Region Make Vert (URMV)
2638  *
2639  * Disconnects a face from its vertex fan at loop \a l_sep
2640  *
2641  * \return The newly created BMVert
2642  *
2643  * \note Will be a no-op and return original vertex if only two edges at that vertex.
2644  */
2645 BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *l_sep)
2646 {
2647         BMVert *v_new = NULL;
2648         BMVert *v_sep = l_sep->v;
2649         BMEdge *e_iter;
2650         BMEdge *edges[2];
2651         int i;
2652
2653         /* peel the face from the edge radials on both sides of the
2654          * loop vert, disconnecting the face from its fan */
2655         if (!BM_edge_is_boundary(l_sep->e))
2656                 bmesh_edge_separate(bm, l_sep->e, l_sep, false);
2657         if (!BM_edge_is_boundary(l_sep->prev->e))
2658                 bmesh_edge_separate(bm, l_sep->prev->e, l_sep->prev, false);
2659
2660         /* do inline, below */
2661 #if 0
2662         if (BM_vert_edge_count_is_equal(v_sep, 2)) {
2663                 return v_sep;
2664         }
2665 #endif
2666
2667         /* Search for an edge unattached to this loop */
2668         e_iter = v_sep->e;
2669         while (!ELEM(e_iter, l_sep->e, l_sep->prev->e)) {
2670                 e_iter = bmesh_disk_edge_next(e_iter, v_sep);
2671
2672                 /* We've come back around to the initial edge, all touch this loop.
2673                  * If there are still only two edges out of v_sep,
2674                  * then this whole URMV was just a no-op, so exit now. */
2675                 if (e_iter == v_sep->e) {
2676                         BLI_assert(BM_vert_edge_count_is_equal(v_sep, 2));
2677                         return v_sep;
2678                 }
2679         }
2680
2681         v_sep->e = l_sep->e;
2682
2683         v_new = BM_vert_create(bm, v_sep->co, v_sep, BM_CREATE_NOP);
2684
2685         edges[0] = l_sep->e;
2686         edges[1] = l_sep->prev->e;
2687
2688         for (i = 0; i < ARRAY_SIZE(edges); i++) {
2689                 BMEdge *e = edges[i];
2690                 bmesh_edge_vert_swap(e, v_new, v_sep);
2691         }
2692
2693         BLI_assert(v_sep != l_sep->v);
2694         BLI_assert(v_sep->e != l_sep->v->e);
2695
2696         BM_CHECK_ELEMENT(l_sep);
2697         BM_CHECK_ELEMENT(v_sep);
2698         BM_CHECK_ELEMENT(edges[0]);
2699         BM_CHECK_ELEMENT(edges[1]);
2700         BM_CHECK_ELEMENT(v_new);
2701
2702         return v_new;
2703 }
2704
2705 /**
2706  * A version of #bmesh_urmv_loop that disconnects multiple loops at once.
2707  *
2708  * Handles the task of finding fans boundaries.
2709  */
2710 BMVert *bmesh_urmv_loop_multi(
2711         BMesh *bm, BMLoop **larr, int larr_len)
2712 {
2713         BMVert *v_sep = larr[0]->v;
2714         BMVert *v_new;
2715         int i;
2716         bool is_mixed_any = false;
2717
2718         BLI_SMALLSTACK_DECLARE(edges, BMEdge *);
2719
2720 #define LOOP_VISIT _FLAG_WALK
2721 #define EDGE_VISIT _FLAG_WALK
2722
2723         for (i = 0; i < larr_len; i++) {
2724                 BMLoop *l_sep = larr[i];
2725
2726                 /* all must be from the same vert! */
2727                 BLI_assert(v_sep == l_sep->v);
2728
2729                 BLI_assert(!BM_ELEM_API_FLAG_TEST(l_sep, LOOP_VISIT));
2730                 BM_ELEM_API_FLAG_ENABLE(l_sep, LOOP_VISIT);
2731
2732                 /* weak! but it makes it simpler to check for edges to split
2733                  * while doing a radial loop (where loops may be adjacent) */
2734                 BM_ELEM_API_FLAG_ENABLE(l_sep->next, LOOP_VISIT);
2735                 BM_ELEM_API_FLAG_ENABLE(l_sep->prev, LOOP_VISIT);
2736         }
2737
2738         for (i = 0; i < larr_len; i++) {
2739                 BMLoop *l_sep = larr[i];
2740
2741                 BMLoop *loop_pair[2] = {l_sep, l_sep->prev};
2742                 int j;
2743                 for (j = 0; j < ARRAY_SIZE(loop_pair); j++) {
2744                         BMEdge *e = loop_pair[j]->e;
2745                         if (!BM_ELEM_API_FLAG_TEST(e, EDGE_VISIT)) {
2746                                 BMLoop *l_iter, *l_first;
2747                                 bool is_mixed = false;
2748
2749                                 BM_ELEM_API_FLAG_ENABLE(e, EDGE_VISIT);
2750
2751                                 l_iter = l_first = e->l;
2752                                 do {
2753                                         if (!BM_ELEM_API_FLAG_TEST(l_iter, LOOP_VISIT)) {
2754                                                 is_mixed = true;
2755                                                 is_mixed_any = true;
2756                                                 break;
2757                                         }
2758                                 } while ((l_iter = l_iter->radial_next) != l_first);
2759
2760                                 if (is_mixed) {
2761                                         /* ensure the first loop is one we don't own so we can do a quick check below
2762                                          * on the edge's loop-flag to see if the edge is mixed or not. */
2763                                         e->l = l_iter;
2764                                 }
2765                                 BLI_SMALLSTACK_PUSH(edges, e);
2766                         }
2767                 }
2768         }
2769
2770         if (is_mixed_any == false) {
2771                 /* all loops in 'larr' are the sole owners of their edges.
2772                  * nothing to split away from, this is a no-op */
2773                 v_new = v_sep;
2774         }
2775         else {
2776                 BMEdge *e;
2777
2778                 BLI_assert(!BLI_SMALLSTACK_IS_EMPTY(edges));
2779
2780                 v_new = BM_vert_create(bm, v_sep->co, v_sep, BM_CREATE_NOP);
2781                 while ((e = BLI_SMALLSTACK_POP(edges))) {
2782                         BMLoop *l_iter, *l_first, *l_next;
2783                         BMEdge *e_new;
2784
2785                         /* disable so copied edge isn't left dirty (loop edges are cleared last too) */
2786                         BM_ELEM_API_FLAG_DISABLE(e, EDGE_VISIT);
2787
2788                         if (!BM_ELEM_API_FLAG_TEST(e->l, LOOP_VISIT)) {
2789                                 /* edge has some loops owned by us, some owned by other loops */
2790                                 BMVert *e_new_v_pair[2];
2791
2792                                 if (e->v1 == v_sep) {
2793                                         e_new_v_pair[0] = v_new;
2794                                         e_new_v_pair[1] = e->v2;
2795                                 }
2796                                 else {
2797                                         BLI_assert(v_sep == e->v2);
2798                                         e_new_v_pair[0] = e->v1;
2799                                         e_new_v_pair[1] = v_new;
2800                                 }
2801
2802                                 e_new = BM_edge_create(bm, UNPACK2(e_new_v_pair), e, BM_CREATE_NOP);
2803
2804                                 /* now moved all loops from 'larr' to this newly created edge */
2805                                 l_iter = l_first = e->l;
2806                                 do {
2807                                         l_next = l_iter->radial_next;
2808                                         if (BM_ELEM_API_FLAG_TEST(l_iter, LOOP_VISIT)) {
2809                                                 bmesh_radial_loop_remove(e, l_iter);
2810                                                 bmesh_radial_loop_append(e_new, l_iter);
2811                                                 l_iter->e = e_new;
2812                                         }
2813                                 } while ((l_iter = l_next) != l_first);
2814                         }
2815                         else {
2816                                 /* we own the edge entirely, replace the vert */
2817                                 bmesh_disk_vert_replace(e, v_new, v_sep);
2818                         }
2819
2820                         /* loop vert is handled last! */
2821                 }
2822         }
2823
2824         for (i = 0; i < larr_len; i++) {
2825                 BMLoop *l_sep = larr[i];
2826
2827                 l_sep->v = v_new;
2828
2829                 BLI_assert(BM_ELEM_API_FLAG_TEST(l_sep, LOOP_VISIT));
2830                 BLI_assert(BM_ELEM_API_FLAG_TEST(l_sep->prev, LOOP_VISIT));
2831                 BLI_assert(BM_ELEM_API_FLAG_TEST(l_sep->next, LOOP_VISIT));
2832                 BM_ELEM_API_FLAG_DISABLE(l_sep, LOOP_VISIT);
2833                 BM_ELEM_API_FLAG_DISABLE(l_sep->prev, LOOP_VISIT);
2834                 BM_ELEM_API_FLAG_DISABLE(l_sep->next, LOOP_VISIT);
2835
2836
2837                 BM_ELEM_API_FLAG_DISABLE(l_sep->prev->e, EDGE_VISIT);
2838                 BM_ELEM_API_FLAG_DISABLE(l_sep->e, EDGE_VISIT);
2839         }
2840
2841 #undef LOOP_VISIT
2842 #undef EDGE_VISIT
2843
2844         return v_new;
2845 }
2846
2847 static void bmesh_edge_vert_swap__recursive(BMEdge *e, BMVert *v_dst, BMVert *v_src)
2848 {
2849         BMLoop *l_iter, *l_first;
2850
2851         BLI_assert(ELEM(v_src, e->v1, e->v2));
2852         bmesh_disk_vert_replace(e, v_dst, v_src);
2853
2854         l_iter = l_first = e->l;
2855         do {
2856                 if (l_iter->v == v_src) {
2857                         l_iter->v = v_dst;
2858                         if (BM_vert_in_edge(l_iter->prev->e, v_src)) {
2859                                 bmesh_edge_vert_swap__recursive(l_iter->prev->e, v_dst, v_src);
2860                         }
2861                 }
2862                 else if (l_iter->next->v == v_src) {
2863                         l_iter->next->v = v_dst;
2864                         if (BM_vert_in_edge(l_iter->next->e, v_src)) {
2865                                 bmesh_edge_vert_swap__recursive(l_iter->next->e, v_dst, v_src);
2866                         }
2867                 }
2868                 else {
2869                         BLI_assert(l_iter->prev->v != v_src);
2870                 }
2871         } while ((l_iter = l_iter->radial_next) != l_first);
2872 }
2873
2874 /**
2875  * This function assumes l_sep is apart of a larger fan which has already been
2876  * isolated by calling bmesh_edge_separate to segregate it radially.
2877  */
2878 BMVert *bmesh_urmv_loop_region(BMesh *bm, BMLoop *l_sep)
2879 {
2880         BMVert *v_new = BM_vert_create(bm, l_sep->v->co, l_sep->v, BM_CREATE_NOP);
2881         /* passing either 'l_sep->e', 'l_sep->prev->e' will work */
2882         bmesh_edge_vert_swap__recursive(l_sep->e, v_new, l_sep->v);
2883         BLI_assert(l_sep->v == v_new);
2884         return v_new;
2885 }
2886
2887
2888 /**
2889  * \brief Unglue Region Make Vert (URMV)
2890  *
2891  * Disconnects f_sep from the vertex fan at \a v_sep
2892  *
2893  * \return The newly created BMVert
2894  */
2895 BMVert *bmesh_urmv(BMesh *bm, BMFace *f_sep, BMVert *v_sep)
2896 {
2897         BMLoop *l = BM_face_vert_share_loop(f_sep, v_sep);
2898         return bmesh_urmv_loop(bm, l);
2899 }
2900
2901 /**
2902  * Avoid calling this where possible,
2903  * low level function so both face pointers remain intact but point to swapped data.
2904  * \note must be from the same bmesh.
2905  */
2906 void bmesh_face_swap_data(BMFace *f_a, BMFace *f_b)
2907 {
2908         BMLoop *l_iter, *l_first;
2909
2910         BLI_assert(f_a != f_b);
2911
2912         l_iter = l_first = BM_FACE_FIRST_LOOP(f_a);
2913         do {
2914                 l_iter->f = f_b;
2915         } while ((l_iter = l_iter->next) != l_first);
2916
2917         l_iter = l_first = BM_FACE_FIRST_LOOP(f_b);
2918         do {
2919                 l_iter->f = f_a;
2920         } while ((l_iter = l_iter->next) != l_first);
2921
2922         SWAP(BMFace, (*f_a), (*f_b));
2923
2924         /* swap back */
2925         SWAP(void *, f_a->head.data, f_b->head.data);
2926         SWAP(int, f_a->head.index, f_b->head.index);
2927 }