[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [40545] branches/bmesh/blender/source/ blender: Bread-first bmesh walkers:
Andrew Wiggin
ender79bl at gmail.com
Mon Sep 26 05:38:31 CEST 2011
Revision: 40545
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=40545
Author: ender79
Date: 2011-09-26 03:38:30 +0000 (Mon, 26 Sep 2011)
Log Message:
-----------
Bread-first bmesh walkers:
- walkers can be run in breadth-first order or depth-first order (previously there was only depth-first)
- walkers keep track of current depth (with this + breadth-first, select nth implementation is now trivial)
- new connected vertex walker (similar to shell walker, but returns vertices instead of edges)
- shell walker can be started from a vertex (in which case the walker starts by queueing all the edges incident on the vertex) or from an edge (walker starts by queueing the single edge)
- bug fix for walker reset (was emptying states, but not clearing the visithash)
- bug fix for select nth (indexing for deselection was walking through *all* connected elmeents, to match trunk it should only walk through *selected* connected elements)
Modified Paths:
--------------
branches/bmesh/blender/source/blender/bmesh/bmesh_walkers.h
branches/bmesh/blender/source/blender/bmesh/intern/bmesh_walkers.c
branches/bmesh/blender/source/blender/bmesh/intern/bmesh_walkers_impl.c
branches/bmesh/blender/source/blender/bmesh/intern/bmesh_walkers_private.h
branches/bmesh/blender/source/blender/editors/mesh/bmesh_select.c
Modified: branches/bmesh/blender/source/blender/bmesh/bmesh_walkers.h
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/bmesh_walkers.h 2011-09-26 03:37:12 UTC (rev 40544)
+++ branches/bmesh/blender/source/blender/bmesh/bmesh_walkers.h 2011-09-26 03:38:30 UTC (rev 40545)
@@ -7,19 +7,26 @@
NOTE: do NOT modify topology while walking a mesh!
*/
+typedef enum {
+ BMW_DEPTH_FIRST,
+ BMW_BREADTH_FIRST,
+} BMWOrder;
+
/*Walkers*/
typedef struct BMWalker {
void (*begin) (struct BMWalker *walker, void *start);
void *(*step) (struct BMWalker *walker);
void *(*yield)(struct BMWalker *walker);
int structsize;
+ BMWOrder order;
int flag;
BMesh *bm;
- BLI_mempool *stack;
- void *currentstate;
+ BLI_mempool *worklist;
+ ListBase states;
int restrictflag;
GHash *visithash;
+ int depth;
} BMWalker;
/*initialize a walker. searchmask restricts some (not all) walkers to
@@ -28,10 +35,12 @@
void *BMW_Begin(BMWalker *walker, void *start);
void *BMW_Step(struct BMWalker *walker);
void BMW_End(struct BMWalker *walker);
+int BMW_CurrentDepth(BMWalker *walker);
/*these are used by custom walkers*/
-void BMW_pushstate(BMWalker *walker);
-void BMW_popstate(BMWalker *walker);
+void *BMW_currentstate(BMWalker *walker);
+void *BMW_addstate(BMWalker *walker);
+void BMW_removestate(BMWalker *walker);
void *BMW_walk(BMWalker *walker);
void BMW_reset(BMWalker *walker);
@@ -75,6 +84,8 @@
BMW_ISLANDBOUND,
/*walk over all faces in an island of tool flagged faces.*/
BMW_ISLAND,
+ /*walk from a vertex to all connected vertices.*/
+ BMW_CONNECTED_VERTEX,
/*do not intitialze function pointers and struct size in BMW_Init*/
BMW_CUSTOM,
BMW_MAXWALKERS
Modified: branches/bmesh/blender/source/blender/bmesh/intern/bmesh_walkers.c
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/intern/bmesh_walkers.c 2011-09-26 03:37:12 UTC (rev 40544)
+++ branches/bmesh/blender/source/blender/bmesh/intern/bmesh_walkers.c 2011-09-26 03:38:30 UTC (rev 40545)
@@ -51,14 +51,14 @@
design notes:
original desing: walkers directly emulation recursive functions.
- functions save their state onto a stack, and also push new states
+ functions save their state onto a worklist, and also add 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 step may push multiple new states onto the stack at once.
+ the ghash. each step may push multiple new states onto the worklist at once.
* walkers use tool flags, not header flags
* walkers now use ghash for storing visited elements,
@@ -68,17 +68,10 @@
for if walkers fail.
*/
-
-/* Pointer hiding*/
-typedef struct bmesh_walkerGeneric{
- struct bmesh_walkerGeneric *prev;
-} bmesh_walkerGeneric;
-
-
void *BMW_Begin(BMWalker *walker, void *start) {
walker->begin(walker, start);
- return walker->currentstate ? walker->step(walker) : NULL;
+ return BMW_currentstate(walker) ? walker->step(walker) : NULL;
}
/*
@@ -109,22 +102,23 @@
walker->yield = bm_walker_types[type]->yield;
walker->step = bm_walker_types[type]->step;
walker->structsize = bm_walker_types[type]->structsize;
+ walker->order = bm_walker_types[type]->order;
}
- walker->stack = BLI_mempool_create(walker->structsize, 100, 100, 1, 0);
- walker->currentstate = NULL;
+ walker->worklist = BLI_mempool_create(walker->structsize, 100, 100, 1, 0);
+ walker->states.first = walker->states.last = NULL;
}
/*
* BMW_End
*
- * Frees a walker's stack.
+ * Frees a walker's worklist.
*
*/
void BMW_End(BMWalker *walker)
{
- BLI_mempool_destroy(walker->stack);
+ BLI_mempool_destroy(walker->worklist);
BLI_ghash_free(walker->visithash, NULL, NULL);
}
@@ -144,6 +138,18 @@
}
/*
+ * BMW_CurrentDepth
+ *
+ * Returns the current depth of the walker.
+ *
+*/
+
+int BMW_CurrentDepth(BMWalker *walker)
+{
+ return walker->depth;
+}
+
+/*
* BMW_WALK
*
* Steps a mesh walker forward by one element
@@ -157,7 +163,7 @@
{
void *current = NULL;
- while(walker->currentstate){
+ while(BMW_currentstate(walker)){
current = walker->step(walker);
if(current) return current;
}
@@ -165,40 +171,93 @@
}
/*
- * BMW_popstate
+ * BMW_currentstate
*
- * Pops the current walker state off the stack
- * and makes the previous state current
+ * Returns the first state from the walker state
+ * worklist. This state is the the next in the
+ * worklist for processing.
*
*/
-void BMW_popstate(BMWalker *walker)
+void* BMW_currentstate(BMWalker *walker)
{
+ bmesh_walkerGeneric *currentstate = walker->states.first;
+ if (currentstate) {
+ /* Automatic update of depth. For most walkers that
+ follow the standard "Step" pattern of:
+ - read current state
+ - remove current state
+ - push new states
+ - return walk result from just-removed current state
+ this simple automatic update should keep track of depth
+ just fine. Walkers that deviate from that pattern may
+ need to manually update the depth if they care about
+ keeping it correct. */
+ walker->depth = currentstate->depth + 1;
+ }
+ return currentstate;
+}
+
+/*
+ * BMW_removestate
+ *
+ * Remove and free an item from the end of the walker state
+ * worklist.
+ *
+*/
+
+void BMW_removestate(BMWalker *walker)
+{
void *oldstate;
- oldstate = walker->currentstate;
- walker->currentstate
- = ((bmesh_walkerGeneric*)walker->currentstate)->prev;
- BLI_mempool_free(walker->stack, oldstate);
+ oldstate = BMW_currentstate(walker);
+ BLI_remlink(&walker->states, oldstate);
+ BLI_mempool_free(walker->worklist, oldstate);
}
/*
- * BMW_pushstate
+ * BMW_newstate
*
- * Pushes the current state down the stack and allocates
- * a new one.
+ * Allocate a new empty state and put it on the worklist.
+ * A pointer to the new state is returned so that the caller
+ * can fill in the state data. The new state will be inserted
+ * at the front for depth-first walks, and at the end for
+ * breadth-first walks.
*
*/
-void BMW_pushstate(BMWalker *walker)
+void* BMW_addstate(BMWalker *walker)
{
bmesh_walkerGeneric *newstate;
- newstate = BLI_mempool_alloc(walker->stack);
- newstate->prev = walker->currentstate;
- walker->currentstate = newstate;
+ newstate = BLI_mempool_alloc(walker->worklist);
+ newstate->depth = walker->depth;
+ switch (walker->order)
+ {
+ case BMW_DEPTH_FIRST:
+ BLI_addhead(&walker->states, newstate);
+ break;
+ case BMW_BREADTH_FIRST:
+ BLI_addtail(&walker->states, newstate);
+ break;
+ default:
+ BLI_assert(0);
+ break;
+ }
+ return newstate;
}
+/*
+ * BMW_reset
+ *
+ * Frees all states from the worklist, resetting the walker
+ * for reuse in a new walk.
+ *
+*/
+
void BMW_reset(BMWalker *walker) {
- while (walker->currentstate) {
- BMW_popstate(walker);
+ while (BMW_currentstate(walker)) {
+ BMW_removestate(walker);
}
+ walker->depth = 0;
+ BLI_ghash_free(walker->visithash, NULL, NULL);
+ walker->visithash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "bmesh walkers 1");
}
Modified: branches/bmesh/blender/source/blender/bmesh/intern/bmesh_walkers_impl.c
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/intern/bmesh_walkers_impl.c 2011-09-26 03:37:12 UTC (rev 40544)
+++ branches/bmesh/blender/source/blender/bmesh/intern/bmesh_walkers_impl.c 2011-09-26 03:38:30 UTC (rev 40545)
@@ -57,68 +57,77 @@
*
*/
-static void shellWalker_begin(BMWalker *walker, void *data){
- BMIter eiter;
- BMEdge *e;
- BMVert *v = data;
+static void shellWalker_visitEdge(BMWalker *walker, BMEdge *e) {
shellWalker *shellWalk = NULL;
- if (!v->e)
+ if (BLI_ghash_haskey(walker->visithash, e)) {
return;
-
- if (walker->restrictflag) {
- BM_ITER(e, &eiter, walker->bm, BM_EDGES_OF_VERT, v) {
- if (BMO_TestFlag(walker->bm, e, walker->restrictflag))
- break;
- }
- } else {
- e = v->e;
}
- if (!e)
+ if (walker->restrictflag && !BMO_TestFlag(walker->bm, e, walker->restrictflag)) {
return;
+ }
- if (BLI_ghash_haskey(walker->visithash, e))
+ shellWalk = BMW_addstate(walker);
+ shellWalk->curedge = e;
+ BLI_ghash_insert(walker->visithash, e, NULL);
+}
+
+static void shellWalker_begin(BMWalker *walker, void *data){
+ BMIter eiter;
+ BMHeader *h = data;
+ BMEdge *e;
+ BMVert *v;
+
+ if (h == NULL)
+ {
return;
+ }
- BMW_pushstate(walker);
+ switch (h->type) {
+ case BM_VERT:
+ {
+ /* starting the walk at a vert, add all the edges
+ to the worklist */
+ v = (BMVert*)h;
+ BM_ITER(e, &eiter, walker->bm, BM_EDGES_OF_VERT, v) {
+ shellWalker_visitEdge(walker, e);
+ }
+ break;
+ }
- shellWalk = walker->currentstate;
- shellWalk->base = v;
- shellWalk->curedge = e;
- BLI_ghash_insert(walker->visithash, e, NULL);
+ case BM_EDGE:
+ {
+ /* starting the walk at an edge, add the single edge
+ to the worklist */
+ e = (BMEdge*)h;
+ shellWalker_visitEdge(walker, e);
+ break;
+ }
+ }
}
static void *shellWalker_yield(BMWalker *walker)
{
- shellWalker *shellWalk = walker->currentstate;
+ shellWalker *shellWalk = BMW_currentstate(walker);
return shellWalk->curedge;
}
static void *shellWalker_step(BMWalker *walker)
{
- shellWalker *swalk = walker->currentstate;
+ shellWalker *swalk = BMW_currentstate(walker);
BMEdge *e, *e2;
BMVert *v;
BMIter iter;
int i;
- BMW_popstate(walker);
+ e = swalk->curedge;
+ BMW_removestate(walker);
- e = swalk->curedge;
for (i=0; i<2; i++) {
v = i ? e->v2 : e->v1;
BM_ITER(e2, &iter, walker->bm, BM_EDGES_OF_VERT, v) {
- if (walker->restrictflag && !BMO_TestFlag(walker->bm, e2, walker->restrictflag))
- continue;
- if (BLI_ghash_haskey(walker->visithash, e2))
- continue;
-
- BMW_pushstate(walker);
- BLI_ghash_insert(walker->visithash, e2, NULL);
-
- swalk = walker->currentstate;
- swalk->curedge = e2;
+ shellWalker_visitEdge(walker, e2);
}
}
@@ -131,12 +140,12 @@
BMEdge *curedge, *next = NULL;
BMVert *ov = NULL;
int restrictpass = 1;
- shellWalker shellWalk = *((shellWalker*)walker->currentstate);
+ shellWalker shellWalk = *((shellWalker*)BMW_currentstate(walker));
if (!BLI_ghash_haskey(walker->visithash, shellWalk.base))
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list