Got the walker API to work, for safely recursing the mesh.
authorJoseph Eagar <joeedh@gmail.com>
Sun, 8 Mar 2009 15:02:49 +0000 (15:02 +0000)
committerJoseph Eagar <joeedh@gmail.com>
Sun, 8 Mar 2009 15:02:49 +0000 (15:02 +0000)
Used it to implement the dissolve faces operation (previous
incarnation was just a debugging hack).  The code works by
creating one giant new face per region of faces.

The dissolve verts (xkey->collapse, heh need to rename it)
operator now invokes dissolve faces on the faces around verts.
This is less error-prone then a pure topological/euler based
solution.

source/blender/bmesh/bmesh.h
source/blender/bmesh/bmesh_iterators.h
source/blender/bmesh/bmesh_operators.h
source/blender/bmesh/bmesh_queries.h
source/blender/bmesh/bmesh_walkers.h
source/blender/bmesh/intern/bmesh_eulers.c
source/blender/bmesh/intern/bmesh_iterators.c
source/blender/bmesh/intern/bmesh_operators.c
source/blender/bmesh/intern/bmesh_queries.c
source/blender/bmesh/intern/bmesh_walkers.c
source/blender/bmesh/operators/dissolveops.c

index f581e4b1054c27b47749d409cd6519b7bdcf53e3..054e81566657ac5af637992c06b78cc677d966a7 100644 (file)
@@ -1,7 +1,7 @@
 /**
  *  bmesh.h    jan 2007
  *
- *     BM API.
+ *     BMesh API.
  *
  * $Id: BKE_bmesh.h,v 1.00 2007/01/17 17:42:01 Briggs Exp $
  *
@@ -34,8 +34,8 @@
  * ***** END GPL LICENSE BLOCK *****
  */
 
-#ifndef BM_H
-#define BM_H
+#ifndef BMESH_H
+#define BMESH_H
 
 #include "DNA_listBase.h"
 #include "DNA_customdata_types.h"
@@ -217,4 +217,6 @@ struct EditMesh *bmesh_to_editmesh(BMesh *bm);
 #include "bmesh_marking.h"
 #include "bmesh_operators.h"
 #include "bmesh_queries.h"
-#endif
+#include "bmesh_walkers.h"
+
+#endif /* BMESH_H */
index f2d2f03932f8ad40778cadf2e60f89054946ad0b..acba428c0f9bb16658a216555e4a752cedc25b9c 100644 (file)
@@ -26,6 +26,7 @@
 #define BM_EDGES_OF_FACE                       10
 #define BM_LOOPS_OF_FACE                       11
 #define BM_LOOPS_OF_VERT               12
