source/blender/blenkernel/intern/BME_structure.c

   1 /*
   2  * BME_structure.c    jan 2007
   3  *
   4  *      Low level routines for manipulating the BMesh structure.
   5  *
   6  *
   7  * ***** BEGIN GPL LICENSE BLOCK *****
   8  *
   9  * This program is free software; you can redistribute it and/or
  10  * modify it under the terms of the GNU General Public License
  11  * as published by the Free Software Foundation; either version 2
  12  * of the License, or (at your option) any later version.
  13  * about this.
  14  *
  15  * This program is distributed in the hope that it will be useful,
  16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  * GNU General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; if not, write to the Free Software Foundation,
  22  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  23  *
  24  * The Original Code is Copyright (C) 2007 Blender Foundation.
  25  * All rights reserved.
  26  *
  27  * The Original Code is: all of this file.
  28  *
  29  * Contributor(s): Geoffrey Bantle.
  30  *
  31  * ***** END GPL LICENSE BLOCK *****
  32  */
  33
  34 /** \file blender/blenkernel/intern/BME_structure.c
  35  *  \ingroup bke
  36  */
  37
  38
  39 #include <limits.h>
  40
  41 #include "MEM_guardedalloc.h"
  42 #include "BLI_listbase.h"
  43 #include "BLI_utildefines.h"
  44 #include "BKE_bmesh.h"
  45 /**
  46  *      MISC utility functions.
  47  *
  48  */
  49
  50 int BME_vert_in_edge(BME_Edge *e, BME_Vert *v){
  51         if(e->v1 == v || e->v2 == v) return 1;
  52         return 0;
  53 }
  54 int BME_verts_in_edge(BME_Vert *v1, BME_Vert *v2, BME_Edge *e){
  55         if(e->v1 == v1 && e->v2 == v2) return 1;
  56         else if(e->v1 == v2 && e->v2 == v1) return 1;
  57         return 0;
  58 }
  59
  60 BME_Vert *BME_edge_getothervert(BME_Edge *e, BME_Vert *v){
  61         if(e->v1 == v) return e->v2;
  62         else if(e->v2 == v) return e->v1;
  63         return NULL;
  64 }
  65
  66 int BME_edge_swapverts(BME_Edge *e, BME_Vert *orig, BME_Vert *new){
  67         if(e->v1 == orig){
  68                 e->v1 = new;
  69                 e->d1.next = NULL;
  70                 e->d1.prev = NULL;
  71                 return 1;
  72         }
  73         else if(e->v2 == orig){
  74                 e->v2 = new;
  75                 e->d2.next = NULL;
  76                 e->d2.prev = NULL;
  77                 return 1;
  78         }
  79         return 0;
  80 }
  81
  82 /**
  83  *      ALLOCATION/DEALLOCATION FUNCTIONS
  84  */
  85
  86 BME_Vert *BME_addvertlist(BME_Mesh *bm, BME_Vert *example){
  87         BME_Vert *v=NULL;
  88         v = BLI_mempool_alloc(bm->vpool);
  89         v->next = v->prev = NULL;
  90         v->EID = bm->nextv;
  91         v->co[0] = v->co[1] = v->co[2] = 0.0f;
  92         v->no[0] = v->no[1] = v->no[2] = 0.0f;
  93         v->edge = NULL;
  94         v->data = NULL;
  95         v->eflag1 = v->eflag2 = v->tflag1 = v->tflag2 = 0;
  96         v->flag = v->h = 0;
  97         v->bweight = 0.0f;
  98         BLI_addtail(&(bm->verts), v);
  99         bm->nextv++;
 100         bm->totvert++;
 101
 102         if(example){
 103                 VECCOPY(v->co,example->co);
 104                 CustomData_bmesh_copy_data(&bm->vdata, &bm->vdata, example->data, &v->data);
 105         }
 106         else
 107                 CustomData_bmesh_set_default(&bm->vdata, &v->data);
 108
 109         return v;
 110 }
 111 BME_Edge *BME_addedgelist(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Edge *example){
 112         BME_Edge *e=NULL;
 113         e = BLI_mempool_alloc(bm->epool);
 114         e->next = e->prev = NULL;
 115         e->EID = bm->nexte;
 116         e->v1 = v1;
 117         e->v2 = v2;
 118         e->d1.next = e->d1.prev = e->d2.next = e->d2.prev = NULL;
 119         e->d1.data = e;
 120         e->d2.data = e;
 121         e->loop = NULL;
 122         e->data = NULL;
 123         e->eflag1 = e->eflag2 = e->tflag1 = e->tflag2 = 0;
 124         e->flag = e->h = 0;
 125         e->crease = e->bweight = 0.0f;
 126         bm->nexte++;
 127         bm->totedge++;
 128         BLI_addtail(&(bm->edges), e);
 129
 130         if(example)
 131                 CustomData_bmesh_copy_data(&bm->edata, &bm->edata, example->data, &e->data);
 132         else
 133                 CustomData_bmesh_set_default(&bm->edata, &e->data);
 134
 135
 136         return e;
 137 }
 138 BME_Loop *BME_create_loop(BME_Mesh *bm, BME_Vert *v, BME_Edge *e, BME_Poly *f, BME_Loop *example){
 139         BME_Loop *l=NULL;
 140         l = BLI_mempool_alloc(bm->lpool);
 141         l->next = l->prev = NULL;
 142         l->EID = bm->nextl;
 143         l->radial.next = l->radial.prev = NULL;
 144         l->radial.data = l;
 145         l->v = v;
 146         l->e = e;
 147         l->f = f;
 148         l->data = NULL;
 149         l->eflag1 = l->eflag2 = l->tflag1 = l->tflag2 = 0;
 150         l->flag = l->h = 0; //stupid waste!
 151         bm->nextl++;
 152         bm->totloop++;
 153
 154         if(example)
 155                 CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, example->data, &l->data);
 156         else
 157                 CustomData_bmesh_set_default(&bm->ldata, &l->data);
 158
 159         return l;
 160 }
 161
 162 BME_Poly *BME_addpolylist(BME_Mesh *bm, BME_Poly *example){
 163         BME_Poly *f = NULL;
 164         f = BLI_mempool_alloc(bm->ppool);
 165         f->next = f->prev = NULL;
 166         f->EID = bm->nextp;
 167         f->loopbase = NULL;
 168         f->len = 0;
 169         f->data = NULL;
 170         f->eflag1 = f->eflag2 = f->tflag1 = f->tflag2 = 0;
 171         f->flag = f->h = f->mat_nr;
 172         BLI_addtail(&(bm->polys),f);
 173         bm->nextp++;
 174         bm->totpoly++;
 175
 176         if(example)
 177                 CustomData_bmesh_copy_data(&bm->pdata, &bm->pdata, example->data, &f->data);
 178         else
 179                 CustomData_bmesh_set_default(&bm->pdata, &f->data);
 180
 181
 182         return f;
 183 }
 184
 185 /*      free functions dont do much *yet*. When per-vertex, per-edge and per-face/faceloop
 186         data is added though these will be needed.
 187 */
 188 void BME_free_vert(BME_Mesh *bm, BME_Vert *v){
 189         bm->totvert--;
 190         CustomData_bmesh_free_block(&bm->vdata, &v->data);
 191         BLI_mempool_free(bm->vpool, v);
 192 }
 193 void BME_free_edge(BME_Mesh *bm, BME_Edge *e){
 194         bm->totedge--;
 195         CustomData_bmesh_free_block(&bm->edata, &e->data);
 196         BLI_mempool_free(bm->epool, e);
 197 }
 198 void BME_free_poly(BME_Mesh *bm, BME_Poly *f){
 199         bm->totpoly--;
 200         CustomData_bmesh_free_block(&bm->pdata, &f->data);
 201         BLI_mempool_free(bm->ppool, f);
 202 }
 203 void BME_free_loop(BME_Mesh *bm, BME_Loop *l){
 204         bm->totloop--;
 205         CustomData_bmesh_free_block(&bm->ldata, &l->data);
 206         BLI_mempool_free(bm->lpool, l);
 207 }
 208 /**
 209  *      BMESH CYCLES
 210  *
 211  *      Cycles are circular doubly linked lists that form the basis of adjacency
 212  *      information in the BME modeller. Full adjacency relations can be derived
 213  *      from examining these cycles very quickly. Although each cycle is a double
 214  *  circular linked list, each one is considered to have a 'base' or 'head',
 215  *      and care must be taken by Euler code when modifying the contents of a cycle.
 216  *
 217  *      The contents of this file are split into two parts. First there are the
 218  *      BME_cycle family of functions which are generic circular double linked list
 219  *      procedures. The second part contains higher level procedures for supporting
 220  *      modification of specific cycle types.
 221  *
 222  *      The three cycles explicitly stored in the BMesh data structure are as follows:
 223  *
 224  *      1: The Disk Cycle - A circle of edges around a vertex
 225  *     Base: vertex->edge pointer.
 226  *
 227  *     This cycle is the most complicated in terms of its structure. Each BME_Edge contains
 228  *         two BME_CycleNode structures to keep track of that edge's membership in the disk cycle
 229  *         of each of its vertices. However for any given vertex it may be the first in some edges
 230  *         in its disk cycle and the second for others. The BME_disk_XXX family of functions contain
 231  *         some nice utilities for navigating disk cycles in a way that hides this detail from the
 232  *         tool writer.
 233  *
 234  *              Note that the disk cycle is completley independant from face data. One advantage of this
 235  *              is that wire edges are fully integrated into the topology database. Another is that the
 236  *          the disk cycle has no problems dealing with non-manifold conditions involving faces.
 237  *
 238  *              Functions relating to this cycle:
 239  *
 240  *                      BME_disk_append_edge
 241  *                      BME_disk_remove_edge
 242  *                      BME_disk_nextedge
 243  *                      BME_disk_getpointer
 244  *
 245  *      2: The Radial Cycle - A circle of face edges (BME_Loop) around an edge
 246  *         Base: edge->loop->radial structure.
 247  *
 248  *              The radial cycle is similar to the radial cycle in the radial edge data structure.*
 249  *              Unlike the radial edge however, the radial cycle does not require a large amount of memory
 250  *              to store non-manifold conditions since BMesh does not keep track of region/shell
 251  *              information.
 252  *
 253  *              Functions relating to this cycle:
 254  *
 255  *                      BME_radial_append
 256  *                      BME_radial_remove_loop
 257  *                      BME_radial_nextloop
 258  *                      BME_radial_find_face
 259  *
 260  *
 261  *      3: The Loop Cycle - A circle of face edges around a polygon.
 262  *     Base: polygon->loopbase.
 263  *
 264  *         The loop cycle keeps track of a faces vertices and edges. It should be noted that the
 265  *     direction of a loop cycle is either CW or CCW depending on the face normal, and is
 266  *     not oriented to the faces editedges.
 267  *
 268  *              Functions relating to this cycle:
 269  *
 270  *                      BME_cycle_XXX family of functions.
 271  *
 272  *
 273  *      Note that the order of elements in all cycles except the loop cycle is undefined. This
 274  *  leads to slightly increased seek time for deriving some adjacency relations, however the
 275  *  advantage is that no intrinsic properties of the data structures are dependant upon the
 276  *  cycle order and all non-manifold conditions are represented trivially.
 277  *
 278 */
 279
 280
 281 void BME_cycle_append(void *h, void *nt)
 282 {
 283         BME_CycleNode *oldtail, *head, *newtail;
 284
 285         head = (BME_CycleNode*)h;
 286         newtail = (BME_CycleNode*)nt;
 287
 288         if(head->next == NULL){
 289                 head->next = newtail;
 290                 head->prev = newtail;
 291                 newtail->next = head;
 292                 newtail->prev = head;
 293         }
 294         else{
 295                 oldtail = head->prev;
 296                 oldtail->next = newtail;
 297                 newtail->next = head;
 298                 newtail->prev = oldtail;
 299                 head->prev = newtail;
 300
 301         }
 302 }
 303
 304 /**
 305  *                      BME_cycle_length
 306  *
 307  *      Count the nodes in a cycle.
 308  *
 309  *  Returns -
 310  *      Integer
 311  */
 312
 313 int BME_cycle_length(void *h){
 314
 315         int len = 0;
 316         BME_CycleNode *head, *curnode;
 317         head = (BME_CycleNode*)h;
 318
 319         if(head){
 320                 len = 1;
 321                 for(curnode = head->next; curnode != head; curnode=curnode->next){
 322                         if(len == INT_MAX){ //check for infinite loop/corrupted cycle
 323                                         return -1;
 324                         }
 325                         len++;
 326                 }
 327         }
 328         return len;
 329 }
 330
 331
 332 /**
 333  *                      BME_cycle_remove
 334  *
 335  *      Removes a node from a cycle.
 336  *
 337  *  Returns -
 338  *      1 for success, 0 for failure.
 339  */
 340
 341 int BME_cycle_remove(void *h, void *remn)
 342 {
 343         int i, len;
 344         BME_CycleNode *head, *remnode, *curnode;
 345
 346         head = (BME_CycleNode*)h;
 347         remnode = (BME_CycleNode*)remn;
 348         len = BME_cycle_length(h);
 349
 350         if(len == 1 && head == remnode){
 351                 head->next = NULL;
 352                 head->prev = NULL;
 353                 return 1;
 354         }
 355         else{
 356                 for(i=0, curnode = head; i < len; curnode = curnode->next){
 357                         if(curnode == remnode){
 358                                 remnode->prev->next = remnode->next;
 359                                 remnode->next->prev = remnode->prev;
 360                                 /*zero out remnode pointers, important!*/
 361                                 //remnode->next = NULL;
 362                                 //remnode->prev = NULL;
 363                                 return 1;
 364
 365                         }
 366                 }
 367         }
 368         return 0;
 369 }
 370
 371 /**
 372  *                      BME_cycle_validate
 373  *
 374  *      Validates a cycle. Takes as an argument the expected length of the cycle and
 375  *      a pointer to the cycle head or base.
 376  *
 377  *
 378  *  Returns -
 379  *      1 for success, 0 for failure.
 380  */
 381
 382 int BME_cycle_validate(int len, void *h){
 383         int i;
 384         BME_CycleNode *curnode, *head;
 385         head = (BME_CycleNode*)h;
 386
 387         /*forward validation*/
 388         for(i = 0, curnode = head; i < len; i++, curnode = curnode->next);
 389         if(curnode != head) return 0;
 390
 391         /*reverse validation*/
 392         for(i = 0, curnode = head; i < len; i++, curnode = curnode->prev);
 393         if(curnode != head) return 0;
 394
 395         return 1;
 396 }
 397
 398 /*Begin Disk Cycle routines*/
 399
 400 /**
 401  *                      BME_disk_nextedge
 402  *
 403  *      Find the next edge in a disk cycle
 404  *
 405  *  Returns -
 406  *      Pointer to the next edge in the disk cycle for the vertex v.
 407  */
 408
 409 BME_Edge *BME_disk_nextedge(BME_Edge *e, BME_Vert *v)
 410 {
 411         if(BME_vert_in_edge(e, v)){
 412                 if(e->v1 == v) return e->d1.next->data;
 413                 else if(e->v2 == v) return e->d2.next->data;
 414         }
 415         return NULL;
 416 }
 417
 418 /**
 419  *                      BME_disk_getpointer
 420  *
 421  *      Given an edge and one of its vertices, find the apporpriate CycleNode
 422  *
 423  *  Returns -
 424  *      Pointer to BME_CycleNode.
 425  */
 426 BME_CycleNode *BME_disk_getpointer(BME_Edge *e, BME_Vert *v){
 427         /*returns pointer to the cycle node for the appropriate vertex in this disk*/
 428         if(e->v1 == v) return &(e->d1);
 429         else if (e->v2 == v) return &(e->d2);
 430         return NULL;
 431 }
 432
 433 /**
 434  *                      BME_disk_append_edge
 435  *
 436  *      Appends edge to the end of a vertex disk cycle.
 437  *
 438  *  Returns -
 439  *      1 for success, 0 for failure
 440  */
 441
 442 int BME_disk_append_edge(BME_Edge *e, BME_Vert *v)
 443 {
 444
 445         BME_CycleNode *base, *tail;
 446
 447         if(BME_vert_in_edge(e, v) == 0) return 0; /*check to make sure v is in e*/
 448
 449         /*check for loose vert first*/
 450         if(v->edge == NULL){
 451                 v->edge = e;
 452                 base = tail = BME_disk_getpointer(e, v);
 453                 BME_cycle_append(base, tail); /*circular reference is ok!*/
 454                 return 1;
 455         }
 456
 457         /*insert e at the end of disk cycle and make it the new v->edge*/
 458         base = BME_disk_getpointer(v->edge, v);
 459         tail = BME_disk_getpointer(e, v);
 460         BME_cycle_append(base, tail);
 461         return 1;
 462 }
 463
 464 /**
 465  *                      BME_disk_remove_edge
 466  *
 467  *      Removes an edge from a disk cycle. If the edge to be removed is
 468  *      at the base of the cycle, the next edge becomes the new base.
 469  *
 470  *
 471  *  Returns -
 472  *      Nothing
 473  */
 474
 475 void BME_disk_remove_edge(BME_Edge *e, BME_Vert *v)
 476 {
 477         BME_CycleNode *base, *remnode;
 478         BME_Edge *newbase;
 479         int len;
 480
 481         base = BME_disk_getpointer(v->edge, v);
 482         remnode = BME_disk_getpointer(e, v);
 483
 484         /*first deal with v->edge pointer...*/
 485         len = BME_cycle_length(base);
 486         if(len == 1) newbase = NULL;
 487         else if(v->edge == e) newbase = base->next-> data;
 488         else newbase = v->edge;
 489
 490         /*remove and rebase*/
 491         BME_cycle_remove(base, remnode);
 492         v->edge = newbase;
 493 }
 494
 495 /**
 496  *                      BME_disk_next_edgeflag
 497  *
 498  *      Searches the disk cycle of v, starting with e, for the
 499  *  next edge that has either eflag or tflag.
 500  *
 501  *      BME_Edge pointer.
 502  */
 503
 504 BME_Edge *BME_disk_next_edgeflag(BME_Edge *e, BME_Vert *v, int eflag, int tflag){
 505
 506         /* BME_CycleNode *diskbase; */ /* UNUSED */
 507         BME_Edge *curedge;
 508         int /* len, */ /* UNUSED */ ok;
 509
 510         if(eflag && tflag) return NULL;
 511
 512         ok = BME_vert_in_edge(e,v);
 513         if(ok){
 514                 /* diskbase = BME_disk_getpointer(e, v); */ /* UNUSED */
 515                 /* len = BME_cycle_length(diskbase); */ /* UNUSED */
 516                 curedge = BME_disk_nextedge(e,v);
 517                 while(curedge != e){
 518                         if(tflag){
 519                                 if(curedge->tflag1 == tflag) return curedge;
 520                         }
 521                         else if(eflag){
 522                                 if(curedge->eflag1 == eflag) return curedge;
 523                         }
 524                         curedge = BME_disk_nextedge(curedge, v);
 525                 }
 526         }
 527         return NULL;
 528 }
 529
 530 /**
 531  *                      BME_disk_count_edgeflag
 532  *
 533  *      Counts number of edges in this verts disk cycle which have
 534  *      either eflag or tflag (but not both!)
 535  *
 536  *  Returns -
 537  *      Integer.
 538  */
 539
 540 int BME_disk_count_edgeflag(BME_Vert *v, int eflag, int tflag){
 541         BME_CycleNode *diskbase;
 542         BME_Edge *curedge;
 543         int i, len=0, count=0;
 544
 545         if(v->edge){
 546                 if(eflag && tflag) return 0; /*tflag and eflag are reserved for different functions!*/
 547                 diskbase = BME_disk_getpointer(v->edge, v);
 548                 len = BME_cycle_length(diskbase);
 549
 550                 for(i = 0, curedge=v->edge; i<len; i++){
 551                         if(tflag){
 552                                 if(curedge->tflag1 == tflag) count++;
 553                         }
 554                         else if(eflag){
 555                                 if(curedge->eflag1 == eflag) count++;
 556                         }
 557                         curedge = BME_disk_nextedge(curedge, v);
 558                 }
 559         }
 560         return count;
 561 }
 562
 563 int BME_disk_hasedge(BME_Vert *v, BME_Edge *e){
 564         BME_CycleNode *diskbase;
 565         BME_Edge *curedge;
 566         int i, len=0;
 567
 568         if(v->edge){
 569                 diskbase = BME_disk_getpointer(v->edge,v);
 570                 len = BME_cycle_length(diskbase);
 571
 572                 for(i = 0, curedge=v->edge; i<len; i++){
 573                         if(curedge == e) return 1;
 574                         else curedge=BME_disk_nextedge(curedge, v);
 575                 }
 576         }
 577         return 0;
 578 }
 579 /*end disk cycle routines*/
 580
 581 BME_Loop *BME_radial_nextloop(BME_Loop *l){
 582         return (BME_Loop*)(l->radial.next->data);
 583 }
 584
 585 void BME_radial_append(BME_Edge *e, BME_Loop *l){
 586         if(e->loop == NULL) e->loop = l;
 587         BME_cycle_append(&(e->loop->radial), &(l->radial));
 588 }
 589
 590 void BME_radial_remove_loop(BME_Loop *l, BME_Edge *e)
 591 {
 592         BME_Loop *newbase;
 593         int len;
 594
 595         /*deal with edge->loop pointer*/
 596         len = BME_cycle_length(&(e->loop->radial));
 597         if(len == 1) newbase = NULL;
 598         else if(e->loop == l) newbase = e->loop->radial.next->data;
 599         else newbase = e->loop;
 600
 601         /*remove and rebase*/
 602         BME_cycle_remove(&(e->loop->radial), &(l->radial));
 603         e->loop = newbase;
 604 }
 605
 606 int BME_radial_find_face(BME_Edge *e,BME_Poly *f)
 607 {
 608
 609         BME_Loop *curloop;
 610         int i, len;
 611
 612         len = BME_cycle_length(&(e->loop->radial));
 613         for(i = 0, curloop = e->loop; i < len; i++, curloop = curloop->radial.next->data){
 614                 if(curloop->f == f) return 1;
 615         }
 616         return 0;
 617 }
 618
 619 struct BME_Loop *BME_loop_find_loop(struct BME_Poly *f, struct BME_Vert *v) {
 620         BME_Loop *l;
 621         int i, len;
 622
 623         len = BME_cycle_length(f->loopbase);
 624         for (i = 0, l=f->loopbase; i < len; i++, l=l->next) {
 625                 if (l->v == v) return l;
 626         }
 627         return NULL;
 628 }