source/blender/bmesh/intern/bmesh_construct.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  * The Original Code is Copyright (C) 2007 Blender Foundation.
  19  * All rights reserved.
  20  *
  21  * The Original Code is: all of this file.
  22  *
  23  * Contributor(s): Geoffrey Bantle.
  24  *
  25  * ***** END GPL LICENSE BLOCK *****
  26  */
  27
  28 /** \file blender/bmesh/intern/bmesh_construct.c
  29  *  \ingroup bmesh
  30  *
  31  * BM construction functions.
  32  */
  33
  34 #include "MEM_guardedalloc.h"
  35
  36 #include "BLI_array.h"
  37 #include "BLI_math.h"
  38
  39 #include "BKE_customdata.h"
  40
  41 #include "DNA_meshdata_types.h"
  42
  43 #include "bmesh.h"
  44 #include "intern/bmesh_private.h"
  45
  46 #define SELECT 1
  47
  48 /* prototypes */
  49 static void bm_loop_attrs_copy(BMesh *source_mesh, BMesh *target_mesh,
  50                                const BMLoop *source_loop, BMLoop *target_loop);
  51
  52 /**
  53  * \brief Make Quad/Triangle
  54  *
  55  * Creates a new quad or triangle from a list of 3 or 4 vertices.
  56  * If \a nodouble is TRUE, then a check is done to see if a face
  57  * with these vertices already exists and returns it instead.
  58  *
  59  * If a pointer to an example face is provided, it's custom data
  60  * and properties will be copied to the new face.
  61  *
  62  * \note The winding of the face is determined by the order
  63  * of the vertices in the vertex array.
  64  */
  65
  66 BMFace *BM_face_create_quad_tri(BMesh *bm,
  67                                 BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4,
  68                                 const BMFace *example, const int nodouble)
  69 {
  70         BMVert *vtar[4] = {v1, v2, v3, v4};
  71         return BM_face_create_quad_tri_v(bm, vtar, v4 ? 4 : 3, example, nodouble);
  72 }
  73
  74 BMFace *BM_face_create_quad_tri_v(BMesh *bm, BMVert **verts, int len, const BMFace *example, const int nodouble)
  75 {
  76         BMFace *f = NULL;
  77         int is_overlap = FALSE;
  78
  79         /* sanity check - debug mode only */
  80         if (len == 3) {
  81                 BLI_assert(verts[0] != verts[1]);
  82                 BLI_assert(verts[0] != verts[2]);
  83                 BLI_assert(verts[1] != verts[2]);
  84         }
  85         else if (len == 4) {
  86                 BLI_assert(verts[0] != verts[1]);
  87                 BLI_assert(verts[0] != verts[2]);
  88                 BLI_assert(verts[0] != verts[3]);
  89
  90                 BLI_assert(verts[1] != verts[2]);
  91                 BLI_assert(verts[1] != verts[3]);
  92
  93                 BLI_assert(verts[2] != verts[3]);
  94         }
  95         else {
  96                 BLI_assert(0);
  97         }
  98
  99
 100         if (nodouble) {
 101                 /* check if face exists or overlaps */
 102                 is_overlap = BM_face_exists(bm, verts, len, &f);
 103         }
 104
 105         /* make new face */
 106         if ((f == NULL) && (!is_overlap)) {
 107                 BMEdge *edar[4] = {NULL};
 108                 edar[0] = BM_edge_create(bm, verts[0], verts[1], NULL, TRUE);
 109                 edar[1] = BM_edge_create(bm, verts[1], verts[2], NULL, TRUE);
 110                 if (len == 4) {
 111                         edar[2] = BM_edge_create(bm, verts[2], verts[3], NULL, TRUE);
 112                         edar[3] = BM_edge_create(bm, verts[3], verts[0], NULL, TRUE);
 113                 }
 114                 else {
 115                         edar[2] = BM_edge_create(bm, verts[2], verts[0], NULL, TRUE);
 116                 }
 117
 118                 f = BM_face_create(bm, verts, edar, len, FALSE);
 119
 120                 if (example && f) {
 121                         BM_elem_attrs_copy(bm, bm, example, f);
 122                 }
 123         }
 124
 125         return f;
 126 }
 127
 128 /**
 129  * \brief copies face loop data from shared adjacent faces.
 130  * \note when a matching edge is found, both loops of that edge are copied
 131  * this is done since the face may not be completely surrounded by faces,
 132  * this way: a quad with 2 connected quads on either side will still get all 4 loops updated */
 133 void BM_face_copy_shared(BMesh *bm, BMFace *f)
 134 {
 135         BMLoop *l_first;
 136         BMLoop *l_iter;
 137
 138         l_iter = l_first = BM_FACE_FIRST_LOOP(f);
 139         do {
 140                 BMLoop *l_other = l_iter->radial_next;
 141
 142                 if (l_other && l_other != l_iter) {
 143                         if (l_other->v == l_iter->v) {
 144                                 bm_loop_attrs_copy(bm, bm, l_other, l_iter);
 145                                 bm_loop_attrs_copy(bm, bm, l_other->next, l_iter->next);
 146                         }
 147                         else {
 148                                 bm_loop_attrs_copy(bm, bm, l_other->next, l_iter);
 149                                 bm_loop_attrs_copy(bm, bm, l_other, l_iter->next);
 150                         }
 151                         /* since we copy both loops of the shared edge, step over the next loop here */
 152                         if ((l_iter = l_iter->next) == l_first) {
 153                                 break;
 154                         }
 155                 }
 156         } while ((l_iter = l_iter->next) != l_first);
 157 }
 158
 159 /**
 160  * \brief Make NGon
 161  *
 162  * Makes an ngon from an unordered list of edges. \a v1 and \a v2
 163  * must be the verts defining edges[0],
 164  * and define the winding of the new face.
 165  *
 166  * \a edges are not required to be ordered, simply to to form
 167  * a single closed loop as a whole.
 168  *
 169  * \note While this function will work fine when the edges
 170  * are already sorted, if the edges are always going to be sorted,
 171  * #BM_face_create should be considered over this function as it
 172  * avoids some unnecessary work.
 173  */
 174 BMFace *BM_face_create_ngon(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **edges, int len, int nodouble)
 175 {
 176         BMEdge **edges2 = NULL;
 177         BLI_array_staticdeclare(edges2, BM_NGON_STACK_SIZE);
 178         BMVert **verts = NULL;
 179         BLI_array_staticdeclare(verts, BM_NGON_STACK_SIZE);
 180         BMFace *f = NULL;
 181         BMEdge *e;
 182         BMVert *v, *ev1, *ev2;
 183         int i, /* j, */ v1found, reverse;
 184
 185         /* this code is hideous, yeek.  I'll have to think about ways of
 186          *  cleaning it up.  basically, it now combines the old BM_face_create_ngon
 187          *  _and_ the old bmesh_mf functions, so its kindof smashed together
 188          * - joeedh */
 189
 190         if (!len || !v1 || !v2 || !edges || !bm)
 191                 return NULL;
 192
 193         /* put edges in correct order */
 194         for (i = 0; i < len; i++) {
 195                 BM_ELEM_API_FLAG_ENABLE(edges[i], _FLAG_MF);
 196         }
 197
 198         ev1 = edges[0]->v1;
 199         ev2 = edges[0]->v2;
 200
 201         if (v1 == ev2) {
 202                 /* Swapping here improves performance and consistency of face
 203                  * structure in the special case that the edges are already in
 204                  * the correct order and winding */
 205                 SWAP(BMVert *, ev1, ev2);
 206         }
 207
 208         BLI_array_append(verts, ev1);
 209         v = ev2;
 210         e = edges[0];
 211         do {
 212                 BMEdge *e2 = e;
 213
 214                 BLI_array_append(verts, v);
 215                 BLI_array_append(edges2, e);
 216
 217                 do {
 218                         e2 = bmesh_disk_edge_next(e2, v);
 219                         if (e2 != e && BM_ELEM_API_FLAG_TEST(e2, _FLAG_MF)) {
 220                                 v = BM_edge_other_vert(e2, v);
 221                                 break;
 222                         }
 223                 } while (e2 != e);
 224
 225                 if (e2 == e)
 226                         goto err; /* the edges do not form a closed loop */
 227
 228                 e = e2;
 229         } while (e != edges[0]);
 230
 231         if (BLI_array_count(edges2) != len) {
 232                 goto err; /* we didn't use all edges in forming the boundary loop */
 233         }
 234
 235         /* ok, edges are in correct order, now ensure they are going
 236          * in the correct direction */
 237         v1found = reverse = FALSE;
 238         for (i = 0; i < len; i++) {
 239                 if (BM_vert_in_edge(edges2[i], v1)) {
 240                         /* see if v1 and v2 are in the same edge */
 241                         if (BM_vert_in_edge(edges2[i], v2)) {
 242                                 /* if v1 is shared by the *next* edge, then the winding
 243                                  * is incorrect */
 244                                 if (BM_vert_in_edge(edges2[(i + 1) % len], v1)) {
 245                                         reverse = TRUE;
 246                                         break;
 247                                 }
 248                         }
 249
 250                         v1found = TRUE;
 251                 }
 252
 253                 if ((v1found == FALSE) && BM_vert_in_edge(edges2[i], v2)) {
 254                         reverse = TRUE;
 255                         break;
 256                 }
 257         }
 258
 259         if (reverse) {
 260                 for (i = 0; i < len / 2; i++) {
 261                         v = verts[i];
 262                         verts[i] = verts[len - i - 1];
 263                         verts[len - i - 1] = v;
 264                 }
 265         }
 266
 267         for (i = 0; i < len; i++) {
 268                 edges2[i] = BM_edge_exists(verts[i], verts[(i + 1) % len]);
 269                 if (!edges2[i]) {
 270                         goto err;
 271                 }
 272         }
 273
 274         f = BM_face_create(bm, verts, edges2, len, nodouble);
 275
 276         /* clean up flags */
 277         for (i = 0; i < len; i++) {
 278                 BM_ELEM_API_FLAG_DISABLE(edges2[i], _FLAG_MF);
 279         }
 280
 281         BLI_array_free(verts);
 282         BLI_array_free(edges2);
 283
 284         return f;
 285
 286 err:
 287         for (i = 0; i < len; i++) {
 288                 BM_ELEM_API_FLAG_DISABLE(edges[i], _FLAG_MF);
 289         }
 290
 291         BLI_array_free(verts);
 292         BLI_array_free(edges2);
 293
 294         return NULL;
 295 }
 296
 297 typedef struct AngleIndexPair {
 298         float angle;
 299         int index;
 300 } AngleIndexPair;
 301
 302 static int angle_index_pair_cmp(const void *e1, const void *e2)
 303 {
 304         const AngleIndexPair *p1 = e1, *p2 = e2;
 305         if      (p1->angle > p2->angle) return  1;
 306         else if (p1->angle < p2->angle) return -1;
 307         else return 0;
 308 }
 309
 310 /**
 311  * Makes an NGon from an un-ordered set of verts
 312  *
 313  * assumes...
 314  * - that verts are only once in the list.
 315  * - that the verts have roughly planer bounds
 316  * - that the verts are roughly circular
 317  * there can be concave areas but overlapping folds from the center point will fail.
 318  *
 319  * a brief explanation of the method used
 320  * - find the center point
 321  * - find the normal of the vcloud
 322  * - order the verts around the face based on their angle to the normal vector at the center point.
 323  *
 324  * \note Since this is a vcloud there is no direction.
 325  */
 326 BMFace *BM_face_create_ngon_vcloud(BMesh *bm, BMVert **vert_arr, int totv, int nodouble)
 327 {
 328         BMFace *f;
 329
 330         float totv_inv = 1.0f / (float)totv;
 331         int i = 0;
 332
 333         float cent[3], nor[3];
 334
 335         float *far = NULL, *far_cross = NULL;
 336
 337         float far_vec[3];
 338         float far_cross_vec[3];
 339         float sign_vec[3]; /* work out if we are pos/neg angle */
 340
 341         float far_dist, far_best;
 342         float far_cross_dist, far_cross_best = 0.0f;
 343
 344         AngleIndexPair *vang;
 345
 346         BMVert **vert_arr_map;
 347         BMEdge **edge_arr;
 348         int i_prev;
 349
 350         unsigned int winding[2] = {0, 0};
 351
 352         /* get the center point and collect vector array since we loop over these a lot */
 353         zero_v3(cent);
 354         for (i = 0; i < totv; i++) {
 355                 madd_v3_v3fl(cent, vert_arr[i]->co, totv_inv);
 356         }
 357
 358
 359         /* find the far point from cent */
 360         far_best = 0.0f;
 361         for (i = 0; i < totv; i++) {
 362                 far_dist = len_squared_v3v3(vert_arr[i]->co, cent);
 363                 if (far_dist > far_best || far == NULL) {
 364                         far = vert_arr[i]->co;
 365                         far_best = far_dist;
 366                 }
 367         }
 368
 369         sub_v3_v3v3(far_vec, far, cent);
 370         far_dist = len_v3(far_vec); /* real dist */
 371
 372         /* --- */
 373
 374         /* find a point 90deg about to compare with */
 375         far_cross_best = 0.0f;
 376         for (i = 0; i < totv; i++) {
 377
 378                 if (far == vert_arr[i]->co) {
 379                         continue;
 380                 }
 381
 382                 sub_v3_v3v3(far_cross_vec, vert_arr[i]->co, cent);
 383                 far_cross_dist = normalize_v3(far_cross_vec);
 384
 385                 /* more of a weight then a distance */
 386                 far_cross_dist = (/* first we want to have a value close to zero mapped to 1 */
 387                                                   1.0 - fabsf(dot_v3v3(far_vec, far_cross_vec)) *
 388
 389                                                   /* second  we multiply by the distance
 390                                                    * so points close to the center are not preferred */
 391                                                   far_cross_dist);
 392
 393                 if (far_cross_dist > far_cross_best || far_cross == NULL) {
 394                         far_cross = vert_arr[i]->co;
 395                         far_cross_best = far_cross_dist;
 396                 }
 397         }
 398
 399         sub_v3_v3v3(far_cross_vec, far_cross, cent);
 400
 401         /* --- */
 402
 403         /* now we have 2 vectors we can have a cross product */
 404         cross_v3_v3v3(nor, far_vec, far_cross_vec);
 405         normalize_v3(nor);
 406         cross_v3_v3v3(sign_vec, far_vec, nor); /* this vector should match 'far_cross_vec' closely */
 407
 408         /* --- */
 409
 410         /* now calculate every points angle around the normal (signed) */
 411         vang = MEM_mallocN(sizeof(AngleIndexPair) * totv, __func__);
 412
 413         for (i = 0; i < totv; i++) {
 414                 float co[3];
 415                 float proj_vec[3];
 416                 float angle;
 417
 418                 /* center relative vec */
 419                 sub_v3_v3v3(co, vert_arr[i]->co, cent);
 420
 421                 /* align to plane */
 422                 project_v3_v3v3(proj_vec, co, nor);
 423                 sub_v3_v3(co, proj_vec);
 424
 425                 /* now 'co' is valid - we can compare its angle against the far vec */
 426                 angle = angle_v3v3(far_vec, co);
 427
 428                 if (dot_v3v3(co, sign_vec) < 0.0f) {
 429                         angle = -angle;
 430                 }
 431
 432                 vang[i].angle = angle;
 433                 vang[i].index = i;
 434         }
 435
 436         /* sort by angle and magic! - we have our ngon */
 437         qsort(vang, totv, sizeof(AngleIndexPair), angle_index_pair_cmp);
 438
 439         /* --- */
 440
 441         /* create edges and find the winding (if faces are attached to any existing edges) */
 442         vert_arr_map = MEM_mallocN(sizeof(BMVert **) * totv, __func__);
 443         edge_arr = MEM_mallocN(sizeof(BMEdge **) * totv, __func__);
 444
 445         for (i = 0; i < totv; i++) {
 446                 vert_arr_map[i] = vert_arr[vang[i].index];
 447         }
 448         MEM_freeN(vang);
 449
 450         i_prev = totv - 1;
 451         for (i = 0; i < totv; i++) {
 452                 edge_arr[i] = BM_edge_create(bm, vert_arr_map[i_prev], vert_arr_map[i], NULL, TRUE);
 453
 454                 /* the edge may exist already and be attached to a face
 455                  * in this case we can find the best winding to use for the new face */
 456                 if (edge_arr[i]->l) {
 457                         BMVert *test_v1, *test_v2;
 458                         /* we want to use the reverse winding to the existing order */
 459                         BM_edge_ordered_verts(edge_arr[i], &test_v2, &test_v1);
 460                         winding[(vert_arr_map[i_prev] == test_v2)]++;
 461
 462                 }
 463
 464                 i_prev = i;
 465         }
 466
 467         /* --- */
 468
 469         if (winding[0] < winding[1]) {
 470                 winding[0] = 1;
 471                 winding[1] = 0;
 472         }
 473         else {
 474                 winding[0] = 0;
 475                 winding[1] = 1;
 476         }
 477
 478         /* --- */
 479
 480         /* create the face */
 481         f = BM_face_create_ngon(bm, vert_arr_map[winding[0]], vert_arr_map[winding[1]], edge_arr, totv, nodouble);
 482
 483         MEM_freeN(edge_arr);
 484         MEM_freeN(vert_arr_map);
 485
 486         return f;
 487 }
 488
 489 /**
 490  * Called by operators to remove elements that they have marked for
 491  * removal.
 492  */
 493 void BMO_remove_tagged_faces(BMesh *bm, const short oflag)
 494 {
 495         BMFace *f;
 496         BMIter iter;
 497
 498         BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
 499                 if (BMO_elem_flag_test(bm, f, oflag)) {
 500                         BM_face_kill(bm, f);
 501                 }
 502         }
 503 }
 504
 505 void BMO_remove_tagged_edges(BMesh *bm, const short oflag)
 506 {
 507         BMEdge *e;
 508         BMIter iter;
 509
 510         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
 511                 if (BMO_elem_flag_test(bm, e, oflag)) {
 512                         BM_edge_kill(bm, e);
 513                 }
 514         }
 515 }
 516
 517 void BMO_remove_tagged_verts(BMesh *bm, const short oflag)
 518 {
 519         BMVert *v;
 520         BMIter iter;
 521
 522         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
 523                 if (BMO_elem_flag_test(bm, v, oflag)) {
 524                         BM_vert_kill(bm, v);
 525                 }
 526         }
 527 }
 528
 529 /*************************************************************/
 530 /* you need to make remove tagged verts/edges/faces
 531  * api functions that take a filter callback.....
 532  * and this new filter type will be for opstack flags.
 533  * This is because the BM_remove_taggedXXX functions bypass iterator API.
 534  *  - Ops don't care about 'UI' considerations like selection state, hide state, etc.
 535  *    If you want to work on unhidden selections for instance,
 536  *    copy output from a 'select context' operator to another operator....
 537  */
 538
 539 static void bmo_remove_tagged_context_verts(BMesh *bm, const short oflag)
 540 {
 541         BMVert *v;
 542         BMEdge *e;
 543         BMFace *f;
 544
 545         BMIter iter;
 546         BMIter itersub;
 547
 548         BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
 549                 if (BMO_elem_flag_test(bm, v, oflag)) {
 550                         /* Visit edge */
 551                         BM_ITER_ELEM (e, &itersub, v, BM_EDGES_OF_VERT) {
 552                                 BMO_elem_flag_enable(bm, e, oflag);
 553                         }
 554                         /* Visit face */
 555                         BM_ITER_ELEM (f, &itersub, v, BM_FACES_OF_VERT) {
 556                                 BMO_elem_flag_enable(bm, f, oflag);
 557                         }
 558                 }
 559         }
 560
 561         BMO_remove_tagged_faces(bm, oflag);
 562         BMO_remove_tagged_edges(bm, oflag);
 563         BMO_remove_tagged_verts(bm, oflag);
 564 }
 565
 566 static void bmo_remove_tagged_context_edges(BMesh *bm, const short oflag)
 567 {
 568         BMEdge *e;
 569         BMFace *f;
 570
 571         BMIter iter;
 572         BMIter itersub;
 573
 574         BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
 575                 if (BMO_elem_flag_test(bm, e, oflag)) {
 576                         BM_ITER_ELEM (f, &itersub, e, BM_FACES_OF_EDGE) {
 577                                 BMO_elem_flag_enable(bm, f, oflag);
 578                         }
 579                 }
 580         }
 581         BMO_remove_tagged_faces(bm, oflag);
 582         BMO_remove_tagged_edges(bm, oflag);
 583 }
 584
 585 #define DEL_WIREVERT    (1 << 10)
 586
 587 /**
 588  * \warning oflag applies to different types in some contexts,
 589  * not just the type being removed.
 590  *
 591  * \warning take care, uses operator flag DEL_WIREVERT
 592  */
 593 void BMO_remove_tagged_context(BMesh *bm, const short oflag, const int type)
 594 {
 595         BMVert *v;
 596         BMEdge *e;
 597         BMFace *f;
 598
 599         BMIter viter;
 600         BMIter eiter;
 601         BMIter fiter;
 602
 603         switch (type) {
 604                 case DEL_VERTS:
 605                 {
 606                         bmo_remove_tagged_context_verts(bm, oflag);
 607
 608                         break;
 609                 }
 610                 case DEL_EDGES:
 611                 {
 612                         /* flush down to vert */
 613                         BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
 614                                 if (BMO_elem_flag_test(bm, e, oflag)) {
 615                                         BMO_elem_flag_enable(bm, e->v1, oflag);
 616                                         BMO_elem_flag_enable(bm, e->v2, oflag);
 617                                 }
 618                         }
 619                         bmo_remove_tagged_context_edges(bm, oflag);
 620                         /* remove loose vertice */
 621                         BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
 622                                 if (BMO_elem_flag_test(bm, v, oflag) && (!(v->e)))
 623                                         BMO_elem_flag_enable(bm, v, DEL_WIREVERT);
 624                         }
 625                         BMO_remove_tagged_verts(bm, DEL_WIREVERT);
 626
 627                         break;
 628                 }
 629                 case DEL_EDGESFACES:
 630                 {
 631                         bmo_remove_tagged_context_edges(bm, oflag);
 632
 633                         break;
 634                 }
 635                 case DEL_ONLYFACES:
 636                 {
 637                         BMO_remove_tagged_faces(bm, oflag);
 638
 639                         break;
 640                 }
 641                 case DEL_ONLYTAGGED:
 642                 {
 643                         BMO_remove_tagged_faces(bm, oflag);
 644                         BMO_remove_tagged_edges(bm, oflag);
 645                         BMO_remove_tagged_verts(bm, oflag);
 646
 647                         break;
 648                 }
 649                 case DEL_FACES:
 650                 {
 651                         /* go through and mark all edges and all verts of all faces for delet */
 652                         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
 653                                 if (BMO_elem_flag_test(bm, f, oflag)) {
 654                                         for (e = BM_iter_new(&eiter, bm, BM_EDGES_OF_FACE, f); e; e = BM_iter_step(&eiter))
 655                                                 BMO_elem_flag_enable(bm, e, oflag);
 656                                         for (v = BM_iter_new(&viter, bm, BM_VERTS_OF_FACE, f); v; v = BM_iter_step(&viter))
 657                                                 BMO_elem_flag_enable(bm, v, oflag);
 658                                 }
 659                         }
 660                         /* now go through and mark all remaining faces all edges for keeping */
 661                         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
 662                                 if (!BMO_elem_flag_test(bm, f, oflag)) {
 663                                         for (e = BM_iter_new(&eiter, bm, BM_EDGES_OF_FACE, f); e; e = BM_iter_step(&eiter)) {
 664                                                 BMO_elem_flag_disable(bm, e, oflag);
 665                                         }
 666                                         for (v = BM_iter_new(&viter, bm, BM_VERTS_OF_FACE, f); v; v = BM_iter_step(&viter)) {
 667                                                 BMO_elem_flag_disable(bm, v, oflag);
 668                                         }
 669                                 }
 670                         }
 671                         /* also mark all the vertices of remaining edges for keeping */
 672                         BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
 673                                 if (!BMO_elem_flag_test(bm, e, oflag)) {
 674                                         BMO_elem_flag_disable(bm, e->v1, oflag);
 675                                         BMO_elem_flag_disable(bm, e->v2, oflag);
 676                                 }
 677                         }
 678                         /* now delete marked face */
 679                         BMO_remove_tagged_faces(bm, oflag);
 680                         /* delete marked edge */
 681                         BMO_remove_tagged_edges(bm, oflag);
 682                         /* remove loose vertice */
 683                         BMO_remove_tagged_verts(bm, oflag);
 684
 685                         break;
 686                 }
 687                 case DEL_ALL:
 688                 {
 689                         /* does this option even belong in here? */
 690                         BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
 691                                 BMO_elem_flag_enable(bm, f, oflag);
 692                         }
 693                         BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
 694                                 BMO_elem_flag_enable(bm, e, oflag);
 695                         }
 696                         BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
 697                                 BMO_elem_flag_enable(bm, v, oflag);
 698                         }
 699
 700                         BMO_remove_tagged_faces(bm, oflag);
 701                         BMO_remove_tagged_edges(bm, oflag);
 702                         BMO_remove_tagged_verts(bm, oflag);
 703
 704                         break;
 705                 }
 706         }
 707 }
 708 /*************************************************************/
 709
 710
 711 static void bm_vert_attrs_copy(BMesh *source_mesh, BMesh *target_mesh,
 712                                const BMVert *source_vertex, BMVert *target_vertex)
 713 {
 714         if ((source_mesh == target_mesh) && (source_vertex == target_vertex)) {
 715                 return;
 716         }
 717         copy_v3_v3(target_vertex->no, source_vertex->no);
 718         CustomData_bmesh_free_block(&target_mesh->vdata, &target_vertex->head.data);
 719         CustomData_bmesh_copy_data(&source_mesh->vdata, &target_mesh->vdata,
 720                                    source_vertex->head.data, &target_vertex->head.data);
 721 }
 722
 723 static void bm_edge_attrs_copy(BMesh *source_mesh, BMesh *target_mesh,
 724                                const BMEdge *source_edge, BMEdge *target_edge)
 725 {
 726         if ((source_mesh == target_mesh) && (source_edge == target_edge)) {
 727                 return;
 728         }
 729         CustomData_bmesh_free_block(&target_mesh->edata, &target_edge->head.data);
 730         CustomData_bmesh_copy_data(&source_mesh->edata, &target_mesh->edata,
 731                                    source_edge->head.data, &target_edge->head.data);
 732 }
 733
 734 static void bm_loop_attrs_copy(BMesh *source_mesh, BMesh *target_mesh,
 735                                const BMLoop *source_loop, BMLoop *target_loop)
 736 {
 737         if ((source_mesh == target_mesh) && (source_loop == target_loop)) {
 738                 return;
 739         }
 740         CustomData_bmesh_free_block(&target_mesh->ldata, &target_loop->head.data);
 741         CustomData_bmesh_copy_data(&source_mesh->ldata, &target_mesh->ldata,
 742                                    source_loop->head.data, &target_loop->head.data);
 743 }
 744
 745 static void bm_face_attrs_copy(BMesh *source_mesh, BMesh *target_mesh,
 746                                const BMFace *source_face, BMFace *target_face)
 747 {
 748         if ((source_mesh == target_mesh) && (source_face == target_face)) {
 749                 return;
 750         }
 751         copy_v3_v3(target_face->no, source_face->no);
 752         CustomData_bmesh_free_block(&target_mesh->pdata, &target_face->head.data);
 753         CustomData_bmesh_copy_data(&source_mesh->pdata, &target_mesh->pdata,
 754                                    source_face->head.data, &target_face->head.data);
 755         target_face->mat_nr = source_face->mat_nr;
 756 }
 757
 758 /* BMESH_TODO: Special handling for hide flags? */
 759
 760 /**
 761  * Copies attributes, e.g. customdata, header flags, etc, from one element
 762  * to another of the same type.
 763  */
 764 void BM_elem_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, const void *source, void *target)
 765 {
 766         const BMHeader *sheader = source;
 767         BMHeader *theader = target;
 768
 769         BLI_assert(sheader->htype == theader->htype);
 770
 771         if (sheader->htype != theader->htype)
 772                 return;
 773
 774         /* First we copy select */
 775         if (BM_elem_flag_test((BMElem *)sheader, BM_ELEM_SELECT)) {
 776                 BM_elem_select_set(target_mesh, (BMElem *)target, TRUE);
 777         }
 778
 779         /* Now we copy flags */
 780         theader->hflag = sheader->hflag;
 781
 782         /* Copy specific attributes */
 783         switch (theader->htype) {
 784                 case BM_VERT:
 785                         bm_vert_attrs_copy(source_mesh, target_mesh, (const BMVert *)source, (BMVert *)target);
 786                         break;
 787                 case BM_EDGE:
 788                         bm_edge_attrs_copy(source_mesh, target_mesh, (const BMEdge *)source, (BMEdge *)target);
 789                         break;
 790                 case BM_LOOP:
 791                         bm_loop_attrs_copy(source_mesh, target_mesh, (const BMLoop *)source, (BMLoop *)target);
 792                         break;
 793                 case BM_FACE:
 794                         bm_face_attrs_copy(source_mesh, target_mesh, (const BMFace *)source, (BMFace *)target);
 795                         break;
 796                 default:
 797                         BLI_assert(0);
 798         }
 799 }
 800
 801 BMesh *BM_mesh_copy(BMesh *bm_old)
 802 {
 803         BMesh *bm_new;
 804         BMVert *v, *v2, **vtable = NULL;
 805         BMEdge *e, *e2, **edges = NULL, **etable = NULL;
 806         BMElem **eletable;
 807         BLI_array_declare(edges);
 808         BMLoop *l, /* *l2, */ **loops = NULL;
 809         BLI_array_declare(loops);
 810         BMFace *f, *f2, **ftable = NULL;
 811         BMEditSelection *ese;
 812         BMIter iter, liter;
 813         int i, j;
 814         BMAllocTemplate allocsize = {bm_old->totvert,
 815                                      bm_old->totedge,
 816                                      bm_old->totloop,
 817                                      bm_old->totface};
 818
 819         /* allocate a bmesh */
 820         bm_new = BM_mesh_create(&allocsize);
 821
 822         CustomData_copy(&bm_old->vdata, &bm_new->vdata, CD_MASK_BMESH, CD_CALLOC, 0);
 823         CustomData_copy(&bm_old->edata, &bm_new->edata, CD_MASK_BMESH, CD_CALLOC, 0);
 824         CustomData_copy(&bm_old->ldata, &bm_new->ldata, CD_MASK_BMESH, CD_CALLOC, 0);
 825         CustomData_copy(&bm_old->pdata, &bm_new->pdata, CD_MASK_BMESH, CD_CALLOC, 0);
 826
 827         CustomData_bmesh_init_pool(&bm_new->vdata, allocsize.totvert, BM_VERT);
 828         CustomData_bmesh_init_pool(&bm_new->edata, allocsize.totedge, BM_EDGE);
 829         CustomData_bmesh_init_pool(&bm_new->ldata, allocsize.totloop, BM_LOOP);
 830         CustomData_bmesh_init_pool(&bm_new->pdata, allocsize.totface, BM_FACE);
 831
 832         vtable = MEM_mallocN(sizeof(BMVert *) * bm_old->totvert, "BM_mesh_copy vtable");
 833         etable = MEM_mallocN(sizeof(BMEdge *) * bm_old->totedge, "BM_mesh_copy etable");
 834         ftable = MEM_mallocN(sizeof(BMFace *) * bm_old->totface, "BM_mesh_copy ftable");
 835
 836         v = BM_iter_new(&iter, bm_old, BM_VERTS_OF_MESH, NULL);
 837         for (i = 0; v; v = BM_iter_step(&iter), i++) {
 838                 v2 = BM_vert_create(bm_new, v->co, NULL); /* copy between meshes so cant use 'example' argument */
 839                 BM_elem_attrs_copy(bm_old, bm_new, v, v2);
 840                 vtable[i] = v2;
 841                 BM_elem_index_set(v, i); /* set_inline */
 842                 BM_elem_index_set(v2, i); /* set_inline */
 843         }
 844         bm_old->elem_index_dirty &= ~BM_VERT;
 845         bm_new->elem_index_dirty &= ~BM_VERT;
 846
 847         /* safety check */
 848         BLI_assert(i == bm_old->totvert);
 849
 850         e = BM_iter_new(&iter, bm_old, BM_EDGES_OF_MESH, NULL);
 851         for (i = 0; e; e = BM_iter_step(&iter), i++) {
 852                 e2 = BM_edge_create(bm_new,
 853                                     vtable[BM_elem_index_get(e->v1)],
 854                                     vtable[BM_elem_index_get(e->v2)],
 855                                     e, FALSE);
 856
 857                 BM_elem_attrs_copy(bm_old, bm_new, e, e2);
 858                 etable[i] = e2;
 859                 BM_elem_index_set(e, i); /* set_inline */
 860                 BM_elem_index_set(e2, i); /* set_inline */
 861         }
 862         bm_old->elem_index_dirty &= ~BM_EDGE;
 863         bm_new->elem_index_dirty &= ~BM_EDGE;
 864
 865         /* safety check */
 866         BLI_assert(i == bm_old->totedge);
 867
 868         f = BM_iter_new(&iter, bm_old, BM_FACES_OF_MESH, NULL);
 869         for (i = 0; f; f = BM_iter_step(&iter), i++) {
 870                 BM_elem_index_set(f, i); /* set_inline */
 871
 872                 BLI_array_empty(loops);
 873                 BLI_array_empty(edges);
 874                 BLI_array_grow_items(loops, f->len);
 875                 BLI_array_grow_items(edges, f->len);
 876
 877                 l = BM_iter_new(&liter, bm_old, BM_LOOPS_OF_FACE, f);
 878                 for (j = 0; j < f->len; j++, l = BM_iter_step(&liter)) {
 879                         loops[j] = l;
 880                         edges[j] = etable[BM_elem_index_get(l->e)];
 881                 }
 882
 883                 v = vtable[BM_elem_index_get(loops[0]->v)];
 884                 v2 = vtable[BM_elem_index_get(loops[1]->v)];
 885
 886                 if (!bmesh_verts_in_edge(v, v2, edges[0])) {
 887                         v = vtable[BM_elem_index_get(loops[BLI_array_count(loops) - 1]->v)];
 888                         v2 = vtable[BM_elem_index_get(loops[0]->v)];
 889                 }
 890
 891                 f2 = BM_face_create_ngon(bm_new, v, v2, edges, f->len, FALSE);
 892                 if (!f2)
 893                         continue;
 894                 /* use totface in case adding some faces fails */
 895                 BM_elem_index_set(f2, (bm_new->totface - 1)); /* set_inline */
 896
 897                 ftable[i] = f2;
 898
 899                 BM_elem_attrs_copy(bm_old, bm_new, f, f2);
 900                 copy_v3_v3(f2->no, f->no);
 901
 902                 l = BM_iter_new(&liter, bm_new, BM_LOOPS_OF_FACE, f2);
 903                 for (j = 0; j < f->len; j++, l = BM_iter_step(&liter)) {
 904                         BM_elem_attrs_copy(bm_old, bm_new, loops[j], l);
 905                 }
 906
 907                 if (f == bm_old->act_face) bm_new->act_face = f2;
 908         }
 909         bm_old->elem_index_dirty &= ~BM_FACE;
 910         bm_new->elem_index_dirty &= ~BM_FACE;
 911
 912         /* safety check */
 913         BLI_assert(i == bm_old->totface);
 914
 915         /* copy over edit selection history */
 916         for (ese = bm_old->selected.first; ese; ese = ese->next) {
 917                 BMElem *ele = NULL;
 918
 919                 switch (ese->htype) {
 920                         case BM_VERT:
 921                                 eletable = (BMElem **)vtable;
 922                                 break;
 923                         case BM_EDGE:
 924                                 eletable = (BMElem **)etable;
 925                                 break;
 926                         case BM_FACE:
 927                                 eletable = (BMElem **)ftable;
 928                                 break;
 929                         default:
 930                                 eletable = NULL;
 931                                 break;
 932                 }
 933
 934                 if (eletable) {
 935                         ele = eletable[BM_elem_index_get(ese->ele)];
 936                         if (ele) {
 937                                 BM_select_history_store(bm_new, ele);
 938                         }
 939                 }
 940         }
 941
 942         MEM_freeN(etable);
 943         MEM_freeN(vtable);
 944         MEM_freeN(ftable);
 945
 946         BLI_array_free(loops);
 947         BLI_array_free(edges);
 948
 949         return bm_new;
 950 }
 951
 952 /* ME -> BM */
 953 char BM_vert_flag_from_mflag(const char  meflag)
 954 {
 955         return ( ((meflag & SELECT)       ? BM_ELEM_SELECT : 0) |
 956                  ((meflag & ME_HIDE)      ? BM_ELEM_HIDDEN : 0)
 957                  );
 958 }
 959 char BM_edge_flag_from_mflag(const short meflag)
 960 {
 961         return ( ((meflag & SELECT)        ? BM_ELEM_SELECT : 0) |
 962                  ((meflag & ME_SEAM)       ? BM_ELEM_SEAM   : 0) |
 963                  ((meflag & ME_SHARP) == 0 ? BM_ELEM_SMOOTH : 0) | /* invert */
 964                  ((meflag & ME_HIDE)       ? BM_ELEM_HIDDEN : 0) |
 965                  ((meflag & ME_FREESTYLE_EDGE) ? BM_ELEM_FREESTYLE : 0)
 966                  );
 967 }
 968 char BM_face_flag_from_mflag(const char  meflag)
 969 {
 970         return ( ((meflag & ME_FACE_SEL)  ? BM_ELEM_SELECT : 0) |
 971                  ((meflag & ME_SMOOTH)    ? BM_ELEM_SMOOTH : 0) |
 972                  ((meflag & ME_HIDE)      ? BM_ELEM_HIDDEN : 0) |
 973                  ((meflag & ME_FREESTYLE_FACE) ? BM_ELEM_FREESTYLE : 0)
 974                  );
 975 }
 976
 977 /* BM -> ME */
 978 char  BM_vert_flag_to_mflag(BMVert *eve)
 979 {
 980         const char hflag = eve->head.hflag;
 981
 982         return ( ((hflag & BM_ELEM_SELECT)  ? SELECT  : 0) |
 983                  ((hflag & BM_ELEM_HIDDEN)  ? ME_HIDE : 0)
 984                  );
 985 }
 986 short BM_edge_flag_to_mflag(BMEdge *eed)
 987 {
 988         const char hflag = eed->head.hflag;
 989
 990         return ( ((hflag & BM_ELEM_SELECT)       ? SELECT    : 0) |
 991                  ((hflag & BM_ELEM_SEAM)         ? ME_SEAM   : 0) |
 992                  ((hflag & BM_ELEM_SMOOTH) == 0  ? ME_SHARP  : 0) |
 993                  ((hflag & BM_ELEM_HIDDEN)       ? ME_HIDE   : 0) |
 994                  ((hflag & BM_ELEM_FREESTYLE) ? ME_FREESTYLE_EDGE : 0) |
 995                  ((BM_edge_is_wire(eed)) ? ME_LOOSEEDGE : 0) | /* not typical */
 996                  (ME_EDGEDRAW | ME_EDGERENDER)
 997                  );
 998 }
 999 char  BM_face_flag_to_mflag(BMFace *efa)
1000 {
1001         const char hflag = efa->head.hflag;
1002
1003         return ( ((hflag & BM_ELEM_SELECT) ? ME_FACE_SEL : 0) |
1004                  ((hflag & BM_ELEM_SMOOTH) ? ME_SMOOTH   : 0) |
1005                  ((hflag & BM_ELEM_HIDDEN) ? ME_HIDE     : 0) |
1006                  ((hflag & BM_ELEM_FREESTYLE) ? ME_FREESTYLE_FACE : 0)
1007                  );
1008 }