+#define BM_LOOPS_OF_LOOP               13
 
 /*Iterator Structure*/
 typedef struct BMIter{
index a1f0a82257bba0cbc80a84de28a3c708414a2a1b..37225ab342ed6a78b600ae7bfd2881094d4358f2 100644 (file)
@@ -146,6 +146,7 @@ void BMO_RaiseError(BMesh *bm, BMOperator *owner, int errcode, char *msg);
 /*gets the topmost error from the stack.
   returns error code or 0 if no error.*/
 int BMO_GetError(BMesh *bm, char **msg, BMOperator **op);
+int BMO_HasError(BMesh *bm);
 
 /*same as geterror, only pops the error off the stack as well*/
 int BMO_PopError(BMesh *bm, char **msg, BMOperator **op);
@@ -168,6 +169,8 @@ int BMO_CatchOpError(BMesh *bm, BMOperator *catchop, int errorcode, char **msg);
 #define BMERR_DISSOLVEDISK_FAILED              2
 #define BMERR_CONNECTVERT_FAILED               3
 #define BMERR_WALKER_FAILED                    4
+#define BMERR_DISSOLVEFACES_FAILED             5
+#define BMERR_DISSOLVEVERTS_FAILED             6
 
 static char *bmop_error_messages[] = {
        0,
@@ -175,6 +178,8 @@ static char *bmop_error_messages[] = {
        "Could not dissolve vert",
        "Could not connect verts",
        "Could not traverse mesh",
+       "Could not dissolve faces",
+       "Could not dissolve vertices",
 };
 
 /*------------begin operator defines (see bmesh_opdefines.c too)------------*/
index 3f8a9dcb9d785d473c23c3956320842497a0240a..cc0a7214d605fceaad6e70f2b416df993d709255 100644 (file)
@@ -32,4 +32,5 @@ float BM_Face_Angle(struct BMesh *bm, struct BMEdge *e);
 int BM_Exist_Face_Overlaps(struct BMesh *bm, struct BMVert **varr, int len, struct BMFace **existface);
 int BM_Edge_Share_Faces(struct BMEdge *e1, struct BMEdge *e2);
 int BM_Validate_Face(BMesh *bm, BMFace *face, FILE *err);
+int BM_FacesAroundEdge(BMEdge *e);
 #endif
index 22e92e9b6596d8fd9e9ea7896775799e402bb00c..b53de31bab34a026382bfcb9dde3ffc703deab0d 100644 (file)
@@ -8,26 +8,28 @@
 */
 
 /*Walkers*/
-typedef struct BMWalker{
+typedef struct BMWalker {
        BLI_mempool *stack;
        BMesh *bm;
        void *currentstate;
-       void *(*begin) (struct BMWalker *walker, void *start);
+       void (*begin) (struct BMWalker *walker, void *start);
        void *(*yield)(struct BMWalker *walker);
        void *(*step) (struct BMWalker *walker);
        int restrictflag;
        GHash *visithash;
-}BMWalker;
+} BMWalker;
 
-void BMWalker_Init(struct BMWalker *walker,BMesh *bm,int type, int searchmask);
-void *BMWalker_Step(struct BMWalker *walker);
-void BMWalker_End(struct BMWalker *walker);
+void BMW_Init(struct BMWalker *walker,BMesh *bm,int type, int searchmask);
+void *BMW_Begin(BMWalker *walker, void *start);
+void *BMW_Step(struct BMWalker *walker);
+void BMW_End(struct BMWalker *walker);
 
 #define BMW_SHELL      0
 /*#define BMW_LOOP     1
 #define BMW_RING       2
 #define BMW_UVISLANDS  3*/
 #define BMW_ISLANDBOUND        1
-#define BMW_MAXWALKERS 2
+#define BMW_ISLAND     2
+#define BMW_MAXWALKERS 3
 
 #endif
\ No newline at end of file
index 278613f9d72090bb4e5a7f3d2b6646dec204ed31..ccf6336960eabf7dcaf9cc6576619f8e40cc7743 100644 (file)
@@ -317,6 +317,8 @@ BMFace *bmesh_mf(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **elist, int len)
                        if(edok != (l->e->head.eflag2 + 1)) bmesh_error();
                }
        }
+
+       for(i=0;i<len;i++) elist[i]->head.eflag1=elist[i]->head.eflag2 = 0;
        return f;
 }
 
index 11db2ba47fd86dd6a2ab9bf647f1e5f2d141d86d..19b5e88e5bd922288be62a184458057bb65dba65 100644 (file)
@@ -182,6 +182,30 @@ static void *face_of_vert_step(BMIter *iter)
        return NULL;
 }
 
