implemented an (edge) loop walker. note I misunderstood
authorJoseph Eagar <joeedh@gmail.com>
Wed, 11 Mar 2009 05:13:36 +0000 (05:13 +0000)
committerJoseph Eagar <joeedh@gmail.com>
Wed, 11 Mar 2009 05:13:36 +0000 (05:13 +0000)
how original edge loop worked, and made it so if it starts
at a boundary edge, it walks across the boundary.  I'm not
sure if this is bad, most of the time I do that I want it
to do that anyway.

source/blender/bmesh/bmesh.h
source/blender/bmesh/bmesh_operators.h
source/blender/bmesh/bmesh_queries.h
source/blender/bmesh/bmesh_walkers.h
source/blender/bmesh/intern/bmesh_construct.c
source/blender/bmesh/intern/bmesh_opdefines.c
source/blender/bmesh/intern/bmesh_polygon.c
source/blender/bmesh/intern/bmesh_queries.c
source/blender/bmesh/intern/bmesh_walkers.c
source/blender/bmesh/intern/editmesh_to_bmesh.c
source/blender/editors/mesh/editmesh_mods.c

index 3d72d12651263d692b575bf1f68ee35957fb741d..0416ca8efdfc5a95af945115d574c37d9cf411eb 100644 (file)
@@ -209,7 +209,9 @@ void BM_Data_Facevert_Edgeinterp(struct BMesh *bm, struct BMVert *v1, struct BMV
 //void bmesh_data_interp_from_face(struct BMesh *bm, struct BMFace *source, struct BMFace *target);
 
 struct EditMesh;
+struct BMOperator;
 BMesh *editmesh_to_bmesh(struct EditMesh *em);
+BMesh *init_editmesh_to_bmesh(struct EditMesh *em, struct BMOperator *op);
 struct EditMesh *bmesh_to_editmesh(BMesh *bm);
 
 /*include the rest of the API*/
index e0ee4ce1ba98e60ed6e29f0225340f86c47c1b6d..9e3def37b2b767acd535039fa718868cf4591256 100644 (file)
@@ -55,6 +55,11 @@ enum {
 /*editmesh->bmesh op*/
 enum {
        BMOP_FROM_EDITMESH_EM, /*em*/
+       
+       /*maps old elements to new ones.
+        coud do new elements to old too,
+        in the future*/
+       BMOP_FROM_EDITMESH_MAP,
        BMOP_FROM_EDITMESH_TOTSLOT,
 };
 
index cc0a7214d605fceaad6e70f2b416df993d709255..204f3fb3305929d9436220dde0d32d492ae95ddf 100644 (file)
@@ -33,4 +33,5 @@ int BM_Exist_Face_Overlaps(struct BMesh *bm, struct BMVert **varr, int len, stru
 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);
+int BM_EdgesAroundVert(BMVert *v);
 #endif
index 5b3da894511e2dd3ec2f3fabd95dd7931baa23af..3d74a915bac6fd33699463f58b7b82159448bee5 100644 (file)
@@ -39,11 +39,11 @@ BMW_End(&walker);
 */
 
 #define BMW_SHELL      0
-/*#define BMW_LOOP     1
-#define BMW_RING       2
+#define BMW_LOOP       1
+/*#define BMW_RING     2
 #define BMW_UVISLANDS  3*/
-#define BMW_ISLANDBOUND        1
-#define BMW_ISLAND     2
-#define BMW_MAXWALKERS 3
+#define BMW_ISLANDBOUND        2
+#define BMW_ISLAND     3
+#define BMW_MAXWALKERS 4
 
 #endif
\ No newline at end of file
index f061358c8f8a8a056d1a2d6a4f042d02e43658ec..c517e802602c09d5eee87a0fbf8e410fe82c297c 100644 (file)
@@ -240,6 +240,11 @@ BMFace *BM_Make_Ngon(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **edges, int len,
                        }
                }
                
+               if (j != len) {
+                       /*sanity check*/
+                       return NULL;
+               }
+
                overlap = BM_Exist_Face_Overlaps(bm, verts, len, &f);
                
                /*clear flags*/
index 021c66123699fd03a8ec249ad800eac37c1ab0c4..b84937dc2fa3579ecd8ccffb54b854ead8e3eab8 100644 (file)
@@ -76,17 +76,17 @@ BMOpDefine def_subdop = {
 
 BMOpDefine def_edit2bmesh = {
        "editmesh_to_bmesh",
-       {{BMOP_OPSLOT_PNT, "emout"}},
+       {{BMOP_OPSLOT_PNT, "em"}, {BMOP_OPSLOT_MAPPING, "map"}},
        edit2bmesh_exec,
-       BMOP_TO_EDITMESH_TOTSLOT,
+       BMOP_FROM_EDITMESH_TOTSLOT,
        0
 };
 
 BMOpDefine def_bmesh2edit = {
        "bmesh_to_editmesh",
-       {{BMOP_OPSLOT_PNT, "em"}},
+       {{BMOP_OPSLOT_PNT, "emout"}},
        bmesh2edit_exec,
-       BMOP_FROM_EDITMESH_TOTSLOT,
+       BMOP_TO_EDITMESH_TOTSLOT,
        0
 };
 
index 841a28614878d1ef2be941bec3f63066e70448e2..9f8ca809a3cb42f8720c3ad4c81bf31ad4cbeb45 100644 (file)
@@ -395,18 +395,23 @@ int goodline(float (*projectverts)[3], BMFace *f, int v1i,
        
        if (testedgeside(v1, v2, v3)) return 0;
        
-       for (i=0; i<nvert; i++) {
-               if (i == v1i || i == v2i || i == v3i) continue;
+       //for (i=0; i<nvert; i++) {
+       do {
+               i = l->v->head.eflag2;
+               if (i == v1i || i == v2i || i == v3i) {
+                       l = l->head.next;
+                       continue;
+               }
                
-               VECCOPY(pv1, projectverts[i]); //l->v->head.eflag2]);
-               VECCOPY(pv2, projectverts[(i+1) % nvert]); //((BMLoop*)l->head.next)->v->head.eflag2]);
+               VECCOPY(pv1, projectverts[l->v->head.eflag2]);
+               VECCOPY(pv2, projectverts[((BMLoop*)l->head.next)->v->head.eflag2]);
                
                //if (linecrosses(pv1, pv2, v1, v3)) return 0;
                if (point_in_triangle(v1, v2, v3, pv1)) return 0;
                if (point_in_triangle(v3, v2, v1, pv1)) return 0;
 
-               //l = l->head.next;
-       } //while (l != f->loopbase);
+               l = l->head.next;
+       } while (l != f->loopbase);
        return 1;
 }
 /*
index 9bc4fe03fdc3098d968de2494b745e4883d3ae61..dcad4023d8aac4be3b5eeb46e45c9c930ad2f3a5 100644 (file)
@@ -36,6 +36,12 @@ int BM_Count_Element(BMesh *bm, int type)
        return 0;
 }
 
+int BM_EdgesAroundVert(BMVert *v)
+{
+       if (v == v->edge->v1) return bmesh_cycle_length(&v->edge->d1);
+       else return bmesh_cycle_length(&v->edge->d2);
+}
+
 /*
  * BMESH VERT IN EDGE
  *
@@ -52,7 +58,7 @@ int BM_Vert_In_Edge(BMEdge *e, BMVert *v)
 /*
  * BMESH OTHER EDGE IN FACE SHARING A VERTEX
  *
- * Returns an opposing edge that shares the same face.
+ * Returns an opposing loop that shares the same face.
  *
 */
 
index 91c15e4615b918deeb1ffa04489dfeb77b5b5dc9..b1f675f16f9883c60de1f5cc05852e649b2911e2 100644 (file)
    for if walkers fail.
 */
 
-/*
-NOTE: This code needs to be read through a couple of times!!
-*/
-
 typedef struct shellWalker{
        struct shellWalker *prev;
        BMVert *base;                   
@@ -51,6 +47,13 @@ typedef struct islandWalker {
        BMFace *cur;
 } islandWalker;
 
+typedef struct loopWalker {
+       struct islandWalker * prev;
+       BMEdge *cur, *start;
+       BMVert *lastv, *startv;
+       int startrad, stage2;
+} loopWalker;
+
 /*  NOTE: this comment is out of date, update it - joeedh
  *     BMWalker - change this to use the filters functions.
  *     
@@ -87,12 +90,13 @@ 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;
+static void loopWalker_begin(BMWalker *walker, void *data);
+static void *loopWalker_yield(BMWalker *walker);
+static void *loopWalker_step(BMWalker *walker);
 
 /* Pointer hiding*/
 typedef struct bmesh_walkerGeneric{
@@ -143,13 +147,12 @@ void BMW_Init(BMWalker *walker, BMesh *bm, int type, int searchmask)
                        walker->yield = islandWalker_yield;
                        size = sizeof(islandWalker);            
                        break;
-               
-               //case BMW_LOOP:
-               //      walker->begin = loopwalker_Begin;
-               //      walker->step = loopwalker_Step;
-               //      walker->yield = loopwalker_Yield;
-               //      size = sizeof(loopWalker);
-               //      break;
+               case BMW_LOOP:
+                       walker->begin = loopWalker_begin;
+                       walker->step = loopWalker_step;
+                       walker->yield = loopWalker_yield;
+                       size = sizeof(loopWalker);
+                       break;
                //case BMW_RING:
                //      walker->begin = ringwalker_Begin;
                //      walker->step = ringwalker_Step;
@@ -479,3 +482,115 @@ static void *islandWalker_step(BMWalker *walker)
        
        return curf;
 }
+
+
+/*     Island Walker:
+ *
+ *     Starts at a tool flagged-face and walks over the face region
+ *
+ *     TODO:
+ *
+ *  Add restriction flag/callback for wire edges.
+ * 
+*/
+
+static void loopWalker_begin(BMWalker *walker, void *data){
+       loopWalker *lwalk = NULL, owalk;
+       BMEdge *e = data;
+       BMVert *v;
+       int found=1, val;
+
+       v = e->v1;
+
+       val = BM_EdgesAroundVert(v);
+
+       BMW_pushstate(walker);
+       
+       lwalk = walker->currentstate;
+       BLI_ghash_insert(walker->visithash, e, NULL);
+       
+       lwalk->cur = lwalk->start = e;
+       lwalk->lastv = lwalk->startv = v;
+       lwalk->stage2 = 0;
+       lwalk->startrad = BM_FacesAroundEdge(e);
+
+       /*rewind*/
+       while (walker->currentstate) {
+               owalk = *((loopWalker*)walker->currentstate);
+               BMW_walk(walker);
+       }
+
+       BMW_pushstate(walker);
+       lwalk = walker->currentstate;
+       *lwalk = owalk;
+
+       if (lwalk->lastv == owalk.cur->v1) lwalk->lastv = owalk.cur->v2;
+       else lwalk->lastv = owalk.cur->v1;
+
+       lwalk->startv = lwalk->lastv;
+
+       BLI_ghash_free(walker->visithash, NULL, NULL);
+       walker->visithash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp);
+       BLI_ghash_insert(walker->visithash, owalk.cur, NULL);
+}
+
+static void *loopWalker_yield(BMWalker *walker)
+{
+       loopWalker *lwalk = walker->currentstate;
+
+       return lwalk->cur;
+}
+
+static void *loopWalker_step(BMWalker *walker)
+{
+       loopWalker *lwalk = walker->currentstate, owalk;
+       BMIter iter;
+       BMEdge *e = lwalk->cur, *nexte = NULL;
+       BMLoop *l, *l2;
+       BMVert *v;
+       int val, rlen, found=0, i=0, stopi;
+
+       owalk = *lwalk;
+       
+       if (e->v1 == lwalk->lastv) v = e->v2;
+       else v = e->v1;
+
+       val = BM_EdgesAroundVert(v);
+       
+       BMW_popstate(walker);
+       
+       rlen = owalk.startrad;
+       l = e->loop;
+
+       if (val == 4 || val == 2 || rlen == 1) {                
+               i = 0;
+               stopi = val / 2;
+               while (1) {
+                       if (rlen != 1 && i == stopi) break;
+
+                       l = BM_OtherFaceLoop(l->e, l->f, v);
+                       l2 = bmesh_radial_nextloop(l);
+                       
+                       if (l2 == l) {
+                               break;
+                       }
+
+                       l = l2;
+
+                       i += 1;
+               }
+       }
+       
+       if (l != e->loop && !BLI_ghash_haskey(walker->visithash, l->e)) {
+               if (!(rlen != 1 && i != stopi)) {
+                       BMW_pushstate(walker);
+                       lwalk = walker->currentstate;
+                       *lwalk = owalk;
+                       lwalk->cur = l->e;
+                       lwalk->lastv = v;
+                       BLI_ghash_insert(walker->visithash, l->e, NULL);
+               }
+       }
+       
+       return owalk.cur;
+}
index bd82144f5f29e142ecc4c21efc9d7d12be845615..656e9804aaf40d7aea1c7306db09c8d7fd18c13d 100644 (file)
@@ -86,7 +86,7 @@ static void editmesh_corners_to_loops(BMesh *bm, CustomData *facedata, void *fac
  *
 */
 
-static BMVert *editvert_to_BMVert(BMesh *bm, EditMesh *em, EditVert *eve)
+static BMVert *editvert_to_BMVert(BMesh *bm, BMOperator *op, EditMesh *em, EditVert *eve)
 {
                BMVert *v = NULL;
 
@@ -98,6 +98,8 @@ static BMVert *editvert_to_BMVert(BMesh *bm, EditMesh *em, EditVert *eve)
                if(eve->f & SELECT) BM_Select_Vert(bm, v, 1);
                v->bweight = eve->bweight;
 
+               BMO_Insert_MapPointer(bm, op, BMOP_FROM_EDITMESH_MAP, eve, v);
+
                /*Copy Custom Data*/
                CustomData_bmesh_copy_data(&em->vdata, &bm->vdata, eve->data, &v->data);
                
@@ -112,7 +114,7 @@ static BMVert *editvert_to_BMVert(BMesh *bm, EditMesh *em, EditVert *eve)
  *
 */
 
-static void editedge_to_BMEdge_internal(BMesh *bm, EditMesh *em, BMEdge *e, EditEdge *eed)
+static void editedge_to_BMEdge_internal(BMesh *bm, BMOperator *op, EditMesh *em, BMEdge *e, EditEdge *eed)
 {
        e->crease = eed->crease;
        e->bweight = eed->bweight;
@@ -124,9 +126,11 @@ static void editedge_to_BMEdge_internal(BMesh *bm, EditMesh *em, BMEdge *e, Edit
        e->head.flag |= eed->sharp ? BM_SHARP : 0;
 
        CustomData_bmesh_copy_data(&em->edata, &bm->edata, eed->data, &e->data);
+
+       BMO_Insert_MapPointer(bm, op, BMOP_FROM_EDITMESH_MAP, eed, e);
 }
 
-static BMEdge *editedge_to_BMEdge(BMesh *bm, EditMesh *em, EditEdge *eed)
+static BMEdge *editedge_to_BMEdge(BMesh *bm, BMOperator *op, EditMesh *em, EditEdge *eed)
 {
                BMVert *v1 = NULL, *v2 = NULL;
                BMEdge *e = NULL;
@@ -136,7 +140,7 @@ static BMEdge *editedge_to_BMEdge(BMesh *bm, EditMesh *em, EditEdge *eed)
        
                e = BM_Make_Edge(bm, v1, v2,NULL, 0); 
 
-               editedge_to_BMEdge_internal(bm, em, e, eed);
+               editedge_to_BMEdge_internal(bm, op, em, e, eed);
 
                return e;
 }
@@ -149,7 +153,7 @@ static BMEdge *editedge_to_BMEdge(BMesh *bm, EditMesh *em, EditEdge *eed)
  *
 */
 
-static BMFace *editface_to_BMFace(BMesh *bm, EditMesh *em, EditFace *efa, int numCol, int numTex)
+static BMFace *editface_to_BMFace(BMesh *bm, BMOperator *op, EditMesh *em, EditFace *efa, int numCol, int numTex)
 {
                BMVert *v1 = NULL, *v2 = NULL;
                BMFace *f = NULL;
@@ -165,11 +169,11 @@ static BMFace *editface_to_BMFace(BMesh *bm, EditMesh *em, EditFace *efa, int nu
                        edar[2] = BM_Make_Edge(bm, efa->v3->tmp.p, efa->v1->tmp.p, NULL, 1); 
                }
 
-               editedge_to_BMEdge_internal(bm, em, edar[0], efa->e1);
-               editedge_to_BMEdge_internal(bm, em, edar[1], efa->e2);
-               editedge_to_BMEdge_internal(bm, em, edar[2], efa->e3);
+               editedge_to_BMEdge_internal(bm, op, em, edar[0], efa->e1);
+               editedge_to_BMEdge_internal(bm, op, em, edar[1], efa->e2);
+               editedge_to_BMEdge_internal(bm, op, em, edar[2], efa->e3);
                if(efa->v4)
-                       editedge_to_BMEdge_internal(bm, em, edar[3], efa->e4);
+                       editedge_to_BMEdge_internal(bm, op, em, edar[3], efa->e4);
 
 
                if(efa->e1->fgoni) edar[0]->head.flag |= BM_FGON;
@@ -185,6 +189,9 @@ static BMFace *editface_to_BMFace(BMesh *bm, EditMesh *em, EditFace *efa, int nu
                v2 = efa->v2->tmp.p;
 
                f = BM_Make_Ngon(bm, v1, v2, edar, len, 0);
+
+               BMO_Insert_MapPointer(bm, op, BMOP_FROM_EDITMESH_MAP, efa, f);
+
                f->head.flag = 0;
                f->mat_nr = efa->mat_nr;
                if(efa->f & SELECT) BM_Select_Face(bm, f, 1);
@@ -267,7 +274,7 @@ static void fuse_fgon(BMesh *bm, BMFace *f)
        }
 }
 
-static BM_fgonconvert(BMesh *bm, EditMesh *em, int numCol, int numTex)
+static BM_fgonconvert(BMesh *bm, BMOperator *op, EditMesh *em, int numCol, int numTex)
 {
        EditFace *efa;
        BMFace *f;
@@ -318,7 +325,7 @@ static BM_fgonconvert(BMesh *bm, EditMesh *em, int numCol, int numTex)
                        /*first pass: add in faces for this fgon*/
                        for(b=a, sb1 = sb; b<amount && sb1->x == sb->x; b++, sb1++){
                                efa = sb1->efa;
-                               sb1->f = editface_to_BMFace(bm, em, efa, numCol, numTex);
+                               sb1->f = editface_to_BMFace(bm, op, em, efa, numCol, numTex);
                                sb1->done = 1;
                        }
                        /*fuse fgon*/
@@ -357,7 +364,7 @@ static void tag_wire_edges(EditMesh *em){
  *
 */
 
-BMesh *editmesh_to_bmesh_intern(EditMesh *em, BMesh *bm) {
+BMesh *editmesh_to_bmesh_intern(EditMesh *em, BMesh *bm, BMOperator *op) {
        BMVert *v;
        EditVert *eve;
        EditEdge *eed;
@@ -398,20 +405,20 @@ BMesh *editmesh_to_bmesh_intern(EditMesh *em, BMesh *bm) {
 
        /*add verts*/
        for(eve = em->verts.first; eve; eve = eve->next){
-               v = editvert_to_BMVert(bm, em, eve);
+               v = editvert_to_BMVert(bm, op, em, eve);
                eve->tmp.p = v;
        }
        /*convert f-gons*/
-       BM_fgonconvert(bm, em, numCol, numTex);
+       BM_fgonconvert(bm, op, em, numCol, numTex);
        
        /*do quads + triangles*/
        for(efa = em->faces.first; efa; efa = efa->next){
-               if(!efa->tmp.l) editface_to_BMFace(bm, em, efa, numCol, numTex);
+               if(!efa->tmp.l) editface_to_BMFace(bm, op, em, efa, numCol, numTex);
        }
 
        /*add wire edges*/      
        for(eed = em->edges.first; eed; eed = eed->next){
-               if(eed->f1) editedge_to_BMEdge(bm, em, eed);
+               if(eed->f1) editedge_to_BMEdge(bm, op, em, eed);
        }
        //BM_end_edit(bm, BM_CALC_NORM);
        return bm;
@@ -419,7 +426,7 @@ BMesh *editmesh_to_bmesh_intern(EditMesh *em, BMesh *bm) {
 
 void edit2bmesh_exec(BMesh *bmesh, BMOperator *op)
 {
-       editmesh_to_bmesh_intern(op->slots[BMOP_FROM_EDITMESH_EM].data.p, bmesh);
+       editmesh_to_bmesh_intern(op->slots[BMOP_FROM_EDITMESH_EM].data.p, bmesh, op);
 }
 
 BMesh *editmesh_to_bmesh(EditMesh *em)
@@ -436,5 +443,19 @@ BMesh *editmesh_to_bmesh(EditMesh *em)
        BMO_Exec_Op(bm, &conv);
        BMO_Finish_Op(bm, &conv);
 
+       return bm;
+}
+
+BMesh *init_editmesh_to_bmesh(EditMesh *em, BMOperator *op)
+{
+       BMesh *bm;
+       int allocsize[4] = {512,512,2048,512}, numTex, numCol;
+
+       /*allocate a bmesh*/
+       bm = BM_Make_Mesh(allocsize);
+
+       BMO_Init_Op(op, BMOP_FROM_EDITMESH);
+       BMO_Set_Pnt(op, BMOP_FROM_EDITMESH_EM, em);
+
        return bm;
 }
\ No newline at end of file
index e2898d886405881749814c9e50da1dd997044749..0e0694fa168ca50d1ccd44927e326ea489ba8683 100644 (file)
@@ -1782,6 +1782,34 @@ static int edge_not_in_tagged_face(EditMesh *em, EditEdge *eed)
        - has vertices with valence 2
 */
 static void edgeloop_select(EditMesh *em, EditEdge *starteed, int select)
+{
+       BMesh *bm;
+       BMEdge *e;
+       EditMesh *em2;
+       BMOperator op;
+       BMWalker walker;
+
+       bm = init_editmesh_to_bmesh(em, &op);
+       BMO_Exec_Op(bm, &op);
+
+       e = BMO_Get_MapPointer(bm, &op, BMOP_FROM_EDITMESH_MAP, starteed);
+
+       BMW_Init(&walker, bm, BMW_LOOP, 0);
+       e = BMW_Begin(&walker, e);
+       for (; e; e=BMW_Step(&walker)) {
+               BM_Select(bm, e, 1);
+       }
+       BMW_End(&walker);
+       
+       BMO_Finish_Op(bm, &op);
+       
+       em2 = bmesh_to_editmesh(bm);
+       BM_Free_Mesh(bm);
+       set_editMesh(em, em2);
+       MEM_freeN(em2);
+}
+
+static void edgeloop_select_old(EditMesh *em, EditEdge *starteed, int select)
 {
        EditVert *eve;
        EditEdge *eed;