2
* BME_structure.c jan 2007
4
* Low level routines for manipulating the BMesh structure.
6
* $Id: BME_structure.c,v 1.00 2007/01/17 17:42:01 Briggs Exp $
8
* ***** BEGIN GPL LICENSE BLOCK *****
10
* This program is free software; you can redistribute it and/or
11
* modify it under the terms of the GNU General Public License
12
* as published by the Free Software Foundation; either version 2
13
* of the License, or (at your option) any later version.
16
* This program is distributed in the hope that it will be useful,
17
* but WITHOUT ANY WARRANTY; without even the implied warranty of
18
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19
* GNU General Public License for more details.
21
* You should have received a copy of the GNU General Public License
22
* along with this program; if not, write to the Free Software Foundation,
23
* Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
25
* The Original Code is Copyright (C) 2007 Blender Foundation.
26
* All rights reserved.
28
* The Original Code is: all of this file.
30
* Contributor(s): Geoffrey Bantle.
32
* ***** END GPL LICENSE BLOCK *****
36
#include "MEM_guardedalloc.h"
38
#include "DNA_listBase.h"
39
#include "BKE_utildefines.h"
40
#include "BKE_bmesh.h"
41
#include "BLI_blenlib.h"
42
#include "BLI_linklist.h"
43
#include "BLI_ghash.h"
45
* MISC utility functions.
49
int BME_vert_in_edge(BME_Edge *e, BME_Vert *v){
50
if(e->v1 == v || e->v2 == v) return 1;
53
int BME_verts_in_edge(BME_Vert *v1, BME_Vert *v2, BME_Edge *e){
54
if(e->v1 == v1 && e->v2 == v2) return 1;
55
else if(e->v1 == v2 && e->v2 == v1) return 1;
59
BME_Vert *BME_edge_getothervert(BME_Edge *e, BME_Vert *v){
60
if(e->v1 == v) return e->v2;
61
else if(e->v2 == v) return e->v1;
65
int BME_edge_swapverts(BME_Edge *e, BME_Vert *orig, BME_Vert *new){
72
else if(e->v2 == orig){
82
* ALLOCATION/DEALLOCATION FUNCTIONS
85
BME_Vert *BME_addvertlist(BME_Mesh *bm, BME_Vert *example){
87
v = BLI_mempool_alloc(bm->vpool);
88
v->next = v->prev = NULL;
90
v->co[0] = v->co[1] = v->co[2] = 0.0f;
91
v->no[0] = v->no[1] = v->no[2] = 0.0f;
94
v->eflag1 = v->eflag2 = v->tflag1 = v->tflag2 = 0;
97
BLI_addtail(&(bm->verts), v);
102
VECCOPY(v->co,example->co);
103
CustomData_bmesh_copy_data(&bm->vdata, &bm->vdata, example->data, &v->data);
106
CustomData_bmesh_set_default(&bm->vdata, &v->data);
110
BME_Edge *BME_addedgelist(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Edge *example){
112
e = BLI_mempool_alloc(bm->epool);
113
e->next = e->prev = NULL;
117
e->d1.next = e->d1.prev = e->d2.next = e->d2.prev = NULL;
122
e->eflag1 = e->eflag2 = e->tflag1 = e->tflag2 = 0;
124
e->crease = e->bweight = 0.0f;
127
BLI_addtail(&(bm->edges), e);
130
CustomData_bmesh_copy_data(&bm->edata, &bm->edata, example->data, &e->data);
132
CustomData_bmesh_set_default(&bm->edata, &e->data);
137
BME_Loop *BME_create_loop(BME_Mesh *bm, BME_Vert *v, BME_Edge *e, BME_Poly *f, BME_Loop *example){
139
l = BLI_mempool_alloc(bm->lpool);
140
l->next = l->prev = NULL;
142
l->radial.next = l->radial.prev = NULL;
148
l->eflag1 = l->eflag2 = l->tflag1 = l->tflag2 = 0;
149
l->flag = l->h = 0; //stupid waste!
154
CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, example->data, &l->data);
156
CustomData_bmesh_set_default(&bm->ldata, &l->data);
161
BME_Poly *BME_addpolylist(BME_Mesh *bm, BME_Poly *example){
163
f = BLI_mempool_alloc(bm->ppool);
164
f->next = f->prev = NULL;
169
f->eflag1 = f->eflag2 = f->tflag1 = f->tflag2 = 0;
170
f->flag = f->h = f->mat_nr;
171
BLI_addtail(&(bm->polys),f);
176
CustomData_bmesh_copy_data(&bm->pdata, &bm->pdata, example->data, &f->data);
178
CustomData_bmesh_set_default(&bm->pdata, &f->data);
184
/* free functions dont do much *yet*. When per-vertex, per-edge and per-face/faceloop
185
data is added though these will be needed.
187
void BME_free_vert(BME_Mesh *bm, BME_Vert *v){
189
CustomData_bmesh_free_block(&bm->vdata, &v->data);
190
BLI_mempool_free(bm->vpool, v);
192
void BME_free_edge(BME_Mesh *bm, BME_Edge *e){
194
CustomData_bmesh_free_block(&bm->edata, &e->data);
195
BLI_mempool_free(bm->epool, e);
197
void BME_free_poly(BME_Mesh *bm, BME_Poly *f){
199
CustomData_bmesh_free_block(&bm->pdata, &f->data);
200
BLI_mempool_free(bm->ppool, f);
202
void BME_free_loop(BME_Mesh *bm, BME_Loop *l){
204
CustomData_bmesh_free_block(&bm->ldata, &l->data);
205
BLI_mempool_free(bm->lpool, l);
210
* Cycles are circular doubly linked lists that form the basis of adjacency
211
* information in the BME modeller. Full adjacency relations can be derived
212
* from examining these cycles very quickly. Although each cycle is a double
213
* circular linked list, each one is considered to have a 'base' or 'head',
214
* and care must be taken by Euler code when modifying the contents of a cycle.
216
* The contents of this file are split into two parts. First there are the
217
* BME_cycle family of functions which are generic circular double linked list
218
* procedures. The second part contains higher level procedures for supporting
219
* modification of specific cycle types.
221
* The three cycles explicitly stored in the BMesh data structure are as follows:
223
* 1: The Disk Cycle - A circle of edges around a vertex
224
* Base: vertex->edge pointer.
226
* This cycle is the most complicated in terms of its structure. Each BME_Edge contains
227
* two BME_CycleNode structures to keep track of that edge's membership in the disk cycle
228
* of each of its vertices. However for any given vertex it may be the first in some edges
229
* in its disk cycle and the second for others. The BME_disk_XXX family of functions contain
230
* some nice utilities for navigating disk cycles in a way that hides this detail from the
233
* Note that the disk cycle is completley independant from face data. One advantage of this
234
* is that wire edges are fully integrated into the topology database. Another is that the
235
* the disk cycle has no problems dealing with non-manifold conditions involving faces.
237
* Functions relating to this cycle:
239
* BME_disk_append_edge
240
* BME_disk_remove_edge
242
* BME_disk_getpointer
244
* 2: The Radial Cycle - A circle of face edges (BME_Loop) around an edge
245
* Base: edge->loop->radial structure.
247
* The radial cycle is similar to the radial cycle in the radial edge data structure.*
248
* Unlike the radial edge however, the radial cycle does not require a large amount of memory
249
* to store non-manifold conditions since BMesh does not keep track of region/shell
252
* Functions relating to this cycle:
255
* BME_radial_remove_loop
256
* BME_radial_nextloop
257
* BME_radial_find_face
260
* 3: The Loop Cycle - A circle of face edges around a polygon.
261
* Base: polygon->loopbase.
263
* The loop cycle keeps track of a faces vertices and edges. It should be noted that the
264
* direction of a loop cycle is either CW or CCW depending on the face normal, and is
265
* not oriented to the faces editedges.
267
* Functions relating to this cycle:
269
* BME_cycle_XXX family of functions.
272
* Note that the order of elements in all cycles except the loop cycle is undefined. This
273
* leads to slightly increased seek time for deriving some adjacency relations, however the
274
* advantage is that no intrinsic properties of the data structures are dependant upon the
275
* cycle order and all non-manifold conditions are represented trivially.
280
void BME_cycle_append(void *h, void *nt)
282
BME_CycleNode *oldtail, *head, *newtail;
284
head = (BME_CycleNode*)h;
285
newtail = (BME_CycleNode*)nt;
287
if(head->next == NULL){
288
head->next = newtail;
289
head->prev = newtail;
290
newtail->next = head;
291
newtail->prev = head;
294
oldtail = head->prev;
295
oldtail->next = newtail;
296
newtail->next = head;
297
newtail->prev = oldtail;
298
head->prev = newtail;
306
* Count the nodes in a cycle.
312
int BME_cycle_length(void *h){
315
BME_CycleNode *head, *curnode;
316
head = (BME_CycleNode*)h;
320
for(curnode = head->next; curnode != head; curnode=curnode->next){
321
if(len == INT_MAX){ //check for infinite loop/corrupted cycle
334
* Removes a node from a cycle.
337
* 1 for success, 0 for failure.
340
int BME_cycle_remove(void *h, void *remn)
343
BME_CycleNode *head, *remnode, *curnode;
345
head = (BME_CycleNode*)h;
346
remnode = (BME_CycleNode*)remn;
347
len = BME_cycle_length(h);
349
if(len == 1 && head == remnode){
355
for(i=0, curnode = head; i < len; curnode = curnode->next){
356
if(curnode == remnode){
357
remnode->prev->next = remnode->next;
358
remnode->next->prev = remnode->prev;
359
/*zero out remnode pointers, important!*/
360
//remnode->next = NULL;
361
//remnode->prev = NULL;
373
* Validates a cycle. Takes as an argument the expected length of the cycle and
374
* a pointer to the cycle head or base.
378
* 1 for success, 0 for failure.
381
int BME_cycle_validate(int len, void *h){
383
BME_CycleNode *curnode, *head;
384
head = (BME_CycleNode*)h;
386
/*forward validation*/
387
for(i = 0, curnode = head; i < len; i++, curnode = curnode->next);
388
if(curnode != head) return 0;
390
/*reverse validation*/
391
for(i = 0, curnode = head; i < len; i++, curnode = curnode->prev);
392
if(curnode != head) return 0;
397
/*Begin Disk Cycle routines*/
402
* Find the next edge in a disk cycle
405
* Pointer to the next edge in the disk cycle for the vertex v.
408
BME_Edge *BME_disk_nextedge(BME_Edge *e, BME_Vert *v)
410
if(BME_vert_in_edge(e, v)){
411
if(e->v1 == v) return e->d1.next->data;
412
else if(e->v2 == v) return e->d2.next->data;
418
* BME_disk_getpointer
420
* Given an edge and one of its vertices, find the apporpriate CycleNode
423
* Pointer to BME_CycleNode.
425
BME_CycleNode *BME_disk_getpointer(BME_Edge *e, BME_Vert *v){
426
/*returns pointer to the cycle node for the appropriate vertex in this disk*/
427
if(e->v1 == v) return &(e->d1);
428
else if (e->v2 == v) return &(e->d2);
433
* BME_disk_append_edge
435
* Appends edge to the end of a vertex disk cycle.
438
* 1 for success, 0 for failure
441
int BME_disk_append_edge(BME_Edge *e, BME_Vert *v)
444
BME_CycleNode *base, *tail;
446
if(BME_vert_in_edge(e, v) == 0) return 0; /*check to make sure v is in e*/
448
/*check for loose vert first*/
451
base = tail = BME_disk_getpointer(e, v);
452
BME_cycle_append(base, tail); /*circular reference is ok!*/
456
/*insert e at the end of disk cycle and make it the new v->edge*/
457
base = BME_disk_getpointer(v->edge, v);
458
tail = BME_disk_getpointer(e, v);
459
BME_cycle_append(base, tail);
464
* BME_disk_remove_edge
466
* Removes an edge from a disk cycle. If the edge to be removed is
467
* at the base of the cycle, the next edge becomes the new base.
474
void BME_disk_remove_edge(BME_Edge *e, BME_Vert *v)
476
BME_CycleNode *base, *remnode;
480
base = BME_disk_getpointer(v->edge, v);
481
remnode = BME_disk_getpointer(e, v);
483
/*first deal with v->edge pointer...*/
484
len = BME_cycle_length(base);
485
if(len == 1) newbase = NULL;
486
else if(v->edge == e) newbase = base->next-> data;
487
else newbase = v->edge;
489
/*remove and rebase*/
490
BME_cycle_remove(base, remnode);
495
* BME_disk_next_edgeflag
497
* Searches the disk cycle of v, starting with e, for the
498
* next edge that has either eflag or tflag.
503
BME_Edge *BME_disk_next_edgeflag(BME_Edge *e, BME_Vert *v, int eflag, int tflag){
505
BME_CycleNode *diskbase;
509
if(eflag && tflag) return NULL;
511
ok = BME_vert_in_edge(e,v);
513
diskbase = BME_disk_getpointer(e, v);
514
len = BME_cycle_length(diskbase);
515
curedge = BME_disk_nextedge(e,v);
518
if(curedge->tflag1 == tflag) return curedge;
521
if(curedge->eflag1 == eflag) return curedge;
523
curedge = BME_disk_nextedge(curedge, v);
530
* BME_disk_count_edgeflag
532
* Counts number of edges in this verts disk cycle which have
533
* either eflag or tflag (but not both!)
539
int BME_disk_count_edgeflag(BME_Vert *v, int eflag, int tflag){
540
BME_CycleNode *diskbase;
542
int i, len=0, count=0;
545
if(eflag && tflag) return 0; /*tflag and eflag are reserved for different functions!*/
546
diskbase = BME_disk_getpointer(v->edge, v);
547
len = BME_cycle_length(diskbase);
549
for(i = 0, curedge=v->edge; i<len; i++){
551
if(curedge->tflag1 == tflag) count++;
554
if(curedge->eflag1 == eflag) count++;
556
curedge = BME_disk_nextedge(curedge, v);
562
int BME_disk_hasedge(BME_Vert *v, BME_Edge *e){
563
BME_CycleNode *diskbase;
568
diskbase = BME_disk_getpointer(v->edge,v);
569
len = BME_cycle_length(diskbase);
571
for(i = 0, curedge=v->edge; i<len; i++){
572
if(curedge == e) return 1;
573
else curedge=BME_disk_nextedge(curedge, v);
578
/*end disk cycle routines*/
580
BME_Loop *BME_radial_nextloop(BME_Loop *l){
581
return (BME_Loop*)(l->radial.next->data);
584
void BME_radial_append(BME_Edge *e, BME_Loop *l){
585
if(e->loop == NULL) e->loop = l;
586
BME_cycle_append(&(e->loop->radial), &(l->radial));
589
void BME_radial_remove_loop(BME_Loop *l, BME_Edge *e)
594
/*deal with edge->loop pointer*/
595
len = BME_cycle_length(&(e->loop->radial));
596
if(len == 1) newbase = NULL;
597
else if(e->loop == l) newbase = e->loop->radial.next->data;
598
else newbase = e->loop;
600
/*remove and rebase*/
601
BME_cycle_remove(&(e->loop->radial), &(l->radial));
605
int BME_radial_find_face(BME_Edge *e,BME_Poly *f)
611
len = BME_cycle_length(&(e->loop->radial));
612
for(i = 0, curloop = e->loop; i < len; i++, curloop = curloop->radial.next->data){
613
if(curloop->f == f) return 1;
618
struct BME_Loop *BME_loop_find_loop(struct BME_Poly *f, struct BME_Vert *v) {
622
len = BME_cycle_length(f->loopbase);
623
for (i = 0, l=f->loopbase; i < len; i++, l=l->next) {
624
if (l->v == v) return l;
2
* BME_structure.c jan 2007
4
* Low level routines for manipulating the BMesh structure.
6
* $Id: BME_structure.c 19485 2009-03-31 22:34:34Z gsrb3d $
8
* ***** BEGIN GPL LICENSE BLOCK *****
10
* This program is free software; you can redistribute it and/or
11
* modify it under the terms of the GNU General Public License
12
* as published by the Free Software Foundation; either version 2
13
* of the License, or (at your option) any later version.
16
* This program is distributed in the hope that it will be useful,
17
* but WITHOUT ANY WARRANTY; without even the implied warranty of
18
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19
* GNU General Public License for more details.
21
* You should have received a copy of the GNU General Public License
22
* along with this program; if not, write to the Free Software Foundation,
23
* Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
25
* The Original Code is Copyright (C) 2007 Blender Foundation.
26
* All rights reserved.
28
* The Original Code is: all of this file.
30
* Contributor(s): Geoffrey Bantle.
32
* ***** END GPL LICENSE BLOCK *****
36
#include "MEM_guardedalloc.h"
38
#include "DNA_listBase.h"
39
#include "BKE_utildefines.h"
40
#include "BKE_bmesh.h"
41
#include "BLI_blenlib.h"
42
#include "BLI_linklist.h"
43
#include "BLI_ghash.h"
45
* MISC utility functions.
49
int BME_vert_in_edge(BME_Edge *e, BME_Vert *v){
50
if(e->v1 == v || e->v2 == v) return 1;
53
int BME_verts_in_edge(BME_Vert *v1, BME_Vert *v2, BME_Edge *e){
54
if(e->v1 == v1 && e->v2 == v2) return 1;
55
else if(e->v1 == v2 && e->v2 == v1) return 1;
59
BME_Vert *BME_edge_getothervert(BME_Edge *e, BME_Vert *v){
60
if(e->v1 == v) return e->v2;
61
else if(e->v2 == v) return e->v1;
65
int BME_edge_swapverts(BME_Edge *e, BME_Vert *orig, BME_Vert *new){
72
else if(e->v2 == orig){
82
* ALLOCATION/DEALLOCATION FUNCTIONS
85
BME_Vert *BME_addvertlist(BME_Mesh *bm, BME_Vert *example){
87
v = BLI_mempool_alloc(bm->vpool);
88
v->next = v->prev = NULL;
90
v->co[0] = v->co[1] = v->co[2] = 0.0f;
91
v->no[0] = v->no[1] = v->no[2] = 0.0f;
94
v->eflag1 = v->eflag2 = v->tflag1 = v->tflag2 = 0;
97
BLI_addtail(&(bm->verts), v);
102
VECCOPY(v->co,example->co);
103
CustomData_bmesh_copy_data(&bm->vdata, &bm->vdata, example->data, &v->data);
106
CustomData_bmesh_set_default(&bm->vdata, &v->data);
110
BME_Edge *BME_addedgelist(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Edge *example){
112
e = BLI_mempool_alloc(bm->epool);
113
e->next = e->prev = NULL;
117
e->d1.next = e->d1.prev = e->d2.next = e->d2.prev = NULL;
122
e->eflag1 = e->eflag2 = e->tflag1 = e->tflag2 = 0;
124
e->crease = e->bweight = 0.0f;
127
BLI_addtail(&(bm->edges), e);
130
CustomData_bmesh_copy_data(&bm->edata, &bm->edata, example->data, &e->data);
132
CustomData_bmesh_set_default(&bm->edata, &e->data);
137
BME_Loop *BME_create_loop(BME_Mesh *bm, BME_Vert *v, BME_Edge *e, BME_Poly *f, BME_Loop *example){
139
l = BLI_mempool_alloc(bm->lpool);
140
l->next = l->prev = NULL;
142
l->radial.next = l->radial.prev = NULL;
148
l->eflag1 = l->eflag2 = l->tflag1 = l->tflag2 = 0;
149
l->flag = l->h = 0; //stupid waste!
154
CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, example->data, &l->data);
156
CustomData_bmesh_set_default(&bm->ldata, &l->data);
161
BME_Poly *BME_addpolylist(BME_Mesh *bm, BME_Poly *example){
163
f = BLI_mempool_alloc(bm->ppool);
164
f->next = f->prev = NULL;
169
f->eflag1 = f->eflag2 = f->tflag1 = f->tflag2 = 0;
170
f->flag = f->h = f->mat_nr;
171
BLI_addtail(&(bm->polys),f);
176
CustomData_bmesh_copy_data(&bm->pdata, &bm->pdata, example->data, &f->data);
178
CustomData_bmesh_set_default(&bm->pdata, &f->data);
184
/* free functions dont do much *yet*. When per-vertex, per-edge and per-face/faceloop
185
data is added though these will be needed.
187
void BME_free_vert(BME_Mesh *bm, BME_Vert *v){
189
CustomData_bmesh_free_block(&bm->vdata, &v->data);
190
BLI_mempool_free(bm->vpool, v);
192
void BME_free_edge(BME_Mesh *bm, BME_Edge *e){
194
CustomData_bmesh_free_block(&bm->edata, &e->data);
195
BLI_mempool_free(bm->epool, e);
197
void BME_free_poly(BME_Mesh *bm, BME_Poly *f){
199
CustomData_bmesh_free_block(&bm->pdata, &f->data);
200
BLI_mempool_free(bm->ppool, f);
202
void BME_free_loop(BME_Mesh *bm, BME_Loop *l){
204
CustomData_bmesh_free_block(&bm->ldata, &l->data);
205
BLI_mempool_free(bm->lpool, l);
210
* Cycles are circular doubly linked lists that form the basis of adjacency
211
* information in the BME modeller. Full adjacency relations can be derived
212
* from examining these cycles very quickly. Although each cycle is a double
213
* circular linked list, each one is considered to have a 'base' or 'head',
214
* and care must be taken by Euler code when modifying the contents of a cycle.
216
* The contents of this file are split into two parts. First there are the
217
* BME_cycle family of functions which are generic circular double linked list
218
* procedures. The second part contains higher level procedures for supporting
219
* modification of specific cycle types.
221
* The three cycles explicitly stored in the BMesh data structure are as follows:
223
* 1: The Disk Cycle - A circle of edges around a vertex
224
* Base: vertex->edge pointer.
226
* This cycle is the most complicated in terms of its structure. Each BME_Edge contains
227
* two BME_CycleNode structures to keep track of that edge's membership in the disk cycle
228
* of each of its vertices. However for any given vertex it may be the first in some edges
229
* in its disk cycle and the second for others. The BME_disk_XXX family of functions contain
230
* some nice utilities for navigating disk cycles in a way that hides this detail from the
233
* Note that the disk cycle is completley independant from face data. One advantage of this
234
* is that wire edges are fully integrated into the topology database. Another is that the
235
* the disk cycle has no problems dealing with non-manifold conditions involving faces.
237
* Functions relating to this cycle:
239
* BME_disk_append_edge
240
* BME_disk_remove_edge
242
* BME_disk_getpointer
244
* 2: The Radial Cycle - A circle of face edges (BME_Loop) around an edge
245
* Base: edge->loop->radial structure.
247
* The radial cycle is similar to the radial cycle in the radial edge data structure.*
248
* Unlike the radial edge however, the radial cycle does not require a large amount of memory
249
* to store non-manifold conditions since BMesh does not keep track of region/shell
252
* Functions relating to this cycle:
255
* BME_radial_remove_loop
256
* BME_radial_nextloop
257
* BME_radial_find_face
260
* 3: The Loop Cycle - A circle of face edges around a polygon.
261
* Base: polygon->loopbase.
263
* The loop cycle keeps track of a faces vertices and edges. It should be noted that the
264
* direction of a loop cycle is either CW or CCW depending on the face normal, and is
265
* not oriented to the faces editedges.
267
* Functions relating to this cycle:
269
* BME_cycle_XXX family of functions.
272
* Note that the order of elements in all cycles except the loop cycle is undefined. This
273
* leads to slightly increased seek time for deriving some adjacency relations, however the
274
* advantage is that no intrinsic properties of the data structures are dependant upon the
275
* cycle order and all non-manifold conditions are represented trivially.
280
void BME_cycle_append(void *h, void *nt)
282
BME_CycleNode *oldtail, *head, *newtail;
284
head = (BME_CycleNode*)h;
285
newtail = (BME_CycleNode*)nt;
287
if(head->next == NULL){
288
head->next = newtail;
289
head->prev = newtail;
290
newtail->next = head;
291
newtail->prev = head;
294
oldtail = head->prev;
295
oldtail->next = newtail;
296
newtail->next = head;
297
newtail->prev = oldtail;
298
head->prev = newtail;
306
* Count the nodes in a cycle.
312
int BME_cycle_length(void *h){
315
BME_CycleNode *head, *curnode;
316
head = (BME_CycleNode*)h;
320
for(curnode = head->next; curnode != head; curnode=curnode->next){
321
if(len == INT_MAX){ //check for infinite loop/corrupted cycle
334
* Removes a node from a cycle.
337
* 1 for success, 0 for failure.
340
int BME_cycle_remove(void *h, void *remn)
343
BME_CycleNode *head, *remnode, *curnode;
345
head = (BME_CycleNode*)h;
346
remnode = (BME_CycleNode*)remn;
347
len = BME_cycle_length(h);
349
if(len == 1 && head == remnode){
355
for(i=0, curnode = head; i < len; curnode = curnode->next){
356
if(curnode == remnode){
357
remnode->prev->next = remnode->next;
358
remnode->next->prev = remnode->prev;
359
/*zero out remnode pointers, important!*/
360
//remnode->next = NULL;
361
//remnode->prev = NULL;
373
* Validates a cycle. Takes as an argument the expected length of the cycle and
374
* a pointer to the cycle head or base.
378
* 1 for success, 0 for failure.
381
int BME_cycle_validate(int len, void *h){
383
BME_CycleNode *curnode, *head;
384
head = (BME_CycleNode*)h;
386
/*forward validation*/
387
for(i = 0, curnode = head; i < len; i++, curnode = curnode->next);
388
if(curnode != head) return 0;
390
/*reverse validation*/
391
for(i = 0, curnode = head; i < len; i++, curnode = curnode->prev);
392
if(curnode != head) return 0;
397
/*Begin Disk Cycle routines*/
402
* Find the next edge in a disk cycle
405
* Pointer to the next edge in the disk cycle for the vertex v.
408
BME_Edge *BME_disk_nextedge(BME_Edge *e, BME_Vert *v)
410
if(BME_vert_in_edge(e, v)){
411
if(e->v1 == v) return e->d1.next->data;
412
else if(e->v2 == v) return e->d2.next->data;
418
* BME_disk_getpointer
420
* Given an edge and one of its vertices, find the apporpriate CycleNode
423
* Pointer to BME_CycleNode.
425
BME_CycleNode *BME_disk_getpointer(BME_Edge *e, BME_Vert *v){
426
/*returns pointer to the cycle node for the appropriate vertex in this disk*/
427
if(e->v1 == v) return &(e->d1);
428
else if (e->v2 == v) return &(e->d2);
433
* BME_disk_append_edge
435
* Appends edge to the end of a vertex disk cycle.
438
* 1 for success, 0 for failure
441
int BME_disk_append_edge(BME_Edge *e, BME_Vert *v)
444
BME_CycleNode *base, *tail;
446
if(BME_vert_in_edge(e, v) == 0) return 0; /*check to make sure v is in e*/
448
/*check for loose vert first*/
451
base = tail = BME_disk_getpointer(e, v);
452
BME_cycle_append(base, tail); /*circular reference is ok!*/
456
/*insert e at the end of disk cycle and make it the new v->edge*/
457
base = BME_disk_getpointer(v->edge, v);
458
tail = BME_disk_getpointer(e, v);
459
BME_cycle_append(base, tail);
464
* BME_disk_remove_edge
466
* Removes an edge from a disk cycle. If the edge to be removed is
467
* at the base of the cycle, the next edge becomes the new base.
474
void BME_disk_remove_edge(BME_Edge *e, BME_Vert *v)
476
BME_CycleNode *base, *remnode;
480
base = BME_disk_getpointer(v->edge, v);
481
remnode = BME_disk_getpointer(e, v);
483
/*first deal with v->edge pointer...*/
484
len = BME_cycle_length(base);
485
if(len == 1) newbase = NULL;
486
else if(v->edge == e) newbase = base->next-> data;
487
else newbase = v->edge;
489
/*remove and rebase*/
490
BME_cycle_remove(base, remnode);
495
* BME_disk_next_edgeflag
497
* Searches the disk cycle of v, starting with e, for the
498
* next edge that has either eflag or tflag.
503
BME_Edge *BME_disk_next_edgeflag(BME_Edge *e, BME_Vert *v, int eflag, int tflag){
505
BME_CycleNode *diskbase;
509
if(eflag && tflag) return NULL;
511
ok = BME_vert_in_edge(e,v);
513
diskbase = BME_disk_getpointer(e, v);
514
len = BME_cycle_length(diskbase);
515
curedge = BME_disk_nextedge(e,v);
518
if(curedge->tflag1 == tflag) return curedge;
521
if(curedge->eflag1 == eflag) return curedge;
523
curedge = BME_disk_nextedge(curedge, v);
530
* BME_disk_count_edgeflag
532
* Counts number of edges in this verts disk cycle which have
533
* either eflag or tflag (but not both!)
539
int BME_disk_count_edgeflag(BME_Vert *v, int eflag, int tflag){
540
BME_CycleNode *diskbase;
542
int i, len=0, count=0;
545
if(eflag && tflag) return 0; /*tflag and eflag are reserved for different functions!*/
546
diskbase = BME_disk_getpointer(v->edge, v);
547
len = BME_cycle_length(diskbase);
549
for(i = 0, curedge=v->edge; i<len; i++){
551
if(curedge->tflag1 == tflag) count++;
554
if(curedge->eflag1 == eflag) count++;
556
curedge = BME_disk_nextedge(curedge, v);
562
int BME_disk_hasedge(BME_Vert *v, BME_Edge *e){
563
BME_CycleNode *diskbase;
568
diskbase = BME_disk_getpointer(v->edge,v);
569
len = BME_cycle_length(diskbase);
571
for(i = 0, curedge=v->edge; i<len; i++){
572
if(curedge == e) return 1;
573
else curedge=BME_disk_nextedge(curedge, v);
578
/*end disk cycle routines*/
580
BME_Loop *BME_radial_nextloop(BME_Loop *l){
581
return (BME_Loop*)(l->radial.next->data);
584
void BME_radial_append(BME_Edge *e, BME_Loop *l){
585
if(e->loop == NULL) e->loop = l;
586
BME_cycle_append(&(e->loop->radial), &(l->radial));
589
void BME_radial_remove_loop(BME_Loop *l, BME_Edge *e)
594
/*deal with edge->loop pointer*/
595
len = BME_cycle_length(&(e->loop->radial));
596
if(len == 1) newbase = NULL;
597
else if(e->loop == l) newbase = e->loop->radial.next->data;
598
else newbase = e->loop;
600
/*remove and rebase*/
601
BME_cycle_remove(&(e->loop->radial), &(l->radial));
605
int BME_radial_find_face(BME_Edge *e,BME_Poly *f)
611
len = BME_cycle_length(&(e->loop->radial));
612
for(i = 0, curloop = e->loop; i < len; i++, curloop = curloop->radial.next->data){
613
if(curloop->f == f) return 1;
618
struct BME_Loop *BME_loop_find_loop(struct BME_Poly *f, struct BME_Vert *v) {
622
len = BME_cycle_length(f->loopbase);
623
for (i = 0, l=f->loopbase; i < len; i++, l=l->next) {
624
if (l->v == v) return l;
added
removed
source/blender/blenkernel/intern/BME_structure.c