+static void loops_of_loop_begin(BMIter *iter)
+{
+       BMLoop *l;
+
+       l = iter->ldata;
+
+       /*note sure why this sets ldata. . .*/
+       init_iterator(iter);
+
+       iter->firstloop = l;
+       iter->nextloop = bmesh_radial_nextloop(iter->firstloop);
+}
+
+static void *loops_of_loop_step(BMIter *iter)
+{
+       BMLoop *current = iter->nextloop;
+
+       if(iter->nextloop) iter->nextloop = bmesh_radial_nextloop(iter->nextloop);
+
+       if(iter->nextloop == iter->firstloop) iter->nextloop = NULL;
+       if(current) return current;
+       return NULL;
+}
+
 /*
  * FACE OF EDGE CALLBACKS
  *
@@ -384,6 +408,11 @@ void *BMIter_New(BMIter *iter, BMesh *bm, int type, void *data)
                        iter->step = loop_of_vert_step;
                        iter->vdata = data;
                        break;
+               case BM_LOOPS_OF_LOOP:
+                       iter->begin = loops_of_loop_begin;
+                       iter->step = loops_of_loop_step;
+                       iter->ldata = data;
+                       break;
                default:
                        break;
        }
index ef45284a1fff6829e413d718ce0ec0d3585e1d87..714164ea14834e5f8125425760349158900a8cb4 100644 (file)
@@ -809,6 +809,11 @@ void BMO_RaiseError(BMesh *bm, BMOperator *owner, int errcode, char *msg)
        BLI_addhead(&bm->errorstack, err);
 }
 
+int BMO_HasError(BMesh *bm)
+{
+       return bm->errorstack.first != NULL;
+}
+
 /*returns error code or 0 if no error*/
 int BMO_GetError(BMesh *bm, char **msg, BMOperator **op)
 {
index e7dee09107599eb7d3716fef0f37c5a4663e83f7..a77f1112c26fd9dc5d415e9cd98e1adb4aeb37b0 100644 (file)
@@ -62,12 +62,19 @@ BMLoop *BM_OtherFaceLoop(BMEdge *e, BMFace *f, BMVert *v)
        int found = 0;
        
        do {
-               if (l->v == v) break;
+               if (l->e == e) break;
                found = 1;
                l = l->head.next;
        } while (l != f->loopbase);
        
-       return l->head.prev;
+       return l->v == v ? l->head.prev : l->head.next;
+}
+
+int BM_FacesAroundEdge(BMEdge *e)
+{
+       if (!e->loop) return 0;
+
+       return bmesh_cycle_length(&(e->loop->radial));
 }
 
 /*
index 4ac140d14b59ed8340d3f52f061985426bf98e00..b7321bed4bc967710b7c405020cb7f02ea1e928e 100644 (file)
  - 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.
 */
@@ -34,11 +41,16 @@ typedef struct shellWalker{
 
 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.
  *     
@@ -46,34 +58,39 @@ typedef struct islandboundWalker {
  *  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;
 
@@ -83,8 +100,14 @@ typedef struct bmesh_walkerGeneric{
 } 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
@@ -92,7 +115,7 @@ typedef struct bmesh_walkerGeneric{
  *
 */
 
-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;
        
@@ -103,17 +126,24 @@ void BMWalker_Init(BMWalker *walker, BMesh *bm, int type, int searchmask)
 
        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;
@@ -134,34 +164,35 @@ void BMWalker_Init(BMWalker *walker, BMesh *bm, int type, int searchmask)
 }
 
 /*
- * 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
  *
@@ -170,29 +201,27 @@ void *BMWalker_Step(BMWalker *walker)
  *
 */
 
-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;
@@ -202,14 +231,14 @@ static void BMWalker_popstate(BMWalker *walker)
 }
 
 /*
- * 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);
@@ -217,9 +246,9 @@ static void BMWalker_pushstate(BMWalker *walker)
        walker->currentstate = newstate;
 }
 
-void BMWalker_reset(BMWalker *walker) {
+void BMW_reset(BMWalker *walker) {
        while (walker->currentstate) {
-               BMWalker_popstate(walker);
+               BMW_popstate(walker);
        }
 }
 
@@ -234,27 +263,28 @@ void BMWalker_reset(BMWalker *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;
@@ -269,14 +299,19 @@ static void *shellWalker_Step(BMWalker *walker)
        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;
@@ -286,12 +321,12 @@ static void *shellWalker_Step(BMWalker *walker)
                                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:
@@ -305,82 +340,143 @@ static void *shellWalker_Step(BMWalker *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;
 }
index 75833ee67e7125c1a83d4851edaa6878372852f0..e21ac95207d50d998ec7adae475f1c01df170e70 100644 (file)
 #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(&regwalker, bm, BMW_ISLAND, FACE_MARK);
+                               f2 = BMW_Begin(&regwalker, region[0]->f);
+                               for (; f2; f2=BMW_Step(&regwalker)) {
+                                       BMO_ClearFlag(bm, f2, FACE_MARK);
+                                       BMO_SetFlag(bm, f2, FACE_ORIG);
+                               }
+                               BMW_End(&regwalker);
+
+                               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*/
@@ -67,34 +168,33 @@ int BM_DissolveFaces(EditMesh *em, int flag) {
 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
@@ -155,6 +255,5 @@ void dissolveverts_exec(BMesh *bm, BMOperator *op)
                }
                if (oldlen == len) break;
                oldlen = len;
-       }
 
-}
\ No newline at end of file
+#endif