Part two of branch creation: add new files
authorJoseph Eagar <joeedh@gmail.com>
Tue, 22 May 2007 20:03:24 +0000 (20:03 +0000)
committerJoseph Eagar <joeedh@gmail.com>
Tue, 22 May 2007 20:03:24 +0000 (20:03 +0000)
14 files changed:
source/blender/blenkernel/BKE_bmesh.h [new file with mode: 0644]
source/blender/blenlib/BLI_PointerArray.h [new file with mode: 0644]
source/blender/blenlib/intern/pa_array.c [new file with mode: 0644]
source/blender/bmesh/BME_eulers.c [new file with mode: 0644]
source/blender/bmesh/BME_mesh.c [new file with mode: 0644]
source/blender/bmesh/BME_structure.c [new file with mode: 0644]
source/blender/bmesh/BME_tools.c [new file with mode: 0644]
source/blender/bmesh/SConscript [new file with mode: 0644]
source/blender/bmesh/bmesh_private.h [new file with mode: 0644]
source/blender/include/editbmesh.h [new file with mode: 0644]
source/blender/src/editbmesh_derivedmesh.c [new file with mode: 0644]
source/blender/src/editbmesh_interface.c [new file with mode: 0644]
source/blender/src/editbmesh_tools.c [new file with mode: 0644]
source/blender/src/editbmesh_util.c [new file with mode: 0644]

