diff options
author | Andrew Wiggin <ender79bl@gmail.com> | 2011-09-23 18:38:45 +0400 |
---|---|---|
committer | Andrew Wiggin <ender79bl@gmail.com> | 2011-09-23 18:38:45 +0400 |
commit | bf95e3c34e0f2a3b4011abf1720d4c7df46204e7 (patch) | |
tree | 755f65045a4825d78ef541ee63a5230a28616dae /source/blender/bmesh | |
parent | d7a5429f421c9677035a91553c882a4d10e56086 (diff) |
Port jfke and jekv euler functions to new bmesh structures
Diffstat (limited to 'source/blender/bmesh')
-rw-r--r-- | source/blender/bmesh/intern/bmesh_newcore.c | 301 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_private.h | 2 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_structure.c | 47 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_structure.h | 5 |
4 files changed, 345 insertions, 10 deletions
diff --git a/source/blender/bmesh/intern/bmesh_newcore.c b/source/blender/bmesh/intern/bmesh_newcore.c index 71753776b6a..3566c6c5f13 100644 --- a/source/blender/bmesh/intern/bmesh_newcore.c +++ b/source/blender/bmesh/intern/bmesh_newcore.c @@ -1035,16 +1035,16 @@ BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **re){ BMLoop *nextl; BMEdge *ne; BMVert *nv, *ov; - int i, edok, valance1=0, valance2=0; + int i, edok, valence1=0, valence2=0; if(bmesh_vert_in_edge(e,tv) == 0) return NULL; ov = bmesh_edge_getothervert(e,tv); - /*count valance of v1*/ - valance1 = bmesh_disk_count(ov); + /*count valence of v1*/ + valence1 = bmesh_disk_count(ov); - /*count valance of v2*/ - valance2 = bmesh_disk_count(tv); + /*count valence of v2*/ + valence2 = bmesh_disk_count(tv); nv = BM_Make_Vert(bm, tv->co, tv); ne = BM_Make_Edge(bm, nv, tv, e, 0); @@ -1068,9 +1068,9 @@ BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **re){ bmesh_disk_append_edge(ne, tv); /*verify disk cycles*/ - edok = bmesh_disk_validate(valance1, ov->e, ov); + edok = bmesh_disk_validate(valence1, ov->e, ov); if(!edok) bmesh_error(); - edok = bmesh_disk_validate(valance2, tv->e, tv); + edok = bmesh_disk_validate(valence2, tv->e, tv); if(!edok) bmesh_error(); edok = bmesh_disk_validate(2, nv->e, nv); if(!edok) bmesh_error(); @@ -1178,9 +1178,296 @@ BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **re){ CHECK_ELEMENT(bm, ne); CHECK_ELEMENT(bm, nv); + CHECK_ELEMENT(bm, ov); CHECK_ELEMENT(bm, e); CHECK_ELEMENT(bm, tv); if(re) *re = ne; return nv; } + +/** + * bmesh_JEKV + * + * JOIN EDGE KILL VERT: + * Takes a an edge and pointer to one of its vertices and collapses + * the edge on that vertex. + * + * Before: OE KE + * ------- ------- + * | || | + * OV KV TV + * + * + * After: OE + * --------------- + * | | + * OV TV + * + * + * Restrictions: + * KV is a vertex that must have a valance of exactly two. Furthermore + * both edges in KV's disk cycle (OE and KE) must be unique (no double + * edges). + * + * It should also be noted that this euler has the possibility of creating + * faces with just 2 edges. It is up to the caller to decide what to do with + * these faces. + * + * Returns - + * 1 for success, 0 for failure. + */ +int bmesh_jekv(BMesh *bm, BMEdge *ke, BMVert *kv) +{ + BMEdge *oe; + BMVert *ov, *tv; + BMLoop *killoop, *l; + int len,radlen=0, halt = 0, i, valence1, valence2,edok; + BMLoop **loops = NULL; + BLI_array_staticdeclare(loops, 256); + + if(bmesh_vert_in_edge(ke,kv) == 0) return 0; + len = bmesh_disk_count(kv); + + if(len == 2){ + oe = bmesh_disk_nextedge(ke, kv); + tv = bmesh_edge_getothervert(ke, kv); + ov = bmesh_edge_getothervert(oe, kv); + halt = bmesh_verts_in_edge(kv, tv, oe); /*check for double edges*/ + + if(halt) return 0; + else{ + /*For verification later, count valence of ov and tv*/ + valence1 = bmesh_disk_count(ov); + valence2 = bmesh_disk_count(tv); + + /*remove oe from kv's disk cycle*/ + bmesh_disk_remove_edge(oe,kv); + /*relink oe->kv to be oe->tv*/ + bmesh_edge_swapverts(oe, kv, tv); + /*append oe to tv's disk cycle*/ + bmesh_disk_append_edge(oe, tv); + /*remove ke from tv's disk cycle*/ + bmesh_disk_remove_edge(ke, tv); + + /*deal with radial cycle of ke*/ + radlen = bmesh_radial_length(ke->l); + if(ke->l){ + /*first step, fix the neighboring loops of all loops in ke's radial cycle*/ + for(i=0,killoop = ke->l; i<radlen; i++, killoop = bmesh_radial_nextloop(killoop)){ + /*relink loops and fix vertex pointer*/ + if( killoop->next->v == kv ) killoop->next->v = tv; + + killoop->next->prev = killoop->prev; + killoop->prev->next = killoop->next; + if (bm_firstfaceloop(killoop->f) == killoop) + bm_firstfaceloop(killoop->f) = killoop->next; + killoop->next = NULL; + killoop->prev = NULL; + + /*fix len attribute of face*/ + killoop->f->len--; + } + /*second step, remove all the hanging loops attached to ke*/ + killoop = ke->l; + radlen = bmesh_radial_length(ke->l); + /*this should be wrapped into a bme_free_radial function to be used by bmesh_KF as well...*/ + for (i=0;i<radlen;i++) { + BLI_array_growone(loops); + loops[BLI_array_count(loops)-1] = killoop; + killoop = bmesh_radial_nextloop(killoop); + } + for (i=0;i<radlen;i++) { + bm->totloop--; + BLI_mempool_free(bm->lpool, loops[i]); + } + /*Validate radial cycle of oe*/ + edok = bmesh_radial_validate(radlen,oe->l); + if(!edok) bmesh_error(); + } + + /*deallocate edge*/ + BM_remove_selection(bm, ke); + BLI_mempool_free(bm->toolflagpool, ke->head.flags); + BLI_mempool_free(bm->epool, ke); + bm->totedge--; + /*deallocate vertex*/ + BM_remove_selection(bm, kv); + BLI_mempool_free(bm->toolflagpool, kv->head.flags); + BLI_mempool_free(bm->vpool, kv); + bm->totvert--; + + /*Validate disk cycle lengths of ov,tv are unchanged*/ + edok = bmesh_disk_validate(valence1, ov->e, ov); + if(!edok) bmesh_error(); + edok = bmesh_disk_validate(valence2, tv->e, tv); + if(!edok) bmesh_error(); + + /*Validate loop cycle of all faces attached to oe*/ + for(i=0,l = oe->l; i<radlen; i++, l = bmesh_radial_nextloop(l)){ + if(l->e != oe) bmesh_error(); + edok = bmesh_verts_in_edge(l->v, l->next->v, oe); + if(!edok) bmesh_error(); + edok = bmesh_loop_validate(l->f); + if(!edok) bmesh_error(); + + CHECK_ELEMENT(bm, l); + CHECK_ELEMENT(bm, l->v); + CHECK_ELEMENT(bm, l->e); + CHECK_ELEMENT(bm, l->f); + } + + CHECK_ELEMENT(bm, ov); + CHECK_ELEMENT(bm, tv); + CHECK_ELEMENT(bm, oe); + + return 1; + } + } + return 0; +} + +/** + * bmesh_JFKE + * + * JOIN FACE KILL EDGE: + * + * Takes two faces joined by a single 2-manifold edge and fuses them togather. + * The edge shared by the faces must not be connected to any other edges which have + * Both faces in its radial cycle + * + * Examples: + * + * A B + * ---------- ---------- + * | | | | + * | f1 | | f1 | + * v1========v2 = Ok! v1==V2==v3 == Wrong! + * | f2 | | f2 | + * | | | | + * ---------- ---------- + * + * In the example A, faces f1 and f2 are joined by a single edge, and the euler can safely be used. + * In example B however, f1 and f2 are joined by multiple edges and will produce an error. The caller + * in this case should call bmesh_JEKV on the extra edges before attempting to fuse f1 and f2. + * + * Also note that the order of arguments decides whether or not certain per-face attributes are present + * in the resultant face. For instance vertex winding, material index, smooth flags, ect are inherited + * from f1, not f2. + * + * Returns - + * A BMFace pointer +*/ +BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e) +{ + BMLoop *curloop, *f1loop=NULL, *f2loop=NULL; + int loopok = 0, newlen = 0,i, f1len=0, f2len=0, radlen=0, edok, shared; + BMIter iter; + + /*can't join a face to itself*/ + if(f1 == f2) return NULL; + /*verify that e is in both f1 and f2*/ + f1len = f1->len; + f2len = f2->len; + BM_ITER(curloop, &iter, bm, BM_LOOPS_OF_FACE, f1) { + if(curloop->e == e){ + f1loop = curloop; + break; + } + } + BM_ITER(curloop, &iter, bm, BM_LOOPS_OF_FACE, f2) { + if(curloop->e == e){ + f2loop = curloop; + break; + } + } + if (!(f1loop && f2loop)) return NULL; + + /*validate that edge is 2-manifold edge*/ + radlen = bmesh_radial_length(f1loop); + if(radlen != 2) return NULL; + + /*validate direction of f2's loop cycle is compatible.*/ + if(f1loop->v == f2loop->v) return NULL; + + /* + validate that for each face, each vertex has another edge in its disk cycle that is + not e, and not shared. + */ + if(bmesh_radial_find_face(f1loop->next->e,f2)) return NULL; + if(bmesh_radial_find_face(f1loop->prev->e,f2)) return NULL; + if(bmesh_radial_find_face(f2loop->next->e,f1)) return NULL; + if(bmesh_radial_find_face(f2loop->prev->e,f1)) return NULL; + + /*validate only one shared edge*/ + shared = BM_Face_Sharededges(f1,f2); + if(shared > 1) return NULL; + + /*validate no internal joins*/ + for(i=0, curloop = bm_firstfaceloop(f1); i < f1len; i++, curloop = curloop->next) + bmesh_api_setindex(curloop->v, 0); + for(i=0, curloop = bm_firstfaceloop(f2); i < f2len; i++, curloop = curloop->next) + bmesh_api_setindex(curloop->v, 0); + + for(i=0, curloop = bm_firstfaceloop(f1); i < f1len; i++, curloop = curloop->next) { + if (curloop != f1loop) + bmesh_api_setindex(curloop->v, bmesh_api_getindex(curloop->v) + 1); + } + for(i=0, curloop = bm_firstfaceloop(f2); i < f2len; i++, curloop = curloop->next) { + if (curloop != f2loop) + bmesh_api_setindex(curloop->v, bmesh_api_getindex(curloop->v) + 1); + } + + for(i=0, curloop = bm_firstfaceloop(f1); i < f1len; i++, curloop = curloop->next) { + if (bmesh_api_getindex(curloop->v) > 1) + return NULL; + } + + for(i=0, curloop = bm_firstfaceloop(f2); i < f2len; i++, curloop = curloop->next) { + if (bmesh_api_getindex(curloop->v) > 1) + return NULL; + } + + /*join the two loops*/ + f1loop->prev->next = f2loop->next; + f2loop->next->prev = f1loop->prev; + + f1loop->next->prev = f2loop->prev; + f2loop->prev->next = f1loop->next; + + /*if f1loop was baseloop, make f1loop->next the base.*/ + if(bm_firstfaceloop(f1) == f1loop) + bm_firstfaceloop(f1) = f1loop->next; + + /*increase length of f1*/ + f1->len += (f2->len - 2); + + /*make sure each loop points to the proper face*/ + newlen = f1->len; + for(i = 0, curloop = bm_firstfaceloop(f1); i < newlen; i++, curloop = curloop->next) + curloop->f = f1; + + /*remove edge from the disk cycle of its two vertices.*/ + bmesh_disk_remove_edge(f1loop->e, f1loop->e->v1); + bmesh_disk_remove_edge(f1loop->e, f1loop->e->v2); + + /*deallocate edge and its two loops as well as f2*/ + BLI_mempool_free(bm->toolflagpool, f1loop->e->head.flags); + BLI_mempool_free(bm->epool, f1loop->e); + bm->totedge--; + BLI_mempool_free(bm->lpool, f1loop); + bm->totloop--; + BLI_mempool_free(bm->lpool, f2loop); + bm->totloop--; + BLI_mempool_free(bm->toolflagpool, f2->head.flags); + BLI_mempool_free(bm->fpool, f2); + bm->totface--; + + CHECK_ELEMENT(bm, f1); + + /*validate the new loop cycle*/ + edok = bmesh_loop_validate(f1); + if(!edok) bmesh_error(); + + return f1; +} diff --git a/source/blender/bmesh/intern/bmesh_private.h b/source/blender/bmesh/intern/bmesh_private.h index 5627a7bfefb..0986c491817 100644 --- a/source/blender/bmesh/intern/bmesh_private.h +++ b/source/blender/bmesh/intern/bmesh_private.h @@ -72,6 +72,8 @@ int bmesh_get_filter_argtype(int type); #define bmesh_api_setflag(element, f) (((BMHeader*)(element))->flags[0].pflag |= (f)) #define bmesh_api_getflag(element, f) (((BMHeader*)(element))->flags[0].pflag & (f)) #define bmesh_api_clearflag(element, f) (((BMHeader*)(element))->flags[0].pflag &= ~(f)) +#define bmesh_api_setindex(element, i) (((BMHeader*)(element))->flags[0].index = (i)) +#define bmesh_api_getindex(element) (((BMHeader*)(element))->flags[0].index + 0) /*Polygon Utilities ? FIXME... where do these each go?*/ /*newedgeflag sets a flag layer flag, obviously not the header flag.*/ diff --git a/source/blender/bmesh/intern/bmesh_structure.c b/source/blender/bmesh/intern/bmesh_structure.c index f5005355e7f..6fdf87039ef 100644 --- a/source/blender/bmesh/intern/bmesh_structure.c +++ b/source/blender/bmesh/intern/bmesh_structure.c @@ -217,6 +217,22 @@ static BMEdge *bmesh_disk_prevedge(BMEdge *e, BMVert *v) return NULL; } +BMEdge *bmesh_disk_existedge(BMVert *v1, BMVert *v2) +{ + BMEdge *curedge, *startedge; + + if(v1->e) { + startedge = v1->e; + curedge = startedge; + do { + if (bmesh_verts_in_edge(v1,v2,curedge)) return curedge; + curedge = bmesh_disk_nextedge(curedge, v1); + } while (curedge != startedge); + } + + return NULL; +} + int bmesh_disk_count(struct BMVert *v) { BMEdge *e = v->e; @@ -468,8 +484,36 @@ int bmesh_radial_count_facevert(BMLoop *l, BMVert *v) return count; } +/*****loop cycle functions, e.g. loops surrounding a face******/ +int bmesh_loop_validate(BMFace *f) +{ + int i; + int len = f->len; + BMLoop *curloop, *head; + head = bm_firstfaceloop(f); + + if (head == NULL) + return 0; + + /* Validate that the face loop cycle is the length specified by f->len */ + for(i = 1, curloop = head->next; i < len; i++, curloop = curloop->next) { + if (curloop->f != f) return 0; + if (curloop == head) return 0; + } + if(curloop != head) return 0; + + /* Validate the loop->prev links also form a cycle of length f->len */ + for(i = 1, curloop = head->prev; i < len; i++, curloop = curloop->prev) { + if (curloop == head) return 0; + } + if(curloop != head) return 0; + + return 1; +} + + #if 0 - void bmesh_cycle_append(void *h, void *nt) +void bmesh_cycle_append(void *h, void *nt) { BMNode *oldtail, *head, *newtail; @@ -784,7 +828,6 @@ BMEdge *bmesh_disk_existedge(BMVert *v1, BMVert *v2){ } /*end disk cycle routines*/ - BMLoop *bmesh_radial_nextloop(BMLoop *l){ return l->radial_next; } diff --git a/source/blender/bmesh/intern/bmesh_structure.h b/source/blender/bmesh/intern/bmesh_structure.h index 58f7cbc16f2..b9cbeeeb966 100644 --- a/source/blender/bmesh/intern/bmesh_structure.h +++ b/source/blender/bmesh/intern/bmesh_structure.h @@ -50,6 +50,9 @@ int bmesh_cycle_remove(void *h, void *remn); int bmesh_cycle_validate(int len, void *h); int bmesh_cycle_length(void *h); +/* LOOP CYCLE MANAGEMENT */ +int bmesh_loop_validate(BMFace *f); + /*DISK CYCLE MANAGMENT*/ int bmesh_disk_append_edge(struct BMEdge *e, struct BMVert *v); void bmesh_disk_remove_edge(struct BMEdge *e, struct BMVert *v); @@ -94,7 +97,7 @@ int bmesh_jekv(struct BMesh *bm, struct BMEdge *ke, struct BMVert *kv); int bmesh_loop_reverse(struct BMesh *bm, struct BMFace *f); struct BMFace *bmesh_jfke(struct BMesh *bm, struct BMFace *f1, struct BMFace *f2, struct BMEdge *e); -struct BMVert *bmesh_urmv(struct BMesh *bm, struct BMFace *sf, struct BMVert *sv); +//struct BMVert *bmesh_urmv(struct BMesh *bm, struct BMFace *sf, struct BMVert *sv); //int *bmesh_grkv(struct BMesh *bm, struct BMFace *sf, struct BMVert *kv); #endif |