[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [19225] branches/bmesh/blender/source/ blender/bmesh: Got the walker API to work, for safely recursing the mesh.

Joseph Eagar joeedh at gmail.com
Sun Mar 8 16:02:49 CET 2009


Revision: 19225
          http://projects.blender.org/plugins/scmsvn/viewcvs.php?view=rev&root=bf-blender&revision=19225
Author:   joeedh
Date:     2009-03-08 16:02:49 +0100 (Sun, 08 Mar 2009)

Log Message:
-----------
Got the walker API to work, for safely recursing the mesh.
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.

Modified Paths:
--------------
    branches/bmesh/blender/source/blender/bmesh/bmesh.h
    branches/bmesh/blender/source/blender/bmesh/bmesh_iterators.h
    branches/bmesh/blender/source/blender/bmesh/bmesh_operators.h
    branches/bmesh/blender/source/blender/bmesh/bmesh_queries.h
    branches/bmesh/blender/source/blender/bmesh/bmesh_walkers.h
    branches/bmesh/blender/source/blender/bmesh/intern/bmesh_eulers.c
    branches/bmesh/blender/source/blender/bmesh/intern/bmesh_iterators.c
    branches/bmesh/blender/source/blender/bmesh/intern/bmesh_operators.c
    branches/bmesh/blender/source/blender/bmesh/intern/bmesh_queries.c
    branches/bmesh/blender/source/blender/bmesh/intern/bmesh_walkers.c
    branches/bmesh/blender/source/blender/bmesh/operators/dissolveops.c

Modified: branches/bmesh/blender/source/blender/bmesh/bmesh.h
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/bmesh.h	2009-03-08 13:14:12 UTC (rev 19224)
+++ branches/bmesh/blender/source/blender/bmesh/bmesh.h	2009-03-08 15:02:49 UTC (rev 19225)
@@ -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 @@
 #include "bmesh_marking.h"
 #include "bmesh_operators.h"
 #include "bmesh_queries.h"
-#endif
+#include "bmesh_walkers.h"
+
+#endif /* BMESH_H */

Modified: branches/bmesh/blender/source/blender/bmesh/bmesh_iterators.h
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/bmesh_iterators.h	2009-03-08 13:14:12 UTC (rev 19224)
+++ branches/bmesh/blender/source/blender/bmesh/bmesh_iterators.h	2009-03-08 15:02:49 UTC (rev 19225)
@@ -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{

Modified: branches/bmesh/blender/source/blender/bmesh/bmesh_operators.h
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/bmesh_operators.h	2009-03-08 13:14:12 UTC (rev 19224)
+++ branches/bmesh/blender/source/blender/bmesh/bmesh_operators.h	2009-03-08 15:02:49 UTC (rev 19225)
@@ -146,6 +146,7 @@
 /*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 @@
 #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 @@
        "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)------------*/

Modified: branches/bmesh/blender/source/blender/bmesh/bmesh_queries.h
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/bmesh_queries.h	2009-03-08 13:14:12 UTC (rev 19224)
+++ branches/bmesh/blender/source/blender/bmesh/bmesh_queries.h	2009-03-08 15:02:49 UTC (rev 19225)
@@ -32,4 +32,5 @@
 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

Modified: branches/bmesh/blender/source/blender/bmesh/bmesh_walkers.h
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/bmesh_walkers.h	2009-03-08 13:14:12 UTC (rev 19224)
+++ branches/bmesh/blender/source/blender/bmesh/bmesh_walkers.h	2009-03-08 15:02:49 UTC (rev 19225)
@@ -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

Modified: branches/bmesh/blender/source/blender/bmesh/intern/bmesh_eulers.c
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/intern/bmesh_eulers.c	2009-03-08 13:14:12 UTC (rev 19224)
+++ branches/bmesh/blender/source/blender/bmesh/intern/bmesh_eulers.c	2009-03-08 15:02:49 UTC (rev 19225)
@@ -317,6 +317,8 @@
 			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;
 }
 

Modified: branches/bmesh/blender/source/blender/bmesh/intern/bmesh_iterators.c
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/intern/bmesh_iterators.c	2009-03-08 13:14:12 UTC (rev 19224)
+++ branches/bmesh/blender/source/blender/bmesh/intern/bmesh_iterators.c	2009-03-08 15:02:49 UTC (rev 19225)
@@ -182,6 +182,30 @@
 	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 @@
 			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;
 	}

Modified: branches/bmesh/blender/source/blender/bmesh/intern/bmesh_operators.c
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/intern/bmesh_operators.c	2009-03-08 13:14:12 UTC (rev 19224)
+++ branches/bmesh/blender/source/blender/bmesh/intern/bmesh_operators.c	2009-03-08 15:02:49 UTC (rev 19225)
@@ -809,6 +809,11 @@
 	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)
 {

Modified: branches/bmesh/blender/source/blender/bmesh/intern/bmesh_queries.c
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/intern/bmesh_queries.c	2009-03-08 13:14:12 UTC (rev 19224)
+++ branches/bmesh/blender/source/blender/bmesh/intern/bmesh_queries.c	2009-03-08 15:02:49 UTC (rev 19225)
@@ -62,14 +62,21 @@
 	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));
+}
+
 /*
  * BMESH VERT IN FACE
  *

Modified: branches/bmesh/blender/source/blender/bmesh/intern/bmesh_walkers.c
===================================================================
--- branches/bmesh/blender/source/blender/bmesh/intern/bmesh_walkers.c	2009-03-08 13:14:12 UTC (rev 19224)
+++ branches/bmesh/blender/source/blender/bmesh/intern/bmesh_walkers.c	2009-03-08 15:02:49 UTC (rev 19225)
@@ -11,13 +11,20 @@
  - 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 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,35 +58,40 @@
  *  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

@@ Diff output truncated at 10240 characters. @@




More information about the Bf-blender-cvs mailing list