copying bmesh dir on its own from bmesh branch
authorCampbell Barton <ideasman42@gmail.com>
Sun, 19 Feb 2012 18:31:04 +0000 (18:31 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Sun, 19 Feb 2012 18:31:04 +0000 (18:31 +0000)
54 files changed:
source/blender/bmesh/CMakeLists.txt [new file with mode: 0644]
source/blender/bmesh/SConscript [new file with mode: 0644]
source/blender/bmesh/bmesh.h [new file with mode: 0644]
source/blender/bmesh/bmesh_class.h [new file with mode: 0644]
source/blender/bmesh/bmesh_error.h [new file with mode: 0644]
source/blender/bmesh/bmesh_iterators.h [new file with mode: 0644]
source/blender/bmesh/bmesh_marking.h [new file with mode: 0644]
source/blender/bmesh/bmesh_operator_api.h [new file with mode: 0644]
source/blender/bmesh/bmesh_operators.h [new file with mode: 0644]
source/blender/bmesh/bmesh_queries.h [new file with mode: 0644]
source/blender/bmesh/bmesh_walkers.h [new file with mode: 0644]
source/blender/bmesh/editmesh_tools.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_construct.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_eulers.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_inline.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_interp.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_iterators.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_iterators_inline.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_marking.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_mesh.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_mods.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_newcore.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_opdefines.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_operators.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_operators_private.h [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_polygon.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_private.h [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_queries.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_structure.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_structure.h [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_walkers.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_walkers_impl.c [new file with mode: 0644]
source/blender/bmesh/intern/bmesh_walkers_private.h [new file with mode: 0644]
source/blender/bmesh/intern/in-progress/BME_conversions.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_bevel.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_connect.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_create.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_dissolve.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_dupe.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_edgesplit.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_extrude.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_join_triangles.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_mesh_conv.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_mirror.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_primitive.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_removedoubles.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_subdivide.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_subdivide.h [new file with mode: 0644]
source/blender/bmesh/operators/bmo_triangulate.c [new file with mode: 0644]
source/blender/bmesh/operators/bmo_utils.c [new file with mode: 0644]
source/blender/bmesh/tools/BME_bevel.c [new file with mode: 0644]
source/blender/bmesh/tools/BME_dupe_ops.c [new file with mode: 0644]
source/blender/bmesh/tools/BME_duplicate.c [new file with mode: 0644]
source/blender/bmesh/tools/BME_weld.c [new file with mode: 0644]

diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt
new file mode 100644 (file)
index 0000000..d834901
--- /dev/null
@@ -0,0 +1,137 @@
+# $Id: CMakeLists.txt 31746 2010-09-04 05:31:25Z joeedh $
+# ***** BEGIN GPL 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.
+#
+# 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+#
+# The Original Code is Copyright (C) 2006, Blender Foundation
+# All rights reserved.
+#
+# The Original Code is: all of this file.
+#
+# Contributor(s): Jacques Beaurain.
+#
+# ***** END GPL LICENSE BLOCK *****
+
+set(INC 
+       .
+       intern
+       operators
+       ../avi
+       ../blenfont
+       ../blenkernel
+       ../blenlib
+       ../blenloader
+       ../editors/include
+       ../editors/mesh
+       ../gpu
+       ../ikplugin
+       ../imbuf
+       ../makesdna
+       ../makesrna
+       ../modifiers
+       ../nodes
+       ../render/extern/include
+       ../../../extern/glew/include
+       ../../../intern/audaspace/intern
+       ../../../intern/bsp/extern
+       ../../../intern/decimation/extern
+       ../../../intern/elbeem/extern
+       ../../../intern/guardedalloc
+       ../../../intern/iksolver/extern
+       ../../../intern/memutil
+       ../../../intern/mikktspace
+       ../../../intern/opennl/extern
+       ../../../intern/smoke/extern
+       # XXX - BAD LEVEL CALL WM_api.h
+       ../../../source/blender/windowmanager
+)
+
+set(INC_SYS
+       ${ZLIB_INCLUDE_DIRS}
+)
+
+set(SRC
+       operators/bmo_bevel.c
+       operators/bmo_connect.c
+       operators/bmo_create.c
+       operators/bmo_dissolve.c
+       operators/bmo_dupe.c
+       operators/bmo_edgesplit.c
+       operators/bmo_extrude.c
+       operators/bmo_join_triangles.c
+       operators/bmo_mesh_conv.c
+       operators/bmo_mirror.c
+       operators/bmo_primitive.c
+       operators/bmo_removedoubles.c
+       operators/bmo_subdivide.c
+       operators/bmo_subdivide.h
+       operators/bmo_triangulate.c
+       operators/bmo_utils.c
+
+       intern/bmesh_newcore.c
+       intern/bmesh_interp.c
+       intern/bmesh_iterators.c
+       intern/bmesh_iterators_inline.c
+       intern/bmesh_marking.c
+       intern/bmesh_mesh.c
+       intern/bmesh_mods.c
+       intern/bmesh_structure.h
+       intern/bmesh_construct.c
+       intern/bmesh_operators_private.h
+       intern/bmesh_structure.c
+       intern/bmesh_polygon.c
+       intern/bmesh_queries.c
+       intern/bmesh_opdefines.c
+       intern/bmesh_eulers.c
+       intern/bmesh_operators.c
+       intern/bmesh_private.h
+       intern/bmesh_walkers.c
+       intern/bmesh_walkers_impl.c
+       intern/bmesh_walkers_private.h
+       intern/bmesh_inline.c
+
+       tools/BME_bevel.c
+       bmesh.h
+       bmesh_class.h
+       bmesh_error.h
+       bmesh_iterators.h
+       bmesh_marking.h
+       bmesh_operator_api.h
+       bmesh_operators.h
+       bmesh_queries.h
+       bmesh_walkers.h
+)
+
+add_definitions(-DGLEW_STATIC)
+
+if(WITH_LZO)
+       add_definitions(-DWITH_LZO)
+       list(APPEND INC_SYS
+               ../../../extern/lzo/minilzo
+       )
+endif()
+
+if(WITH_LZMA)
+       add_definitions(-DWITH_LZMA)
+       list(APPEND INC_SYS
+               ../../../extern/lzma
+       )
+endif()
+
+if(MSVC)
+       set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS} /WX")
+endif()
+
+blender_add_lib(bf_bmesh "${SRC}" "${INC}" "${INC_SYS}")
diff --git a/source/blender/bmesh/SConscript b/source/blender/bmesh/SConscript
new file mode 100644 (file)
index 0000000..91b7a72
--- /dev/null
@@ -0,0 +1,40 @@
+#!/usr/bin/python
+Import ('env')
+
+cflags=''
+"""
+sources = ['intern/bmesh_eulers.c']
+sources.append('intern/bmesh_mesh.c')
+sources.append('intern/bmesh_polygon.c')
+sources.append('intern/bmesh_structure.c')
+sources.append('intern/bmesh_marking.c')
+
+sources.append('intern/bmesh_construct.c')
+sources.append('intern/bmesh_interp.c')
+sources.append('intern/bmesh_filters.c')
+sources.append('intern/bmesh_iterators.c')
+sources.append('intern/bmesh_mods.c')
+sources.append('intern/bmesh_queries.c')
+sources.append('intern/bmesh_operators.c')
+"""
+#sources.append('api/BME_walkers.c')
+
+
+sources = env.Glob('intern/*.c')
+sources += env.Glob('operators/*.c')
+
+#sources += env.Glob('tools/*.c')
+
+incs = ['#/intern/guardedalloc'] 
+incs.append('../blenlib') 
+incs.append('../blenloader') 
+incs.append('../makesdna')
+incs.append('../makesrna')
+incs.append('../blenkernel')
+incs.append('./')
+incs.append('./intern')
+incs.append('../editors/mesh')
+incs.append('../editors/include')
+
+defs = []
+env.BlenderLib ( libname = 'bf_bmesh', sources = sources, includes = Split(incs), libtype = 'core', defines=defs, priority=100, compileflags=cflags )
diff --git a/source/blender/bmesh/bmesh.h b/source/blender/bmesh/bmesh.h
new file mode 100644 (file)
index 0000000..ae85c40
--- /dev/null
@@ -0,0 +1,380 @@
+/*
+ * ***** BEGIN GPL 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.
+ *
+ * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Geoffrey Bantle, Levi Schooley.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_H__
+#define __BMESH_H__
+
+/** \file blender/bmesh/bmesh.h
+ *  \ingroup bmesh
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include "DNA_listBase.h"
+#include "DNA_customdata_types.h"
+
+#include "BLI_utildefines.h"
+
+#include "bmesh_class.h"
+
+/*
+ * short introduction:
+ *
+ * the bmesh structure is a boundary representation, supporting non-manifold
+ * locally modifiable topology. the API is designed to allow clean, maintainable
+ * code, that never (or almost never) directly inspects the underlying structure.
+ *
+ * The API includes iterators, including many useful topological iterators;
+ * walkers, which walk over a mesh, without the risk of hitting the recursion
+ * limit; operators, which are logical, reusable mesh modules; topological
+ * modification functions (like split face, join faces, etc), which are used for
+ * topological manipulations; and some (not yet finished) geometric utility
+ * functions.
+ *
+ * some definitions:
+ *
+ * tool flags: private flags for tools.  each operator has it's own private
+ *             tool flag "layer", which it can use to flag elements.
+ *             tool flags are also used by various other parts of the api.
+ * header flags: stores persistent flags, such as selection state, hide state,
+ *               etc.  be careful of touching these.
+ */
+
+/*forward declarations*/
+struct BMesh;
+struct BMVert;
+struct BMEdge;
+struct BMFace;
+struct BMLoop;
+struct BMOperator;
+struct Mesh;
+struct EditMesh;
+
+/*
+ * BMHeader
+ *
+ * All mesh elements begin with a BMHeader. This structure
+ * hold several types of data
+ *
+ * 1: The type of the element (vert, edge, loop or face)
+ * 2: Persistant "header" flags/markings (sharp, seam, select, hidden, ect)
+      note that this is different from the "tool" flags.
+ * 3: Unique ID in the bmesh.
+ * 4: some elements for internal record keeping.
+ *
+*/
+
+/* BMHeader->htype (char) */
+#define BM_VERT        1
+#define BM_EDGE        2
+#define BM_LOOP        4
+#define BM_FACE        8
+#define BM_ALL         (BM_VERT | BM_EDGE | BM_LOOP | BM_FACE)
+
+/* BMHeader->hflag (char) */
+#define BM_ELEM_SELECT (1 << 0)
+#define BM_ELEM_HIDDEN (1 << 1)
+#define BM_ELEM_SEAM   (1 << 2)
+#define BM_ELEM_SMOOTH (1 << 3) /* used for faces and edges, note from the user POV,
+                                  * this is a sharp edge when disabled */
+
+#define BM_ELEM_TAG     (1 << 4) /* internal flag, used for ensuring correct normals
+                                  * during multires interpolation, and any other time
+                                  * when temp tagging is handy.
+                                  * always assume dirty & clear before use. */
+
+/* we have 3 spare flags which is awesome but since we're limited to 8
+ * only add new flags with care! - campbell */
+/* #define BM_ELEM_SPARE        (1<<5) */
+/* #define BM_ELEM_SPARE        (1<<6) */
+/* #define BM_ELEM_NONORMCALC (1<<7) */ /* UNUSED */
+
+/* stub */
+void bmesh_error(void);
+
+/* Mesh Level Ops */
+extern int bm_mesh_allocsize_default[4];
+
+/* ob is needed by multires */
+BMesh *BM_mesh_create(struct Object *ob, const int allocsize[4]);
+BMesh *BM_mesh_copy(BMesh *bmold);
+void   BM_mesh_free(BMesh *bm);
+
+/* frees mesh, but not actual BMesh struct */
+void BM_mesh_data_free(BMesh *bm);
+void BM_mesh_normals_update(BMesh *bm);
+
+/* Construction */
+BMVert *BM_vert_create(BMesh *bm, const float co[3], const BMVert *example);
+BMEdge *BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2, const BMEdge *example, int nodouble);
+BMFace *BM_face_create(BMesh *bm, BMVert **verts, BMEdge **edges, const int len, int nodouble);
+
+BMFace *BM_face_create_quad_tri_v(BMesh *bm,
+                                  BMVert **verts, int len,
+                                  const BMFace *example, const int nodouble);
+
+/* easier to use version of BM_face_create_quad_tri_v.
+ * creates edges if necassary. */
+BMFace *BM_face_create_quad_tri(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4,
+                                const BMFace *example, const int nodouble);
+
+/* makes an ngon from an unordered list of edges.  v1 and v2 must be the verts
+ * defining edges[0], and define the winding of the new face. */
+BMFace *BM_face_create_ngon(BMesh *bm, BMVert *v1, BMVert *v2, BMEdge **edges, int len, int nodouble);
+
+/* stuff for dealing with header flags */
+BM_INLINE char BM_elem_flag_test(const void *element, const char hflag);
+
+/* stuff for dealing with header flags */
+BM_INLINE void BM_elem_flag_enable(void *element, const char hflag);
+
+/* stuff for dealing with header flags */
+BM_INLINE void BM_elem_flag_disable(void *element, const char hflag);
+
+/* stuff for dealing BM_elem_flag_toggle header flags */
+BM_INLINE void BM_elem_flag_toggle(void *element, const char hflag);
+BM_INLINE void BM_elem_flag_merge(void *element_a, void *element_b);
+
+/* notes on BM_elem_index_set(...) usage,
+ * Set index is sometimes abused as temp storage, other times we cant be
+ * sure if the index values are valid because certain operations have modified
+ * the mesh structure.
+ *
+ * To set the elements to valid indicies 'BM_mesh_elem_index_ensure' should be used
+ * rather then adding inline loops, however there are cases where we still
+ * set the index directly
+ *
+ * In an attempt to manage this, here are 3 tags Im adding to uses of
+ * 'BM_elem_index_set'
+ *
+ * - 'set_inline'  -- since the data is already being looped over set to a
+ *                    valid value inline.
+ *
+ * - 'set_dirty!'  -- intentionally sets the index to an invalid value,
+ *                    flagging 'bm->elem_index_dirty' so we dont use it.
+ *
+ * - 'set_ok'      -- this is valid use since the part of the code is low level.
+ *
+ * - 'set_ok_invalid'  -- set to -1 on purpose since this should not be
+ *                    used without a full array re-index, do this on
+ *                    adding new vert/edge/faces since they may be added at
+ *                    the end of the array.
+ *
+ * - 'set_loop'    -- currently loop index values are not used used much so
+ *                    assume each case they are dirty.
+ * - campbell */
+
+BM_INLINE void BM_elem_index_set(void *element, const int index);
+BM_INLINE int  BM_elem_index_get(const void *element);
+
+/* todo */
+BMFace *BM_face_copy(BMesh *bm, BMFace *f, int copyedges, int copyverts);
+
+/* copies loop data from adjacent faces */
+void BM_face_copy_shared(BMesh *bm, BMFace *f);
+
+/* copies attributes, e.g. customdata, header flags, etc, from one element
+ * to another of the same type.*/
+void BM_elem_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, const void *source, void *target);
+
+/* Modification */
+/* join two adjacent faces together along an edge.  note that
+ * the faces must only be joined by on edge.  e is the edge you
+ * wish to dissolve.*/
+BMFace *BM_faces_join_pair(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e);
+
+/* generic, flexible join faces function; note that most everything uses
+ * this, including BM_faces_join_pair */
+BMFace *BM_faces_join(BMesh *bm, BMFace **faces, int totface);
+
+/* split a face along two vertices.  returns the newly made face, and sets
+ * the nl member to a loop in the newly created edge.*/
+BMFace *BM_face_split(BMesh *bm, BMFace *f,
+                      BMVert *v1, BMVert *v2,
+                      struct BMLoop **nl, BMEdge *example);
+
+/* these 2 functions are very similar */
+BMEdge* BM_vert_collapse_faces(BMesh *bm, BMEdge *ke, BMVert *kv, float fac, const int join_faces);
+BMEdge* BM_vert_collapse_edges(BMesh *bm, BMEdge *ke, BMVert *kv);
+
+
+/* splits an edge.  ne is set to the new edge created. */
+BMVert *BM_edge_split(BMesh *bm, BMVert *v, BMEdge *e, BMEdge **ne, float percent);
+
+/* split an edge multiple times evenly */
+BMVert  *BM_edge_split_n(BMesh *bm, BMEdge *e, int numcuts);
+
+/* connect two verts together, through a face they share.  this function may
+ * be removed in the future. */
+BMEdge *BM_verts_connect(BMesh *bm, BMVert *v1, BMVert *v2, BMFace **nf);
+
+/* rotates an edge topologically, either clockwise (if ccw=0) or counterclockwise
+ * (if ccw is 1). */
+BMEdge *BM_edge_rotate(BMesh *bm, BMEdge *e, int ccw);
+
+/* Rip a single face from a vertex fan */
+BMVert *BM_vert_rip(BMesh *bm, BMFace *sf, BMVert *sv);
+
+/*updates a face normal*/
+void BM_face_normal_update(BMesh *bm, BMFace *f);
+void BM_face_normal_update_vcos(BMesh *bm, BMFace *f, float no[3], float (*vertexCos)[3]);
+
+/*updates face and vertex normals incident on an edge*/
+void BM_edge_normals_update(BMesh *bm, BMEdge *e);
+
+/*update a vert normal (but not the faces incident on it)*/
+void BM_vert_normal_update(BMesh *bm, BMVert *v);
+void BM_vert_normal_update_all(BMesh *bm, BMVert *v);
+
+void BM_face_normal_flip(BMesh *bm, BMFace *f);
+
+/*dissolves all faces around a vert, and removes it.*/
+int BM_disk_dissolve(BMesh *bm, BMVert *v);
+
+/* dissolves vert, in more situations then BM_disk_dissolve
+ * (e.g. if the vert is part of a wire edge, etc).*/
+int BM_vert_dissolve(BMesh *bm, BMVert *v);
+
+/* Projects co onto face f, and returns true if it is inside
+ * the face bounds.  Note that this uses a best-axis projection
+ * test, instead of projecting co directly into f's orientation
+ * space, so there might be accuracy issues.*/
+int BM_face_point_inside_test(BMesh *bm, BMFace *f, const float co[3]);
+
+/* Interpolation */
+
+/* projects target onto source for customdata interpolation.  note: only
+ * does loop customdata.  multires is handled.  */
+void BM_face_interp_from_face(BMesh *bm, BMFace *target, BMFace *source);
+
+/* projects a single loop, target, onto source for customdata interpolation. multires is handled.
+ * if do_vertex is true, target's vert data will also get interpolated.*/
+void BM_loop_interp_from_face(BMesh *bm, BMLoop *target, BMFace *source,
+                              int do_vertex, int do_multires);
+
+/* smoothes boundaries between multires grids, including some borders in adjacent faces */
+void BM_face_multires_bounds_smooth(BMesh *bm, BMFace *f);
+
+/* project the multires grid in target onto source's set of multires grids */
+void BM_loop_interp_multires(BMesh *bm, BMLoop *target, BMFace *source);
+void BM_vert_interp_from_face(BMesh *bm, BMVert *v, BMFace *source);
+
+void  BM_data_interp_from_verts(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v, const float fac);
+void  BM_data_interp_face_vert_edge(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v, struct BMEdge *e1, const float fac);
+void  BM_data_layer_add(BMesh *em, CustomData *data, int type);
+void  BM_data_layer_add_named(BMesh *bm, CustomData *data, int type, const char *name);
+void  BM_data_layer_free(BMesh *em, CustomData *data, int type);
+void  BM_data_layer_free_n(BMesh *bm, CustomData *data, int type, int n);
+float BM_elem_float_data_get(struct CustomData *cd, void *element, int type);
+void  BM_elem_float_data_set(struct CustomData *cd, void *element, int type, const float val);
+
+/* get the area of the face */
+float BM_face_area_calc(BMesh *bm, BMFace *f);
+/* computes the centroid of a face, using the center of the bounding box */
+void BM_face_center_bounds_calc(BMesh *bm, BMFace *f, float center[3]);
+/* computes the centroid of a face, using the mean average */
+void BM_face_center_mean_calc(BMesh *bm, BMFace *f, float center[3]);
+
+void BM_mesh_select_mode_flush(BMesh *bm);
+
+/* mode independant flushing up/down */
+void BM_mesh_deselect_flush(BMesh *bm);
+void BM_mesh_select_flush(BMesh *bm);
+
+/* flag conversion funcs */
+char BM_face_flag_from_mflag(const char  mflag);
+char BM_edge_flag_from_mflag(const short mflag);
+char BM_vert_flag_from_mflag(const char  mflag);
+/* reverse */
+char  BM_face_flag_to_mflag(BMFace *f);
+short BM_edge_flag_to_mflag(BMEdge *e);
+char  BM_vert_flag_to_mflag(BMVert *v);
+
+
+/* convert MLoop*** in a bmface to mtface and mcol in
+ * an MFace*/
+void BM_loops_to_corners(BMesh *bm, struct Mesh *me, int findex,
+                         BMFace *f, int numTex, int numCol);
+
+void BM_loop_kill(BMesh *bm, BMLoop *l);
+void BM_face_kill(BMesh *bm, BMFace *f);
+void BM_edge_kill(BMesh *bm, BMEdge *e);
+void BM_vert_kill(BMesh *bm, BMVert *v);
+
+/* kills all edges associated with f, along with any other faces containing
+ * those edges*/
+void BM_face_edges_kill(BMesh *bm, BMFace *f);
+
+/* kills all verts associated with f, along with any other faces containing
+ * those vertices*/
+void BM_face_verts_kill(BMesh *bm, BMFace *f);
+
+/*clear all data in bm*/
+void BM_mesh_clear(BMesh *bm);
+
+void BM_mesh_elem_index_ensure(BMesh *bm, const char hflag);
+
+void BM_mesh_elem_index_validate(BMesh *bm, const char *location, const char *func,
+                                 const char *msg_a, const char *msg_b);
+
+BMVert *BM_vert_at_index(BMesh *bm, const int index);
+BMEdge *BM_edge_at_index(BMesh *bm, const int index);
+BMFace *BM_face_at_index(BMesh *bm, const int index);
+
+/*start/stop edit*/
+void bmesh_begin_edit(BMesh *bm, int flag);
+void bmesh_end_edit(BMesh *bm, int flag);
+
+
+#ifdef USE_BMESH_HOLES
+#  define BM_FACE_FIRST_LOOP(p) (((BMLoopList *)((p)->loops.first))->first)
+#else
+#  define BM_FACE_FIRST_LOOP(p) ((p)->l_first)
+#endif
+
+/* size to use for static arrays when dealing with NGons,
+ * alloc after this limit is reached.
+ * this value is rather arbitrary */
+#define BM_NGON_STACK_SIZE 32
+
+/* avoid inf loop, this value is arbtrary
+ * but should not error on valid cases */
+#define BM_LOOP_RADIAL_MAX 10000
+#define BM_NGON_MAX 100000
+
+/* include the rest of the API */
+#include "bmesh_marking.h"
+#include "bmesh_operator_api.h"
+#include "bmesh_operators.h"
+#include "bmesh_error.h"
+#include "bmesh_queries.h"
+#include "bmesh_iterators.h"
+#include "bmesh_walkers.h"
+#include "intern/bmesh_inline.c"
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __BMESH_H__ */
diff --git a/source/blender/bmesh/bmesh_class.h b/source/blender/bmesh/bmesh_class.h
new file mode 100644 (file)
index 0000000..3a62eaa
--- /dev/null
@@ -0,0 +1,190 @@
+/*
+ * ***** BEGIN GPL 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.
+ *
+ * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Geoffrey Bantle, Levi Schooley, Joseph Eagar.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_CLASS_H__
+#define __BMESH_CLASS_H__
+
+/** \file blender/bmesh/bmesh_class.h
+ *  \ingroup bmesh
+ */
+
+/* bmesh data structures */
+
+/* dissable holes for now, these are ifdef'd because they use more memory and cant be saved in DNA currently */
+// define USE_BMESH_HOLES
+
+struct BMesh;
+struct BMVert;
+struct BMEdge;
+struct BMLoop;
+struct BMFace;
+struct BMFlagLayer;
+struct BMLayerType;
+struct BMSubClassLayer;
+
+struct BLI_mempool;
+struct Object;
+
+/*note: it is very important for BMHeader to start with two
+  pointers. this is a requirement of mempool's method of
+  iteration.
+*/
+typedef struct BMHeader {
+       void *data; /* customdata layers */
+       int index; /* notes:
+                   * - Use BM_elem_index_get/SetIndex macros for index
+                   * - Unitialized to -1 so we can easily tell its not set.
+                   * - Used for edge/vert/face, check BMesh.elem_index_dirty for valid index values,
+                   *   this is abused by various tools which set it dirty.
+                   * - For loops this is used for sorting during tesselation. */
+
+       char htype; /* element geometric type (verts/edges/loops/faces) */
+       char hflag; /* this would be a CD layer, see below */
+} BMHeader;
+
+/* note: need some way to specify custom locations for custom data layers.  so we can
+ * make them point directly into structs.  and some way to make it only happen to the
+ * active layer, and properly update when switching active layers.*/
+
+typedef struct BMVert {
+       BMHeader head;
+       struct BMFlagLayer *oflags; /* keep after header, an array of flags, mostly used by the operator stack */
+
+       float co[3];
+       float no[3];
+       struct BMEdge *e;
+} BMVert;
+
+/* disk link structure, only used by edges */
+typedef struct BMDiskLink {
+       struct BMEdge *next, *prev;
+} BMDiskLink;
+
+typedef struct BMEdge {
+       BMHeader head;
+       struct BMFlagLayer *oflags; /* keep after header, an array of flags, mostly used by the operator stack */
+
+       struct BMVert *v1, *v2;
+       struct BMLoop *l;
+       
+       /* disk cycle pointers */
+       BMDiskLink v1_disk_link, v2_disk_link;
+} BMEdge;
+
+typedef struct BMLoop {
+       BMHeader head;
+       /* notice no flags layer */
+
+       struct BMVert *v;
+       struct BMEdge *e;
+       struct BMFace *f;
+
+       struct BMLoop *radial_next, *radial_prev;
+       
+       /* these were originally commented as private but are used all over the code */
+       /* can't use ListBase API, due to head */
+       struct BMLoop *next, *prev;
+} BMLoop;
+
+/* can cast BMFace/BMEdge/BMVert, but NOT BMLoop, since these dont have a flag layer */
+typedef struct BMElemF {
+       BMHeader head;
+       struct BMFlagLayer *oflags; /* keep after header, an array of flags, mostly used by the operator stack */
+} BMElemF;
+
+#ifdef USE_BMESH_HOLES
+/* eventually, this structure will be used for supporting holes in faces */
+typedef struct BMLoopList {
+       struct BMLoopList *next, *prev;
+       struct BMLoop *first, *last;
+} BMLoopList;
+#endif
+
+typedef struct BMFace {
+       BMHeader head;
+       struct BMFlagLayer *oflags; /* an array of flags, mostly used by the operator stack */
+
+       int len; /*includes all boundary loops*/
+#ifdef USE_BMESH_HOLES
+       int totbounds; /*total boundaries, is one plus the number of holes in the face*/
+       ListBase loops;
+#else
+       BMLoop *l_first;
+#endif
+       float no[3]; /*yes, we do store this here*/
+       short mat_nr;
+} BMFace;
+
+typedef struct BMFlagLayer {
+       short f, pflag; /* flags */
+} BMFlagLayer;
+
+typedef struct BMesh {
+       int totvert, totedge, totloop, totface;
+       int totvertsel, totedgesel, totfacesel;
+
+       /* flag index arrays as being dirty so we can check if they are clean and
+        * avoid looping over the entire vert/edge/face array in those cases.
+        * valid flags are - BM_VERT | BM_EDGE | BM_FACE.
+        * BM_LOOP isnt handled so far. */
+       char elem_index_dirty;
+       
+       /*element pools*/
+       struct BLI_mempool *vpool, *epool, *lpool, *fpool;
+
+       /*operator api stuff*/
+       struct BLI_mempool *toolflagpool;
+       int stackdepth;
+       struct BMOperator *currentop;
+       
+       CustomData vdata, edata, ldata, pdata;
+
+#ifdef USE_BMESH_HOLES
+       struct BLI_mempool *looplistpool;
+#endif
+
+       /* should be copy of scene select mode */
+       /* stored in BMEditMesh too, this is a bit confusing,
+        * make sure the're in sync!
+        * Only use when the edit mesh cant be accessed - campbell */
+       short selectmode;
+       
+       /*ID of the shape key this bmesh came from*/
+       int shapenr;
+       
+       int walkers, totflags;
+       ListBase selected, error_stack;
+       
+       BMFace *act_face;
+
+       ListBase errorstack;
+       struct Object *ob; /* owner object */
+       
+       int opflag; /* current operator flag */
+} BMesh;
+
+#define BM_VERT                1
+#define BM_EDGE                2
+#define BM_LOOP                4
+#define BM_FACE                8
+
+#endif /* __BMESH_CLASS_H__ */
diff --git a/source/blender/bmesh/bmesh_error.h b/source/blender/bmesh/bmesh_error.h
new file mode 100644 (file)
index 0000000..26f499a
--- /dev/null
@@ -0,0 +1,72 @@
+/*
+ * ***** BEGIN GPL 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.
+ *
+ * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Joseph Eagar.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_ERROR_H__
+#define __BMESH_ERROR_H__
+
+/** \file blender/bmesh/bmesh_error.h
+ *  \ingroup bmesh
+ */
+
+/*----------- bmop error system ----------*/
+
+/* pushes an error onto the bmesh error stack.
+ * if msg is null, then the default message for the errorcode is used.*/
+void BMO_error_raise(BMesh *bm, BMOperator *owner, int errcode, const char *msg);
+
+/* gets the topmost error from the stack.
+ * returns error code or 0 if no error.*/
+int BMO_error_get(BMesh *bm, const char **msg, BMOperator **op);
+int BMO_error_occurred(BMesh *bm);
+
+/* same as geterror, only pops the error off the stack as well */
+int BMO_error_pop(BMesh *bm, const char **msg, BMOperator **op);
+void BMO_error_clear(BMesh *bm);
+
+#if 0
+//this is meant for handling errors, like self-intersection test failures.
+//it's dangerous to handle errors in general though, so disabled for now.
+
+/* catches an error raised by the op pointed to by catchop.
+ * errorcode is either the errorcode, or BMERR_ALL for any
+ * error.*/
+int BMO_error_catch_op(BMesh *bm, BMOperator *catchop, int errorcode, char **msg);
+#endif
+
+#define BM_ELEM_INDEX_VALIDATE(_bm, _msg_a, _msg_b) \
+       BM_mesh_elem_index_validate(_bm, __FILE__ ":" STRINGIFY(__LINE__), __func__, _msg_a, _msg_b)
+
+/*------ error code defines -------*/
+
+/*error messages*/
+#define BMERR_SELF_INTERSECTING                        1
+#define BMERR_DISSOLVEDISK_FAILED              2
+#define BMERR_CONNECTVERT_FAILED               3
+#define BMERR_WALKER_FAILED                            4
+#define BMERR_DISSOLVEFACES_FAILED             5
+#define BMERR_DISSOLVEVERTS_FAILED             6
+#define BMERR_TESSELATION                              7
+#define BMERR_NONMANIFOLD                              8
+#define BMERR_INVALID_SELECTION                        9
+#define BMERR_MESH_ERROR                               10
+
+#endif /* __BMESH_ERROR_H__ */
diff --git a/source/blender/bmesh/bmesh_iterators.h b/source/blender/bmesh/bmesh_iterators.h
new file mode 100644 (file)
index 0000000..51df946
--- /dev/null
@@ -0,0 +1,136 @@
+/*
+ * ***** BEGIN GPL 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.
+ *
+ * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Joseph Eagar.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_ITERATORS_H__
+#define __BMESH_ITERATORS_H__
+
+/** \file blender/bmesh/bmesh_iterators.h
+ *  \ingroup bmesh
+ */
+
+/*
+ * BMESH ITERATORS
+ *
+ * The functions and structures in this file
+ * provide a unified method for iterating over
+ * the elements of a mesh and answering simple
+ * adjacency queries. Tool authors should use
+ * the iterators provided in this file instead
+ * of inspecting the structure directly.
+ *
+*/
+
+#include "BLI_mempool.h"
+
+/* Defines for passing to BM_iter_new.
+ *
+ * "OF" can be substituted for "around"
+ * so BM_VERTS_OF_FACE means "vertices
+ * around a face."
+ */
+
+/* these iterator over all elements of a specific
+ * type in the mesh.*/
+#define BM_VERTS_OF_MESH                       1
+#define BM_EDGES_OF_MESH                       2
+#define BM_FACES_OF_MESH                       3
+
+/*these are topological iterators.*/
+#define BM_EDGES_OF_VERT                       4
+#define BM_FACES_OF_VERT                       5
+#define BM_LOOPS_OF_VERT                       6
+#define BM_FACES_OF_EDGE                       7
+#define BM_VERTS_OF_FACE                       8
+#define BM_EDGES_OF_FACE                       9
+#define BM_LOOPS_OF_FACE                       10
+/* returns elements from all boundaries, and returns
+ * the first element at the end to flag that we're entering
+ * a different face hole boundary*/
+#define BM_ALL_LOOPS_OF_FACE           11
+
+/* iterate through loops around this loop, which are fetched
+ * from the other faces in the radial cycle surrounding the
+ * input loop's edge.*/
+#define BM_LOOPS_OF_LOOP               12
+#define BM_LOOPS_OF_EDGE               13
+
+#define BM_ITER(ele, iter, bm, itype, data)                                   \
+       ele = BM_iter_new(iter, bm, itype, data);                                 \
+       for ( ; ele; ele=BM_iter_step(iter))
+
+#define BM_ITER_INDEX(ele, iter, bm, itype, data, indexvar)                   \
+       ele = BM_iter_new(iter, bm, itype, data);                                 \
+       for (indexvar=0; ele; indexvar++, ele=BM_iter_step(iter))
+
+/*Iterator Structure*/
+typedef struct BMIter {
+       BLI_mempool_iter pooliter;
+
+       struct BMVert *firstvert, *nextvert, *vdata;
+       struct BMEdge *firstedge, *nextedge, *edata;
+       struct BMLoop *firstloop, *nextloop, *ldata, *l;
+       struct BMFace *firstpoly, *nextpoly, *pdata;
+       struct BMesh *bm;
+       void (*begin)(struct BMIter *iter);
+       void *(*step)(struct BMIter *iter);
+       union {
+               void       *p;
+               int         i;
+               long        l;
+               float       f;
+       } filter;
+       int count;
+       char itype;
+} BMIter;
+
+void *BM_iter_at_index(struct BMesh *bm, const char htype, void *data, int index);
+int   BM_iter_as_array(struct BMesh *bm, const char htype, void *data, void **array, const int len);
+
+/* private for bmesh_iterators_inline.c */
+void  bmiter__vert_of_mesh_begin(struct BMIter *iter);
+void *bmiter__vert_of_mesh_step(struct BMIter *iter);
+void  bmiter__edge_of_mesh_begin(struct BMIter *iter);
+void *bmiter__edge_of_mesh_step(struct BMIter *iter);
+void  bmiter__face_of_mesh_begin(struct BMIter *iter);
+void *bmiter__face_of_mesh_step(struct BMIter *iter);
+void  bmiter__edge_of_vert_begin(struct BMIter *iter);
+void *bmiter__edge_of_vert_step(struct BMIter *iter);
+void  bmiter__face_of_vert_begin(struct BMIter *iter);
+void *bmiter__face_of_vert_step(struct BMIter *iter);
+void  bmiter__loop_of_vert_begin(struct BMIter *iter);
+void *bmiter__loop_of_vert_step(struct BMIter *iter);
+void  bmiter__loops_of_edge_begin(struct BMIter *iter);
+void *bmiter__loops_of_edge_step(struct BMIter *iter);
+void  bmiter__loops_of_loop_begin(struct BMIter *iter);
+void *bmiter__loops_of_loop_step(struct BMIter *iter);
+void  bmiter__face_of_edge_begin(struct BMIter *iter);
+void *bmiter__face_of_edge_step(struct BMIter *iter);
+void  bmiter__vert_of_face_begin(struct BMIter *iter);
+void *bmiter__vert_of_face_step(struct BMIter *iter);
+void  bmiter__edge_of_face_begin(struct BMIter *iter);
+void *bmiter__edge_of_face_step(struct BMIter *iter);
+void  bmiter__loop_of_face_begin(struct BMIter *iter);
+void *bmiter__loop_of_face_step(struct BMIter *iter);
+
+#include "intern/bmesh_iterators_inline.c"
+
+#endif /* __BMESH_ITERATORS_H__ */
diff --git a/source/blender/bmesh/bmesh_marking.h b/source/blender/bmesh/bmesh_marking.h
new file mode 100644 (file)
index 0000000..9b45ac1
--- /dev/null
@@ -0,0 +1,75 @@
+/*
+ * ***** BEGIN GPL 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.
+ *
+ * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Joseph Eagar.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_MARKING_H__
+#define __BMESH_MARKING_H__
+
+/** \file blender/bmesh/bmesh_marking.h
+ *  \ingroup bmesh
+ */
+
+typedef struct BMEditSelection
+{
+       struct BMEditSelection *next, *prev;
+       void *data;
+       char htype;
+} BMEditSelection;
+
+/* geometry hiding code */
+void BM_elem_hide_set(BMesh *bm, void *element, int hide);
+void BM_vert_hide_set(BMesh *bm, BMVert *v, int hide);
+void BM_edge_hide_set(BMesh *bm, BMEdge *e, int hide);
+void BM_face_hide_set(BMesh *bm, BMFace *f, int hide);
+
+/* Selection code */
+void BM_elem_select_set(struct BMesh *bm, void *element, int select);
+
+/* use BM_elem_flag_test(ele, BM_ELEM_SELECT) to test selection */
+
+void BM_mesh_elem_flag_enable_all(BMesh *bm, const char htype, const char hflag);
+void BM_mesh_elem_flag_disable_all(BMesh *bm, const char htype, const char hflag);
+
+/* individual element select functions, BM_elem_select_set is a shortcut for these
+ * that automatically detects which one to use*/
+void BM_vert_select_set(struct BMesh *bm, struct BMVert *v, int select);
+void BM_edge_select_set(struct BMesh *bm, struct BMEdge *e, int select);
+void BM_face_select_set(struct BMesh *bm, struct BMFace *f, int select);
+
+void BM_select_mode_set(struct BMesh *bm, int selectmode);
+
+/* counts number of elements with flag set */
+int BM_mesh_count_flag(struct BMesh *bm, const char htype, const char hflag, int respecthide);
+
+/* edit selection stuff */
+void    BM_active_face_set(BMesh *em, BMFace *f);
+BMFace *BM_active_face_get(BMesh *bm, int sloppy);
+void BM_editselection_center(BMesh *bm, float r_center[3], BMEditSelection *ese);
+void BM_editselection_normal(float r_normal[3], BMEditSelection *ese);
+void BM_editselection_plane(BMesh *bm, float r_plane[3], BMEditSelection *ese);
+
+int  BM_select_history_check(BMesh *bm, void *data);
+void BM_select_history_remove(BMesh *bm, void *data);
+void BM_select_history_store(BMesh *bm, void *data);
+void BM_select_history_validate(BMesh *bm);
+void BM_select_history_clear(BMesh *em);
+
+#endif /* __BMESH_MARKING_H__ */
diff --git a/source/blender/bmesh/bmesh_operator_api.h b/source/blender/bmesh/bmesh_operator_api.h
new file mode 100644 (file)
index 0000000..7bbb579
--- /dev/null
@@ -0,0 +1,555 @@
+/*
+ * ***** BEGIN GPL 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.
+ *
+ * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Joseph Eagar.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_OPERATOR_API_H__
+#define __BMESH_OPERATOR_API_H__
+
+/** \file blender/bmesh/bmesh_operator_api.h
+ *  \ingroup bmesh
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include "BLI_memarena.h"
+#include "BLI_ghash.h"
+
+#include "BKE_utildefines.h"
+
+#include <stdarg.h>
+#include <string.h> /* for memcpy */
+
+/*
+ * operators represent logical, executable mesh modules.  all topological
+ * operations involving a bmesh has to go through them.
+ *
+ * operators are nested, as are tool flags, which are private to an operator
+ * when it's executed.  tool flags are allocated in layers, one per operator
+ * execution, and are used for all internal flagging a tool needs to do.
+ *
+ * each operator has a series of "slots," which can be of the following types:
+ * - simple numerical types
+ * - arrays of elements (e.g. arrays of faces).
+ * - hash mappings.
+ *
+ * each slot is identified by a slot code, as are each operator.
+ * operators, and their slots, are defined in bmesh_opdefines.c (with their
+ * execution functions prototyped in bmesh_operators_private.h), with all their
+ * operator code and slot codes defined in bmesh_operators.h.  see
+ * bmesh_opdefines.c and the BMOpDefine struct for how to define new operators.
+ *
+ * in general, operators are fed arrays of elements, created using either
+ * BM_HeaderFlag_To_Slot or BM_Flag_To_Slot (or through one of the format
+ * specifyers in BMO_op_callf or BMO_op_initf).  Note that multiple element
+ * types (e.g. faces and edges) can be fed to the same slot array.  Operators
+ * act on this data, and possibly spit out data into output slots.
+ *
+ * some notes:
+ * - operators should never read from header flags (e.g. element->head.flag). for
+ *   example, if you want an operator to only operate on selected faces, you
+ *   should use BM_HeaderFlag_To_Slot to put the selected elements into a slot.
+ * - when you read from an element slot array or mapping, you can either tool-flag
+ *   all the elements in it, or read them using an iterator APi (which is
+ *   semantically similar to the iterator api in bmesh_iterators.h).
+ */
+
+struct GHashIterator;
+
+/* slot type arrays are terminated by the last member
+ * having a slot type of 0.*/
+#define BMO_OP_SLOT_SENTINEL   0
+#define BMO_OP_SLOT_INT                        1
+#define BMO_OP_SLOT_FLT                        2
+#define BMO_OP_SLOT_PNT                        3
+#define BMO_OP_SLOT_MAT                        4
+#define BMO_OP_SLOT_VEC                        7
+
+/* after BMO_OP_SLOT_VEC, everything is
+
+ * dynamically allocated arrays.  we
+ * leave a space in the identifiers
+ * for future growth.
+ */
+//it's very important this remain a power of two
+#define BMO_OP_SLOT_ELEMENT_BUF                8
+#define BMO_OP_SLOT_MAPPING                    9
+/* #define BMO_OP_SLOT_TOTAL_TYPES             10 */ /* not used yet */
+
+/* please ignore all these structures, don't touch them in tool code, except
+ * for when your defining an operator with BMOpDefine.*/
+
+typedef struct BMOpSlot{
+       int slottype;
+       int len;
+       int flag;
+       int index; /* index within slot array */
+       union {
+               int i;
+               float f;
+               void *p;
+               float vec[3];
+               void *buf;
+               GHash *ghash;
+       } data;
+} BMOpSlot;
+
+#define BMO_OP_MAX_SLOTS 16 /* way more than probably needed */
+
+#ifdef slots
+#undef slots
+#endif
+
+typedef struct BMOperator {
+       int type;
+       int slottype;
+       int needflag;
+       int flag;
+       struct BMOpSlot slots[BMO_OP_MAX_SLOTS];
+       void (*exec)(struct BMesh *bm, struct BMOperator *op);
+       MemArena *arena;
+} BMOperator;
+
+#define MAX_SLOTNAME   32
+
+typedef struct BMOSlotType {
+       int type;
+       char name[MAX_SLOTNAME];
+} BMOSlotType;
+
+typedef struct BMOpDefine {
+       const char *name;
+       BMOSlotType slottypes[BMO_OP_MAX_SLOTS];
+       void (*exec)(BMesh *bm, BMOperator *op);
+       int flag;
+} BMOpDefine;
+
+/* BMOpDefine->flag */
+#define BMO_OP_FLAG_UNTAN_MULTIRES             1 /*switch from multires tangent space to absolute coordinates*/
+
+/* ensures consistent normals before operator execution,
+ * restoring the original ones windings/normals afterwards.
+ * keep in mind, this won't work if the input mesh isn't
+ * manifold.*/
+#define BMO_OP_FLAG_RATIONALIZE_NORMALS 2
+
+/*------------- Operator API --------------*/
+
+/* data types that use pointers (arrays, etc) should never
+ * have it set directly.  and never use BMO_slot_ptr_set to
+ * pass in a list of edges or any arrays, really.*/
+
+void BMO_op_init(struct BMesh *bm, struct BMOperator *op, const char *opname);
+
+/* executes an operator, pushing and popping a new tool flag
+ * layer as appropriate.*/
+void BMO_op_exec(struct BMesh *bm, struct BMOperator *op);
+
+/* finishes an operator (though note the operator's tool flag is removed
+ * after it finishes executing in BMO_op_exec).*/
+void BMO_op_finish(struct BMesh *bm, struct BMOperator *op);
+
+
+/* tool flag API. never, ever ever should tool code put junk in
+ * header flags (element->head.flag), nor should they use
+ * element->head.eflag1/eflag2.  instead, use this api to set
+ * flags.
+ *
+ * if you need to store a value per element, use a
+ * ghash or a mapping slot to do it. */
+
+/* flags 15 and 16 (1<<14 and 1<<15) are reserved for bmesh api use */
+#define BMO_elem_flag_test(bm, element, oflag)    ((element)->oflags[bm->stackdepth-1].f &   (oflag))
+#define BMO_elem_flag_enable(bm, element, oflag)  ((element)->oflags[bm->stackdepth-1].f |=  (oflag))
+#define BMO_elem_flag_disable(bm, element, oflag) ((element)->oflags[bm->stackdepth-1].f &= ~(oflag))
+#define BMO_elem_flag_toggle(bm, element, oflag)  ((element)->oflags[bm->stackdepth-1].f ^=  (oflag))
+
+/* profiling showed a significant amount of time spent in BMO_elem_flag_test */
+#if 0
+void BMO_elem_flag_enable(struct BMesh *bm, void *element, const short oflag);
+void BMO_elem_flag_disable(struct BMesh *bm, void *element, const short oflag);
+int BMO_elem_flag_test(struct BMesh *bm, void *element, const short oflag);
+#endif
+
+/* count the number of elements with a specific flag.
+ * type can be a bitmask of BM_FACE, BM_EDGE, or BM_FACE. */
+int BMO_mesh_flag_count(struct BMesh *bm, const short oflag, const char htype);
+
+/*---------formatted operator initialization/execution-----------*/
+/*
+ * this system is used to execute or initialize an operator,
+ * using a formatted-string system.
+ *
+ * for example, BMO_op_callf(bm, "del geom=%hf context=%d", BM_ELEM_SELECT, DEL_FACES);
+ * . . .will execute the delete operator, feeding in selected faces, deleting them.
+ *
+ * the basic format for the format string is:
+ *   [operatorname] [slotname]=%[code] [slotname]=%[code]
+ *
+ * as in printf, you pass in one additional argument to the function
+ * for every code.
+ *
+ * the formatting codes are:
+ *    %d - put int in slot
+ *    %f - put float in slot
+ *    %p - put pointer in slot
+ *    %h[f/e/v] - put elements with a header flag in slot.
+ *                 the letters after %h define which element types to use,
+ *             so e.g. %hf will do faces, %hfe will do faces and edges,
+ *             %hv will do verts, etc.  must pass in at least one
+ *             element type letter.
+ *    %f[f/e/v] - same as %h, except it deals with tool flags instead of
+ *                 header flags.
+ *    %a[f/e/v] - pass all elements (of types specified by f/e/v) to the
+ *                 slot.
+ *    %e        - pass in a single element.
+ *    %v - pointer to a float vector of length 3.
+ *    %m[3/4] - matrix, 3/4 refers to the matrix size, 3 or 4.  the
+ *              corrusponding argument must be a pointer to
+ *          a float matrix.
+ *    %s - copy a slot from another op, instead of mapping to one
+ *         argument, it maps to two, a pointer to an operator and
+ *     a slot name.
+ */
+void BMO_push(BMesh *bm, BMOperator *op);
+void BMO_pop(BMesh *bm);
+
+/*executes an operator*/
+int BMO_op_callf(BMesh *bm, const char *fmt, ...);
+
+/* initializes, but doesn't execute an operator.  this is so you can
+ * gain access to the outputs of the operator.  note that you have
+ * to execute/finitsh (BMO_op_exec and BMO_op_finish) yourself. */
+int BMO_op_initf(BMesh *bm, BMOperator *op, const char *fmt, ...);
+
+/* va_list version, used to implement the above two functions,
+ * plus EDBM_CallOpf in bmeshutils.c. */
+int BMO_op_vinitf(BMesh *bm, BMOperator *op, const char *fmt, va_list vlist);
+
+/* test whether a named slot exists */
+int BMO_slot_exists(struct BMOperator *op, const char *slotname);
+
+/* get a pointer to a slot.  this may be removed layer on from the public API. */
+BMOpSlot *BMO_slot_get(struct BMOperator *op, const char *slotname);
+
+/* copies the data of a slot from one operator to another.  src and dst are the
+ * source/destination slot codes, respectively. */
+void BMO_slot_copy(struct BMOperator *source_op, struct BMOperator *dest_op,
+                   const char *src, const char *dst);
+
+/* remove tool flagged elements */
+void BMO_remove_tagged_faces(struct BMesh *bm, const short oflag);
+void BMO_remove_tagged_edges(struct BMesh *bm, const short oflag);
+void BMO_remove_tagged_verts(struct BMesh *bm, const short oflag);
+
+/* take care, uses operator flag DEL_WIREVERT */
+void BMO_remove_tagged_context(BMesh *bm, const short oflag, const int type);
+
+/* del "context" slot values, used for operator too */
+enum {
+       DEL_VERTS = 1,
+       DEL_EDGES,
+       DEL_ONLYFACES,
+       DEL_EDGESFACES,
+       DEL_FACES,
+       DEL_ALL ,
+       DEL_ONLYTAGGED
+};
+
+void BMO_op_flag_enable(struct BMesh *bm, struct BMOperator *op, const int op_flag);
+void BMO_op_flag_disable(struct BMesh *bm, struct BMOperator *op, const int op_flag);
+
+void  BMO_slot_float_set(struct BMOperator *op, const char *slotname, const float f);
+float BMO_slot_float_get(BMOperator *op, const char *slotname);
+void  BMO_slot_int_set(struct BMOperator *op, const char *slotname, const int i);
+int   BMO_slot_int_get(BMOperator *op, const char *slotname);
+
+/* don't pass in arrays that are supposed to map to elements this way.
+ *
+ * so, e.g. passing in list of floats per element in another slot is bad.
+ * passing in, e.g. pointer to an editmesh for the conversion operator is fine
+ * though. */
+void  BMO_slot_ptr_set(struct BMOperator *op, const char *slotname, void *p);
+void *BMO_slot_ptr_get(BMOperator *op, const char *slotname);
+void  BMO_slot_vec_set(struct BMOperator *op, const char *slotname, const float vec[3]);
+void  BMO_slot_vec_get(BMOperator *op, const char *slotname, float r_vec[3]);
+
+/* only supports square mats */
+/* size must be 3 or 4; this api is meant only for transformation matrices.
+ * note that internally the matrix is stored in 4x4 form, and it's safe to
+ * call whichever BMO_Get_Mat* function you want. */
+void BMO_slot_mat_set(struct BMOperator *op, const char *slotname, const float *mat, int size);
+void BMO_slot_mat4_get(struct BMOperator *op, const char *slotname, float r_mat[4][4]);
+void BMO_slot_mat3_set(struct BMOperator *op, const char *slotname, float r_mat[3][3]);
+
+void BMO_mesh_flag_disable_all(BMesh *bm, BMOperator *op, const char htype, const short oflag);
+
+/* puts every element of type type (which is a bitmask) with tool flag flag,
+ * into a slot. */
+void BMO_slot_from_flag(struct BMesh *bm, struct BMOperator *op, const char *slotname,
+                        const short oflag, const char htype);
+
+/* tool-flags all elements inside an element slot array with flag flag. */
+void BMO_slot_buffer_flag_enable(struct BMesh *bm, struct BMOperator *op, const char *slotname,
+                          const short oflag, const char htype);
+/* clears tool-flag flag from all elements inside a slot array. */
+void BMO_slot_buffer_flag_disable(struct BMesh *bm, struct BMOperator *op, const char *slotname,
+                                const short oflag, const char htype);
+
+/* tool-flags all elements inside an element slot array with flag flag. */
+void BMO_slot_buffer_hflag_enable(struct BMesh *bm, struct BMOperator *op, const char *slotname,
+                                  const char hflag, const char htype);
+/* clears tool-flag flag from all elements inside a slot array. */
+void BMO_slot_buffer_hflag_disable(struct BMesh *bm, struct BMOperator *op, const char *slotname,
+                                   const char hflag, const char htype);
+
+/* puts every element of type type (which is a bitmask) with header flag
+ * flag, into a slot.  note: ignores hidden elements (e.g. elements with
+ * header flag BM_ELEM_HIDDEN set).*/
+void BMO_slot_from_hflag(struct BMesh *bm, struct BMOperator *op, const char *slotname,
+                         const char hflag, const char htype);
+
+/* counts number of elements inside a slot array. */
+int BMO_slot_buf_count(struct BMesh *bm, struct BMOperator *op, const char *slotname);
+int BMO_slot_map_count(struct BMesh *bm, struct BMOperator *op, const char *slotname);
+
+/* Counts the number of edges with tool flag toolflag around
+ */
+int BMO_vert_edge_flags_count(BMesh *bm, BMVert *v, const short oflag);
+
+/* inserts a key/value mapping into a mapping slot.  note that it copies the
+ * value, it doesn't store a reference to it. */
+
+#if 0
+
+BM_INLINE void BMO_slot_map_insert(BMesh *bm, BMOperator *op, const char *slotname,
+                                   void *element, void *data, int len);
+
+/* inserts a key/float mapping pair into a mapping slot. */
+BM_INLINE void BMO_slot_map_float_insert(BMesh *bm, BMOperator *op, const char *slotname,
+                                         void *element, float val);
+
+/* returns 1 if the specified pointer is in the map. */
+BM_INLINE int BMO_slot_map_contains(BMesh *bm, BMOperator *op, const char *slotname, void *element);
+
+/* returns a point to the value of a specific key. */
+BM_INLINE void *BMO_slot_map_data_get(BMesh *bm, BMOperator *op, const char *slotname, void *element);
+
+/* returns the float part of a key/float pair. */
+BM_INLINE float BMO_slot_map_float_get(BMesh *bm, BMOperator *op, const char *slotname, void *element);
+
+#endif
+
+/* flags all elements in a mapping.  note that the mapping must only have
+ * bmesh elements in it.*/
+void BMO_slot_map_to_flag(struct BMesh *bm, struct BMOperator *op,
+                          const char *slotname, const short oflag);
+
+/* pointer versoins of BMO_slot_map_float_get and BMO_slot_map_float_insert.
+ *
+ * do NOT use these for non-operator-api-allocated memory! instead
+ * use BMO_slot_map_data_get and BMO_slot_map_insert, which copies the data. */
+
+#if 0
+BM_INLINE void BMO_slot_map_ptr_insert(BMesh *bm, BMOperator *op, const char *slotname, void *key, void *val);
+BM_INLINE void *BMO_slot_map_ptr_get(BMesh *bm, BMOperator *op, const char *slotname, void *key);
+#endif
+
+/* this part of the API is used to iterate over element buffer or
+ * mapping slots.
+ *
+ * for example, iterating over the faces in a slot is:
+ *
+ *    BMOIter oiter;
+ *    BMFace *f;
+ *
+ *    f = BMO_iter_new(&oiter, bm, some_operator, "slotname", BM_FACE);
+ *    for (; f; f=BMO_iter_step(&oiter)) {
+ *        /do something with the face
+ *    }
+ *
+ * another example, iterating over a mapping:
+ *    BMOIter oiter;
+ *    void *key;
+ *    void *val;
+ *
+ *    key = BMO_iter_new(&oiter, bm, some_operator, "slotname", 0);
+ *    for (; key; key=BMO_iter_step(&oiter)) {
+ *        val = BMO_iter_map_value(&oiter);
+ *        //do something with the key/val pair
+ *        //note that val is a pointer to the val data,
+ *        //whether it's a float, pointer, whatever.
+ *        //
+ *        // so to get a pointer, for example, use:
+ *        //  *((void**)BMO_iter_map_value(&oiter));
+ *        //or something like that.
+ *    }
+ */
+
+/* contents of this structure are private,
+ * don't directly access. */
+typedef struct BMOIter {
+       BMOpSlot *slot;
+       int cur; //for arrays
+       struct GHashIterator giter;
+       void *val;
+       char restrictmask; /* bitwise '&' with BMHeader.htype */
+} BMOIter;
+
+void *BMO_slot_elem_first(BMOperator *op, const char *slotname);
+
+/* restrictmask restricts the iteration to certain element types
+ * (e.g. combination of BM_VERT, BM_EDGE, BM_FACE), if iterating
+ * over an element buffer (not a mapping).*/
+void *BMO_iter_new(BMOIter *iter, BMesh *bm, BMOperator *op,
+                   const char *slotname, const char restrictmask);
+void *BMO_iter_step(BMOIter *iter);
+
+/* returns a pointer to the key value when iterating over mappings.
+ * remember for pointer maps this will be a pointer to a pointer.*/
+void *BMO_iter_map_value(BMOIter *iter);
+
+/* use this for pointer mappings */
+void *BMO_iter_map_value_p(BMOIter *iter);
+
+/* use this for float mappings */
+float BMO_iter_map_value_f(BMOIter *iter);
+
+#define BMO_ITER(ele, iter, bm, op, slotname, restrict)   \
+       ele = BMO_iter_new(iter, bm, op, slotname, restrict); \
+       for ( ; ele; ele=BMO_iter_step(iter))
+
+/******************* Inlined Functions********************/
+typedef void (*opexec)(struct BMesh *bm, struct BMOperator *op);
+
+/* mappings map elements to data, which
+ * follows the mapping struct in memory. */
+typedef struct BMOElemMapping {
+       BMHeader *element;
+       int len;
+} BMOElemMapping;
+
+extern const int BMO_OPSLOT_TYPEINFO[];
+
+BM_INLINE void BMO_slot_map_insert(BMesh *UNUSED(bm), BMOperator *op, const char *slotname,
+                                   void *element, void *data, int len)
+{
+       BMOElemMapping *mapping;
+       BMOpSlot *slot = BMO_slot_get(op, slotname);
+
+       /*sanity check*/
+       if (slot->slottype != BMO_OP_SLOT_MAPPING) {
+               return;
+       }
+
+       mapping = (BMOElemMapping *) BLI_memarena_alloc(op->arena, sizeof(*mapping) + len);
+
+       mapping->element = (BMHeader*) element;
+       mapping->len = len;
+       memcpy(mapping + 1, data, len);
+
+       if (!slot->data.ghash) {
+               slot->data.ghash = BLI_ghash_new(BLI_ghashutil_ptrhash,
+                                                BLI_ghashutil_ptrcmp, "bmesh op");
+       }
+
+       BLI_ghash_insert(slot->data.ghash, element, mapping);
+}
+
+BM_INLINE void BMO_slot_map_int_insert(BMesh *bm, BMOperator *op, const char *slotname,
+                                       void *element, int val)
+{
+       BMO_slot_map_insert(bm, op, slotname, element, &val, sizeof(int));
+}
+
+BM_INLINE void BMO_slot_map_float_insert(BMesh *bm, BMOperator *op, const char *slotname,
+                                         void *element, float val)
+{
+       BMO_slot_map_insert(bm, op, slotname, element, &val, sizeof(float));
+}
+
+BM_INLINE void BMO_slot_map_ptr_insert(BMesh *bm, BMOperator *op, const char *slotname,
+                                       void *element, void *val)
+{
+       BMO_slot_map_insert(bm, op, slotname, element, &val, sizeof(void*));
+}
+
+BM_INLINE int BMO_slot_map_contains(BMesh *UNUSED(bm), BMOperator *op, const char *slotname, void *element)
+{
+       BMOpSlot *slot = BMO_slot_get(op, slotname);
+
+       /*sanity check*/
+       if (slot->slottype != BMO_OP_SLOT_MAPPING) return 0;
+       if (!slot->data.ghash) return 0;
+
+       return BLI_ghash_haskey(slot->data.ghash, element);
+}
+
+BM_INLINE void *BMO_slot_map_data_get(BMesh *UNUSED(bm), BMOperator *op, const char *slotname,
+                                      void *element)
+{
+       BMOElemMapping *mapping;
+       BMOpSlot *slot = BMO_slot_get(op, slotname);
+
+       /*sanity check*/
+       if (slot->slottype != BMO_OP_SLOT_MAPPING) return NULL;
+       if (!slot->data.ghash) return NULL;
+
+       mapping = (BMOElemMapping *)BLI_ghash_lookup(slot->data.ghash, element);
+
+       if (!mapping) return NULL;
+
+       return mapping + 1;
+}
+
+BM_INLINE float BMO_slot_map_float_get(BMesh *bm, BMOperator *op, const char *slotname,
+                                       void *element)
+{
+       float *val = (float*) BMO_slot_map_data_get(bm, op, slotname, element);
+       if (val) return *val;
+
+       return 0.0f;
+}
+
+BM_INLINE int BMO_slot_map_int_get(BMesh *bm, BMOperator *op, const char *slotname,
+                                   void *element)
+{
+       int *val = (int*) BMO_slot_map_data_get(bm, op, slotname, element);
+       if (val) return *val;
+
+       return 0;
+}
+
+BM_INLINE void *BMO_slot_map_ptr_get(BMesh *bm, BMOperator *op, const char *slotname,
+                                     void *element)
+{
+       void **val = (void**) BMO_slot_map_data_get(bm, op, slotname, element);
+       if (val) return *val;
+
+       return NULL;
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __BMESH_OPERATOR_API_H__ */
diff --git a/source/blender/bmesh/bmesh_operators.h b/source/blender/bmesh/bmesh_operators.h
new file mode 100644 (file)
index 0000000..de92f57
--- /dev/null
@@ -0,0 +1,105 @@
+/*
+ * ***** BEGIN GPL 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.
+ *
+ * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Joseph Eagar.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_OPERATORS_H__
+#define __BMESH_OPERATORS_H__
+
+/** \file blender/bmesh/bmesh_operators.h
+ *  \ingroup bmesh
+ */
+
+/*see comments in intern/bmesh_opdefines.c for documentation of specific operators*/
+
+/*--------defines/enumerations for specific operators-------*/
+
+/*quad innervert values*/
+enum {
+       SUBD_INNERVERT,
+       SUBD_PATH,
+       SUBD_FAN,
+       SUBD_STRAIGHT_CUT
+};
+
+/* similar face selection slot values */
+enum {
+       SIMFACE_MATERIAL = 201,
+       SIMFACE_IMAGE,
+       SIMFACE_AREA,
+       SIMFACE_PERIMETER,
+       SIMFACE_NORMAL,
+       SIMFACE_COPLANAR
+};
+
+/* similar edge selection slot values */
+enum {
+       SIMEDGE_LENGTH = 101,
+       SIMEDGE_DIR,
+       SIMEDGE_FACE,
+       SIMEDGE_FACE_ANGLE,
+       SIMEDGE_CREASE,
+       SIMEDGE_SEAM,
+       SIMEDGE_SHARP
+};
+
+/* similar vertex selection slot values */
+enum {
+       SIMVERT_NORMAL = 0,
+       SIMVERT_FACE,
+       SIMVERT_VGROUP
+};
+
+enum {
+       OPUVC_AXIS_X = 1,
+       OPUVC_AXIS_Y
+};
+
+enum {
+       DIRECTION_CW = 1,
+       DIRECTION_CCW
+};
+
+/* vertex path selection values */
+enum {
+       VPATH_SELECT_EDGE_LENGTH = 0,
+       VPATH_SELECT_TOPOLOGICAL
+};
+
+extern BMOpDefine *opdefines[];
+extern int bmesh_total_ops;
+
+/*------specific operator helper functions-------*/
+
+/* executes the duplicate operation, feeding elements of
+ * type flag etypeflag and header flag flag to it.  note,
+ * to get more useful information (such as the mapping from
+ * original to new elements) you should run the dupe op manually.*/
+struct Object;
+struct EditMesh;
+
+#if 0
+void BMO_dupe_from_flag(struct BMesh *bm, int etypeflag, const char hflag);
+#endif
+void BM_mesh_esubdivideflag(struct Object *obedit, BMesh *bm, int flag, float smooth,
+                            float fractal, int beauty, int numcuts, int seltype,
+                            int cornertype, int singleedge, int gridfill, int seed);
+
+#endif /* __BMESH_OPERATORS_H__ */
diff --git a/source/blender/bmesh/bmesh_queries.h b/source/blender/bmesh/bmesh_queries.h
new file mode 100644 (file)
index 0000000..1ae469e
--- /dev/null
@@ -0,0 +1,123 @@
+/*
+ * ***** BEGIN GPL 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.
+ *
+ * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Joseph Eagar.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_QUERIES_H__
+#define __BMESH_QUERIES_H__
+
+/** \file blender/bmesh/bmesh_queries.h
+ *  \ingroup bmesh
+ */
+
+#include <stdio.h>
+
+/* Queries */
+
+/* counts number of elements of type type are in the mesh. */
+int BM_mesh_elem_count(struct BMesh *bm, const char htype);
+
+/*returns true if v is in f*/
+int BM_vert_in_face(struct BMFace *f, struct BMVert *v);
+
+// int BM_verts_in_face(struct BMFace *f, struct BMVert **varr, int len);
+int BM_verts_in_face(struct BMesh *bm, struct BMFace *f, struct BMVert **varr, int len);
+
+int BM_edge_in_face(struct BMFace *f, struct BMEdge *e);
+
+int BM_vert_in_edge(struct BMEdge *e, struct BMVert *v);
+
+int BM_verts_in_edge(struct BMVert *v1, struct BMVert *v2, struct BMEdge *e);
+
+/*get opposing vert from v in edge e.*/
+struct BMVert *BM_edge_other_vert(struct BMEdge *e, struct BMVert *v);
+
+/*finds other loop that shares v with e's loop in f.*/
+struct BMLoop *BM_face_other_loop(BMEdge *e, BMFace *f, BMVert *v);
+
+/*returns the edge existing between v1 and v2, or NULL if there isn't one.*/
+struct BMEdge *BM_edge_exists(struct BMVert *v1, struct BMVert *v2);
+
+
+/*returns number of edges aroudn a vert*/
+int BM_vert_edge_count(struct BMVert *v);
+
+/*returns number of faces around an edge*/
+int BM_edge_face_count(struct BMEdge *e);
+
+/*returns number of faces around a vert.*/
+int BM_vert_face_count(struct BMVert *v);
+
+
+/*returns true if v is a wire vert*/
+int BM_vert_is_wire(struct BMesh *bm, struct BMVert *v);
+
+/*returns true if e is a wire edge*/
+int BM_edge_is_wire(struct BMesh *bm, struct BMEdge *e);
+
+/* returns FALSE if v is part of a non-manifold edge in the mesh,
+ * I believe this includes if it's part of both a wire edge and
+ * a face.*/
+int BM_vert_is_manifold(struct BMesh *bm, struct BMVert *v);
+
+/* returns FALSE if e is shared by more then two faces. */
+int BM_edge_is_manifold(struct BMesh *bm, struct BMEdge *e);
+
+/* returns true if e is a boundary edge, e.g. has only 1 face bordering it. */
+int BM_edge_is_boundry(struct BMEdge *e);
+
+
+/* returns angle of two faces surrounding an edge.  note there must be
+ * exactly two faces sharing the edge.*/
+float BM_edge_face_angle(struct BMesh *bm, struct BMEdge *e);
+
+/* returns angle of two faces surrounding edges.  note there must be
+ * exactly two edges sharing the vertex.*/
+float BM_vert_edge_angle(struct BMesh *bm, struct BMVert *v);
+
+/* checks overlapping of existing faces with the verts in varr. */
+int BM_face_exists_overlap(struct BMesh *bm, struct BMVert **varr, int len, struct BMFace **existface);
+
+/* checks if a face defined by varr already exists. */
+int BM_face_exists(BMesh *bm, BMVert **varr, int len, BMFace **existface);
+
+
+/* returns number of edges f1 and f2 share. */
+int BM_face_share_edges(struct BMFace *f1, struct BMFace *f2);
+
+/* returns number of faces e1 and e2 share. */
+int BM_edge_share_faces(struct BMEdge *e1, struct BMEdge *e2);
+
+/* returns bool 1/0 if the edges share a vertex */
+int BM_edge_share_vert(struct BMEdge *e1, struct BMEdge *e2);
+
+/* edge verts in winding order from face */
+void BM_edge_ordered_verts(struct BMEdge *edge, struct BMVert **r_v1, struct BMVert **r_v2);
+
+/* checks if a face is valid in the data structure */
+int BM_face_validate(BMesh *bm, BMFace *face, FILE *err);
+
+/* each pair of loops defines a new edge, a split.  this function goes
+ * through and sets pairs that are geometrically invalid to null.  a
+ * split is invalid, if it forms a concave angle or it intersects other
+ * edges in the face.*/
+void BM_face_legal_splits(BMesh *bm, BMFace *f, BMLoop *(*loops)[2], int len);
+
+#endif /* __BMESH_QUERIES_H__ */
diff --git a/source/blender/bmesh/bmesh_walkers.h b/source/blender/bmesh/bmesh_walkers.h
new file mode 100644 (file)
index 0000000..a9515db
--- /dev/null
@@ -0,0 +1,139 @@
+/*
+ * ***** BEGIN GPL 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.
+ *
+ * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * Contributor(s): Joseph Eagar.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_WALKERS_H__
+#define __BMESH_WALKERS_H__
+
+/** \file blender/bmesh/bmesh_walkers.h
+ *  \ingroup bmesh
+ */
+
+#include "BLI_ghash.h"
+
+/*
+  NOTE: do NOT modify topology while walking a mesh!
+*/
+
+typedef enum {
+       BMW_DEPTH_FIRST,
+       BMW_BREADTH_FIRST
+} BMWOrder;
+
+/*Walkers*/
+typedef struct BMWalker {
+       void (*begin) (struct BMWalker *walker, void *start);
+       void *(*step) (struct BMWalker *walker);
+       void *(*yield)(struct BMWalker *walker);
+       int structsize;
+       BMWOrder order;
+       int valid_mask;
+
+       /* runtime */
+       int layer;
+
+       BMesh *bm;
+       BLI_mempool *worklist;
+       ListBase states;
+
+       short mask_vert;
+       short mask_edge;
+       short mask_loop;
+       short mask_face;
+
+       GHash *visithash;
+       int depth;
+} BMWalker;
+
+/* define to make BMW_init more clear */
+#define BMW_MASK_NOP 0
+
+/* initialize a walker.  searchmask restricts some (not all) walkers to
+ * elements with a specific tool flag set.  flags is specific to each walker.*/
+void BMW_init(struct BMWalker *walker, BMesh *bm, int type,
+              short mask_vert, short mask_edge, short mask_loop, short mask_face,
+              int layer);
+void *BMW_begin(BMWalker *walker, void *start);
+void *BMW_step(struct BMWalker *walker);
+void  BMW_end(struct BMWalker *walker);
+int   BMW_current_depth(BMWalker *walker);
+
+/*these are used by custom walkers*/
+void *BMW_current_state(BMWalker *walker);
+void *BMW_state_add(BMWalker *walker);
+void  BMW_state_remove(BMWalker *walker);
+void *BMW_walk(BMWalker *walker);
+void  BMW_reset(BMWalker *walker);
+
+/*
+example of usage, walking over an island of tool flagged faces:
+
+BMWalker walker;
+BMFace *f;
+
+BMW_init(&walker, bm, BMW_ISLAND, SOME_OP_FLAG);
+f = BMW_begin(&walker, some_start_face);
+for (; f; f=BMW_step(&walker)) {
+       //do something with f
+}
+BMW_end(&walker);
+*/
+
+enum {
+       /* walk over connected geometry.  can restrict to a search flag,
+        * or not, it's optional.
+        *
+        * takes a vert as an arugment, and spits out edges, restrict flag acts
+        * on the edges as well. */
+       BMW_SHELL,
+       /*walk over an edge loop.  search flag doesn't do anything.*/
+       BMW_LOOP,
+       BMW_FACELOOP,
+       BMW_EDGERING,
+       /* #define BMW_RING     2 */
+       /* walk over uv islands; takes a loop as input.  restrict flag
+        * restricts the walking to loops whose vert has restrict flag set as a
+        * tool flag.
+        *
+        * the flag parameter to BMW_init maps to a loop customdata layer index.
+        */
+       BMW_LOOPDATA_ISLAND,
+       /* walk over an island of flagged faces.  note, that this doesn't work on
+        * non-manifold geometry.  it might be better to rewrite this to extract
+        * boundary info from the island walker, rather then directly walking
+        * over the boundary.  raises an error if it encouters nonmanifold
+        * geometry. */
+       BMW_ISLANDBOUND,
+       /* walk over all faces in an island of tool flagged faces. */
+       BMW_ISLAND,
+       /* walk from a vertex to all connected vertices. */
+       BMW_CONNECTED_VERTEX,
+       /* end of array index enum vals */
+
+       /* do not intitialze function pointers and struct size in BMW_init */
+       BMW_CUSTOM,
+       BMW_MAXWALKERS
+};
+
+/* use with BMW_init, so as not to confuse with restrict flags */
+#define BMW_NIL_LAY  0
+
+#endif /* __BMESH_WALKERS_H__ */
diff --git a/source/blender/bmesh/editmesh_tools.c b/source/blender/bmesh/editmesh_tools.c
new file mode 100644 (file)
index 0000000..93be1ac
--- /dev/null
@@ -0,0 +1,6384 @@
+#if 0
+
+/*
+ * ***** BEGIN GPL 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.
+ *
+ * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2004 by NaN Holding BV.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Johnny Matthews, Geoffrey Bantle.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/*
+
+editmesh_tool.c: UI called tools for editmesh, geometry changes here, otherwise in mods.c
+
+*/
+
+#include <stdlib.h>
+#include <string.h>
+#include <math.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BMF_Api.h"
+#include "DNA_mesh_types.h"
+#include "DNA_material_types.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_modifier_types.h"
+#include "DNA_object_types.h"
+#include "DNA_scene_types.h"
+#include "DNA_screen_types.h"
+#include "DNA_view3d_types.h"
+#include "DNA_key_types.h"
+
+#include "BLI_blenlib.h"
+#include "BLI_math.h"
+#include "BLI_editVert.h"
+#include "BLI_rand.h"
+#include "BLI_ghash.h"
+#include "BLI_linklist.h"
+#include "BLI_heap.h"
+
+#include "BKE_depsgraph.h"
+#include "BKE_customdata.h"
+#include "BKE_global.h"
+#include "BKE_library.h"
+#include "BKE_mesh.h"
+#include "BKE_object.h"
+#include "BKE_utildefines.h"
+#include "BKE_bmesh.h"
+
+#ifdef WITH_VERSE
+#include "BKE_verse.h"
+#endif
+
+#include "BIF_cursors.h"
+#include "BIF_editmesh.h"
+#include "BIF_gl.h"
+#include "BIF_glutil.h"
+#include "BIF_graphics.h"
+#include "BIF_interface.h"
+#include "BIF_mywindow.h"
+#include "BIF_screen.h"
+#include "BIF_space.h"
+#include "BIF_resources.h"
+#include "BIF_toolbox.h"
+#include "BIF_transform.h"
+#include "transform.h"
+
+#ifdef WITH_VERSE
+#include "BIF_verse.h"
+#endif
+
+#include "BDR_drawobject.h"
+#include "BDR_editobject.h"
+
+#include "BSE_view.h"
+#include "BSE_edit.h"
+
+#include "blendef.h"
+#include "multires.h"
+#include "mydevice.h"
+
+#include "editmesh.h"
+
+#include "MTC_vectorops.h"
+
+#include "PIL_time.h"
+
+#include "BLO_sys_types.h" // for intptr_t support
+
+/* local prototypes ---------------*/
+void bevel_menu(void);
+static void free_tagged_edges_faces(EditEdge *eed, EditFace *efa);
+
+/********* qsort routines *********/
+
+
+typedef struct xvertsort {
+       float x;
+       EditVert *v1;
+} xvertsort;
+
+static int vergxco(const void *v1, const void *v2)
+{
+       const xvertsort *x1=v1, *x2=v2;
+
+       if( x1->x > x2->x ) return 1;
+       else if( x1->x < x2->x) return -1;
+       return 0;
+}
+
+struct facesort {
+       uintptr_t x;
+       struct EditFace *efa;
+};
+
+
+static int vergface(const void *v1, const void *v2)
+{
+       const struct facesort *x1=v1, *x2=v2;
+       
+       if( x1->x > x2->x ) return 1;
+       else if( x1->x < x2->x) return -1;
+       return 0;
+}
+
+
+/* *********************************** */
+
+void convert_to_triface(int direction)
+{
+       EditMesh *em = G.editMesh;
+       EditFace *efa, *efan, *next;
+       float fac;
+       
+       if(multires_test()) return;
+       
+       efa= em->faces.last;
+       while(efa) {
+               next= efa->prev;
+               if(efa->v4) {
+                       if(efa->f & SELECT) {
+                               /* choose shortest diagonal for split */
+                               fac= len_v3v3(efa->v1->co, efa->v3->co) - len_v3v3(efa->v2->co, efa->v4->co);
+                               /* this makes sure exact squares get split different in both cases */
+                               if( (direction==0 && fac<FLT_EPSILON) || (direction && fac>0.0f) ) {
+                                       efan= EM_face_from_faces(efa, NULL, 0, 1, 2, -1);
+                                       if(efa->f & SELECT) EM_select_face(efan, 1);
+                                       efan= EM_face_from_faces(efa, NULL, 0, 2, 3, -1);
+                                       if(efa->f & SELECT) EM_select_face(efan, 1);
+                               }
+                               else {
+                                       efan= EM_face_from_faces(efa, NULL, 0, 1, 3, -1);
+                                       if(efa->f & SELECT) EM_select_face(efan, 1);
+                                       efan= EM_face_from_faces(efa, NULL, 1, 2, 3, -1);
+                                       if(efa->f & SELECT) EM_select_face(efan, 1);
+                               }
+                               
+                               BLI_remlink(&em->faces, efa);
+                               free_editface(efa);
+                       }
+               }
+               efa= next;
+       }
+       
+       EM_fgon_flags();        // redo flags and indices for fgons
+
+#ifdef WITH_VERSE
+       if(G.editMesh->vnode)
+               sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
+#endif
+       BIF_undo_push("Convert Quads to Triangles");
+       
+}
+
+int removedoublesflag(short flag, short automerge, float limit)                /* return amount */
+{
+       /*
+               flag -          Test with vert->flags
+               automerge -     Alternative operation, merge unselected into selected.
+                                       Used for "Auto Weld" mode. warning.
+               limit -         Quick manhattan distance between verts.
+       */
+       
+       EditMesh *em = G.editMesh;
+       /* all verts with (flag & 'flag') are being evaluated */
+       EditVert *eve, *v1, *nextve;
+       EditEdge *eed, *e1, *nexted;
+       EditFace *efa, *nextvl;
+       xvertsort *sortblock, *sb, *sb1;
+       struct facesort *vlsortblock, *vsb, *vsb1;
+       int a, b, test, amount;
+       
+       if(multires_test()) return 0;
+
+       
+       /* flag 128 is cleared, count */
+
+       /* Normal non weld operation */
+       eve= em->verts.first;
+       amount= 0;
+       while(eve) {
+               eve->f &= ~128;
+               if(eve->h==0 && (automerge || (eve->f & flag))) amount++;
+               eve= eve->next;
+       }
+       if(amount==0) return 0;
+
+       /* allocate memory and qsort */
+       sb= sortblock= MEM_mallocN(sizeof(xvertsort)*amount,"sortremovedoub");
+       eve= em->verts.first;
+       while(eve) {
+               if(eve->h==0 && (automerge || (eve->f & flag))) {
+                       sb->x= eve->co[0]+eve->co[1]+eve->co[2];
+                       sb->v1= eve;
+                       sb++;
+               }
+               eve= eve->next;
+       }
+       qsort(sortblock, amount, sizeof(xvertsort), vergxco);
+
+       
+       /* test for doubles */
+       sb= sortblock;  
+       if (automerge) {
+               for(a=0; a<amount; a++, sb++) {
+                       eve= sb->v1;
+                       if( (eve->f & 128)==0 ) {
+                               sb1= sb+1;
+                               for(b=a+1; b<amount && (eve->f & 128)==0; b++, sb1++) {
+                                       if(sb1->x - sb->x > limit) break;
+                                       
+                                       /* when automarge, only allow unselected->selected */
+                                       v1= sb1->v1;
+                                       if( (v1->f & 128)==0 ) {
+                                               if ((eve->f & flag)==0 && (v1->f & flag)==1) {
+                                                       if(     (float)fabs(v1->co[0]-eve->co[0])<=limit && 
+                                                               (float)fabs(v1->co[1]-eve->co[1])<=limit &&
+                                                               (float)fabs(v1->co[2]-eve->co[2])<=limit)
+                                                       {       /* unique bit */
+                                                               eve->f|= 128;
+                                                               eve->tmp.v = v1;
+                                                       }
+                                               } else if(      (eve->f & flag)==1 && (v1->f & flag)==0 ) {
+                                                       if(     (float)fabs(v1->co[0]-eve->co[0])<=limit && 
+                                                               (float)fabs(v1->co[1]-eve->co[1])<=limit &&
+                                                               (float)fabs(v1->co[2]-eve->co[2])<=limit)
+                                                       {       /* unique bit */
+                                                               v1->f|= 128;
+                                                               v1->tmp.v = eve;
+                                                       }
+                                               }
+                                       }
+                               }
+                       }
+               }
+       } else {
+               for(a=0; a<amount; a++, sb++) {
+                       eve= sb->v1;
+                       if( (eve->f & 128)==0 ) {
+                               sb1= sb+1;
+                               for(b=a+1; b<amount; b++, sb1++) {
+                                       /* first test: simpel dist */
+                                       if(sb1->x - sb->x > limit) break;
+                                       v1= sb1->v1;
+                                       
+                                       /* second test: is vertex allowed */
+                                       if( (v1->f & 128)==0 ) {
+                                               if(     (float)fabs(v1->co[0]-eve->co[0])<=limit && 
+                                                       (float)fabs(v1->co[1]-eve->co[1])<=limit &&
+                                                       (float)fabs(v1->co[2]-eve->co[2])<=limit)
+                                               {
+                                                       v1->f|= 128;
+                                                       v1->tmp.v = eve;
+                                               }
+                                       }
+                               }
+                       }
+               }
+       }
+       MEM_freeN(sortblock);
+       
+       if (!automerge)
+               for(eve = em->verts.first; eve; eve=eve->next)
+                       if((eve->f & flag) && (eve->f & 128))
+                               EM_data_interp_from_verts(eve, eve->tmp.v, eve->tmp.v, 0.5f);
+       
+       /* test edges and insert again */
+       eed= em->edges.first;
+       while(eed) {
+               eed->f2= 0;
+               eed= eed->next;
+       }
+       eed= em->edges.last;
+       while(eed) {
+               nexted= eed->prev;
+
+               if(eed->f2==0) {
+                       if( (eed->v1->f & 128) || (eed->v2->f & 128) ) {
+                               remedge(eed);
+
+                               if(eed->v1->f & 128) eed->v1 = eed->v1->tmp.v;
+                               if(eed->v2->f & 128) eed->v2 = eed->v2->tmp.v;
+                               e1= addedgelist(eed->v1, eed->v2, eed);
+
+                               if(e1) {
+                                       e1->f2= 1;
+                                       if(eed->f & SELECT)
+                                               e1->f |= SELECT;
+                               }
+                               if(e1!=eed) free_editedge(eed);
+                       }
+               }
+               eed= nexted;
+       }
+
+       /* first count amount of test faces */
+       efa= (struct EditFace *)em->faces.first;
+       amount= 0;
+       while(efa) {
+               efa->f1= 0;
+               if(efa->v1->f & 128) efa->f1= 1;
+               else if(efa->v2->f & 128) efa->f1= 1;
+               else if(efa->v3->f & 128) efa->f1= 1;
+               else if(efa->v4 && (efa->v4->f & 128)) efa->f1= 1;
+               
+               if(efa->f1==1) amount++;
+               efa= efa->next;
+       }
+
+       /* test faces for double vertices, and if needed remove them */
+       efa= (struct EditFace *)em->faces.first;
+       while(efa) {
+               nextvl= efa->next;
+               if(efa->f1==1) {
+                       
+                       if(efa->v1->f & 128) efa->v1= efa->v1->tmp.v;
+                       if(efa->v2->f & 128) efa->v2= efa->v2->tmp.v;
+                       if(efa->v3->f & 128) efa->v3= efa->v3->tmp.v;
+                       if(efa->v4 && (efa->v4->f & 128)) efa->v4= efa->v4->tmp.v;
+               
+                       test= 0;
+                       if(efa->v1==efa->v2) test+=1;
+                       if(efa->v2==efa->v3) test+=2;
+                       if(efa->v3==efa->v1) test+=4;
+                       if(efa->v4==efa->v1) test+=8;
+                       if(efa->v3==efa->v4) test+=16;
+                       if(efa->v2==efa->v4) test+=32;
+                       
+                       if(test) {
+                               if(efa->v4) {
+                                       if(test==1 || test==2) {
+                                               efa->v2= efa->v3;
+                                               efa->v3= efa->v4;
+                                               efa->v4= 0;
+
+                                               EM_data_interp_from_faces(efa, NULL, efa, 0, 2, 3, 3);
+
+                                               test= 0;
+                                       }
+                                       else if(test==8 || test==16) {
+                                               efa->v4= 0;
+                                               test= 0;
+                                       }
+                                       else {
+                                               BLI_remlink(&em->faces, efa);
+                                               free_editface(efa);
+                                               amount--;
+                                       }
+                               }
+                               else {
+                                       BLI_remlink(&em->faces, efa);
+                                       free_editface(efa);
+                                       amount--;
+                               }
+                       }
+                       
+                       if(test==0) {
+                               /* set edge pointers */
+                               efa->e1= findedgelist(efa->v1, efa->v2);
+                               efa->e2= findedgelist(efa->v2, efa->v3);
+                               if(efa->v4==0) {
+                                       efa->e3= findedgelist(efa->v3, efa->v1);
+                                       efa->e4= 0;
+                               }
+                               else {
+                                       efa->e3= findedgelist(efa->v3, efa->v4);
+                                       efa->e4= findedgelist(efa->v4, efa->v1);
+                               }
+                       }
+               }
+               efa= nextvl;
+       }
+
+       /* double faces: sort block */
+       /* count again, now all selected faces */
+       amount= 0;
+       efa= em->faces.first;
+       while(efa) {
+               efa->f1= 0;
+               if(faceselectedOR(efa, 1)) {
+                       efa->f1= 1;
+                       amount++;
+               }
+               efa= efa->next;
+       }
+
+       if(amount) {
+               /* double faces: sort block */
+               vsb= vlsortblock= MEM_mallocN(sizeof(struct facesort)*amount, "sortremovedoub");
+               efa= em->faces.first;
+               while(efa) {
+                       if(efa->f1 & 1) {
+                               if(efa->v4) vsb->x= (uintptr_t) MIN4( (uintptr_t)efa->v1, (uintptr_t)efa->v2, (uintptr_t)efa->v3, (uintptr_t)efa->v4);
+                               else vsb->x= (uintptr_t) MIN3( (uintptr_t)efa->v1, (uintptr_t)efa->v2, (uintptr_t)efa->v3);
+
+                               vsb->efa= efa;
+                               vsb++;
+                       }
+                       efa= efa->next;
+               }
+               
+               qsort(vlsortblock, amount, sizeof(struct facesort), vergface);
+                       
+               vsb= vlsortblock;
+               for(a=0; a<amount; a++) {
+                       efa= vsb->efa;
+                       if( (efa->f1 & 128)==0 ) {
+                               vsb1= vsb+1;
+
+                               for(b=a+1; b<amount; b++) {
+                               
+                                       /* first test: same pointer? */
+                                       if(vsb->x != vsb1->x) break;
+                                       
+                                       /* second test: is test permitted? */
+                                       efa= vsb1->efa;
+                                       if( (efa->f1 & 128)==0 ) {
+                                               if( compareface(efa, vsb->efa)) efa->f1 |= 128;
+                                               
+                                       }
+                                       vsb1++;
+                               }
+                       }
+                       vsb++;
+               }
+               
+               MEM_freeN(vlsortblock);
+               
+               /* remove double faces */
+               efa= (struct EditFace *)em->faces.first;
+               while(efa) {
+                       nextvl= efa->next;
+                       if(efa->f1 & 128) {
+                               BLI_remlink(&em->faces, efa);
+                               free_editface(efa);
+                       }
+                       efa= nextvl;
+               }
+       }
+       
+       /* remove double vertices */
+       a= 0;
+       eve= (struct EditVert *)em->verts.first;
+       while(eve) {
+               nextve= eve->next;
+               if(automerge || eve->f & flag) {
+                       if(eve->f & 128) {
+                               a++;
+                               BLI_remlink(&em->verts, eve);
+                               free_editvert(eve);
+                       }
+               }
+               eve= nextve;
+       }
+
+#ifdef WITH_VERSE
+       if((a>0) && (G.editMesh->vnode)) {
+               sync_all_verseverts_with_editverts((VNode*)G.editMesh->vnode);
+               sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
+       }
+#endif
+
+       return a;       /* amount */
+}
+
+/* called from buttons */
+static void xsortvert_flag__doSetX(void *userData, EditVert *eve, int x, int y, int index)
+{
+       xvertsort *sortblock = userData;
+
+       sortblock[index].x = x;
+}
+void xsortvert_flag(int flag)
+{
+       EditMesh *em = G.editMesh;
+       /* all verts with (flag & 'flag') are sorted */
+       EditVert *eve;
+       xvertsort *sortblock;
+       ListBase tbase;
+       int i, amount = BLI_countlist(&em->verts);
+       
+       if(multires_test()) return;
+       
+       sortblock = MEM_callocN(sizeof(xvertsort)*amount,"xsort");
+       for (i=0,eve=em->verts.first; eve; i++,eve=eve->next)
+               if(eve->f & flag)
+                       sortblock[i].v1 = eve;
+       mesh_foreachScreenVert(xsortvert_flag__doSetX, sortblock, V3D_CLIP_TEST_OFF);
+       qsort(sortblock, amount, sizeof(xvertsort), vergxco);
+       
+               /* make temporal listbase */
+       tbase.first= tbase.last= 0;
+       for (i=0; i<amount; i++) {
+               eve = sortblock[i].v1;
+
+               if (eve) {
+                       BLI_remlink(&em->verts, eve);
+                       BLI_addtail(&tbase, eve);
+               }
+       }
+       
+       addlisttolist(&em->verts, &tbase);
+       
+       MEM_freeN(sortblock);
+
+#ifdef WITH_VERSE
+       if(G.editMesh->vnode)
+               sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
+#endif
+
+       BIF_undo_push("Xsort");
+       
+}
+
+/* called from buttons */
+void hashvert_flag(int flag)
+{
+       /* switch vertex order using hash table */
+       EditMesh *em = G.editMesh;
+       EditVert *eve;
+       struct xvertsort *sortblock, *sb, onth, *newsort;
+       ListBase tbase;
+       int amount, a, b;
+       
+       if(multires_test()) return;
+       
+       /* count */
+       eve= em->verts.first;
+       amount= 0;
+       while(eve) {
+               if(eve->f & flag) amount++;
+               eve= eve->next;
+       }
+       if(amount==0) return;
+       
+       /* allocate memory */
+       sb= sortblock= (struct xvertsort *)MEM_mallocN(sizeof(struct xvertsort)*amount,"sortremovedoub");
+       eve= em->verts.first;
+       while(eve) {
+               if(eve->f & flag) {
+                       sb->v1= eve;
+                       sb++;
+               }
+               eve= eve->next;
+       }
+
+       BLI_srand(1);
+       
+       sb= sortblock;
+       for(a=0; a<amount; a++, sb++) {
+               b= (int)(amount*BLI_drand());
+               if(b>=0 && b<amount) {
+                       newsort= sortblock+b;
+                       onth= *sb;
+                       *sb= *newsort;
+                       *newsort= onth;
+               }
+       }
+
+       /* make temporal listbase */
+       tbase.first= tbase.last= 0;
+       sb= sortblock;
+       while(amount--) {
+               eve= sb->v1;
+               BLI_remlink(&em->verts, eve);
+               BLI_addtail(&tbase, eve);
+               sb++;
+       }
+       
+       addlisttolist(&em->verts, &tbase);
+       
+       MEM_freeN(sortblock);
+#ifdef WITH_VERSE
+       if(G.editMesh->vnode)
+               sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
+#endif
+       BIF_undo_push("Hash");
+
+}
+
+/* generic extern called extruder */
+void extrude_mesh(void)
+{
+       float nor[3]= {0.0, 0.0, 0.0};
+       short nr, transmode= 0;
+
+       TEST_EDITMESH
+       if(multires_test()) return;
+       
+       if(G.scene->selectmode & SCE_SELECT_VERTEX) {
+               if(G.totvertsel==0) nr= 0;
+               else if(G.totvertsel==1) nr= 4;
+               else if(G.totedgesel==0) nr= 4;
+               else if(G.totfacesel==0) 
+                       nr= pupmenu("Extrude %t|Only Edges%x3|Only Vertices%x4");
+               else if(G.totfacesel==1)
+                       nr= pupmenu("Extrude %t|Region %x1|Only Edges%x3|Only Vertices%x4");
+               else 
+                       nr= pupmenu("Extrude %t|Region %x1||Individual Faces %x2|Only Edges%x3|Only Vertices%x4");
+       }
+       else if(G.scene->selectmode & SCE_SELECT_EDGE) {
+               if (G.totedgesel==0) nr = 0;
+               else if (G.totedgesel==1) nr = 3;
+               else if(G.totfacesel==0) nr = 3;
+               else if(G.totfacesel==1)
+                       nr= pupmenu("Extrude %t|Region %x1|Only Edges%x3");
+               else
+                       nr= pupmenu("Extrude %t|Region %x1||Individual Faces %x2|Only Edges%x3");
+       }
+       else {
+               if (G.totfacesel == 0) nr = 0;
+               else if (G.totfacesel == 1) nr = 1;
+               else
+                       nr= pupmenu("Extrude %t|Region %x1||Individual Faces %x2");
+       }
+               
+       if(nr<1) return;
+
+       if(nr==1)  transmode= extrudeflag(SELECT, nor);
+       else if(nr==4) transmode= extrudeflag_verts_indiv(SELECT, nor);
+       else if(nr==3) transmode= extrudeflag_edges_indiv(SELECT, nor);
+       else transmode= extrudeflag_face_indiv(SELECT, nor);
+       
+       if(transmode==0) {
+               error("No valid selection");
+       }
+       else {
+               EM_fgon_flags();
+               countall(); 
+               
+                       /* We need to force immediate calculation here because 
+                       * transform may use derived objects (which are now stale).
+                       *
+                       * This shouldn't be necessary, derived queries should be
+                       * automatically building this data if invalid. Or something.
+                       */
+               DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);     
+               object_handle_update(G.obedit);
+
+               /* individual faces? */
+               BIF_TransformSetUndo("Extrude");
+               if(nr==2) {
+                       initTransform(TFM_SHRINKFATTEN, CTX_NO_PET|CTX_NO_MIRROR);
+                       Transform();
+               }
+               else {
+                       initTransform(TFM_TRANSLATION, CTX_NO_PET|CTX_NO_MIRROR);
+                       if(transmode=='n') {
+                               mul_m4_v3(G.obedit->obmat, nor);
+                               sub_v3_v3v3(nor, nor, G.obedit->obmat[3]);
+                               BIF_setSingleAxisConstraint(nor, "along normal");
+                       }
+                       Transform();
+               }
+       }
+
+}
+
+void split_mesh(void)
+{
+
+       TEST_EDITMESH
+       if(multires_test()) return;
+
+       if(okee(" Split ")==0) return;
+
+       waitcursor(1);
+
+       /* make duplicate first */
+       adduplicateflag(SELECT);
+       /* old faces have flag 128 set, delete them */
+       delfaceflag(128);
+       recalc_editnormals();
+
+       waitcursor(0);
+
+       countall();
+       allqueue(REDRAWVIEW3D, 0);
+       DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
+
+#ifdef WITH_VERSE
+       if(G.editMesh->vnode)
+               sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
+#endif
+
+       BIF_undo_push("Split");
+
+}
+
+void extrude_repeat_mesh(int steps, float offs)
+{
+       float dvec[3], tmat[3][3], bmat[3][3], nor[3]= {0.0, 0.0, 0.0};
+       short a;
+
+       TEST_EDITMESH
+       if(multires_test()) return;
+       
+       /* dvec */
+       dvec[0]= G.vd->persinv[2][0];
+       dvec[1]= G.vd->persinv[2][1];
+       dvec[2]= G.vd->persinv[2][2];
+       normalize_v3(dvec);
+       dvec[0]*= offs;
+       dvec[1]*= offs;
+       dvec[2]*= offs;
+
+       /* base correction */
+       copy_m3_m4(bmat, G.obedit->obmat);
+       invert_m3_m3(tmat, bmat);
+       mul_m3_v3(tmat, dvec);
+
+       for(a=0; a<steps; a++) {
+               extrudeflag(SELECT, nor);
+               translateflag(SELECT, dvec);
+       }
+       
+       recalc_editnormals();
+       
+       EM_fgon_flags();
+       countall();
+       
+       allqueue(REDRAWVIEW3D, 0);
+       DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
+
+       BIF_undo_push("Extrude Repeat");
+}
+
+void spin_mesh(int steps, float degr, float *dvec, int mode)
+{
+       EditMesh *em = G.editMesh;
+       EditVert *eve,*nextve;
+       float nor[3]= {0.0, 0.0, 0.0};
+       float *curs, si,n[3],q[4],cmat[3][3],imat[3][3], tmat[3][3];
+       float cent[3],bmat[3][3];
+       float phi;
+       short a,ok;
+
+       TEST_EDITMESH
+       if(multires_test()) return;
+       
+       /* imat and center and size */
+       copy_m3_m4(bmat, G.obedit->obmat);
+       invert_m3_m3(imat,bmat);
+
+       curs= give_cursor();
+       copy_v3_v3(cent, curs);
+       cent[0]-= G.obedit->obmat[3][0];
+       cent[1]-= G.obedit->obmat[3][1];
+       cent[2]-= G.obedit->obmat[3][2];
+       mul_m3_v3(imat, cent);
+
+       phi= degr*M_PI/360.0;
+       phi/= steps;
+       if(G.scene->toolsettings->editbutflag & B_CLOCKWISE) phi= -phi;
+
+       if(dvec) {
+               n[0]= G.vd->viewinv[1][0];
+               n[1]= G.vd->viewinv[1][1];
+               n[2]= G.vd->viewinv[1][2];
+       } else {
+               n[0]= G.vd->viewinv[2][0];
+               n[1]= G.vd->viewinv[2][1];
+               n[2]= G.vd->viewinv[2][2];
+       }
+       normalize_v3(n);
+
+       q[0]= (float)cos(phi);
+       si= (float)sin(phi);
+       q[1]= n[0]*si;
+       q[2]= n[1]*si;
+       q[3]= n[2]*si;
+       quat_to_mat3( cmat,q);
+
+       mul_m3_m3m3(tmat,cmat,bmat);
+       mul_m3_m3m3(bmat,imat,tmat);
+
+       if(mode==0) if(G.scene->toolsettings->editbutflag & B_KEEPORIG) adduplicateflag(1);
+       ok= 1;
+
+       for(a=0;a<steps;a++) {
+               if(mode==0) ok= extrudeflag(SELECT, nor);
+               else adduplicateflag(SELECT);
+               if(ok==0) {
+                       error("No valid vertices are selected");
+                       break;
+               }
+               rotateflag(SELECT, cent, bmat);
+               if(dvec) {
+                       mul_m3_v3(bmat,dvec);
+                       translateflag(SELECT, dvec);
+               }
+       }
+
+       if(ok==0) {
+               /* no vertices or only loose ones selected, remove duplicates */
+               eve= em->verts.first;
+               while(eve) {
+                       nextve= eve->next;
+                       if(eve->f & SELECT) {
+                               BLI_remlink(&em->verts,eve);
+                               free_editvert(eve);
+                       }
+                       eve= nextve;
+               }
+       }
+       recalc_editnormals();
+
+       EM_fgon_flags();
+       countall();
+       allqueue(REDRAWVIEW3D, 0);
+       DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
+
+       
+       if(dvec==NULL) BIF_undo_push("Spin");
+}
+
+void screw_mesh(int steps, int turns)
+{
+       EditMesh *em = G.editMesh;
+       EditVert *eve,*v1=0,*v2=0;
+       EditEdge *eed;
+       float dvec[3], nor[3];
+
+       TEST_EDITMESH
+       if(multires_test()) return;
+       
+       /* clear flags */
+       eve= em->verts.first;
+       while(eve) {
+               eve->f1= 0;
+               eve= eve->next;
+       }
+       /* edges set flags in verts */
+       eed= em->edges.first;
+       while(eed) {
+               if(eed->v1->f & SELECT) {
+                       if(eed->v2->f & SELECT) {
+                               /* watch: f1 is a byte */
+                               if(eed->v1->f1<2) eed->v1->f1++;
+                               if(eed->v2->f1<2) eed->v2->f1++;
+                       }
+               }
+               eed= eed->next;
+       }
+       /* find two vertices with eve->f1==1, more or less is wrong */
+       eve= em->verts.first;
+       while(eve) {
+               if(eve->f1==1) {
+                       if(v1==0) v1= eve;
+                       else if(v2==0) v2= eve;
+                       else {
+                               v1=0;
+                               break;
+                       }
+               }
+               eve= eve->next;
+       }
+       if(v1==0 || v2==0) {
+               error("You have to select a string of connected vertices too");
+               return;
+       }
+
+       /* calculate dvec */
+       dvec[0]= ( (v1->co[0]- v2->co[0]) )/(steps);
+       dvec[1]= ( (v1->co[1]- v2->co[1]) )/(steps);
+       dvec[2]= ( (v1->co[2]- v2->co[2]) )/(steps);
+
+       copy_v3_v3(nor, G.obedit->obmat[2]);
+
+       if(nor[0]*dvec[0]+nor[1]*dvec[1]+nor[2]*dvec[2]>0.000) {
+               dvec[0]= -dvec[0];
+               dvec[1]= -dvec[1];
+               dvec[2]= -dvec[2];
+       }
+
+       spin_mesh(turns*steps, turns*360, dvec, 0);
+
+       BIF_undo_push("Spin");
+}
+
+
+static void erase_edges(ListBase *l)
+{
+       EditEdge *ed, *nexted;
+       
+       ed = (EditEdge *) l->first;
+       while(ed) {
+               nexted= ed->next;
+               if( (ed->v1->f & SELECT) || (ed->v2->f & SELECT) ) {
+                       remedge(ed);
+                       free_editedge(ed);
+               }
+               ed= nexted;
+       }
+}
+
+static void erase_faces(ListBase *l)
+{
+       EditFace *f, *nextf;
+
+       f = (EditFace *) l->first;
+
+       while(f) {
+               nextf= f->next;
+               if( faceselectedOR(f, SELECT) ) {
+                       BLI_remlink(l, f);
+                       free_editface(f);
+               }
+               f = nextf;
+       }
+}      
+
+static void erase_vertices(ListBase *l)
+{
+       EditVert *v, *nextv;
+
+       v = (EditVert *) l->first;
+       while(v) {
+               nextv= v->next;
+               if(v->f & 1) {
+                       BLI_remlink(l, v);
+                       free_editvert(v);
+               }
+               v = nextv;
+       }
+}
+
+void delete_mesh(void)
+{
+       EditMesh *em = G.editMesh;
+       EditFace *efa, *nextvl;
+       EditVert *eve,*nextve;
+       EditEdge *eed,*nexted;
+       short event;
+       int count;
+       char *str="Erase";
+
+       TEST_EDITMESH
+       if(multires_test()) return;
+       
+       event= pupmenu("Erase %t|Vertices%x10|Edges%x1|Faces%x2|All%x3|Edges & Faces%x4|Only Faces%x5|Edge Loop%x6");
+       if(event<1) return;
+
+       if(event==10 ) {
+               str= "Erase Vertices";
+               erase_edges(&em->edges);
+               erase_faces(&em->faces);
+               erase_vertices(&em->verts);
+       } 
+       else if(event==6) {
+               if(!EdgeLoopDelete())
+                       return;
+
+               str= "Erase Edge Loop";
+       }
+       else if(event==4) {
+               str= "Erase Edges & Faces";
+               efa= em->faces.first;
+               while(efa) {
+                       nextvl= efa->next;
+                       /* delete only faces with 1 or more edges selected */
+                       count= 0;
+                       if(efa->e1->f & SELECT) count++;
+                       if(efa->e2->f & SELECT) count++;
+                       if(efa->e3->f & SELECT) count++;
+                       if(efa->e4 && (efa->e4->f & SELECT)) count++;
+                       if(count) {
+                               BLI_remlink(&em->faces, efa);
+                               free_editface(efa);
+                       }
+                       efa= nextvl;
+               }
+               eed= em->edges.first;
+               while(eed) {
+                       nexted= eed->next;
+                       if(eed->f & SELECT) {
+                               remedge(eed);
+                               free_editedge(eed);
+                       }
+                       eed= nexted;
+               }
+               efa= em->faces.first;
+               while(efa) {
+                       nextvl= efa->next;
+                       event=0;
+                       if( efa->v1->f & SELECT) event++;
+                       if( efa->v2->f & SELECT) event++;
+                       if( efa->v3->f & SELECT) event++;
+                       if(efa->v4 && (efa->v4->f & SELECT)) event++;
+                       
+                       if(event>1) {
+                               BLI_remlink(&em->faces, efa);
+                               free_editface(efa);
+                       }
+                       efa= nextvl;
+               }
+       } 
+       else if(event==1) {
+               str= "Erase Edges";
+               // faces first
+               efa= em->faces.first;
+               while(efa) {
+                       nextvl= efa->next;
+                       event=0;
+                       if( efa->e1->f & SELECT) event++;
+                       if( efa->e2->f & SELECT) event++;
+                       if( efa->e3->f & SELECT) event++;
+                       if(efa->e4 && (efa->e4->f & SELECT)) event++;
+                       
+                       if(event) {
+                               BLI_remlink(&em->faces, efa);
+                               free_editface(efa);
+                       }
+                       efa= nextvl;
+               }
+               eed= em->edges.first;
+               while(eed) {
+                       nexted= eed->next;
+                       if(eed->f & SELECT) {
+                               remedge(eed);
+                               free_editedge(eed);
+                       }
+                       eed= nexted;
+               }
+               /* to remove loose vertices: */
+               eed= em->edges.first;
+               while(eed) {
+                       if( eed->v1->f & SELECT) eed->v1->f-=SELECT;
+                       if( eed->v2->f & SELECT) eed->v2->f-=SELECT;
+                       eed= eed->next;
+               }
+               eve= em->verts.first;
+               while(eve) {
+                       nextve= eve->next;
+                       if(eve->f & SELECT) {
+                               BLI_remlink(&em->verts,eve);
+                               free_editvert(eve);
+                       }
+                       eve= nextve;
+               }
+
+       }
+       else if(event==2) {
+               str="Erase Faces";
+               delfaceflag(SELECT);
+       }
+       else if(event==3) {
+               str= "Erase All";
+               if(em->verts.first) free_vertlist(&em->verts);
+               if(em->edges.first) free_edgelist(&em->edges);
+               if(em->faces.first) free_facelist(&em->faces);
+               if(em->selected.first) BLI_freelistN(&(em->selected));
+       }
+       else if(event==5) {
+               str= "Erase Only Faces";
+               efa= em->faces.first;
+               while(efa) {
+                       nextvl= efa->next;
+                       if(efa->f & SELECT) {
+                               BLI_remlink(&em->faces, efa);
+                               free_editface(efa);
+                       }
+                       efa= nextvl;
+               }
+       }
+
+       EM_fgon_flags();        // redo flags and indices for fgons
+
+       countall();
+       allqueue(REDRAWVIEW3D, 0);
+       DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
+       BIF_undo_push(str);
+}
+
+
+/* Got this from scanfill.c. You will need to juggle around the
+ * callbacks for the scanfill.c code a bit for this to work. */
+void fill_mesh(void)
+{
+       EditMesh *em = G.editMesh;
+       EditVert *eve,*v1;
+       EditEdge *eed,*e1,*nexted;
+       EditFace *efa,*nextvl, *efan;
+       short ok;
+
+       if(G.obedit==0 || (G.obedit->type!=OB_MESH)) return;
+       if(multires_test()) return;
+
+       waitcursor(1);
+
+       /* copy all selected vertices */
+       eve= em->verts.first;
+       while(eve) {
+               if(eve->f & SELECT) {
+                       v1= BLI_addfillvert(eve->co);
+                       eve->tmp.v= v1;
+                       v1->tmp.v= eve;
+                       v1->xs= 0;      // used for counting edges
+               }
+               eve= eve->next;
+       }
+       /* copy all selected edges */
+       eed= em->edges.first;
+       while(eed) {
+               if( (eed->v1->f & SELECT) && (eed->v2->f & SELECT) ) {
+                       e1= BLI_addfilledge(eed->v1->tmp.v, eed->v2->tmp.v);
+                       e1->v1->xs++; 
+                       e1->v2->xs++;
+               }
+               eed= eed->next;
+       }
+       /* from all selected faces: remove vertices and edges to prevent doubles */
+       /* all edges add values, faces subtract,
+          then remove edges with vertices ->xs<2 */
+       efa= em->faces.first;
+       ok= 0;
+       while(efa) {
+               nextvl= efa->next;
+               if( faceselectedAND(efa, 1) ) {
+                       efa->v1->tmp.v->xs--;
+                       efa->v2->tmp.v->xs--;
+                       efa->v3->tmp.v->xs--;
+                       if(efa->v4) efa->v4->tmp.v->xs--;
+                       ok= 1;
+                       
+               }
+               efa= nextvl;
+       }
+       if(ok) {        /* there are faces selected */
+               eed= filledgebase.first;
+               while(eed) {
+                       nexted= eed->next;
+                       if(eed->v1->xs<2 || eed->v2->xs<2) {
+                               BLI_remlink(&filledgebase,eed);
+                       }
+                       eed= nexted;
+               }
+       }
+
+       if(BLI_edgefill(0, (G.obedit && G.obedit->actcol)?(G.obedit->actcol-1):0)) {
+               efa= fillfacebase.first;
+               while(efa) {
+                       /* normals default pointing up */
+                       efan= addfacelist(efa->v3->tmp.v, efa->v2->tmp.v, 
+                                                         efa->v1->tmp.v, 0, NULL, NULL);
+                       if(efan) EM_select_face(efan, 1);
+                       efa= efa->next;
+               }
+       }
+
+       BLI_end_edgefill();
+
+       waitcursor(0);
+       EM_select_flush();
+       countall();
+       allqueue(REDRAWVIEW3D, 0);
+       DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
+
+#ifdef WITH_VERSE
+       if(G.editMesh->vnode)
+               sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
+#endif
+
+       BIF_undo_push("Fill");
+}
+/*GB*/
+/*-------------------------------------------------------------------------------*/
+/*--------------------------- Edge Based Subdivide ------------------------------*/
+
+#define EDGENEW        2
+#define FACENEW        2
+#define EDGEINNER  4
+#define EDGEOLD  8
+
+/*used by faceloop cut to select only edges valid for edge slide*/
+#define DOUBLEOPFILL 16
+
+/* calculates offset for co, based on fractal, sphere or smooth settings  */
+static void alter_co(float *co, EditEdge *edge, float rad, int beauty, float perc)
+{
+       float vec1[3], fac;
+       
+       if(beauty & B_SMOOTH) {
+               /* we calculate an offset vector vec1[], to be added to *co */
+               float len, fac, nor[3], nor1[3], nor2[3];
+               
+               sub_v3_v3v3(nor, edge->v1->co, edge->v2->co);
+               len= 0.5f*normalize_v3(nor);
+       
+               copy_v3_v3(nor1, edge->v1->no);
+               copy_v3_v3(nor2, edge->v2->no);
+       
+               /* cosine angle */
+               fac= nor[0]*nor1[0] + nor[1]*nor1[1] + nor[2]*nor1[2] ;
+               
+               vec1[0]= fac*nor1[0];
+               vec1[1]= fac*nor1[1];
+               vec1[2]= fac*nor1[2];
+       
+               /* cosine angle */
+               fac= -nor[0]*nor2[0] - nor[1]*nor2[1] - nor[2]*nor2[2] ;
+               
+               vec1[0]+= fac*nor2[0];
+               vec1[1]+= fac*nor2[1];
+               vec1[2]+= fac*nor2[2];
+               
+               vec1[0]*= rad*len;
+               vec1[1]*= rad*len;
+               vec1[2]*= rad*len;
+               
+               co[0] += vec1[0];
+               co[1] += vec1[1];
+               co[2] += vec1[2];
+       }
+       else {
+               if(rad > 0.0) {   /* subdivide sphere */
+                       normalize_v3(co);
+                       co[0]*= rad;
+                       co[1]*= rad;
+                       co[2]*= rad;
+               }
+               else if(rad< 0.0) {  /* fractal subdivide */
+                       fac= rad* len_v3v3(edge->v1->co, edge->v2->co);
+                       vec1[0]= fac*(float)(0.5-BLI_drand());
+                       vec1[1]= fac*(float)(0.5-BLI_drand());
+                       vec1[2]= fac*(float)(0.5-BLI_drand());
+                       add_v3_v3v3(co, co, vec1);
+               }
+
+       }
+}
+
+/* assumes in the edge is the correct interpolated vertices already */
+/* percent defines the interpolation, rad and beauty are for special options */
+/* results in new vertex with correct coordinate, vertex normal and weight group info */
+static EditVert *subdivide_edge_addvert(EditEdge *edge, float rad, int beauty, float percent)
+{
+       EditVert *ev;
+       float co[3];
+       
+       co[0] = (edge->v2->co[0]-edge->v1->co[0])*percent + edge->v1->co[0];
+       co[1] = (edge->v2->co[1]-edge->v1->co[1])*percent + edge->v1->co[1];
+       co[2] = (edge->v2->co[2]-edge->v1->co[2])*percent + edge->v1->co[2];                                    
+       
+       /* offset for smooth or sphere or fractal */
+       alter_co(co, edge, rad, beauty, percent);
+       
+       /* clip if needed by mirror modifier */
+       if (edge->v1->f2) {
+               if ( edge->v1->f2 & edge->v2->f2 & 1) {
+                       co[0]= 0.0f;
+               }
+               if ( edge->v1->f2 & edge->v2->f2 & 2) {
+                       co[1]= 0.0f;
+               }
+               if ( edge->v1->f2 & edge->v2->f2 & 4) {
+                       co[2]= 0.0f;
+               }
+       }
+       
+       ev = addvertlist(co, NULL);
+       
+       /* vert data (vgroups, ..) */
+       EM_data_interp_from_verts(edge->v1, edge->v2, ev, percent);
+       
+       /* normal */
+       ev->no[0] = (edge->v2->no[0]-edge->v1->no[0])*percent + edge->v1->no[0];
+       ev->no[1] = (edge->v2->no[1]-edge->v1->no[1])*percent + edge->v1->no[1];
+       ev->no[2] = (edge->v2->no[2]-edge->v1->no[2])*percent + edge->v1->no[2];
+       normalize_v3(ev->no);
+       
+       return ev;
+}
+
+static void flipvertarray(EditVert** arr, short size)
+{
+       EditVert *hold;
+       int i;
+       
+       for(i=0; i<size/2; i++) {
+               hold = arr[i];
+               arr[i] = arr[size-i-1];
+               arr[size-i-1] = hold;   
+       }
+}
+
+static void facecopy(EditFace *source, EditFace *target)
+{
+       EditMesh *em= G.editMesh;
+       float *v1 = source->v1->co, *v2 = source->v2->co, *v3 = source->v3->co;
+       float *v4 = source->v4? source->v4->co: NULL;
+       float w[4][4];
+
+       CustomData_em_copy_data(&em->fdata, &em->fdata, source->data, &target->data);
+
+       target->mat_nr = source->mat_nr;
+       target->flag   = source->flag;  
+       target->h          = source->h;
+       
+       interp_weights_face_v3( w[0],v1, v2, v3, v4, target->v1->co);
+       interp_weights_face_v3( w[1],v1, v2, v3, v4, target->v2->co);
+       interp_weights_face_v3( w[2],v1, v2, v3, v4, target->v3->co);
+       if (target->v4)
+               interp_weights_face_v3( w[3],v1, v2, v3, v4, target->v4->co);
+       
+       CustomData_em_interp(&em->fdata, &source->data, NULL, (float*)w, 1, target->data);
+}
+
+static void fill_quad_single(EditFace *efa, struct GHash *gh, int numcuts, int seltype)
+{
+       EditEdge *cedge=NULL;
+       EditVert *v[4], **verts;
+       EditFace *hold;
+       short start=0, end, left, right, vertsize,i;   
+                                                       
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3;
+       v[3] = efa->v4;  
+
+       if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
+       else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}        
+       else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}        
+       else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}              
+
+       // Point verts to the array of new verts for cedge
+       verts = BLI_ghash_lookup(gh, cedge);
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+
+       if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
+       end     = (start+1)%4;
+       left   = (start+2)%4;
+       right  = (start+3)%4; 
+                  
+       /*
+       We should have something like this now
+
+                         end            start                           
+                          3   2   1   0   
+                          |---*---*---|
+                          |               |
+                          |               |       
+                          |               |
+                          -------------           
+                         left     right
+
+       where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
+       and 0,1,2... are the indexes of the new verts stored in verts
+
+       We will fill this case like this or this depending on even or odd cuts
+        
+                          |---*---*---|                  |---*---|
+                          |  /  \  |             |  / \  |
+                          | /     \ |            | /   \ |      
+                          |/            \|               |/     \|
+                          -------------                  ---------  
+       */
+
+       // Make center face
+       if(vertsize % 2 == 0) {
+               hold = addfacelist(verts[(vertsize-1)/2],verts[((vertsize-1)/2)+1],v[left],v[right], NULL,NULL);
+               hold->e2->f2 |= EDGEINNER;
+               hold->e4->f2 |= EDGEINNER;
+       }else{
+               hold = addfacelist(verts[(vertsize-1)/2],v[left],v[right],NULL, NULL,NULL);  
+               hold->e1->f2 |= EDGEINNER;
+               hold->e3->f2 |= EDGEINNER;
+       }
+       facecopy(efa,hold);
+
+       // Make side faces
+       for(i=0;i<(vertsize-1)/2;i++) {
+               hold = addfacelist(verts[i],verts[i+1],v[right],NULL,NULL,NULL);  
+               facecopy(efa,hold);
+               if(i+1 != (vertsize-1)/2) {
+            if(seltype == SUBDIV_SELECT_INNER) {
+                          hold->e2->f2 |= EDGEINNER;
+            }
+               }
+               hold = addfacelist(verts[vertsize-2-i],verts[vertsize-1-i],v[left],NULL,NULL,NULL); 
+               facecopy(efa,hold);
+               if(i+1 != (vertsize-1)/2) {
+            if(seltype == SUBDIV_SELECT_INNER) {
+                               hold->e3->f2 |= EDGEINNER;
+            }
+               }
+       }        
+}
+
+static void fill_tri_single(EditFace *efa, struct GHash *gh, int numcuts, int seltype)
+{
+       EditEdge *cedge=NULL;
+       EditVert *v[3], **verts;
+       EditFace *hold;
+       short start=0, end, op, vertsize,i;   
+                                                       
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3; 
+
+       if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
+       else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}        
+       else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}              
+
+       // Point verts to the array of new verts for cedge
+       verts = BLI_ghash_lookup(gh, cedge);
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+
+       if(verts[0] != v[start]) {flipvertarray(verts,numcuts+2);}
+          end  = (start+1)%3;
+          op    = (start+2)%3;
+                  
+       /*
+       We should have something like this now
+
+                         end            start                           
+                          3   2   1   0   
+                          |---*---*---|
+                          \               |
+                                \               |         
+                                  \       |
+                                        \       |
+                                          \   |
+                                                \ |
+                                                  |op
+                                                  
+       where start,end,op are indexes of EditFace->v1, etc (stored in v)
+       and 0,1,2... are the indexes of the new verts stored in verts
+
+       We will fill this case like this or this depending on even or odd cuts
+        
+                          3   2   1   0   
+                          |---*---*---|
+                          \    \  \   |
+                                \      \ \  |     
+                                  \   \ \ |
+                                        \  \ \|
+                                          \ \\|
+                                                \ |
+                                                  |op
+       */
+
+       // Make side faces
+       for(i=0;i<(vertsize-1);i++) {
+               hold = addfacelist(verts[i],verts[i+1],v[op],NULL,NULL,NULL);  
+               if(i+1 != vertsize-1) {
+            if(seltype == SUBDIV_SELECT_INNER) {
+                               hold->e2->f2 |= EDGEINNER;
+            }
+               }
+               facecopy(efa,hold);
+       }         
+}
+
+static void fill_quad_double_op(EditFace *efa, struct GHash *gh, int numcuts)
+{
+       EditEdge *cedge[2]={NULL, NULL};
+       EditVert *v[4], **verts[2];
+       EditFace *hold;
+       short start=0, end, left, right, vertsize,i;
+                                                       
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3;
+       v[3] = efa->v4;  
+
+       if(efa->e1->f & SELECT)   { cedge[0] = efa->e1;  cedge[1] = efa->e3; start = 0;}
+       else if(efa->e2->f & SELECT)      { cedge[0] = efa->e2;  cedge[1] = efa->e4; start = 1;}
+
+       // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
+       verts[0] = BLI_ghash_lookup(gh, cedge[0]);
+       verts[1] = BLI_ghash_lookup(gh, cedge[1]);
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+
+       if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
+       end     = (start+1)%4;
+       left   = (start+2)%4;
+       right  = (start+3)%4; 
+       if(verts[1][0] != v[left]) {flipvertarray(verts[1],numcuts+2);} 
+       /*
+       We should have something like this now
+
+                         end            start                           
+                          3   2   1   0   
+                          |---*---*---|
+                          |               |
+                          |               |       
+                          |               |
+                          |---*---*---|          
+                          0   1   2   3
+                         left     right
+
+       We will fill this case like this or this depending on even or odd cuts
+        
+                          |---*---*---|
+                          |   |   |   |
+                          |   |   |   |           
+                          |   |   |   |
+                          |---*---*---| 
+       */
+          
+       // Make side faces
+       for(i=0;i<vertsize-1;i++) {
+               hold = addfacelist(verts[0][i],verts[0][i+1],verts[1][vertsize-2-i],verts[1][vertsize-1-i],NULL,NULL);  
+               if(i < vertsize-2) {
+                       hold->e2->f2 |= EDGEINNER;
+                       hold->e2->f2 |= DOUBLEOPFILL;
+               }
+               facecopy(efa,hold);
+       }         
+}
+
+static void fill_quad_double_adj_path(EditFace *efa, struct GHash *gh, int numcuts)
+{
+       EditEdge *cedge[2]={NULL, NULL};
+       EditVert *v[4], **verts[2];
+       EditFace *hold;
+       short start=0, start2=0, vertsize,i;
+                                                       
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3;
+       v[3] = efa->v4;  
+
+       if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
+       if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
+       if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3;}
+       if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0;}
+
+       // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
+       verts[0] = BLI_ghash_lookup(gh, cedge[0]);
+       verts[1] = BLI_ghash_lookup(gh, cedge[1]);
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+
+       if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
+       if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}       
+       /*
+       We should have something like this now
+
+                          end           start                           
+                               3   2   1   0   
+               start2 0|---*---*---|
+                               |                  |
+                          1*              |
+                               |                  |
+                          2*              |       
+                               |                  |
+                end2  3|-----------|   
+
+       We will fill this case like this or this depending on even or odd cuts
+                          |---*---*---|
+                          | /   /   / |
+                          *   /   /   |
+                          | /   /       |
+                          *   /           |       
+                          | /           |
+                          |-----------|  
+       */
+
+       // Make outside tris
+       hold = addfacelist(verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);  
+       /* when ctrl is depressed, only want verts on the cutline selected */
+       if (G.qual  != LR_CTRLKEY)
+               hold->e3->f2 |= EDGEINNER;
+       facecopy(efa,hold);        
+       hold = addfacelist(verts[0][0],verts[1][vertsize-1],v[(start2+2)%4],NULL,NULL,NULL);
+       /* when ctrl is depressed, only want verts on the cutline selected */
+       if (G.qual  != LR_CTRLKEY)
+               hold->e1->f2 |= EDGEINNER;  
+       facecopy(efa,hold);                        
+       //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
+       //      hold->e1->h |= EM_FGON;
+       //}     
+       // Make side faces
+
+       for(i=0;i<numcuts;i++) {
+               hold = addfacelist(verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);  
+               hold->e2->f2 |= EDGEINNER;
+               facecopy(efa,hold);
+       }
+       //EM_fgon_flags();
+                 
+}
+
+static void fill_quad_double_adj_fan(EditFace *efa, struct GHash *gh, int numcuts)
+{
+       EditEdge *cedge[2]={NULL, NULL};
+       EditVert *v[4], *op=NULL, **verts[2];
+       EditFace *hold;
+       short start=0, start2=0, vertsize,i;
+                                                       
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3;
+       v[3] = efa->v4;  
+
+       if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
+       if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
+       if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
+       if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
+
+       
+       // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
+       verts[0] = BLI_ghash_lookup(gh, cedge[0]);
+       verts[1] = BLI_ghash_lookup(gh, cedge[1]);
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+
+       if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
+       if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}       
+       /*
+       We should have something like this now
+
+                          end           start                           
+                               3   2   1   0   
+               start2 0|---*---*---|
+                               |                  |
+                          1*              |
+                               |                  |
+                          2*              |       
+                               |                  |
+                end2  3|-----------|op   
+
+       We will fill this case like this or this (warning horrible ascii art follows)
+                          |---*---*---|
+                          | \  \   \  |
+                          *---\  \  \ |
+                          |   \ \ \  \|
+                          *---- \ \  \ |          
+                          |    ---  \\\|
+                          |-----------|  
+       */
+
+       for(i=0;i<=numcuts;i++) {
+               hold = addfacelist(op,verts[1][numcuts-i],verts[1][numcuts-i+1],NULL,NULL,NULL);  
+               hold->e1->f2 |= EDGEINNER;
+               facecopy(efa,hold);
+
+               hold = addfacelist(op,verts[0][i],verts[0][i+1],NULL,NULL,NULL);  
+               hold->e3->f2 |= EDGEINNER;
+               facecopy(efa,hold);
+       }         
+}
+
+static void fill_quad_double_adj_inner(EditFace *efa, struct GHash *gh, int numcuts)
+{
+       EditEdge *cedge[2]={NULL, NULL};
+       EditVert *v[4], *op=NULL, **verts[2],**inner;
+       EditFace *hold;
+       short start=0, start2=0, vertsize,i;
+       float co[3];
+                                               
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3;
+       v[3] = efa->v4;  
+
+       if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1; op = efa->v4;}
+       if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2; op = efa->v1;}
+       if(efa->e3->f & SELECT && efa->e4->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e4; start = 2; start2 = 3; op = efa->v2;}
+       if(efa->e4->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e4;  cedge[1] = efa->e1; start = 3; start2 = 0; op = efa->v3;}
+
+       
+       // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
+       verts[0] = BLI_ghash_lookup(gh, cedge[0]);
+       verts[1] = BLI_ghash_lookup(gh, cedge[1]);
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+
+       if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
+       if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}       
+       /*
+       We should have something like this now
+
+                          end           start                           
+                               3   2   1   0   
+               start2 0|---*---*---|
+                               |                  |
+                          1*              |
+                               |                  |
+                          2*              |       
+                               |                  |
+                end2  3|-----------|op   
+
+       We will fill this case like this or this (warning horrible ascii art follows)
+                          |---*-----*---|
+                          | *     /     |
+                          *   \ /       |
+                          |    *        |
+                          | /    \          |
+                          *        \    |         
+                          |           \ |
+                          |-------------|  
+       */
+
+       // Add Inner Vert(s)
+       inner = MEM_mallocN(sizeof(EditVert*)*numcuts,"New inner verts");
+       
+       for(i=0;i<numcuts;i++) {
+               co[0] = (verts[0][numcuts-i]->co[0] + verts[1][i+1]->co[0] ) / 2 ;
+               co[1] = (verts[0][numcuts-i]->co[1] + verts[1][i+1]->co[1] ) / 2 ;
+               co[2] = (verts[0][numcuts-i]->co[2] + verts[1][i+1]->co[2] ) / 2 ;
+               inner[i] = addvertlist(co, NULL);
+               inner[i]->f2 |= EDGEINNER;
+
+               EM_data_interp_from_verts(verts[0][numcuts-i], verts[1][i+1], inner[i], 0.5f);
+       }
+       
+       // Add Corner Quad
+       hold = addfacelist(verts[0][numcuts+1],verts[1][1],inner[0],verts[0][numcuts],NULL,NULL);  
+       hold->e2->f2 |= EDGEINNER;
+       hold->e3->f2 |= EDGEINNER;
+       facecopy(efa,hold);     
+       // Add Bottom Quads
+       hold = addfacelist(verts[0][0],verts[0][1],inner[numcuts-1],op,NULL,NULL);  
+       hold->e2->f2 |= EDGEINNER;
+       facecopy(efa,hold);     
+
+       hold = addfacelist(op,inner[numcuts-1],verts[1][numcuts],verts[1][numcuts+1],NULL,NULL);  
+       hold->e2->f2 |= EDGEINNER;
+       facecopy(efa,hold);             
+       
+       //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
+       //      hold->e1->h |= EM_FGON;
+       //}     
+       // Add Fill Quads (if # cuts > 1)
+
+       for(i=0;i<numcuts-1;i++) {
+               hold = addfacelist(inner[i],verts[1][i+1],verts[1][i+2],inner[i+1],NULL,NULL);  
+               hold->e1->f2 |= EDGEINNER;
+               hold->e3->f2 |= EDGEINNER;
+               facecopy(efa,hold);
+
+               hold = addfacelist(inner[i],inner[i+1],verts[0][numcuts-1-i],verts[0][numcuts-i],NULL,NULL);  
+               hold->e2->f2 |= EDGEINNER;
+               hold->e4->f2 |= EDGEINNER;
+               facecopy(efa,hold);     
+               
+               //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
+               //      hold->e1->h |= EM_FGON;
+               //}     
+       }       
+       
+       //EM_fgon_flags();
+       
+       MEM_freeN(inner);  
+}
+
+static void fill_tri_double(EditFace *efa, struct GHash *gh, int numcuts)
+{
+       EditEdge *cedge[2]={NULL, NULL};
+       EditVert *v[3], **verts[2];
+       EditFace *hold;
+       short start=0, start2=0, vertsize,i;
+                                                       
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3;
+
+       if(efa->e1->f & SELECT && efa->e2->f & SELECT) {cedge[0] = efa->e1;  cedge[1] = efa->e2; start = 0; start2 = 1;}
+       if(efa->e2->f & SELECT && efa->e3->f & SELECT) {cedge[0] = efa->e2;  cedge[1] = efa->e3; start = 1; start2 = 2;}
+       if(efa->e3->f & SELECT && efa->e1->f & SELECT) {cedge[0] = efa->e3;  cedge[1] = efa->e1; start = 2; start2 = 0;}
+
+       // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
+       verts[0] = BLI_ghash_lookup(gh, cedge[0]);
+       verts[1] = BLI_ghash_lookup(gh, cedge[1]);
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+
+       if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
+       if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}       
+       /*
+       We should have something like this now
+
+                          end           start                           
+                               3   2   1   0   
+               start2 0|---*---*---|
+                               |                /       
+                          1*      /            
+                               |        /               
+                          2*   /                                
+                               | /                
+                end2  3|  
+
+       We will fill this case like this or this depending on even or odd cuts
+                          |---*---*---|
+                          | /   /   / 
+                          *   /   /   
+                          | /   /       
+                          *   /                          
+                          | /           
+                          |
+       */
+
+       // Make outside tri
+       hold = addfacelist(verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);  
+       hold->e3->f2 |= EDGEINNER;
+       facecopy(efa,hold);                       
+       // Make side faces
+
+       for(i=0;i<numcuts;i++) {
+               hold = addfacelist(verts[0][i],verts[0][i+1],verts[1][vertsize-1-(i+1)],verts[1][vertsize-1-i],NULL,NULL);  
+               hold->e2->f2 |= EDGEINNER;
+               facecopy(efa,hold);
+       }         
+}
+
+static void fill_quad_triple(EditFace *efa, struct GHash *gh, int numcuts)
+{
+       EditEdge *cedge[3]={0};
+       EditVert *v[4], **verts[3];
+       EditFace *hold;
+       short start=0, start2=0, start3=0, vertsize, i, repeats;
+       
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3;
+       v[3] = efa->v4;  
+          
+       if(!(efa->e1->f & SELECT)) {
+               cedge[0] = efa->e2;  
+               cedge[1] = efa->e3; 
+               cedge[2] = efa->e4;
+               start = 1;start2 = 2;start3 = 3;   
+       }
+       if(!(efa->e2->f & SELECT)) {
+               cedge[0] = efa->e3;  
+               cedge[1] = efa->e4; 
+               cedge[2] = efa->e1;
+               start = 2;start2 = 3;start3 = 0;   
+       }
+       if(!(efa->e3->f & SELECT)) {
+               cedge[0] = efa->e4;  
+               cedge[1] = efa->e1; 
+               cedge[2] = efa->e2;
+               start = 3;start2 = 0;start3 = 1;   
+       }
+       if(!(efa->e4->f & SELECT)) {
+               cedge[0] = efa->e1;  
+               cedge[1] = efa->e2; 
+               cedge[2] = efa->e3;
+               start = 0;start2 = 1;start3 = 2;   
+       }          
+       // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
+       verts[0] = BLI_ghash_lookup(gh, cedge[0]);
+       verts[1] = BLI_ghash_lookup(gh, cedge[1]);
+       verts[2] = BLI_ghash_lookup(gh, cedge[2]);
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+       
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+       
+       if(verts[0][0] != v[start]) {flipvertarray(verts[0],numcuts+2);}
+       if(verts[1][0] != v[start2]) {flipvertarray(verts[1],numcuts+2);}  
+       if(verts[2][0] != v[start3]) {flipvertarray(verts[2],numcuts+2);}   
+       /*
+        We should have something like this now
+        
+        start2                          
+        3   2   1   0   
+        start3 0|---*---*---|3 
+        |                 |
+        1*                *2
+        |                 |
+        2*                *1      
+        |                 |
+        3|-----------|0 start   
+        
+        We will fill this case like this or this depending on even or odd cuts  
+        there are a couple of differences. For odd cuts, there is a tri in the
+        middle as well as 1 quad at the bottom (not including the extra quads
+        for odd cuts > 1                 
+        
+        For even cuts, there is a quad in the middle and 2 quads on the bottom
+        
+        they are numbered here for clarity
+        
+        1 outer tris and bottom quads
+        2 inner tri or quad
+        3 repeating quads
+        
+        |---*---*---*---|
+        |1/   /  \   \ 1|
+        |/ 3 / \  3 \|
+        *  /   2   \   *
+        | /              \  |
+        |/                     \ | 
+        *---------------*
+        |        3             |
+        |                         |  
+        *---------------*
+        |                         |
+        |        1             |                                 
+        |                         |
+        |---------------|
+        
+        |---*---*---*---*---|
+        | 1/   /        \   \ 1|   
+        | /   /           \   \ |  
+        |/ 3 /          \ 3 \|
+        *   /             \   *
+        |  /                    \  |   
+        | /       2       \ |   
+        |/                              \|
+        *-------------------*
+        |                                 |
+        |               3               |
+        |                                 | 
+        *-------------------*
+        |                                 |
+        |               1               |
+        |                                 | 
+        *-------------------*
+        |                                 |
+        |              1                 |
+        |                                 | 
+        |-------------------|
+        
+        */
+
+       // Make outside tris
+       hold = addfacelist(verts[0][vertsize-2],verts[0][vertsize-1],verts[1][1],NULL,NULL,NULL);  
+       hold->e3->f2 |= EDGEINNER;
+       facecopy(efa,hold);       
+       hold = addfacelist(verts[1][vertsize-2],verts[1][vertsize-1],verts[2][1],NULL,NULL,NULL);  
+       hold->e3->f2 |= EDGEINNER;
+       facecopy(efa,hold);                       
+       // Make bottom quad
+       hold = addfacelist(verts[0][0],verts[0][1],verts[2][vertsize-2],verts[2][vertsize-1],NULL,NULL);  
+       hold->e2->f2 |= EDGEINNER;
+       facecopy(efa,hold);              
+       //If it is even cuts, add the 2nd lower quad
+       if(numcuts % 2 == 0) {
+               hold = addfacelist(verts[0][1],verts[0][2],verts[2][vertsize-3],verts[2][vertsize-2],NULL,NULL);  
+               hold->e2->f2 |= EDGEINNER;
+               facecopy(efa,hold);              
+               // Also Make inner quad
+               hold = addfacelist(verts[1][numcuts/2],verts[1][(numcuts/2)+1],verts[2][numcuts/2],verts[0][(numcuts/2)+1],NULL,NULL);             
+               hold->e3->f2 |= EDGEINNER;
+               //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
+               //      hold->e3->h |= EM_FGON;
+               //}
+               facecopy(efa,hold);
+               repeats = (numcuts / 2) -1;
+       } else {
+               // Make inner tri        
+               hold = addfacelist(verts[1][(numcuts/2)+1],verts[2][(numcuts/2)+1],verts[0][(numcuts/2)+1],NULL,NULL,NULL);                
+               hold->e2->f2 |= EDGEINNER;
+               //if(G.scene->toolsettings->editbutflag & B_AUTOFGON) {
+               //      hold->e2->h |= EM_FGON;
+               //}
+               facecopy(efa,hold);   
+               repeats = ((numcuts+1) / 2)-1;
+       }
+       
+       // cuts for 1 and 2 do not have the repeating quads
+       if(numcuts < 3) {repeats = 0;}
+       for(i=0;i<repeats;i++) {
+               //Make side repeating Quads
+               hold = addfacelist(verts[1][i+1],verts[1][i+2],verts[0][vertsize-i-3],verts[0][vertsize-i-2],NULL,NULL);  
+               hold->e2->f2 |= EDGEINNER;               
+               facecopy(efa,hold);                        
+               hold = addfacelist(verts[1][vertsize-i-3],verts[1][vertsize-i-2],verts[2][i+1],verts[2][i+2],NULL,NULL);                   
+               hold->e4->f2 |= EDGEINNER;
+               facecopy(efa,hold); 
+       }
+       // Do repeating bottom quads 
+       for(i=0;i<repeats;i++) {
+               if(numcuts % 2 == 1) {   
+                       hold = addfacelist(verts[0][1+i],verts[0][2+i],verts[2][vertsize-3-i],verts[2][vertsize-2-i],NULL,NULL);  
+               } else {
+                       hold = addfacelist(verts[0][2+i],verts[0][3+i],verts[2][vertsize-4-i],verts[2][vertsize-3-i],NULL,NULL);                                  
+               }
+               hold->e2->f2 |= EDGEINNER;
+               facecopy(efa,hold);                             
+       }       
+       //EM_fgon_flags();
+}
+
+static void fill_quad_quadruple(EditFace *efa, struct GHash *gh, int numcuts, float rad, int beauty)
+{
+       EditVert **verts[4], ***innerverts;
+       EditFace *hold; 
+       EditEdge temp;
+       short vertsize, i, j;
+       
+       // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
+       verts[0] = BLI_ghash_lookup(gh, efa->e1);
+       verts[1] = BLI_ghash_lookup(gh, efa->e2);
+       verts[2] = BLI_ghash_lookup(gh, efa->e3);
+       verts[3] = BLI_ghash_lookup(gh, efa->e4);
+
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+
+       if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
+       if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}  
+       if(verts[2][0] == efa->v3) {flipvertarray(verts[2],numcuts+2);}
+       if(verts[3][0] == efa->v4) {flipvertarray(verts[3],numcuts+2);}  
+       /*
+       We should have something like this now
+                                         1
+                                                                                 
+                               3   2   1   0   
+                          0|---*---*---|0 
+                               |           |
+                          1*           *1
+                    2  |           |   4
+                          2*           *2         
+                               |           |
+                          3|---*---*---|3      
+                               3   2   1   0
+
+                                         3
+       // we will fill a 2 dim array of editvert*s to make filling easier
+       //  the innervert order is shown
+
+                               0   0---1---2---3 
+                                       |   |   |   |
+                               1   0---1---2---3 
+                                       |   |   |   |
+                               2   0---1---2---3               
+                                       |   |   |   |
+                               3   0---1---2---3  
+                 
+        */
+       innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts outer array"); 
+       for(i=0;i<numcuts+2;i++) {
+               innerverts[i] = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"quad-quad subdiv inner verts inner array");
+       }  
+       
+       // first row is e1 last row is e3
+       for(i=0;i<numcuts+2;i++) {
+               innerverts[0][i]                  = verts[0][(numcuts+1)-i];
+               innerverts[numcuts+1][i]  = verts[2][(numcuts+1)-i];
+       }
+       
+       for(i=1;i<=numcuts;i++) {
+               /* we create a fake edge for the next loop */
+               temp.v2 = innerverts[i][0]                      = verts[1][i];
+               temp.v1 = innerverts[i][numcuts+1]  = verts[3][i];
+               
+               for(j=1;j<=numcuts;j++) { 
+                       float percent= (float)j/(float)(numcuts+1);
+
+                       innerverts[i][(numcuts+1)-j]= subdivide_edge_addvert(&temp, rad, beauty, percent);
+               }       
+       }       
+       // Fill with faces
+       for(i=0;i<numcuts+1;i++) {
+               for(j=0;j<numcuts+1;j++) {
+                       hold = addfacelist(innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],innerverts[i+1][j+1],NULL,NULL);       
+                       hold->e1->f2 = EDGENEW;   
+                       hold->e2->f2 = EDGENEW;  
+                       hold->e3->f2 = EDGENEW;                 
+                       hold->e4->f2 = EDGENEW;   
+                       
+                       if(i != 0) { hold->e1->f2 |= EDGEINNER; }
+                       if(j != 0) { hold->e2->f2 |= EDGEINNER; }
+                       if(i != numcuts) { hold->e3->f2 |= EDGEINNER; }
+                       if(j != numcuts) { hold->e4->f2 |= EDGEINNER; }
+                       
+                       facecopy(efa,hold);             
+               }               
+       }
+       // Clean up our dynamic multi-dim array
+       for(i=0;i<numcuts+2;i++) {
+          MEM_freeN(innerverts[i]);   
+       }       
+       MEM_freeN(innerverts);
+}
+
+static void fill_tri_triple(EditFace *efa, struct GHash *gh, int numcuts, float rad, int beauty)
+{
+       EditVert **verts[3], ***innerverts;
+       short vertsize, i, j;
+       EditFace *hold;  
+       EditEdge temp;
+
+       // Point verts[0] and [1] to the array of new verts for cedge[0] and cedge[1]
+       verts[0] = BLI_ghash_lookup(gh, efa->e1);
+       verts[1] = BLI_ghash_lookup(gh, efa->e2);
+       verts[2] = BLI_ghash_lookup(gh, efa->e3);
+
+       //This is the index size of the verts array
+       vertsize = numcuts+2;
+
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+
+       if(verts[0][0] != efa->v1) {flipvertarray(verts[0],numcuts+2);}
+       if(verts[1][0] != efa->v2) {flipvertarray(verts[1],numcuts+2);}  
+       if(verts[2][0] != efa->v3) {flipvertarray(verts[2],numcuts+2);}   
+       /*
+       We should have something like this now
+                                          3
+                                                                                 
+                               3   2   1   0   
+                          0|---*---*---|3 
+                               |                 /     
+                 1     1*              *2   
+                               |         /       
+                          2*   *1         2             
+                               |  /               
+                          3|/ 
+                                0
+
+       we will fill a 2 dim array of editvert*s to make filling easier
+
+                                               3
+
+                        0  0---1---2---3---4
+                               | / | /  |/  | /        
+                        1  0---1----2---3 
+          1            | /  | / | /    
+                        2  0----1---2   2
+                               |  / |  /          
+                               |/   |/   
+                        3  0---1 
+                               |  /
+                               |/
+                        4  0  
+         
+       */
+       
+       innerverts = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"tri-tri subdiv inner verts outer array"); 
+       for(i=0;i<numcuts+2;i++) {
+                 innerverts[i] = MEM_mallocN(sizeof(EditVert*)*((numcuts+2)-i),"tri-tri subdiv inner verts inner array");
+       }
+       //top row is e3 backwards
+       for(i=0;i<numcuts+2;i++) {
+                 innerverts[0][i]                = verts[2][(numcuts+1)-i];
+       }   
+                  
+       for(i=1;i<=numcuts+1;i++) {
+               //fake edge, first vert is from e1, last is from e2
+               temp.v1= innerverts[i][0]                         = verts[0][i];
+               temp.v2= innerverts[i][(numcuts+1)-i]  = verts[1][(numcuts+1)-i];
+               
+               for(j=1;j<(numcuts+1)-i;j++) {
+                       float percent= (float)j/(float)((numcuts+1)-i);
+
+                       innerverts[i][((numcuts+1)-i)-j]= subdivide_edge_addvert(&temp, rad, beauty, 1-percent);
+               }
+       }
+
+       // Now fill the verts with happy little tris :)
+       for(i=0;i<=numcuts+1;i++) {
+               for(j=0;j<(numcuts+1)-i;j++) {   
+                       //We always do the first tri
+                       hold = addfacelist(innerverts[i][j+1],innerverts[i][j],innerverts[i+1][j],NULL,NULL,NULL);      
+                       hold->e1->f2 |= EDGENEW;          
+                       hold->e2->f2 |= EDGENEW;  
+                       hold->e3->f2 |= EDGENEW;  
+                       if(i != 0) { hold->e1->f2 |= EDGEINNER; }
+                       if(j != 0) { hold->e2->f2 |= EDGEINNER; }
+                       if(j+1 != (numcuts+1)-i) {hold->e3->f2 |= EDGEINNER;}
+                       
+                       facecopy(efa,hold);             
+                       //if there are more to come, we do the 2nd       
+                       if(j+1 <= numcuts-i) {
+                               hold = addfacelist(innerverts[i+1][j],innerverts[i+1][j+1],innerverts[i][j+1],NULL,NULL,NULL);             
+                               facecopy(efa,hold); 
+                               hold->e1->f2 |= EDGENEW;          
+                               hold->e2->f2 |= EDGENEW;  
+                               hold->e3->f2 |= EDGENEW;        
+                       }
+               } 
+       }
+
+       // Clean up our dynamic multi-dim array
+       for(i=0;i<numcuts+2;i++) {
+               MEM_freeN(innerverts[i]);   
+       }       
+       MEM_freeN(innerverts);
+}
+
+//Next two fill types are for knife exact only and are provided to allow for knifing through vertices
+//This means there is no multicut!
+static void fill_quad_doublevert(EditFace *efa, int v1, int v2)
+{
+       EditFace *hold;
+       /*
+               Depending on which two vertices have been knifed through (v1 and v2), we
+               triangulate like the patterns below.
+                               X-------|       |-------X
+                               | \     |       |     / |
+                               |   \   |       |   /   |
+                               |         \     |       | /         |
+                               --------X       X--------
+       */
+       
+       if(v1 == 1 && v2 == 3){
+               hold= addfacelist(efa->v1, efa->v2, efa->v3, 0, efa, NULL);
+               hold->e1->f2 |= EDGENEW;
+               hold->e2->f2 |= EDGENEW;
+               hold->e3->f2 |= EDGENEW;
+               hold->e3->f2 |= EDGEINNER;
+               facecopy(efa, hold);
+               
+               hold= addfacelist(efa->v1, efa->v3, efa->v4, 0, efa, NULL);
+               hold->e1->f2 |= EDGENEW;
+               hold->e2->f2 |= EDGENEW;
+               hold->e3->f2 |= EDGENEW;
+               hold->e1->f2 |= EDGEINNER;
+               facecopy(efa, hold);
+       }
+       else{
+               hold= addfacelist(efa->v1, efa->v2, efa->v4, 0, efa, NULL);
+               hold->e1->f2 |= EDGENEW;
+               hold->e2->f2 |= EDGENEW;
+               hold->e3->f2 |= EDGENEW;
+               hold->e2->f2 |= EDGEINNER;
+               facecopy(efa, hold);
+               
+               hold= addfacelist(efa->v2, efa->v3, efa->v4, 0, efa, NULL);
+               hold->e1->f2 |= EDGENEW;
+               hold->e2->f2 |= EDGENEW;
+               hold->e3->f2 |= EDGENEW;
+               hold->e3->f2 |= EDGEINNER;
+               facecopy(efa, hold);
+       }
+}
+
+static void fill_quad_singlevert(EditFace *efa, struct GHash *gh)
+{
+       EditEdge *cedge=NULL;
+       EditVert *v[4], **verts;
+       EditFace *hold;
+       short start=0, end, left, right, vertsize;   
+                                                       
+       v[0] = efa->v1;
+       v[1] = efa->v2;
+       v[2] = efa->v3;
+       v[3] = efa->v4;  
+
+       if(efa->e1->f & SELECT)   { cedge = efa->e1; start = 0;}
+       else if(efa->e2->f & SELECT) { cedge = efa->e2; start = 1;}        
+       else if(efa->e3->f & SELECT) { cedge = efa->e3; start = 2;}        
+       else if(efa->e4->f & SELECT) { cedge = efa->e4; start = 3;}              
+
+       // Point verts to the array of new verts for cedge
+       verts = BLI_ghash_lookup(gh, cedge);
+       //This is the index size of the verts array
+       vertsize = 3;
+
+       // Is the original v1 the same as the first vert on the selected edge?
+       // if not, the edge is running the opposite direction in this face so flip
+       // the array to the correct direction
+
+       if(verts[0] != v[start]) {flipvertarray(verts,3);}
+       end     = (start+1)%4;
+       left   = (start+2)%4;
+       right  = (start+3)%4; 
+
+/*
+       We should have something like this now
+
+                         end            start                           
+                          2     1     0   
+                          |-----*-----|
+                          |               |
+                          |               |       
+                          |               |
+                          -------------           
+                         left     right
+
+       where start,end,left, right are indexes of EditFace->v1, etc (stored in v)
+       and 0,1,2 are the indexes of the new verts stored in verts. We fill like
+       this, depending on whether its vertex 'left' or vertex 'right' thats
+       been knifed through...
+                               
+                               |---*---|       |---*---|
+                               |  /    |       |    \  |
+                               | /             |       |         \ |
+                               |/              |       |          \|
+                               X--------       --------X
+*/
+
+       if(v[left]->f1) {
+               //triangle is composed of cutvert, end and left
+               hold = addfacelist(verts[1],v[end],v[left],NULL, NULL,NULL);
+               hold->e1->f2 |= EDGENEW;
+               hold->e2->f2 |= EDGENEW;
+               hold->e3->f2 |= EDGENEW;
+               hold->e3->f2 |= EDGEINNER;
+               facecopy(efa, hold);
+               
+               //quad is composed of cutvert, left, right and start
+               hold = addfacelist(verts[1],v[left],v[right],v[start], NULL, NULL);
+               hold->e1->f2 |= EDGENEW;
+               hold->e2->f2 |= EDGENEW;
+               hold->e3->f2 |= EDGENEW;
+               hold->e4->f2 |= EDGENEW;
+               hold->e1->f2 |= EDGEINNER;
+               facecopy(efa, hold);
+       }
+       else if(v[right]->f1) {
+               //triangle is composed of cutvert, right and start
+               hold = addfacelist(verts[1],v[right],v[start], NULL, NULL, NULL);
+               hold->e1->f2 |= EDGENEW;
+               hold->e2->f2 |= EDGENEW;
+               hold->e3->f2 |= EDGENEW;
+               hold->e1->f2 |= EDGEINNER;
+               facecopy(efa, hold);
+               //quad is composed of cutvert, end, left, right
+               hold = addfacelist(verts[1],v[end], v[left], v[right], NULL, NULL);
+               hold->e1->f2 |= EDGENEW;
+               hold->e2->f2 |= EDGENEW;
+               hold->e3->f2 |= EDGENEW;
+               hold->e4->f2 |= EDGENEW;
+               hold->e4->f2 |= EDGEINNER;
+               facecopy(efa, hold);
+       }
+       
+}      
+
+// This function takes an example edge, the current point to create and 
+// the total # of points to create, then creates the point and return the
+// editvert pointer to it.
+static EditVert *subdivideedgenum(EditEdge *edge, int curpoint, int totpoint, float rad, int beauty)
+{
+       EditVert *ev;
+       float percent;
+        
+       if (beauty & (B_PERCENTSUBD) && totpoint == 1)
+               //percent=(float)(edge->tmp.l)/32768.0f;
+               percent= edge->tmp.fp;
+       else
+               percent= (float)curpoint/(float)(totpoint+1);
+
+       ev= subdivide_edge_addvert(edge, rad, beauty, percent);
+       ev->f = edge->v1->f;
+       
+       return ev;
+}
+
+void esubdivideflag(int flag, float rad, int beauty, int numcuts, int seltype)
+{
+       EditMesh *em = G.editMesh;
+       EditFace *ef;
+       EditEdge *eed, *cedge, *sort[4];
+       EditVert *eve, **templist;
+       struct GHash *gh;
+       float length[4], v1mat[3], v2mat[3], v3mat[3], v4mat[3];
+       int i, j, edgecount, touchcount, facetype,hold;
+       ModifierData *md= G.obedit->modifiers.first;
+       
+       if(multires_test()) return;
+
+       //Set faces f1 to 0 cause we need it later
+       for(ef=em->faces.first;ef;ef = ef->next) ef->f1 = 0;
+       for(eve=em->verts.first; eve; eve=eve->next) {
+               if(!(beauty & B_KNIFE)) /* knife sets this flag for vertex cuts */
+                       eve->f1 = 0;
+               eve->f2 = 0;
+       }
+
+       for (; md; md=md->next) {
+               if ((md->type==eModifierType_Mirror) && (md->mode & eModifierMode_Realtime)) {
+                       MirrorModifierData *mmd = (MirrorModifierData*) md;     
+               
+                       if(mmd->flag & MOD_MIR_CLIPPING) {
+                               for (eve= em->verts.first; eve; eve= eve->next) {
+                                       eve->f2= 0;
+                                       switch(mmd->axis) {
+                                               case 0:
+                                                       if (fabs(eve->co[0]) < mmd->tolerance)
+                                                               eve->f2 |= 1;
+                                                       break;
+                                               case 1:
+                                                       if (fabs(eve->co[1]) < mmd->tolerance)
+                                                               eve->f2 |= 2;
+                                                       break;
+                                               case 2:
+                                                       if (fabs(eve->co[2]) < mmd->tolerance)
+                                                               eve->f2 |= 4;
+                                                       break;
+                                       }
+                               }
+                       }
+               }
+       }
+       
+       //Flush vertex flags upward to the edges
+       for(eed = em->edges.first;eed;eed = eed->next) {
+               //if(eed->f & flag && eed->v1->f == eed->v2->f) {
+               //      eed->f |= eed->v1->f;   
+               // }
+               eed->f2 = 0;   
+               if(eed->f & flag) {
+                       eed->f2 |= EDGEOLD;
+               }
+       }
+       
+       // We store an array of verts for each edge that is subdivided,
+       // we put this array as a value in a ghash which is keyed by the EditEdge*
+
+       // Now for beauty subdivide deselect edges based on length
+       if(beauty & B_BEAUTY) { 
+               for(ef = em->faces.first;ef;ef = ef->next) {
+                       if(!ef->v4) {
+                               continue;
+                       }
+                       if(ef->f & SELECT) {
+                               copy_v3_v3(v1mat, ef->v1->co);
+                               copy_v3_v3(v2mat, ef->v2->co);
+                               copy_v3_v3(v3mat, ef->v3->co);
+                               copy_v3_v3(v4mat, ef->v4->co);
+                               mul_mat3_m4_v3(G.obedit->obmat, v1mat);
+                               mul_mat3_m4_v3(G.obedit->obmat, v2mat);                                                                                 
+                               mul_mat3_m4_v3(G.obedit->obmat, v3mat);
+                               mul_mat3_m4_v3(G.obedit->obmat, v4mat);
+                               
+                               length[0] = len_v3v3(v1mat, v2mat);
+                               length[1] = len_v3v3(v2mat, v3mat);
+                               length[2] = len_v3v3(v3mat, v4mat);
+                               length[3] = len_v3v3(v4mat, v1mat);
+                               sort[0] = ef->e1;
+                               sort[1] = ef->e2;
+                               sort[2] = ef->e3;
+                               sort[3] = ef->e4;
+                                                                                                 
+                                                                                               
+                               // Beauty Short Edges
+                               if(beauty & B_BEAUTY_SHORT) {
+                                       for(j=0;j<2;j++) {
+                                               hold = -1;
+                                               for(i=0;i<4;i++) {
+                                                       if(length[i] < 0) {
+                                                               continue;                                                       
+                                                       } else if(hold == -1) {  
+                                                               hold = i; 
+                                                       } else {
+                                                               if(length[hold] < length[i]) {
+                                                                       hold = i;   
+                                                               }
+                                                       }
+                                               }
+                                               sort[hold]->f &= ~SELECT;
+                                               sort[hold]->f2 |= EDGENEW;
+                                               length[hold] = -1;
+                                       }                                                       
+                               } 
+                               
+                               // Beauty Long Edges
+                               else {
+                                        for(j=0;j<2;j++) {
+                                               hold = -1;
+                                               for(i=0;i<4;i++) {
+                                                       if(length[i] < 0) {
+                                                               continue;                                                       
+                                                       } else if(hold == -1) {  
+                                                               hold = i; 
+                                                       } else {
+                                                               if(length[hold] > length[i]) {
+                                                                       hold = i;   
+                                                               }
+                                                       }
+                                               }
+                                               sort[hold]->f &= ~SELECT;
+                                               sort[hold]->f2 |= EDGENEW;
+                                               length[hold] = -1;
+                                       }                                                       
+                               }   
+                       }
+               }       
+       }
+
+       gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp); 
+
+       // If we are knifing, We only need the selected edges that were cut, so deselect if it was not cut
+       if(beauty & B_KNIFE) {  
+               for(eed= em->edges.first;eed;eed=eed->next) {   
+                       if( eed->tmp.fp == 0 ) {
+                               EM_select_edge(eed,0);
+                       }
+               }
+       }  
+       // So for each edge, if it is selected, we allocate an array of size cuts+2
+       // so we can have a place for the v1, the new verts and v2  
+       for(eed=em->edges.first;eed;eed = eed->next) {
+               if(eed->f & flag) {
+                       templist = MEM_mallocN(sizeof(EditVert*)*(numcuts+2),"vertlist");
+                       templist[0] = eed->v1;
+                       for(i=0;i<numcuts;i++) {
+                               // This function creates the new vert and returns it back
+                               // to the array
+                               templist[i+1] = subdivideedgenum(eed, i+1, numcuts, rad, beauty);
+                               //while we are here, we can copy edge info from the original edge
+                               cedge = addedgelist(templist[i],templist[i+1],eed);
+                               // Also set the edge f2 to EDGENEW so that we can use this info later
+                               cedge->f2 = EDGENEW;
+                       }
+                       templist[i+1] = eed->v2;
+                       //Do the last edge too
+                       cedge = addedgelist(templist[i],templist[i+1],eed);
+                       cedge->f2 = EDGENEW;
+                       // Now that the edge is subdivided, we can put its verts in the ghash 
+                       BLI_ghash_insert(gh, eed, templist);                       
+               }                                                                 
+       }
+
+       DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
+       // Now for each face in the mesh we need to figure out How many edges were cut
+       // and which filling method to use for that face
+       for(ef = em->faces.first;ef;ef = ef->next) {
+               edgecount = 0;
+               facetype = 3;
+               if(ef->e1->f & flag) {edgecount++;}
+               if(ef->e2->f & flag) {edgecount++;}
+               if(ef->e3->f & flag) {edgecount++;}
+               if(ef->v4) {
+                       facetype = 4;
+                       if(ef->e4->f & flag) {edgecount++;}
+               }  
+               if(facetype == 4) {
+                       switch(edgecount) {
+                               case 0:
+                                       if(beauty & B_KNIFE && numcuts == 1){
+                                               /*Test for when knifing through two opposite verts but no edges*/
+                                               touchcount = 0;
+                                               if(ef->v1->f1) touchcount++;
+                                               if(ef->v2->f1) touchcount++;
+                                               if(ef->v3->f1) touchcount++;
+                                               if(ef->v4->f1) touchcount++;
+                                               if(touchcount == 2){
+                                                       if(ef->v1->f1 && ef->v3->f1){ 
+                                                               ef->f1 = SELECT;
+                                                               fill_quad_doublevert(ef, 1, 3); 
+                                                       }
+                                                       else if(ef->v2->f1 && ef->v4->f1){
+                                                               ef->f1 = SELECT;
+                                                               fill_quad_doublevert(ef, 2, 4);
+                                                       }
+                                               }
+                                       }
+                                       break; 
+                               
+                               case 1: 
+                                       if(beauty & B_KNIFE && numcuts == 1){
+                                               /*Test for when knifing through an edge and one vert*/
+                                               touchcount = 0;
+                                               if(ef->v1->f1) touchcount++;
+                                               if(ef->v2->f1) touchcount++;
+                                               if(ef->v3->f1) touchcount++;
+                                               if(ef->v4->f1) touchcount++;
+                                               
+                                               if(touchcount == 1){
+                                                       if( (ef->e1->f & flag && ( !ef->e1->v1->f1 && !ef->e1->v2->f1 )) ||
+                                                               (ef->e2->f & flag && ( !ef->e2->v1->f1 && !ef->e2->v2->f1 )) ||
+                                                               (ef->e3->f & flag && ( !ef->e3->v1->f1 && !ef->e3->v2->f1 )) ||
+                                                               (ef->e4->f & flag && ( !ef->e4->v1->f1 && !ef->e4->v2->f1 )) ){
+                                                               
+                                                               ef->f1 = SELECT; 
+                                                               fill_quad_singlevert(ef, gh);
+                                                       }
+                                                       else{
+                                                               ef->f1 = SELECT;
+                                                               fill_quad_single(ef, gh, numcuts, seltype);
+                                                       }
+                                               }
+                                               else{ 
+                                                       ef->f1 = SELECT; 
+                                                       fill_quad_single(ef, gh, numcuts, seltype);
+                                               }
+                                       }
+                                       else{ 
+                                               ef->f1 = SELECT;
+                                               fill_quad_single(ef, gh, numcuts, seltype);
+                                       }
+                                       break;   
+                               case 2: ef->f1 = SELECT;
+                                       // if there are 2, we check if edge 1 and 3 are either both on or off that way
+                                       // we can tell if the selected pair is Adjacent or Opposite of each other
+                                       if((ef->e1->f & flag && ef->e3->f & flag) || 
+                                          (ef->e2->f & flag && ef->e4->f & flag)) {
+                                               fill_quad_double_op(ef, gh, numcuts);                                                     
+                                       }else{
+                                               switch(G.scene->toolsettings->cornertype) {
+                                                       case 0: fill_quad_double_adj_path(ef, gh, numcuts); break;
+                                                       case 1: fill_quad_double_adj_inner(ef, gh, numcuts); break;
+                                                       case 2: fill_quad_double_adj_fan(ef, gh, numcuts); break;
+                                               }
+                                                                                                 
+                                       }
+                                               break;  
+                               case 3: ef->f1 = SELECT;
+                                       fill_quad_triple(ef, gh, numcuts); 
+                                       break;  
+                               case 4: ef->f1 = SELECT;
+                                       fill_quad_quadruple(ef, gh, numcuts, rad, beauty); 
+                                       break;  
+                       }
+               } else {
+                       switch(edgecount) {
+                               case 0: break;
+                               case 1: ef->f1 = SELECT;
+                                       fill_tri_single(ef, gh, numcuts, seltype);
+                                       break;   
+                               case 2: ef->f1 = SELECT;
+                                       fill_tri_double(ef, gh, numcuts);
+                                       break;  
+                               case 3: ef->f1 = SELECT;
+                                       fill_tri_triple(ef, gh, numcuts, rad, beauty);
+                                       break;  
+                       }       
+               }       
+       }
+       
+       // Delete Old Edges and Faces
+       for(eed = em->edges.first;eed;eed = eed->next) {
+               if(BLI_ghash_haskey(gh,eed)) {
+                       eed->f1 = SELECT; 
+               } else {
+                       eed->f1 = 0;   
+               }
+       } 
+       free_tagged_edges_faces(em->edges.first, em->faces.first); 
+       
+       if(seltype == SUBDIV_SELECT_ORIG  && G.qual  != LR_CTRLKEY) {
+               /* bugfix: vertex could get flagged as "not-selected"
+               // solution: clear flags before, not at the same time as setting SELECT flag -dg
+               */
+               for(eed = em->edges.first;eed;eed = eed->next) {
+                       if(!(eed->f2 & EDGENEW || eed->f2 & EDGEOLD)) {
+                               eed->f &= !flag;
+                               EM_select_edge(eed,0); 
+                       }
+               }
+               for(eed = em->edges.first;eed;eed = eed->next) {
+                       if(eed->f2 & EDGENEW || eed->f2 & EDGEOLD) {
+                               eed->f |= flag;
+                               EM_select_edge(eed,1);
+                       }
+               }
+       } else if ((seltype == SUBDIV_SELECT_INNER || seltype == SUBDIV_SELECT_INNER_SEL)|| G.qual == LR_CTRLKEY) {
+               for(eed = em->edges.first;eed;eed = eed->next) {
+                       if(eed->f2 & EDGEINNER) {
+                               eed->f |= flag;
+                               EM_select_edge(eed,1);   
+                               if(eed->v1->f & EDGEINNER) eed->v1->f |= SELECT;
+                               if(eed->v2->f & EDGEINNER) eed->v2->f |= SELECT;
+                       }else{
+                               eed->f &= !flag;
+                               EM_select_edge(eed,0); 
+                       }
+               }                 
+       } else if(seltype == SUBDIV_SELECT_LOOPCUT){
+               for(eed = em->edges.first;eed;eed = eed->next) {
+                       if(eed->f2 & DOUBLEOPFILL){
+                               eed->f |= flag;
+                               EM_select_edge(eed,1);
+                       }else{
+                               eed->f &= !flag;
+                               EM_select_edge(eed,0);
+                       }
+               }
+       } 
+        if(G.scene->selectmode & SCE_SELECT_VERTEX) {
+                for(eed = em->edges.first;eed;eed = eed->next) {
+                       if(eed->f & SELECT) {
+                               eed->v1->f |= SELECT;
+                               eed->v2->f |= SELECT;
+                       }
+               }       
+       }
+       
+       //fix hide flags for edges. First pass, hide edges of hidden faces
+       for(ef=em->faces.first; ef; ef=ef->next){
+               if(ef->h){
+                       ef->e1->h |= 1;
+                       ef->e2->h |= 1;
+                       ef->e3->h |= 1;
+                       if(ef->e4) ef->e4->h |= 1;
+               }
+       }
+       //second pass: unhide edges of visible faces adjacent to hidden faces
+       for(ef=em->faces.first; ef; ef=ef->next){
+               if(ef->h == 0){
+                       ef->e1->h &= ~1;
+                       ef->e2->h &= ~1;
+                       ef->e3->h &= ~1;
+                       if(ef->e4) ef->e4->h &= ~1;
+               }
+       }
+       
+       // Free the ghash and call MEM_freeN on all the value entries to return 
+       // that memory
+       BLI_ghash_free(gh, NULL, (GHashValFreeFP)MEM_freeN);   
+       
+       EM_selectmode_flush();
+       for(ef=em->faces.first;ef;ef = ef->next) {
+               if(ef->e4) {
+                       if(  (ef->e1->f & SELECT && ef->e2->f & SELECT) &&
+                        (ef->e3->f & SELECT && ef->e4->f & SELECT) ) {
+                               ef->f |= SELECT;                         
+                       }                                  
+               } else {
+                       if(  (ef->e1->f & SELECT && ef->e2->f & SELECT) && ef->e3->f & SELECT) {
+                               ef->f |= SELECT;                         
+                       }
+               }
+       }
+       
+       recalc_editnormals();
+       countall();
+       allqueue(REDRAWVIEW3D, 0);
+       DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
+}
+
+static int count_selected_edges(EditEdge *ed)
+{
+       int totedge = 0;
+       while(ed) {
+               ed->tmp.p = 0;
+               if( ed->f & SELECT ) totedge++;
+               ed= ed->next;
+       }
+       return totedge;
+}
+
+/* hurms, as if this makes code readable! It's pointerpointer hiding... (ton) */
+typedef EditFace *EVPtr;
+typedef EVPtr EVPTuple[2];
+
+/** builds EVPTuple array efaa of face tuples (in fact pointers to EditFaces)
+       sharing one edge.
+       arguments: selected edge list, face list.
+       Edges will also be tagged accordingly (see eed->f2)               */
+
+static int collect_quadedges(EVPTuple *efaa, EditEdge *eed, EditFace *efa)
+{
+       EditEdge *e1, *e2, *e3;
+       EVPtr *evp;
+       int i = 0;
+
+       /* run through edges, if selected, set pointer edge-> facearray */
+       while(eed) {
+               eed->f2= 0;
+               eed->f1= 0;
+               if( eed->f & SELECT ) {
+                       eed->tmp.p = (EditVert *) (&efaa[i]);
+                       i++;
+               }
+               else eed->tmp.p = NULL;
+               
+               eed= eed->next;
+       }
+               
+       
+       /* find edges pointing to 2 faces by procedure:
+       
+       - run through faces and their edges, increase
+         face counter e->f1 for each face 
+       */
+
+       while(efa) {
+               efa->f1= 0;
+               if(efa->v4==0 && (efa->f & SELECT)) {  /* if selected triangle */
+                       e1= efa->e1;
+                       e2= efa->e2;
+                       e3= efa->e3;
+                       if(e1->f2<3 && e1->tmp.p) {
+                               if(e1->f2<2) {
+                                       evp= (EVPtr *) e1->tmp.p;
+                                       evp[(int)e1->f2] = efa;
+                               }
+                               e1->f2+= 1;
+                       }
+                       if(e2->f2<3 && e2->tmp.p) {
+                               if(e2->f2<2) {
+                                       evp= (EVPtr *) e2->tmp.p;
+                                       evp[(int)e2->f2]= efa;
+                               }
+                               e2->f2+= 1;
+                       }
+                       if(e3->f2<3 && e3->tmp.p) {
+                               if(e3->f2<2) {
+                                       evp= (EVPtr *) e3->tmp.p;
+                                       evp[(int)e3->f2]= efa;
+                               }
+                               e3->f2+= 1;
+                       }
+               }
+               else {
+                       /* set to 3 to make sure these are not flipped or joined */
+                       efa->e1->f2= 3;
+                       efa->e2->f2= 3;
+                       efa->e3->f2= 3;
+                       if (efa->e4) efa->e4->f2= 3;
+               }
+
+               efa= efa->next;
+       }
+       return i;
+}
+
+
+/* returns vertices of two adjacent triangles forming a quad 
+   - can be righthand or lefthand
+
+                       4-----3
+                       |\      |
+                       | \ 2 | <- efa1
+                       |  \  | 
+         efa-> | 1 \ | 
+                       |       \| 
+                       1-----2
+
+*/
+#define VTEST(face, num, other) \
+       (face->v##num != other->v1 && face->v##num != other->v2 && face->v##num != other->v3) 
+
+static void givequadverts(EditFace *efa, EditFace *efa1, EditVert **v1, EditVert **v2, EditVert **v3, EditVert **v4, int *vindex)
+{
+       if VTEST(efa, 1, efa1) {
+               *v1= efa->v1;
+               *v2= efa->v2;
+               vindex[0]= 0;
+               vindex[1]= 1;
+       }
+       else if VTEST(efa, 2, efa1) {
+               *v1= efa->v2;
+               *v2= efa->v3;
+               vindex[0]= 1;
+               vindex[1]= 2;
+       }
+       else if VTEST(efa, 3, efa1) {
+               *v1= efa->v3;
+               *v2= efa->v1;
+               vindex[0]= 2;
+               vindex[1]= 0;
+       }
+       
+       if VTEST(efa1, 1, efa) {
+               *v3= efa1->v1;
+               *v4= efa1->v2;
+               vindex[2]= 0;
+               vindex[3]= 1;
+       }
+       else if VTEST(efa1, 2, efa) {
+               *v3= efa1->v2;
+               *v4= efa1->v3;
+               vindex[2]= 1;
+               vindex[3]= 2;
+       }
+       else if VTEST(efa1, 3, efa) {
+               *v3= efa1->v3;
+               *v4= efa1->v1;
+               vindex[2]= 2;
+               vindex[3]= 0;
+       }
+       else
+               *v3= *v4= NULL;
+}
+
+/* Helper functions for edge/quad edit features*/
+static void untag_edges(EditFace *f)
+{
+       f->e1->f1 = 0;
+       f->e2->f1 = 0;
+       f->e3->f1 = 0;
+       if (f->e4) f->e4->f1 = 0;
+}
+
+/** remove and free list of tagged edges and faces */
+static void free_tagged_edges_faces(EditEdge *eed, EditFace *efa)
+{
+       EditMesh *em= G.editMesh;
+       EditEdge *nexted;
+       EditFace *nextvl;
+
+       while(efa) {
+               nextvl= efa->next;
+               if(efa->f1) {
+                       BLI_remlink(&em->faces, efa);
+                       free_editface(efa);
+               }
+               else
+                       /* avoid deleting edges that are still in use */
+                       untag_edges(efa);
+               efa= nextvl;
+       }
+
+       while(eed) {
+               nexted= eed->next;
+               if(eed->f1) {
+                       remedge(eed);
+                       free_editedge(eed);
+               }
+               eed= nexted;
+       }       
+}      
+
+/* note; the EM_selectmode_set() calls here illustrate how badly constructed it all is... from before the
+   edge/face flags, with very mixed results.... */
+void beauty_fill(void)
+{
+       EditMesh *em = G.editMesh;
+       EditVert *v1, *v2, *v3, *v4;
+       EditEdge *eed, *nexted;
+       EditEdge dia1, dia2;
+       EditFace *efa, *w;
+       // void **efaar, **efaa;
+       EVPTuple *efaar;
+       EVPtr *efaa;
+       float len1, len2, len3, len4, len5, len6, opp1, opp2, fac1, fac2;
+       int totedge, ok, notbeauty=8, onedone, vindex[4];
+       
+       if(multires_test()) return;
+
+       /* - all selected edges with two faces
+               * - find the faces: store them in edges (using datablock)
+               * - per edge: - test convex
+               *                          - test edge: flip?
+               *                          - if true: remedge,  addedge, all edges at the edge get new face pointers
+               */
+       
+       EM_selectmode_set();    // makes sure in selectmode 'face' the edges of selected faces are selected too 
+
+       totedge = count_selected_edges(em->edges.first);
+       if(totedge==0) return;
+
+       /* temp block with face pointers */
+       efaar= (EVPTuple *) MEM_callocN(totedge * sizeof(EVPTuple), "beautyfill");
+
+       while (notbeauty) {
+               notbeauty--;
+
+               ok = collect_quadedges(efaar, em->edges.first, em->faces.first);
+
+               /* there we go */
+               onedone= 0;
+
+               eed= em->edges.first;
+               while(eed) {
+                       nexted= eed->next;
+                       
+                       /* f2 is set in collect_quadedges() */
+                       if(eed->f2==2 && eed->h==0) {
+
+                               efaa = (EVPtr *) eed->tmp.p;
+
+                               /* none of the faces should be treated before, nor be part of fgon */
+                               ok= 1;
+                               efa= efaa[0];
+                               if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
+                               if(efa->fgonf) ok= 0;
+                               efa= efaa[1];
+                               if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
+                               if(efa->fgonf) ok= 0;
+                               
+                               if(ok) {
+                                       /* test convex */
+                                       givequadverts(efaa[0], efaa[1], &v1, &v2, &v3, &v4, vindex);
+                                       if(v1 && v2 && v3 && v4) {
+                                               if( convex(v1->co, v2->co, v3->co, v4->co) ) {
+
+                                                       /* test edges */
+                                                       if( (v1) > (v3) ) {
+                                                               dia1.v1= v3;
+                                                               dia1.v2= v1;
+                                                       }
+                                                       else {
+                                                               dia1.v1= v1;
+                                                               dia1.v2= v3;
+                                                       }
+
+                                                       if( (v2) > (v4) ) {
+                                                               dia2.v1= v4;
+                                                               dia2.v2= v2;
+                                                       }
+                                                       else {
+                                                               dia2.v1= v2;
+                                                               dia2.v2= v4;
+                                                       }
+
+                                                       /* testing rule:
+                                                        * the area divided by the total edge lengths
+                                                        */
+
+                                                       len1= len_v3v3(v1->co, v2->co);
+                                                       len2= len_v3v3(v2->co, v3->co);
+                                                       len3= len_v3v3(v3->co, v4->co);
+                                                       len4= len_v3v3(v4->co, v1->co);
+                                                       len5= len_v3v3(v1->co, v3->co);
+                                                       len6= len_v3v3(v2->co, v4->co);
+
+                                                       opp1= area_tri_v3(v1->co, v2->co, v3->co);
+                                                       opp2= area_tri_v3(v1->co, v3->co, v4->co);
+
+                                                       fac1= opp1/(len1+len2+len5) + opp2/(len3+len4+len5);
+
+                                                       opp1= area_tri_v3(v2->co, v3->co, v4->co);
+                                                       opp2= area_tri_v3(v2->co, v4->co, v1->co);
+
+                                                       fac2= opp1/(len2+len3+len6) + opp2/(len4+len1+len6);
+
+                                                       ok= 0;
+                                                       if(fac1 > fac2) {
+                                                               if(dia2.v1==eed->v1 && dia2.v2==eed->v2) {
+                                                                       eed->f1= 1;
+                                                                       efa= efaa[0];
+                                                                       efa->f1= 1;
+                                                                       efa= efaa[1];
+                                                                       efa->f1= 1;
+
+                                                                       w= EM_face_from_faces(efaa[0], efaa[1],
+                                                                               vindex[0], vindex[1], 4+vindex[2], -1);
+                                                                       w->f |= SELECT;
+
+
+                                                                       w= EM_face_from_faces(efaa[0], efaa[1],
+                                                                               vindex[0], 4+vindex[2], 4+vindex[3], -1);
+                                                                       w->f |= SELECT;
+
+                                                                       onedone= 1;
+                                                               }
+                                                       }
+                                                       else if(fac1 < fac2) {
+                                                               if(dia1.v1==eed->v1 && dia1.v2==eed->v2) {
+                                                                       eed->f1= 1;
+                                                                       efa= efaa[0];
+                                                                       efa->f1= 1;
+                                                                       efa= efaa[1];
+                                                                       efa->f1= 1;
+
+
+                                                                       w= EM_face_from_faces(efaa[0], efaa[1],
+                                                                               vindex[1], 4+vindex[2], 4+vindex[3], -1);
+                                                                       w->f |= SELECT;
+
+
+                                                                       w= EM_face_from_faces(efaa[0], efaa[1],
+                                                                               vindex[0], 4+vindex[1], 4+vindex[3], -1);
+                                                                       w->f |= SELECT;
+
+                                                                       onedone= 1;
+                                                               }
+                                                       }
+                                               }
+                                       }
+                               }
+
+                       }
+                       eed= nexted;
+               }
+
+               free_tagged_edges_faces(em->edges.first, em->faces.first);
+
+               if(onedone==0) break;
+               
+               EM_selectmode_set();    // new edges/faces were added
+       }
+
+       MEM_freeN(efaar);
+
+       EM_select_flush();
+       
+       allqueue(REDRAWVIEW3D, 0);
+       DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
+#ifdef WITH_VERSE
+       if(G.editMesh->vnode)
+               sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
+#endif
+       BIF_undo_push("Beauty Fill");
+}
+
+
+/* ******************** BEGIN TRIANGLE TO QUAD ************************************* */
+static float measure_facepair(EditVert *v1, EditVert *v2, EditVert *v3, EditVert *v4, float limit)
+{
+       
+       /*gives a 'weight' to a pair of triangles that join an edge to decide how good a join they would make*/
+       /*Note: this is more complicated than it needs to be and should be cleaned up...*/
+       float   measure = 0.0, noA1[3], noA2[3], noB1[3], noB2[3], normalADiff, normalBDiff,
+                       edgeVec1[3], edgeVec2[3], edgeVec3[3], edgeVec4[3], diff,
+                       minarea, maxarea, areaA, areaB;
+       
+       /*First Test: Normal difference*/
+       normal_tri_v3( noA1,v1->co, v2->co, v3->co);
+       normal_tri_v3( noA2,v1->co, v3->co, v4->co);
+       
+       if(noA1[0] == noA2[0] && noA1[1] == noA2[1] && noA1[2] == noA2[2]) normalADiff = 0.0;
+       else normalADiff = angle_v2v2(noA1, noA2);
+               //if(!normalADiff) normalADiff = 179;
+       normal_tri_v3( noB1,v2->co, v3->co, v4->co);
+       normal_tri_v3( noB2,v4->co, v1->co, v2->co);
+       
+       if(noB1[0] == noB2[0] && noB1[1] == noB2[1] && noB1[2] == noB2[2]) normalBDiff = 0.0;
+       else normalBDiff = angle_v2v2(noB1, noB2);
+               //if(!normalBDiff) normalBDiff = 179;
+       
+       measure += (normalADiff/360) + (normalBDiff/360);
+       if(measure > limit) return measure;
+       
+       /*Second test: Colinearity*/
+       sub_v3_v3v3(edgeVec1, v1->co, v2->co);
+       sub_v3_v3v3(edgeVec2, v2->co, v3->co);
+       sub_v3_v3v3(edgeVec3, v3->co, v4->co);
+       sub_v3_v3v3(edgeVec4, v4->co, v1->co);
+       
+       diff = 0.0;
+       
+       diff = (
+               fabs(angle_v2v2(edgeVec1, edgeVec2) - 90) +
+               fabs(angle_v2v2(edgeVec2, edgeVec3) - 90) + 
+               fabs(angle_v2v2(edgeVec3, edgeVec4) - 90) + 
+               fabs(angle_v2v2(edgeVec4, edgeVec1) - 90)) / 360;
+       if(!diff) return 0.0;
+       
+       measure +=  diff;
+       if(measure > limit) return measure;
+
+       /*Third test: Concavity*/
+       areaA = area_tri_v3(v1->co, v2->co, v3->co) + area_tri_v3(v1->co, v3->co, v4->co);
+       areaB = area_tri_v3(v2->co, v3->co, v4->co) + area_tri_v3(v4->co, v1->co, v2->co);
+       
+       if(areaA <= areaB) minarea = areaA;
+       else minarea = areaB;
+       
+       if(areaA >= areaB) maxarea = areaA;
+       else maxarea = areaB;
+       
+       if(!maxarea) measure += 1;
+       else measure += (1 - (minarea / maxarea));
+
+       return measure;
+}
+
+#define T2QUV_LIMIT 0.005
+#define T2QCOL_LIMIT 3
+static int compareFaceAttribs(EditFace *f1, EditFace *f2, EditEdge *eed) 
+{
+       /*Test to see if the per-face attributes for the joining edge match within limit*/      
+       MTFace *tf1, *tf2;
+       unsigned int *col1, *col2;
+       short i,attrok=0, flag = G.scene->toolsettings->editbutflag, fe1[2], fe2[2];
+       
+       tf1 = CustomData_em_get(&G.editMesh->fdata, f1->data, CD_MTFACE);
+       tf2 = CustomData_em_get(&G.editMesh->fdata, f2->data, CD_MTFACE);
+
+       col1 = CustomData_em_get(&G.editMesh->fdata, f1->data, CD_MCOL);
+       col2 = CustomData_em_get(&G.editMesh->fdata, f2->data, CD_MCOL);
+       
+       /*store indices for faceedges*/
+       f1->v1->f1 = 0;
+       f1->v2->f1 = 1;
+       f1->v3->f1 = 2;
+       
+       fe1[0] = eed->v1->f1;
+       fe1[1] = eed->v2->f1;
+       
+       f2->v1->f1 = 0;
+       f2->v2->f1 = 1;
+       f2->v3->f1 = 2;
+       
+       fe2[0] = eed->v1->f1;
+       fe2[1] = eed->v2->f1;
+       
+       /*compare faceedges for each face attribute. Additional per face attributes can be added later*/
+       /*do UVs*/
+       if(flag & B_JOINTRIA_UV){
+               
+               if(tf1 == NULL || tf2 == NULL) attrok |= B_JOINTRIA_UV;
+               else if(tf1->tpage != tf2->tpage); /*do nothing*/
+               else{
+                       for(i = 0; i < 2; i++){
+                               if(tf1->uv[fe1[i]][0] + T2QUV_LIMIT > tf2->uv[fe2[i]][0] && tf1->uv[fe1[i]][0] - T2QUV_LIMIT < tf2->uv[fe2[i]][0] &&
+                                       tf1->uv[fe1[i]][1] + T2QUV_LIMIT > tf2->uv[fe2[i]][1] && tf1->uv[fe1[i]][1] - T2QUV_LIMIT < tf2->uv[fe2[i]][1]) attrok |= B_JOINTRIA_UV;
+                       }
+               }
+       }
+       
+       /*do VCOLs*/
+       if(flag & B_JOINTRIA_VCOL){
+               if(!col1 || !col2) attrok |= B_JOINTRIA_VCOL;
+               else{
+                       char *f1vcol, *f2vcol;
+                       for(i = 0; i < 2; i++){
+                               f1vcol = (char *)&(col1[fe1[i]]);
+                               f2vcol = (char *)&(col2[fe2[i]]);
+               
+                               /*compare f1vcol with f2vcol*/
+                               if(     f1vcol[1] + T2QCOL_LIMIT > f2vcol[1] && f1vcol[1] - T2QCOL_LIMIT < f2vcol[1] &&
+                                       f1vcol[2] + T2QCOL_LIMIT > f2vcol[2] && f1vcol[2] - T2QCOL_LIMIT < f2vcol[2] &&
+                                       f1vcol[3] + T2QCOL_LIMIT > f2vcol[3] && f1vcol[3] - T2QCOL_LIMIT < f2vcol[3]) attrok |= B_JOINTRIA_VCOL;
+                       }
+               }
+       }
+       
+       if( ((attrok & B_JOINTRIA_UV) == (flag & B_JOINTRIA_UV)) && ((attrok & B_JOINTRIA_VCOL) == (flag & B_JOINTRIA_VCOL)) ) return 1;
+       return 0;
+}      
+       
+static int fplcmp(const void *v1, const void *v2)
+{
+       const EditEdge *e1= *((EditEdge**)v1), *e2=*((EditEdge**)v2);
+       
+       if( e1->crease > e2->crease) return 1;
+       else if( e1->crease < e2->crease) return -1;
+       
+       return 0;
+}
+
+/*Bitflags for edges.*/
+#define T2QDELETE      1
+#define T2QCOMPLEX     2
+#define T2QJOIN                4
+void join_triangles(void)
+{
+       EditMesh *em=G.editMesh;
+       EditVert *v1, *v2, *v3, *v4, *eve;
+       EditEdge *eed, **edsortblock = NULL, **edb = NULL;
+       EditFace *efa;
+       EVPTuple *efaar = NULL;
+       EVPtr *efaa = NULL;
+       float *creases = NULL;
+       float measure; /*Used to set tolerance*/
+       float limit = G.scene->toolsettings->jointrilimit;
+       int i, ok, totedge=0, totseledge=0, complexedges, vindex[4];
+       
+       /*test for multi-resolution data*/
+       if(multires_test()) return;
+
+       /*if we take a long time on very dense meshes we want waitcursor to display*/
+       waitcursor(1);
+       
+       totseledge = count_selected_edges(em->edges.first);
+       if(totseledge==0) return;
+       
+       /*abusing crease value to store weights for edge pairs. Nasty*/
+       for(eed=em->edges.first; eed; eed=eed->next) totedge++;
+       if(totedge) creases = MEM_callocN(sizeof(float) * totedge, "Join Triangles Crease Array"); 
+       for(eed=em->edges.first, i = 0; eed; eed=eed->next, i++){
+               creases[i] = eed->crease; 
+               eed->crease = 0.0;
+       }
+       
+       /*clear temp flags*/
+       for(eve=em->verts.first; eve; eve=eve->next) eve->f1 = eve->f2 = 0;
+       for(eed=em->edges.first; eed; eed=eed->next) eed->f2 = eed->f1 = 0;
+       for(efa=em->faces.first; efa; efa=efa->next) efa->f1 = efa->tmp.l = 0;
+
+       /*For every selected 2 manifold edge, create pointers to its two faces.*/
+       efaar= (EVPTuple *) MEM_callocN(totseledge * sizeof(EVPTuple), "Tri2Quad");
+       ok = collect_quadedges(efaar, em->edges.first, em->faces.first);
+       complexedges = 0;
+       
+       if(ok){
+               
+               
+               /*clear tmp.l flag and store number of faces that are selected and coincident to current face here.*/  
+               for(eed=em->edges.first; eed; eed=eed->next){
+                       /* eed->f2 is 2 only if this edge is part of exactly two
+                          triangles, and both are selected, and it has EVPTuple assigned */
+                       if(eed->f2 == 2){
+                               efaa= (EVPtr *) eed->tmp.p;
+                               efaa[0]->tmp.l++;
+                               efaa[1]->tmp.l++;
+                       }
+               }
+               
+               for(eed=em->edges.first; eed; eed=eed->next){
+                       if(eed->f2 == 2){
+                               efaa= (EVPtr *) eed->tmp.p;
+                               v1 = v2 = v3 = v4 = NULL;
+                               givequadverts(efaa[0], efaa[1], &v1, &v2, &v3, &v4, vindex);
+                               if(v1 && v2 && v3 && v4){
+                                       /*test if simple island first. This mimics 2.42 behaviour and the tests are less restrictive.*/
+                                       if(efaa[0]->tmp.l == 1 && efaa[1]->tmp.l == 1){
+                                               if( convex(v1->co, v2->co, v3->co, v4->co) ){ 
+                                                       eed->f1 |= T2QJOIN;
+                                                       efaa[0]->f1 = 1; //mark for join
+                                                       efaa[1]->f1 = 1; //mark for join
+                                               }
+                                       }
+                                       else{ 
+                                               
+                                               /*      The face pair is part of a 'complex' island, so the rules for dealing with it are more involved.
+                                                       Depending on what options the user has chosen, this face pair can be 'thrown out' based upon the following criteria:
+                                                       
+                                                       1: the two faces do not share the same material
+                                                       2: the edge joining the two faces is marked as sharp.
+                                                       3: the two faces UV's do not make a good match
+                                                       4: the two faces Vertex colors do not make a good match
+                                                       
+                                                       If the face pair passes all the applicable tests, it is then given a 'weight' with the measure_facepair() function.
+                                                       This measures things like concavity, colinearity ect. If this weight is below the threshold set by the user
+                                                       the edge joining them is marked as being 'complex' and will be compared against other possible pairs which contain one of the
+                                                       same faces in the current pair later.
+                                               
+                                                       This technique is based upon an algorithm that Campbell Barton developed for his Tri2Quad script that was previously part of
+                                                       the python scripts bundled with Blender releases.
+                                               */
+                                               
+                                               if(G.scene->toolsettings->editbutflag & B_JOINTRIA_SHARP && eed->sharp); /*do nothing*/
+                                               else if(G.scene->toolsettings->editbutflag & B_JOINTRIA_MAT && efaa[0]->mat_nr != efaa[1]->mat_nr); /*do nothing*/
+                                               else if(((G.scene->toolsettings->editbutflag & B_JOINTRIA_UV) || (G.scene->toolsettings->editbutflag & B_JOINTRIA_VCOL)) &&
+                                                               compareFaceAttribs(efaa[0], efaa[1], eed) == 0); /*do nothing*/
+                                               else{   
+                                                       measure = measure_facepair(v1, v2, v3, v4, limit);
+                                                       if(measure < limit){
+                                                               complexedges++;
+                                                               eed->f1 |= T2QCOMPLEX;
+                                                               eed->crease = measure; /*we dont mark edges for join yet*/
+                                                       }
+                                               }
+                                       }
+                               }
+                       }
+               }
+               
+               /*Quicksort the complex edges according to their weighting*/
+               if(complexedges){
+                       edsortblock = edb = MEM_callocN(sizeof(EditEdge*) * complexedges, "Face Pairs quicksort Array");
+                       for(eed = em->edges.first; eed; eed=eed->next){
+                               if(eed->f1 & T2QCOMPLEX){
+                                       *edb = eed;
+                                       edb++;
+                               }
+                       }
+                       qsort(edsortblock, complexedges, sizeof(EditEdge*), fplcmp);
+                       /*now go through and mark the edges who get the highest weighting*/
+                       for(edb=edsortblock, i=0; i < complexedges; edb++, i++){ 
+                               efaa = (EVPtr *)((*edb)->tmp.p); /*suspect!*/
+                               if( !efaa[0]->f1 && !efaa[1]->f1){
+                                       efaa[0]->f1 = 1; //mark for join
+                                       efaa[1]->f1 = 1; //mark for join
+                                       (*edb)->f1 |= T2QJOIN;
+                               }
+                       }
+               }
+               
+               /*finally go through all edges marked for join (simple and complex) and create new faces*/ 
+               for(eed=em->edges.first; eed; eed=eed->next){
+                       if(eed->f1 & T2QJOIN){
+                               efaa= (EVPtr *)eed->tmp.p;
+                               v1 = v2 = v3 = v4 = NULL;
+                               givequadverts(efaa[0], efaa[1], &v1, &v2, &v3, &v4, vindex);
+                               if((v1 && v2 && v3 && v4) && (exist_face(v1, v2, v3, v4)==0)){ /*exist_face is very slow! Needs to be adressed.*/
+                                       /*flag for delete*/
+                                       eed->f1 |= T2QDELETE;
+                                       /*create new quad and select*/
+                                       efa = EM_face_from_faces(efaa[0], efaa[1], vindex[0], vindex[1], 4+vindex[2], 4+vindex[3]);
+                                       EM_select_face(efa,1);
+                               }
+                               else{
+                                               efaa[0]->f1 = 0;
+                                               efaa[1]->f1 = 0;
+                               }
+                       }
+               }
+       }
+       
+       /*free data and cleanup*/
+       if(creases){
+               for(eed=em->edges.first, i = 0; eed; eed=eed->next, i++) eed->crease = creases[i]; 
+               MEM_freeN(creases);
+       }
+       for(eed=em->edges.first; eed; eed=eed->next){
+               if(eed->f1 & T2QDELETE) eed->f1 = 1;
+               else eed->f1 = 0;
+       }
+       free_tagged_edges_faces(em->edges.first, em->faces.first);
+       if(efaar) MEM_freeN(efaar);
+       if(edsortblock) MEM_freeN(edsortblock);
+               
+       EM_selectmode_flush();
+       countall();
+       allqueue(REDRAWVIEW3D, 0);
+       DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
+       #ifdef WITH_VERSE
+       if(G.editMesh->vnode)
+               sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
+       #endif
+       waitcursor(0);
+       BIF_undo_push("Convert Triangles to Quads");
+}
+/* ******************** END TRIANGLE TO QUAD ************************************* */
+
+#define FACE_MARKCLEAR(f) (f->f1 = 1)
+
+/* quick hack, basically a copy of beauty_fill */
+void edge_flip(void)
+{
+       EditMesh *em = G.editMesh;
+       EditVert *v1, *v2, *v3, *v4;
+       EditEdge *eed, *nexted;
+       EditFace *efa, *w;
+       //void **efaar, **efaa;
+       EVPTuple *efaar;
+       EVPtr *efaa;
+       int totedge, ok, vindex[4];
+       
+       /* - all selected edges with two faces
+        * - find the faces: store them in edges (using datablock)
+        * - per edge: - test convex
+        *                         - test edge: flip?
+                                               - if true: remedge,  addedge, all edges at the edge get new face pointers
+        */
+
+       EM_selectmode_flush();  // makes sure in selectmode 'face' the edges of selected faces are selected too 
+
+       totedge = count_selected_edges(em->edges.first);
+       if(totedge==0) return;
+
+       /* temporary array for : edge -> face[1], face[2] */
+       efaar= (EVPTuple *) MEM_callocN(totedge * sizeof(EVPTuple), "edgeflip");
+
+       ok = collect_quadedges(efaar, em->edges.first, em->faces.first);
+       
+       eed= em->edges.first;
+       while(eed) {
+               nexted= eed->next;
+               
+               if(eed->f2==2) {  /* points to 2 faces */
+                       
+                       efaa= (EVPtr *) eed->tmp.p;
+                       
+                       /* don't do it if flagged */
+
+                       ok= 1;
+                       efa= efaa[0];
+                       if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
+                       efa= efaa[1];
+                       if(efa->e1->f1 || efa->e2->f1 || efa->e3->f1) ok= 0;
+                       
+                       if(ok) {
+                               /* test convex */
+                               givequadverts(efaa[0], efaa[1], &v1, &v2, &v3, &v4, vindex);
+
+/*
+               4-----3         4-----3
+               |\      |               |       /|
+               | \ 1 |         | 1 / |
+               |  \  |  ->     |  /  | 
+               | 0 \ |         | / 0 | 
+               |       \|              |/      |
+               1-----2         1-----2
+*/
+                               /* make new faces */
+                               if (v1 && v2 && v3) {
+                                       if( convex(v1->co, v2->co, v3->co, v4->co) ) {
+                                               if(exist_face(v1, v2, v3, v4)==0) {
+                                                       /* outch this may break seams */ 
+                                                       w= EM_face_from_faces(efaa[0], efaa[1], vindex[0],
+                                                               vindex[1], 4+vindex[2], -1);
+
+                                                       EM_select_face(w, 1);
+
+                                                       /* outch this may break seams */
+                                                       w= EM_face_from_faces(efaa[0], efaa[1], vindex[0],
+                                                               4+vindex[2], 4+vindex[3], -1);
+
+                                                       EM_select_face(w, 1);
+                                               }
+                                               /* tag as to-be-removed */
+                                               FACE_MARKCLEAR(efaa[1]);
+                                               FACE_MARKCLEAR(efaa[0]);
+                                               eed->f1 = 1; 
+                                               
+                                       } /* endif test convex */
+                               }
+                       }
+               }
+               eed= nexted;
+       }
+
+       /* clear tagged edges and faces: */
+       free_tagged_edges_faces(em->edges.first, em->faces.first);
+       
+       MEM_freeN(efaar);
+       
+       allqueue(REDRAWVIEW3D, 0);
+       DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
+#ifdef WITH_VERSE
+       if(G.editMesh->vnode)
+               sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
+#endif
+       BIF_undo_push("Flip Triangle Edges");
+       
+}
+
+static void edge_rotate(EditEdge *eed,int dir)
+{
+       EditMesh *em = G.editMesh;
+       EditVert **verts[2];
+       EditFace *face[2], *efa, *newFace[2];
+       EditEdge **edges[2], **hiddenedges, *srchedge;
+       int facecount, p1, p2, p3, p4, fac1, fac2, i, j;
+       int numhidden, numshared, p[2][4];
+       
+       /* check to make sure that the edge is only part of 2 faces */
+       facecount = 0;
+       for(efa = em->faces.first;efa;efa = efa->next) {
+               if((efa->e1 == eed || efa->e2 == eed) || (efa->e3 == eed || efa->e4 == eed)) {
+                       if(facecount >= 2) {
+                               /* more than two faces with this edge */
+                               return;
+                       }
+                       else {
+                               face[facecount] = efa;
+                               facecount++;
+                       }
+               }
+       }
+       if(facecount < 2)
+               return;
+
+       /* how many edges does each face have */
+       if(face[0]->e4) fac1= 4;
+       else fac1= 3;
+
+       if(face[1]->e4) fac2= 4;
+       else fac2= 3;
+       
+       /* make a handy array for verts and edges */
+       verts[0]= &face[0]->v1;
+       edges[0]= &face[0]->e1;
+       verts[1]= &face[1]->v1;
+       edges[1]= &face[1]->e1;
+
+       /* we don't want to rotate edges between faces that share more than one edge */
+       numshared= 0;
+       for(i=0; i<fac1; i++)
+               for(j=0; j<fac2; j++)
+                       if (edges[0][i] == edges[1][j])
+                               numshared++;
+
+       if(numshared > 1)
+               return;
+       
+       /* coplaner faces only please */
+       if(dot_v3v3(face[0]->n,face[1]->n) <= 0.000001)
+               return;
+       
+       /* we want to construct an array of vertex indicis in both faces, starting at
+          the last vertex of the edge being rotated.
+          - first we find the two vertices that lie on the rotating edge
+          - then we make sure they are ordered according to the face vertex order
+          - and then we construct the array */
+       p1= p2= p3= p4= 0;
+
+       for(i=0; i<4; i++) {
+               if(eed->v1 == verts[0][i]) p1 = i;
+               if(eed->v2 == verts[0][i]) p2 = i;
+               if(eed->v1 == verts[1][i]) p3 = i;
+               if(eed->v2 == verts[1][i]) p4 = i;
+       }
+       
+       if((p1+1)%fac1 == p2)
+               SWAP(int, p1, p2);
+       if((p3+1)%fac2 == p4)
+               SWAP(int, p3, p4);
+       
+       for (i = 0; i < 4; i++) {
+               p[0][i]= (p1 + i)%fac1;
+               p[1][i]= (p3 + i)%fac2;
+       }
+
+       /* create an Array of the Edges who have h set prior to rotate */
+       numhidden = 0;
+       for(srchedge = em->edges.first;srchedge;srchedge = srchedge->next)
+               if(srchedge->h && ((srchedge->v1->f & SELECT) || (srchedge->v2->f & SELECT)))
+                       numhidden++;
+
+       hiddenedges = MEM_mallocN(sizeof(EditVert*)*numhidden+1, "RotateEdgeHiddenVerts");
+       if(!hiddenedges) {
+        error("Malloc Was not happy!");
+        return;   
+    }
+
+    numhidden = 0;
+       for(srchedge=em->edges.first; srchedge; srchedge=srchedge->next)
+               if(srchedge->h && (srchedge->v1->f & SELECT || srchedge->v2->f & SELECT))
+                       hiddenedges[numhidden++] = srchedge;
+
+       /* create the 2 new faces */
+       if(fac1 == 3 && fac2 == 3) {
+               /* no need of reverse setup */
+
+               newFace[0]= EM_face_from_faces(face[0], face[1], p[0][1], p[0][2], 4+p[1][1], -1);
+               newFace[1]= EM_face_from_faces(face[1], face[0], p[1][1], p[1][2], 4+p[0][1], -1);
+       }
+       else if(fac1 == 4 && fac2 == 3) {
+               if(dir == 1) {
+                       newFace[0]= EM_face_from_faces(face[0], face[1], p[0][1], p[0][2], p[0][3], 4+p[1][1]);
+                       newFace[1]= EM_face_from_faces(face[1], face[0], p[1][1], p[1][2], 4+p[0][1], -1);
+               } else if (dir == 2) {
+                       newFace[0]= EM_face_from_faces(face[0], face[1], p[0][2], 4+p[1][1], p[0][0], p[0][1]);
+                       newFace[1]= EM_face_from_faces(face[1], face[0], 4+p[0][2], p[1][0], p[1][1], -1);
+                       
+                       verts[0][p[0][2]]->f |= SELECT;
+                       verts[1][p[1][1]]->f |= SELECT;         
+               }
+       }
+       else if(fac1 == 3 && fac2 == 4) {
+               if(dir == 1) {
+                       newFace[0]= EM_face_from_faces(face[0], face[1], p[0][1], p[0][2], 4+p[1][1], -1);
+                       newFace[1]= EM_face_from_faces(face[1], face[0], p[1][1], p[1][2], p[1][3], 4+p[0][1]);
+               } else if (dir == 2) {
+                       newFace[0]= EM_face_from_faces(face[0], face[1], p[0][0], p[0][1], 4+p[1][2], -1);
+                       newFace[1]= EM_face_from_faces(face[1], face[0], p[1][1], p[1][2], 4+p[0][1], 4+p[0][2]);
+                       
+                       verts[0][p[0][1]]->f |= SELECT;
+                       verts[1][p[1][2]]->f |= SELECT; 
+               }
+       
+       }
+       else if(fac1 == 4 && fac2 == 4) {
+               if(dir == 1) {
+                       newFace[0]= EM_face_from_faces(face[0], face[1], p[0][1], p[0][2], p[0][3], 4+p[1][1]);
+                       newFace[1]= EM_face_from_faces(face[1], face[0], p[1][1], p[1][2], p[1][3], 4+p[0][1]);
+               } else if (dir == 2) {
+                       newFace[0]= EM_face_from_faces(face[0], face[1], p[0][2], p[0][3], 4+p[1][1], 4+p[1][2]);
+                       newFace[1]= EM_face_from_faces(face[1], face[0], p[1][2], p[1][3], 4+p[0][1], 4+p[0][2]);
+                       
+                       verts[0][p[0][2]]->f |= SELECT;
+                       verts[1][p[1][2]]->f |= SELECT; 
+               }
+       }               
+       else
+               return; /* This should never happen */
+
+       if(dir == 1 || (fac1 == 3 && fac2 == 3)) {
+               verts[0][p[0][1]]->f |= SELECT;
+               verts[1][p[1][1]]->f |= SELECT;
+       }
+       
+       /* copy old edge's flags to new center edge*/
+       for(srchedge=em->edges.first;srchedge;srchedge=srchedge->next) {
+               if((srchedge->v1->f & SELECT) && (srchedge->v2->f & SELECT)) {
+                       srchedge->f = eed->f;
+                       srchedge->h = eed->h;
+                       srchedge->dir = eed->dir;
+                       srchedge->seam = eed->seam;
+                       srchedge->crease = eed->crease;
+                       srchedge->bweight = eed->bweight;
+               }
+       }
+       
+       /* resetting hidden flag */
+       for(numhidden--; numhidden>=0; numhidden--)
+               hiddenedges[numhidden]->h= 1;
+       
+       /* check for orhphan edges */
+       for(srchedge=em->edges.first; srchedge; srchedge=srchedge->next)
+               srchedge->f1= -1;   
+       
+       /* cleanup */
+       MEM_freeN(hiddenedges);
+       
+       /* get rid of the old edge and faces*/
+       remedge(eed);
+       free_editedge(eed);     
+       BLI_remlink(&em->faces, face[0]);
+       free_editface(face[0]); 
+       BLI_remlink(&em->faces, face[1]);
+       free_editface(face[1]);         
+}
+
+/* only accepts 1 selected edge, or 2 selected faces */
+void edge_rotate_selected(int dir)
+{
+       EditEdge *eed;
+       EditFace *efa;
+       short edgeCount = 0;
+       
+       /*clear new flag for new edges, count selected edges */
+       for(eed= G.editMesh->edges.first; eed; eed= eed->next) {
+               eed->f1= 0;
+               eed->f2 &= ~2;
+               if(eed->f & SELECT) edgeCount++;        
+       }
+       
+       if(edgeCount>1) {
+               /* more selected edges, check faces */
+               for(efa= G.editMesh->faces.first; efa; efa= efa->next) {
+                       if(efa->f & SELECT) {
+                               efa->e1->f1++;
+                               efa->e2->f1++;
+                               efa->e3->f1++;
+                               if(efa->e4) efa->e4->f1++;
+                       }
+               }
+               edgeCount= 0;
+               for(eed= G.editMesh->edges.first; eed; eed= eed->next) {
+                       if(eed->f1==2) edgeCount++;
+               }
+               if(edgeCount==1) {
+                       for(eed= G.editMesh->edges.first; eed; eed= eed->next) {
+                               if(eed->f1==2) {
+                                       edge_rotate(eed,dir);
+                                       break;
+                               }
+                       }
+               }
+               else error("Select one edge or two adjacent faces");
+       }
+       else if(edgeCount==1) {
+               for(eed= G.editMesh->edges.first; eed; eed= eed->next) {
+                       if(eed->f & SELECT) {
+                               EM_select_edge(eed, 0);
+                               edge_rotate(eed,dir);
+                               break;
+                       }
+               }
+       }
+       else error("Select one edge or two adjacent faces");
+       
+
+       /* flush selected vertices (again) to edges/faces */
+       EM_select_flush();
+       
+       allqueue(REDRAWVIEW3D, 0);
+       DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
+
+#ifdef WITH_VERSE
+       if(G.editMesh->vnode)
+               sync_all_versefaces_with_editfaces((VNode*)G.editMesh->vnode);
+#endif
+
+       BIF_undo_push("Rotate Edge");   
+}
+
+/******************* BEVEL CODE STARTS HERE ********************/
+
+static void bevel_displace_vec(float *midvec, float *v1, float *v2, float *v3, float d, float no[3])
+{
+       float a[3], c[3], n_a[3], n_c[3], mid[3], ac, ac2, fac;
+
+       sub_v3_v3v3(a, v1, v2);
+       sub_v3_v3v3(c, v3, v2);
+
+       cross_v3_v3v3(n_a, a, no);
+       normalize_v3(n_a);
+       cross_v3_v3v3(n_c, no, c);
+       normalize_v3(n_c);
+
+       normalize_v3(a);
+       normalize_v3(c);
+       ac = dot_v3v3(a, c);
+
+       if (ac == 1 || ac == -1) {
+               midvec[0] = midvec[1] = midvec[2] = 0;
+               return;
+       }
+       ac2 = ac * ac;
+       fac = (float)sqrt((ac2 + 2*ac + 1)/(1 - ac2) + 1);
+       add_v3_v3v3(mid, n_c, n_a);
+       normalize_v3(mid);
+       mul_v3_fl(mid, d * fac);
+       add_v3_v3v3(mid, mid, v2);
+       copy_v3_v3(midvec, mid);
+}
+
+/*     Finds the new point using the sinus law to extrapolate a triangle
+       Lots of sqrts which would not be good for a real time algo
+       Using the mid  point of the extrapolation of both sides 
+       Useless for coplanar quads, but that doesn't happen too often */
+static void fix_bevel_wrap(float *midvec, float *v1, float *v2, float *v3, float *v4, float d, float no[3]) 
+{
+       float a[3], b[3], c[3], l_a, l_b, l_c, s_a, s_b, s_c, Pos1[3], Pos2[3], Dir[3];
+
+       sub_v3_v3v3(a, v3, v2);
+       l_a = normalize_v3(a);
+       sub_v3_v3v3(b, v4, v3);
+       normalize_v3(b);
+       sub_v3_v3v3(c, v1, v2);
+       normalize_v3(c);
+
+       s_b = dot_v3v3(a, c);
+       s_b = (float)sqrt(1 - (s_b * s_b));
+       s_a = dot_v3v3(b, c);
+       s_a = (float)sqrt(1 - (s_a * s_a));
+       mul_v3_fl(a, -1);
+       s_c = dot_v3v3(a, b);
+       s_c = (float)sqrt(1 - (s_c * s_c));
+
+       l_b = s_b * l_a / s_a;
+       l_c = s_c * l_a / s_a;
+
+       mul_v3_fl(b, l_b);
+       mul_v3_fl(c, l_c);
+
+       add_v3_v3v3(Pos1, v2, c);
+       add_v3_v3v3(Pos2, v3, b);
+
+       add_v3_v3v3(Dir, Pos1, Pos2);
+       mul_v3_fl(Dir, 0.5);
+
+       bevel_displace_vec(midvec, v3, Dir, v2, d, no);
+
+}
+
+
+static char detect_wrap(float *o_v1, float *o_v2, float *v1, float *v2, float *no) 
+{
+       float o_a[3], a[3], o_c[3], c[3];
+
+       sub_v3_v3v3(o_a, o_v1, o_v2);
+       sub_v3_v3v3(a, v1, v2);
+
+       cross_v3_v3v3(o_c, o_a, no);
+       cross_v3_v3v3(c, a, no);
+
+       if (dot_v3v3(c, o_c) <= 0)
+               return 1;
+       else
+               return 0;
+}
+
+// Detects and fix a quad wrapping after the resize
+// Arguments are the orginal verts followed by the final verts and then the bevel size and the normal
+static void fix_bevel_quad_wrap(float *o_v1, float *o_v2, float *o_v3, float *o_v4, float *v1, float *v2, float *v3, float *v4, float d, float *no) 
+{
+       float vec[3];
+       char wrap[4];
+       
+       // Quads can wrap partially. Watch out
+       wrap[0] = detect_wrap(o_v1, o_v2, v1, v2, no); // Edge 1-2
+       wrap[1] = detect_wrap(o_v2, o_v3, v2, v3, no); // Edge 2-3
+       wrap[2] = detect_wrap(o_v3, o_v4, v3, v4, no); // Edge 3-4
+       wrap[3] = detect_wrap(o_v4, o_v1, v4, v1, no); // Edge 4-1
+
+       // Edge 1 inverted
+       if (wrap[0] == 1 && wrap[1] == 0 && wrap[2] == 0 && wrap[3] == 0) {
+               fix_bevel_wrap(vec, o_v2, o_v3, o_v4, o_v1, d, no);
+               copy_v3_v3(v1, vec);
+               copy_v3_v3(v2, vec);
+       }
+       // Edge 2 inverted
+       else if (wrap[0] == 0 && wrap[1] == 1 && wrap[2] == 0 && wrap[3] == 0) {
+               fix_bevel_wrap(vec, o_v3, o_v4, o_v1, o_v2, d, no);
+               copy_v3_v3(v2, vec);
+               copy_v3_v3(v3, vec);
+       }
+       // Edge 3 inverted
+       else if (wrap[0] == 0 && wrap[1] == 0 && wrap[2] == 1 && wrap[3] == 0) {
+               fix_bevel_wrap(vec, o_v4, o_v1, o_v2, o_v3, d, no);
+               copy_v3_v3(v3, vec);
+               copy_v3_v3(v4, vec);
+       }
+       // Edge 4 inverted
+       else if (wrap[0] == 0 && wrap[1] == 0 && wrap[2] == 0 && wrap[3] == 1) {
+               fix_bevel_wrap(vec, o_v1, o_v2, o_v3, o_v4, d, no);
+               copy_v3_v3(v4, vec);
+               copy_v3_v3(v1, vec);
+       }
+       // Edge 2 and 4 inverted
+       else if (wrap[0] == 0 && wrap[1] == 1 && wrap[2] == 0 && wrap[3] == 1) {
+               add_v3_v3v3(vec, v2, v3);
+               mul_v3_fl(vec, 0.5);
+               copy_v3_v3(v2, vec);
+               copy_v3_v3(v3, vec);
+               add_v3_v3v3(vec, v1, v4);
+               mul_v3_fl(vec, 0.5);
+               copy_v3_v3(v1, vec);
+               copy_v3_v3(v4, vec);
+       }
+       // Edge 1 and 3 inverted
+       else if (wrap[0] == 1 && wrap[1] == 0 && wrap[2] == 1 && wrap[3] == 0) {
+               add_v3_v3v3(vec, v1, v2);
+               mul_v3_fl(vec, 0.5);
+               copy_v3_v3(v1, vec);
+               copy_v3_v3(v2, vec);
+               add_v3_v3v3(vec, v3, v4);
+               mul_v3_fl(vec, 0.5);
+               copy_v3_v3(v3, vec);
+               copy_v3_v3(v4, vec);
+       }
+       // Totally inverted
+       else if (wrap[0] == 1 && wrap[1] == 1 && wrap[2] == 1 && wrap[3] == 1) {
+               add_v3_v3v3(vec, v1, v2);
+               add_v3_v3v3(vec, vec, v3);
+               add_v3_v3v3(vec, vec, v4);
+               mul_v3_fl(vec, 0.25);
+               copy_v3_v3(v1, vec);
+               copy_v3_v3(v2, vec);
+               copy_v3_v3(v3, vec);
+               copy_v3_v3(v4, vec);
+       }
+
+}
+
+// Detects and fix a tri wrapping after the resize
+// Arguments are the orginal verts followed by the final verts and the normal
+// Triangles cannot wrap partially (not in this situation
+static void fix_bevel_tri_wrap(float *o_v1, float *o_v2, float *o_v3, float *v1, float *v2, float *v3, float *no) 
+{
+       if (detect_wrap(o_v1, o_v2, v1, v2, no)) {
+               float vec[3];
+               add_v3_v3v3(vec, o_v1, o_v2);
+               add_v3_v3v3(vec, vec, o_v3);
+               mul_v3_fl(vec, 1.0f/3.0f);
+               copy_v3_v3(v1, vec);
+               copy_v3_v3(v2, vec);
+               copy_v3_v3(v3, vec);
+       }
+}
+
+static void bevel_shrink_faces(float d, int flag)
+{
+       EditMesh *em = G.editMesh;
+       EditFace *efa;
+       float vec[3], no[3], v1[3], v2[3], v3[3], v4[3];
+
+       /* move edges of all faces with efa->f1 & flag closer towards their centers */
+       efa= em->faces.first;
+       while (efa) {
+               if (efa->f1 & flag) {
+                       copy_v3_v3(v1, efa->v1->co);
+                       copy_v3_v3(v2, efa->v2->co);
+                       copy_v3_v3(v3, efa->v3->co);
+                       copy_v3_v3(no, efa->n);
+                       if (efa->v4 == NULL) {
+                               bevel_displace_vec(vec, v1, v2, v3, d, no);
+                               copy_v3_v3(efa->v2->co, vec);
+                               bevel_displace_vec(vec, v2, v3, v1, d, no);
+                               copy_v3_v3(efa->v3->co, vec);
+                               bevel_displace_vec(vec, v3, v1, v2, d, no);
+                               copy_v3_v3(efa->v1->co, vec);
+
+                               fix_bevel_tri_wrap(v1, v2, v3, efa->v1->co, efa->v2->co, efa->v3->co, no);
+                       } else {
+                               copy_v3_v3(v4, efa->v4->co);
+                               bevel_displace_vec(vec, v1, v2, v3, d, no);
+                               copy_v3_v3(efa->v2->co, vec);
+                               bevel_displace_vec(vec, v2, v3, v4, d, no);
+                               copy_v3_v3(efa->v3->co, vec);
+                               bevel_displace_vec(vec, v3, v4, v1, d, no);
+                               copy_v3_v3(efa->v4->co, vec);
+                               bevel_displace_vec(vec, v4, v1, v2, d, no);
+                               copy_v3_v3(efa->v1->co, vec);
+
+                               fix_bevel_quad_wrap(v1, v2, v3, v4, efa->v1->co, efa->v2->co, efa->v3->co, efa->v4->co, d, no);
+                       }
+               }
+               efa= efa->next;
+       }       
+}
+
+static void bevel_shrink_draw(float d, int flag)
+{
+       EditMesh *em = G.editMesh;
+       EditFace *efa;
+       float vec[3], no[3], v1[3], v2[3], v3[3], v4[3], fv1[3], fv2[3], fv3[3], fv4[3];
+
+       /* move edges of all faces with efa->f1 & flag closer towards their centers */
+       efa= em->faces.first;
+       while (efa) {
+               copy_v3_v3(v1, efa->v1->co);
+               copy_v3_v3(v2, efa->v2->co);
+               copy_v3_v3(v3, efa->v3->co);
+               copy_v3_v3(no, efa->n);
+               if (efa->v4 == NULL) {
+                       bevel_displace_vec(vec, v1, v2, v3, d, no);
+                       copy_v3_v3(fv2, vec);
+                       bevel_displace_vec(vec, v2, v3, v1, d, no);
+                       copy_v3_v3(fv3, vec);
+                       bevel_displace_vec(vec, v3, v1, v2, d, no);
+                       copy_v3_v3(fv1, vec);
+
+                       fix_bevel_tri_wrap(v1, v2, v3, fv1, fv2, fv3, no);
+
+                       glBegin(GL_LINES);
+                       glVertex3fv(fv1);
+                       glVertex3fv(fv2);
+                       glEnd();                                                
+                       glBegin(GL_LINES);
+                       glVertex3fv(fv2);
+                       glVertex3fv(fv3);
+                       glEnd();                                                
+                       glBegin(GL_LINES);
+                       glVertex3fv(fv1);
+                       glVertex3fv(fv3);
+                       glEnd();                                                
+               } else {
+                       copy_v3_v3(v4, efa->v4->co);
+                       bevel_displace_vec(vec, v4, v1, v2, d, no);
+                       copy_v3_v3(fv1, vec);
+                       bevel_displace_vec(vec, v1, v2, v3, d, no);
+                       copy_v3_v3(fv2, vec);
+                       bevel_displace_vec(vec, v2, v3, v4, d, no);
+                       copy_v3_v3(fv3, vec);
+                       bevel_displace_vec(vec, v3, v4, v1, d, no);
+                       copy_v3_v3(fv4, vec);
+
+                       fix_bevel_quad_wrap(v1, v2, v3, v4, fv1, fv2, fv3, fv4, d, no);
+
+                       glBegin(GL_LINES);
+                       glVertex3fv(fv1);
+                       glVertex3fv(fv2);
+                       glEnd();                                                
+                       glBegin(GL_LINES);
+                       glVertex3fv(fv2);
+                       glVertex3fv(fv3);
+                       glEnd();                                                
+                       glBegin(GL_LINES);
+                       glVertex3fv(fv3);
+                       glVertex3fv(fv4);
+                       glEnd();                                                
+                       glBegin(GL_LINES);
+                       glVertex3fv(fv1);
+                       glVertex3fv(fv4);
+                       glEnd();                                                
+               }
+               efa= efa->next;
+       }       
+}
+
+static void bevel_mesh(float bsize, int allfaces)
+{
+       EditMesh *em = G.editMesh;
+//#define BEV_DEBUG
+/* Enables debug printfs and assigns material indices: */
+/* 2 = edge quad                                                                          */
+/* 3 = fill polygon (vertex clusters)                            */
+
+       EditFace *efa, *example; //, *nextvl;
+       EditEdge *eed, *eed2;
+       EditVert *neweve[1024], *eve, *eve2, *eve3, *v1, *v2, *v3, *v4; //, *eve4;
+       //short found4,  search;
+       //float f1, f2, f3, f4;
+       float cent[3], min[3], max[3];
+       int a, b, c;
+       float limit= 0.001f;
+       
+       if(multires_test()) return;
+
+       waitcursor(1);
+
+       removedoublesflag(1, 0, limit);
+
+       /* tag all original faces */
+       efa= em->faces.first;
+       while (efa) {
+               efa->f1= 0;
+               if (faceselectedAND(efa, 1)||allfaces) {
+                       efa->f1= 1;
+                       efa->v1->f |= 128;
+                       efa->v2->f |= 128;
+                       efa->v3->f |= 128;
+                       if (efa->v4) efa->v4->f |= 128;                 
+               }
+               efa->v1->f &= ~64;
+               efa->v2->f &= ~64;
+               efa->v3->f &= ~64;
+               if (efa->v4) efa->v4->f &= ~64;         
+
+               efa= efa->next;
+       }
+
+#ifdef BEV_DEBUG
+       fprintf(stderr,"bevel_mesh: split\n");
+#endif
+       
+       efa= em->faces.first;
+       while (efa) {
+               if (efa->f1 & 1) {
+                       efa->f1-= 1;
+                       v1= addvertlist(efa->v1->co, efa->v1);
+                       v1->f= efa->v1->f & ~128;
+                       efa->v1->tmp.v = v1;
+
+                       v1= addvertlist(efa->v2->co, efa->v2);
+                       v1->f= efa->v2->f & ~128;
+                       efa->v2->tmp.v = v1;
+
+                       v1= addvertlist(efa->v3->co, efa->v3);
+                       v1->f= efa->v3->f & ~128;
+                       efa->v3->tmp.v = v1;
+
+                       if (efa->v4) {
+                               v1= addvertlist(efa->v4->co, efa->v4);
+                               v1->f= efa->v4->f & ~128;
+                               efa->v4->tmp.v = v1;
+                       }
+
+                       /* Needs better adaption of creases? */
+                       addedgelist(efa->e1->v1->tmp.v, 
+                                               efa->e1->v2->tmp.v, 
+                                               efa->e1);
+                       addedgelist(efa->e2->v1->tmp.v,
+                                               efa->e2->v2->tmp.v, 
+                                               efa->e2);
+                       addedgelist(efa->e3->v1->tmp.v,
+                                               efa->e3->v2->tmp.v,
+                                               efa->e3);
+                       if (efa->e4) addedgelist(efa->e4->v1->tmp.v,
+                                                                        efa->e4->v2->tmp.v,
+                                                                        efa->e4);
+
+                       if(efa->v4) {
+                               v1 = efa->v1->tmp.v;
+                               v2 = efa->v2->tmp.v;
+                               v3 = efa->v3->tmp.v;
+                               v4 = efa->v4->tmp.v;
+                               addfacelist(v1, v2, v3, v4, efa,NULL);
+                       } else {
+                               v1= efa->v1->tmp.v;
+                               v2= efa->v2->tmp.v;
+                               v3= efa->v3->tmp.v;
+                               addfacelist(v1, v2, v3, 0, efa,NULL);
+                       }
+
+                       efa= efa-> next;
+               } else {
+                       efa= efa->next;
+               }
+       }
+       
+       for(efa= em->faces.first; efa; efa= efa->next) {
+               if( (efa->v1->f & 128) && (efa->v2->f & 128) && (efa->v3->f & 128) ) {
+                       if(efa->v4==NULL || (efa->v4->f & 128)) efa->f |= 128;
+               }
+       }
+
+       delfaceflag(128); // works with face flag now
+
+       /* tag all faces for shrink*/
+       efa= em->faces.first;
+       while (efa) {
+               if (faceselectedAND(efa, 1)||allfaces) {
+                       efa->f1= 2;
+               }
+               efa= efa->next;
+       }
+
+#ifdef BEV_DEBUG
+       fprintf(stderr,"bevel_mesh: make edge quads\n");
+#endif
+
+       /* find edges that are on each other and make quads between them */
+
+       eed= em->edges.first;
+       while(eed) {
+               eed->f2= eed->f1= 0;
+               if ( ((eed->v1->f & eed->v2->f) & 1) || allfaces) 
+                       eed->f1 |= 4;   /* original edges */
+               eed->tmp.v = 0;
+               eed= eed->next;
+       }
+
+       eed= em->edges.first;
+       while (eed) {
+               if ( ((eed->f1 & 2)==0) && (eed->f1 & 4) ) {
+                       eed2= em->edges.first;
+                       while (eed2) {
+                               if ( (eed2 != eed) && ((eed2->f1 & 2)==0) && (eed->f1 & 4) ) {
+                                       if (
+                                          (eed->v1 != eed2->v1) &&
+                                          (eed->v1 != eed2->v2) &&                                        
+                                          (eed->v2 != eed2->v1) &&
+                                          (eed->v2 != eed2->v2) &&     (
+                                          ( compare_v3v3(eed->v1->co, eed2->v1->co, limit) &&
+                                                compare_v3v3(eed->v2->co, eed2->v2->co, limit) ) ||
+                                          ( compare_v3v3(eed->v1->co, eed2->v2->co, limit) &&
+                                                compare_v3v3(eed->v2->co, eed2->v1->co, limit) ) ) )
+                                               {
+                                               
+#ifdef BEV_DEBUG                                               
+                                               fprintf(stderr, "bevel_mesh: edge quad\n");
+#endif                                         
+                                               
+                                               eed->f1 |= 2;   /* these edges are finished */
+                                               eed2->f1 |= 2;
+                                               
+                                               example= NULL;
+                                               efa= em->faces.first;   /* search example face (for mat_nr, ME_SMOOTH, ...) */
+                                               while (efa) {
+                                                       if ( (efa->e1 == eed) ||
+                                                                (efa->e2 == eed) ||
+                                                                (efa->e3 == eed) ||
+                                                                (efa->e4 && (efa->e4 == eed)) ) {
+                                                               example= efa;
+                                                               efa= NULL;
+                                                       }
+                                                       if (efa) efa= efa->next;
+                                               }
+                                               
+                                               neweve[0]= eed->v1; neweve[1]= eed->v2;
+                                               neweve[2]= eed2->v1; neweve[3]= eed2->v2;
+                                               
+                                               if(exist_face(neweve[0], neweve[1], neweve[2], neweve[3])==0) {
+                                                       efa= NULL;
+
+                                                       if (compare_v3v3(eed->v1->co, eed2->v2->co, limit)) {
+                                                               efa= addfacelist(neweve[0], neweve[1], neweve[2], neweve[3], example,NULL);
+                                                       } else {
+                                                               efa= addfacelist(neweve[0], neweve[2], neweve[3], neweve[1], example,NULL);
+                                                       }
+                                               
+                                                       if(efa) {
+                                                               float inp;      
+                                                               normal_tri_v3( efa->n,efa->v1->co, efa->v2->co, efa->v3->co);
+                                                               inp= efa->n[0]*G.vd->viewmat[0][2] + efa->n[1]*G.vd->viewmat[1][2] + efa->n[2]*G.vd->viewmat[2][2];
+                                                               if(inp < 0.0) flipface(efa);
+#ifdef BEV_DEBUG
+                                                               efa->mat_nr= 1;
+#endif
+                                                       } else fprintf(stderr,"bevel_mesh: error creating face\n");
+                                               }
+                                               eed2= NULL;
+                                       }
+                               }
+                               if (eed2) eed2= eed2->next;
+                       }
+               }
+               eed= eed->next;
+       }
+
+       eed= em->edges.first;
+       while(eed) {
+               eed->f2= eed->f1= 0;
+               eed->f1= 0;
+               eed->v1->f1 &= ~1;
+               eed->v2->f1 &= ~1;              
+               eed->tmp.v = 0;
+               eed= eed->next;
+       }
+
+#ifdef BEV_DEBUG
+       fprintf(stderr,"bevel_mesh: find clusters\n");
+#endif 
+
+       /* Look for vertex clusters */
+
+       eve= em->verts.first;
+       while (eve) {
+               eve->f &= ~(64|128);
+               eve->tmp.v = NULL;
+               eve= eve->next;
+       }
+       
+       /* eve->f: 128: first vertex in a list (->tmp.v) */
+       /*                64: vertex is in a list */
+       
+       eve= em->verts.first;
+       while (eve) {
+               eve2= em->verts.first;
+               eve3= NULL;
+               while (eve2) {
+                       if ((eve2 != eve) && ((eve2->f & (64|128))==0)) {
+                               if (compare_v3v3(eve->co, eve2->co, limit)) {
+                                       if ((eve->f & (128|64)) == 0) {
+                                               /* fprintf(stderr,"Found vertex cluster:\n  *\n  *\n"); */
+                                               eve->f |= 128;
+                                               eve->tmp.v = eve2;
+                                               eve3= eve2;
+                                       } else if ((eve->f & 64) == 0) {
+                                               /* fprintf(stderr,"  *\n"); */
+                                               if (eve3) eve3->tmp.v = eve2;
+                                               eve2->f |= 64;
+                                               eve3= eve2;
+                                       }
+                               }
+                       }
+                       eve2= eve2->next;
+                       if (!eve2) {
+                               if (eve3) eve3->tmp.v = NULL;
+                       }
+               }
+               eve= eve->next;
+       }
+
+#ifdef BEV_DEBUG
+       fprintf(stderr,"bevel_mesh: shrink faces\n");
+#endif 
+
+       bevel_shrink_faces(bsize, 2);
+
+#ifdef BEV_DEBUG
+       fprintf(stderr,"bevel_mesh: fill clusters\n");
+#endif
+       
+       /* Make former vertex clusters faces */
+
+       eve= em->verts.first;
+       while (eve) {
+               eve->f &= ~64;
+               eve= eve->next;
+       }
+
+       eve= em->verts.first;
+       while (eve) {
+               if (eve->f & 128) {
+                       eve->f &= ~128;
+                       a= 0;
+                       neweve[a]= eve;
+                       eve2 = eve->tmp.v;
+                       while (eve2) {
+                               a++;
+                               neweve[a]= eve2;
+                               eve2 = eve2->tmp.v;
+                       }
+                       a++;
+                       efa= NULL;
+                       if (a>=3) {
+                               example= NULL;
+                               efa= em->faces.first;   /* search example face */
+                               while (efa) {
+                                       if ( (efa->v1 == neweve[0]) ||
+                                                (efa->v2 == neweve[0]) ||
+                                                (efa->v3 == neweve[0]) ||
+                                                (efa->v4 && (efa->v4 == neweve[0])) ) {
+                                               example= efa;
+                                               efa= NULL;
+                                       }
+                                       if (efa) efa= efa->next;
+                               }
+#ifdef BEV_DEBUG                               
+                               fprintf(stderr,"bevel_mesh: Making %d-gon\n", a);
+#endif                         
+                               if (a>4) {
+                                       cent[0]= cent[1]= cent[2]= 0.0;                         
+                                       INIT_MINMAX(min, max);                          
+                                       for (b=0; b<a; b++) {
+                                               add_v3_v3v3(cent, cent, neweve[b]->co);
+                                               DO_MINMAX(neweve[b]->co, min, max);
+                                       }
+                                       cent[0]= (min[0]+max[0])/2;
+                                       cent[1]= (min[1]+max[1])/2;
+                                       cent[2]= (min[2]+max[2])/2;
+                                       eve2= addvertlist(cent, NULL);
+                                       eve2->f |= 1;
+                                       eed= em->edges.first;
+                                       while (eed) {
+                                               c= 0;
+                                               for (b=0; b<a; b++) 
+                                                       if ((neweve[b]==eed->v1) || (neweve[b]==eed->v2)) c++;
+                                               if (c==2) {
+                                                       if(exist_face(eed->v1, eed->v2, eve2, 0)==0) {
+                                                               efa= addfacelist(eed->v1, eed->v2, eve2, 0, example,NULL);
+#ifdef BEV_DEBUG
+                                                               efa->mat_nr= 2;
+#endif                                                         
+                                                       }
+                                               }
+                                               eed= eed->next;
+                                       }
+                               } else if (a==4) {
+                                       if(exist_face(neweve[0], neweve[1], neweve[2], neweve[3])==0) {
+                                               /* the order of vertices can be anything, three cases to check */
+                                               if( convex(neweve[0]->co, neweve[1]->co, neweve[2]->co, neweve[3]->co) ) {
+                                                       efa= addfacelist(neweve[0], neweve[1], neweve[2], neweve[3], NULL, NULL);
+                                               }
+                                               else if( convex(neweve[0]->co, neweve[2]->co, neweve[3]->co, neweve[1]->co) ) {
+                                                       efa= addfacelist(neweve[0], neweve[2], neweve[3], neweve[1], NULL, NULL);
+                                               }
+                                               else if( convex(neweve[0]->co, neweve[2]->co, neweve[1]->co, neweve[3]->co) ) {
+                                                       efa= addfacelist(neweve[0], neweve[2], neweve[1], neweve[3], NULL, NULL);
+                                               }
+                                       }                               
+                               }
+                               else if (a==3) {
+                                       if(exist_face(neweve[0], neweve[1], neweve[2], 0)==0)
+                                               efa= addfacelist(neweve[0], neweve[1], neweve[2], 0, example, NULL);
+                               }
+                               if(efa) {
+                                       float inp;      
+                                       normal_tri_v3( efa->n,neweve[0]->co, neweve[1]->co, neweve[2]->co);
+                                       inp= efa->n[0]*G.vd->viewmat[0][2] + efa->n[1]*G.vd->viewmat[1][2] + efa->n[2]*G.vd->viewmat[2][2];
+                                       if(inp < 0.0) flipface(efa);
+#ifdef BEV_DEBUG
+                                               efa->mat_nr= 2;
+#endif                                                                                         
+                               }                               
+                       }
+               }
+               eve= eve->next;
+       }
+
+       eve= em->verts.first;
+       while (eve) {
+               eve->f1= 0;
+               eve->f &= ~(128|64);
+               eve->tmp.v= NULL;
+               eve= eve->next;
+       }
+       
+       recalc_editnormals();
+       waitcursor(0);
+       countall();
+       allqueue(REDRAWVIEW3D, 0);
+       DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
+       
+       removedoublesflag(1, 0, limit);
+
+       /* flush selected vertices to edges/faces */
+       EM_select_flush();
+
+#undef BEV_DEBUG
+}
+
+static void bevel_mesh_recurs(float bsize, short recurs, int allfaces) 
+{
+       float d;
+       short nr;
+
+       d= bsize;
+       for (nr=0; nr<recurs; nr++) {
+               bevel_mesh(d, allfaces);
+               if (nr==0) d /= 3; else d /= 2;
+       }
+}
+
+void bevel_menu(void)
+{
+       BME_Mesh *bm;
+       BME_TransData_Head *td;
+       TransInfo *t;
+       int options, res, gbm_free = 0;
+
+       t = BIF_GetTransInfo();
+       if (!G.editBMesh) {
+               G.editBMesh = MEM_callocN(sizeof(*(G.editBMesh)),"bevel_menu() G.editBMesh");
+               gbm_free = 1;
+       }
+
+       G.editBMesh->options = BME_BEVEL_RUNNING | BME_BEVEL_SELECT;
+       G.editBMesh->res = 1;
+
+       while(G.editBMesh->options & BME_BEVEL_RUNNING) {
+               options = G.editBMesh->options;
+               res = G.editBMesh->res;
+               bm = BME_editmesh_to_bmesh(G.editMesh);
+               BIF_undo_push("Pre-Bevel");
+               free_editMesh(G.editMesh);
+               BME_bevel(bm,0.1f,res,options,0,0,&td);
+               BME_bmesh_to_editmesh(bm, td);
+               EM_selectmode_flush();
+               G.editBMesh->bm = bm;
+               G.editBMesh->td = td;
+               initTransform(TFM_BEVEL,CTX_BMESH);
+               Transform();
+               BME_free_transdata(td);
+               BME_free_mesh(bm);
+               if (t->state != TRANS_CONFIRM) {
+                       BIF_undo();
+               }
+               if (options == G.editBMesh->options) {
+                       G.editBMesh->options &= ~BME_BEVEL_RUNNING;
+               }
+       }
+
+       if (gbm_free) {
+               MEM_freeN(G.editBMesh);
+               G.editBMesh = NULL;
+       }
+}
+
+
+void bevel_menu_old()
+{
+       char Finished = 0, Canceled = 0, str[100], Recalc = 0;
+       short mval[2], oval[2], curval[2], event = 0, recurs = 1, nr;
+       float vec[3], d, drawd=0.0, center[3], fac = 1;
+
+       getmouseco_areawin(mval);
+       oval[0] = mval[0]; oval[1] = mval[1];
+
+       // Silly hackish code to initialise the variable (warning if not done)
+       // while still drawing in the first iteration (and without using another variable)
+       curval[0] = mval[0] + 1; curval[1] = mval[1] + 1;
+
+       // Init grabz for window to vec conversions
+       initgrabz(-G.vd->ofs[0], -G.vd->ofs[1], -G.vd->ofs[2]);
+       window_to_3d(center, mval[0], mval[1]);
+
+       if(button(&recurs, 1, 4, "Recursion:")==0) return;
+
+       for (nr=0; nr<recurs-1; nr++) {
+               if (nr==0) fac += 1.0f/3.0f; else fac += 1.0f/(3 * nr * 2.0f);
+       }
+       
+       EM_set_flag_all(SELECT);
+               
+       SetBlenderCursor(SYSCURSOR);
+
+       while (Finished == 0)
+       {
+               getmouseco_areawin(mval);
+               if (mval[0] != curval[0] || mval[1] != curval[1] || (Recalc == 1))
+               {
+                       Recalc = 0;
+                       curval[0] = mval[0];
+                       curval[1] = mval[1];
+                       
+                       window_to_3d(vec, mval[0]-oval[0], mval[1]-oval[1]);
+                       d = normalize_v3(vec) / 10;
+
+
+                       drawd = d * fac;
+                       if (G.qual & LR_CTRLKEY)
+                               drawd = (float) floor(drawd * 10.0f)/10.0f;
+                       if (G.qual & LR_SHIFTKEY)
+                               drawd /= 10;
+
+                       /*------------- Preview lines--------------- */
+                       
+                       /* uses callback mechanism to draw it all in current area */
+                       scrarea_do_windraw(curarea);                    
+                       
+                       /* set window matrix to perspective, default an area returns with buttons transform */
+                       persp(PERSP_VIEW);
+                       /* make a copy, for safety */
+                       glPushMatrix();
+                       /* multiply with the object transformation */
+                       mymultmatrix(G.obedit->obmat);
+                       
+                       glColor3ub(255, 255, 0);
+
+                       // PREVIEW CODE GOES HERE
+                       bevel_shrink_draw(drawd, 2);
+
+                       /* restore matrix transform */
+                       glPopMatrix();
+                       
+                       sprintf(str, "Bevel Size: %.4f          LMB to confirm, RMB to cancel, SPACE to input directly.", drawd);
+                       headerprint(str);
+
+                       /* this also verifies other area/windows for clean swap */
+                       screen_swapbuffers();
+
+                       persp(PERSP_WIN);
+                       
+                       glDrawBuffer(GL_FRONT);
+                       
+                       BIF_ThemeColor(TH_WIRE);
+
+                       setlinestyle(3);
+                       glBegin(GL_LINE_STRIP); 
+                               glVertex2sv(mval); 
+                               glVertex2sv(oval); 
+                       glEnd();
+                       setlinestyle(0);
+                       
+                       persp(PERSP_VIEW);
+                       bglFlush(); // flush display for frontbuffer
+                       glDrawBuffer(GL_BACK);
+               }
+               while(qtest()) {
+                       short val=0;                    
+                       event= extern_qread(&val);      // extern_qread stores important events for the mainloop to handle 
+
+                       /* val==0 on key-release event */
+                       if(val && (event==ESCKEY || event==RIGHTMOUSE || event==LEFTMOUSE || event==RETKEY || event==ESCKEY)) {
+                               if (event==RIGHTMOUSE || event==ESCKEY)
+                                       Canceled = 1;
+                               Finished = 1;
+                       }
+                       else if (val && event==SPACEKEY) {
+                               if (fbutton(&d, 0.000, 10.000, 10, 0, "Width:")!=0) {
+                                       drawd = d * fac;
+                                       Finished = 1;
+                               }
+                       }
+                       else if (val) {
+                               /* On any other keyboard event, recalc */
+                               Recalc = 1;
+                       }
+
+               }       
+       }
+       if (Canceled==0) {
+               SetBlenderCursor(BC_WAITCURSOR);
+               bevel_mesh_recurs(drawd/fac, recurs, 1);
+               righthandfaces(1);
+               SetBlenderCursor(SYSCURSOR);
+               BIF_undo_push("Bevel");
+       }
+}
+
+/* -------------------- More tools ------------------ */
+
+void mesh_set_face_flags(short mode)
+{
+       EditMesh *em = G.editMesh;
+       EditFace *efa;
+       MTFace *tface;
+       short   m_tex=0, m_tiles=0, m_shared=0,
+                       m_light=0, m_invis=0, m_collision=0,
+                       m_twoside=0, m_obcolor=0, m_halo=0,
+                       m_billboard=0, m_shadow=0, m_text=0,
+                       m_sort=0;
+       short flag = 0, change = 0;
+       
+       if (!EM_texFaceCheck()) {
+               error("not a mesh with uv/image layers");
+               return;
+       }
+       
+       add_numbut(0, TOG|SHO, "Texture", 0, 0, &m_tex, NULL);
+       add_numbut(1, TOG|SHO, "Tiles", 0, 0, &m_tiles, NULL);
+       add_numbut(2, TOG|SHO, "Light", 0, 0, &m_light, NULL);
+       add_numbut(3, TOG|SHO, "Invisible", 0, 0, &m_invis, NULL);
+       add_numbut(4, TOG|SHO, "Collision", 0, 0, &m_collision, NULL);
+       add_numbut(5, TOG|SHO, "Shared", 0, 0, &m_shared, NULL);
+       add_numbut(6, TOG|SHO, "Twoside", 0, 0, &m_twoside, NULL);
+       add_numbut(7, TOG|SHO, "ObColor", 0, 0, &m_obcolor, NULL);
+       add_numbut(8, TOG|SHO, "Halo", 0, 0, &m_halo, NULL);
+       add_numbut(9, TOG|SHO, "Billboard", 0, 0, &m_billboard, NULL);
+       add_numbut(10, TOG|SHO, "Shadow", 0, 0, &m_shadow, NULL);
+       add_numbut(11, TOG|SHO, "Text", 0, 0, &m_text, NULL);
+       add_numbut(12, TOG|SHO, "Sort", 0, 0, &m_sort, NULL);
+       
+       if (!do_clever_numbuts((mode ? "Set Flags" : "Clear Flags"), 13, REDRAW))
+               return;
+       
+       /* these 2 cant both be on */
+       if (mode) /* are we seeting*/
+               if (m_halo)
+                       m_billboard = 0;
+       
+       if (m_tex)                      flag |= TF_TEX;
+       if (m_tiles)            flag |= TF_TILES;
+       if (m_shared)           flag |= TF_SHAREDCOL;
+       if (m_light)            flag |= TF_LIGHT;
+       if (m_invis)            flag |= TF_INVISIBLE;
+       if (m_collision)        flag |= TF_DYNAMIC;
+       if (m_twoside)          flag |= TF_TWOSIDE;
+       if (m_obcolor)          flag |= TF_OBCOL;
+       if (m_halo)                     flag |= TF_BILLBOARD;
+       if (m_billboard)        flag |= TF_BILLBOARD2;
+       if (m_shadow)           flag |= TF_SHADOW;
+       if (m_text)                     flag |= TF_BMFONT;
+       if (m_sort)                     flag |= TF_ALPHASORT;
+       
+       if (flag==0)
+               return;
+       
+       efa= em->faces.first;
+       while(efa) {
+               if(efa->f & SELECT) {
+                       tface= CustomData_em_get(&em->fdata, efa->data, CD_MTFACE);
+                       if (mode)       tface->mode |= flag;
+                       else            tface->mode &= ~flag;
+                       change = 1;
+               }
+               efa= efa->next;
+       }
+       
+       if (change) {
+               BIF_undo_push((mode ? "Set Flags" : "Clear Flags"));
+               
+               allqueue(REDRAWIMAGE, 0);
+               allqueue(REDRAWVIEW3D, 0);
+       }
+}
+
+void mesh_set_smooth_faces(short event)
+{
+       EditMesh *em = G.editMesh;
+       EditFace *efa;
+
+       if(G.obedit==0) return;
+       
+       if(G.obedit->type != OB_MESH) return;
+       
+       efa= em->faces.first;
+       while(efa) {
+               if(efa->f & SELECT) {
+                       if(event==1) efa->flag |= ME_SMOOTH;
+                       else if(event==0) efa->flag &= ~ME_SMOOTH;
+               }
+               efa= efa->next;
+       }
+       
+       DAG_object_flush_update(G.scene, G.obedit, OB_RECALC_DATA);
+       allqueue(REDRAWVIEW3D, 0);
+       
+       if(event==1) BIF_undo_push("Set Smooth");
+       else if(event==0) BIF_undo_push("Set Solid");
+}
+
+/* helper to find edge for edge_rip */
+static float mesh_rip_edgedist(float mat[][4], float *co1, float *co2, short *mval)
+{
+       float vec1[3], vec2[3], mvalf[2];
+       
+       view3d_project_float(curarea, co1, vec1, mat);
+       view3d_project_float(curarea, co2, vec2, mat);
+       mvalf[0]= (float)mval[0];
+       mvalf[1]= (float)mval[1];
+       
+       return dist_to_line_segment_v2(mvalf, vec1, vec2);
+}
+
+/* helper for below */
+static void mesh_rip_setface(EditFace *sefa)
+{
+