diff --git a/source/blender/blenkernel/BKE_bmesh.h b/source/blender/blenkernel/BKE_bmesh.h
new file mode 100644 (file)
index 0000000..4197c3c
--- /dev/null
@@ -0,0 +1,176 @@
+/**
+ * BKE_bmesh.h    jan 2007
+ *
+ *     BMesh modeler structure and functions.
+ *
+ * $Id: BKE_bmesh.h,v 1.00 2007/01/17 17:42:01 Briggs Exp $
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this. 
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2004 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Geoffrey Bantle.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+
+#ifndef BKE_BMESH_H
+#define BKE_BMESH_H
+
+#include "DNA_listBase.h"
+#include "BLI_ghash.h"
+#include "DNA_customdata_types.h"
+
+struct BME_Vert;
+struct BME_Edge;
+struct BME_Poly;
+struct BME_Loop;
+struct RetopoPaintData;
+struct DerivedMesh;
+
+typedef struct BME_CycleNode{
+       struct BME_CycleNode *next, *prev;
+       void *data;
+} BME_CycleNode;
+
+typedef struct BME_Mesh
+{
+       ListBase verts, edges, polys, loops;
+       int lock;                                                                               /*if set, all calls to eulers will fail.*/
+       struct BME_Mesh *backup;                                                /*full copy of the mesh*/
+       int totvert, totedge, totpoly, totloop;                 /*record keeping*/
+       int nextv, nexte, nextp, nextl;                                 /*Next element ID for verts/edges/faces/loops. Never reused*/
+       struct CustomData vdata, edata, pdata, ldata;   /*Custom Data Layer information*/
+       struct DerivedMesh *derivedFinal, *derivedCage;
+       struct RetopoPaintData *retopo_paint_data; /*here for temporary code compatibility only*/
+       int lastDataMask;
+} BME_Mesh;
+
+//60, 52, 52, 12 704
+//60, 52, 84 
+
+
+typedef struct BME_Vert
+{
+       struct BME_Vert *next, *prev;
+       int     EID;
+       struct BME_Edge *edge;                                                  /*first edge in the disk cycle for this vertex*/
+       float no[3];                                                                    /*vertex normal. Actually pointer to custom data block*/
+       float co[3];                                                                    /*vertex location. Actually pointer to custom data block*/
+       void *data;                                                                             /*custom vertex data*/
+       int eflag1, eflag2;                                                             /*reserved for use by eulers*/
+       int tflag1, tflag2;                                                             /*reserved for use by tools*/
+       unsigned short flag, h;
+} BME_Vert;
+
+typedef struct BME_Edge
+{
+       struct BME_Edge *next, *prev;
+       int EID;
+       struct BME_Vert *v1, *v2;                                               /*note that order of vertex pointers means nothing to eulers*/
+       struct BME_CycleNode d1, d2;                                    /*disk cycle nodes for v1 and v2 respectivley*/
+       struct BME_Loop *loop;                                                  /*first BME_Loop in the radial cycle around this edge*/
+       void *data;                                                                             /*custom edge data*/
+       int eflag1, eflag2;                                                             /*reserved for use by eulers*/
+       int tflag1, tflag2;                                                             /*reserved for use by tools*/
+       unsigned char flag, h, crease;
+} BME_Edge;
+
+typedef struct BME_Loop 
+{      
+       struct BME_Loop *next, *prev;                                   /*circularly linked list around face*/
+       int EID;
+       struct BME_CycleNode radial;                                    /*circularly linked list used to find faces around an edge*/
+       struct BME_CycleNode *gref;                                             /*pointer to loop ref. Nasty.*/
+       struct BME_Vert *v;                                                             /*vertex that this loop starts at.*/
+       struct BME_Edge *e;                                                             /*edge this loop belongs to*/
+       struct BME_Poly *f;                                                             /*face this loop belongs to*/   
+       void *data;                                                                             /*custom per face vertex data*/
+       int eflag1, eflag2;                                                             /*reserved for use by eulers*/
+       int tflag1, tflag2;                                                             /*reserved for use by tools*/
+       unsigned short flag, h;
+} BME_Loop;
+
+typedef struct BME_Poly
+{
+       struct BME_Poly *next, *prev;
+       int EID;
+       struct BME_Loop *loopbase;                                              /*First editloop around Polygon.*/
+       struct ListBase holes;                                                  /*list of inner loops in the face*/
+       unsigned int len;                                                               /*total length of the face. Eulers should preserve this data*/
+       void *data;                                                                             /*custom face data*/
+       int eflag1, eflag2;                                                             /*reserved for use by eulers*/
+       int tflag1, tflag2;                                                             /*reserved for use by tools*/
+       unsigned short flag, h, mat_nr;
+} BME_Poly;
+
+//*EDGE UTILITIES*/
+int BME_verts_in_edge(struct BME_Vert *v1, struct BME_Vert *v2, struct BME_Edge *e);
+int BME_vert_in_edge(struct BME_Edge *e, BME_Vert *v);
+struct BME_Vert *BME_edge_getothervert(struct BME_Edge *e, struct BME_Vert *v);
+
+/*GENERAL CYCLE*/
+int BME_cycle_length(void *h);
+
+/*DISK CYCLE*/
+struct BME_Edge *BME_disk_nextedge(struct BME_Edge *e, struct BME_Vert *v); 
+struct BME_CycleNode *BME_disk_getpointer(struct BME_Edge *e, struct BME_Vert *v);
+struct BME_Edge *BME_disk_next_edgeflag(struct BME_Edge *e, struct BME_Vert *v, int eflag, int tflag);
+int BME_disk_count_edgeflag(struct BME_Vert *v, int eflag, int tflag);
+
+/*RADIAL CYCLE*/
+struct BME_Loop *BME_radial_nextloop(struct BME_Loop *l);
+int BME_radial_find_face(struct BME_Edge *e,struct BME_Poly *f);
+
+/*MESH CREATION/DESTRUCTION*/
+struct BME_Mesh *BME_make_mesh(void);
+void BME_free_mesh(struct BME_Mesh *bm);
+struct BME_Mesh *BME_copy_mesh(struct BME_Mesh *bm);
+/*FULL MESH VALIDATION*/
+int BME_validate_mesh(struct BME_Mesh *bm, int halt);
+/*ENTER/EXIT MODELLING LOOP*/
+int BME_model_begin(struct BME_Mesh *bm);
+void BME_model_end(struct BME_Mesh *bm);
+
+/*MESH CONSTRUCTION API.*/
+/*MAKE*/
+struct BME_Vert *BME_MV(struct BME_Mesh *bm, float *vec);
+struct BME_Edge *BME_ME(struct BME_Mesh *bm, struct BME_Vert *v1, struct BME_Vert *v2);
+struct BME_Poly *BME_MF(struct BME_Mesh *bm, struct BME_Vert *v1, struct BME_Vert *v2, struct BME_Edge **elist, int len);
+/*KILL*/
+int BME_KV(struct BME_Mesh *bm, struct BME_Vert *v);
+int BME_KE(struct BME_Mesh *bm, struct BME_Edge *e);
+int BME_KF(struct BME_Mesh *bm, struct BME_Poly *bply);
+/*SPLIT*/
+struct BME_Vert *BME_SEMV(struct BME_Mesh *bm, struct BME_Vert *tv, struct BME_Edge *e, struct BME_Edge **re);
+struct BME_Poly *BME_SFME(struct BME_Mesh *bm, struct BME_Poly *f, struct BME_Vert *v1, struct BME_Vert *v2, struct BME_Loop **rl);
+/*JOIN*/
+int BME_JEKV(struct BME_Mesh *bm, struct BME_Edge *ke, struct BME_Vert *kv);
+struct BME_Poly *BME_JFKE(struct BME_Mesh *bm, struct BME_Poly *f1, struct BME_Poly *f2,struct BME_Edge *e); /*no reason to return BME_Poly pointer?*/
+/*NORMAL FLIP(Is its own inverse)*/
+int BME_loop_reverse(struct BME_Mesh *bm, struct BME_Poly *f);
+
+/*TOOLS CODE*/
+struct BME_Loop *BME_inset_edge(struct BME_Mesh *bm, struct BME_Loop *l, struct BME_Poly *f);
+struct BME_Poly *BME_inset_poly(struct BME_Mesh *bm, struct BME_Poly *f);
+#endif
diff --git a/source/blender/blenlib/BLI_PointerArray.h b/source/blender/blenlib/BLI_PointerArray.h
new file mode 100644 (file)
index 0000000..15c9fde
--- /dev/null
@@ -0,0 +1,14 @@
+#ifndef _BLI_PARRAY_H
+#define _BLI_PARRAY_H
+
+typedef struct PointerArray {
+    void **array;
+    int len;
+} PointerArray;
+
+extern void PA_AddToArray(PointerArray *arr, void *ptr, int index);
+extern void PA_FreeArray(PointerArray *arr);
+
+#define LA_ARR_INC     2048
+
+#endif /* _BLI_PARRAY_H */
diff --git a/source/blender/blenlib/intern/pa_array.c b/source/blender/blenlib/intern/pa_array.c
new file mode 100644 (file)
index 0000000..0d5dc10
--- /dev/null
@@ -0,0 +1,30 @@
+#include "BLI_PointerArray.h"
+#include "MEM_guardedalloc.h"
+
+#include <stdio.h>
+
+void PA_AddToArray(struct PointerArray *arr, void *ptr, int index)
+{
+    void **tmp;
+    int i;
+    
+    if (index>=arr->len) {
+        //if (arr->len != 0) printf("Reallocating Array: %d.\n", arr->len);
+        tmp = MEM_callocN(sizeof(void*)*(arr->len+LA_ARR_INC), "new pointer arrray");
+               if (arr->array) {
+                       for (i=0; i<arr->len; i++) tmp[i] = arr->array[i];
+                       MEM_freeN(arr->array);
+               }                       
+               arr->len += LA_ARR_INC;
+               arr->array = tmp;
+    }
+    arr->array[index] = ptr;
+}
+
+void PA_FreeArray(struct PointerArray *arr)
+{
+    if (arr->array) MEM_freeN(arr->array);
+    arr->array = NULL;
+    arr->len = 0;
+}    
diff --git a/source/blender/bmesh/BME_eulers.c b/source/blender/bmesh/BME_eulers.c
new file mode 100644 (file)
index 0000000..2d0ee6b
--- /dev/null
@@ -0,0 +1,1002 @@
+/**
+ * BME_eulers.c    jan 2007
+ *
+ *     BMesh Euler construction API.
+ *
+ * $Id: BME_eulers.c,v 1.00 2007/01/17 17:42:01 Briggs Exp $
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this. 
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2004 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Geoffrey Bantle.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_listBase.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_mesh_types.h"
+
+#include "BKE_utildefines.h"
+#include "BKE_bmesh.h"
+
+#include "BLI_blenlib.h"
+#include "bmesh_private.h"
+#include "BLI_ghash.h"
+
+/*********************************************************
+ *                    "Euler API"                        *
+ *                                                       *
+ *                                                       *
+ *      Primitive construction operators for mesh tools.    *
+ *                                                       *
+ **********************************************************/
+
+
+/*
+       The functions in this file represent the 'primitive' or 'atomic' operators that
+       mesh tools use to manipulate the topology of the structure.* The purpose of these
+       functions is to provide a trusted set of operators to manipulate the mesh topology
+       and which can also be combined together like building blocks to create more 
+       sophisticated tools. It needs to be stressed that NO manipulation of an existing 
+       mesh structure should be done outside of these functions.
+       
+       In the BMesh system, each euler is named by an ancronym which describes what it actually does.
+       Furthermore each Euler has a logical inverse. An important design criteria of all Eulers is that
+       through a Euler's logical inverse you can 'undo' an operation. (Special note should
+       be taken of BME_loop_reverse, which is its own inverse).
+               
+       BME_MF/KF: Make Face and Kill Face
+       BME_ME/KE: Make Edge and Kill Edge
+       BME_MV/KV: Make Vert and Kill Vert
+       BME_SEMV/JEKV: Split Edge, Make Vert and Join Edge, Kill Vert
+       BME_SFME/JFKE: Split Face, Make Edge and Join Face, Kill Edge
+       BME_loop_reverse: Reverse a Polygon's loop cycle. (used for flip normals for one)
+       
+       Using a combination of these eleven eulers any non-manifold modelling operation can be achieved.
+       Each Euler operator has a detailed explanation of what is does in the comments preceding its 
+       code. 
+
+   *The term "Euler Operator" is actually a misnomer when referring to a non-manifold 
+    data structure. Its use is in keeping with the convention established by others.
+
+       TODO:
+       -Finish inserting 'strict' validation in all Eulers
+*/
+
+#define RETCLEAR(bm) {bm->rval->v = bm->rval->e = bm->rval->f = bm->rva->l = NULL;}
+/*MAKE Eulers*/
+
+/**
+ *                     BME_MV
+ *
+ *     MAKE VERT EULER:
+ *     
+ *     Makes a single loose vertex.
+ *
+ *     Returns -
+ *     A BME_Vert pointer.
+ */
+
+BME_Vert *BME_MV(BME_Mesh *bm, float *vec){
+       BME_Vert *v = BME_addvertlist(bm, NULL);        
+       VECCOPY(v->co,vec);
+       return v;
+}
+
+/**
+ *                     BME_ME
+ *
+ *     MAKE EDGE EULER:
+ *     
+ *     Makes a single wire edge between two vertices.
+ *     If the caller does not want there to be duplicate
+ *     edges between the vertices, it is up to them to check 
+ *     for this condition beforehand.
+ *
+ *     Returns -
+ *     A BME_Edge pointer.
+ */
+
+BME_Edge *BME_ME(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2){
+       BME_Edge *e=NULL;
+       BME_CycleNode *d1=NULL, *d2=NULL;
+       int valance1=0, valance2=0, edok;
+       
+       /*edge must be between two distinct vertices...*/
+       if(v1 == v2) return NULL;
+       
+       #ifndef BME_FASTEULER
+       /*count valance of v1*/
+       if(v1->edge){ 
+               d1 = BME_disk_getpointer(v1->edge,v1);
+               if(d1) valance1 = BME_cycle_length(d1);
+               else BME_error();
+       }
+       if(v2->edge){
+               d2 = BME_disk_getpointer(v2->edge,v2);
+               if(d2) valance2 = BME_cycle_length(d2);
+               else BME_error();
+       }
+       #endif
+       
+       /*go ahead and add*/
+       e = BME_addedgelist(bm, v1, v2, NULL);
+       BME_disk_append_edge(e, e->v1);
+       BME_disk_append_edge(e, e->v2);
+       
+       #ifndef BME_FASTEULER
+       /*verify disk cycle lengths*/
+       d1 = BME_disk_getpointer(e, e->v1);
+       edok = BME_cycle_validate(valance1+1, d1);
+       if(!edok) BME_error();
+       d2 = BME_disk_getpointer(e, e->v2);
+       edok = BME_cycle_validate(valance2+1, d2);
+       if(!edok) BME_error();
+       
+       /*verify that edge actually made it into the cycle*/
+       edok = BME_disk_hasedge(v1, e);
+       if(!edok) BME_error();
+       edok = BME_disk_hasedge(v2, e);
+       if(!edok) BME_error();
+       #endif
+       return e;
+}
+
+
+
+/**
+ *                     BME_MF
+ *
+ *     MAKE FACE EULER:
+ *     Takes a list of edge pointers which form a closed loop and makes a face 
+ *  from them. The first edge in elist is considered to be the start of the 
+ *     polygon, and v1 and v2 are its vertices and determine the winding of the face 
+ *  Other than the first edge, no other assumptions are made about the order of edges
+ *  in the elist array. To verify that it is a single closed loop and derive the correct 
+ *  order a simple series of verifications is done and all elements are visited.
+ *             
+ *  Returns -
+ *     A BME_Poly pointer
+ */
+
+#define MF_CANDIDATE   1
+#define MF_VISITED             2
+#define MF_TAKEN               4 
+
+BME_Poly *BME_MF(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Edge **elist, int len)
+{
+       BME_Poly *f = NULL;
+       BME_Edge *curedge;
+       BME_Vert *curvert, *tv, *nextv,**vlist;
+       int i, j, done, cont, edok,vlen;
+       
+       if(len < 2) return NULL;
+       
+       /*make sure that v1 and v2 are in elist[0]*/
+       if(BME_verts_in_edge(v1,v2,elist[0]) == 0) return NULL;
+       
+       /*clear euler flags*/
+       for(i=0;i<len;i++) elist[i]->eflag1=elist[i]->eflag2 = 0;
+       for(i=0;i<len;i++){
+               elist[i]->eflag1 |= MF_CANDIDATE;
+               
+               /*if elist[i] has a loop, count its radial length*/
+               if(elist[i]->loop) elist[i]->eflag2 = BME_cycle_length(&(elist[i]->loop->radial));
+               else elist[i]->eflag2 = 0;
+       }
+       
+       /*      For each vertex in each edge, it must have exactly two MF_CANDIDATE edges attached to it
+               Note that this does not gauruntee that face is a single closed loop. At best it gauruntees
+               that elist contains a finite number of seperate closed loops.
+       */
+       for(i=0; i<len; i++){
+               edok = BME_disk_count_edgeflag(elist[i]->v1, MF_CANDIDATE, 0);
+               if(edok != 2) return NULL;
+               edok = BME_disk_count_edgeflag(elist[i]->v2, MF_CANDIDATE, 0);
+               if(edok != 2) return NULL;
+       }
+       
+       /*set start edge, start vert and target vert for our loop traversal*/
+       curedge = elist[0];
+       tv = v1;
+       curvert = v2;
+       
+       /*insert tv into vlist since its the first vertex in face*/
+       i=0;
+       vlist=MEM_callocN(sizeof(BME_Vert*)*len,"BME_MF vlist array");
+       vlist[i] = tv;
+
+       /*      Basic procedure: Starting with curv we find the edge in it's disk cycle which hasn't 
+               been visited yet. When we do, we put curv in a linked list and find the next MF_CANDIDATE
+               edge, loop until we find TV. We know TV is reachable because of test we did earlier.
+       */
+       done=0;
+       while(!done){
+               /*add curvert to vlist*/
+               /*insert some error cheking here for overflows*/
+               i++;
+               vlist[i] = curvert;
+               
+               /*mark curedge as visited*/
+               curedge->eflag1 |= MF_VISITED;
+               
+               /*find next edge and vert*/
+               curedge = BME_disk_next_edgeflag(curedge, curvert, MF_CANDIDATE, 0);
+               curvert = BME_edge_getothervert(curedge, curvert);
+               if(curvert == tv){
+                       curedge->eflag1 |= MF_VISITED;
+                       done=1;
+               }
+       }
+
+       /*      Verify that all edges have been visited It's possible that we did reach tv 
+               from sv, but that several unconnected loops were passed in via elist.
+       */
+       cont=1;
+       for(i=0; i<len; i++){
+               if((elist[i]->eflag1 & MF_VISITED) == 0) cont = 0;
+       }
+       
+       /*if we get this far, its ok to allocate the face and add the loops*/
+       if(cont){
+               BME_Loop *l;
+               BME_Edge *e;
+               f = BME_addpolylist(bm, NULL);
+               f->len = len;
+               for(i=0;i<len;i++){
+                       curvert = vlist[i];
+                       l = BME_create_loop(bm,curvert,NULL,f,NULL);
+                       if(!(f->loopbase)) f->loopbase = l;
+                       BME_cycle_append(f->loopbase, l);
+               }
+               
+               /*take care of edge pointers and radial cycle*/
+               for(i=0, l = f->loopbase; i<len; i++, l=l->next){
+                       e = NULL;
+                       if(l == f->loopbase) e = elist[0]; /*first edge*/
+                       
+                       else{/*search elist for others*/
+                               for(j=1; j<len; j++){
+                                       edok = BME_verts_in_edge(l->v, l->next->v, elist[j]);
+                                       if(edok){ 
+                                               e = elist[j];
+                                               break;
+                                       }
+                               }
+                       }
+                       l->e = e; /*set pointer*/
+                       BME_radial_append(e, l); /*append into radial*/
+               }
+
+               f->len = len;
+               
+               /*Validation Loop cycle*/
+               edok = BME_cycle_validate(len, f->loopbase);
+               if(!edok) BME_error();
+               for(i=0, l = f->loopbase; i<len; i++, l=l->next){
+                       /*validate loop vert pointers*/
+                       edok = BME_verts_in_edge(l->v, l->next->v, l->e);
+                       if(!edok) BME_error();
+                       /*validate the radial cycle of each edge*/
+                       edok = BME_cycle_length(&(l->radial));
+                       if(edok != (l->e->eflag2 + 1)) BME_error();
+               }
+       }
+       
+       MEM_freeN(vlist);
+       return f;
+}
+
+/* KILL Eulers */
+
+/**
+ *                     BME_KV
+ *
+ *     KILL VERT EULER:
+ *     
+ *     Kills a single loose vertex.
+ *
+ *     Returns -
+ *     1 for success, 0 for failure.
+ */
+
+int BME_KV(BME_Mesh *bm, BME_Vert *v){
+       if(v->edge == NULL){ 
+               BLI_remlink(&(bm->verts), v);
+               BME_free_vert(bm,v);
+               return 1;
+       }
+       return 0;
+}
+
+/**
+ *                     BME_KE
+ *
+ *     KILL EDGE EULER:
+ *     
+ *     Kills a wire edge.
+ *
+ *     Returns -
+ *     1 for success, 0 for failure.
+ */
+
+int BME_KE(BME_Mesh *bm, BME_Edge *e){
+       int edok;
+       
+       /*Make sure that no faces!*/
+       if(e->loop == NULL){
+               BME_disk_remove_edge(e, e->v1);
+               BME_disk_remove_edge(e, e->v2);
+               
+               /*verify that edge out of disk*/
+               edok = BME_disk_hasedge(e->v1, e);
+               if(edok) BME_error();
+               edok = BME_disk_hasedge(e->v2, e);
+               if(edok) BME_error();
+               
+               /*remove and deallocate*/
+               BLI_remlink(&(bm->edges), e);
+               BME_free_edge(bm, e);
+               return 1;
+       }
+       return 0;
+}
+
+/**
+ *                     BME_KF
+ *
+ *     KILL FACE EULER:
+ *     
+ *     The logical inverse of BME_MF.
+ *     Kills a face and removes each of its loops from the radial that it belongs to.
+ *
+ *  Returns -
+ *     1 for success, 0 for failure.
+*/
+
+int BME_KF(BME_Mesh *bm, BME_Poly *bply){
+       BME_Loop *newbase,*oldbase, *curloop;
+       int i,len=0;
+       
+       /*add validation to make sure that radial cycle is cleaned up ok*/
+       /*deal with radial cycle first*/
+       len = BME_cycle_length(bply->loopbase);
+       for(i=0, curloop=bply->loopbase; i < len; i++, curloop = curloop->next) 
+               BME_radial_remove_loop(curloop, curloop->e);
+       
+       /*now deallocate the editloops*/
+       for(i=0; i < len; i++){
+               newbase = bply->loopbase->next;
+               oldbase = bply->loopbase;
+               BME_cycle_remove(oldbase, oldbase);
+               BME_free_loop(bm, oldbase);
+               bply->loopbase = newbase;
+       }
+       
+       BLI_remlink(&(bm->polys), bply);
+       BME_free_poly(bm, bply);
+       return 1;
+}
+
+/*SPLIT Eulers*/
+
+/**
+ *                     BME_SEMV
+ *
+ *     SPLIT EDGE MAKE VERT:
+ *     Takes a given edge and splits it into two, creating a new vert.
+ *
+ *
+ *             Before: OV---------TV   
+ *             After:  OV----NV---TV
+ *
+ *  Returns -
+ *     BME_Vert pointer.
+ *
+*/
+
+BME_Vert *BME_SEMV(BME_Mesh *bm, BME_Vert *tv, BME_Edge *e, BME_Edge **re){
+       BME_Vert *nv, *ov;
+       BME_CycleNode *diskbase;
+       BME_Edge *ne;
+       int i, radlen, edok, valance1=0, valance2=0;
+       
+       if(BME_vert_in_edge(e,tv) == 0) return NULL;
+       ov = BME_edge_getothervert(e,tv);
+       //v2 = tv;
+
+       /*count valance of v1*/
+       diskbase = BME_disk_getpointer(e, ov);
+       valance1 = BME_cycle_length(diskbase);
+       /*count valance of v2*/
+       diskbase = BME_disk_getpointer(e, tv);
+       valance2 = BME_cycle_length(diskbase);
+       
+       nv = BME_addvertlist(bm, tv);
+       ne = BME_addedgelist(bm, nv, tv, e);
+       
+       //e->v2 = nv;
+       /*remove e from v2's disk cycle*/
+       BME_disk_remove_edge(e, tv);
+       /*swap out tv for nv in e*/
+       BME_edge_swapverts(e, tv, nv);
+       /*add e to nv's disk cycle*/
+       BME_disk_append_edge(e, nv);
+       /*add ne to nv's disk cycle*/
+       BME_disk_append_edge(ne, nv);
+       /*add ne to tv's disk cycle*/
+       BME_disk_append_edge(ne, tv);
+       /*verify disk cycles*/
+       diskbase = BME_disk_getpointer(ov->edge,ov);
+       edok = BME_cycle_validate(valance1, diskbase);
+       if(!edok) BME_error();
+       diskbase = BME_disk_getpointer(tv->edge,tv);
+       edok = BME_cycle_validate(valance2, diskbase);
+       if(!edok) BME_error();
+       diskbase = BME_disk_getpointer(nv->edge,nv);
+       edok = BME_cycle_validate(2, diskbase);
+       if(!edok) BME_error();
+       
+       /*Split the radial cycle if present*/
+       if(e->loop){
+               BME_Loop *nl,*l;
+               BME_CycleNode *radEBase=NULL, *radNEBase=NULL;
+               int radlen = BME_cycle_length(&(e->loop->radial));
+               /*Take the next loop. Remove it from radial. Split it. Append to appropriate radials.*/
+               while(e->loop){
+                       l=e->loop;
+                       l->f->len++;
+                       BME_radial_remove_loop(l,e);
+                       
+                       nl = BME_create_loop(bm,NULL,NULL,l->f,l);
+                       nl->prev = l;
+                       nl->next = l->next;
+                       nl->prev->next = nl;
+                       nl->next->prev = nl;
+                       nl->v = nv;
+                       
+                       /*assign the correct edge to the correct loop*/
+                       if(BME_verts_in_edge(nl->v, nl->next->v, e)){
+                               nl->e = e;
+                               l->e = ne;
+                               
+                               /*append l into ne's rad cycle*/
+                               if(!radNEBase){
+                                       radNEBase = &(l->radial);
+                                       radNEBase->next = NULL;
+                                       radNEBase->prev = NULL;
+                               }
+                               
+                               if(!radEBase){
+                                       radEBase = &(nl->radial);
+                                       radEBase->next = NULL;
+                                       radEBase->prev = NULL;
+                               }
+                               
+                               BME_cycle_append(radEBase,&(nl->radial));
+                               BME_cycle_append(radNEBase,&(l->radial));
+                                       
+                       }
+                       else if(BME_verts_in_edge(nl->v,nl->next->v,ne)){
+                               nl->e = ne;
+                               l->e = e;
+                               
+                               if(!radNEBase){
+                                       radNEBase = &(nl->radial);
+                                       radNEBase->next = NULL;
+                                       radNEBase->prev = NULL;
+                               }
+                               if(!radEBase){
+                                       radEBase = &(l->radial);
+                                       radEBase->next = NULL;
+                                       radEBase->prev = NULL;
+                               }
+                               BME_cycle_append(radEBase,&(l->radial));
+                               BME_cycle_append(radNEBase,&(nl->radial));
+                       }
+                                       
+               }
+               
+               e->loop = radEBase->data;
+               ne->loop = radNEBase->data;
+               
+               /*verify length of radial cycle*/
+               edok = BME_cycle_validate(radlen,&(e->loop->radial));
+               if(!edok) BME_error();
+               edok = BME_cycle_validate(radlen,&(ne->loop->radial));
+               if(!edok) BME_error();
+               
+               /*verify loop->v and loop->next->v pointers for e*/
+               for(i=0,l=e->loop; i < radlen; i++, l = l->radial.next->data){
+                       if(!(l->e == e)) BME_error();
+                       if(!(l->radial.data == l)) BME_error();
+                       if(l->prev->e != ne && l->next->e != ne) BME_error();
+                       edok = BME_verts_in_edge(l->v, l->next->v, e);
+                       if(!edok) BME_error();
+                       if(l->v == l->next->v) BME_error();
+                       if(l->e == l->next->e) BME_error();
+                       /*verify loop cycle for kloop->f*/
+                       edok = BME_cycle_validate(l->f->len, l->f->loopbase);
+                       if(!edok) BME_error();
+               }
+               /*verify loop->v and loop->next->v pointers for ne*/
+               for(i=0,l=ne->loop; i < radlen; i++, l = l->radial.next->data){
+                       if(!(l->e == ne)) BME_error();
+                       if(!(l->radial.data == l)) BME_error();
+                       if(l->prev->e != e && l->next->e != e) BME_error();
+                       edok = BME_verts_in_edge(l->v, l->next->v, ne);
+                       if(!edok) BME_error();
+                       if(l->v == l->next->v) BME_error();
+                       if(l->e == l->next->e) BME_error();
+                       /*verify loop cycle for kloop->f. Redundant*/
+                       edok = BME_cycle_validate(l->f->len, l->f->loopbase);
+                       if(!edok) BME_error();
+               }
+       }
+       
+       if(re) *re = ne;
+       return nv;
+}
+
+/**
+ *                     BME_SFME
+ *
+ *     SPLIT FACE MAKE EDGE:
+ *
+ *     Takes as input two vertices in a single face. An edge is created which divides the original face
+ *     into two distinct regions. One of the regions is assigned to the original face and it is closed off.
+ *     The second region has a new face assigned to it.
+ *
+ *     Examples:
+ *     
+ *     Before:               After:
+ *      ----------           ----------
+ *      |                |           |        | 
+ *      |        |           |   f1   |
+ *     v1   f1   v2          v1======v2
+ *      |        |           |   f2   |
+ *      |        |           |        |
+ *      ----------           ---------- 
+ *
+ *     Note that the input vertices can be part of the same edge. This will result in a two edged face.
+ *  This is desirable for advanced construction tools and particularly essential for edge bevel. Because
+ *  of this it is up to the caller to decide what to do with the extra edge.
+ *
+ *     Returns -
+ *  A BME_Poly pointer
+ */
+BME_Poly *BME_SFME(BME_Mesh *bm, BME_Poly *f, BME_Vert *v1, BME_Vert *v2, BME_Loop **rl){
+
+       BME_Poly *f2;
+       BME_Loop *v1loop = NULL, *v2loop = NULL, *curloop, *f1loop=NULL, *f2loop=NULL;
+       BME_Edge *e;
+       int i, len, f1len, f2len;
+       
+       if(f->holes.first) return NULL; //not good, fix me
+       
+       /*verify that v1 and v2 are in face.*/
+       len = BME_cycle_length(f->loopbase);
+       for(i = 0, curloop = f->loopbase; i < len; i++, curloop = curloop->next){
+               if(curloop->v == v1) v1loop = curloop;
+               else if(curloop->v == v2) v2loop = curloop;
+       }
+       
+       if(!v1loop || !v2loop) return NULL;
+       
+       /*allocate new edge between v1 and v2*/
+       e = BME_addedgelist(bm, v1, v2,NULL);
+       BME_disk_append_edge(e, v1);
+       BME_disk_append_edge(e, v2);
+       
+       f2 = BME_addpolylist(bm,f);
+       f1loop = BME_create_loop(bm,v2,e,f,NULL);
+       f2loop = BME_create_loop(bm,v1,e,f2,NULL);
+       
+       f1loop->prev = v2loop->prev;
+       f2loop->prev = v1loop->prev;
+       v2loop->prev->next = f1loop;
+       v1loop->prev->next = f2loop;
+       
+       f1loop->next = v1loop;
+       f2loop->next = v2loop;
+       v1loop->prev = f1loop;
+       v2loop->prev = f2loop;
+       
+       f2->loopbase = f2loop;
+       f->loopbase = f1loop;
+       
+       /*validate both loops*/
+       /*I dont know how many loops are supposed to be in each face at this point! FIXME!*/
+       
+       /*go through all of f2's loops and make sure they point to it properly.*/
+       f2len = BME_cycle_length(f2->loopbase);
+       for(i=0, curloop = f2->loopbase; i < f2len; i++, curloop = curloop->next) curloop->f = f2;
+       
+       /*link up the new loops into the new edges radial*/
+       BME_radial_append(e, f1loop);
+       BME_radial_append(e, f2loop);
+       
+       
+       f2->len = f2len;
+       
+       f1len = BME_cycle_length(f->loopbase);
+       f->len = f1len;
+       
+       if(rl) *rl = f2loop;
+       return f2;
+}
+
+
+/**
+ *                     BME_JEKV
+ *
+ *     JOIN EDGE KILL VERT:
+ *     Takes a an edge and pointer to one of its vertices and collapses
+ *     the edge on that vertex.
+ *     
+ *     Before:             OE      KE
+ *                      ------- -------
+ *               |     ||      |
+ *                             OV     KV      TV
+ *
+ *
+ *   After:             OE      
+ *                      ---------------
+ *               |             |
+ *                             OV             TV
+ *
+ *
+ *     Restrictions:
+ *     KV is a vertex that must have a valance of exactly two. Furthermore
+ *  both edges in KV's disk cycle (OE and KE) must be unique (no double
+ *  edges).
+ *
+ *     It should also be noted that this euler has the possibility of creating
+ *     faces with just 2 edges. It is up to the caller to decide what to do with
+ *  these faces.
+ *
+ *  Returns -
+ *     1 for success, 0 for failure.
+ */
+int BME_JEKV(BME_Mesh *bm, BME_Edge *ke, BME_Vert *kv)
+{
+       BME_Edge *oe;
+       BME_Vert *ov, *tv;
+       BME_CycleNode *diskbase;
+       BME_Loop *killoop,*nextl;
+       int len,radlen=0, halt = 0, i, valance1, valance2,edok;
+       
+       if(BME_vert_in_edge(ke,kv) == 0) return 0;
+       diskbase = BME_disk_getpointer(kv->edge, kv);
+       len = BME_cycle_length(diskbase);
+       
+       if(len == 2){
+               oe = BME_disk_nextedge(ke, kv);
+               tv = BME_edge_getothervert(ke, kv);
+               ov = BME_edge_getothervert(oe, kv);             
+               halt = BME_verts_in_edge(kv, tv, oe); //check for double edges
+               
+               if(halt) return 0;
+               else{
+                       
+                       /*For verification later, count valance of ov and tv*/
+                       diskbase = BME_disk_getpointer(ov->edge, ov);
+                       valance1 = BME_cycle_length(diskbase);
+                       diskbase = BME_disk_getpointer(tv->edge, tv);
+                       valance2 = BME_cycle_length(diskbase);
+                       
+                       /*remove oe from kv's disk cycle*/
+                       BME_disk_remove_edge(oe,kv);
+                       /*relink oe->kv to be oe->tv*/
+                       BME_edge_swapverts(oe, kv, tv);
+                       /*append oe to tv's disk cycle*/
+                       BME_disk_append_edge(oe, tv);
+                       /*remove ke from tv's disk cycle*/
+                       BME_disk_remove_edge(ke, tv);
+               
+                       /*deal with radial cycle of ke*/
+                       if(ke->loop){
+                               /*first step, fix the neighboring loops of all loops in ke's radial cycle*/
+                               radlen = BME_cycle_length(&(ke->loop->radial));
+                               for(i=0,killoop = ke->loop; i<radlen; i++, killoop = BME_radial_nextloop(killoop)){
+                                       /*relink loops and fix vertex pointer*/
+                                       killoop->next->prev = killoop->prev;
+                                       killoop->prev->next = killoop->next;
+                                       if(killoop->next->v == kv) killoop->next->v = tv;
+                                       
+                                       /*fix len attribute of face*/
+                                       killoop->f->len--;
+                                       if(killoop->f->loopbase == killoop) killoop->f->loopbase = killoop->next;
+                               }
+                               /*second step, remove all the hanging loops attached to ke*/
+                               killoop = ke->loop;
+                               radlen = BME_cycle_length(&(ke->loop->radial));
+                               i=0;
+                               while(i<radlen){
+                                       nextl = killoop->radial.next->data;
+                                       BME_free_loop(bm, killoop);
+                                       killoop = nextl;
+                                       i++;
+                               }       
+                               /*Validate radial cycle of oe*/
+                               edok = BME_cycle_validate(radlen,&(oe->loop->radial));
+                               
+                       }
+                       
+                       /*Validate disk cycles*/
+                       diskbase = BME_disk_getpointer(ov->edge,ov);
+                       edok = BME_cycle_validate(valance1, diskbase);
+                       if(!edok) BME_error();
+                       diskbase = BME_disk_getpointer(tv->edge,tv);
+                       edok = BME_cycle_validate(valance2, diskbase);
+                       if(!edok) BME_error();
+                       
+                       /*Validate loop cycle of all faces attached to oe*/
+                       for(i=0,nextl = oe->loop; i<radlen; i++, nextl = BME_radial_nextloop(nextl)){
+                               edok = BME_cycle_validate(nextl->f->len,nextl->f->loopbase);
+                               if(!edok) BME_error();
+                       }
+                       /*deallocate edge*/
+                       BLI_remlink(&(bm->edges), ke);
+                       BME_free_edge(bm, ke);
+                       /*deallocate vertex*/
+                       BLI_remlink(&(bm->verts), kv);
+                       BME_free_vert(bm, kv);  
+                       return 1;
+               }
+       }
+       return 0;
+}
+
+
+/**
+ *                     BME_loop_reverse
+ *
+ *     FLIP FACE EULER
+ *
+ *     Changes the winding order of a face from CW to CCW or vice versa.
+ *     This euler is a bit peculiar in compairson to others as it is its
+ *     own inverse.
+ *
+ *     TODO: reinsert validation code.
+ *
+ *  Returns -
+ *     1 for success, 0 for failure.
+ */
+
+int BME_loop_reverse(BME_Mesh *bm, BME_Poly *f){
+       BME_Loop *l = f->loopbase, *curloop, *oldprev, *oldnext;
+       BME_Edge **elist;
+       int i, j, edok, len = 0;
+
+       len = BME_cycle_length(l);
+       elist = MEM_callocN(sizeof(BME_Edge *)*len, "BME Loop Reverse edge array");
+       
+       for(i=0, curloop = l; i< len; i++, curloop=curloop->next){
+               BME_radial_remove_loop(curloop, curloop->e);
+               curloop->e->eflag1 = 0;
+               elist[i] = curloop->e;
+       }
+       
+       /*actually reverse the loop. This belongs in BME_cycle_reverse!*/
+       for(i=0, curloop = l; i < len; i++){
+               oldnext = curloop->next;
+               oldprev = curloop->prev;
+               curloop->next = oldprev;
+               curloop->prev = oldnext;
+               curloop = oldnext;
+       }
+
+       if(len == 2){ //two edged face
+               //do some verification here!
+               l->e = elist[0];
+               l->next->e = elist[1];
+       }
+       else{
+               for(i=0, curloop = l; i < len; i++, curloop = curloop->next){
+                       edok = 0;
+                       for(j=0; j < len; j++){
+                               edok = BME_verts_in_edge(curloop->v, curloop->next->v, elist[j]);
+                               if(edok){
+                                       curloop->e = elist[j];
+                                       break;
+                               }
+                       }
+               }
+       }
+       /*rebuild radial*/
+       for(i=0, curloop = l; i < len; i++, curloop = curloop->next){
+               BME_radial_append(curloop->e, curloop);
+               //radok = BME_cycle_validate(curloop->e->tmp.l, &(curloop->radial));
+               //if(!radok || curloop->e->loop == NULL) BME_error();
+       }
+       MEM_freeN(elist);
+       return 1;
+}
+
+/**
+ *                     BME_JFKE
+ *
+ *     JOIN FACE KILL EDGE:
+ *     
+ *     Takes two faces joined by a single 2-manifold edge and fuses them togather.
+ *     The edge shared by the faces must not be connected to any other edges which have
+ *     Both faces in its radial cycle
+ *
+ *     Examples:
+ *     
+ *        A                   B
+ *      ----------           ----------
+ *      |                |           |        | 
+ *      |   f1   |           |   f1   |
+ *     v1========v2 = Ok!    v1==V2==v3 == Wrong!
+ *      |   f2   |           |   f2   |
+ *      |        |           |        |
+ *      ----------           ---------- 
+ *
+ *     In the example A, faces f1 and f2 are joined by a single edge, and the euler can safely be used.
+ *     In example B however, f1 and f2 are joined by multiple edges and will produce an error. The caller
+ *     in this case should call BME_JEKV on the extra edges before attempting to fuse f1 and f2.
+ *
+ *     Also note that the order of arguments decides whether or not certain per-face attributes are present
+ *     in the resultant face. For instance vertex winding, material index, smooth flags, ect are inherited
+ *     from f1, not f2.
+ *
+ *  Returns -
+ *     A BME_Poly pointer
+*/
+
+BME_Poly *BME_JFKE(BME_Mesh *bm, BME_Poly *f1, BME_Poly *f2, BME_Edge *e)
+{
+       
+       BME_Loop *curloop, *f1loop=NULL, *f2loop=NULL;
+       int loopok = 0, newlen = 0,i, f1len=0, f2len=0, radlen=0, valance1,valance2,edok;
+       
+       if(f1->holes.first || f2->holes.first) return NULL; //dont operate on faces with holes. Not best solution but tolerable.
+       if(f1 == f2) return NULL; //can't join a face to itself
+       /*verify that e is in both f1 and f2*/
+       f1len = BME_cycle_length(f1->loopbase);
+       f2len = BME_cycle_length(f2->loopbase);
+       for(i=0, curloop = f1->loopbase; i < f1len; i++, curloop = curloop->next){
+               if(curloop->e == e){ 
+                       f1loop = curloop;
+                       break;
+               }
+       }
+       for(i=0, curloop = f2->loopbase; i < f2len; i++, curloop = curloop->next){
+               if(curloop->e==e){
+                       f2loop = curloop;
+                       break;
+               }
+       }
+       if(!(f1loop && f2loop)) return NULL;
+       
+       /*validate that edge is 2-manifold edge*/
+       radlen = BME_cycle_length(&(f1loop->radial));
+       if(radlen != 2) return NULL;
+
+       /*validate direction of f2's loop cycle is compatible.*/
+       if(f1loop->v == f2loop->v) return NULL;
+       
+       /*
+               Finally validate that for each face, each vertex has another edge in its disk cycle that is 
+               not e, and not shared.
+       */
+       if(BME_radial_find_face(f1loop->next->e,f2)) return NULL;
+       if(BME_radial_find_face(f1loop->prev->e,f2)) return NULL;
+       if(BME_radial_find_face(f2loop->next->e,f1)) return NULL;
+       if(BME_radial_find_face(f2loop->prev->e,f1)) return NULL;
+       
+       /*join the two loops*/
+       f1loop->prev->next = f2loop->next;
+       f2loop->next->prev = f1loop->prev;
+       
+       f1loop->next->prev = f2loop->prev;
+       f2loop->prev->next = f1loop->next;
+       
+       /*if f1loop was baseloop, give f1loop->next the base.*/
+       if(f1->loopbase == f1loop) f1->loopbase = f1loop->next;
+       
+       /*validate the new loop*/
+       loopok = BME_cycle_validate((f1len+f2len)-2, f1->loopbase);
+       if(!loopok) BME_error();
+       
+       /*make sure each loop points to the proper face*/
+       newlen = BME_cycle_length(f1->loopbase);
+       for(i = 0, curloop = f1->loopbase; i < newlen; i++, curloop = curloop->next) curloop->f = f1;
+       
+       f1->len = newlen;
+       
+       edok = BME_cycle_validate(f1->len, f1->loopbase);
+       if(!edok) BME_error();
+       
+       /*remove edge from the disk cycle of its two vertices.*/
+       BME_disk_remove_edge(f1loop->e, f1loop->e->v1);
+       BME_disk_remove_edge(f1loop->e, f1loop->e->v2);
+       
+       /*deallocate edge and its two loops as well as f2*/
+       BLI_remlink(&(bm->edges), f1loop->e);
+       BLI_remlink(&(bm->polys), f2);
+       BME_free_edge(bm, f1loop->e);
+       BME_free_loop(bm, f1loop);
+       BME_free_loop(bm, f2loop);
+       BME_free_poly(bm, f2);  
+       return f1;
+}
+
+/**
+ *                     BME_MEKL
+ *
+ *     MAKE EDGE KILL LOOP:
+ *     
+ *     Bridges a perphiary loop of a face with an internal loop
+ *
+ *     Examples:
+ *
+ *     ----------------                ----------------
+ *     |      f1      |                |      f1      |
+ *     |     -----    |                |     -----    |
+ *     |     |   |    |                |     |   |    |
+ *     X     X   |    |        X-----X   |    |
+ *     |     |   |    |                |     |   |    |
+ *     |     -----    |                |     -----    |
+ *     |                          |            |                          |
+ *     ----------------                ----------------
+ *
+ *
+ *  Returns -
+ *     A BME_Poly pointer
+ */
+
+/**
+ *                     BME_KEML
+ *
+ *     KILL EDGE MAKE LOOP:
+ *     
+ *     Kills an edge and splits the loose loops off into an internal loop
+ *
+ *     Examples:
+ *
+ *     ----------------                ----------------
+ *     |      f1      |                |      f1      |
+ *     |     -----    |                |     -----    |
+ *     |     |   |    |                |     |   |    |
+ *     X ----X   |    |        X     X   |    |
+ *     |     |   |    |                |     |   |    |
+ *     |     -----    |                |     -----    |
+ *     |                          |            |                          |
+ *     ----------------                ----------------
+ *
+ *     The tool author should take care to realize that although a face may have 
+ *     a hole in its topology, that hole may be filled with one or many other faces.
+ *     Regardless, this does not imply a parent child relationship.
+ *
+ *
+ *  Returns -
+ *     A BME_Poly pointer
+ */
+
diff --git a/source/blender/bmesh/BME_mesh.c b/source/blender/bmesh/BME_mesh.c
new file mode 100644 (file)
index 0000000..153a102
--- /dev/null
@@ -0,0 +1,317 @@
+/**
+ * BME_mesh.c    jan 2007
+ *
+ *     BMesh mesh level functions.
+ *
+ * $Id: BME_eulers.c,v 1.00 2007/01/17 17:42:01 Briggs Exp $
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this. 
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2007 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Geoffrey Bantle.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_listBase.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_mesh_types.h"
+#include "DNA_object_types.h"
+#include "DNA_scene_types.h"
+
+
+#include "BKE_utildefines.h"
+#include "BKE_bmesh.h"
+#include "BKE_global.h"
+#include "BKE_depsgraph.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_editVert.h"
+#include "BIF_editmesh.h"
+#include "BIF_space.h"
+#include "editmesh.h"
+#include "bmesh_private.h"
+#include "mydevice.h"
+
+#include "BSE_edit.h"
+
+
+/*     
+ *     BME MAKE MESH
+ *
+ *  Allocates a new BME_Mesh structure
+*/
+
+BME_Mesh *BME_make_mesh(void){
+       BME_Mesh *bm = MEM_callocN(sizeof(BME_Mesh),"BMesh");
+       return bm;
+}
+
+/*     
+ *     BME FREE MESH
+ *
+ *     Frees a BME_Mesh structure.
+*/
+
+void BME_free_mesh(BME_Mesh *bm)
+{
+       BME_Poly *bf, *nextf;
+       BME_Edge *be, *nexte;
+       BME_Vert *bv, *nextv;
+       BME_CycleNode *loopref;
+       int loopcount=0;
+       
+       /*destroy polygon data*/
+       bf = bm->polys.first;
+       while(bf){
+               nextf = bf->next;
+               BLI_remlink(&(bm->polys), bf);
+               if(bf->holes.first)
+                       BLI_freelistN(&(bf->holes));
+               BME_free_poly(bm, bf);
+               
+               bf = nextf;
+       }
+       /*destroy edge data*/
+       be = bm->edges.first;
+       while(be){
+               nexte = be->next;
+               BLI_remlink(&(bm->edges), be);
+               BME_free_edge(bm, be);
+               be = nexte;
+       }
+       /*destroy vert data*/
+       bv = bm->verts.first;
+       while(bv){
+               nextv = bv->next;
+               BLI_remlink(&(bm->verts), bv);
+               BME_free_vert(bm, bv);
+               bv = nextv; 
+       }
+
+       for(loopref=bm->loops.first;loopref;loopref=loopref->next) BME_delete_loop(bm,loopref->data);
+       BLI_freelistN(&(bm->loops));
+       MEM_freeN(bm);
+}
+
+/*     
+ *     BME COPY MESH
+ *
+ *     Copies a BME_Mesh structure.
+ *
+ *  This is probably more low level than any mesh manipulation routine should be
+ *  and somewhat violates the rule about modifying/creating mesh structures outside
+ *  of the euler API. Regardless, its much more effecient than rebuilding the mesh
+ *  from scratch. 
+*/
+
+BME_Mesh *BME_copy_mesh(BME_Mesh *bm){
+       
+       BME_Vert *v, *cv;
+       BME_Edge *e, *ce;
+       BME_Poly *f, *cf;
+       BME_Loop *l, *cl;
+       BME_Mesh *meshcopy;
+       meshcopy = BME_make_mesh();
+       
+
+       return meshcopy;
+}
+
+/*     
+ *     BME MODEL BEGIN AND END
+ *
+ *     These two functions represent the 'point of entry' for tools. Every BMesh tool
+ *     must begin with a call to BME_model_end() and finish with a call to BME_model_end().
+ *     No modification of mesh data is allowed except in between these two calls.
+ *
+ *     TODO 
+ *             FOR BME_MODEL_BEGIN:
+ *             -integrate euler undo system.
+ *             -make full copy of structure to safely recover from errors.
+ *             -accept a toolname string.
+ *             -accept param to turn off full copy if just selection tool. (perhaps check for this in eulers...)
+ *
+ *             BME_MODEL_END:
+ *             -full mesh validation if debugging turned on
+ *             -free structure copy or use it to restore.
+ *             -do euler undo push.
+ *
+*/
+
+int BME_model_begin(BME_Mesh *bm){
+       if(bm->lock) return 0;
+       bm->lock = 1;
+       bm->backup = BME_copy_mesh(bm);
+       return 1;
+}
+
+void BME_model_end(BME_Mesh *bm){
+       BME_Mesh *badmesh;
+       int meshok,backupok, totvert, totedge, totpoly, totloop;
+
+       totvert = BLI_countlist(&(bm->verts));
+       totedge = BLI_countlist(&(bm->edges));
+       totpoly = BLI_countlist(&(bm->polys));
+       totloop = BLI_countlist(&(bm->loops));
+       
+       if(bm->totvert!=totvert || bm->totedge!=totedge || bm->totpoly!=totpoly || bm->totloop!=totloop)
+               BME_error();
+       
+       meshok = BME_validate_mesh(bm, 1);
+       if(!meshok){
+               printf("Warning, Mesh failed validation, restoring from backup");
+               badmesh = bm;
+               bm= badmesh->backup;
+               bm->backup = badmesh;
+               backupok = BME_validate_mesh(bm,1);
+               if(!backupok) printf("Backup corrupted too, Briggs did something stupid!");
+       }
+       BME_free_mesh(bm->backup);
+       bm->lock = 0;
+}
+
+
+/*     
+ *     BME VALIDATE MESH
+ *
+ *     There are several levels of validation for meshes. At the 
+ *  Euler level, some basic validation is done to local topology.
+ *  To catch more subtle problems however, BME_validate_mesh() is 
+ *  called by BME_model_end() whenever a tool is done executing.
+ *  The purpose of this function is to insure that during the course 
+ *  of tool execution that nothing has been done to invalidate the 
+ *  structure, and if it has, provide a way of reporting that so that
+ *  we can restore the proper structure from a backup. Since a full mesh
+ *  validation would be too expensive, this is presented as a compromise.
+ *
+ *     TODO 
+ *     
+ *     -Add validation for hole loops (which are experimental anyway)
+ *     -Write a full mesh validation function for debugging purposes.
+ */
+
+#define VHALT(halt) {BME_error(); if(halt) return 0;}
+
+int BME_validate_mesh(struct BME_Mesh *bm, int halt)
+{
+       BME_Vert *v;
+       BME_Edge *e;
+       BME_Poly *f;
+       BME_Loop *l;
+       BME_CycleNode *diskbase;
+       int i, ok;
+       
+       /*Simple edge verification*/
+       for(e=bm->edges.first; e; e=e->next){
+               if(e->v1 == e->v2) VHALT(halt);
+               /*validate e->d1.data and e->d2.data*/
+               if(e->d1.data != e || e->d2.data != e) VHALT(halt);
+               /*validate e->loop->e*/
+               if(e->loop){
+                       if(e->loop->e != e) VHALT(halt);
+               }
+       }
+       
+       /*calculate disk cycle lengths*/
+       for(v=bm->verts.first; v; v=v->next) v->tflag1 = v->tflag2 = 0;
+       for(e=bm->edges.first; e; e=e->next){ 
+               e->v1->tflag1++;
+               e->v2->tflag1++;
+       }
+       /*Validate vertices and disk cycle*/
+       for(v=bm->verts.first; v; v=v->next){
+               /*validate v->edge pointer*/
+               if(v->tflag1){
+                       if(v->edge){
+                               ok = BME_vert_in_edge(v->edge,v);
+                               if(!ok) VHALT(halt);
+                               /*validate length of disk cycle*/
+                               diskbase = BME_disk_getpointer(v->edge, v);
+                               ok = BME_cycle_validate(v->tflag1, diskbase);
+                               if(!ok) VHALT(halt);
+                               /*validate that each edge in disk cycle contains V*/
+                               for(i=0, e=v->edge; i < v->tflag1; i++, e = BME_disk_nextedge(e,v)){
+                                       ok = BME_vert_in_edge(e, v);
+                                       if(!ok) VHALT(halt);
+                               }
+                       }
+                       else VHALT(halt);
+               }
+       }
+       /*validate edges*/
+       for(e=bm->edges.first; e; e=e->next){
+               /*seperate these into BME_disk_hasedge (takes pointer to edge)*/
+               /*search v1 disk cycle for edge*/
+               ok = BME_disk_hasedge(e->v1,e);
+               if(!ok) VHALT(halt);
+               /*search v2 disk cycle for edge*/
+               ok = BME_disk_hasedge(e->v2,e);
+               if(!ok) VHALT(halt);
+       }
+       
+       for(e=bm->edges.first; e; e=e->next) e->tflag2 = 0; //store incident faces
+       /*Validate the loop cycle integrity.*/
+       for(f=bm->polys.first; f; f=f->next){
+               ok = BME_cycle_length(f->loopbase);
+               if(ok > 1){
+                       f->tflag1 = ok;
+               }
+               else VHALT(halt);
+               for(i=0, l=f->loopbase; i < f->tflag1; i++, l=l->next){
+                       /*verify loop->v pointers*/
+                       ok = BME_verts_in_edge(l->v, l->next->v, l->e);
+                       if(!ok) VHALT(halt);
+                       /*verify radial node data pointer*/
+                       if(l->radial.data != l) VHALT(halt);
+                       /*validate l->e->loop poitner*/
+                       if(l->e->loop == NULL) VHALT(halt);
+                       /*validate l->f pointer*/
+                       if(l->f != f) VHALT(halt);
+                       /*see if l->e->loop is actually in radial cycle*/
+                       
+                       l->e->tflag2++;
+                }
+       }
+       
+       /*validate length of radial cycle*/
+       for(e=bm->edges.first; e; e=e->next){
+               if(e->loop){
+                       ok = BME_cycle_validate(e->tflag2,&(e->loop->radial));
+                       if(!ok) VHALT(halt);
+               }
+       }
+       
+       /*if we get this far, pretty safe to return 1*/
+       return 1;
+}
+
+/*     Currently just a convient place for a breakpoint.
+       Probably should take an error string
+*/
+void BME_error(void){
+       printf("BME modelling error!");
+}
diff --git a/source/blender/bmesh/BME_structure.c b/source/blender/bmesh/BME_structure.c
new file mode 100644 (file)
index 0000000..6566fd6
--- /dev/null
@@ -0,0 +1,606 @@
+/**
+ * BME_structure.c    jan 2007
+ *
+ *     Low level routines for manipulating the BMesh structure.
+ *
+ * $Id: BME_structure.c,v 1.00 2007/01/17 17:42:01 Briggs Exp $
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this. 
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2007 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Geoffrey Bantle.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+
+#include <limits.h>
+#include "MEM_guardedalloc.h"
+
+#include "DNA_listBase.h"
+#include "BKE_utildefines.h"
+#include "BKE_bmesh.h"
+#include "BLI_blenlib.h"
+#include "BLI_linklist.h"
+#include "BLI_GHash.h"
+
+/**
+ *     MISC utility functions.
+ *
+ */
+int BME_vert_in_edge(BME_Edge *e, BME_Vert *v){
+       if(e->v1 == v || e->v2 == v) return 1;
+       return 0;
+}
+int BME_verts_in_edge(BME_Vert *v1, BME_Vert *v2, BME_Edge *e){
+       if(e->v1 == v1 && e->v2 == v2) return 1;
+       else if(e->v1 == v2 && e->v2 == v1) return 1;
+       return 0;
+}
+
+BME_Vert *BME_edge_getothervert(BME_Edge *e, BME_Vert *v){
+       if(e->v1 == v) return e->v2;
+       else if(e->v2 == v) return e->v1;
+       return NULL;
+}
+
+int BME_edge_swapverts(BME_Edge *e, BME_Vert *orig, BME_Vert *new){
+       if(e->v1 == orig){ 
+               e->v1 = new;
+               e->d1.next = NULL;
+               e->d1.prev = NULL;
+               return 1;
+       }
+       else if(e->v2 == orig){
+               e->v2 = new;
+               e->d2.next = NULL;
+               e->d2.prev = NULL;
+               return 1;
+       }
+       return 0;
+}
+
+/**
+ *     ALLOCATION/DEALLOCATION FUNCTIONS
+ */
+
+BME_Vert *BME_addvertlist(BME_Mesh *bm, BME_Vert *example){
+       BME_Vert *v=NULL;
+       v = MEM_callocN(sizeof(BME_Vert), "BME Vertex");
+       BLI_addtail(&(bm->verts), v);
+       v->EID = bm->nextv;
+       bm->nextv++;
+       bm->totvert++;
+
+       if(example)
+               VECCOPY(v->co,example->co);
+/*     if(example)
+               BME_CustomData_copy_data(&bm->vdata, &bm->vdata, example->data, &v->data);
+       else
+               BME_CustomData_set_default(&bm->vdata, &v->data);
+*/     
+       return v;
+}
+BME_Edge *BME_addedgelist(BME_Mesh *bm, BME_Vert *v1, BME_Vert *v2, BME_Edge *example){
+       BME_Edge *e=NULL;
+       e = MEM_callocN(sizeof(BME_Edge), "BME_Edge");
+       e->v1 = v1;
+       e->v2 = v2;
+       e->d1.data = e;
+       e->d2.data = e;
+       e->EID = bm->nexte;
+       bm->nexte++;
+       bm->totedge++;
+       BLI_addtail(&(bm->edges), e);
+       
+/*     if(example)
+               BME_CustomData_copy_data(&bm->edata, &bm->edata, example->data, &e->data);
+       else
+               BME_CustomData_set_default(&bm->edata, &e->data);
+*/
+
+       return e;
+}
+BME_Loop *BME_create_loop(BME_Mesh *bm, BME_Vert *v, BME_Edge *e, BME_Poly *f, BME_Loop *example){
+       /*allocate a BME_Loop and add it to the loophash*/
+       BME_Loop *l=NULL;
+       BME_CycleNode *loopnode = MEM_callocN(sizeof(BME_CycleNode),"BME Loop Reference");
+       l = MEM_callocN(sizeof(BME_Loop), "BME_Loop");
+       l->radial.data = l;
+       l->v = v;
+       l->e = e;
+       l->f = f;
+       l->EID = bm->nextl;
+       l->gref = loopnode;
+       loopnode->data = l;
+       BLI_addtail(&(bm->loops),loopnode);
+       bm->nextl++;
+       bm->totloop++;
+       
+
+/*     if(example)
+               BME_CustomData_copy_data(&bm->ldata, &bm->ldata, example->data, &l->data);
+       else
+               BME_CustomData_set_default(&bm->ldata, &l->data);
+*/
+       return l;
+}
+
+BME_Poly *BME_addpolylist(BME_Mesh *bm, BME_Poly *example){
+       BME_Poly *f = NULL;
+       f= MEM_callocN(sizeof(BME_Poly),"BME_Poly");
+       BLI_addtail(&(bm->polys),f);
+       f->EID = bm->nextp;
+       bm->nextp++;
+       bm->totpoly++;
+
+/*     if(example)
+               BME_CustomData_copy_data(&bm->pdata, &bm->pdata, example->data, &f->data);
+       else
+               BME_CustomData_set_default(&bm->pdata, &f->data);
+*/
+
+       return f;
+}
+
+/*     free functions dont do much *yet*. When per-vertex, per-edge and per-face/faceloop
+       data is added though these will be needed.
+*/
+void BME_free_vert(BME_Mesh *bm, BME_Vert *v){
+       bm->totvert--;
+       //BME_CustomData_free_block(&bm->vdata, &v->data);
+       MEM_freeN(v);
+}
+void BME_free_edge(BME_Mesh *bm, BME_Edge *e){
+       bm->totedge--;
+       //BME_CustomData_free_block(&bm->edata, &e->data);
+       MEM_freeN(e);
+}
+void BME_free_poly(BME_Mesh *bm, BME_Poly *f){
+       bm->totpoly--;
+       //BME_CustomData_free_block(&bm->pdata, &f->data);
+       MEM_freeN(f);
+}
+void BME_delete_loop(BME_Mesh *bm, BME_Loop *l){
+       bm->totloop--;
+       //BME_CustomData_free_block(&bm->ldata, &l->data);
+       MEM_freeN(l);
+}
+void BME_free_loop(BME_Mesh *bm, BME_Loop *l){
+       BME_CycleNode *loopref = l->gref;
+       BLI_freelinkN(&(bm->loops),loopref);
+       BME_delete_loop(bm,l);
+}
+
+
+/**
+ *     BMESH CYCLES
+ *
+ *     Cycles are circular doubly linked lists that form the basis of adjacency
+ *     information in the BME modeller. Full adjacency relations can be derived
+ *     from examining these cycles very quickly. Although each cycle is a double
+ *  circular linked list, each one is considered to have a 'base' or 'head',
+ *     and care must be taken by Euler code when modifying the contents of a cycle.
+ *
+ *     The contents of this file are split into two parts. First there are the 
+ *     BME_cycle family of functions which are generic circular double linked list 
+ *     procedures. The second part contains higher level procedures for supporting 
+ *     modification of specific cycle types.
+ *
+ *     The three cycles explicitly stored in the BMesh data structure are as follows:
+ *
+ *     1: The Disk Cycle - A circle of edges around a vertex
+ *     Base: vertex->edge pointer.
+ *        
+ *     This cycle is the most complicated in terms of its structure. Each BME_Edge contains    
+ *        two BME_CycleNode structures to keep track of that edge's membership in the disk cycle
+ *        of each of its vertices. However for any given vertex it may be the first in some edges
+ *        in its disk cycle and the second for others. The BME_disk_XXX family of functions contain
+ *        some nice utilities for navigating disk cycles in a way that hides this detail from the 
+ *        tool writer.
+ *
+ *             Note that the disk cycle is completley independant from face data. One advantage of this
+ *             is that wire edges are fully integrated into the topology database. Another is that the 
+ *         the disk cycle has no problems dealing with non-manifold conditions involving faces.
+ *
+ *             Functions relating to this cycle:
+ *             
+ *                     BME_disk_append_edge
+ *                     BME_disk_remove_edge
+ *                     BME_disk_nextedge
+ *                     BME_disk_getpointer
+ *
+ *     2: The Radial Cycle - A circle of face edges (BME_Loop) around an edge
+ *        Base: edge->loop->radial structure.
+ *
+ *             The radial cycle is similar to the radial cycle in the radial edge data structure.*
+ *             Unlike the radial edge however, the radial cycle does not require a large amount of memory 
+ *             to store non-manifold conditions since BMesh does not keep track of region/shell
+ *             information.
+ *             
+ *             Functions relating to this cycle:
+ *                     
+ *                     BME_radial_append
+ *                     BME_radial_remove_loop
+ *                     BME_radial_nextloop
+ *                     BME_radial_find_face
+ *             
+ *
+ *     3: The Loop Cycle - A circle of face edges around a polygon.
+ *     Base: polygon->loopbase.
+ *
+ *        The loop cycle keeps track of a faces vertices and edges. It should be noted that the
+ *     direction of a loop cycle is either CW or CCW depending on the face normal, and is 
+ *     not oriented to the faces editedges. 
+ *
+ *             Functions relating to this cycle:
+ *             
+ *                     BME_cycle_XXX family of functions.
+ *
+ *     
+ *     Note that the order of elements in all cycles except the loop cycle is undefined. This 
+ *  leads to slightly increased seek time for deriving some adjacency relations, however the 
+ *  advantage is that no intrinsic properties of the data structures are dependant upon the 
+ *  cycle order and all non-manifold conditions are represented trivially.
+ *
+*/
+void BME_cycle_append(void *h, void *nt)
+{
+       BME_CycleNode *oldtail, *head, *newtail;
+       
+       head = (BME_CycleNode*)h;
+       newtail = (BME_CycleNode*)nt;
+       
+       if(head->next == NULL){
+               head->next = newtail;
+               head->prev = newtail;
+               newtail->next = head;
+               newtail->prev = head;
+       }
+       else{
+               oldtail = head->prev;
+               oldtail->next = newtail;
+               newtail->next = head;
+               newtail->prev = oldtail;
+               head->prev = newtail;
+               
+       }
+}
+
+/**
+ *                     BME_cycle_length
+ *
+ *     Count the nodes in a cycle.
+ *
+ *  Returns -
+ *     Integer
+ */
+
+int BME_cycle_length(void *h){
+       
+       int len = 0;
+       BME_CycleNode *head, *curnode;
+       head = (BME_CycleNode*)h;
+       
+       if(head){ 
+               len = 1;
+               for(curnode = head->next; curnode != head; curnode=curnode->next){ 
+                       if(len == INT_MAX){ //check for infinite loop/corrupted cycle
+                                       return -1;
+                       }
+                       len++;
+               }
+       }
+       return len;
+}
+
+
+/**
+ *                     BME_cycle_remove
+ *
+ *     Removes a node from a cycle.
+ *
+ *  Returns -
+ *     1 for success, 0 for failure.
+ */
+
+int BME_cycle_remove(void *h, void *remn)
+{
+       int i, len;
+       BME_CycleNode *head, *remnode, *curnode;
+       
+       head = (BME_CycleNode*)h;
+       remnode = (BME_CycleNode*)remn;
+       len = BME_cycle_length(h);
+       
+       if(len == 1 && head == remnode){
+               head->next = NULL;
+               head->prev = NULL;
+               return 1;
+       }
+       else{
+               for(i=0, curnode = head; i < len; curnode = curnode->next){
+                       if(curnode == remnode){
+                               remnode->prev->next = remnode->next;
+                               remnode->next->prev = remnode->prev;
+                               /*zero out remnode pointers, important!*/
+                               //remnode->next = NULL;
+                               //remnode->prev = NULL;
+                               return 1;
+               
+                       }
+               }
+       }
+       return 0;
+}
+
+/**
+ *                     BME_cycle_validate
+ *
+ *     Validates a cycle. Takes as an argument the expected length of the cycle and
+ *     a pointer to the cycle head or base.
+ *
+ *
+ *  Returns -
+ *     1 for success, 0 for failure.
+ */
+
+int BME_cycle_validate(int len, void *h){
+       int i;
+       BME_CycleNode *curnode, *head;
+       head = (BME_CycleNode*)h;
+       
+       /*forward validation*/
+       for(i = 0, curnode = head; i < len; i++, curnode = curnode->next);
+       if(curnode != head) return 0;
+       
+       /*reverse validation*/
+       for(i = 0, curnode = head; i < len; i++, curnode = curnode->prev);
+       if(curnode != head) return 0;
+       
+       return 1;
+}
+
+/*Begin Disk Cycle routines*/
+
+/**
+ *                     BME_disk_nextedge
+ *
+ *     Find the next edge in a disk cycle
+ *
+ *  Returns -
+ *     Pointer to the next edge in the disk cycle for the vertex v.
+ */
+BME_Edge *BME_disk_nextedge(BME_Edge *e, BME_Vert *v)
+{      
+       if(BME_vert_in_edge(e, v)){
+               if(e->v1 == v) return e->d1.next->data;
+               else if(e->v2 == v) return e->d2.next->data;
+       }
+       return NULL;
+}
+
+/**
+ *                     BME_disk_getpointer
+ *
+ *     Given an edge and one of its vertices, find the apporpriate CycleNode
+ *
+ *  Returns -
+ *     Pointer to BME_CycleNode.
+ */
+BME_CycleNode *BME_disk_getpointer(BME_Edge *e, BME_Vert *v){
+       /*returns pointer to the cycle node for the appropriate vertex in this disk*/
+       if(e->v1 == v) return &(e->d1);
+       else if (e->v2 == v) return &(e->d2);
+       return NULL;
+}
+
+/**
+ *                     BME_disk_append_edge
+ *
+ *     Appends edge to the end of a vertex disk cycle.
+ *
+ *  Returns -
+ *     1 for success, 0 for failure
+ */
+
+int BME_disk_append_edge(BME_Edge *e, BME_Vert *v)
+{ 
+       
+       BME_CycleNode *base, *tail;
+       
+       if(BME_vert_in_edge(e, v) == 0) return 0; /*check to make sure v is in e*/
+       
+       /*check for loose vert first*/
+       if(v->edge == NULL){
+               v->edge = e;
+               base = tail = BME_disk_getpointer(e, v);
+               BME_cycle_append(base, tail); /*circular reference is ok!*/
+               return 1;
+       }
+       
+       /*insert e at the end of disk cycle and make it the new v->edge*/
+       base = BME_disk_getpointer(v->edge, v);
+       tail = BME_disk_getpointer(e, v);
+       BME_cycle_append(base, tail);
+       return 1;
+}
+
+/**
+ *                     BME_disk_remove_edge
+ *
+ *     Removes an edge from a disk cycle. If the edge to be removed is
+ *     at the base of the cycle, the next edge becomes the new base.
+ *
+ *
+ *  Returns -
+ *     Nothing
+ */
+
+void BME_disk_remove_edge(BME_Edge *e, BME_Vert *v)
+{
+       BME_CycleNode *base, *remnode;
+       BME_Edge *newbase;
+       int len;
+       
+       base = BME_disk_getpointer(v->edge, v);
+       remnode = BME_disk_getpointer(e, v);
+       
+       /*first deal with v->edge pointer...*/
+       len = BME_cycle_length(base);
+       if(len == 1) newbase = NULL;
+       else if(v->edge == e) newbase = base->next-> data;
+       else newbase = v->edge;
+       
+       /*remove and rebase*/
+       BME_cycle_remove(base, remnode);
+       v->edge = newbase;
+}
+
+/**
+ *                     BME_disk_next_edgeflag
+ *
+ *     Searches the disk cycle of v, starting with e, for the 
+ *  next edge that has either eflag or tflag.
+ *
+ *     BME_Edge pointer.
+ */
+
+BME_Edge *BME_disk_next_edgeflag(BME_Edge *e, BME_Vert *v, int eflag, int tflag){
+       
+       BME_CycleNode *diskbase;
+       BME_Edge *curedge;
+       int len, ok;
+       
+       if(eflag && tflag) return NULL;
+       
+       ok = BME_vert_in_edge(e,v);
+       if(ok){
+               diskbase = BME_disk_getpointer(e, v);
+               len = BME_cycle_length(diskbase);
+               curedge = BME_disk_nextedge(e,v);
+               while(curedge != e){
+                       if(tflag){
+                               if(curedge->tflag1 == tflag) return curedge;
+                       }
+                       else if(eflag){
+                               if(curedge->eflag1 == eflag) return curedge;
+                       }
+                       curedge = BME_disk_nextedge(curedge, v);
+               }
+       }
+       return NULL;
+}
+
+/**
+ *                     BME_disk_count_edgeflag
+ *
+ *     Counts number of edges in this verts disk cycle which have 
+ *     either eflag or tflag (but not both!)
+ *
+ *  Returns -
+ *     Integer.
+ */
+
+int BME_disk_count_edgeflag(BME_Vert *v, int eflag, int tflag){
+       BME_CycleNode *diskbase;
+       BME_Edge *curedge;
+       int i, len=0, count=0;
+       
+       if(v->edge){
+               if(eflag && tflag) return 0; /*tflag and eflag are reserved for different functions!*/
+               diskbase = BME_disk_getpointer(v->edge, v);
+               len = BME_cycle_length(diskbase);
+               
+               for(i = 0, curedge=v->edge; i<len; i++){
+                       if(tflag){
+                               if(curedge->tflag1 == tflag) count++;
+                       }
+                       else if(eflag){
+                               if(curedge->eflag1 == eflag) count++;
+                       }
+                       curedge = BME_disk_nextedge(curedge, v);
+               }
+       }
+       return count;
+}
+
+int BME_disk_hasedge(BME_Vert *v, BME_Edge *e){
+       BME_CycleNode *diskbase;
+       BME_Edge *curedge;
+       int i, len=0;
+       
+       if(v->edge){
+               diskbase = BME_disk_getpointer(v->edge,v);
+               len = BME_cycle_length(diskbase);
+               
+               for(i = 0, curedge=v->edge; i<len; i++){
+                       if(curedge == e) return 1;
+                       else curedge=BME_disk_nextedge(curedge, v);
+               }
+       }
+       return 0;
+}
+/*end disk cycle routines*/
+
+BME_Loop *BME_radial_nextloop(BME_Loop *l){
+       return (BME_Loop*)(l->radial.next->data);
+}
+
+void BME_radial_append(BME_Edge *e, BME_Loop *l){
+       if(e->loop == NULL) e->loop = l;
+       BME_cycle_append(&(e->loop->radial), &(l->radial));
+}
+
+void BME_radial_remove_loop(BME_Loop *l, BME_Edge *e)
+{
+       BME_Loop *newbase;
+       int len;
+       
+       /*deal with edge->loop pointer*/
+       len = BME_cycle_length(&(e->loop->radial));
+       if(len == 1) newbase = NULL;
+       else if(e->loop == l) newbase = e->loop->radial.next->data;
+       else newbase = e->loop;
+       
+       /*remove and rebase*/
+       BME_cycle_remove(&(e->loop->radial), &(l->radial));
+       e->loop = newbase;
+}
+
+int BME_radial_find_face(BME_Edge *e,BME_Poly *f)
+{
+               
+       BME_Loop *curloop;
+       int i, len;
+       
+       len = BME_cycle_length(&(e->loop->radial));
+       for(i = 0, curloop = e->loop; i < len; i++, curloop = curloop->radial.next->data){
+               if(curloop->f == f) return 1;
+       }
+       return 0;
+}
diff --git a/source/blender/bmesh/BME_tools.c b/source/blender/bmesh/BME_tools.c
new file mode 100644 (file)
index 0000000..2906bc2
--- /dev/null
@@ -0,0 +1,182 @@
+/**
+ * BME_tools.c    jan 2007
+ *
+ *     Functions for changing the topology of a mesh.
+ *
+ * $Id: BME_eulers.c,v 1.00 2007/01/17 17:42:01 Briggs Exp $
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this. 
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2004 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Geoffrey Bantle.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_listBase.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_mesh_types.h"
+
+#include "BKE_utildefines.h"
+#include "BKE_bmesh.h"
+#include "BLI_blenlib.h"
+
+/**
+ *                     BME_dissolve_edge
+ *
+ *     Edge Dissolve Function:
+ *     
+ *     Dissolves a 2-manifold edge by joining it's two faces. if 
+ *     they have opposite windings it first makes them consistent 
+ *     by calling BME_loop_reverse()
+ *
+ *     Returns -
+*/
+
+/**
+ *                     BME_inset_edge
+ *
+ *     Edge Inset Function:
+ *     
+ *     Splits a face in two along an edge and returns the next loop 
+ *
+ *     Returns -
+ *     A BME_Poly pointer.
+ */
+
+BME_Loop *BME_inset_edge(BME_Mesh *bm, BME_Loop *l, BME_Poly *f){
+       BME_Loop *nloop;
+       BME_SFME(bm, f, l->v, l->next->v, &nloop);
+       return nloop->next; 
+}
+
+/**
+ *                     BME_inset_poly
+ *
+ *     Face Inset Tool:
+ *     
+ *     Insets a single face and returns a pointer to the face at the 
+ *     center of the newly created region
+ *
+ *     Returns -
+ *     A BME_Poly pointer.
+ */
+
+#define MIN(a,b) (((a)<(b))?(a):(b))
+#define MAX(a,b) (((a)>(b))?(a):(b))
+
+BME_Poly *BME_inset_poly(BME_Mesh *bm,BME_Poly *f){
+       
+       BME_Vert *v, *killvert;
+       BME_Edge *killedge;
+       BME_Loop *l,*nextloop, *newloop, *killoop, *sloop;
+       BME_CycleNode *loopref;
+       
+       int done,len,i;
+       float max[3],min[3],cent[3]; //center of original face
+       
+       /*get bounding box for face*/
+       VECCOPY(max,f->loopbase->v->co);
+       VECCOPY(min,f->loopbase->v->co);
+       len = f->len;
+       for(i=0,l=f->loopbase;i<len;i++,l=l->next){
+               max[0] = MAX(max[0],l->v->co[0]);
+               max[1] = MAX(max[1],l->v->co[1]);
+               max[2] = MAX(max[2],l->v->co[2]);
+               
+               min[0] = MIN(min[0],l->v->co[0]);
+               min[1] = MIN(min[1],l->v->co[1]);
+               min[2] = MIN(min[2],l->v->co[2]);
+       }
+       
+       cent[0] = (min[0] + max[0]) / 2.0;
+       cent[1] = (min[1] + max[1]) / 2.0;
+       cent[2] = (min[2] + max[2]) / 2.0;
+       
+       
+       
+       /*inset each edge in the polygon.*/
+       len = f->len;
+       for(i=0,l=f->loopbase; i < len; i++){
+               nextloop = l->next;
+               f = BME_SFME(bm,l->f,l->v,l->next->v,NULL);
+               l=nextloop;
+       }
+       
+       /*for each new edge, call SEMV twice on it*/
+       for(i=0,l=f->loopbase; i < len; i++, l=l->next){ 
+               l->tflag1 = 1; //going to store info that this loops edge still needs split
+               l->tflag2 = l->v->tflag1 = l->v->tflag2 = 0; 
+       }
+       
+       len = f->len;
+       for(i=0,l=f->loopbase; i < len; i++){
+               if(l->tflag1){
+                       l->tflag1 = 0;
+                       v= BME_SEMV(bm,l->next->v,l->e,NULL);
+                       VECCOPY(v->co,l->v->co);
+                       l->e->tflag2 =1; //mark for kill with JFKE
+                       v->tflag2 = 1; //mark for kill with JEKV
+                       v->tflag1 = 1; //mark for what?
+                       v= BME_SEMV(bm,l->next->v,l->e,NULL);
+                       VECCOPY(v->co,l->next->next->v->co);
+                       v->tflag1 = 1;
+                       l = l->next->next->next;
+               }
+       }
+       
+       len = f->len;
+       sloop = NULL;
+       for(i=0,l=f->loopbase; i < len; i++,l=l->next){
+               if(l->v->tflag1 && l->next->next->v->tflag1){
+                       sloop = l;
+                       break;
+               }
+       }
+       if(sloop){
+               for(i=0,l=sloop; i < len; i++){
+                       nextloop = l->next->next->next;
+                       f = BME_SFME(bm,f,l->v,l->next->next->v,&killoop);
+                       i+=2;
+                       BME_JFKE(bm,l->f,((BME_Loop*)l->radial.next->data)->f,l->e);
+                       killedge = killoop->e;
+                       killvert = killoop->v;
+                       done = BME_JEKV(bm,killedge,killvert);
+                       if(!done){
+                               printf("whoops!");
+                       }
+                       l=nextloop;
+               }
+       }
+       
+       len = f->len;
+       for(i=0,l=f->loopbase; i < len; i++,l=l->next){
+               l->v->co[0] = (l->v->co[0] + cent[0]) / 2.0;
+               l->v->co[1] = (l->v->co[1] + cent[1]) / 2.0;
+               l->v->co[2] = (l->v->co[2] + cent[2]) / 2.0;
+       }
+       return NULL;
+}
\ No newline at end of file
diff --git a/source/blender/bmesh/SConscript b/source/blender/bmesh/SConscript
new file mode 100644 (file)
index 0000000..eb3ad38
--- /dev/null
@@ -0,0 +1,16 @@
+#!/usr/bin/python
+Import ('env')
+
+sources = env.Glob('*.c')
+
+incs = '. ./intern '
+incs += '#/intern/guardedalloc ../include ../blenlib ../makesdna'
+incs += ' ../python ../render/extern/include '
+incs += ' ../imbuf ../avi '
+incs += ' ../blenloader ../quicktime'
+incs += ' ../blenkernel ../renderconverter '
+
+incs += ' ' + env['BF_ZLIB_INC']
+defs = ''
+
+env.BlenderLib ( libname = 'bf_bmesh', sources = sources, includes = Split(incs), defines = Split(defs), libtype=['core','player'], priority = [63, 21] )
diff --git a/source/blender/bmesh/bmesh_private.h b/source/blender/bmesh/bmesh_private.h
new file mode 100644 (file)
index 0000000..66557fe
--- /dev/null
@@ -0,0 +1,71 @@
+/**
+ * BME_private.h    jan 2007
+ *
+ *     low level, 'private' function prototypes for bmesh kernel.
+ *
+ * $Id: BKE_bmesh.h,v 1.00 2007/01/17 17:42:01 Briggs Exp $
+ *
+ * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version. The Blender
+ * Foundation also sells licenses for use in proprietary software under
+ * the Blender License.  See http://www.blender.org/BL/ for information
+ * about this. 
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
+ *
+ * The Original Code is Copyright (C) 2004 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Geoffrey Bantle.
+ *
+ * ***** END GPL/BL DUAL LICENSE BLOCK *****
+ */
+
+#ifndef BMESH_PRIVATE
+#define BMESH_PRIVATE
+
+#include "BKE_bmesh.h"
+
+/*ALLOCATION/DEALLOCATION*/
+struct BME_Vert *BME_addvertlist(struct BME_Mesh *bm, struct BME_Vert *example);
+struct BME_Edge *BME_addedgelist(struct BME_Mesh *bm, struct BME_Vert *v1, struct BME_Vert *v2, struct BME_Edge *example);
+struct BME_Poly *BME_addpolylist(struct BME_Mesh *bm, struct BME_Poly *example); 
+struct BME_Loop *BME_create_loop(struct BME_Mesh *bm, struct BME_Vert *v, struct BME_Edge *e, struct BME_Poly *f, struct BME_Loop *example);
+
+void BME_free_vert(struct BME_Mesh *bm, struct BME_Vert *v);
+void BME_free_edge(struct BME_Mesh *bm, struct BME_Edge *e);
+void BME_free_poly(struct BME_Mesh *bm, struct BME_Poly *f);
+void BME_free_loop(struct BME_Mesh *bm, struct BME_Loop *l);
+void BME_delete_loop(struct BME_Mesh *bm, struct BME_Loop *l);
+
+/*DOUBLE CIRCULAR LINKED LIST FUNCTIONS*/
+void BME_cycle_append(void *h, void *nt);
+int BME_cycle_remove(void *h, void *remn);
+int BME_cycle_validate(int len, void *h);
+/*DISK CYCLE MANAGMENT*/
+int BME_disk_append_edge(struct BME_Edge *e, struct BME_Vert *v);
+void BME_disk_remove_edge(struct BME_Edge *e, struct BME_Vert *v);
+/*RADIAL CYCLE MANAGMENT*/
+void BME_radial_append(struct BME_Edge *e, struct BME_Loop *l);
+void BME_radial_remove_loop(struct BME_Loop *l, struct BME_Edge *e);
+
+/*MISC FUNCTIONS*/
+int BME_edge_swapverts(struct BME_Edge *e, struct BME_Vert *orig, struct BME_Vert *new); /*relink edge*/
+int BME_disk_hasedge(struct BME_Vert *v, struct BME_Edge *e);
+
+/*Error reporting. Shouldnt be called by tools ever.*/
+void BME_error(void);
+#endif
\ No newline at end of file
diff --git a/source/blender/include/editbmesh.h b/source/blender/include/editbmesh.h
new file mode 100644 (file)
index 0000000..0863084
--- /dev/null
@@ -0,0 +1,20 @@
+struct Mesh;
+struct CustomData;
+struct BME_Mesh;
+struct BME_Vert;
+struct BME_Edge;
+struct BME_Loop;
+struct BME_Face;
+
+struct BME_Mesh *BME_FromMesh(Mesh *mesh);
+void Mesh_FromBMesh(struct BME_Mesh *bmesh, struct Mesh *mesh);
+void EditBME_remakeEditMesh(void);
+void EditBME_makeEditMesh(void);
+void EditBME_loadEditMesh(struct Mesh *mesh);
+void EditBME_MouseClick();
+void BME_data_interp_from_verts(struct BME_Vert *v1, struct BME_Vert *v2, struct BME_Vert *eve, float fac);
+void BME_add_data_layer(struct CustomData *data, int type);
+void BME_free_data_layer(struct CustomData *data, int type);
+struct BME_Vert *EditBME_FindNearestVert(int *dis);
+struct BME_Edge *EditBME_FindNearestEdge(int *dis);
+struct BME_Poly *EditBME_FindNearestPoly(int *dis);
diff --git a/source/blender/src/editbmesh_derivedmesh.c b/source/blender/src/editbmesh_derivedmesh.c
new file mode 100644 (file)
index 0000000..e69de29
diff --git a/source/blender/src/editbmesh_interface.c b/source/blender/src/editbmesh_interface.c
new file mode 100644 (file)
index 0000000..69e85bc
--- /dev/null
@@ -0,0 +1,449 @@
+#include "MEM_guardedalloc.h"
+
+#include "BKE_bmesh.h"
+#include "BKE_mesh.h"
+#include "BKE_global.h"
+#include "BKE_main.h"
+#include "BKE_customdata.h"
+#include "BKE_DerivedMesh.h"
+#include "BKE_depsgraph.h"
+#include "BKE_utildefines.h"
+
+#include "DNA_meshdata_types.h"
+#include "DNA_mesh_types.h"
+#include "DNA_object_types.h"
+#include "DNA_customdata_types.h"
+
+#include "BLI_PointerArray.h"
+#include "BLI_memarena.h"
+#include "BLI_blenlib.h"
+
+#include "BIF_space.h"
+
+#include "mydevice.h" //event codes
+#include "editbmesh.h"
+
+typedef struct BME_Undo_Mesh {
+} BME_Undo_Mesh;
+
+typedef struct BME_Undo_Poly {
+} BME_Undo_Poly;
+
+typedef struct BME_Undo_Loop {
+} BME_Undo_Loop;
+
+typedef struct BME_Undo_Edge {
+} BME_Undo_Edge;
+
+typedef struct BME_Undo_Vert {
+} BME_Undo_Vert;
+
+BME_Undo_Mesh *EditBME_makeUndoMesh(BME_Mesh *mesh)
+{
+       return NULL;
+}
+
+typedef struct _edgeref {
+       struct _edgeref *next, *prev;
+       BME_Edge *edge;
+} _edgeref;
+
+//after this, iref should point to the right BME_Edge _edgeref.
+#define GET_EDGE_FOR_VERTS(_iref, _v1, _v2, _vlist_edges) \
+       for (_iref=_vlist_edges[_v1->tflag1].first; _iref; _iref=_iref->next) {\
+               if ((_iref->edge->v1==_v1 && _iref->edge->v2==_v2) ||\
+                   (_iref->edge->v1==_v2 && _iref->edge->v2==_v1)) break;}
+
+/*okkkaaay. . .why did I write this function, conversion is better in readfile.c*/
+BME_Mesh *BME_fromOldMesh(Mesh *mesh)
+{
+       BME_Mesh *bmesh = BME_make_mesh();
+       MFace *mface;
+       MEdge *medge;
+       MVert *mvert;
+       BME_Vert **vert_table;
+       BME_Edge **edge_table;
+       BME_Edge *edges[4];
+       ListBase *vlist_edges;
+       _edgeref *ref;
+       MemArena *edgearena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE);
+       int i, j;
+       
+       if (!mesh->totvert) return bmesh;
+       vert_table = MEM_callocN(sizeof(void*)*mesh->totvert, "vert table");
+       edge_table = MEM_callocN(sizeof(void*)*mesh->totedge, "edge table");
+       
+       vlist_edges = MEM_callocN(sizeof(ListBase)*mesh->totvert, "vlist_e");
+       
+       for (i=0, mvert=mesh->mvert; i<mesh->totvert; i++, mvert++) {
+               vert_table[i] = BME_MV(bmesh, mvert->co);
+               vert_table[i]->flag = mvert->flag;
+               vert_table[i]->tflag1 = i;
+       }
+       
+       for (i=0, medge=mesh->medge; i<mesh->totedge; i++, medge++) {
+               edge_table[i] = BME_ME(bmesh, vert_table[medge->v1], vert_table[medge->v2]);
+               ref = BLI_memarena_alloc(edgearena, sizeof(_edgeref)*2);
+               ref->edge = edge_table[i];
+               BLI_addtail(&vlist_edges[medge->v1], ref);
+               ref++;
+               ref->edge = edge_table[i];
+               BLI_addtail(&vlist_edges[medge->v2], ref);
+       }
+       
+       for (i=0, mface=mesh->mface; i<mesh->totface; i++, mface++) {
+               j = 0;
+               GET_EDGE_FOR_VERTS(ref, vert_table[mface->v1], vert_table[mface->v2], vlist_edges);
+               edges[0] = ref->edge;
+               GET_EDGE_FOR_VERTS(ref, vert_table[mface->v2], vert_table[mface->v3], vlist_edges);
+               edges[1] = ref->edge;
+               if (mface->v4) {
+                       GET_EDGE_FOR_VERTS(ref, vert_table[mface->v3], vert_table[mface->v4], vlist_edges);
+                       edges[2] = ref->edge;
+                       GET_EDGE_FOR_VERTS(ref, vert_table[mface->v4], vert_table[mface->v1], vlist_edges);
+                       edges[3] = ref->edge;
+               } else {
+                       GET_EDGE_FOR_VERTS(ref, vert_table[mface->v3], vert_table[mface->v1], vlist_edges);
+                       edges[3] = ref->edge;
+               }
+               
+               BME_MF(bmesh, edges[0]->v1, edges[0]->v2, edges, mface->v4?4:3);
+       }
+       
+       if (vert_table) MEM_freeN(vert_table);
+       if (edge_table) MEM_freeN(edge_table);
+       if (vlist_edges) MEM_freeN(vlist_edges);
+       BLI_memarena_free(edgearena);
+       
+       return bmesh;   
+}
+
+BME_Mesh *BME_FromMesh(Mesh *me)
+{
+       BME_Mesh *bmesh = BME_make_mesh();
+       MPoly *mpoly;
+       MLoop *mloop;
+       MEdge *medge;
+       MVert *mvert;
+       BME_Vert **vert_table = MEM_callocN(sizeof(void*)*me->totvert, "vert table");
+       BME_Edge **edge_table = MEM_callocN(sizeof(void*)*me->totedge, "edge table");
+       BME_Poly *poly;
+       PointerArray edgearr = {0};
+       int i, j;
+       
+       if (me->totface && !me->totpoly) return BME_fromOldMesh(me);
+       
+       CustomData_copy(&me->vdata, &bmesh->vdata, CD_MASK_EDITMESH, CD_CALLOC, 0);
+       for (i=0, mvert=me->mvert; i<me->totvert; i++, mvert++) {
+               vert_table[i] = BME_MV(bmesh, mvert->co);
+               vert_table[i]->flag = mvert->flag;
+               CustomData_to_em_block(&me->vdata, &bmesh->vdata, i, &vert_table[i]->data);
+       }
+       
+       for (i=0, medge=me->medge; i<me->totedge; i++, medge++) {
+               edge_table[i] = BME_ME(bmesh, vert_table[medge->v1], vert_table[medge->v2]);
+       }
+       
+       CustomData_copy(&me->pdata, &bmesh->pdata, CD_MASK_EDITMESH, CD_CALLOC, 0);
+       for (i=0, mpoly=me->mpoly; i<me->totpoly; i++, mpoly++) {
+               mloop = &me->mloop[mpoly->firstloop];
+               printf("mpoly->firstloop: %d, me->mloop: %p\n", mpoly->firstloop, me->mloop);
+               for (j=0; j<mpoly->totloop; j++) {
+                       PA_AddToArray(&edgearr, edge_table[mloop->edge], j);
+                       mloop++;
+               }               
+               poly = BME_MF(bmesh, ((BME_Edge*)edgearr.array[0])->v1, ((BME_Edge*)edgearr.array[0])->v2, (BME_Edge**)edgearr.array, j);
+               if (!poly) printf("EVIL POLY NOT CREATED!! EVVVIILL!!\n");
+               PA_FreeArray(&edgearr);
+               CustomData_to_em_block(&me->pdata, &bmesh->pdata, i, &poly->data);
+       }
+       
+       /*remember to restore loop data here, including custom data!*/
+       
+       if (vert_table) MEM_freeN(vert_table);
+       if (edge_table) MEM_freeN(edge_table);
+       
+       return bmesh;
+}
+
+/*Remember to use custom data stuff to allocate everything, including mpolys and mloops!*/
+void Mesh_FromBMesh(BME_Mesh *bmesh, Mesh *me)
+{
+       MPoly *mpoly;
+       MLoop *mloop;
+       MEdge *medge;
+       MVert *mvert;
+       BME_Vert *bve;
+       BME_Edge *bed;
+       BME_Loop *blo;
+       BME_Poly *bply;
+       int i, j, curloop=0;
+       
+       printf("v: %d e: %d l: %d p: %d\n", bmesh->totvert, bmesh->totedge, bmesh->totloop, bmesh->totpoly);
+       CustomData_free(&me->vdata, me->totvert);
+       CustomData_free(&me->edata, me->totedge);
+       CustomData_free(&me->fdata, me->totface);
+       CustomData_free(&me->ldata, me->totloop);
+       CustomData_free(&me->pdata, me->totpoly);
+       
+       /*mvert/edge/loop/poly are all used progressively, from this initial assignment.*/
+       mvert = me->mvert = MEM_callocN(sizeof(MVert)*bmesh->totvert, "mvert");
+       medge = me->medge = MEM_callocN(sizeof(MEdge)*bmesh->totedge, "medge");
+       mloop = me->mloop = MEM_callocN(sizeof(MLoop)*bmesh->totloop, "mloop");
+       mpoly = me->mpoly = MEM_callocN(sizeof(MPoly)*bmesh->totpoly, "mpoly");
+       
+       CustomData_copy(&bmesh->vdata, &me->vdata, CD_MASK_MESH, CD_CALLOC, me->totvert);
+       CustomData_copy(&bmesh->ldata, &me->ldata, CD_MASK_MESH, CD_CALLOC, me->totloop);
+       CustomData_copy(&bmesh->pdata, &me->pdata, CD_MASK_MESH, CD_CALLOC, me->totpoly);
+
+       CustomData_add_layer(&me->vdata, CD_MVERT, CD_ASSIGN, mvert, me->totvert);
+       CustomData_add_layer(&me->edata, CD_MEDGE, CD_ASSIGN, medge, me->totedge);
+       CustomData_add_layer(&me->ldata, CD_MLOOP, CD_ASSIGN, mloop, me->totloop);
+       CustomData_add_layer(&me->pdata, CD_MPOLY, CD_ASSIGN, mpoly, me->totpoly);
+       
+       me->totface = 0; me->mface = NULL; /*set mface to NULL*/
+
+       me->totvert = bmesh->totvert;
+       me->totedge = bmesh->totedge;
+       me->totloop = bmesh->totloop;
+       me->totpoly = bmesh->totpoly;
+       
+       mesh_update_customdata_pointers(me);
+
+       for (bve=bmesh->verts.first, i=0; bve; i++, bve=bve->next, mvert++) {
+               bve->tflag1 = i;
+               VECCOPY(bve->co, mvert->co);
+               VECCOPY(bve->no, mvert->no);
+               CustomData_from_em_block(&bmesh->vdata, &me->vdata, bve->data, i);
+       }
+       
+       /* the edges */
+       for (bed=bmesh->edges.first, i=0; bed; i++, bed=bed->next, mvert++) {
+               bed->tflag1 = i;
+               medge->v1= (unsigned int) bed->v1->tflag1;
+               medge->v2= (unsigned int) bed->v2->tflag1;
+               
+               medge->flag= (bed->flag & SELECT) | ME_EDGERENDER;
+               //if(eed->f2<2) medge->flag |= ME_EDGEDRAW;
+               //f(eed->f2==0) medge->flag |= ME_LOOSEEDGE;
+               //if (eed->sharp) medge->flag |= ME_SHARP;
+               //if (eed->seam) medge->flag |= ME_SEAM;
+               //if (eed->h & EM_FGON) medge->flag |= ME_FGON; // different defines yes
+               //if (eed->h & 1) medge->flag |= ME_HIDE;
+               
+               medge->crease= (char)(255.0*bed->crease);
+       }
+       
+       for (bply=bmesh->polys.first, i=0; bply; i++, mpoly++, bply=bply->next) {
+               CustomData_from_em_block(&bmesh->pdata, &me->pdata, bply->data, i);
+               mpoly->firstloop = curloop;
+               mpoly->flag = bply->flag;
+               mpoly->mat_nr = bply->mat_nr;
+               blo=bply->loopbase;
+               j = 0;
+               do {
+                       mloop->v = blo->v->tflag1;
+                       mloop->poly = i;
+                       mloop->edge = blo->e->tflag1;
+                       mloop++;
+                       curloop++;
+                       j++;
+                       blo=blo->next;
+               } while (blo != bply->loopbase);
+               mpoly->totloop = j;
+       }
+}
+
+
+void hide_mesh(int i)
+{
+}
+
+void reveal_mesh(void)
+{
+}
+
+void deselectall_mesh(void)
+{
+}
+
+/*eventual replacement for EM_check_backbuf, if I decide to do it that way.*/
+void BME_check_backbuf(int offset)
+{
+}
+
+void add_primitiveMesh(int type)
+{
+}
+
+void EditBME_remakeEditMesh(void)
+{
+       EditBME_makeEditMesh();
+       allqueue(REDRAWVIEW3D, 0);
+       DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
+       BIF_undo_push("Undo all changes");
+}
+
+void EditBME_makeEditMesh(void)
+{
+       G.editMesh = BME_FromMesh(G.obedit->data);
+}
+
+void EditBME_loadEditMesh(Mesh *mesh)
+{
+       Mesh_FromBMesh(G.editMesh, mesh);
+}
+
+void mouse_bmesh()
+{
+}
+
+BME_Vert *EditBME_FindNearestVert(int *dis)
+{
+}
+
+BME_Edge *EditBME_FindNearestEdge(int *dis)
+{
+}
+
+BME_Poly *EditBME_FindNearestPoly(int *dis)
+{
+}
+
+void undo_push_mesh(char *str)
+{
+}
+
+void BME_data_interp_from_verts(BME_Vert *v1, BME_Vert *v2, BME_Vert *eve, float fac)
+{
+       BME_Mesh *em= G.editMesh;
+       void *src[2];
+       float w[2];
+
+       if (v1->data && v2->data) {
+               src[0]= v1->data;
+               src[1]= v2->data;
+               w[0] = 1.0f-fac;
+               w[1] = fac;
+
+               CustomData_em_interp(&em->vdata, src, w, NULL, 2, eve->data);
+       }
+}
+
+static void update_data_blocks(CustomData *olddata, CustomData *data)
+{
+       BME_Mesh *em= G.editMesh;
+       BME_Poly *efa;
+       BME_Vert *eve;
+       void *block;
+
+       if (data == &G.editMesh->vdata) {
+               for(eve= em->verts.first; eve; eve= eve->next) {
+                       block = NULL;
+                       CustomData_em_set_default(data, &block);
+                       CustomData_em_copy_data(olddata, data, eve->data, &block);
+                       CustomData_em_free_block(olddata, &eve->data);
+                       eve->data= block;
+               }
+       }
+       else if (data == &G.editMesh->pdata) {
+               for(efa= em->polys.first; efa; efa= efa->next) {
+                       block = NULL;
+                       CustomData_em_set_default(data, &block);
+                       CustomData_em_copy_data(olddata, data, efa->data, &block);
+                       CustomData_em_free_block(olddata, &efa->data);
+                       efa->data= block;
+               }
+       }
+       else if (data == &G.editMesh->edata) {
+       }
+       else if (data == &G.editMesh->ldata) {
+       }
+}
+
+void BME_add_data_layer(CustomData *data, int type)
+{
+       CustomData olddata;
+
+       olddata= *data;
+       olddata.layers= (olddata.layers)? MEM_dupallocN(olddata.layers): NULL;
+       CustomData_add_layer(data, type, CD_CALLOC, NULL, 0);
+
+       update_data_blocks(&olddata, data);
+       if (olddata.layers) MEM_freeN(olddata.layers);
+}
+
+void BME_free_data_layer(CustomData *data, int type)
+{
+       CustomData olddata;
+
+       olddata= *data;
+       olddata.layers= (olddata.layers)? MEM_dupallocN(olddata.layers): NULL;
+       CustomData_free_layer_active(data, type, 0);
+
+       update_data_blocks(&olddata, data);
+       if (olddata.layers) MEM_freeN(olddata.layers);
+}
+
+/*Various customdata stuff still in need of conversion :/*/
+#if 0
+/* paranoia check, actually only for entering editmode. rule:
+- vertex hidden, always means edge is hidden too
+- edge hidden, always means face is hidden too
+- face hidden, dont change anything
+*/
+void EM_hide_reset(void)
+{
+       EditMesh *em = G.editMesh;
+       EditEdge *eed;
+       EditFace *efa;
+       
+       for(eed= em->edges.first; eed; eed= eed->next) 
+               if(eed->v1->h || eed->v2->h) eed->h |= 1;
+               
+       for(efa= em->faces.first; efa; efa= efa->next) 
+               if((efa->e1->h & 1) || (efa->e2->h & 1) || (efa->e3->h & 1) || (efa->e4 && (efa->e4->h & 1)))
+                       efa->h= 1;
+               
+}
+
+void EM_data_interp_from_faces(EditFace *efa1, EditFace *efa2, EditFace *efan, int i1, int i2, int i3, int i4)
+{
+       EditMesh *em= G.editMesh;
+       float w[2][4][4];
+       void *src[2];
+       int count = (efa2)? 2: 1;
+
+       if (efa1->data) {
+               /* set weights for copying from corners directly to other corners */
+               memset(w, 0, sizeof(w));
+
+               w[i1/4][0][i1%4]= 1.0f;
+               w[i2/4][1][i2%4]= 1.0f;
+               w[i3/4][2][i3%4]= 1.0f;
+               if (i4 != -1)
+                       w[i4/4][3][i4%4]= 1.0f;
+
+               src[0]= efa1->data;
+               src[1]= (efa2)? efa2->data: NULL;
+
+               CustomData_em_interp(&em->fdata, src, NULL, (float*)w, count, efan->data);
+       }
+}
+
+EditFace *EM_face_from_faces(EditFace *efa1, EditFace *efa2, int i1, int i2, int i3, int i4)
+{
+       EditFace *efan;
+       EditVert **v[2];
+       
+       v[0]= &efa1->v1;
+       v[1]= (efa2)? &efa2->v1: NULL;
+
+       efan= addfacelist(v[i1/4][i1%4], v[i2/4][i2%4], v[i3/4][i3%4],
+               (i4 == -1)? 0: v[i4/4][i4%4], efa1, NULL);
+
+       EM_data_interp_from_faces(efa1, efa2, efan, i1, i2, i3, i4);
+       
+       return efan;
+}
+#endif
diff --git a/source/blender/src/editbmesh_tools.c b/source/blender/src/editbmesh_tools.c
new file mode 100644 (file)
index 0000000..e69de29
diff --git a/source/blender/src/editbmesh_util.c b/source/blender/src/editbmesh_util.c
new file mode 100644 (file)
index 0000000..e69de29