- joeedh -
design notes:
- * walkers should use tool flags, not header flags
- * walkers now use ghash rather then stealing flags.
- ghash can be rewritten to be faster if necassary.
- * walkers should always raise BMERR_WALKER_FAILED,
- with a custom error message. This message will
- probably be replaced by operator-specific messages
- in most cases.
+ original desing: walkers directly emulation recursive functions.
+ functions save their state onto a stack, and also push new states
+ to implement recursive or looping behaviour. generally only one
+ state push per call with a specific state is desired.
+
+ basic design pattern: the walker step function goes through it's
+ list of possible choices for recursion, and recurses (by pushing a new state)
+ using the first non-visited one. this choise is the flagged as visited using
+ the ghash. each time this happens, only one state is pushed.
+
+ * walkers use tool flags, not header flags
+ * walkers now use ghash for storing visited elements,
+ rather then stealing flags. ghash can be rewritten
+ to be faster if necassary, in the far future :) .
* tools should ALWAYS have necassary error handling
for if walkers fail.
*/
typedef struct islandboundWalker {
struct islandboundWalker *prev;
- BMEdge *base;
+ BMLoop *base;
BMVert *lastv;
- BMEdge *curedge;
+ BMLoop *curloop;
} islandboundWalker;
+typedef struct islandWalker {
+ struct islandWalker * prev;
+ BMFace *cur;
+} islandWalker;
+
/* NOTE: this comment is out of date, update it - joeedh
* BMWalker - change this to use the filters functions.
*
* the surface of a mesh. An example of usage:
*
* BMEdge *edge;
- * BMWalker *walker = BMWalker_create(BM_SHELLWALKER, BM_SELECT);
+ * BMWalker *walker = BMW_create(BM_SHELLWALKER, BM_SELECT);
* walker->begin(walker, vert);
- * for(edge = BMWalker_walk(walker); edge; edge = bmeshWwalker_walk(walker)){
+ * for(edge = BMW_walk(walker); edge; edge = bmeshWwalker_walk(walker)){
* bmesh_select_edge(edge);
* }
- * BMWalker_free(walker);
+ * BMW_free(walker);
*
* The above example creates a walker that walks over the surface a mesh by starting at
* a vertex and traveling across its edges to other vertices, and repeating the process
* over and over again until it has visited each vertex in the shell. An additional restriction
- * is passed into the BMWalker_create function stating that we are only interested
+ * is passed into the BMW_create function stating that we are only interested
* in walking over edges that have been flagged with the bitmask 'BM_SELECT'.
*
*
*/
/*Forward declerations*/
-static void *BMWalker_walk(struct BMWalker *walker);
-static void BMWalker_popstate(struct BMWalker *walker);
-static void BMWalker_pushstate(struct BMWalker *walker);
+static void *BMW_walk(struct BMWalker *walker);
+static void BMW_popstate(struct BMWalker *walker);
+static void BMW_pushstate(struct BMWalker *walker);
+
+static void shellWalker_begin(struct BMWalker *walker, void *data);
+static void *shellWalker_yield(struct BMWalker *walker);
+static void *shellWalker_step(struct BMWalker *walker);
-static void *shellWalker_Begin(struct BMWalker *walker, void *data);
-static void *shellWalker_Yield(struct BMWalker *walker);
-static void *shellWalker_Step(struct BMWalker *walker);
+static void islandboundWalker_begin(BMWalker *walker, void *data);
+static void *islandboundWalker_yield(BMWalker *walker);
+static void *islandboundWalker_step(BMWalker *walker);
-static void *islandboundWalker_Begin(BMWalker *walker, void *data);
-static void *islandboundWalker_Yield(BMWalker *walker);
-static void *islandboundWalker_Step(BMWalker *walker);
+
+static void islandWalker_begin(BMWalker *walker, void *data);
+static void *islandWalker_yield(BMWalker *walker);
+static void *islandWalker_step(BMWalker *walker);
struct shellWalker;
} bmesh_walkerGeneric;
+void *BMW_Begin(BMWalker *walker, void *start) {
+ walker->begin(walker, start);
+
+ return walker->step(walker);
+}
+
/*
- * BMWalker_CREATE
+ * BMW_CREATE
*
* Allocates and returns a new mesh walker of
* a given type. The elements visited are filtered
*
*/
-void BMWalker_Init(BMWalker *walker, BMesh *bm, int type, int searchmask)
+void BMW_Init(BMWalker *walker, BMesh *bm, int type, int searchmask)
{
int size = 0;
switch(type){
case BMW_SHELL:
- walker->begin = shellWalker_Begin;
- walker->step = shellWalker_Step;
- walker->yield = shellWalker_Yield;
+ walker->begin = shellWalker_begin;
+ walker->step = shellWalker_step;
+ walker->yield = shellWalker_yield;
size = sizeof(shellWalker);
break;
case BMW_ISLANDBOUND:
- walker->begin = islandboundWalker_Begin;
- walker->step = islandboundWalker_Step;
- walker->yield = islandboundWalker_Yield;
+ walker->begin = islandboundWalker_begin;
+ walker->step = islandboundWalker_step;
+ walker->yield = islandboundWalker_yield;
size = sizeof(islandboundWalker);
break;
+ case BMW_ISLAND:
+ walker->begin = islandWalker_begin;
+ walker->step = islandWalker_step;
+ walker->yield = islandWalker_yield;
+ size = sizeof(islandWalker);
+ break;
+
//case BMW_LOOP:
// walker->begin = loopwalker_Begin;
// walker->step = loopwalker_Step;
}
/*
- * BMWalker_End
+ * BMW_End
*
* Frees a walker's stack.
*
*/
-void BMWalker_End(BMWalker *walker)
+void BMW_End(BMWalker *walker)
{
BLI_mempool_destroy(walker->stack);
+ BLI_ghash_free(walker->visithash, NULL, NULL);
}
/*
- * BMWalker_Step
+ * BMW_Step
*
*/
-void *BMWalker_Step(BMWalker *walker)
+void *BMW_Step(BMWalker *walker)
{
BMHeader *head;
- head = BMWalker_walk(walker);
+ head = BMW_walk(walker);
return head;
}
/*
- * BMWalker_WALK
+ * BMW_WALK
*
* Steps a mesh walker forward by one element
*
*
*/
-static void *BMWalker_walk(BMWalker *walker)
+static void *BMW_walk(BMWalker *walker)
{
void *current = NULL;
while(walker->currentstate){
- walker->step(walker);
- current = walker->yield(walker);
+ current = walker->step(walker);
if(current) return current;
- else BMWalker_popstate(walker);
-
+ else BMW_popstate(walker);
}
return NULL;
}
/*
- * BMWalker_popstate
+ * BMW_popstate
*
* Pops the current walker state off the stack
* and makes the previous state current
*
*/
-static void BMWalker_popstate(BMWalker *walker)
+static void BMW_popstate(BMWalker *walker)
{
void *oldstate;
oldstate = walker->currentstate;
}
/*
- * BMWalker_pushstate
+ * BMW_pushstate
*
* Pushes the current state down the stack and allocates
* a new one.
*
*/
-static void BMWalker_pushstate(BMWalker *walker)
+static void BMW_pushstate(BMWalker *walker)
{
bmesh_walkerGeneric *newstate;
newstate = BLI_mempool_alloc(walker->stack);
walker->currentstate = newstate;
}
-void BMWalker_reset(BMWalker *walker) {
+void BMW_reset(BMWalker *walker) {
while (walker->currentstate) {
- BMWalker_popstate(walker);
+ BMW_popstate(walker);
}
}
*
*/
-static void *shellWalker_Begin(BMWalker *walker, void *data){
+static void shellWalker_begin(BMWalker *walker, void *data){
BMVert *v = data;
shellWalker *shellWalk = NULL;
- BMWalker_pushstate(walker);
+
+ BMW_pushstate(walker);
+
shellWalk = walker->currentstate;
shellWalk->base = NULL;
shellWalk->curedge = NULL;
+
if(v->edge){
shellWalk->base = v;
shellWalk->curedge = v->edge;
}
-
- return v->edge;
}
-static void *shellWalker_Yield(BMWalker *walker)
+static void *shellWalker_yield(BMWalker *walker)
{
shellWalker *shellWalk = walker->currentstate;
return shellWalk->curedge;
}
-static void *shellWalker_Step(BMWalker *walker)
+static void *shellWalker_step(BMWalker *walker)
{
BMEdge *curedge, *next = NULL;
BMVert *ov = NULL;
do{
if (!BLI_ghash_lookup(walker->visithash, curedge)) {
BLI_ghash_insert(walker->visithash, curedge, NULL);
- if(walker->restrictflag && (!BMO_TestFlag(walker->bm, curedge, walker->restrictflag))) restrictpass = 0;
+ if(walker->restrictflag &&
+ (!BMO_TestFlag(walker->bm, curedge, walker->restrictflag)))
+ {
+ restrictpass = 0;
+ }
if(restrictpass) {
ov = BM_OtherEdgeVert(curedge, shellWalk->base);
/*save current state*/
shellWalk->curedge = curedge;
+
/*push a new state onto the stack*/
- BMWalker_pushstate(walker);
+ BMW_pushstate(walker);
/*populate the new state*/
((shellWalker*)walker->currentstate)->base = ov;
next = curedge;
break;
}
- curedge = bmesh_disk_nextedge(curedge, shellWalk->base);
}
+ curedge = bmesh_disk_nextedge(curedge, shellWalk->base);
}while(curedge != shellWalk->curedge);
shellWalk->current = next;
- return shellWalk->current;
+ return next;
}
/* Island Boundary Walker:
*
*/
-static void *islandboundWalker_Begin(BMWalker *walker, void *data){
- BMEdge *e = data;
+static void islandboundWalker_begin(BMWalker *walker, void *data){
+ BMLoop *l = data;
islandboundWalker *iwalk = NULL;
- BMWalker_pushstate(walker);
+ BMW_pushstate(walker);
iwalk = walker->currentstate;
- iwalk->base = iwalk->curedge = e;
- return e;
+ iwalk->base = iwalk->curloop = l;
+ iwalk->lastv = l->v;
+
+ BLI_ghash_insert(walker->visithash, data, NULL);
+
}
-static void *islandboundWalker_Yield(BMWalker *walker)
+static void *islandboundWalker_yield(BMWalker *walker)
{
islandboundWalker *iwalk = walker->currentstate;
- return iwalk->curedge;
+ return iwalk->curloop;
}
-static void *islandboundWalker_Step(BMWalker *walker)
+static void *islandboundWalker_step(BMWalker *walker)
{
- islandboundWalker *iwalk = walker->currentstate, *owalk;
- BMIter iter, liter;
+ islandboundWalker *iwalk = walker->currentstate, owalk;
BMVert *v;
- BMEdge *e = iwalk->curedge;
+ BMEdge *e = iwalk->curloop->e;
BMFace *f;
- BMLoop *l;
- int found=0, radlen, sellen;;
+ BMLoop *l = iwalk->curloop;
+ int found=0;
- owalk = iwalk;
+ owalk = *iwalk;
if (iwalk->lastv == e->v1) v = e->v2;
else v = e->v1;
- if (BM_Nonmanifold_Vert(v)) {
- BMWalker_reset(walker);
+ if (BM_Nonmanifold_Vert(walker->bm, v)) {
+ BMW_reset(walker);
BMO_RaiseError(walker->bm, NULL,BMERR_WALKER_FAILED,
"Non-manifold vert"
"while searching region boundary");
return NULL;
}
-
- BMWalker_popstate(walker);
- /*find start face*/
- l = BMIter_New(&liter, walker->bm, BM_LOOPS_OF_EDGE; e);
- for (; l; l=BMIter_Step(&liter)) {
- if (BMO_TestFlag(walker->bm, l->f, walker->restrictflag)) {
- f = l->f;
- break;
- }
- }
+ /*pop off current state*/
+ BMW_popstate(walker);
+
+ f = l->f;
while (1) {
- l = BM_OtherFaceLoop(e, v, f);
- if (l) {
- l = l->radial.next->data;
+ l = BM_OtherFaceLoop(e, f, v);
+ if (bmesh_radial_nextloop(l) != l) {
+ l = bmesh_radial_nextloop(l);
f = l->f;
e = l->e;
- if(!BMO_TestFlag(walker->bm,l->f,walker->restrictflag))
+ if(!BMO_TestFlag(walker->bm, f, walker->restrictflag)){
+ l = l->radial.next->data;
break;
+ }
} else {
+ f = l->f;
+ e = l->e;
break;
}
}
- if (e == iwalk->curedge) return NULL;
- if (BLI_ghash_haskey(walker->visithash, e)) return NULL;
+ if (l == owalk.curloop) return NULL;
+ if (BLI_ghash_haskey(walker->visithash, l)) return owalk.curloop;
- BLI_ghash_insert(walker->visithash, e, NULL);
- BMWalker_pushstate(walker);
-
+ BLI_ghash_insert(walker->visithash, l, NULL);
+ BMW_pushstate(walker);
iwalk = walker->currentstate;
- iwalk->base = owalk->base;
- iwalk->curedge = e;
+ iwalk->base = owalk.base;
+
+ //if (!BMO_TestFlag(walker->bm, l->f, walker->restrictflag))
+ // iwalk->curloop = l->radial.next->data;
+ iwalk->curloop = l; //else iwalk->curloop = l;
iwalk->lastv = v;
- return iwalk->curedge;
+ return owalk.curloop;
+}
+
+
+/* Island Walker:
+ *
+ * Starts at a tool flagged-face and walks over the face region
+ *
+ * TODO:
+ *
+ * Add restriction flag/callback for wire edges.
+ *
+*/
+
+static void islandWalker_begin(BMWalker *walker, void *data){
+ islandWalker *iwalk = NULL;
+
+ BMW_pushstate(walker);
+
+ iwalk = walker->currentstate;
+ BLI_ghash_insert(walker->visithash, data, NULL);
+
+ iwalk->cur = data;
+}
+
+static void *islandWalker_yield(BMWalker *walker)
+{
+ islandWalker *iwalk = walker->currentstate;
+
+ return iwalk->cur;
+}
+
+static void *islandWalker_step(BMWalker *walker)
+{
+ islandWalker *iwalk = walker->currentstate, *owalk;
+ BMIter iter, liter;
+ BMFace *f, *curf = iwalk->cur;
+ BMLoop *l;
+ owalk = iwalk;
+
+ BMW_popstate(walker);
+
+ l = BMIter_New(&liter, walker->bm, BM_LOOPS_OF_FACE, iwalk->cur);
+ for (; l; l=BMIter_Step(&liter)) {
+ f = BMIter_New(&iter, walker->bm, BM_FACES_OF_EDGE, l->e);
+ for (; f; f=BMIter_Step(&iter)) {
+ if (!BMO_TestFlag(walker->bm, f, walker->restrictflag))
+ continue;
+ if (BLI_ghash_haskey(walker->visithash, f)) continue;
+
+ BMW_pushstate(walker);
+ iwalk = walker->currentstate;
+ iwalk->cur = f;
+ BLI_ghash_insert(walker->visithash, f, NULL);
+ break;
+
+ }
+ }
+
+ return curf;
}
#include "BLI_arithb.h"
#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
#define FACE_MARK 1
+#define FACE_ORIG 2
#define VERT_MARK 1
+#define FACE_NEW 4
void dissolvefaces_exec(BMesh *bm, BMOperator *op)
{
- BMOIter iter;
- BMIter liter;
- BMLoop *l;
+ BMOIter oiter;
+ BMIter liter, liter2;
+ BMLoop *l, *l2;
BMFace *f, *f2, *nf = NULL;
+ V_DECLARE(region);
+ V_DECLARE(regions);
+ BMLoop ***regions = NULL;
+ BMLoop **region = NULL;
+ BMWalker walker, regwalker;
+ int i, j, fcopied;
- //BMO_Flag_Buffer(bm, op, BMOP_DISFACES_FACEIN, FACE_MARK);
+ BMO_Flag_Buffer(bm, op, BMOP_DISFACES_FACEIN, FACE_MARK);
+
+ /*collect regions*/
+ f = BMO_IterNew(&oiter, bm, op, BMOP_DISFACES_FACEIN);
+ for (; f; f=BMO_IterStep(&oiter)) {
+ if (!BMO_TestFlag(bm, f, FACE_MARK)) continue;
+
+ l = BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f);
+ for (; l; l=BMIter_Step(&liter)) {
+ l2 = bmesh_radial_nextloop(l);
+ if (l2!=l && BMO_TestFlag(bm, l2->f, FACE_MARK))
+ continue;
+ if (BM_FacesAroundEdge(l->e) <= 2) {
+ V_RESET(region);
+ region = NULL; /*forces different allocation*/
- /*TODO: need to discuss with Briggs how best to implement this, seems this would be
- a great time to use the walker api, get it up to snuff. perhaps have a walker
- that goes over inner vertices of a contiguously-flagged region? then you
- could just use dissolve disk on them.*/
- if (BMO_GetSlot(op, BMOP_DISFACES_FACEIN)->len != 2) return;
+ /*yay, walk!*/
+ BMW_Init(&walker, bm, BMW_ISLANDBOUND, FACE_MARK);
+ l = BMW_Begin(&walker, l);
+ for (; l; l=BMW_Step(&walker)) {
+ V_GROW(region);
+ region[V_COUNT(region)-1] = l;
+ }
+ BMW_End(&walker);
- /*HACK: for debugging purposes, handle cases of two adjacent faces*/
- f = BMO_IterNew(&iter, bm, op, BMOP_DISFACES_FACEIN);
- f2 = BMO_IterStep(&iter);
+ if (BMO_HasError(bm)) {
+ BMO_ClearStack(bm);
+ BMO_RaiseError(bm, op, BMERR_DISSOLVEFACES_FAILED, NULL);
+ goto cleanup;
+ }
+
+ if (region == NULL) continue;
- for (l=BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f);l;l=BMIter_Step(&liter)) {
- if (!l->radial.next) continue;
- if (((BMLoop*)l->radial.next->data)->f == f2) {
- nf = BM_Join_Faces(bm, f, f2, l->e, 1, 0);
- break;
+ BMW_Init(®walker, bm, BMW_ISLAND, FACE_MARK);
+ f2 = BMW_Begin(®walker, region[0]->f);
+ for (; f2; f2=BMW_Step(®walker)) {
+ BMO_ClearFlag(bm, f2, FACE_MARK);
+ BMO_SetFlag(bm, f2, FACE_ORIG);
+ }
+ BMW_End(®walker);
+
+ if (BMO_HasError(bm)) {
+ BMO_ClearStack(bm);
+ BMO_RaiseError(bm, op, BMERR_DISSOLVEFACES_FAILED, NULL);
+ goto cleanup;
+ }
+
+ V_GROW(region);
+ V_GROW(regions);
+ regions[V_COUNT(regions)-1] = region;
+ region[V_COUNT(region)-1] = NULL;
+ break;
+ }
}
}
+
+ for (i=0; i<V_COUNT(regions); i++) {
+ BMEdge **edges = NULL;
+ V_DECLARE(edges);
- if (nf) {
- BMO_SetFlag(bm, nf, 1);
- BMO_Flag_To_Slot(bm, op, BMOP_DISFACES_REGIONOUT, 1, BM_FACE);
+ region = regions[i];
+ for (j=0; region[j]; j++) {
+ V_GROW(edges);
+ edges[V_COUNT(edges)-1] = region[j]->e;
+ }
+
+ f= BM_Make_Ngon(bm, edges[0]->v1, edges[0]->v2, edges, j, 0);
+
+ if (!f) {
+ /*raise error*/
+ BMO_RaiseError(bm, op, BMERR_DISSOLVEFACES_FAILED, NULL);
+ goto cleanup;
+ }
+
+ BMO_SetFlag(bm, f, FACE_NEW);
+
+ fcopied = 0;
+ l=BMIter_New(&liter, bm, BM_LOOPS_OF_FACE, f);
+ for (; l; l=BMIter_Step(&liter)) {
+ /*ensure winding is identical*/
+ l2 = BMIter_New(&liter2, bm, BM_LOOPS_OF_LOOP, l);
+ for (; l2; l2=BMIter_Step(&liter2)) {
+ if (BMO_TestFlag(bm, l2->f, FACE_ORIG)) {
+ if (l2->v != l->v)
+ bmesh_loop_reverse(bm, l2->f);
+ break;
+ }
+ }
+
+ /*copy over attributes*/
+ l2 = BMIter_New(&liter2, bm, BM_LOOPS_OF_LOOP, l);
+ for (; l2; l2=BMIter_Step(&liter2)) {
+ if (BMO_TestFlag(bm, l2->f, FACE_ORIG)) {
+ if (!fcopied) {
+ BM_Copy_Attributes(bm, bm, l2->f, f);
+ fcopied = 1;
+ }
+ BM_Copy_Attributes(bm, bm, l2, l);
+ break;
+ }
+ }
+ }
}
+ BMO_CallOpf(bm, "del geom=%ff context=%d", FACE_ORIG, DEL_FACES);
+ if (BMO_HasError(bm)) return;
+
+ BMO_Flag_To_Slot(bm, op, BMOP_DISFACES_REGIONOUT, FACE_NEW, BM_FACE);
+
+cleanup:
+ /*free/cleanup*/
+ for (i=0; i<V_COUNT(regions); i++) {
+ if (regions[i]) V_FREE(regions[i]);
+ }
+
+ V_FREE(regions);
}
/*returns 1 if any faces were dissolved*/
void dissolveverts_exec(BMesh *bm, BMOperator *op)
{
BMOpSlot *vinput;
- BMIter iter, liter, fiter;
+ BMIter iter, fiter;
BMVert *v;
- BMFace *f, *f2;
- BMEdge *fe;
- BMLoop *l;
- int found, found2, found3, len, oldlen=0;
+ BMFace *f;
vinput = BMO_GetSlot(op, BMOP_DISVERTS_VERTIN);
BMO_Flag_Buffer(bm, op, BMOP_DISVERTS_VERTIN, VERT_MARK);
- found = 1;
- while (found) {
- found = 0;
- len = 0;
- for (v=BMIter_New(&iter, bm, BM_VERTS, NULL); v; v=BMIter_Step(&iter)) {
- if (BMO_TestFlag(bm, v, VERT_MARK)) {
- if (!BM_Dissolve_Vert(bm, v)) {
- BMO_RaiseError(bm, op,
- BMERR_DISSOLVEDISK_FAILED, NULL);
- return;
- }
- found = 1;
- len++;
+ for (v=BMIter_New(&iter, bm, BM_VERTS, NULL); v; v=BMIter_Step(&iter)) {
+ if (BMO_TestFlag(bm, v, VERT_MARK)) {
+ f=BMIter_New(&fiter, bm, BM_FACES_OF_VERT, v);
+ for (; f; f=BMIter_Step(&fiter)) {
+ BMO_SetFlag(bm, f, FACE_MARK);
}
}
+ }
+ BMO_CallOpf(bm, "dissolvefaces faces=%ff", FACE_MARK);
+ if (BMO_HasError(bm)) {
+ BMO_ClearStack(bm);
+ BMO_RaiseError(bm, op, BMERR_DISSOLVEVERTS_FAILED, NULL);
+ }
+}
+/*this code is for cleaning up two-edged faces, it shall become
+ it's own function one day.*/
+#if 0
/*clean up two-edged faces*/
/*basic idea is to keep joining 2-edged faces until their
gone. this however relies on joining two 2-edged faces
}
if (oldlen == len) break;
oldlen = len;
- }
-}
\ No newline at end of file
+#endif
projects / blender.git / commitdiff