source/blender/bmesh/operators/removedoubles.c

   1 #include "MEM_guardedalloc.h"
   2
   3 #include "DNA_meshdata_types.h"
   4 #include "DNA_mesh_types.h"
   5 #include "DNA_object_types.h"
   6 #include "DNA_scene_types.h"
   7
   8 #include "BLI_utildefines.h"
   9
  10 #include "BLI_math.h"
  11 #include "BLI_ghash.h"
  12 #include "BLI_blenlib.h"
  13 #include "BLI_array.h"
  14 #include "BLI_utildefines.h"
  15
  16 #include "bmesh.h"
  17 #include "mesh_intern.h"
  18 #include "bmesh_private.h"
  19
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <string.h>
  23
  24 #define BL(ptr) ((BMLoop*)(ptr))
  25
  26 static void remdoubles_splitface(BMFace *f, BMesh *bm, BMOperator *op)
  27 {
  28         BMIter liter;
  29         BMLoop *l;
  30         BMVert *v2, *doub;
  31         int split=0;
  32
  33         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
  34                 v2 = BMO_Get_MapPointer(bm, op, "targetmap", l->v);
  35                 /*ok: if v2 is NULL (e.g. not in the map) then it's
  36                       a target vert, otherwise it's a double*/
  37                 if (v2 && BM_Vert_In_Face(f, v2) && v2 != BL(l->prev)->v
  38                     && v2 != BL(l->next)->v)
  39                 {
  40                         doub = l->v;
  41                         split = 1;
  42                         break;
  43                 }
  44         }
  45
  46         if (split && doub != v2) {
  47                 BMLoop *nl;
  48                 BMFace *f2 = BM_Split_Face(bm, f, doub, v2, &nl, NULL);
  49
  50                 remdoubles_splitface(f, bm, op);
  51                 remdoubles_splitface(f2, bm, op);
  52         }
  53 }
  54
  55 #define ELE_DEL         1
  56 #define EDGE_COL        2
  57 #define FACE_MARK       2
  58
  59 #if 0
  60 int remdoubles_face_overlaps(BMesh *bm, BMVert **varr,
  61                              int len, BMFace *exclude,
  62                              BMFace **overlapface)
  63 {
  64         BMIter vertfaces;
  65         BMFace *f;
  66         int i, amount;
  67
  68         if (overlapface) *overlapface = NULL;
  69
  70         for(i=0; i < len; i++){
  71                 f = BMIter_New(&vertfaces, bm, BM_FACES_OF_VERT, varr[i] );
  72                 while(f){
  73                         amount = BM_Verts_In_Face(bm, f, varr, len);
  74                         if(amount >= len){
  75                                 if (overlapface) *overlapface = f;
  76                                 return 1;
  77                         }
  78                         f = BMIter_Step(&vertfaces);
  79                 }
  80         }
  81         return 0;
  82 }
  83 #endif
  84
  85 void bmesh_weldverts_exec(BMesh *bm, BMOperator *op)
  86 {
  87         BMIter iter, liter;
  88         BMVert *v, *v2;
  89         BMEdge *e, *e2, **edges = NULL;
  90         BLI_array_declare(edges);
  91         BMLoop *l, *l2, **loops = NULL;
  92         BLI_array_declare(loops);
  93         BMFace *f, *f2;
  94         int a, b;
  95
  96         BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) {
  97                 if (BMO_Get_MapPointer(bm, op, "targetmap", v))
  98                         BMO_SetFlag(bm, v, ELE_DEL);
  99         }
 100
 101         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
 102                 remdoubles_splitface(f, bm, op);
 103         }
 104
 105         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
 106                 if (BMO_TestFlag(bm, e->v1, ELE_DEL) || BMO_TestFlag(bm, e->v2, ELE_DEL)) {
 107                         v = BMO_Get_MapPointer(bm, op, "targetmap", e->v1);
 108                         v2 = BMO_Get_MapPointer(bm, op, "targetmap", e->v2);
 109
 110                         if (!v) v = e->v1;
 111                         if (!v2) v2 = e->v2;
 112
 113                         if (v == v2)
 114                                 BMO_SetFlag(bm, e, EDGE_COL);
 115                         else if (!BM_Edge_Exist(v, v2))
 116                                 BM_Make_Edge(bm, v, v2, e, 1);
 117
 118                         BMO_SetFlag(bm, e, ELE_DEL);
 119                 }
 120         }
 121
 122         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
 123                 BM_SetIndex(f, 0);
 124                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
 125                         if (BMO_TestFlag(bm, l->v, ELE_DEL))
 126                                 BMO_SetFlag(bm, f, FACE_MARK|ELE_DEL);
 127                         if (BMO_TestFlag(bm, l->e, EDGE_COL))
 128                                 BM_SetIndex(f, BM_GetIndex(f)+1);
 129                 }
 130         }
 131
 132         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
 133                 if (!BMO_TestFlag(bm, f, FACE_MARK))
 134                         continue;
 135
 136                 if (f->len - BM_GetIndex(f) < 3) {
 137                         BMO_SetFlag(bm, f, ELE_DEL);
 138                         continue;
 139                 }
 140
 141                 BLI_array_empty(edges);
 142                 BLI_array_empty(loops);
 143                 a = 0;
 144                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
 145                         v = l->v;
 146                         v2 = BL(l->next)->v;
 147                         if (BMO_TestFlag(bm, v, ELE_DEL))
 148                                 v = BMO_Get_MapPointer(bm, op, "targetmap", v);
 149                         if (BMO_TestFlag(bm, v2, ELE_DEL))
 150                                 v2 = BMO_Get_MapPointer(bm, op, "targetmap", v2);
 151
 152                         e2 = v != v2 ? BM_Edge_Exist(v, v2) : NULL;
 153                         if (e2) {
 154                                 for (b=0; b<a; b++) {
 155                                         if (edges[b] == e2)
 156                                                 break;
 157                                 }
 158                                 if (b != a)
 159                                         continue;
 160
 161                                 BLI_array_growone(edges);
 162                                 BLI_array_growone(loops);
 163
 164                                 edges[a] = e2;
 165                                 loops[a] = l;
 166
 167                                 a++;
 168                         }
 169                 }
 170
 171                 if (BLI_array_count(loops) < 3)
 172                         continue;
 173
 174                 v = loops[0]->v;
 175                 v2 = loops[1]->v;
 176
 177                 if (BMO_TestFlag(bm, v, ELE_DEL))
 178                         v = BMO_Get_MapPointer(bm, op, "targetmap", v);
 179                 if (BMO_TestFlag(bm, v2, ELE_DEL))
 180                         v2 = BMO_Get_MapPointer(bm, op, "targetmap", v2);
 181
 182                 f2 = BM_Make_Ngon(bm, v2, v, edges, a, 0);
 183                 if (f2) {
 184                         BM_Copy_Attributes(bm, bm, f, f2);
 185
 186                         a = 0;
 187                         BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f2) {
 188                                 l2 = loops[a];
 189                                 BM_Copy_Attributes(bm, bm, l2, l);
 190
 191                                 a++;
 192                         }
 193                 }
 194         }
 195
 196         BMO_CallOpf(bm, "del geom=%fvef context=%i", ELE_DEL, DEL_ONLYTAGGED);
 197
 198         BLI_array_free(edges);
 199         BLI_array_free(loops);
 200 }
 201
 202 static int vergaverco(const void *e1, const void *e2)
 203 {
 204         const BMVert *v1 = *(void**)e1, *v2 = *(void**)e2;
 205         float x1 = v1->co[0] + v1->co[1] + v1->co[2];
 206         float x2 = v2->co[0] + v2->co[1] + v2->co[2];
 207
 208         if (x1 > x2) return 1;
 209         else if (x1 < x2) return -1;
 210         else return 0;
 211 }
 212
 213 #define VERT_TESTED     1
 214 #define VERT_DOUBLE     2
 215 #define VERT_TARGET     4
 216 #define VERT_KEEP       8
 217 #define VERT_MARK       16
 218 #define VERT_IN         32
 219
 220 #define EDGE_MARK       1
 221
 222 void bmesh_pointmerge_facedata_exec(BMesh *bm, BMOperator *op)
 223 {
 224         BMOIter siter;
 225         BMIter iter;
 226         BMVert *v, *snapv;
 227         BMLoop *l, *firstl = NULL;
 228         float fac;
 229         int i, tot;
 230
 231         snapv = BMO_IterNew(&siter, bm, op, "snapv", BM_VERT);
 232         tot = BM_Vert_FaceCount(snapv);
 233
 234         if (!tot)
 235                 return;
 236
 237         fac = 1.0f / tot;
 238         BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, snapv) {
 239                 if (!firstl) {
 240                         firstl = l;
 241                 }
 242
 243                 for (i=0; i<bm->ldata.totlayer; i++) {
 244                         if (CustomData_layer_has_math(&bm->ldata, i)) {
 245                                 int type = bm->ldata.layers[i].type;
 246                                 void *e1, *e2;
 247
 248                                 e1 = CustomData_bmesh_get_layer_n(&bm->ldata, firstl->head.data, i);
 249                                 e2 = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
 250
 251                                 CustomData_data_multiply(type, e2, fac);
 252
 253                                 if (l != firstl)
 254                                         CustomData_data_add(type, e1, e2);
 255                         }
 256                 }
 257         }
 258
 259         BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
 260                 BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) {
 261                         if (l == firstl)
 262                                 continue;
 263
 264                         CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, firstl->head.data, &l->head.data);
 265                 }
 266         }
 267 }
 268
 269 void bmesh_vert_average_facedata_exec(BMesh *bm, BMOperator *op)
 270 {
 271         BMOIter siter;
 272         BMIter iter;
 273         BMVert *v;
 274         BMLoop *l /* , *firstl = NULL */;
 275         CDBlockBytes min, max;
 276         void *block;
 277         int i, type;
 278
 279         for (i=0; i<bm->ldata.totlayer; i++) {
 280                 if (!CustomData_layer_has_math(&bm->ldata, i))
 281                         continue;
 282
 283                 type = bm->ldata.layers[i].type;
 284                 CustomData_data_initminmax(type, &min, &max);
 285
 286                 BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
 287                         BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) {
 288                                 block = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
 289                                 CustomData_data_dominmax(type, block, &min, &max);
 290                         }
 291                 }
 292
 293                 CustomData_data_multiply(type, &min, 0.5f);
 294                 CustomData_data_multiply(type, &max, 0.5f);
 295                 CustomData_data_add(type, &min, &max);
 296
 297                 BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
 298                         BM_ITER(l, &iter, bm, BM_LOOPS_OF_VERT, v) {
 299                                 block = CustomData_bmesh_get_layer_n(&bm->ldata, l->head.data, i);
 300                                 CustomData_data_copy_value(type, &min, block);
 301                         }
 302                 }
 303         }
 304 }
 305
 306 void bmesh_pointmerge_exec(BMesh *bm, BMOperator *op)
 307 {
 308         BMOperator weldop;
 309         BMOIter siter;
 310         BMVert *v, *snapv = NULL;
 311         float vec[3];
 312
 313         BMO_Get_Vec(op, "mergeco", vec);
 314
 315         //BMO_CallOpf(bm, "collapse_uvs edges=%s", op, "edges");
 316         BMO_Init_Op(&weldop, "weldverts");
 317
 318         BMO_ITER(v, &siter, bm, op, "verts", BM_VERT) {
 319                 if (!snapv) {
 320                         snapv = v;
 321                         copy_v3_v3(snapv->co, vec);
 322                 } else {
 323                         BMO_Insert_MapPointer(bm, &weldop, "targetmap", v, snapv);
 324                 }
 325         }
 326
 327         BMO_Exec_Op(bm, &weldop);
 328         BMO_Finish_Op(bm, &weldop);
 329 }
 330
 331 void bmesh_collapse_exec(BMesh *bm, BMOperator *op)
 332 {
 333         BMOperator weldop;
 334         BMWalker walker;
 335         BMIter iter;
 336         BMEdge *e, **edges = NULL;
 337         BLI_array_declare(edges);
 338         float min[3], max[3];
 339         int i, tot;
 340
 341         BMO_CallOpf(bm, "collapse_uvs edges=%s", op, "edges");
 342         BMO_Init_Op(&weldop, "weldverts");
 343
 344         BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE);
 345         BMW_Init(&walker, bm, BMW_SHELL, EDGE_MARK, 0);
 346
 347         BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
 348                 if (!BMO_TestFlag(bm, e, EDGE_MARK))
 349                         continue;
 350
 351                 e = BMW_Begin(&walker, e->v1);
 352                 BLI_array_empty(edges);
 353
 354                 INIT_MINMAX(min, max);
 355                 for (tot=0; e; tot++, e=BMW_Step(&walker)) {
 356                         BLI_array_growone(edges);
 357                         edges[tot] = e;
 358
 359                         DO_MINMAX(e->v1->co, min, max);
 360                         DO_MINMAX(e->v2->co, min, max);
 361                 }
 362
 363                 add_v3_v3v3(min, min, max);
 364                 mul_v3_fl(min, 0.5f);
 365
 366                 /*snap edges to a point.  for initial testing purposes anyway.*/
 367                 for (i=0; i<tot; i++) {
 368                         VECCOPY(edges[i]->v1->co, min);
 369                         VECCOPY(edges[i]->v2->co, min);
 370
 371                         if (edges[i]->v1 != edges[0]->v1)
 372                                 BMO_Insert_MapPointer(bm, &weldop, "targetmap", edges[i]->v1, edges[0]->v1);
 373                         if (edges[i]->v2 != edges[0]->v1)
 374                                 BMO_Insert_MapPointer(bm, &weldop, "targetmap", edges[i]->v2, edges[0]->v1);
 375                 }
 376         }
 377
 378         BMO_Exec_Op(bm, &weldop);
 379         BMO_Finish_Op(bm, &weldop);
 380
 381         BMW_End(&walker);
 382         BLI_array_free(edges);
 383 }
 384
 385 /*uv collapse function*/
 386 static void bmesh_collapsecon_do_layer(BMesh *bm, BMOperator *op, int layer)
 387 {
 388         BMIter iter, liter;
 389         BMFace *f;
 390         BMLoop *l, *l2;
 391         BMWalker walker;
 392         void **blocks = NULL;
 393         BLI_array_declare(blocks);
 394         CDBlockBytes min, max;
 395         int i, tot, type = bm->ldata.layers[layer].type;
 396
 397         BMO_Clear_Flag_All(bm, op, BM_ALL, 65535);
 398
 399         BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE);
 400         BMW_Init(&walker, bm, BMW_LOOPDATA_ISLAND, EDGE_MARK, layer);
 401
 402         BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
 403                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
 404                         if (BMO_TestFlag(bm, l->e, EDGE_MARK)) {
 405                                 /*walk*/
 406                                 BLI_array_empty(blocks);
 407                                 tot = 0;
 408                                 l2 = BMW_Begin(&walker, l);
 409
 410                                 CustomData_data_initminmax(type, &min, &max);
 411                                 for (tot=0; l2; tot++, l2=BMW_Step(&walker)) {
 412                                         BLI_array_growone(blocks);
 413                                         blocks[tot] = CustomData_bmesh_get_layer_n(&bm->ldata, l2->head.data, layer);
 414                                         CustomData_data_dominmax(type, blocks[tot], &min, &max);
 415                                 }
 416
 417                                 if (tot) {
 418                                         CustomData_data_multiply(type, &min, 0.5f);
 419                                         CustomData_data_multiply(type, &max, 0.5f);
 420                                         CustomData_data_add(type, &min, &max);
 421
 422                                         /*snap CD (uv, vcol) points to their centroid*/
 423                                         for (i=0; i<tot; i++) {
 424                                                 CustomData_data_copy_value(type, &min, blocks[i]);
 425                                         }
 426                                 }
 427                         }
 428                 }
 429         }
 430
 431         BMW_End(&walker);
 432         BLI_array_free(blocks);
 433 }
 434
 435 void bmesh_collapsecon_exec(BMesh *bm, BMOperator *op)
 436 {
 437         int i;
 438
 439         for (i=0; i<bm->ldata.totlayer; i++) {
 440                 if (CustomData_layer_has_math(&bm->ldata, i))
 441                         bmesh_collapsecon_do_layer(bm, op, i);
 442         }
 443 }
 444
 445 void bmesh_removedoubles_exec(BMesh *bm, BMOperator *op)
 446 {
 447         BMOperator weldop;
 448         BMOIter oiter;
 449         BMVert *v, *v2;
 450         BMVert **verts=NULL;
 451         BLI_array_declare(verts);
 452         float dist, distsqr;
 453         int i, j, len;
 454
 455         dist = BMO_Get_Float(op, "dist");
 456         distsqr = dist*dist;
 457
 458         BMO_Init_Op(&weldop, "weldverts");
 459
 460         i = 0;
 461         BMO_ITER(v, &oiter, bm, op, "verts", BM_VERT) {
 462                 BLI_array_growone(verts);
 463                 verts[i++] = v;
 464         }
 465
 466         /*sort by vertex coordinates added together*/
 467         qsort(verts, BLI_array_count(verts), sizeof(void*), vergaverco);
 468
 469         len = BLI_array_count(verts);
 470         for (i=0; i<len; i++) {
 471                 v = verts[i];
 472                 if (BMO_TestFlag(bm, v, VERT_TESTED)) continue;
 473
 474                 BMO_SetFlag(bm, v, VERT_TESTED);
 475                 for (j=i+1; j<len; j++) {
 476                         float vec[3];
 477
 478                         v2 = verts[j];
 479                         //if ((v2->co[0]+v2->co[1]+v2->co[2]) - (v->co[0]+v->co[1]+v->co[2])
 480                         //     > distsqr) break;
 481                         if ((v2->co[0]-v->co[0]) + (v2->co[1]-v->co[1]) + (v2->co[2]-v->co[2]) > distsqr*4.0f)
 482                                 break;
 483
 484                         vec[0] = v->co[0] - v2->co[0];
 485                         vec[1] = v->co[1] - v2->co[1];
 486                         vec[2] = v->co[2] - v2->co[2];
 487
 488                         if (INPR(vec, vec) < distsqr) {
 489                                 BMO_SetFlag(bm, v2, VERT_TESTED);
 490                                 BMO_SetFlag(bm, v2, VERT_DOUBLE);
 491                                 BMO_SetFlag(bm, v, VERT_TARGET);
 492
 493                                 BMO_Insert_MapPointer(bm, &weldop, "targetmap", v2, v);
 494                         }
 495                 }
 496         }
 497
 498         BLI_array_free(verts);
 499
 500         BMO_Exec_Op(bm, &weldop);
 501         BMO_Finish_Op(bm, &weldop);
 502 }
 503
 504
 505 void bmesh_finddoubles_exec(BMesh *bm, BMOperator *op)
 506 {
 507         BMOIter oiter;
 508         BMVert *v, *v2;
 509         BMVert **verts=NULL;
 510         BLI_array_declare(verts);
 511         float dist, distsqr;
 512         int i, j, len, keepvert;
 513
 514         dist = BMO_Get_Float(op, "dist");
 515         distsqr = dist*dist;
 516
 517         i = 0;
 518         BMO_ITER(v, &oiter, bm, op, "verts", BM_VERT) {
 519                 BLI_array_growone(verts);
 520                 verts[i++] = v;
 521         }
 522
 523         keepvert = BMO_IterNew(&oiter, bm, op, "keepverts", BM_VERT) != NULL;
 524
 525         /*sort by vertex coordinates added together*/
 526         qsort(verts, BLI_array_count(verts), sizeof(void*), vergaverco);
 527
 528         BMO_Flag_Buffer(bm, op, "keepverts", VERT_KEEP, BM_VERT);
 529
 530         len = BLI_array_count(verts);
 531         for (i=0; i<len; i++) {
 532                 v = verts[i];
 533                 if (BMO_TestFlag(bm, v, VERT_DOUBLE)) continue;
 534
 535                 for (j=i+1; j<len; j++) {
 536                         v2 = verts[j];
 537                         if ((v2->co[0]+v2->co[1]+v2->co[2]) - (v->co[0]+v->co[1]+v->co[2])
 538                              > distsqr) break;
 539
 540                         if (keepvert) {
 541                                 if (BMO_TestFlag(bm, v2, VERT_KEEP) == BMO_TestFlag(bm, v, VERT_KEEP))
 542                                         continue;
 543                         }
 544
 545                         if (compare_len_v3v3(v->co, v2->co, dist)) {
 546                                 BMO_SetFlag(bm, v2, VERT_DOUBLE);
 547                                 BMO_SetFlag(bm, v, VERT_TARGET);
 548
 549                                 BMO_Insert_MapPointer(bm, op, "targetmapout", v2, v);
 550                         }
 551                 }
 552         }
 553
 554         BLI_array_free(verts);
 555 }
 556
 557 void bmesh_automerge_exec(BMesh *bm, BMOperator *op)
 558 {
 559         BMOIter oiter;
 560         BMOperator weldop;
 561         BMVert *v, *v2;
 562         BMVert **verts=NULL;
 563         BLI_array_declare(verts);
 564         float dist, distsqr;
 565         int i, j, len /* , keepvert */;
 566
 567         dist = BMO_Get_Float(op, "dist");
 568         distsqr = dist*dist;
 569
 570         i = 0;
 571         BMO_ITER(v, &oiter, bm, op, "verts", BM_VERT) {
 572                 BLI_array_growone(verts);
 573                 verts[i++] = v;
 574         }
 575
 576         BMO_Init_Op(&weldop, "weldverts");
 577
 578         /*sort by vertex coordinates added together*/
 579         qsort(verts, BLI_array_count(verts), sizeof(void*), vergaverco);
 580
 581         BMO_Flag_Buffer(bm, op, "verts", VERT_KEEP, BM_VERT);
 582
 583         len = BLI_array_count(verts);
 584         for (i=0; i<len; i++) {
 585                 v = verts[i];
 586                 if (BMO_TestFlag(bm, v, VERT_DOUBLE)) continue;
 587
 588                 for (j=i+1; j<len; j++) {
 589                         v2 = verts[j];
 590                         if ((v2->co[0]+v2->co[1]+v2->co[2]) - (v->co[0]+v->co[1]+v->co[2])
 591                              > distsqr) break;
 592
 593                         /* only allow unselected -> selected */
 594                         if (BMO_TestFlag(bm, v2, VERT_IN))
 595                                 continue;
 596
 597                         if (compare_len_v3v3(v->co, v2->co, dist)) {
 598                                 BMO_SetFlag(bm, v2, VERT_DOUBLE);
 599                                 BMO_SetFlag(bm, v, VERT_TARGET);
 600
 601                                 BMO_Insert_MapPointer(bm, &weldop, "targetmap", v2, v);
 602                         }
 603                 }
 604         }
 605
 606         BMO_Exec_Op(bm, &weldop);
 607         BMO_Finish_Op(bm, &weldop);
 608
 609         BLI_array_free(verts);
 610 }