svn merge -r41899:41926 ^/trunk/blender. also sync mempool with trunk and move BLI_me...
authorCampbell Barton <ideasman42@gmail.com>
Wed, 16 Nov 2011 19:06:38 +0000 (19:06 +0000)
committerCampbell Barton <ideasman42@gmail.com>
Wed, 16 Nov 2011 19:06:38 +0000 (19:06 +0000)
16 files changed:
1  2 
release/scripts/startup/bl_ui/space_view3d.py
source/blender/blenkernel/intern/dynamicpaint.c
source/blender/blenkernel/intern/particle.c
source/blender/blenkernel/intern/particle_system.c
source/blender/blenlib/BLI_mempool.h
source/blender/blenlib/intern/BLI_mempool.c
source/blender/blenloader/intern/readfile.c
source/blender/bmesh/bmesh_operator_api.h
source/blender/bmesh/intern/bmesh_newcore.c
source/blender/bmesh/intern/bmesh_walkers.c
source/blender/bmesh/operators/subdivideop.c
source/blender/editors/mesh/knifetool.c
source/blender/modifiers/intern/MOD_array.c
source/blender/modifiers/intern/MOD_fluidsim_util.c
source/blender/modifiers/intern/MOD_ocean.c
source/blender/render/intern/source/render_texture.c

index 54b4e5584ebb43d44cb132a5a76092abbf86e04a,2a81966986ffac8ee5e443768d03aaa031867dff..2f56bc87665dccd7aaca5df3cf1e79684ea5723e
   *  \brief Simple fast memory allocator.
   */
  
 +#ifdef __cplusplus
 +extern "C"
 +{
 +#endif
 +
  struct BLI_mempool;
- #include "BLI_listbase.h"
- #include "BLI_blenlib.h"
- #include <string.h>
- typedef struct BLI_freenode{
-       struct BLI_freenode *next;
-       int freeword; /*used to identify this as a freed node*/
- }BLI_freenode;
- typedef struct BLI_mempool_chunk{
-       struct BLI_mempool_chunk *next, *prev;
-       void *data;
- }BLI_mempool_chunk;
- typedef struct BLI_mempool{
-       struct ListBase chunks;
-       int esize, csize, pchunk;               /*size of elements and chunks in bytes and number of elements per chunk*/
-       BLI_freenode *free;             /*free element list. Interleaved into chunk datas.*/
-       int totalloc, totused; /*total number of elements allocated in total, and currently in use*/
-       int use_sysmalloc, allow_iter;
- }BLI_mempool;
++struct BLI_mempool_chunk;
 +
++typedef struct BLI_mempool BLI_mempool;
 +
 +/*allow_iter allows iteration on this mempool.  note: this requires that the
 +  first four bytes of the elements never contain the character string
 +  'free'.  use with care.*/
  
- BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk,
-                                                               int use_sysmalloc, int allow_iter);
- //void *BLI_mempool_alloc(BLI_mempool *pool);
 -struct BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk, int use_sysmalloc);
 -void *BLI_mempool_alloc(struct BLI_mempool *pool);
 -void *BLI_mempool_calloc(struct BLI_mempool *pool);
 -void BLI_mempool_free(struct BLI_mempool *pool, void *addr);
 -void BLI_mempool_destroy(struct BLI_mempool *pool);
++struct BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk,
++                                       int use_sysmalloc, int allow_iter);
++void *BLI_mempool_alloc(BLI_mempool *pool);
 +void *BLI_mempool_calloc(BLI_mempool *pool);
 +void BLI_mempool_free(BLI_mempool *pool, void *addr);
 +void BLI_mempool_destroy(BLI_mempool *pool);
 +int BLI_mempool_count(BLI_mempool *pool);
 +
 +/** iteration stuff.  note: this may easy to produce bugs with **/
 +/*private structure*/
 +typedef struct BLI_mempool_iter {
 +      BLI_mempool *pool;
 +      struct BLI_mempool_chunk *curchunk;
 +      int curindex;
 +} BLI_mempool_iter;
 +
 +/*allow iteration on this mempool.  note: this requires that the
 +  first four bytes of the elements never contain the character string
 +  'free'.  use with care.*/
 +void BLI_mempool_allow_iter(BLI_mempool *pool);
 +void BLI_mempool_iternew(BLI_mempool *pool, BLI_mempool_iter *iter);
 +void *BLI_mempool_iterstep(BLI_mempool_iter *iter);
 +
- /* XXX - copied from BKE_utildefines.h, dont use here because we're in BLI */
- #if defined(__sgi) || defined (__sparc) || defined (__sparc__) || defined (__PPC__) || defined (__ppc__) || defined (__hppa__) || defined (__BIG_ENDIAN__)
-       /* Big Endian */
- #define MAKE_ID(a,b,c,d) ( (int)(a)<<24 | (int)(b)<<16 | (c)<<8 | (d) )
- #else
-       /* Little Endian */
- #define MAKE_ID(a,b,c,d) ( (int)(d)<<24 | (int)(c)<<16 | (b)<<8 | (a) )
- #endif
- /************ inlined stuff ***********/
- #define FREEWORD MAKE_ID('f', 'r', 'e', 'e')
- #include "MEM_guardedalloc.h"
- BM_INLINE void *BLI_mempool_alloc(BLI_mempool *pool) {
-       void *retval=NULL;
-       BLI_freenode *curnode=NULL;
-       char *addr=NULL;
-       
-       if (!pool) return NULL;
-       
-       pool->totused++;
-       if (!(pool->free)) {
-               int j;
-               /*need to allocate a new chunk*/
-               BLI_mempool_chunk *mpchunk = pool->use_sysmalloc ? (BLI_mempool_chunk*)malloc(sizeof(BLI_mempool_chunk)) :  (BLI_mempool_chunk*)MEM_mallocN(sizeof(BLI_mempool_chunk), "BLI_Mempool Chunk");
-               mpchunk->next = mpchunk->prev = NULL;
-               mpchunk->data = pool->use_sysmalloc ? malloc(pool->csize) : MEM_mallocN(pool->csize, "BLI_Mempool Chunk Data");
-               BLI_addtail(&(pool->chunks), mpchunk);
-               pool->free = (BLI_freenode*)mpchunk->data; /*start of the list*/
-               if (pool->allow_iter)
-                       pool->free->freeword = FREEWORD;
-               for(addr = (char*)mpchunk->data, j=0; j < pool->pchunk; j++){
-                       curnode = ((BLI_freenode*)addr);
-                       addr += pool->esize;
-                       curnode->next = (BLI_freenode*)addr;
-                       if (pool->allow_iter) {
-                               curnode->freeword = FREEWORD;
-                               if (j != pool->pchunk-1)
-                                       curnode->next->freeword = FREEWORD;
-                       }
-               }
-               curnode->next = NULL; /*terminate the list*/
-               pool->totalloc += pool->pchunk;
-       }
-       retval = pool->free;
-       if (pool->allow_iter)
-               pool->free->freeword = 0x7FFFFFFF;
-       pool->free = pool->free->next;
-       //memset(retval, 0, pool->esize);
-       return retval;
- }
 +#ifdef __cplusplus
 +}
 +#endif
  
  #endif
index 7dd4b6707c3ab1b10dea2ba0af2e3cd20f0ab740,7e79b9f65a1ab17009c7bb91217ece2abbef9d62..80b70dd45b61d5472e916ec8aea000fe32511a5d
   *  \ingroup bli
   */
  
--
  /*
--      Simple, fast memory allocator for allocating many elements of the same size.
--*/
- #include "MEM_guardedalloc.h"
++ * Simple, fast memory allocator for allocating many elements of the same size.
++ */
 +
 +#include "BLI_utildefines.h"
++#include "BLI_listbase.h"
 +
- #include "BLI_blenlib.h"
- #include "BLI_linklist.h"
- #include "BLI_mempool.h"
- #include "BLI_utildefines.h"
++#include "BLI_mempool.h" /* own include */
 +
 +#include "DNA_listBase.h"
- #include "DNA_ID.h"
  
- #include <string.h> 
+ #include "MEM_guardedalloc.h"
 -#include "BLI_blenlib.h"
 -#include "BLI_mempool.h"
 -#include <string.h> 
++
++#include <string.h>
++#include <stdlib.h>
 +
- #define BLI_MEMPOOL_INTERN
- #include "BLI_mempool.h"
++/* note: copied from BKE_utildefines.h, dont use here because we're in BLI */
++#ifdef __BIG_ENDIAN__
++/* Big Endian */
++#  define MAKE_ID(a,b,c,d) ( (int)(a)<<24 | (int)(b)<<16 | (c)<<8 | (d) )
++#else
++/* Little Endian */
++#  define MAKE_ID(a,b,c,d) ( (int)(d)<<24 | (int)(c)<<16 | (b)<<8 | (a) )
++#endif
++
++#define FREEWORD MAKE_ID('f', 'r', 'e', 'e')
+ typedef struct BLI_freenode {
+       struct BLI_freenode *next;
++      int freeword; /* used to identify this as a freed node */
+ } BLI_freenode;
+ typedef struct BLI_mempool_chunk {
+       struct BLI_mempool_chunk *next, *prev;
+       void *data;
+ } BLI_mempool_chunk;
+ typedef struct BLI_mempool {
+       struct ListBase chunks;
+       int esize, csize, pchunk;               /*size of elements and chunks in bytes and number of elements per chunk*/
 -      struct BLI_freenode     *free;          /*free element list. Interleaved into chunk datas.*/
++      BLI_freenode *free;             /*free element list. Interleaved into chunk datas.*/
+       int totalloc, totused; /*total number of elements allocated in total, and currently in use*/
 -      int use_sysmalloc;
++      int use_sysmalloc, allow_iter;
+ } BLI_mempool;
  
 -BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk, int use_sysmalloc)
 +BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk,
 +                                int use_sysmalloc, int allow_iter)
  {
        BLI_mempool  *pool = NULL;
        BLI_freenode *lasttail = NULL, *curnode = NULL;
        int i,j, maxchunks;
        char *addr;
        
 -      if (esize < sizeof(void*))
 -              esize = sizeof(void*);
 +      if (esize < sizeof(void*)*2)
 +              esize = sizeof(void*)*2;
        
 +      if (esize < sizeof(void*)*2)
 +              esize = sizeof(void*)*2;
 +
        /*allocate the pool structure*/
        pool = use_sysmalloc ? malloc(sizeof(BLI_mempool)) : MEM_mallocN(sizeof(BLI_mempool), "memory pool");
 -      pool->esize = esize;
 +      pool->esize = allow_iter ? MAX2(esize, sizeof(BLI_freenode)) : esize;
        pool->use_sysmalloc = use_sysmalloc;
-       pool->pchunk = pchunk;  
+       pool->pchunk = pchunk;
        pool->csize = esize * pchunk;
        pool->chunks.first = pool->chunks.last = NULL;
        pool->totused= 0;
 +      pool->allow_iter= allow_iter;
        
        maxchunks = tote / pchunk + 1;
 -      
 +      if (maxchunks==0) maxchunks = 1;
 +
        /*allocate the actual chunks*/
-       for(i=0; i < maxchunks; i++){
+       for (i=0; i < maxchunks; i++) {
                BLI_mempool_chunk *mpchunk = use_sysmalloc ? malloc(sizeof(BLI_mempool_chunk)) : MEM_mallocN(sizeof(BLI_mempool_chunk), "BLI_Mempool Chunk");
                mpchunk->next = mpchunk->prev = NULL;
                mpchunk->data = use_sysmalloc ? malloc(pool->csize) : MEM_mallocN(pool->csize, "BLI Mempool Chunk Data");
                BLI_addtail(&(pool->chunks), mpchunk);
                
 -              if (i==0) pool->free = mpchunk->data; /*start of the list*/
 +              if(i==0) {
 +                      pool->free = mpchunk->data; /*start of the list*/
 +                      if (pool->allow_iter)
 +                              pool->free->freeword = FREEWORD;
 +              }
 +
                /*loop through the allocated data, building the pointer structures*/
-               for(addr = mpchunk->data, j=0; j < pool->pchunk; j++){
+               for (addr = mpchunk->data, j=0; j < pool->pchunk; j++) {
                        curnode = ((BLI_freenode*)addr);
                        addr += pool->esize;
                        curnode->next = (BLI_freenode*)addr;
  void *BLI_mempool_alloc(BLI_mempool *pool)
  {
        void *retval=NULL;
-       BLI_freenode *curnode=NULL;
-       char *addr=NULL;
-       int j;
-       
 +      if (!pool) return NULL;
-       
++
        pool->totused++;
  
-       if(!(pool->free)){
+       if (!(pool->free)) {
+               BLI_freenode *curnode=NULL;
+               char *addr;
+               int j;
                /*need to allocate a new chunk*/
                BLI_mempool_chunk *mpchunk = pool->use_sysmalloc ? malloc(sizeof(BLI_mempool_chunk)) :  MEM_mallocN(sizeof(BLI_mempool_chunk), "BLI_Mempool Chunk");
                mpchunk->next = mpchunk->prev = NULL;
@@@ -175,16 -144,11 +196,13 @@@ void *BLI_mempool_calloc(BLI_mempool *p
        return retval;
  }
  
- void BLI_mempool_free(BLI_mempool *pool, void *addr) //doesnt protect against double frees, dont be stupid!
+ /* doesnt protect against double frees, dont be stupid! */
+ void BLI_mempool_free(BLI_mempool *pool, void *addr)
  {
        BLI_freenode *newhead = addr;
-       BLI_freenode *curnode=NULL;
-       char *tmpaddr=NULL;
-       int i;
-       
 +      if (pool->allow_iter)
 +              newhead->freeword = FREEWORD;
        newhead->next = pool->free;
        pool->free = newhead;
  
index 82443221e4c4471164a2ecbc5161f2ea1e23ba0f,0000000000000000000000000000000000000000..43f05a2ff0d205b57970ed48d429290b970ed4ca
mode 100644,000000..100644
--- /dev/null
@@@ -1,499 -1,0 +1,500 @@@
 +#ifndef _BMESH_OPERATOR_API_H
 +#define _BMESH_OPERATOR_API_H
 +
 +#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_CallOpf or BMO_InitOpf).  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 BMOP_OPSLOT_SENTINEL          0
 +#define BMOP_OPSLOT_INT                       1
 +#define BMOP_OPSLOT_FLT                       2
 +#define BMOP_OPSLOT_PNT                       3
 +#define BMOP_OPSLOT_MAT                       4
 +#define BMOP_OPSLOT_VEC                       7
 +
 +/*after BMOP_OPSLOT_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 BMOP_OPSLOT_ELEMENT_BUF               8
 +#define BMOP_OPSLOT_MAPPING           9
 +#define BMOP_OPSLOT_TYPES             10
 +
 +/*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 BMOP_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[BMOP_MAX_SLOTS];
 +      void (*exec)(struct BMesh *bm, struct BMOperator *op);
 +      MemArena *arena;
 +} BMOperator;
 +
 +#define MAX_SLOTNAME  32
 +
 +typedef struct slottype {
 +      int type;
 +      char name[MAX_SLOTNAME];
 +} slottype;
 +
 +typedef struct BMOpDefine {
 +      const char *name;
 +      slottype slottypes[BMOP_MAX_SLOTS];
 +      void (*exec)(BMesh *bm, BMOperator *op);
 +      int flag; 
 +} BMOpDefine;
 +
 +/*BMOpDefine->flag*/
 +#define BMOP_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 BMOP_RATIONALIZE_NORMALS 2
 +
 +/*------------- Operator API --------------*/
 +
 +/*data types that use pointers (arrays, etc) should never
 +  have it set directly.  and never use BMO_Set_Pnt to
 +  pass in a list of edges or any arrays, really.*/
 +
 +void BMO_Init_Op(struct BMesh *bm, struct BMOperator *op, const char *opname);
 +
 +/*executes an operator, pushing and popping a new tool flag 
 +  layer as appropriate.*/
 +void BMO_Exec_Op(struct BMesh *bm, struct BMOperator *op);
 +
 +/*finishes an operator (though note the operator's tool flag is removed 
 +  after it finishes executing in BMO_Exec_Op).*/
 +void BMO_Finish_Op(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_TestFlag(bm, element, flag) (((BMHeader*)(element))->flags[bm->stackdepth-1].f & (flag))
 +#define BMO_SetFlag(bm, element, flag) (((BMHeader*)(element))->flags[bm->stackdepth-1].f |= (flag))
 +#define BMO_ClearFlag(bm, element, flag) (((BMHeader*)(element))->flags[bm->stackdepth-1].f &= ~(flag))
 +#define BMO_ToggleFlag(bm, element, flag) (((BMHeader*)(element))->flags[bm->stackdepth-1].f ^= (flag))
 +
 +/*profiling showed a significant amount of time spent in BMO_TestFlag
 +void BMO_SetFlag(struct BMesh *bm, void *element, int flag);
 +void BMO_ClearFlag(struct BMesh *bm, void *element, int flag);
 +int BMO_TestFlag(struct BMesh *bm, void *element, int flag);*/
 +
 +/*count the number of elements with a specific flag.  type
 +  can be a bitmask of BM_FACE, BM_EDGE, or BM_FACE.*/
 +int BMO_CountFlag(struct BMesh *bm, int flag, 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_CallOpf(bm, "del geom=%hf context=%d", BM_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_CallOpf(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_Exec_Op and BMO_Finish_Op) yourself.*/
 +int BMO_InitOpf(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_VInitOpf(BMesh *bm, BMOperator *op, const char *fmt, va_list vlist);
 +
 +/*test whether a named slot exists*/
 +int BMO_HasSlot(struct BMOperator *op, const char *slotname);
 +
 +/*get a pointer to a slot.  this may be removed layer on from the public API.*/
 +BMOpSlot *BMO_GetSlot(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_CopySlot(struct BMOperator *source_op, struct BMOperator *dest_op, 
 +                  const char *src, const char *dst);
 +
 +/*remove tool flagged elements*/
 +void BM_remove_tagged_faces(struct BMesh *bm, int flag);
 +void BM_remove_tagged_edges(struct BMesh *bm, int flag);
 +void BM_remove_tagged_verts(struct BMesh *bm, int flag);
 +
 +void BMO_Set_OpFlag(struct BMesh *bm, struct BMOperator *op, int flag);
 +void BMO_Clear_OpFlag(struct BMesh *bm, struct BMOperator *op, int flag);
 +
 +void BMO_Set_Float(struct BMOperator *op, const char *slotname, float f);
 +float BMO_Get_Float(BMOperator *op, const char *slotname);
 +void BMO_Set_Int(struct BMOperator *op, const char *slotname, int i);
 +int BMO_Get_Int(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_Set_Pnt(struct BMOperator *op, const char *slotname, void *p);
 +void *BMO_Get_Pnt(BMOperator *op, const char *slotname);
 +void BMO_Set_Vec(struct BMOperator *op, const char *slotname, float *vec);
 +void BMO_Get_Vec(BMOperator *op, const char *slotname, float *vec_out);
 +
 +/*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_Set_Mat(struct BMOperator *op, const char *slotname, float *mat, int size);
 +void BMO_Get_Mat4(struct BMOperator *op, const char *slotname, float mat[4][4]);
 +void BMO_Get_Mat3(struct BMOperator *op, const char *slotname, float mat[3][3]);
 +
 +void BMO_Clear_Flag_All(BMesh *bm, BMOperator *op, const char htype, int flag);
 +
 +/*puts every element of type type (which is a bitmask) with tool flag flag,
 +  into a slot.*/
 +void BMO_Flag_To_Slot(struct BMesh *bm, struct BMOperator *op, const char *slotname, const int flag, const char htype);
 +
 +/*tool-flags all elements inside an element slot array with flag flag.*/
 +void BMO_Flag_Buffer(struct BMesh *bm, struct BMOperator *op, const char *slotname, const int hflag, const char htype);
 +/*clears tool-flag flag from all elements inside a slot array.*/
 +void BMO_Unflag_Buffer(struct BMesh *bm, struct BMOperator *op, const char *slotname, const int flag, const char htype);
 +
 +/*tool-flags all elements inside an element slot array with flag flag.*/
 +void BMO_HeaderFlag_Buffer(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_UnHeaderFlag_Buffer(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_HIDDEN set).*/
 +void BMO_HeaderFlag_To_Slot(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_CountSlotBuf(struct BMesh *bm, struct BMOperator *op, const char *slotname);
 +int BMO_CountSlotMap(struct BMesh *bm, struct BMOperator *op, const char *slotname);
 +
 +/*Counts the number of edges with tool flag toolflag around
 +  v*/
 +int BMO_Vert_CountEdgeFlags(BMesh *bm, BMVert *v, int toolflag);
 +
 +/*inserts a key/value mapping into a mapping slot.  note that it copies the
 +  value, it doesn't store a reference to it.*/
 +//BM_INLINE void BMO_Insert_Mapping(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_Insert_MapFloat(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_InMap(BMesh *bm, BMOperator *op, const char *slotname, void *element);
 +
 +/*returns a point to the value of a specific key.*/
 +//BM_INLINE void *BMO_Get_MapData(BMesh *bm, BMOperator *op, const char *slotname, void *element);
 +
 +/*returns the float part of a key/float pair.*/
 +//BM_INLINE float BMO_Get_MapFloat(BMesh *bm, BMOperator *op, const char *slotname, void *element);
 +
 +/*flags all elements in a mapping.  note that the mapping must only have
 +  bmesh elements in it.*/
 +void BMO_Mapping_To_Flag(struct BMesh *bm, struct BMOperator *op, 
 +                       const char *slotname, int flag);
 +
 +/*pointer versoins of BMO_Get_MapFloat and BMO_Insert_MapFloat.
 +
 +  do NOT use these for non-operator-api-allocated memory! instead
 +  use BMO_Get_MapData and BMO_Insert_Mapping, which copies the data.*/
 +//BM_INLINE void BMO_Insert_MapPointer(BMesh *bm, BMOperator *op, const char *slotname, 
 +                      //void *key, void *val);
 +//BM_INLINE void *BMO_Get_MapPointer(BMesh *bm, BMOperator *op, const char *slotname,
 +                     //void *key);
 +
 +/*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_IterNew(&oiter, bm, some_operator, "slotname", BM_FACE);
 +        for (; f; f=BMO_IterStep(&oiter)) {
 +              /do something with the face
 +        }
 +
 +  another example, iterating over a mapping:
 +        BMOIter oiter;
 +        void *key;
 +        void *val;
 +
 +        key = BMO_IterNew(&oiter, bm, some_operator, "slotname", 0);
 +        for (; key; key=BMO_IterStep(&oiter)) {
 +              val = BMO_IterMapVal(&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_IterMapVal(&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_FirstElem(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_IterNew(BMOIter *iter, BMesh *bm, BMOperator *op, 
 +                  const char *slotname, const char restrictmask);
 +void *BMO_IterStep(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_IterMapVal(BMOIter *iter);
 +
 +/*use this for pointer mappings*/
 +void *BMO_IterMapValp(BMOIter *iter);
 +
 +/*use this for float mappings*/
 +float BMO_IterMapValf(BMOIter *iter);
 +
 +#define BMO_ITER(ele, iter, bm, op, slotname, restrict) \
 +      ele = BMO_IterNew(iter, bm, op, slotname, restrict); \
 +      for ( ; ele; ele=BMO_IterStep(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 element_mapping {
 +      BMHeader *element;
 +      int len;
 +} element_mapping;
 +
 +extern const int BMOP_OPSLOT_TYPEINFO[];
 +
 +BM_INLINE void BMO_Insert_Mapping(BMesh *UNUSED(bm), BMOperator *op, const char *slotname, 
 +                      void *element, void *data, int len) {
 +      element_mapping *mapping;
 +      BMOpSlot *slot = BMO_GetSlot(op, slotname);
 +
 +      /*sanity check*/
 +      if (slot->slottype != BMOP_OPSLOT_MAPPING) return;
 +      
 +      mapping = (element_mapping*) 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_Insert_MapInt(BMesh *bm, BMOperator *op, const char *slotname, 
 +                      void *element, int val)
 +{
 +      BMO_Insert_Mapping(bm, op, slotname, element, &val, sizeof(int));
 +}
 +
 +BM_INLINE void BMO_Insert_MapFloat(BMesh *bm, BMOperator *op, const char *slotname, 
 +                      void *element, float val)
 +{
 +      BMO_Insert_Mapping(bm, op, slotname, element, &val, sizeof(float));
 +}
 +
 +BM_INLINE void BMO_Insert_MapPointer(BMesh *bm, BMOperator *op, const char *slotname, 
 +                      void *element, void *val)
 +{
 +      BMO_Insert_Mapping(bm, op, slotname, element, &val, sizeof(void*));
 +}
 +
 +BM_INLINE int BMO_InMap(BMesh *UNUSED(bm), BMOperator *op, const char *slotname, void *element)
 +{
 +      BMOpSlot *slot = BMO_GetSlot(op, slotname);
 +
 +      /*sanity check*/
 +      if (slot->slottype != BMOP_OPSLOT_MAPPING) return 0;
 +      if (!slot->data.ghash) return 0;
 +
 +      return BLI_ghash_haskey(slot->data.ghash, element);
 +}
 +
 +BM_INLINE void *BMO_Get_MapData(BMesh *UNUSED(bm), BMOperator *op, const char *slotname,
 +                    void *element)
 +{
 +      element_mapping *mapping;
 +      BMOpSlot *slot = BMO_GetSlot(op, slotname);
 +
 +      /*sanity check*/
 +      if (slot->slottype != BMOP_OPSLOT_MAPPING) return NULL;
 +      if (!slot->data.ghash) return NULL;
 +
 +      mapping = (element_mapping*) BLI_ghash_lookup(slot->data.ghash, element);
 +      
 +      if (!mapping) return NULL;
 +
 +      return mapping + 1;
 +}
 +
 +BM_INLINE float BMO_Get_MapFloat(BMesh *bm, BMOperator *op, const char *slotname,
 +                     void *element)
 +{
 +      float *val = (float*) BMO_Get_MapData(bm, op, slotname, element);
 +      if (val) return *val;
 +
 +      return 0.0f;
 +}
 +
 +BM_INLINE int BMO_Get_MapInt(BMesh *bm, BMOperator *op, const char *slotname,
 +                     void *element)
 +{
 +      int *val = (int*) BMO_Get_MapData(bm, op, slotname, element);
 +      if (val) return *val;
 +
 +      return 0;
 +}
 +
 +BM_INLINE void *BMO_Get_MapPointer(BMesh *bm, BMOperator *op, const char *slotname,
 +                     void *element)
 +{
 +      void **val = (void**) BMO_Get_MapData(bm, op, slotname, element);
 +      if (val) return *val;
 +
 +      return NULL;
 +}
 +
 +#ifdef __cplusplus
 +}
 +#endif
 +
 +#endif /* _BMESH_OPERATOR_API_H */
index 5c7144b21f530be2305343609e2ea5c46b0f137a,0000000000000000000000000000000000000000..e54bb01bf8f2ffcae97d26ec93dc9ebfe6684b25
mode 100644,000000..100644
--- /dev/null
@@@ -1,1840 -1,0 +1,1842 @@@
 +#include <limits.h>
 +
 +#include "BLI_math_vector.h"
 +
 +#include "BKE_customdata.h"
 +#include "BKE_DerivedMesh.h"
 +
 +#include "BLI_utildefines.h"
 +#include "BLI_blenlib.h"
 +#include "BLI_listbase.h"
 +#include "BLI_mempool.h"
 +#include "BLI_ghash.h"
 +#include "BLI_array.h"
 +
++#include "MEM_guardedalloc.h"
++
 +#include "DNA_listBase.h"
 +
 +#include "bmesh_class.h"
 +
 +#include "bmesh_iterators.h"
 +#include "bmesh_private.h"
 +
 +BMVert *BM_Make_Vert(BMesh *bm, float co[3], const struct BMVert *example)
 +{
 +      BMVert *v = BLI_mempool_calloc(bm->vpool);
 +
 +      BM_SetIndex(v, bm->totvert); /* set_ok */
 +
 +      bm->totvert++;
 +
 +      v->head.htype = BM_VERT;
 +
 +      /* 'v->no' is handled by BM_Copy_Attributes */
 +      if (co) copy_v3_v3(v->co, co);
 +      
 +      /*allocate flags*/
 +      v->head.flags = BLI_mempool_calloc(bm->toolflagpool);
 +
 +      CustomData_bmesh_set_default(&bm->vdata, &v->head.data);
 +      
 +      if (example) {
 +              BM_Copy_Attributes(bm, bm, (BMVert*)example, (BMVert*)v);
 +      }
 +
 +      BM_CHECK_ELEMENT(bm, v);
 +
 +      return (BMVert*) v;
 +}
 +
 +/**
 + *                    BMESH EDGE EXIST
 + *
 + *  Finds out if two vertices already have an edge
 + *  connecting them. Note that multiple edges may
 + *  exist between any two vertices, and therefore
 + *  This function only returns the first one found.
 + *
 + *  Returns -
 + *    BMEdge pointer
 + */
 +BMEdge *BM_Edge_Exist(BMVert *v1, BMVert *v2)
 +{
 +      BMIter iter;
 +      BMEdge *e;
 +
 +      BM_ITER(e, &iter, NULL, BM_EDGES_OF_VERT, v1) {
 +              if (e->v1 == v2 || e->v2 == v2)
 +                      return e;
 +      }
 +
 +      return NULL;
 +}
 +
 +BMEdge *BM_Make_Edge(BMesh *bm, BMVert *v1, BMVert *v2, const BMEdge *example, int nodouble)
 +{
 +      BMEdge *e;
 +      
 +      if (nodouble && (e= BM_Edge_Exist(v1, v2)))
 +              return (BMEdge*)e;
 +      
 +      e = BLI_mempool_calloc(bm->epool);
 +
 +      BM_SetIndex(e, bm->totedge); /* set_ok */
 +
 +      bm->totedge++;
 +
 +      e->head.htype = BM_EDGE;
 +      
 +      /*allocate flags*/
 +      e->head.flags = BLI_mempool_calloc(bm->toolflagpool);
 +
 +      e->v1 = (BMVert*) v1;
 +      e->v2 = (BMVert*) v2;
 +      
 +      
 +      CustomData_bmesh_set_default(&bm->edata, &e->head.data);
 +      
 +      bmesh_disk_append_edge(e, e->v1);
 +      bmesh_disk_append_edge(e, e->v2);
 +      
 +      if (example)
 +              BM_Copy_Attributes(bm, bm, (BMEdge*)example, (BMEdge*)e);
 +      
 +      BM_CHECK_ELEMENT(bm, e);
 +
 +      return (BMEdge*) e;
 +}
 +
 +static BMLoop *bmesh_create_loop(BMesh *bm, BMVert *v, BMEdge *e, BMFace *f, const BMLoop *example)
 +{
 +      BMLoop *l=NULL;
 +
 +      l = BLI_mempool_calloc(bm->lpool);
 +      l->next = l->prev = NULL;
 +      l->v = v;
 +      l->e = e;
 +      l->f = f;
 +      l->radial_next = l->radial_prev = NULL;
 +      l->head.data = NULL;
 +      l->head.htype = BM_LOOP;
 +
 +      bm->totloop++;
 +
 +      if(example)
 +              CustomData_bmesh_copy_data(&bm->ldata, &bm->ldata, example->head.data, &l->head.data);
 +      else
 +              CustomData_bmesh_set_default(&bm->ldata, &l->head.data);
 +
 +      return l;
 +}
 +
 +static BMLoop *BM_Add_FaceBoundary(BMesh *bm, BMFace *f, BMVert *startv, BMEdge *starte)
 +{
 +      BMLoopList *lst = BLI_mempool_calloc(bm->looplistpool);
 +      BMLoop *l = bmesh_create_loop(bm, startv, starte, f, NULL);
 +      
 +      bmesh_radial_append(starte, l);
 +
 +      lst->first = lst->last = l;
 +      BLI_addtail(&f->loops, lst);
 +      
 +      l->f = f;
 +      
 +      return l;       
 +}
 +
 +BMFace *BM_Copy_Face(BMesh *bm, BMFace *f, int copyedges, int copyverts)
 +{
 +      BMEdge **edges = NULL;
 +      BMVert **verts = NULL;
 +      BLI_array_staticdeclare(edges, 256);
 +      BLI_array_staticdeclare(verts, 256);
 +      BMLoop *l, *l2;
 +      BMFace *f2;
 +      int i;
 +
 +      l = bm_firstfaceloop(f);
 +      do {
 +              if (copyverts) {
 +                      BMVert *v = BM_Make_Vert(bm, l->v->co, l->v);
 +                      BLI_array_append(verts, v);
 +              } else {        
 +                      BLI_array_append(verts, l->v);
 +              }
 +              l = l->next;
 +      } while (l != bm_firstfaceloop(f));
 +
 +      l = bm_firstfaceloop(f);
 +      i = 0;
 +      do {
 +              if (copyedges) {
 +                      BMEdge *e;
 +                      BMVert *v1, *v2;
 +                      
 +                      if (l->e->v1 == verts[i]) {
 +                              v1 = verts[i];
 +                              v2 = verts[(i+1)%f->len];
 +                      } else {
 +                              v2 = verts[i];
 +                              v1 = verts[(i+1)%f->len];
 +                      }
 +                      
 +                      e = BM_Make_Edge(bm,  v1, v2, l->e, 0);
 +                      BLI_array_append(edges, e);
 +              } else {
 +                      BLI_array_append(edges, l->e);
 +              }
 +              
 +              i++;
 +              l = l->next;
 +      } while (l != bm_firstfaceloop(f));
 +      
 +      f2 = BM_Make_Face(bm, verts, edges, f->len, 0);
 +      
 +      BM_Copy_Attributes(bm, bm, f, f2);
 +      
 +      l = bm_firstfaceloop(f);
 +      l2 = bm_firstfaceloop(f2);
 +      do {
 +              BM_Copy_Attributes(bm, bm, l, l2);
 +              l = l->next;
 +              l2 = l2->next;
 +      } while (l != bm_firstfaceloop(f));
 +      
 +      return f2;
 +}
 +
 +BMFace *BM_Make_Face(BMesh *bm, BMVert **verts, BMEdge **edges, int len, int nodouble)
 +{
 +      BMFace *f = NULL;
 +      BMLoop *l, *startl, *lastl;
 +      int i, overlap;
 +      
 +      if (len == 0) {
 +              /*just return NULL for now*/
 +              return NULL;
 +      }
 +
 +      if (nodouble) {
 +              /* Check if face already exists */
 +              overlap = BM_Face_Exists(bm, verts, len, &f);
 +              if (overlap) {
 +                      return f;
 +              }
 +              else {
 +                      BLI_assert(f == NULL);
 +              }
 +      }
 +      
 +      f = BLI_mempool_calloc(bm->fpool);
 +
 +      BM_SetIndex(f, bm->totface); /* set_ok */
 +
 +      bm->totface++;
 +
 +      f->head.htype = BM_FACE;
 +
 +      startl = lastl = BM_Add_FaceBoundary(bm, (BMFace*)f, verts[0], edges[0]);
 +      
 +      startl->v = (BMVert*) verts[0];
 +      startl->e = (BMEdge*) edges[0];
 +      for (i=1; i<len; i++) {
 +              l = bmesh_create_loop(bm, verts[i], edges[i], (BMFace *)f, edges[i]->l);
 +              
 +              l->f = (BMFace*) f;
 +              bmesh_radial_append(edges[i], l);
 +
 +              l->prev = lastl;
 +              lastl->next = l;
 +              lastl = l;
 +      }
 +      
 +      /*allocate flags*/
 +      f->head.flags = BLI_mempool_calloc(bm->toolflagpool);
 +
 +      CustomData_bmesh_set_default(&bm->pdata, &f->head.data);
 +      
 +      startl->prev = lastl;
 +      lastl->next = startl;
 +      
 +      f->len = len;
 +      f->totbounds = 0;
 +      
 +      BM_CHECK_ELEMENT(bm, f);
 +
 +      return (BMFace*) f;
 +}
 +
 +int bmesh_check_element(BMesh *UNUSED(bm), void *element, const char htype)
 +{
 +      BMHeader *head = element;
 +      int err = 0;
 +
 +      if (!element)
 +              return 1;
 +
 +      if (head->htype != htype)
 +              return 2;
 +      
 +      switch (htype) {
 +      case BM_VERT: {
 +              BMVert *v = element;
 +              if (v->e && v->e->head.htype != BM_EDGE) {
 +                      err |= 4;
 +              }
 +              break;
 +      }
 +      case BM_EDGE: {
 +              BMEdge *e = element;
 +              if (e->l && e->l->head.htype != BM_LOOP)
 +                      err |= 8;
 +              if (e->l && e->l->f->head.htype != BM_FACE)
 +                      err |= 16;
 +              if (e->dlink1.prev == NULL || e->dlink2.prev == NULL || e->dlink1.next == NULL || e->dlink2.next == NULL)
 +                      err |= 32;
 +              if (e->l && (e->l->radial_next == NULL || e->l->radial_prev == NULL))
 +                      err |= 64;
 +              if (e->l && e->l->f->len <= 0)
 +                      err |= 128;
 +              break;
 +      }
 +      case BM_LOOP: {
 +              BMLoop *l = element, *l2;
 +              int i;
 +
 +              if (l->f->head.htype != BM_FACE)
 +                      err |= 256;
 +              if (l->e->head.htype != BM_EDGE)
 +                      err |= 512;
 +              if (l->v->head.htype !=  BM_VERT)
 +                      err |= 1024;
 +              if (!BM_Vert_In_Edge(l->e, l->v)) {
 +                      fprintf(stderr, "%s: fatal bmesh error (vert not in edge)! (bmesh internal error)\n", __func__);
 +                      err |= 2048;
 +              }
 +
 +              if (l->radial_next == NULL || l->radial_prev == NULL)
 +                      err |= (1<<12);
 +              if (l->f->len <= 0)
 +                      err |= (1<<13);
 +
 +              /*validate boundary loop--invalid for hole loops, of course,
 +                but we won't be allowing those for a while yet*/
 +              l2 = l;
 +              i = 0;
 +              do {
 +                      if (i >= 9999999)
 +                              break;
 +
 +                      i++;
 +                      l2 = l2->next;
 +              } while (l2 != l);
 +
 +              if (i != l->f->len || l2 != l)
 +                      err |= (1<<14);
 +
 +              if (!bmesh_radial_validate(bmesh_radial_length(l), l))
 +                      err |= (1<<15);
 +
 +              break;
 +      }
 +      case BM_FACE: {
 +              BMFace *f = element;
 +              BMLoop *l;
 +              int len=0;
 +
 +              if (!f->loops.first)
 +                      err |= (1<<16);
 +              l = bm_firstfaceloop(f);
 +              do {
 +                      if (l->f != f) {
 +                              fprintf(stderr, "%s: loop inside one face points to another! (bmesh internal error)\n", __func__);
 +                              err |= (1<<17);
 +                      }
 +
 +                      if (!l->e)
 +                              err |= (1<<18);
 +                      if (!l->v)
 +                              err |= (1<<19);
 +                      if (!BM_Vert_In_Edge(l->e, l->v) || !BM_Vert_In_Edge(l->e, l->next->v)) {
 +                              err |= (1<<20);
 +                      }
 +
 +                      if (!bmesh_radial_validate(bmesh_radial_length(l), l))
 +                              err |= (1<<21);
 +
 +                      if (!bmesh_disk_count(l->v) || !bmesh_disk_count(l->next->v))
 +                              err |= (1<<22);
 +
 +                      len++;
 +                      l = l->next;
 +              } while (l != bm_firstfaceloop(f));
 +
 +              if (len != f->len)
 +                      err |= (1<<23);
 +      }
 +      }
 +
 +      if (err) {
 +              bmesh_error();
 +      }
 +
 +      return err;
 +}
 +
 +static void bmesh_kill_loop(BMesh *bm, BMLoop *l)
 +{
 +      bm->totloop--;
 +      if (l->head.data)
 +              CustomData_bmesh_free_block(&bm->ldata, &l->head.data);
 +
 +      if (l->head.flags)
 +              BLI_mempool_free(bm->toolflagpool, l->head.flags);
 +      BLI_mempool_free(bm->lpool, l);
 +}
 +
 +void BM_Kill_Face_Edges(BMesh *bm, BMFace *f)
 +{
 +      BMEdge **edges = NULL;
 +      BLI_array_staticdeclare(edges, 256);
 +      BMLoop *l;
 +      int i;
 +      
 +      l = bm_firstfaceloop(f);
 +      do {
 +              BLI_array_append(edges, l->e);
 +              l = l->next;
 +      } while (l != bm_firstfaceloop(f));
 +      
 +      for (i=0; i<BLI_array_count(edges); i++) {
 +              BM_Kill_Edge(bm, edges[i]);
 +      }
 +      
 +      BLI_array_free(edges);
 +}
 +
 +void BM_Kill_Face_Verts(BMesh *bm, BMFace *f)
 +{
 +      BMVert**verts = NULL;
 +      BLI_array_staticdeclare(verts, 256);
 +      BMLoop *l;
 +      int i;
 +      
 +      l = bm_firstfaceloop(f);
 +      do {
 +              BLI_array_append(verts, l->v);
 +              l = l->next;
 +      } while (l != bm_firstfaceloop(f));
 +      
 +      for (i=0; i<BLI_array_count(verts); i++) {
 +              BM_Kill_Vert(bm, verts[i]);
 +      }
 +      
 +      BLI_array_free(verts);
 +}
 +
 +void BM_Kill_Face(BMesh *bm, BMFace *f)
 +{
 +      BMLoopList *ls, *lsnext;
 +
 +      BM_CHECK_ELEMENT(bm, f);
 +
 +      for (ls=f->loops.first; ls; ls=lsnext) {
 +              BMLoop *l, *lnext;
 +
 +              lsnext = ls->next;
 +              l = ls->first;
 +              do {
 +                      lnext = l->next;
 +
 +                      bmesh_radial_remove_loop(l, l->e);
 +                      bmesh_kill_loop(bm, l);
 +
 +                      l = lnext;
 +              } while (l != ls->first);
 +              
 +              BLI_mempool_free(bm->looplistpool, ls);
 +      }
 +      
 +      if (bm->act_face == f)
 +              bm->act_face = NULL;
 +      
 +      bm->totface--;
 +      bm->elem_index_dirty |= BM_FACE;
 +      BM_remove_selection(bm, f);
 +      if (f->head.data)
 +              CustomData_bmesh_free_block(&bm->pdata, &f->head.data);
 +
 +      BLI_mempool_free(bm->toolflagpool, f->head.flags);
 +
 +      BLI_mempool_free(bm->fpool, f);
 +}
 +
 +void BM_Kill_Edge(BMesh *bm, BMEdge *e)
 +{
 +
 +      bmesh_disk_remove_edge(e, e->v1);
 +      bmesh_disk_remove_edge(e, e->v2);
 +              
 +      if (e->l) {
 +              BMLoop *l = e->l, *lnext, *startl=e->l;
 +                      
 +              do {
 +                      lnext = l->radial_next;
 +                      if (lnext->f == l->f) {
 +                              BM_Kill_Face(bm, l->f);
 +                              break;                                  
 +                      }
 +                      
 +                      BM_Kill_Face(bm, l->f);
 +              
 +                      if (l == lnext)
 +                              break;
 +                      l = lnext;
 +              } while (l != startl);
 +      }
 +      
 +      bm->totedge--;
 +      bm->elem_index_dirty |= BM_EDGE;
 +      BM_remove_selection(bm, e);
 +      if (e->head.data)
 +              CustomData_bmesh_free_block(&bm->edata, &e->head.data);
 +
 +      BLI_mempool_free(bm->toolflagpool, e->head.flags);
 +      BLI_mempool_free(bm->epool, e);
 +}
 +
 +void BM_Kill_Vert(BMesh *bm, BMVert *v)
 +{
 +      if (v->e) {
 +              BMEdge *e, *nexte;
 +              
 +              e = v->e;
 +              while (v->e) {
 +                      nexte=bmesh_disk_nextedge(e, v);
 +                      BM_Kill_Edge(bm, e);
 +                      e = nexte;
 +              }
 +      }
 +
 +      bm->totvert--;
 +      bm->elem_index_dirty |= BM_VERT;
 +      BM_remove_selection(bm, v);
 +      if (v->head.data)
 +              CustomData_bmesh_free_block(&bm->vdata, &v->head.data);
 +
 +      BLI_mempool_free(bm->toolflagpool, v->head.flags);
 +      BLI_mempool_free(bm->vpool, v);
 +}
 +
 +/********** private disk and radial cycle functions ************/
 +
 +/**
 + *                    bmesh_loop_reverse
 + *
 + *    FLIP FACE EULER
 + *
 + *    Changes the winding order of a face from CW to CCW or vice versa.
 + *    This euler is a bit peculiar in compairson to others as it is its
 + *    own inverse.
 + *
 + *    BMESH_TODO: reinsert validation code.
 + *
 + *  Returns -
 + *    1 for success, 0 for failure.
 + */
 +
 +static int bmesh_loop_length(BMLoop *l)
 +{
 +      BMLoop *ol = l;
 +      int i = 0;
 +
 +      do {
 +              l = l->next;
 +              i++;
 +      } while (l != ol);
 +
 +      return i;
 +}
 +
 +static int bmesh_loop_reverse_loop(BMesh *bm, BMFace *f, BMLoopList *lst)
 +{
 +      BMLoop *l = lst->first, *curloop, *oldprev, *oldnext;
 +      BMEdge **edar = NULL;
 +      MDisps *md;
 +      BLI_array_staticdeclare(edar, 64);
 +      int i, j, edok, len = 0, do_disps = CustomData_has_layer(&bm->ldata, CD_MDISPS);
 +
 +      len = bmesh_loop_length(l);
 +
 +      for(i=0, curloop = l; i< len; i++, curloop= curloop->next) {
 +              BMEdge *curedge = curloop->e;
 +              bmesh_radial_remove_loop(curloop, curedge);
 +              BLI_array_append(edar, curedge);
 +      }
 +
 +      /*actually reverse the loop.*/
 +      for(i=0, curloop = l; i < len; i++){
 +              oldnext = curloop->next;
 +              oldprev = curloop->prev;
 +              curloop->next = oldprev;
 +              curloop->prev = oldnext;
 +              curloop = oldnext;
 +              
 +              if (do_disps) {
 +                      float (*co)[3];
 +                      int x, y, sides;
 +                      
 +                      md = CustomData_bmesh_get(&bm->ldata, curloop->head.data, CD_MDISPS);
 +                      if (!md->totdisp || !md->disps)
 +                              continue;
 +                                      
 +                      sides= (int)sqrt(md->totdisp);
 +                      co = md->disps;
 +                      
 +                      for (x=0; x<sides; x++) {
 +                              for (y=0; y<x; y++) {
 +                                      swap_v3_v3(co[y*sides+x], co[sides*x + y]);
 +                              }
 +                      }
 +              }
 +      }
 +
 +      if(len == 2){ //two edged face
 +              //do some verification here!
 +              l->e = edar[1];
 +              l->next->e = edar[0];
 +      }
 +      else{
 +              for(i=0, curloop = l; i < len; i++, curloop = curloop->next) {
 +                      edok = 0;
 +                      for(j=0; j < len; j++){
 +                              edok = bmesh_verts_in_edge(curloop->v, curloop->next->v, edar[j]);
 +                              if(edok){
 +                                      curloop->e = edar[j];
 +                                      break;
 +                              }
 +                      }
 +              }
 +      }
 +      /*rebuild radial*/
 +      for(i=0, curloop = l; i < len; i++, curloop = curloop->next)
 +              bmesh_radial_append(curloop->e, curloop);
 +
 +      /*validate radial*/
 +      for(i=0, curloop = l; i < len; i++, curloop = curloop->next) {
 +              BM_CHECK_ELEMENT(bm, curloop);
 +              BM_CHECK_ELEMENT(bm, curloop->e);
 +              BM_CHECK_ELEMENT(bm, curloop->v);
 +              BM_CHECK_ELEMENT(bm, curloop->f);
 +      }
 +
 +      BLI_array_free(edar);
 +
 +      BM_CHECK_ELEMENT(bm, f);
 +
 +      return 1;
 +}
 +
 +int bmesh_loop_reverse(BMesh *bm, BMFace *f)
 +{
 +      return bmesh_loop_reverse_loop(bm, f, f->loops.first);
 +}
 +
 +static void bmesh_systag_elements(BMesh *UNUSED(bm), void *veles, int tot, int flag)
 +{
 +      BMHeader **eles = veles;
 +      int i;
 +
 +      for (i=0; i<tot; i++) {
 +              bmesh_api_setflag(eles[i], flag);
 +      }
 +}
 +
 +static void bmesh_clear_systag_elements(BMesh *UNUSED(bm), void *veles, int tot, int flag)
 +{
 +      BMHeader **eles = veles;
 +      int i;
 +
 +      for (i=0; i<tot; i++) {
 +              bmesh_api_clearflag(eles[i], flag);
 +      }
 +}
 +
 +#define FACE_MARK     (1<<10)
 +
 +static int count_flagged_radial(BMesh *bm, BMLoop *l, int flag)
 +{
 +      BMLoop *l2 = l;
 +      int i = 0, c=0;
 +
 +      do {
 +              if (!l2) {
 +                      bmesh_error();
 +                      goto error;
 +              }
 +              
 +              i += bmesh_api_getflag(l2->f, flag) ? 1 : 0;
 +              l2 = bmesh_radial_nextloop(l2);
 +              if (c >= 800000) {
 +                      bmesh_error();
 +                      goto error;
 +              }
 +              c++;
 +      } while (l2 != l);
 +
 +      return i;
 +
 +error:
 +      BMO_RaiseError(bm, bm->currentop, BMERR_MESH_ERROR, NULL);
 +      return 0;
 +}
 +
 +static int UNUSED_FUNCTION(count_flagged_disk)(BMVert *v, int flag)
 +{
 +      BMEdge *e = v->e;
 +      int i=0;
 +
 +      if (!e)
 +              return 0;
 +
 +      do {
 +              i += bmesh_api_getflag(e, flag) ? 1 : 0;
 +              e = bmesh_disk_nextedge(e, v);
 +      } while (e != v->e);
 +
 +      return i;
 +}
 +
 +static int disk_is_flagged(BMVert *v, int flag)
 +{
 +      BMEdge *e = v->e;
 +
 +      if (!e)
 +              return 0;
 +
 +      do {
 +              BMLoop *l = e->l;
 +
 +              if (!l) {
 +                      return 0;
 +              }
 +              
 +              if (bmesh_radial_length(l) == 1)
 +                      return 0;
 +              
 +              do {
 +                      if (!bmesh_api_getflag(l->f, flag))
 +                              return 0;
 +
 +                      l = l->radial_next;
 +              } while (l != e->l);
 +
 +              e = bmesh_disk_nextedge(e, v);
 +      } while (e != v->e);
 +
 +      return 1;
 +}
 +
 +/* Midlevel Topology Manipulation Functions */
 +
 +/*
 + * BM_Join_Faces
 + *
 + * Joins a collected group of faces into one. Only restriction on
 + * the input data is that the faces must be connected to each other.
 + *
 + * If a pair of faces share multiple edges, the pair of
 + * faces will be joined at every edge.
 + *
 + * Returns a pointer to the combined face.
 + */
 +BMFace *BM_Join_Faces(BMesh *bm, BMFace **faces, int totface)
 +{
 +      BMFace *f, *newf;
 +      BMLoopList *lst;
 +      BMLoop *l;
 +      BMEdge **edges = NULL;
 +      BMEdge **deledges = NULL;
 +      BMVert **delverts = NULL;
 +      BLI_array_staticdeclare(edges, 64);
 +      BLI_array_staticdeclare(deledges, 64);
 +      BLI_array_staticdeclare(delverts, 64);
 +      BMVert *v1=NULL, *v2=NULL;
 +      ListBase holes = {NULL, NULL};
 +      const char *err = NULL;
 +      int i, tote=0;
 +
 +      if (!totface) {
 +              bmesh_error();
 +              return NULL;
 +      }
 +
 +      if (totface == 1)
 +              return faces[0];
 +
 +      bmesh_systag_elements(bm, faces, totface, _FLAG_JF);
 +
 +      for (i=0; i<totface; i++) {
 +              f = faces[i];
 +              l = bm_firstfaceloop(f);
 +              do {
 +                      int rlen = count_flagged_radial(bm, l, _FLAG_JF);
 +
 +                      if (rlen > 2) {
 +                              err = "Input faces do not form a contiguous manifold region";
 +                              goto error;
 +                      } else if (rlen == 1) {
 +                              BLI_array_append(edges, l->e);
 +
 +                              if (!v1) {
 +                                      v1 = l->v;
 +                                      v2 = BM_OtherEdgeVert(l->e, l->v);
 +                              }
 +                              tote++;
 +                      } else if (rlen == 2) {
 +                              int d1, d2;
 +
 +                              d1 = disk_is_flagged(l->e->v1, _FLAG_JF);
 +                              d2 = disk_is_flagged(l->e->v2, _FLAG_JF);
 +
 +                              if (!d1 && !d2 && !bmesh_api_getflag(l->e, _FLAG_JF)) {
 +                                      BLI_array_append(deledges, l->e);
 +                                      bmesh_api_setflag(l->e, _FLAG_JF);
 +                              } else {
 +                                      if (d1 && !bmesh_api_getflag(l->e->v1, _FLAG_JF)) {
 +                                              BLI_array_append(delverts, l->e->v1);
 +                                              bmesh_api_setflag(l->e->v1, _FLAG_JF);
 +                                      }
 +
 +                                      if (d2 && !bmesh_api_getflag(l->e->v2, _FLAG_JF)) {
 +                                              BLI_array_append(delverts, l->e->v2);
 +                                              bmesh_api_setflag(l->e->v2, _FLAG_JF);
 +                                      }
 +                              }
 +                      }
 +
 +                      l = l->next;
 +              } while (l != bm_firstfaceloop(f));
 +
 +              for (lst=f->loops.first; lst; lst=lst->next) {
 +                      if (lst == f->loops.first) continue;
 +                      
 +                      BLI_remlink(&f->loops, lst);
 +                      BLI_addtail(&holes, lst);
 +              }
 +      }
 +
 +      /*create region face*/
 +      newf = BM_Make_Ngon(bm, v1, v2, edges, tote, 0);
 +      if (!newf || BMO_HasError(bm)) {
 +              if (!BMO_HasError(bm)) 
 +                      err = "Invalid boundary region to join faces";
 +              goto error;
 +      }
 +
 +      /*copy over loop data*/
 +      l = bm_firstfaceloop(newf);
 +      do {
 +              BMLoop *l2 = l->radial_next;
 +
 +              do {
 +                      if (bmesh_api_getflag(l2->f, _FLAG_JF))
 +                              break;
 +                      l2 = l2->radial_next;
 +              } while (l2 != l);
 +
 +              if (l2 != l) {
 +                      /*I think this is correct?*/
 +                      if (l2->v != l->v) {
 +                              l2 = l2->next;
 +                      }
 +
 +                      BM_Copy_Attributes(bm, bm, l2, l);
 +              }
 +
 +              l = l->next;
 +      } while (l != bm_firstfaceloop(newf));
 +      
 +      BM_Copy_Attributes(bm, bm, faces[0], newf);
 +
 +      /*add holes*/
 +      BLI_movelisttolist(&newf->loops, &holes);
 +
 +      /*update loop face pointers*/
 +      for (lst=newf->loops.first; lst; lst=lst->next) {
 +              l = lst->first;
 +              do {
 +                      l->f = newf;
 +                      l = l->next;
 +              } while (l != lst->first);
 +      }
 +
 +      bmesh_clear_systag_elements(bm, faces, totface, _FLAG_JF);
 +      bmesh_api_clearflag(newf, _FLAG_JF);
 +
 +      /* handle multires data*/
 +      if (CustomData_has_layer(&bm->ldata, CD_MDISPS)) {
 +              l = bm_firstfaceloop(newf);
 +              do {
 +                      for (i=0; i<totface; i++) {
 +                              BM_loop_interp_multires(bm, l, faces[i]);
 +                      }
 +                      
 +                      l = l->next;
 +              } while (l != bm_firstfaceloop(newf));
 +      }       
 +
 +      /*delete old geometry*/
 +      for (i=0; i<BLI_array_count(deledges); i++) {
 +              BM_Kill_Edge(bm, deledges[i]);
 +      }
 +
 +      for (i=0; i<BLI_array_count(delverts); i++) {
 +              BM_Kill_Vert(bm, delverts[i]);
 +      }
 +      
 +      BLI_array_free(edges);
 +      BLI_array_free(deledges);
 +      BLI_array_free(delverts);
 +
 +      BM_CHECK_ELEMENT(bm, newf);
 +      return newf;
 +error:
 +      bmesh_clear_systag_elements(bm, faces, totface, _FLAG_JF);
 +      BLI_array_free(edges);
 +      BLI_array_free(deledges);
 +      BLI_array_free(delverts);
 +
 +      if (err) {
 +              BMO_RaiseError(bm, bm->currentop, BMERR_DISSOLVEFACES_FAILED, err);
 +      }
 +      return NULL;
 +}
 +
 +static BMFace *bmesh_addpolylist(BMesh *bm, BMFace *UNUSED(example))
 +{
 +      BMFace *f;
 +      BMLoopList *lst;
 +
 +      f = BLI_mempool_calloc(bm->fpool);
 +      lst = BLI_mempool_calloc(bm->looplistpool);
 +
 +      f->head.htype = BM_FACE;
 +      BLI_addtail(&f->loops, lst);
 +
 +      BM_SetIndex(f, bm->totface); /* set_ok */
 +
 +      bm->totface++;
 +
 +      /*allocate flags*/
 +      f->head.flags = BLI_mempool_calloc(bm->toolflagpool);
 +
 +      CustomData_bmesh_set_default(&bm->pdata, &f->head.data);
 +
 +      f->len = 0;
 +      f->totbounds = 1;
 +
 +      return (BMFace*) f;
 +}
 +
 +/**
 + *                    bmesh_SFME
 + *
 + *    SPLIT FACE MAKE EDGE:
 + *
 + *    Takes as input two vertices in a single face. An edge is created which divides the original face
 + *    into two distinct regions. One of the regions is assigned to the original face and it is closed off.
 + *    The second region has a new face assigned to it.
 + *
 + *    Examples:
 + *
 + *     Before:               After:
 + *     ----------           ----------
 + *     |        |           |        |
 + *     |        |           |   f1   |
 + *    v1   f1   v2          v1======v2
 + *     |        |           |   f2   |
 + *     |        |           |        |
 + *     ----------           ----------
 + *
 + *    Note that the input vertices can be part of the same edge. This will
 + *  result in a two edged face. This is desirable for advanced construction
 + *  tools and particularly essential for edge bevel. Because of this it is
 + *  up to the caller to decide what to do with the extra edge.
 + *
 + *  If holes is NULL, then both faces will lose
 + *  all holes from the original face.  Also, you cannot split between
 + *  a hole vert and a boundary vert; that case is handled by higher-
 + *  level wrapping functions (when holes are fully implemented, anyway).
 + *
 + *  Note that holes represents which holes goes to the new face, and of
 + *  course this requires removing them from the exitsing face first, since
 + *  you cannot have linked list links inside multiple lists.
 + *
 + *    Returns -
 + *  A BMFace pointer
 + */
 +BMFace *bmesh_sfme(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2,
 +                                 BMLoop **rl, ListBase *holes)
 +{
 +
 +      BMFace *f2;
 +      BMLoop *v1loop = NULL, *v2loop = NULL, *curloop, *f1loop=NULL, *f2loop=NULL;
 +      BMEdge *e;
 +      BMLoopList *lst, *lst2;
 +      int i, len, f1len, f2len;
 +
 +      /*verify that v1 and v2 are in face.*/
 +      len = f->len;
 +      for(i = 0, curloop = bm_firstfaceloop(f); i < len; i++, curloop = curloop->next) {
 +              if(curloop->v == v1) v1loop = curloop;
 +              else if(curloop->v == v2) v2loop = curloop;
 +      }
 +
 +      if(!v1loop || !v2loop) return NULL;
 +
 +      /*allocate new edge between v1 and v2*/
 +      e = BM_Make_Edge(bm, v1, v2, NULL, 0);
 +
 +      f2 = bmesh_addpolylist(bm,f);
 +      f1loop = bmesh_create_loop(bm,v2,e,f,v2loop);
 +      f2loop = bmesh_create_loop(bm,v1,e,f2,v1loop);
 +
 +      f1loop->prev = v2loop->prev;
 +      f2loop->prev = v1loop->prev;
 +      v2loop->prev->next = f1loop;
 +      v1loop->prev->next = f2loop;
 +
 +      f1loop->next = v1loop;
 +      f2loop->next = v2loop;
 +      v1loop->prev = f1loop;
 +      v2loop->prev = f2loop;
 +
 +      lst = f->loops.first;
 +      lst2 = f2->loops.first;
 +
 +      lst2->first = lst2->last = f2loop;
 +      lst->first = lst->last = f1loop;
 +
 +      /*validate both loops*/
 +      /*I dont know how many loops are supposed to be in each face at this point! FIXME!*/
 +
 +      /*go through all of f2's loops and make sure they point to it properly.*/
 +      curloop = lst2->first;
 +      f2len = 0;
 +      do {
 +              curloop->f = f2;
 +
 +              curloop = curloop->next;
 +              f2len++;
 +      } while (curloop != lst2->first);
 +
 +      /*link up the new loops into the new edges radial*/
 +      bmesh_radial_append(e, f1loop);
 +      bmesh_radial_append(e, f2loop);
 +
 +      f2->len = f2len;
 +
 +      f1len = 0;
 +      curloop = lst->first;
 +      do {
 +              f1len++;
 +              curloop = curloop->next;
 +      } while (curloop != lst->first);
 +
 +      f->len = f1len;
 +
 +      if(rl) *rl = f2loop;
 +
 +      if (holes) {
 +              BLI_movelisttolist(&f2->loops, holes);
 +      } else {
 +              /*this code is not significant until holes actually work ;) */
 +              //printf("warning: call to split face euler without holes argument; holes will be tossed.\n");
 +              for (lst=f->loops.last; lst != f->loops.first; lst=lst2) {
 +                      lst2 = lst->prev;
 +                      BLI_mempool_free(bm->looplistpool, lst);
 +              }
 +      }
 +
 +      BM_CHECK_ELEMENT(bm, e);
 +      BM_CHECK_ELEMENT(bm, f);
 +      BM_CHECK_ELEMENT(bm, f2);
 +      
 +      return f2;
 +}
 +
 +/**
 + *                    bmesh_SEMV
 + *
 + *    SPLIT EDGE MAKE VERT:
 + *    Takes a given edge and splits it into two, creating a new vert.
 + *
 + *
 + *            Before: OV---------TV
 + *            After:  OV----NV---TV
 + *
 + *  Returns -
 + *    BMVert pointer.
 + *
 +*/
 +
 +BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **re){
 +      BMLoop *nextl;
 +      BMEdge *ne;
 +      BMVert *nv, *ov;
 +      int i, edok, valence1=0, valence2=0;
 +
 +      if(bmesh_vert_in_edge(e,tv) == 0) return NULL;
 +      ov = bmesh_edge_getothervert(e,tv);
 +
 +      /*count valence of v1*/
 +      valence1 = bmesh_disk_count(ov);
 +
 +      /*count valence of v2*/
 +      valence2 = bmesh_disk_count(tv);
 +
 +      nv = BM_Make_Vert(bm, tv->co, tv);
 +      ne = BM_Make_Edge(bm, nv, tv, e, 0);
 +
 +      bmesh_disk_remove_edge(ne, tv);
 +      bmesh_disk_remove_edge(ne, nv);
 +
 +      /*remove e from v2's disk cycle*/
 +      bmesh_disk_remove_edge(e, tv);
 +
 +      /*swap out tv for nv in e*/
 +      bmesh_edge_swapverts(e, tv, nv);
 +
 +      /*add e to nv's disk cycle*/
 +      bmesh_disk_append_edge(e, nv);
 +
 +      /*add ne to nv's disk cycle*/
 +      bmesh_disk_append_edge(ne, nv);
 +
 +      /*add ne to tv's disk cycle*/
 +      bmesh_disk_append_edge(ne, tv);
 +
 +      /*verify disk cycles*/
 +      edok = bmesh_disk_validate(valence1, ov->e, ov);
 +      if(!edok) bmesh_error();
 +      edok = bmesh_disk_validate(valence2, tv->e, tv);
 +      if(!edok) bmesh_error();
 +      edok = bmesh_disk_validate(2, nv->e, nv);
 +      if(!edok) bmesh_error();
 +
 +      /*Split the radial cycle if present*/
 +      nextl = e->l;
 +      e->l = NULL;
 +      if(nextl) {
 +              BMLoop *nl, *l;
 +              int radlen = bmesh_radial_length(nextl);
 +              int first1=0, first2=0;
 +
 +              /*Take the next loop. Remove it from radial. Split it. Append to appropriate radials.*/
 +              while(nextl) {
 +                      l=nextl;
 +                      l->f->len++;
 +                      nextl = nextl!=nextl->radial_next ? nextl->radial_next : NULL;
 +                      bmesh_radial_remove_loop(l, NULL);
 +
 +                      nl = bmesh_create_loop(bm,NULL,NULL,l->f,l);
 +                      nl->prev = l;
 +                      nl->next = (l->next);
 +                      nl->prev->next = nl;
 +                      nl->next->prev = nl;
 +                      nl->v = nv;
 +
 +                      /*assign the correct edge to the correct loop*/
 +                      if(bmesh_verts_in_edge(nl->v, nl->next->v, e)) {
 +                              nl->e = e;
 +                              l->e = ne;
 +
 +                              /*append l into ne's rad cycle*/
 +                              if(!first1) {
 +                                      first1 = 1;
 +                                      l->radial_next = l->radial_prev = NULL;
 +                              }
 +
 +                              if(!first2) {
 +                                      first2 = 1;
 +                                      l->radial_next = l->radial_prev = NULL;
 +                              }
 +                              
 +                              bmesh_radial_append(nl->e, nl);
 +                              bmesh_radial_append(l->e, l);
 +                      }
 +                      else if(bmesh_verts_in_edge(nl->v, nl->next->v, ne)){
 +                              nl->e = ne;
 +                              l->e = e;
 +
 +                              /*append l into ne's rad cycle*/
 +                              if(!first1) {
 +                                      first1 = 1;
 +                                      l->radial_next = l->radial_prev = NULL;
 +                              }
 +
 +                              if(!first2) {
 +                                      first2 = 1;
 +                                      l->radial_next = l->radial_prev = NULL;
 +                              }
 +
 +                              bmesh_radial_append(nl->e, nl);
 +                              bmesh_radial_append(l->e, l);
 +                      }
 +
 +              }
 +
 +              /*verify length of radial cycle*/
 +              edok = bmesh_radial_validate(radlen, e->l);
 +              if(!edok) bmesh_error();
 +              edok = bmesh_radial_validate(radlen, ne->l);
 +              if(!edok) bmesh_error();
 +
 +              /*verify loop->v and loop->next->v pointers for e*/
 +              for(i=0,l=e->l; i < radlen; i++, l = l->radial_next){
 +                      if(!(l->e == e)) bmesh_error();
 +                      //if(!(l->radial_next == l)) bmesh_error();
 +                      if(l->prev->e != ne && l->next->e != ne) bmesh_error();
 +                      edok = bmesh_verts_in_edge(l->v, l->next->v, e);
 +                      if(!edok) bmesh_error();
 +                      if(l->v == l->next->v) bmesh_error();
 +                      if(l->e == l->next->e) bmesh_error();
 +
 +                      /*verify loop cycle for kloop->f*/
 +                      BM_CHECK_ELEMENT(bm, l);
 +                      BM_CHECK_ELEMENT(bm, l->v);
 +                      BM_CHECK_ELEMENT(bm, l->e);
 +                      BM_CHECK_ELEMENT(bm, l->f);
 +              }
 +              /*verify loop->v and loop->next->v pointers for ne*/
 +              for(i=0,l=ne->l; i < radlen; i++, l = l->radial_next){
 +                      if(!(l->e == ne)) bmesh_error();
 +                      //if(!(l->radial_next == l)) bmesh_error();
 +                      if( l->prev->e != e && l->next->e != e) bmesh_error();
 +                      edok = bmesh_verts_in_edge(l->v, l->next->v, ne);
 +                      if(!edok) bmesh_error();
 +                      if(l->v == l->next->v) bmesh_error();
 +                      if(l->e == l->next->e) bmesh_error();
 +
 +                      BM_CHECK_ELEMENT(bm, l);
 +                      BM_CHECK_ELEMENT(bm, l->v);
 +                      BM_CHECK_ELEMENT(bm, l->e);
 +                      BM_CHECK_ELEMENT(bm, l->f);
 +              }
 +      }
 +
 +      BM_CHECK_ELEMENT(bm, ne);
 +      BM_CHECK_ELEMENT(bm, nv);
 +      BM_CHECK_ELEMENT(bm, ov);
 +      BM_CHECK_ELEMENT(bm, e);
 +      BM_CHECK_ELEMENT(bm, tv);
 +
 +      if(re) *re = ne;
 +      return nv;
 +}
 +
 +/**
 + *                    bmesh_JEKV
 + *
 + *    JOIN EDGE KILL VERT:
 + *    Takes a an edge and pointer to one of its vertices and collapses
 + *    the edge on that vertex.
 + *    
 + *    Before:    OE      KE
 + *                     ------- -------
 + *               |     ||      |
 + *            OV     KV      TV
 + *
 + *
 + *   After:             OE      
 + *                     ---------------
 + *               |             |
 + *            OV             TV
 + *
 + *
 + *    Restrictions:
 + *    KV is a vertex that must have a valance of exactly two. Furthermore
 + *  both edges in KV's disk cycle (OE and KE) must be unique (no double
 + *  edges).
 + *
 + *    It should also be noted that this euler has the possibility of creating
 + *    faces with just 2 edges. It is up to the caller to decide what to do with
 + *  these faces.
 + *
 + *  Returns -
 + *    1 for success, 0 for failure.
 + */
 +int bmesh_jekv(BMesh *bm, BMEdge *ke, BMVert *kv)
 +{
 +      BMEdge *oe;
 +      BMVert *ov, *tv;
 +      BMLoop *killoop, *l;
 +      int len,radlen=0, halt = 0, i, valence1, valence2,edok;
 +      BMLoop **loops = NULL;
 +      BLI_array_staticdeclare(loops, 256);
 +
 +      if(bmesh_vert_in_edge(ke,kv) == 0) return 0;
 +      len = bmesh_disk_count(kv);
 +      
 +      if(len == 2){
 +              oe = bmesh_disk_nextedge(ke, kv);
 +              tv = bmesh_edge_getothervert(ke, kv);
 +              ov = bmesh_edge_getothervert(oe, kv);           
 +              halt = bmesh_verts_in_edge(kv, tv, oe); /*check for double edges*/
 +              
 +              if(halt) return 0;
 +              else{
 +                      /*For verification later, count valence of ov and tv*/
 +                      valence1 = bmesh_disk_count(ov);
 +                      valence2 = bmesh_disk_count(tv);
 +                      
 +                      /*remove oe from kv's disk cycle*/
 +                      bmesh_disk_remove_edge(oe,kv);
 +                      /*relink oe->kv to be oe->tv*/
 +                      bmesh_edge_swapverts(oe, kv, tv);
 +                      /*append oe to tv's disk cycle*/
 +                      bmesh_disk_append_edge(oe, tv);
 +                      /*remove ke from tv's disk cycle*/
 +                      bmesh_disk_remove_edge(ke, tv);
 +              
 +                      /*deal with radial cycle of ke*/
 +                      radlen = bmesh_radial_length(ke->l);
 +                      if(ke->l){
 +                              /*first step, fix the neighboring loops of all loops in ke's radial cycle*/
 +                              for(i=0,killoop = ke->l; i<radlen; i++, killoop = bmesh_radial_nextloop(killoop)){
 +                                      /*relink loops and fix vertex pointer*/
 +                                      if( killoop->next->v == kv ) killoop->next->v = tv;
 +
 +                                      killoop->next->prev = killoop->prev;
 +                                      killoop->prev->next = killoop->next;
 +                                      if (bm_firstfaceloop(killoop->f) == killoop)
 +                                              bm_firstfaceloop(killoop->f) = killoop->next;
 +                                      killoop->next = NULL;
 +                                      killoop->prev = NULL;
 +
 +                                      /*fix len attribute of face*/
 +                                      killoop->f->len--;
 +                              }
 +                              /*second step, remove all the hanging loops attached to ke*/
 +                              killoop = ke->l;
 +                              radlen = bmesh_radial_length(ke->l);
 +                              /*this should be wrapped into a bme_free_radial function to be used by bmesh_KF as well...*/
 +                              for (i=0;i<radlen;i++) {
 +                                      BLI_array_growone(loops);
 +                                      loops[BLI_array_count(loops)-1] = killoop;
 +                                      killoop = bmesh_radial_nextloop(killoop);
 +                              }
 +                              for (i=0;i<radlen;i++) {
 +                                      bm->totloop--;
 +                                      BLI_mempool_free(bm->lpool, loops[i]);
 +                              }
 +                              /*Validate radial cycle of oe*/
 +                              edok = bmesh_radial_validate(radlen,oe->l);
 +                              if(!edok) bmesh_error();
 +                      }
 +
 +                      /*deallocate edge*/
 +                      BM_remove_selection(bm, ke);
 +                      BLI_mempool_free(bm->toolflagpool, ke->head.flags);
 +                      BLI_mempool_free(bm->epool, ke);
 +                      bm->totedge--;
 +                      /*deallocate vertex*/
 +                      BM_remove_selection(bm, kv);
 +                      BLI_mempool_free(bm->toolflagpool, kv->head.flags);
 +                      BLI_mempool_free(bm->vpool, kv);
 +                      bm->totvert--;
 +                      /* account for both above */
 +                      bm->elem_index_dirty |= BM_VERT | BM_EDGE;
 +
 +                      /*Validate disk cycle lengths of ov,tv are unchanged*/
 +                      edok = bmesh_disk_validate(valence1, ov->e, ov);
 +                      if(!edok) bmesh_error();
 +                      edok = bmesh_disk_validate(valence2, tv->e, tv);
 +                      if(!edok) bmesh_error();
 +
 +                      /*Validate loop cycle of all faces attached to oe*/
 +                      for(i=0,l = oe->l; i<radlen; i++, l = bmesh_radial_nextloop(l)){
 +                              if(l->e != oe) bmesh_error();
 +                              edok = bmesh_verts_in_edge(l->v, l->next->v, oe);
 +                              if(!edok) bmesh_error();
 +                              edok = bmesh_loop_validate(l->f);
 +                              if(!edok) bmesh_error();
 +
 +                              BM_CHECK_ELEMENT(bm, l);
 +                              BM_CHECK_ELEMENT(bm, l->v);
 +                              BM_CHECK_ELEMENT(bm, l->e);
 +                              BM_CHECK_ELEMENT(bm, l->f);
 +                      }
 +
 +                      BM_CHECK_ELEMENT(bm, ov);
 +                      BM_CHECK_ELEMENT(bm, tv);
 +                      BM_CHECK_ELEMENT(bm, oe);
 +
 +                      return 1;
 +              }
 +      }
 +      return 0;
 +}
 +
 +/**
 + *                    bmesh_JFKE
 + *
 + *    JOIN FACE KILL EDGE:
 + *    
 + *    Takes two faces joined by a single 2-manifold edge and fuses them togather.
 + *    The edge shared by the faces must not be connected to any other edges which have
 + *    Both faces in its radial cycle
 + *
 + *    Examples:
 + *    
 + *        A                   B
 + *     ----------           ----------
 + *     |        |           |        | 
 + *     |   f1   |           |   f1   |
 + *    v1========v2 = Ok!    v1==V2==v3 == Wrong!
 + *     |   f2   |           |   f2   |
 + *     |        |           |        |
 + *     ----------           ---------- 
 + *
 + *    In the example A, faces f1 and f2 are joined by a single edge, and the euler can safely be used.
 + *    In example B however, f1 and f2 are joined by multiple edges and will produce an error. The caller
 + *    in this case should call bmesh_JEKV on the extra edges before attempting to fuse f1 and f2.
 + *
 + *    Also note that the order of arguments decides whether or not certain per-face attributes are present
 + *    in the resultant face. For instance vertex winding, material index, smooth flags, ect are inherited
 + *    from f1, not f2.
 + *
 + *  Returns -
 + *    A BMFace pointer
 +*/
 +BMFace *bmesh_jfke(BMesh *bm, BMFace *f1, BMFace *f2, BMEdge *e)
 +{
 +      BMLoop *curloop, *f1loop=NULL, *f2loop=NULL;
 +      int newlen = 0,i, f1len=0, f2len=0, radlen=0, edok, shared;
 +      BMIter iter;
 +
 +      /*can't join a face to itself*/
 +      if(f1 == f2) return NULL;
 +      /*verify that e is in both f1 and f2*/
 +      f1len = f1->len;
 +      f2len = f2->len;
 +      BM_ITER(curloop, &iter, bm, BM_LOOPS_OF_FACE, f1) {
 +              if(curloop->e == e){ 
 +                      f1loop = curloop;
 +                      break;
 +              }
 +      }
 +      BM_ITER(curloop, &iter, bm, BM_LOOPS_OF_FACE, f2) {
 +              if(curloop->e == e){
 +                      f2loop = curloop;
 +                      break;
 +              }
 +      }
 +      if (!(f1loop && f2loop)) return NULL;
 +      
 +      /*validate that edge is 2-manifold edge*/
 +      radlen = bmesh_radial_length(f1loop);
 +      if(radlen != 2) return NULL;
 +
 +      /*validate direction of f2's loop cycle is compatible.*/
 +      if(f1loop->v == f2loop->v) return NULL;
 +
 +      /*
 +              validate that for each face, each vertex has another edge in its disk cycle that is 
 +              not e, and not shared.
 +      */
 +      if(bmesh_radial_find_face(f1loop->next->e,f2)) return NULL;
 +      if(bmesh_radial_find_face(f1loop->prev->e,f2)) return NULL;
 +      if(bmesh_radial_find_face(f2loop->next->e,f1)) return NULL;
 +      if(bmesh_radial_find_face(f2loop->prev->e,f1)) return NULL;
 +      
 +      /*validate only one shared edge*/
 +      shared = BM_Face_Sharededges(f1,f2);
 +      if(shared > 1) return NULL;
 +
 +      /*validate no internal joins*/
 +      for(i=0, curloop = bm_firstfaceloop(f1); i < f1len; i++, curloop = curloop->next)
 +              bmesh_api_setindex(curloop->v, 0);
 +      for(i=0, curloop = bm_firstfaceloop(f2); i < f2len; i++, curloop = curloop->next)
 +              bmesh_api_setindex(curloop->v, 0);
 +
 +      for(i=0, curloop = bm_firstfaceloop(f1); i < f1len; i++, curloop = curloop->next) {
 +              if (curloop != f1loop)
 +                      bmesh_api_setindex(curloop->v, bmesh_api_getindex(curloop->v) + 1);
 +      }
 +      for(i=0, curloop = bm_firstfaceloop(f2); i < f2len; i++, curloop = curloop->next) {
 +              if (curloop != f2loop)
 +                      bmesh_api_setindex(curloop->v, bmesh_api_getindex(curloop->v) + 1);
 +      }
 +
 +      for(i=0, curloop = bm_firstfaceloop(f1); i < f1len; i++, curloop = curloop->next) {
 +              if (bmesh_api_getindex(curloop->v) > 1)
 +                      return NULL;
 +      }
 +      
 +      for(i=0, curloop = bm_firstfaceloop(f2); i < f2len; i++, curloop = curloop->next) {
 +              if (bmesh_api_getindex(curloop->v) > 1)
 +                      return NULL;
 +      }
 +
 +      /*join the two loops*/
 +      f1loop->prev->next = f2loop->next;
 +      f2loop->next->prev = f1loop->prev;
 +      
 +      f1loop->next->prev = f2loop->prev;
 +      f2loop->prev->next = f1loop->next;
 +      
 +      /*if f1loop was baseloop, make f1loop->next the base.*/
 +      if(bm_firstfaceloop(f1) == f1loop)
 +              bm_firstfaceloop(f1) = f1loop->next;
 +
 +      /*increase length of f1*/
 +      f1->len += (f2->len - 2);
 +
 +      /*make sure each loop points to the proper face*/
 +      newlen = f1->len;
 +      for(i = 0, curloop = bm_firstfaceloop(f1); i < newlen; i++, curloop = curloop->next)
 +              curloop->f = f1;
 +      
 +      /*remove edge from the disk cycle of its two vertices.*/
 +      bmesh_disk_remove_edge(f1loop->e, f1loop->e->v1);
 +      bmesh_disk_remove_edge(f1loop->e, f1loop->e->v2);
 +      
 +      /*deallocate edge and its two loops as well as f2*/
 +      BLI_mempool_free(bm->toolflagpool, f1loop->e->head.flags);
 +      BLI_mempool_free(bm->epool, f1loop->e);
 +      bm->totedge--;
 +      BLI_mempool_free(bm->lpool, f1loop);
 +      bm->totloop--;
 +      BLI_mempool_free(bm->lpool, f2loop);
 +      bm->totloop--;
 +      BLI_mempool_free(bm->toolflagpool, f2->head.flags);
 +      BLI_mempool_free(bm->fpool, f2);
 +      bm->totface--;
 +      /* account for both above */
 +      bm->elem_index_dirty |= BM_EDGE | BM_FACE;
 +
 +      BM_CHECK_ELEMENT(bm, f1);
 +
 +      /*validate the new loop cycle*/
 +      edok = bmesh_loop_validate(f1);
 +      if(!edok) bmesh_error();
 +      
 +      return f1;
 +}
 +
 +/*
 + * BMESH SPLICE VERT
 + *
 + * merges two verts into one (v into vtarget).
 + */
 +static int bmesh_splicevert(BMesh *bm, BMVert *v, BMVert *vtarget)
 +{
 +      BMEdge *e;
 +      BMLoop *l;
 +      BMIter liter;
 +
 +      /* verts already spliced */
 +      if (v == vtarget) {
 +              return 0;
 +      }
 +
 +      /* retarget all the loops of v to vtarget */
 +      BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
 +              l->v = vtarget;
 +      }
 +
 +      /* move all the edges from v's disk to vtarget's disk */
 +      e = v->e;
 +      while (e != NULL) {
 +              bmesh_disk_remove_edge(e, v);
 +              bmesh_edge_swapverts(e, v, vtarget);
 +              bmesh_disk_append_edge(e, vtarget);
 +              e = v->e;
 +      }
 +
 +      BM_CHECK_ELEMENT(bm, v);
 +      BM_CHECK_ELEMENT(bm, vtarget);
 +
 +      /* v is unused now, and can be killed */
 +      BM_Kill_Vert(bm, v);
 +
 +      return 1;
 +}
 +
 +/* BMESH CUT VERT
 + *
 + * cut all disjoint fans that meet at a vertex, making a unique
 + * vertex for each region. returns an array of all resulting
 + * vertices.
 + */
 +static int bmesh_cutvert(BMesh *bm, BMVert *v, BMVert ***vout, int *len)
 +{
 +      BMEdge **stack = NULL;
 +      BLI_array_declare(stack);
 +      BMVert **verts = NULL;
 +      GHash *visithash;
 +      BMIter eiter, liter;
 +      BMLoop *l;
 +      BMEdge *e;
 +      int i, maxindex;
 +      BMLoop *nl;
 +
 +      visithash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "bmesh_cutvert visithash");
 +
 +      maxindex = 0;
 +      BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
 +              if (BLI_ghash_haskey(visithash, e)) {
 +                      continue;
 +              }
 +
 +              /* Prime the stack with this unvisited edge */
 +              BLI_array_append(stack, e);
 +
 +              /* Considering only edges and faces incident on vertex v, walk
 +                 the edges & faces and assign an index to each connected set */
 +              while ((e = BLI_array_pop(stack))) {
 +                      BLI_ghash_insert(visithash, e, SET_INT_IN_POINTER(maxindex));
 +                      BM_SetIndex(e, maxindex); /* set_dirty! */ /* BMESH_TODO, check the indexs are is invalid after this function runs */
 +
 +                      BM_ITER(l, &liter, bm, BM_LOOPS_OF_EDGE, e) {
 +                              nl = (l->v == v) ? l->prev : l->next;
 +                              if (!BLI_ghash_haskey(visithash, nl->e)) {
 +                                      BLI_array_append(stack, nl->e);
 +                              }
 +                      }
 +              }
 +
 +              maxindex++;
 +      }
 +      bm->elem_index_dirty |= BM_EDGE;
 +
 +      /* Make enough verts to split v for each group */
 +      verts = MEM_callocN(sizeof(BMVert *) * maxindex, "bmesh_cutvert");
 +      verts[0] = v;
 +      for (i = 1; i < maxindex; i++) {
 +              verts[i] = BM_Make_Vert(bm, v->co, v);
 +      }
 +
 +      /* Replace v with the new verts in each group */
 +      BM_ITER(l, &liter, bm, BM_LOOPS_OF_VERT, v) {
 +              i = GET_INT_FROM_POINTER(BLI_ghash_lookup(visithash, l->e));
 +              if (i == 0) {
 +                      continue;
 +              }
 +
 +              /* Loops here should alway refer to an edge that has v as an
 +                 endpoint. For each appearance of this vert in a face, there
 +                 will actually be two iterations: one for the loop heading
 +                 towards vertex v, and another for the loop heading out from
 +                 vertex v. Only need to swap the vertex on one of those times,
 +                 on the outgoing loop. */
 +              if (l->v == v) {
 +                      l->v = verts[i];
 +              }
 +      }
 +
 +      BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) {
 +              i = GET_INT_FROM_POINTER(BLI_ghash_lookup(visithash, e));
 +              if (i == 0) {
 +                      continue;
 +              }
 +
 +              BLI_assert(e->v1 == v || e->v2 == v);
 +              bmesh_disk_remove_edge(e, v);
 +              bmesh_edge_swapverts(e, v, verts[i]);
 +              bmesh_disk_append_edge(e, verts[i]);
 +      }
 +
 +      BLI_ghash_free(visithash, NULL, NULL);
 +      BLI_array_free(stack);
 +
 +      for (i = 0; i < maxindex; i++) {
 +              BM_CHECK_ELEMENT(bm, verts[i]);
 +      }
 +
 +      if (len != NULL) {
 +              *len = maxindex;
 +      }
 +
 +      if (vout != NULL) {
 +              *vout = verts;
 +      }
 +      else {
 +              MEM_freeN(verts);
 +      }
 +
 +      return 1;
 +}
 +
 +/* BMESH SPLICE EDGE
 + *
 + * splice two unique edges which share the same two vertices into one edge.
 + *
 + * edges must already have the same vertices
 + */
 +static int UNUSED_FUNCTION(bmesh_spliceedge)(BMesh *bm, BMEdge *e, BMEdge *etarget)
 +{
 +      BMLoop *l;
 +
 +      if (!BM_Vert_In_Edge(e, etarget->v1) || !BM_Vert_In_Edge(e, etarget->v2)) {
 +              /* not the same vertices can't splice */
 +              return 0;
 +      }
 +
 +      while (e->l) {
 +              l = e->l;
 +              BLI_assert(BM_Vert_In_Edge(etarget, l->v));
 +              BLI_assert(BM_Vert_In_Edge(etarget, l->next->v));
 +              bmesh_radial_remove_loop(l, e);
 +              bmesh_radial_append(etarget, l);
 +      }
 +
 +      BLI_assert(bmesh_radial_length(e->l) == 0);
 +
 +      BM_CHECK_ELEMENT(bm, e);
 +      BM_CHECK_ELEMENT(bm, etarget);
 +
 +      BM_Kill_Edge(bm, e);
 +
 +      return 1;
 +}
 +
 +/*
 + * BMESH CUT EDGE
 + *
 + * Cuts a single edge into two edge: the original edge and
 + * a new edge that has only "cutl" in its radial.
 + *
 + * Does nothing if cutl is already the only loop in the
 + * edge radial.
 + */
 +static int bmesh_cutedge(BMesh *bm, BMEdge *e, BMLoop *cutl)
 +{
 +      BMEdge *ne;
 +      int radlen;
 +
 +      BLI_assert(cutl->e == e);
 +      BLI_assert(e->l);
 +      
 +      radlen = bmesh_radial_length(e->l);
 +      if (radlen < 2) {
 +              /* no cut required */
 +              return 1;
 +      }
 +
 +      if (cutl == e->l) {
 +              e->l = cutl->radial_next;
 +      }
 +
 +      ne = BM_Make_Edge(bm, e->v1, e->v2, e, 0);
 +      bmesh_radial_remove_loop(cutl, e);
 +      bmesh_radial_append(ne, cutl);
 +      cutl->e = ne;
 +
 +      BLI_assert(bmesh_radial_length(e->l) == radlen - 1);
 +      BLI_assert(bmesh_radial_length(ne->l) == 1);
 +
 +      BM_CHECK_ELEMENT(bm, ne);
 +      BM_CHECK_ELEMENT(bm, e);
 +
 +      return 1;
 +}
 +
 +/*
 + * BMESH UNGLUE REGION MAKE VERT
 + *
 + * Disconnects a face from its vertex fan at loop sl.
 + */
 +static BMVert *bmesh_urmv_loop(BMesh *bm, BMLoop *sl)
 +{
 +      BMVert **vtar;
 +      int len, i;
 +      BMVert *nv = NULL;
 +      BMVert *sv = sl->v;
 +
 +      /* peel the face from the edge radials on both sides of the
 +         loop vert, disconnecting the face from its fan */
 +      bmesh_cutedge(bm, sl->e, sl);
 +      bmesh_cutedge(bm, sl->prev->e, sl->prev);
 +
 +      if (bmesh_disk_count(sv) == 2) {
 +              /* If there are still only two edges out of sv, then
 +                 this whole URMV was just a no-op, so exit now. */
 +              return sv;
 +      }
 +
 +      /* Update the disk start, so that v->e points to an edge
 +         not touching the split loop. This is so that bmesh_cutvert
 +         will leave the original sv on some *other* fan (not the
 +         one-face fan that holds the unglue face). */
 +      while (sv->e == sl->e || sv->e == sl->prev->e) {
 +              sv->e = bmesh_disk_nextedge(sv->e, sv);
 +      }
 +
 +      /* Split all fans connected to the vert, duplicating it for
 +         each fans. */
 +      bmesh_cutvert(bm, sv, &vtar, &len);
 +
 +      /* There should have been at least two fans cut apart here,
 +         otherwise the early exit would have kicked in. */
 +      BLI_assert(len >= 2);
 +
 +      nv = sl->v;
 +
 +      /* Desired result here is that a new vert should always be
 +         created for the unglue face. This is so we can glue any
 +         extras back into the original vert. */
 +      BLI_assert(nv != sv);
 +      BLI_assert(sv == vtar[0]);
 +
 +      /* If there are more than two verts as a result, glue together
 +         all the verts except the one this URMV intended to create */
 +      if (len > 2) {
 +              for (i = 0; i < len; i++) {
 +                      if (vtar[i] == nv) {
 +                              break;
 +                      }
 +              }
 +
 +              if (i != len) {
 +                      /* Swap the single vert that was needed for the
 +                         unglue into the last array slot */
 +                      SWAP(BMVert *, vtar[i], vtar[len - 1]);
 +
 +                      /* And then glue the rest back together */
 +                      for (i = 1; i < len - 1; i++) {
 +                              bmesh_splicevert(bm, vtar[i], vtar[0]);
 +                      }
 +              }
 +      }
 +
 +      MEM_freeN(vtar);
 +
 +      return nv;
 +}
 +
 +/*
 + * BMESH UNGLUE REGION MAKE VERT
 + *
 + * Disconnects sf from the vertex fan at sv
 + */
 +BMVert *bmesh_urmv(BMesh *bm, BMFace *sf, BMVert *sv)
 +{
 +      BMLoop *hl, *sl;
 +
 +      hl = sl = bm_firstfaceloop(sf);
 +      do {
 +              if (sl->v == sv) break;
 +              sl = sl->next;
 +      } while (sl != hl);
 +              
 +      if (sl->v != sv) {
 +              /* sv is not part of sf */
 +              return NULL;
 +      }
 +
 +      return bmesh_urmv_loop(bm, sl);
 +}
index c6859669f22e7e9e34defa06766fec4afedd8fda,0000000000000000000000000000000000000000..4bedba5f4e4cfd873b4c1e636c76d16766637534
mode 100644,000000..100644
--- /dev/null
@@@ -1,262 -1,0 +1,264 @@@
 +/*
 + *
 + *    BMesh Walker API.
 + *
 + * ***** 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. The Blender
 + * Foundation also sells licenses for use in proprietary software under
 + * the Blender License.  See http://www.blender.org/BL/ for information
 + * about this.
 + *
 + * This program is distributed in the hope that it will be useful,
 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 + * GNU General Public License for more details.
 + *
 + * You should have received a copy of the GNU General Public License
 + * along with this program; if not, write to the Free Software Foundation,
 + * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 + *
 + * Contributor(s): Joseph Eagar, Geoffrey Bantle, Levi Schooley.
 + *
 + * ***** END GPL LICENSE BLOCK *****
 + */
 +
 +#include <stdio.h>
 +#include <string.h>
++#include <stdlib.h>
 +
 +#include "BKE_customdata.h"
 +
 +#include "DNA_meshdata_types.h"
 +#include "DNA_mesh_types.h"
 +
 +#include "BLI_utildefines.h"
++#include "BLI_listbase.h"
 +#include "BLI_mempool.h"
 +#include "BLI_array.h"
 +
 +#include "bmesh.h"
 +
 +#include "bmesh_private.h"
 +#include "bmesh_walkers_private.h"
 +
 +/*
 + - joeedh -
 + design notes:
 +
 + original desing: walkers directly emulation recursive functions.
 + functions save their state onto a worklist, and also add new states
 + to implement recursive or looping behaviour.  generally only one
 + state push per call with a specific state is desired.
 +
 + basic design pattern: the walker step function goes through it's
 + list of possible choices for recursion, and recurses (by pushing a new state)
 + using the first non-visited one.  this choise is the flagged as visited using
 + the ghash.  each step may push multiple new states onto the worklist at once.
 +
 + * walkers use tool flags, not header flags
 + * walkers now use ghash for storing visited elements, 
 +   rather then stealing flags.  ghash can be rewritten 
 +   to be faster if necassary, in the far future :) .
 + * tools should ALWAYS have necassary error handling
 +   for if walkers fail.
 +*/
 +
 +void *BMW_Begin(BMWalker *walker, void *start)
 +{
 +      walker->begin(walker, start);
 +      
 +      return BMW_currentstate(walker) ? walker->step(walker) : NULL;
 +}
 +
 +/*
 + * BMW_CREATE
 + * 
 + * Allocates and returns a new mesh walker of 
 + * a given type. The elements visited are filtered
 + * by the bitmask 'searchmask'.
 + *
 +*/
 +
 +void BMW_Init(BMWalker *walker, BMesh *bm, int type, int searchmask, int flag)
 +{
 +      memset(walker, 0, sizeof(BMWalker));
 +
 +      walker->flag = flag;
 +      walker->bm = bm;
 +      walker->restrictflag = searchmask;
 +      walker->visithash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "bmesh walkers 1");
 +      
 +      if (type >= BMW_MAXWALKERS || type < 0) {
 +              bmesh_error();
 +              fprintf(stderr, "Invalid walker type in BMW_Init; type: %d, searchmask: %d, flag: %d\n", type, searchmask, flag);
 +      }
 +      
 +      if (type != BMW_CUSTOM) {
 +              walker->begin = bm_walker_types[type]->begin;
 +              walker->yield = bm_walker_types[type]->yield;
 +              walker->step = bm_walker_types[type]->step;
 +              walker->structsize = bm_walker_types[type]->structsize;
 +              walker->order = bm_walker_types[type]->order;
 +      }
 +      
 +      walker->worklist = BLI_mempool_create(walker->structsize, 100, 100, 1, 0);
 +      walker->states.first = walker->states.last = NULL;
 +}
 +
 +/*
 + * BMW_End
 + *
 + * Frees a walker's worklist.
 + *
 +*/
 +
 +void BMW_End(BMWalker *walker)
 +{
 +      BLI_mempool_destroy(walker->worklist);
 +      BLI_ghash_free(walker->visithash, NULL, NULL);
 +}
 +
 +
 +/*
 + * BMW_Step
 + *
 +*/
 +
 +void *BMW_Step(BMWalker *walker)
 +{
 +      BMHeader *head;
 +
 +      head = BMW_walk(walker);
 +
 +      return head;
 +}
 +
 +/*
 + * BMW_CurrentDepth
 + *
 + * Returns the current depth of the walker.
 + *
 +*/
 +
 +int BMW_CurrentDepth(BMWalker *walker)
 +{
 +      return walker->depth;
 +}
 +
 +/*
 + * BMW_WALK
 + *
 + * Steps a mesh walker forward by one element
 + *
 + * BMESH_TODO:
 + *  -add searchmask filtering
 + *
 +*/
 +
 +void *BMW_walk(BMWalker *walker)
 +{
 +      void *current = NULL;
 +
 +      while(BMW_currentstate(walker)){
 +              current = walker->step(walker);
 +              if(current) return current;
 +      }
 +      return NULL;
 +}
 +
 +/*
 + * BMW_currentstate
 + *
 + * Returns the first state from the walker state
 + * worklist. This state is the the next in the
 + * worklist for processing.
 + *
 +*/
 +
 +void* BMW_currentstate(BMWalker *walker)
 +{
 +      bmesh_walkerGeneric *currentstate = walker->states.first;
 +      if (currentstate) {
 +              /* Automatic update of depth. For most walkers that
 +                 follow the standard "Step" pattern of:
 +                  - read current state
 +                  - remove current state
 +                  - push new states
 +                  - return walk result from just-removed current state
 +                 this simple automatic update should keep track of depth
 +                 just fine. Walkers that deviate from that pattern may
 +                 need to manually update the depth if they care about
 +                 keeping it correct. */
 +              walker->depth = currentstate->depth + 1;
 +      }
 +      return currentstate;
 +}
 +
 +/*
 + * BMW_removestate
 + *
 + * Remove and free an item from the end of the walker state
 + * worklist.
 + *
 +*/
 +
 +void BMW_removestate(BMWalker *walker)
 +{
 +      void *oldstate;
 +      oldstate = BMW_currentstate(walker);
 +      BLI_remlink(&walker->states, oldstate);
 +      BLI_mempool_free(walker->worklist, oldstate);
 +}
 +
 +/*
 + * BMW_newstate
 + *
 + * Allocate a new empty state and put it on the worklist.
 + * A pointer to the new state is returned so that the caller
 + * can fill in the state data. The new state will be inserted
 + * at the front for depth-first walks, and at the end for
 + * breadth-first walks.
 + *
 +*/
 +
 +void* BMW_addstate(BMWalker *walker)
 +{
 +      bmesh_walkerGeneric *newstate;
 +      newstate = BLI_mempool_alloc(walker->worklist);
 +      newstate->depth = walker->depth;
 +      switch (walker->order)
 +      {
 +      case BMW_DEPTH_FIRST:
 +              BLI_addhead(&walker->states, newstate);
 +              break;
 +      case BMW_BREADTH_FIRST:
 +              BLI_addtail(&walker->states, newstate);
 +              break;
 +      default:
 +              BLI_assert(0);
 +              break;
 +      }               
 +      return newstate;
 +}
 +
 +/*
 + * BMW_reset
 + *
 + * Frees all states from the worklist, resetting the walker
 + * for reuse in a new walk.
 + *
 +*/
 +
 +void BMW_reset(BMWalker *walker)
 +{
 +      while (BMW_currentstate(walker)) {
 +              BMW_removestate(walker);
 +      }
 +      walker->depth = 0;
 +      BLI_ghash_free(walker->visithash, NULL, NULL);
 +      walker->visithash = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "bmesh walkers 1");
 +}
index d0b355eca97d0bbe173aef96610d9dd4899f5305,0000000000000000000000000000000000000000..ca1935bde93a5dfd2ab595e091a14be1d0a7db93
mode 100644,000000..100644
--- /dev/null
@@@ -1,1178 -1,0 +1,1179 @@@
 +/*
 + * ***** 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. The Blender
 + * Foundation also sells licenses for use in proprietary software under
 + * the Blender License.  See http://www.blender.org/BL/ for information
 + * about this.        
 + *
 + * This program is distributed in the hope that it will be useful,
 + * but WITHOUT ANY WARRANTY; without even the implied warranty of
 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 + * GNU General Public License for more details.
 + *
 + * You should have received a copy of the GNU General Public License
 + * along with this program; if not, write to the Free Software Foundation,
 + * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 + *
 + * Contributor(s): Joseph Eagar.
 + *
 + * ***** END GPL LICENSE BLOCK *****
 + */
 +
 +#include "MEM_guardedalloc.h"
 +
 +#include "BKE_utildefines.h"
 +#include "BKE_tessmesh.h"
 +
 +#include "BLI_math.h"
 +#include "BLI_rand.h"
 +#include "BLI_ghash.h"
 +#include "BLI_array.h"
++#include "BLI_noise.h"
 +#include "BLI_utildefines.h"
 +
 +#include "DNA_object_types.h"
 +
 +#include "ED_mesh.h"
 +
 +#include "bmesh.h"
 +#include "bmesh_private.h"
 +
 +#include "mesh_intern.h"
 +#include "subdivideop.h"
 +
 +#include <stdio.h>
 +#include <stdlib.h>
 +#include <string.h>
 +#include <math.h>
 +
 +/*flags for all elements share a common bitfield space*/
 +#define SUBD_SPLIT    1
 +
 +#define EDGE_PERCENT  2
 +
 +/*I don't think new faces are flagged, currently, but
 +  better safe than sorry.*/
 +#define FACE_NEW      4
 +#define FACE_CUSTOMFILL       8
 +#define ELE_INNER     16
 +#define ELE_SPLIT     32
 +#define ELE_CONNECT   64
 +
 +/*stuff for the flag paramter.  note that
 +  what used to live in "beauty" and
 +  in "seltype" live here.  still have to
 +  convert the beauty flags over, which
 +  is why it starts at 128 (to avoid
 +  collision).*/
 +#define SELTYPE_INNER 128
 +
 +/*
 +NOTE: beauty has been renamed to flag!
 +*/
 +
 +/*generic subdivision rules:
 +  
 +  * two selected edges in a face should make a link
 +    between them.
 +
 +  * one edge should do, what? make pretty topology, or just
 +    split the edge only?
 +*/
 +
 +#if 0 //misc. code, maps a parametric coordinate to a fractal line
 +float lastrnd[3], vec2[3] = {0.0f, 0.0f, 0.0f};
 +int seed = BLI_rand();
 +int d, i, j, dp, lvl, wid;
 +float df;
 +
 +BLI_srandom(seed);
 +
 +wid = (params->numcuts+2);
 +dp = perc*wid;
 +wid /= 2;
 +d = lvl = 0;
 +while (1) {
 +      if (d > dp) {
 +              d -= wid;
 +      } else if (d < dp) {
 +              d += wid;
 +      } else {
 +              break;
 +      }
 +      
 +      
 +      wid = MAX2((wid/2), 1);
 +      lvl++;
 +}
 +
 +zero_v3(vec1);
 +df = 1.0f;
 +for (i=0; i<lvl; i++, df /= 4.0f) {
 +      int tot = (1<<i);
 +      
 +      lastrnd[0] = BLI_drand()-0.5f;
 +      lastrnd[1] = BLI_drand()-0.5f;
 +      lastrnd[2] = BLI_drand()-0.5f;
 +      for (j=0; j<tot; j++) {
 +              float a, b, rnd[3], rnd2[3];
 +              
 +              rnd[0] = BLI_drand()-0.5f;
 +              rnd[1] = BLI_drand()-0.5f;
 +              rnd[2] = BLI_drand()-0.5f;
 +              
 +              a = (float)j*(float)((float)params->numcuts/(float)tot);
 +              b = (float)(j+1)*(float)((float)params->numcuts/(float)tot);
 +              if (d >= a && d <= b) {
 +                      interp_v3_v3v3(rnd2, lastrnd, rnd, (((float)d)-a)/(b-a));
 +                      mul_v3_fl(rnd2, df);
 +                      add_v3_v3(vec1, rnd2);
 +              }
 +              
 +              copy_v3_v3(lastrnd, rnd);
 +      }
 +}
 +#endif
 +/*connects face with smallest len, which I think should always be correct for
 +  edge subdivision*/
 +static BMEdge *connect_smallest_face(BMesh *bm, BMVert *v1, BMVert *v2, BMFace **nf) {
 +      BMIter iter, iter2;
 +      BMVert *v;
 +      BMLoop *nl;
 +      BMFace *face, *curf = NULL;
 +
 +      /*this isn't the best thing in the world.  it doesn't handle cases where there's
 +        multiple faces yet.  that might require a convexity test to figure out which
 +        face is "best," and who knows what for non-manifold conditions.*/
 +      for (face = BMIter_New(&iter, bm, BM_FACES_OF_VERT, v1); face; face=BMIter_Step(&iter)) {
 +              for (v=BMIter_New(&iter2, bm, BM_VERTS_OF_FACE, face); v; v=BMIter_Step(&iter2)) {
 +                      if (v == v2) {
 +                              if (!curf || face->len < curf->len) curf = face;
 +                      }
 +              }
 +      }
 +
 +      if (curf) {
 +              face = BM_Split_Face(bm, curf, v1, v2, &nl, NULL);
 +              
 +              if (nf) *nf = face;
 +              return nl ? nl->e : NULL;
 +      }
 +
 +      return NULL;
 +}
 +/* calculates offset for co, based on fractal, sphere or smooth settings  */
 +static void alter_co(BMesh *bm, BMVert *v, BMEdge *UNUSED(origed), const subdparams *params, float perc,
 +                   BMVert *vsta, BMVert *vend)
 +{
 +      float tvec[3], prev_co[3], fac;
 +      float *co=NULL;
 +      int i, totlayer = CustomData_number_of_layers(&bm->vdata, CD_SHAPEKEY);
 +      
 +      BM_Vert_UpdateAllNormals(bm, v);
 +
 +      co = CustomData_bmesh_get_n(&bm->vdata, v->head.data, CD_SHAPEKEY, params->origkey);
 +      copy_v3_v3(prev_co, co);
 +
 +      if(params->beauty & B_SMOOTH) {
 +              /* we calculate an offset vector vec1[], to be added to *co */
 +              float len, nor[3], nor1[3], nor2[3], smooth=params->smooth;
 +
 +              sub_v3_v3v3(nor, vsta->co, vend->co);
 +              len= 0.5f*normalize_v3(nor);
 +
 +              copy_v3_v3(nor1, vsta->no);
 +              copy_v3_v3(nor2, vend->no);
 +
 +              /* cosine angle */
 +              fac=  dot_v3v3(nor, nor1);
 +              mul_v3_v3fl(tvec, nor1, fac);
 +
 +              /* cosine angle */
 +              fac= -dot_v3v3(nor, nor2);
 +              madd_v3_v3fl(tvec, nor2, fac);
 +
 +              /* falloff for multi subdivide */
 +              smooth *= sqrtf(fabsf(1.0f - 2.0f*fabsf(0.5f-perc)));
 +
 +              mul_v3_fl(tvec, smooth * len);
 +
 +              add_v3_v3(co, tvec);
 +      }
 +      else if(params->beauty & B_SPHERE) { /* subdivide sphere */
 +              normalize_v3(co);
 +              mul_v3_fl(co, params->smooth);
 +      }
 +
 +      if(params->beauty & B_FRACTAL) {
 +              float len = len_v3v3(vsta->co, vend->co);
 +              float vec2[3] = {0.0f, 0.0f, 0.0f}, co2[3];
 +
 +              fac= params->fractal*len;
 +
 +              add_v3_v3(vec2, vsta->no);
 +              add_v3_v3(vec2, vend->no);
 +              mul_v3_fl(vec2, 0.5f);
 +
 +              add_v3_v3v3(co2, v->co, params->off);
 +              tvec[0] = fac*(BLI_gTurbulence(1.0, co2[0], co2[1], co2[2], 15, 0, 1)-0.5f);
 +              tvec[1] = fac*(BLI_gTurbulence(1.0, co2[0], co2[1], co2[2], 15, 0, 1)-0.5f);
 +              tvec[2] = fac*(BLI_gTurbulence(1.0, co2[0], co2[1], co2[2], 15, 0, 1)-0.5f);
 +
 +              mul_v3_v3(vec2, tvec);
 +
 +              /*add displacement*/
 +              add_v3_v3v3(co, co, vec2);
 +      }
 +
 +      /* apply the new difference to the rest of the shape keys,
 +       * note that this doent take rotations into account, we _could_ support
 +       * this by getting the normals and coords for each shape key and
 +       * re-calculate the smooth value for each but this is quite involved.
 +       * for now its ok to simply apply the difference IMHO - campbell */
 +      sub_v3_v3v3(tvec, prev_co, co);
 +
 +      for (i=0; i<totlayer; i++) {
 +              if (params->origkey != i) {
 +                      co = CustomData_bmesh_get_n(&bm->vdata, v->head.data, CD_SHAPEKEY, i);
 +                      sub_v3_v3(co, tvec);
 +              }
 +      }
 +
 +}
 +
 +/* assumes in the edge is the correct interpolated vertices already */
 +/* percent defines the interpolation, rad and flag are for special options */
 +/* results in new vertex with correct coordinate, vertex normal and weight group info */
 +static BMVert *bm_subdivide_edge_addvert(BMesh *bm, BMEdge *edge,BMEdge *oedge,
 +                                         const subdparams *params, float percent,
 +                                         float percent2,
 +                                         BMEdge **out,BMVert *vsta,BMVert *vend)
 +{
 +      BMVert *ev;
 +      
 +      ev = BM_Split_Edge(bm, edge->v1, edge, out, percent);
 +
 +      BMO_SetFlag(bm, ev, ELE_INNER);
 +
 +      /* offset for smooth or sphere or fractal */
 +      alter_co(bm, ev, oedge, params, percent2, vsta, vend);
 +
 +#if 0 //BMESH_TODO
 +      /* 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;
 +              }
 +      }
 +#endif        
 +      
 +      return ev;
 +}
 +
 +static BMVert *subdivideedgenum(BMesh *bm, BMEdge *edge, BMEdge *oedge,
 +                                int curpoint, int totpoint, const subdparams *params,
 +                                BMEdge **newe, BMVert *vsta, BMVert *vend)
 +{
 +      BMVert *ev;
 +      float percent, percent2 = 0.0f;
 +       
 +      if (BMO_TestFlag(bm, edge, EDGE_PERCENT) && totpoint == 1)
 +              percent = BMO_Get_MapFloat(bm, params->op, 
 +                                      "edgepercents", edge);
 +      else {
 +              percent= 1.0f/(float)(totpoint+1-curpoint);
 +              percent2 = (float)(curpoint+1) / (float)(totpoint+1);
 +
 +      }
 +      
 +      ev= bm_subdivide_edge_addvert(bm, edge, oedge, params, percent,
 +                                    percent2, newe, vsta, vend);
 +      return ev;
 +}
 +
 +static void bm_subdivide_multicut(BMesh *bm, BMEdge *edge, const subdparams *params,
 +                                  BMVert *vsta, BMVert *vend)
 +{
 +      BMEdge *eed = edge, *newe, temp = *edge;
 +      BMVert *v, ov1=*edge->v1, ov2=*edge->v2, *v1=edge->v1, *v2=edge->v2;
 +      int i, numcuts = params->numcuts;
 +
 +      temp.v1 = &ov1;
 +      temp.v2 = &ov2;
 +      
 +      for(i=0;i<numcuts;i++) {
 +              v = subdivideedgenum(bm, eed, &temp, i, params->numcuts, params, 
 +                                   &newe, vsta, vend);
 +
 +              BMO_SetFlag(bm, v, SUBD_SPLIT);
 +              BMO_SetFlag(bm, eed, SUBD_SPLIT);
 +              BMO_SetFlag(bm, newe, SUBD_SPLIT);
 +
 +              BMO_SetFlag(bm, v, ELE_SPLIT);
 +              BMO_SetFlag(bm, eed, ELE_SPLIT);
 +              BMO_SetFlag(bm, newe, SUBD_SPLIT);
 +
 +              BM_CHECK_ELEMENT(bm, v);
 +              if (v->e) BM_CHECK_ELEMENT(bm, v->e);
 +              if (v->e && v->e->l) BM_CHECK_ELEMENT(bm, v->e->l->f);
 +      }
 +      
 +      alter_co(bm, v1, &temp, params, 0, &ov1, &ov2);
 +      alter_co(bm, v2, &temp, params, 1.0, &ov1, &ov2);
 +}
 +
 +/*note: the patterns are rotated as necassary to
 +  match the input geometry.  they're based on the
 +  pre-split state of the  face*/
 +
 +/*
 +     
 +v3---------v2
 +|          |
 +|          |
 +|          |
 +|          |
 +v4---v0---v1
 +
 +*/
 +static void quad_1edge_split(BMesh *bm, BMFace *UNUSED(face),
 +                             BMVert **verts, const subdparams *params)
 +{
 +      BMFace *nf;
 +      int i, add, numcuts = params->numcuts;
 +
 +      /*if it's odd, the middle face is a quad, otherwise it's a triangle*/
 +      if (numcuts % 2==0) {
 +              add = 2;
 +              for (i=0; i<numcuts; i++) {
 +                      if (i == numcuts/2) add -= 1;
 +                      connect_smallest_face(bm, verts[i], verts[numcuts+add], 
 +                                         &nf);
 +              }
 +      } else {
 +              add = 2;
 +              for (i=0; i<numcuts; i++) {
 +                      connect_smallest_face(bm, verts[i], verts[numcuts+add], 
 +                                         &nf);
 +                      if (i == numcuts/2) {
 +                              add -= 1;
 +                              connect_smallest_face(bm, verts[i], 
 +                                                 verts[numcuts+add],
 +                                                 &nf);
 +                      }
 +              }
 +
 +      }
 +}
 +
 +static subdpattern quad_1edge = {
 +      {1, 0, 0, 0},
 +      quad_1edge_split,
 +      4,
 +};
 +
 +
 +/*
 +v6--------v5
 +|          |
 +|          |v4s
 +|          |v3s
 +|   s  s   |
 +v7-v0--v1-v2
 +
 +*/
 +static void quad_2edge_split_path(BMesh *bm, BMFace *UNUSED(face), BMVert **verts, 
 +                                  const subdparams *params)
 +{
 +      BMFace *nf;
 +      int i, numcuts = params->numcuts;
 +      
 +      for (i=0; i<numcuts; i++) {
 +              connect_smallest_face(bm, verts[i], verts[numcuts+(numcuts-i)],
 +                                 &nf);
 +      }
 +      connect_smallest_face(bm, verts[numcuts*2+3], verts[numcuts*2+1], &nf);
 +}
 +
 +static subdpattern quad_2edge_path = {
 +      {1, 1, 0, 0},
 +      quad_2edge_split_path,
 +      4,
 +};
 +
 +/*
 +v6--------v5
 +|          |
 +|          |v4s
 +|          |v3s
 +|   s  s   |
 +v7-v0--v1-v2
 +
 +*/
 +static void quad_2edge_split_innervert(BMesh *bm, BMFace *UNUSED(face), BMVert **verts, 
 +                                       const subdparams *params)
 +{
 +      BMFace *nf;
 +      BMVert *v, *lastv;
 +      BMEdge *e, *ne, olde;
 +      int i, numcuts = params->numcuts;
 +      
 +      lastv = verts[numcuts];
 +
 +      for (i=numcuts-1; i>=0; i--) {
 +              e = connect_smallest_face(bm, verts[i], verts[numcuts+(numcuts-i)],
 +                                 &nf);
 +              
 +              olde = *e;
 +              v = bm_subdivide_edge_addvert(bm, e, &olde, params, 0.5f, 0.5f, &ne, e->v1, e->v2);
 +
 +              if (i != numcuts-1)
 +                      connect_smallest_face(bm, lastv, v, &nf);
 +              
 +              lastv = v;
 +      }
 +
 +      connect_smallest_face(bm, lastv, verts[numcuts*2+2], &nf);      
 +}
 +
 +static subdpattern quad_2edge_innervert = {
 +      {1, 1, 0, 0},
 +      quad_2edge_split_innervert,
 +      4,
 +};
 +
 +/*
 +v6--------v5
 +|          |
 +|          |v4s
 +|          |v3s
 +|   s  s   |
 +v7-v0--v1-v2
 +
 +*/
 +static void quad_2edge_split_fan(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
 +                                 const subdparams *params)
 +{
 +      BMFace *nf;
 +      /* BMVert *v; */               /* UNUSED */
 +      /* BMVert *lastv= verts[2]; */ /* UNUSED */
 +      /* BMEdge *e, *ne; */          /* UNUSED */
 +      int i, numcuts = params->numcuts;
 +
 +      for (i=0; i<numcuts; i++) {
 +              connect_smallest_face(bm, verts[i], verts[numcuts*2+2], &nf);
 +              connect_smallest_face(bm, verts[numcuts+(numcuts-i)],
 +                                    verts[numcuts*2+2], &nf);
 +      }
 +}
 +
 +static subdpattern quad_2edge_fan = {
 +      {1, 1, 0, 0},
 +      quad_2edge_split_fan,
 +      4,
 +};
 +
 +/*  s   s
 +v8--v7--v6-v5
 +|          |
 +|          v4 s
 +|          |
 +|          v3 s
 +|   s  s   |
 +v9-v0--v1-v2
 +
 +*/
 +static void quad_3edge_split(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
 +                             const subdparams *params)
 +{
 +      BMFace *nf;
 +      int i, add=0, numcuts = params->numcuts;
 +      
 +      for (i=0; i<numcuts; i++) {
 +              if (i == numcuts/2) {
 +                      if (numcuts % 2 != 0) {
 +                              connect_smallest_face(bm, verts[numcuts-i-1+add], 
 +                                               verts[i+numcuts+1], &nf);
 +                      }
 +                      add = numcuts*2+2;
 +              }
 +              connect_smallest_face(bm, verts[numcuts-i-1+add], 
 +                                   verts[i+numcuts+1], &nf);
 +      }
 +
 +      for (i=0; i<numcuts/2+1; i++) {
 +              connect_smallest_face(bm, verts[i],verts[(numcuts-i)+numcuts*2+1],
 +                                 &nf);
 +      }
 +}
 +
 +static subdpattern quad_3edge = {
 +      {1, 1, 1, 0},
 +      quad_3edge_split,
 +      4,
 +};
 +
 +/*
 + 
 +           v8--v7-v6--v5
 +           |     s    |
 +           |v9 s     s|v4
 +first line |          |   last line
 +           |v10s s   s|v3
 +           v11-v0--v1-v2
 +
 +         it goes from bottom up
 +*/
 +static void quad_4edge_subdivide(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
 +                                 const subdparams *params)
 +{
 +      BMFace *nf;
 +      BMVert *v, *v1, *v2;
 +      BMEdge *e, *ne, temp;
 +      BMVert **lines;
 +      int numcuts = params->numcuts;
 +      int i, j, a, b, s=numcuts+2 /* , totv=numcuts*4+4 */;
 +
 +      lines = MEM_callocN(sizeof(BMVert*)*(numcuts+2)*(numcuts+2),
 +                                   "q_4edge_split");
 +      /*build a 2-dimensional array of verts,
 +        containing every vert (and all new ones)
 +        in the face.*/
 +
 +      /*first line*/
 +      for (i=0; i<numcuts+2; i++) {
 +              lines[i] = verts[numcuts*3+2+(numcuts-i+1)];
 +      }
 +
 +      /*last line*/
 +      for (i=0; i<numcuts+2; i++) {
 +              lines[(s-1)*s+i] = verts[numcuts+i];
 +      }
 +      
 +      /*first and last members of middle lines*/
 +      for (i=0; i<numcuts; i++) {
 +              a = i;
 +              b = numcuts + 1 + numcuts + 1 + (numcuts - i - 1);
 +              
 +              e = connect_smallest_face(bm, verts[a], verts[b], &nf);
 +              if (!e)
 +                      continue;
 +
 +              BMO_SetFlag(bm, e, ELE_INNER);
 +              BMO_SetFlag(bm, nf, ELE_INNER);
 +
 +              
 +              v1 = lines[(i+1)*s] = verts[a];
 +              v2 = lines[(i+1)*s + s-1] = verts[b];
 +              
 +              temp = *e;
 +              for (a=0; a<numcuts; a++) {
 +                      v = subdivideedgenum(bm, e, &temp, a, numcuts, params, &ne,
 +                                          v1, v2);
 +                      if (!v)
 +                              bmesh_error();
 +
 +                      BMO_SetFlag(bm, ne, ELE_INNER);
 +                      lines[(i+1)*s+a+1] = v;
 +              }
 +      }
 +
 +      for (i=1; i<numcuts+2; i++) {
 +              for (j=1; j<numcuts+1; j++) {
 +                      a = i*s + j;
 +                      b = (i-1)*s + j;
 +                      e = connect_smallest_face(bm, lines[a], lines[b], &nf);
 +                      if (!e)
 +                              continue;
 +
 +                      BMO_SetFlag(bm, e, ELE_INNER);
 +                      BMO_SetFlag(bm, nf, ELE_INNER);
 +              }
 +      }
 +
 +      MEM_freeN(lines);
 +}
 +
 +/*    v3
 +     / \
 +    /   \
 +   /     \
 +  /       \
 + /         \
 +v4--v0--v1--v2
 +    s    s
 +*/
 +static void tri_1edge_split(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
 +                            const subdparams *params)
 +{
 +      BMFace *nf;
 +      int i, numcuts = params->numcuts;
 +      
 +      for (i=0; i<numcuts; i++) {
 +              connect_smallest_face(bm, verts[i], verts[numcuts+1], &nf);
 +      }
 +}
 +
 +static subdpattern tri_1edge = {
 +      {1, 0, 0},
 +      tri_1edge_split,
 +      3,
 +};
 +
 +/*     v5
 +      / \
 + s v6/---\ v4 s
 +    / \ / \
 +sv7/---v---\ v3 s
 +  /  \/  \/ \
 + v8--v0--v1--v2
 +    s    s
 +*/
 +static void tri_3edge_subdivide(BMesh *bm, BMFace *UNUSED(face), BMVert **verts,
 +                                const subdparams *params)
 +{
 +      BMFace *nf;
 +      BMEdge *e, *ne, temp;
 +      BMVert ***lines, *v, ov1, ov2;
 +      void *stackarr[1];
 +      int i, j, a, b, numcuts = params->numcuts;
 +      
 +      /*number of verts in each line*/
 +      lines = MEM_callocN(sizeof(void*)*(numcuts+2), "triangle vert table");
 +      
 +      lines[0] = (BMVert**) stackarr;
 +      lines[0][0] = verts[numcuts*2+1];
 +      
 +      lines[1+numcuts] = MEM_callocN(sizeof(void*)*(numcuts+2), 
 +                                     "triangle vert table 2");
 +      for (i=0; i<numcuts; i++) {
 +              lines[1+numcuts][1+i] = verts[i];
 +      }
 +      lines[1+numcuts][0] = verts[numcuts*3+2];
 +      lines[1+numcuts][1+numcuts] = verts[numcuts];
 +
 +      for (i=0; i<numcuts; i++) {
 +              lines[i+1] = MEM_callocN(sizeof(void*)*(2+i), 
 +                                     "triangle vert table row");
 +              a = numcuts*2 + 2 + i;
 +              b = numcuts + numcuts - i;
 +              e = connect_smallest_face(bm, verts[a], verts[b], &nf);
 +              if (!e) goto cleanup;
 +
 +              BMO_SetFlag(bm, e, ELE_INNER);
 +              BMO_SetFlag(bm, nf, ELE_INNER);
 +
 +              lines[i+1][0] = verts[a];
 +              lines[i+1][1+i] = verts[b];
 +              
 +              temp = *e;
 +              ov1 = *verts[a];
 +              ov2 = *verts[b];
 +              temp.v1 = &ov1;
 +              temp.v2 = &ov2;
 +              for (j=0; j<i; j++) {
 +                      v = subdivideedgenum(bm, e, &temp, j, i, params, &ne,
 +                                           verts[a], verts[b]);
 +                      lines[i+1][j+1] = v;
 +
 +                      BMO_SetFlag(bm, ne, ELE_INNER);
 +              }
 +      }
 +      
 +
 +/*     v5
 +      / \
 + s v6/---\ v4 s
 +    / \ / \
 +sv7/---v---\ v3 s
 +  /  \/  \/ \
 + v8--v0--v1--v2
 +    s    s
 +*/
 +      for (i=1; i<numcuts+1; i++) {
 +              for (j=0; j<i; j++) {
 +                      e= connect_smallest_face(bm, lines[i][j], lines[i+1][j+1],
 +                                         &nf);
 +
 +                      BMO_SetFlag(bm, e, ELE_INNER);
 +                      BMO_SetFlag(bm, nf, ELE_INNER);
 +
 +                      e= connect_smallest_face(bm,lines[i][j+1],lines[i+1][j+1],
 +                                         &nf);
 +
 +                      BMO_SetFlag(bm, e, ELE_INNER);
 +                      BMO_SetFlag(bm, nf, ELE_INNER);
 +              }
 +      }
 +
 +cleanup:
 +      for (i=1; i<numcuts+2; i++) {
 +              if (lines[i]) MEM_freeN(lines[i]);
 +      }
 +
 +      MEM_freeN(lines);
 +}
 +
 +static subdpattern tri_3edge = {
 +      {1, 1, 1},
 +      tri_3edge_subdivide,
 +      3,
 +};
 +
 +
 +static subdpattern quad_4edge = {
 +      {1, 1, 1, 1},
 +      quad_4edge_subdivide,
 +      4,
 +};
 +
 +static subdpattern *patterns[] = {
 +      NULL, //quad single edge pattern is inserted here
 +      NULL, //quad corner vert pattern is inserted here
 +      NULL, //tri single edge pattern is inserted here
 +      NULL,
 +      &quad_3edge,
 +      NULL,
 +};
 +
 +#define PLEN  (sizeof(patterns) / sizeof(void*))
 +
 +typedef struct subd_facedata {
 +      BMVert *start; subdpattern *pat;
 +      int totedgesel; //only used if pat was NULL, e.g. no pattern was found
 +      BMFace *face;
 +} subd_facedata;
 +
 +void esubdivide_exec(BMesh *bmesh, BMOperator *op)
 +{
 +      BMOpSlot *einput;
 +      subdpattern *pat;
 +      subdparams params;
 +      subd_facedata *facedata = NULL;
 +      BMIter viter, fiter, liter;
 +      BMVert *v, **verts = NULL;
 +      BMEdge *edge, **edges = NULL;
 +      BMLoop *nl, *l, **splits = NULL, **loops = NULL;
 +      BMFace *face;
 +      BLI_array_declare(splits);
 +      BLI_array_declare(loops);
 +      BLI_array_declare(facedata);
 +      BLI_array_declare(edges);
 +      BLI_array_declare(verts);
 +      float smooth, fractal;
 +      int beauty, cornertype, singleedge, gridfill;
 +      int skey, seed, i, j, matched, a, b, numcuts, totesel;
 +      
 +      BMO_Flag_Buffer(bmesh, op, "edges", SUBD_SPLIT, BM_EDGE);
 +      
 +      numcuts = BMO_Get_Int(op, "numcuts");
 +      seed = BMO_Get_Int(op, "seed");
 +      smooth = BMO_Get_Float(op, "smooth");
 +      fractal = BMO_Get_Float(op, "fractal");
 +      beauty = BMO_Get_Int(op, "beauty");
 +      cornertype = BMO_Get_Int(op, "quadcornertype");
 +      singleedge = BMO_Get_Int(op, "singleedge");
 +      gridfill = BMO_Get_Int(op, "gridfill");
 +      
 +      BLI_srandom(seed);
 +      
 +      patterns[1] = NULL;
 +      //straight cut is patterns[1] == NULL
 +      switch (cornertype) {
 +              case SUBD_PATH:
 +                      patterns[1] = &quad_2edge_path;
 +                      break;
 +              case SUBD_INNERVERT:
 +                      patterns[1] = &quad_2edge_innervert;
 +                      break;
 +              case SUBD_FAN:
 +                      patterns[1] = &quad_2edge_fan;
 +                      break;
 +      }
 +      
 +      if (singleedge) {
 +              patterns[0] = &quad_1edge;
 +              patterns[2] = &tri_1edge;
 +      } else {
 +              patterns[0] = NULL;
 +              patterns[2] = NULL;
 +      }
 +
 +      if (gridfill) {
 +              patterns[3] = &quad_4edge;
 +              patterns[5] = &tri_3edge;
 +      } else {
 +              patterns[3] = NULL;
 +              patterns[5] = NULL;
 +      }
 +      
 +      /*add a temporary shapekey layer to store displacements on current geometry*/
 +      BM_add_data_layer(bmesh, &bmesh->vdata, CD_SHAPEKEY);
 +      skey = CustomData_number_of_layers(&bmesh->vdata, CD_SHAPEKEY)-1;
 +      
 +      BM_ITER(v, &viter, bmesh, BM_VERTS_OF_MESH, NULL) {
 +              float *co = CustomData_bmesh_get_n(&bmesh->vdata, v->head.data, CD_SHAPEKEY, skey);
 +              copy_v3_v3(co, v->co);
 +      }
 +
 +      /*first go through and tag edges*/
 +      BMO_Flag_To_Slot(bmesh, op, "edges",
 +               SUBD_SPLIT, BM_EDGE);
 +
 +      params.numcuts = numcuts;
 +      params.op = op;
 +      params.smooth = smooth;
 +      params.seed = seed;
 +      params.fractal = fractal;
 +      params.beauty = beauty;
 +      params.origkey = skey;
 +      params.off[0] = (float)BLI_drand()*200.0f;
 +      params.off[1] = (float)BLI_drand()*200.0f;
 +      params.off[2] = (float)BLI_drand()*200.0f;
 +      
 +      BMO_Mapping_To_Flag(bmesh, op, "custompatterns",
 +                          FACE_CUSTOMFILL);
 +
 +      BMO_Mapping_To_Flag(bmesh, op, "edgepercents",
 +                          EDGE_PERCENT);
 +
 +      for (face=BMIter_New(&fiter, bmesh, BM_FACES_OF_MESH, NULL);
 +           face; face=BMIter_Step(&fiter)) {
 +              BMEdge *e1 = NULL, *e2 = NULL;
 +              float vec1[3], vec2[3];
 +
 +              /*figure out which pattern to use*/
 +
 +              BLI_array_empty(edges);
 +              BLI_array_empty(verts);
 +              matched = 0;
 +
 +              i = 0;
 +              totesel = 0;
 +              for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
 +                   nl; nl=BMIter_Step(&liter)) {
 +                      BLI_array_growone(edges);
 +                      BLI_array_growone(verts);
 +                      edges[i] = nl->e;
 +                      verts[i] = nl->v;
 +
 +                      if (BMO_TestFlag(bmesh, edges[i], SUBD_SPLIT)) {
 +                              if (!e1) e1 = edges[i];
 +                              else e2 = edges[i];
 +
 +                              totesel++;
 +                      }
 +
 +                      i++;
 +              }
 +
 +              /*make sure the two edges have a valid angle to each other*/
 +              if (totesel == 2 && (e1->v1 == e2->v1 || e1->v1 == e2->v2 
 +                                   || e1->v2 == e2->v1 || e1->v2 == e2->v1)) {
 +                      float angle;
 +
 +                      sub_v3_v3v3(vec1, e1->v2->co, e1->v1->co);
 +                      sub_v3_v3v3(vec2, e2->v2->co, e2->v1->co);
 +                      normalize_v3(vec1);
 +                      normalize_v3(vec2);
 +
 +                      angle = dot_v3v3(vec1, vec2);
 +                      angle = fabsf(angle);
 +                      if (fabsf(angle - 1.0f) < 0.01f) {
 +                              totesel = 0;
 +                      }
 +              }
 +
 +              if (BMO_TestFlag(bmesh, face, FACE_CUSTOMFILL)) {
 +                      pat = BMO_Get_MapData(bmesh, op, 
 +                                  "custompatterns", face);
 +                      for (i=0; i<pat->len; i++) {
 +                              matched = 1;
 +                              for (j=0; j<pat->len; j++) {
 +                                      a = (j + i) % pat->len;
 +                                      if ((!!BMO_TestFlag(bmesh, edges[a], SUBD_SPLIT))
 +                                              != (!!pat->seledges[j])) {
 +                                                      matched = 0;
 +                                                      break;
 +                                      }
 +                              }
 +                              if (matched) {
 +                                      BLI_array_growone(facedata);
 +                                      b = BLI_array_count(facedata)-1;
 +                                      facedata[b].pat = pat;
 +                                      facedata[b].start = verts[i];
 +                                      facedata[b].face = face;
 +                                      facedata[b].totedgesel = totesel;
 +                                      BMO_SetFlag(bmesh, face, SUBD_SPLIT);
 +                                      break;
 +                              }
 +                      }
 +
 +                      /*obvously don't test for other patterns matching*/
 +                      continue;
 +              }
 +
 +              for (i=0; i<PLEN; i++) {
 +                      pat = patterns[i];
 +                      if (!pat) continue;
 +
 +                      if (pat->len == face->len) {
 +                              for (a=0; a<pat->len; a++) {
 +                                      matched = 1;
 +                                      for (b=0; b<pat->len; b++) {
 +                                              j = (b + a) % pat->len;
 +                                              if ((!!BMO_TestFlag(bmesh, edges[j], SUBD_SPLIT))
 +                                                      != (!!pat->seledges[b])) {
 +                                                              matched = 0;
 +                                                              break;
 +                                              }
 +                                      }
 +                                      if (matched) break;
 +                              }
 +                              if (matched) {
 +                                      BLI_array_growone(facedata);
 +                                      j = BLI_array_count(facedata) - 1;
 +
 +                                      BMO_SetFlag(bmesh, face, SUBD_SPLIT);
 +
 +                                      facedata[j].pat = pat;
 +                                      facedata[j].start = verts[a];
 +                                      facedata[j].face = face;
 +                                      facedata[j].totedgesel = totesel;
 +                                      break;
 +                              }
 +                      }
 +              
 +              }
 +              
 +              if (!matched && totesel) {
 +                      BLI_array_growone(facedata);
 +                      j = BLI_array_count(facedata) - 1;
 +                      
 +                      BMO_SetFlag(bmesh, face, SUBD_SPLIT);
 +                      facedata[j].totedgesel = totesel;
 +                      facedata[j].face = face;
 +              }
 +      }
 +
 +      einput = BMO_GetSlot(op, "edges");
 +
 +      /*go through and split edges*/
 +      for (i=0; i<einput->len; i++) {
 +              edge = ((BMEdge**)einput->data.p)[i];
 +              bm_subdivide_multicut(bmesh, edge, &params, edge->v1, edge->v2);
 +      }
 +
 +      i = 0;
 +      for (i=0; i<BLI_array_count(facedata); i++) {
 +              face = facedata[i].face;
 +
 +              /*figure out which pattern to use*/
 +              BLI_array_empty(verts);
 +
 +              pat = facedata[i].pat;
 +
 +              if (!pat && facedata[i].totedgesel == 2) {
 +                      int vlen;
 +                      
 +                      /*ok, no pattern.  we still may be able to do something.*/
 +                      BLI_array_empty(loops);
 +                      BLI_array_empty(splits);
 +
 +                      /*for case of two edges, connecting them shouldn't be too hard*/
 +                      BM_ITER(l, &liter, bmesh, BM_LOOPS_OF_FACE, face) {
 +                              BLI_array_growone(loops);
 +                              loops[BLI_array_count(loops)-1] = l;
 +                      }
 +                      
 +                      vlen = BLI_array_count(loops);
 +
 +                      /*find the boundary of one of the split edges*/
 +                      for (a=1; a<vlen; a++) {
 +                              if (!BMO_TestFlag(bmesh, loops[a-1]->v, ELE_INNER) 
 +                                  && BMO_TestFlag(bmesh, loops[a]->v, ELE_INNER))
 +                                      break;
 +                      }
 +                      
 +                      if (BMO_TestFlag(bmesh, loops[(a+numcuts+1)%vlen]->v, ELE_INNER)) {
 +                              b = (a+numcuts+1)%vlen;
 +                      } else {
 +                              /*find the boundary of the other edge.*/
 +                              for (j=0; j<vlen; j++) {
 +                                      b = (j + a + numcuts + 1) % vlen;
 +                                      if (!BMO_TestFlag(bmesh, loops[b==0 ? vlen-1 : b-1]->v, ELE_INNER)
 +                                          && BMO_TestFlag(bmesh, loops[b]->v, ELE_INNER))
 +                                              break;
 +                              }
 +                      }
 +                      
 +                      b += numcuts - 1;
 +
 +                      for (j=0; j<numcuts; j++) {
 +                              BLI_array_growone(splits);
 +                              splits[BLI_array_count(splits)-1] = loops[a];
 +                              
 +                              BLI_array_growone(splits);
 +                              splits[BLI_array_count(splits)-1] = loops[b];
 +
 +                              b = (b-1) % vlen;
 +                              a = (a+1) % vlen;
 +                      }
 +                      
 +                      //BM_LegalSplits(bmesh, face, splits, BLI_array_count(splits)/2);
 +
 +                      for (j=0; j<BLI_array_count(splits)/2; j++) {
 +                              if (splits[j*2]) {
 +                                      /* BMFace *nf= */ /* UNUSED */
 +                                      BM_Split_Face(bmesh, face, splits[j*2]->v, splits[j*2+1]->v, &nl, NULL);
 +                              }
 +                      }
 +
 +                      continue;
 +              } else if (!pat) {
 +                      continue;
 +              }
 +
 +              j = a = 0;
 +              for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
 +                   nl; nl=BMIter_Step(&liter)) {
 +                      if (nl->v == facedata[i].start) {
 +                              a = j+1;
 +                              break;
 +                      }
 +                      j++;
 +              }
 +
 +              for (j=0; j<face->len; j++) {
 +                      BLI_array_growone(verts);
 +              }
 +              
 +              j = 0;
 +              for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
 +                   nl; nl=BMIter_Step(&liter)) {
 +                      b = (j-a+face->len) % face->len;
 +                      verts[b] = nl->v;
 +                      j += 1;
 +              }
 +                                      
 +              BM_CHECK_ELEMENT(bmesh, face);
 +              pat->connectexec(bmesh, face, verts, &params);
 +      }
 +
 +      /*copy original-geometry displacements to current coordinates*/
 +      BM_ITER(v, &viter, bmesh, BM_VERTS_OF_MESH, NULL) {
 +              float *co = CustomData_bmesh_get_n(&bmesh->vdata, v->head.data, CD_SHAPEKEY, skey);
 +              copy_v3_v3(v->co, co);
 +      }
 +
 +      BM_free_data_layer_n(bmesh, &bmesh->vdata, CD_SHAPEKEY, skey);
 +      
 +      if (facedata) BLI_array_free(facedata);
 +      if (edges) BLI_array_free(edges);
 +      if (verts) BLI_array_free(verts);
 +      BLI_array_free(splits);
 +      BLI_array_free(loops);
 +
 +      BMO_Flag_To_Slot(bmesh, op, "outinner",
 +                       ELE_INNER, BM_ALL);    
 +      BMO_Flag_To_Slot(bmesh, op, "outsplit",
 +                       ELE_SPLIT, BM_ALL);
 +      
 +      BMO_Flag_To_Slot(bmesh, op, "geomout",
 +                       ELE_INNER|ELE_SPLIT|SUBD_SPLIT, BM_ALL);
 +}
 +
 +/*editmesh-emulating function*/
 +void BM_esubdivideflag(Object *UNUSED(obedit), BMesh *bm, int flag, float smooth,
 +               float fractal, int beauty, int numcuts, 
 +               int seltype, int cornertype, int singleedge, 
 +               int gridfill, int seed)
 +{
 +      BMOperator op;
 +      
 +      BMO_InitOpf(bm, &op, "esubd edges=%he smooth=%f fractal=%f "
 +                           "beauty=%d numcuts=%d quadcornertype=%d singleedge=%d "
 +                           "gridfill=%d seed=%d",
 +                           flag, smooth, fractal, beauty, numcuts,
 +                           cornertype, singleedge, gridfill, seed);
 +      
 +      BMO_Exec_Op(bm, &op);
 +      
 +      if (seltype == SUBDIV_SELECT_INNER) {
 +              BMOIter iter;
 +              BMHeader *ele;
 +              // int i;
 +              
 +              ele = BMO_IterNew(&iter, bm, &op, "outinner", BM_EDGE|BM_VERT);
 +              for (; ele; ele=BMO_IterStep(&iter)) {
 +                      BM_Select(bm, ele, 1);
 +              }
 +      } else if (seltype == SUBDIV_SELECT_LOOPCUT) {
 +              BMOIter iter;
 +              BMHeader *ele;
 +              // int i;
 +              
 +              /*deselect input*/
 +              BM_clear_flag_all(bm, BM_SELECT);
 +
 +              ele = BMO_IterNew(&iter, bm, &op, "outinner", BM_EDGE|BM_VERT);
 +              for (; ele; ele=BMO_IterStep(&iter)) {
 +                      BM_Select(bm, ele, 1);
 +
 +                      if (ele->htype == BM_VERT) {
 +                              BMEdge *e;
 +                              BMIter eiter;
 +
 +                              BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, ele) {
 +                                      if (!BM_TestHFlag(e, BM_SELECT) && BM_TestHFlag(e->v1, BM_SELECT) 
 +                                                                                                      && BM_TestHFlag(e->v2, BM_SELECT)) {
 +                                              BM_Select(bm, e, 1);
 +                                              bm->totedgesel += 1;
 +                                      } else if (BM_TestHFlag(e, BM_SELECT) && (!BM_TestHFlag(e->v1, BM_SELECT) 
 +                                                                                                                || !BM_TestHFlag(e->v2, BM_SELECT))) {
 +                                              BM_Select(bm, e, 0);
 +                                              bm->totedgesel -= 1;            
 +                                      }
 +                              }
 +                      }
 +              }
 +      }
 +
 +      BMO_Finish_Op(bm, &op);
 +}
 +
 +void esplit_exec(BMesh *bm, BMOperator *op)
 +{
 +      BMOIter siter;
 +      BMEdge *e;
 +      subdparams params;
 +      int skey;
 +      
 +      params.numcuts = BMO_GetSlot(op, "numcuts")->data.i;
 +      params.op = op;
 +      
 +      BM_add_data_layer(bm, &bm->vdata, CD_SHAPEKEY);
 +      skey = CustomData_number_of_layers(&bm->vdata, CD_SHAPEKEY)-1;
 +      
 +      params.origkey = skey;
 +
 +      /*go through and split edges*/
 +      BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
 +              bm_subdivide_multicut(bm, e, &params, e->v1, e->v2);
 +      }
 +
 +      BMO_Flag_To_Slot(bm, op, "outsplit",
 +                       ELE_SPLIT, BM_ALL);
 +
 +      BM_free_data_layer_n(bm, &bm->vdata, CD_SHAPEKEY, skey);
 +}
index 79dac3ae396d7bafbd849385396ac41abf7f3630,0000000000000000000000000000000000000000..55f6c9d0a6e896b8f66036fe6917ffae759d1c96
mode 100755,000000..100755
--- /dev/null
@@@ -1,1987 -1,0 +1,1987 @@@
-               MODE_PANNING,
 +/*
 + * ***** 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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 + *
 + * The Original Code is Copyright (C) 2007 Blender Foundation.
 + * All rights reserved.
 + *
 + * 
 + * Contributor(s): Joseph Eagar, Joshua Leung
 + *
 + * ***** END GPL LICENSE BLOCK *****
 + */
 +
 +#include <float.h>
 +#define _USE_MATH_DEFINES
 +#include <math.h>
 +#include <string.h>
 +#include <ctype.h>
 +#include <stdio.h>
 +
 +#include "DNA_ID.h"
 +#include "DNA_screen_types.h"
 +#include "DNA_scene_types.h"
 +#include "DNA_userdef_types.h"
 +#include "DNA_object_types.h"
 +
 +#include "MEM_guardedalloc.h"
 +
 +#include "PIL_time.h"
 +
 +#include "BLI_utildefines.h"
 +#include "BLI_blenlib.h"
 +#include "BLI_dynstr.h" /*for WM_operator_pystring */
 +#include "BLI_editVert.h"
 +#include "BLI_array.h"
 +#include "BLI_ghash.h"
 +#include "BLI_memarena.h"
 +#include "BLI_mempool.h"
 +#include "BLI_math.h"
 +#include "BLI_rand.h"
 +#include "BLI_kdopbvh.h"
 +#include "BLI_smallhash.h"
 +#include "BLI_scanfill.h"
 +
 +#include "BKE_DerivedMesh.h"
 +#include "BKE_blender.h"
 +#include "BKE_context.h"
 +#include "BKE_depsgraph.h"
 +#include "BKE_scene.h"
 +#include "BKE_mesh.h"
 +#include "BKE_tessmesh.h"
 +#include "BKE_depsgraph.h"
 +
 +#include "BIF_gl.h"
 +#include "BIF_glutil.h" /* for paint cursor */
 +
 +#include "IMB_imbuf_types.h"
 +
 +#include "ED_screen.h"
 +#include "ED_space_api.h"
 +#include "ED_view3d.h"
 +#include "ED_mesh.h"
 +
 +#include "RNA_access.h"
 +#include "RNA_define.h"
 +
 +#include "UI_interface.h"
 +
 +#include "WM_api.h"
 +#include "WM_types.h"
 +
 +#include "mesh_intern.h"
 +#include "editbmesh_bvh.h"
 +
 +/* this code here is kindof messy. . .I might need to eventually rework it - joeedh*/
 +
 +#define MAXGROUP      30
 +#define KMAXDIST      10      /*max mouse distance from edge before not detecting it*/
 +
 +/* knifetool operator */
 +typedef struct KnifeVert {
 +      BMVert *v; /*non-NULL if this is an original vert*/
 +      ListBase edges;
 +
 +      float co[3], cageco[3], sco[3]; /*sco is screen coordinates for cageco*/
 +      short flag, draw, isface, inspace;
 +} KnifeVert;
 +
 +typedef struct Ref {
 +      struct Ref *next, *prev;
 +      void *ref;
 +} Ref;
 +
 +typedef struct KnifeEdge {
 +      KnifeVert *v1, *v2;
 +      BMFace *basef; /*face to restrict face fill to*/
 +      ListBase faces;
 +      int draw;
 +      
 +      BMEdge *e, *oe; /*non-NULL if this is an original edge*/
 +} KnifeEdge;
 +
 +typedef struct BMEdgeHit {
 +      KnifeEdge *kfe;
 +      float hit[3], cagehit[3];
 +      float realhit[3]; /*used in midpoint mode*/
 +      float schit[3];
 +      float l; /*lambda along cut line*/
 +      float perc; /*lambda along hit line*/
 +      KnifeVert *v; //set if snapped to a vert
 +      BMFace *f;
 +} BMEdgeHit;
 +
 +/* struct for properties used while drawing */
 +typedef struct knifetool_opdata {
 +      ARegion *ar;            /* region that knifetool was activated in */
 +      void *draw_handle;      /* for drawing preview loop */
 +      ViewContext vc;
 +      bContext *C;
 +      
 +      Object *ob;
 +      BMEditMesh *em;
 +      
 +      MemArena *arena;
 +
 +      GHash *origvertmap;
 +      GHash *origedgemap;
 +      
 +      GHash *kedgefacemap;
 +      
 +      BMBVHTree *bmbvh;
 +
 +      BLI_mempool *kverts;
 +      BLI_mempool *kedges;
 +      
 +      float vthresh;
 +      float ethresh;
 +      
 +      float vertco[3], vertcage[3];
 +      float prevco[3], prevcage[3];
 +      
 +      /*used for drag-cutting*/
 +      BMEdgeHit *linehits;
 +      int totlinehit;
 +      
 +      /*if curedge is NULL, attach to curvert;
 +        if curvert is NULL, attach to curbmface,
 +        otherwise create null vert*/
 +      KnifeEdge *curedge, *prevedge;
 +      KnifeVert *curvert, *prevvert;
 +      BMFace *curbmface, *prevbmface;
 +
 +      int totkedge, totkvert, cutnr;
 +      
 +      BLI_mempool *refs;
 +      
 +      float projmat[4][4];
 +      int is_ortho;
 +      float clipsta, clipend;
 +      
 +      enum {
 +              MODE_IDLE,
 +              MODE_DRAGGING,
 +              MODE_CONNECT,
++              MODE_PANNING
 +      } mode;
 +      
 +      int snap_midpoints, prevmode, extend;
 +      int ignore_edge_snapping, ignore_vert_snapping;
 +      
 +      int is_space, prev_is_space; /*1 if current cut location, vertco, isn't on the mesh*/
 +      float (*cagecos)[3];
 +} knifetool_opdata;
 +
 +static ListBase *knife_get_face_kedges(knifetool_opdata *kcd, BMFace *f);
 +
 +static void knife_input_ray_cast(knifetool_opdata *kcd, const int mval_i[2],
 +                                 float r_origin[3], float r_ray[3]);
 +
 +static void knife_project_v3(knifetool_opdata *kcd, float co[3], float sco[3])
 +{
 +      if (kcd->is_ortho) {
 +              mul_v3_m4v3(sco, kcd->projmat, co);
 +              
 +              sco[0] = (float)(kcd->ar->winx/2.0f)+(kcd->ar->winx/2.0f)*sco[0];
 +              sco[1] = (float)(kcd->ar->winy/2.0f)+(kcd->ar->winy/2.0f)*sco[1];
 +      }
 +      else {
 +              ED_view3d_project_float(kcd->ar, co, sco, kcd->projmat);
 +      }
 +}
 +
 +static KnifeEdge *new_knife_edge(knifetool_opdata *kcd)
 +{
 +      kcd->totkedge++;
 +      return BLI_mempool_calloc(kcd->kedges);
 +}
 +
 +static KnifeVert *new_knife_vert(knifetool_opdata *kcd, float *co, float *cageco)
 +{
 +      KnifeVert *kfv = BLI_mempool_calloc(kcd->kverts);
 +      
 +      kcd->totkvert++;
 +      
 +      copy_v3_v3(kfv->co, co);
 +      copy_v3_v3(kfv->cageco, cageco);
 +      copy_v3_v3(kfv->sco, co);
 +
 +      knife_project_v3(kcd, kfv->co, kfv->sco);
 +
 +      return kfv;
 +}
 +
 +/*get a KnifeVert wrapper for an existing BMVert*/
 +static KnifeVert *get_bm_knife_vert(knifetool_opdata *kcd, BMVert *v)
 +{
 +      KnifeVert *kfv = BLI_ghash_lookup(kcd->origvertmap, v);
 +      
 +      if (!kfv) {
 +              kfv = new_knife_vert(kcd, v->co, kcd->cagecos[BM_GetIndex(v)]);
 +              kfv->v = v;
 +              BLI_ghash_insert(kcd->origvertmap, v, kfv);
 +      }
 +      
 +      return kfv;
 +}
 +
 +/*get a KnifeEdge wrapper for an existing BMEdge*/
 +static KnifeEdge *get_bm_knife_edge(knifetool_opdata *kcd, BMEdge *e)
 +{
 +      KnifeEdge *kfe = BLI_ghash_lookup(kcd->origedgemap, e);
 +      if (!kfe) {
 +              Ref *ref;
 +              BMIter iter;
 +              BMFace *f;
 +              
 +              kfe = new_knife_edge(kcd);
 +              kfe->e = e;
 +              kfe->v1 = get_bm_knife_vert(kcd, e->v1);
 +              kfe->v2 = get_bm_knife_vert(kcd, e->v2);
 +              
 +              ref = BLI_mempool_calloc(kcd->refs);
 +              ref->ref = kfe;
 +              BLI_addtail(&kfe->v1->edges, ref);
 +
 +              ref = BLI_mempool_calloc(kcd->refs);
 +              ref->ref = kfe;
 +              BLI_addtail(&kfe->v2->edges, ref);
 +              
 +              BLI_ghash_insert(kcd->origedgemap, e, kfe);
 +              
 +              BM_ITER(f, &iter, kcd->em->bm, BM_FACES_OF_EDGE, e) {
 +                      ref = BLI_mempool_calloc(kcd->refs);
 +                      ref->ref = f;
 +                      BLI_addtail(&kfe->faces, ref);
 +                      
 +                      /*ensures the kedges lst for this f is initialized,
 +                        it automatically adds kfe by itself*/
 +                      knife_get_face_kedges(kcd, f);
 +              }
 +      }
 +      
 +      return kfe;
 +}
 +
 +static void knife_start_cut(knifetool_opdata *kcd)
 +{
 +      kcd->prevedge = kcd->curedge;
 +      kcd->prevvert = kcd->curvert;
 +      kcd->prevbmface = kcd->curbmface;
 +      kcd->cutnr++;
 +      kcd->prev_is_space = kcd->is_space;
 +      kcd->is_space = 0;
 +      
 +      copy_v3_v3(kcd->prevco, kcd->vertco);
 +      copy_v3_v3(kcd->prevcage, kcd->vertcage);
 +}
 +
 +static Ref *find_ref(ListBase *lb, void *ref)
 +{
 +      Ref *ref1;
 +      
 +      for (ref1=lb->first; ref1; ref1=ref1->next) {
 +              if (ref1->ref == ref)
 +                      return ref1;
 +      }
 +      
 +      return NULL;
 +}
 +
 +static ListBase *knife_get_face_kedges(knifetool_opdata *kcd, BMFace *f)
 +{
 +      ListBase *lst = BLI_ghash_lookup(kcd->kedgefacemap, f);
 +      
 +      if (!lst) {
 +              BMIter iter;
 +              BMEdge *e;
 +              
 +              lst = BLI_memarena_alloc(kcd->arena, sizeof(ListBase));
 +              lst->first = lst->last = NULL;
 +              
 +              BM_ITER(e, &iter, kcd->em->bm, BM_EDGES_OF_FACE, f) {
 +                      Ref *ref = BLI_mempool_calloc(kcd->refs);
 +                      ref->ref = get_bm_knife_edge(kcd, e);
 +                      BLI_addtail(lst, ref);
 +              }
 +              
 +              BLI_ghash_insert(kcd->kedgefacemap, f, lst);
 +      }
 +      
 +      return lst;
 +}
 +
 +/*finds the proper face to restrict face fill to*/
 +static void knife_find_basef(knifetool_opdata *kcd, KnifeEdge *kfe)
 +{
 +      if (!kfe->basef) {
 +              Ref *r1, *r2, *r3, *r4;
 +              
 +              if (kfe->v1->isface || kfe->v2->isface) {
 +                      if (kfe->v2->isface)
 +                              kfe->basef = kcd->curbmface;
 +                      else 
 +                              kfe->basef = kcd->prevbmface;
 +              } else {                
 +                      for (r1=kfe->v1->edges.first; r1 && !kfe->basef; r1=r1->next) {
 +                              KnifeEdge *ke1 = r1->ref;
 +                              for (r2=ke1->faces.first; r2 && !kfe->basef; r2=r2->next) {
 +                                      for (r3=kfe->v2->edges.first; r3 && !kfe->basef; r3=r3->next) {
 +                                              KnifeEdge *ke2 = r3->ref;
 +                                      
 +                                              for (r4=ke2->faces.first; r4 && !kfe->basef; r4=r4->next) {
 +                                                      if (r2->ref == r4->ref) {
 +                                                              kfe->basef = r2->ref;
 +                                                      }
 +                                              }       
 +                                      }
 +                              }
 +                      }
 +              }
 +              /*ok, at this point kfe->basef should be set if any valid possibility
 +                exists*/
 +      }
 +}
 +
 +static KnifeVert *knife_split_edge(knifetool_opdata *kcd, KnifeEdge *kfe, float co[3], KnifeEdge **newkfe_out)
 +{
 +      KnifeEdge *newkfe = new_knife_edge(kcd);
 +      ListBase *lst;
 +      Ref *ref;
 +      float perc, cageco[3];
 +      
 +      perc = len_v3v3(co, kfe->v1->co) / len_v3v3(kfe->v1->co, kfe->v2->co);
 +      interp_v3_v3v3(cageco, kfe->v1->cageco, kfe->v2->cageco, perc);
 +      
 +      newkfe->v1 = kfe->v1;
 +      newkfe->v2 = new_knife_vert(kcd, co, cageco);
 +      newkfe->v2->draw = 1;
 +      newkfe->basef = kfe->basef;
 +      
 +      ref = find_ref(&kfe->v1->edges, kfe);
 +      BLI_remlink(&kfe->v1->edges, ref);
 +      
 +      kfe->v1 = newkfe->v2;
 +      BLI_addtail(&kfe->v1->edges, ref);
 +      
 +      for (ref=kfe->faces.first; ref; ref=ref->next) {
 +              Ref *ref2 = BLI_mempool_calloc(kcd->refs);
 +              
 +              /*add kedge ref to bm faces*/
 +              lst = knife_get_face_kedges(kcd, ref->ref);
 +              ref2->ref = newkfe;
 +              BLI_addtail(lst, ref2);
 +
 +              ref2 = BLI_mempool_calloc(kcd->refs);
 +              ref2->ref = ref->ref;
 +              BLI_addtail(&newkfe->faces, ref2);
 +      }
 +
 +      ref = BLI_mempool_calloc(kcd->refs);
 +      ref->ref = newkfe;
 +      BLI_addtail(&newkfe->v1->edges, ref);
 +
 +      ref = BLI_mempool_calloc(kcd->refs);
 +      ref->ref = newkfe;
 +      BLI_addtail(&newkfe->v2->edges, ref);
 +      
 +      newkfe->draw = kfe->draw;
 +      newkfe->e = kfe->e;
 +      
 +      *newkfe_out = newkfe;
 +                      
 +      return newkfe->v2;
 +}
 +
 +static void knife_edge_append_face(knifetool_opdata *kcd, KnifeEdge *kfe, BMFace *f)
 +{
 +      ListBase *lst = knife_get_face_kedges(kcd, f);
 +      Ref *ref = BLI_mempool_calloc(kcd->refs);
 +      
 +      ref->ref = kfe;
 +      BLI_addtail(lst, ref);
 +      
 +      ref = BLI_mempool_calloc(kcd->refs);
 +      ref->ref = f;
 +      BLI_addtail(&kfe->faces, ref);
 +}
 +
 +#if 0
 +static void knife_copy_edge_facelist(knifetool_opdata *kcd, KnifeEdge *dest, KnifeEdge *source) 
 +{
 +      Ref *ref, *ref2;
 +      
 +      for (ref2 = source->faces.first; ref2; ref2=ref2->next) {
 +              ListBase *lst = knife_get_face_kedges(kcd, ref2->ref);
 +              
 +              /*add new edge to face knife edge list*/
 +              ref = BLI_mempool_calloc(kcd->refs);
 +              ref->ref = dest;
 +              BLI_addtail(lst, ref);
 +              
 +              /*add face to new edge's face list*/
 +              ref = BLI_mempool_calloc(kcd->refs);
 +              ref->ref = ref2->ref;
 +              BLI_addtail(&dest->faces, ref);
 +      }
 +}
 +#endif
 +
 +static void knife_add_single_cut(knifetool_opdata *kcd)
 +{
 +      KnifeEdge *kfe = new_knife_edge(kcd), *kfe2 = NULL, *kfe3 = NULL;
 +      Ref *ref;
 +      
 +      if (kcd->prevvert && kcd->prevvert == kcd->curvert)
 +              return;
 +      if (kcd->prevedge && kcd->prevedge == kcd->curedge)
 +              return;
 +      
 +      kfe->draw = 1;
 +
 +      if (kcd->prevvert) {
 +              kfe->v1 = kcd->prevvert;
 +      } else if (kcd->prevedge) {
 +              kfe->v1 = knife_split_edge(kcd, kcd->prevedge, kcd->prevco, &kfe2);
 +      } else {
 +              kfe->v1 = new_knife_vert(kcd, kcd->prevco, kcd->prevco);
 +              kfe->v1->draw = kfe->draw = !kcd->prev_is_space;
 +              kfe->v1->inspace = kcd->prev_is_space;
 +              kfe->draw = !kcd->prev_is_space;
 +              kfe->v1->isface = 1;
 +      }
 +      
 +      if (kcd->curvert) {
 +              kfe->v2 = kcd->curvert;
 +      } else if (kcd->curedge) {
 +              kfe->v2 = knife_split_edge(kcd, kcd->curedge, kcd->vertco, &kfe3);
 +      
 +              kcd->curvert = kfe->v2;
 +      } else {
 +              kfe->v2 = new_knife_vert(kcd, kcd->vertco, kcd->vertco);
 +              kfe->v2->draw = !kcd->is_space;
 +              kfe->v2->isface = 1;
 +              kfe->v2->inspace = kcd->is_space;
 +              
 +              if (kcd->is_space)
 +                      kfe->draw = 0;
 +
 +              kcd->curvert = kfe->v2;
 +      }
 +      
 +      knife_find_basef(kcd, kfe);
 +      
 +      ref = BLI_mempool_calloc(kcd->refs);
 +      ref->ref = kfe; 
 +      BLI_addtail(&kfe->v1->edges, ref);
 +
 +      ref = BLI_mempool_calloc(kcd->refs);
 +      ref->ref = kfe;
 +      BLI_addtail(&kfe->v2->edges, ref);      
 +      
 +      if (kfe->basef && !find_ref(&kfe->faces, kfe->basef))
 +              knife_edge_append_face(kcd, kfe, kfe->basef);
 +
 +      /*sanity check to make sure we're in the right edge/face lists*/
 +      if (kcd->curbmface) {
 +              if (!find_ref(&kfe->faces, kcd->curbmface)) {
 +                      knife_edge_append_face(kcd, kfe, kcd->curbmface);
 +              }
 +
 +              if (kcd->prevbmface && kcd->prevbmface != kcd->curbmface) {
 +                      if (!find_ref(&kfe->faces, kcd->prevbmface)) {
 +                              knife_edge_append_face(kcd, kfe, kcd->prevbmface);
 +                      }
 +              }
 +      }
 +              
 +      /*set up for next cut*/
 +      kcd->prevbmface = kcd->curbmface;
 +      kcd->prevvert = kcd->curvert;
 +      kcd->prevedge = kcd->curedge;
 +      copy_v3_v3(kcd->prevco, kcd->vertco);
 +      copy_v3_v3(kcd->prevcage, kcd->vertcage);
 +      kcd->prev_is_space = kcd->is_space;
 +}
 +
 +static int verge_linehit(const void *vlh1, const void *vlh2)
 +{
 +      const BMEdgeHit *lh1=vlh1, *lh2=vlh2;
 +
 +      if (lh1->l < lh2->l) return -1;
 +      else if (lh1->l > lh2->l) return 1;
 +      else return 0;
 +}
 +
 +static void knife_add_cut(knifetool_opdata *kcd)
 +{
 +      /*BMEditMesh *em = kcd->em;*/ /*UNUSED*/
 +      knifetool_opdata oldkcd = *kcd;
 +      
 +      if (kcd->linehits) {
 +              BMEdgeHit *lh, *lastlh, *firstlh;
 +              int i;
 +              
 +              qsort(kcd->linehits, kcd->totlinehit, sizeof(BMEdgeHit), verge_linehit);
 +              
 +              lh = kcd->linehits;
 +              lastlh = firstlh = NULL;
 +              for (i=0; i<kcd->totlinehit; i++, (lastlh=lh), lh++) {
 +                      BMFace *f = lastlh ? lastlh->f : lh->f;
 +                      
 +                      if (lastlh && len_v3v3(lastlh->hit, lh->hit) == 0.0f) {
 +                              if (!firstlh)
 +                                      firstlh = lastlh;
 +                              continue;
 +                      } else if (lastlh && firstlh) {
 +                              if (firstlh->v || lastlh->v) {
 +                                      KnifeVert *kfv = firstlh->v ? firstlh->v : lastlh->v;
 +                                      
 +                                      kcd->prevvert = kfv;
 +                                      copy_v3_v3(kcd->prevco, firstlh->hit);                          
 +                                      copy_v3_v3(kcd->prevcage, firstlh->cagehit);
 +                                      kcd->prevedge = NULL;
 +                                      kcd->prevbmface = f;
 +                              }
 +                              lastlh = firstlh = NULL;
 +                      }
 +                      
 +                      if (len_v3v3(kcd->prevcage, lh->realhit) < FLT_EPSILON*80)
 +                              continue;
 +                      if (len_v3v3(kcd->vertcage, lh->realhit) < FLT_EPSILON*80)
 +                              continue;
 +                      
 +                      if (kcd->prev_is_space || kcd->is_space) {
 +                              kcd->prev_is_space = kcd->is_space = 0;
 +                              copy_v3_v3(kcd->prevco, lh->hit);
 +                              copy_v3_v3(kcd->prevcage, lh->cagehit);
 +                              kcd->prevedge = lh->kfe;
 +                              kcd->curbmface = lh->f;
 +                              continue;
 +                      }                       
 +                      
 +                      kcd->is_space = 0;
 +                      kcd->curedge = lh->kfe;
 +                      kcd->curbmface = lh->f;
 +                      kcd->curvert = lh->v;
 +                      copy_v3_v3(kcd->vertco, lh->hit);
 +                      copy_v3_v3(kcd->vertcage, lh->cagehit);
 +
 +                      knife_add_single_cut(kcd);
 +              }
 +              
 +              kcd->curbmface = oldkcd.curbmface;
 +              kcd->curvert = oldkcd.curvert;
 +              kcd->curedge = oldkcd.curedge;
 +              kcd->is_space = oldkcd.is_space;
 +              copy_v3_v3(kcd->vertco, oldkcd.vertco);
 +              copy_v3_v3(kcd->vertcage, oldkcd.vertcage);
 +              
 +              knife_add_single_cut(kcd);
 +              
 +              MEM_freeN(kcd->linehits);
 +              kcd->linehits = NULL;
 +              kcd->totlinehit = 0;
 +      } else {
 +              knife_add_single_cut(kcd);
 +      }
 +}
 +
 +static void knife_finish_cut(knifetool_opdata *UNUSED(kcd))
 +{
 +
 +}
 +
 +/* modal loop selection drawing callback */
 +static void knifetool_draw(const bContext *UNUSED(C), ARegion *UNUSED(ar), void *arg)
 +{
 +      knifetool_opdata *kcd = arg;
 +      
 +      glDisable(GL_DEPTH_TEST);
 +      
 +      glPolygonOffset(1.0f, 1.0f);
 +      
 +      glPushMatrix();
 +      glMultMatrixf(kcd->ob->obmat);
 +      
 +      if (kcd->mode == MODE_DRAGGING) {
 +              glColor3f(0.1, 0.1, 0.1);
 +              glLineWidth(2.0);
 +              
 +              glBegin(GL_LINES);
 +              glVertex3fv(kcd->prevcage);     
 +              glVertex3fv(kcd->vertcage);
 +              glEnd();
 +              
 +              glLineWidth(1.0);       
 +      }
 +      
 +      if (kcd->curedge) {
 +              glColor3f(0.5, 0.3, 0.15);
 +              glLineWidth(2.0);
 +              
 +              glBegin(GL_LINES);
 +              glVertex3fv(kcd->curedge->v1->cageco);  
 +              glVertex3fv(kcd->curedge->v2->cageco);
 +              glEnd();
 +              
 +              glLineWidth(1.0);
 +      } else if (kcd->curvert) {
 +              glColor3f(0.8, 0.2, 0.1);
 +              glPointSize(11);
 +              
 +              glBegin(GL_POINTS);
 +              glVertex3fv(kcd->vertcage);
 +              glEnd();
 +      }
 +      
 +      if (kcd->curbmface) {           
 +              glColor3f(0.1, 0.8, 0.05);
 +              glPointSize(9);
 +              
 +              glBegin(GL_POINTS);
 +              glVertex3fv(kcd->vertcage);
 +              glEnd();
 +      }
 +      
 +      if (kcd->totlinehit > 0) {
 +              BMEdgeHit *lh;
 +              int i;
 +              
 +              glEnable(GL_BLEND);
 +              glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
 +              
 +              /*draw any snapped verts first*/
 +              glColor4f(0.8, 0.2, 0.1, 0.4);
 +              glPointSize(11);
 +              glBegin(GL_POINTS);
 +              lh = kcd->linehits;
 +              for (i=0; i<kcd->totlinehit; i++, lh++) {
 +                      float sv1[3], sv2[3];
 +                      
 +                      knife_project_v3(kcd, lh->kfe->v1->cageco, sv1);
 +                      knife_project_v3(kcd, lh->kfe->v2->cageco, sv2);
 +                      knife_project_v3(kcd, lh->cagehit, lh->schit);
 +                      
 +                      if (len_v2v2(lh->schit, sv1) < kcd->vthresh/4) {
 +                              copy_v3_v3(lh->cagehit, lh->kfe->v1->cageco);
 +                              glVertex3fv(lh->cagehit);
 +                              lh->v = lh->kfe->v1;
 +                      } else if (len_v2v2(lh->schit, sv2) < kcd->vthresh/4) {
 +                              copy_v3_v3(lh->cagehit, lh->kfe->v2->cageco);
 +                              glVertex3fv(lh->cagehit);
 +                              lh->v = lh->kfe->v2;
 +                      }
 +              }
 +              glEnd();
 +              
 +              /*now draw the rest*/
 +              glColor4f(0.1, 0.8, 0.05, 0.4);
 +              glPointSize(7);
 +              glBegin(GL_POINTS);
 +              lh = kcd->linehits;
 +              for (i=0; i<kcd->totlinehit; i++, lh++) {
 +                      glVertex3fv(lh->cagehit);
 +              }
 +              glEnd();
 +              glDisable(GL_BLEND);
 +      }
 +      
 +      if (kcd->totkedge > 0) {
 +              BLI_mempool_iter iter;
 +              KnifeEdge *kfe;
 +              
 +              glLineWidth(1.0);
 +              glBegin(GL_LINES);
 +
 +              BLI_mempool_iternew(kcd->kedges, &iter);
 +              for (kfe=BLI_mempool_iterstep(&iter); kfe; kfe=BLI_mempool_iterstep(&iter)) {
 +                      if (!kfe->draw)
 +                              continue;
 +                              
 +                      glColor3f(0.2, 0.2, 0.2);
 +                      
 +                      glVertex3fv(kfe->v1->cageco);
 +                      glVertex3fv(kfe->v2->cageco);
 +              }
 +              
 +              glEnd();                
 +              glLineWidth(1.0);       
 +      }
 +
 +      if (kcd->totkvert > 0) {
 +              BLI_mempool_iter iter;
 +              KnifeVert *kfv;
 +              
 +              glPointSize(5.0);
 +                              
 +              glBegin(GL_POINTS);
 +              BLI_mempool_iternew(kcd->kverts, &iter);
 +              for (kfv=BLI_mempool_iterstep(&iter); kfv; kfv=BLI_mempool_iterstep(&iter)) {
 +                      if (!kfv->draw)
 +                              continue;
 +                              
 +                      glColor3f(0.6, 0.1, 0.2);
 +                      
 +                      glVertex3fv(kfv->cageco);
 +              }
 +              
 +              glEnd();                
 +      }
 +
 +      glPopMatrix();
 +      glEnable(GL_DEPTH_TEST);
 +}
 +
 +static int kfe_vert_in_edge(KnifeEdge *e, KnifeVert *v) {
 +      return e->v1 == v || e->v2 == v;
 +}
 +
 +static int point_on_line(float p[3], float v1[3], float v2[3])
 +{
 +      float d = dist_to_line_segment_v3(p, v1, v2);
 +      if (d < 0.01) {
 +              d = len_v3v3(v1, v2);
 +              if (d == 0.0)
 +                      return 0;
 +              
 +              d = len_v3v3(p, v1) / d;
 +              
 +              if (d >= -FLT_EPSILON*10 || d <= 1.0+FLT_EPSILON*10)
 +                      return 1;
 +      }
 +      
 +      return 0;
 +}
 +
 +static BMEdgeHit *knife_edge_tri_isect(knifetool_opdata *kcd, BMBVHTree *bmtree, float v1[3], 
 +                              float v2[3], float v3[3], SmallHash *ehash, bglMats *mats, int *count)
 +{
 +      BVHTree *tree2 = BLI_bvhtree_new(3, FLT_EPSILON*4, 8, 8), *tree = BMBVH_BVHTree(bmtree);
 +      BMEdgeHit *edges = NULL;
 +      BLI_array_declare(edges);
 +      BVHTreeOverlap *results, *result;
 +      BMLoop **ls;
 +      float cos[9], uv[3], lambda, depsilon;
 +      unsigned int tot=0;
 +      int i, j;
 +      
 +      copy_v3_v3(cos, v1);
 +      copy_v3_v3(cos+3, v2);
 +      copy_v3_v3(cos+6, v3);
 +      
 +      /* for comparing distances, error of intersection depends on triangle scale */
 +      depsilon = 50*FLT_EPSILON*MAX3(len_v3v3(v1, v2), len_v3v3(v1, v3), len_v3v3(v2, v3));
 +
 +      BLI_bvhtree_insert(tree2, 0, cos, 3);
 +      BLI_bvhtree_balance(tree2);
 +      
 +      result = results = BLI_bvhtree_overlap(tree, tree2, &tot);
 +      
 +      for (i=0; i<tot; i++, result++) {
 +              float p[3];
 +              
 +              ls = (BMLoop**)kcd->em->looptris[result->indexA];
 +              
 +              for (j=0; j<3; j++) {
 +                      BMLoop *l1 = ls[j];
 +                      BMFace *hitf;
 +                      ListBase *lst = knife_get_face_kedges(kcd, l1->f);
 +                      Ref *ref;
 +                      
 +                      for (ref=lst->first; ref; ref=ref->next) {                      
 +                              KnifeEdge *kfe = ref->ref;
 +                              
 +                              //if (kfe == kcd->curedge || kfe== kcd->prevedge)
 +                              //      continue;
 +                              
 +                              if (isect_line_tri_v3(kfe->v1->cageco, kfe->v2->cageco, v1, v2, v3, &lambda, uv)) {
 +                                      float no[3], view[3], sp[3];
 +                                      
 +                                      interp_v3_v3v3(p, kfe->v1->cageco, kfe->v2->cageco, lambda);
 +                                      
 +                                      if (kcd->curvert && len_v3v3(kcd->curvert->cageco, p) < depsilon)
 +                                              continue;
 +                                      if (kcd->prevvert && len_v3v3(kcd->prevvert->cageco, p) < depsilon)
 +                                              continue;
 +                                      if (len_v3v3(kcd->prevcage, p) < depsilon || len_v3v3(kcd->vertcage, p) < depsilon)
 +                                              continue;
 +                                      
 +                                      /*check if this point is visible in the viewport*/
 +                                      knife_project_v3(kcd, p, sp);
 +                                      view3d_unproject(mats, view, sp[0], sp[1], 0.0f);
 +                                      mul_m4_v3(kcd->ob->imat, view);
 +
 +                                      sub_v3_v3(view, p);
 +                                      normalize_v3(view);
 +      
 +                                      copy_v3_v3(no, view);
 +                                      mul_v3_fl(no, 0.003);
 +                                      
 +                                      /*go towards view a bit*/
 +                                      add_v3_v3(p, no);
 +                                      
 +                                      /*ray cast*/
 +                                      hitf = BMBVH_RayCast(bmtree, p, no, NULL, NULL);
 +                                      
 +                                      /*ok, if visible add the new point*/
 +                                      if (!hitf && !BLI_smallhash_haskey(ehash, (intptr_t)kfe)) {
 +                                              BMEdgeHit hit;
 +                                              
 +                                              if (len_v3v3(p, kcd->vertco) < depsilon || len_v3v3(p, kcd->prevco) < depsilon)
 +                                                      continue;
 +                                              
 +                                              hit.kfe = kfe;
 +                                              hit.v = NULL;
 +                                              
 +                                              knife_find_basef(kcd, kfe);
 +                                              hit.f = kfe->basef;
 +                                              hit.perc = len_v3v3(p, kfe->v1->cageco) / len_v3v3(kfe->v1->cageco, kfe->v2->cageco);
 +                                              copy_v3_v3(hit.cagehit, p);
 +                                              
 +                                              interp_v3_v3v3(p, kfe->v1->co, kfe->v2->co, hit.perc);
 +                                              copy_v3_v3(hit.realhit, p);
 +                                              
 +                                              if (kcd->snap_midpoints) {
 +                                                      float perc = hit.perc;
 +
 +                                                      /* select the closest from the edge endpoints or the midpoint */
 +                                                      if (perc < 0.25f) {
 +                                                              perc = 0.0f;
 +                                                      }
 +                                                      else if (perc < 0.75f) {
 +                                                              perc = 0.5f;
 +                                                      }
 +                                                      else {
 +                                                              perc = 1.0f;
 +                                                      }
 +                                                      
 +                                                      interp_v3_v3v3(hit.hit, kfe->v1->co, kfe->v2->co, perc);
 +                                                      interp_v3_v3v3(hit.cagehit, kfe->v1->cageco, kfe->v2->cageco, perc);
 +                                              } else {
 +                                                      copy_v3_v3(hit.hit, p);
 +                                              }
 +                                              knife_project_v3(kcd, hit.cagehit, hit.schit);
 +                                              
 +                                              BLI_array_append(edges, hit);
 +                                              BLI_smallhash_insert(ehash, (intptr_t)kfe, NULL);
 +                                      }
 +                              }
 +                      }
 +              }
 +      }
 +      
 +      if (results)
 +              MEM_freeN(results);
 +      
 +      BLI_bvhtree_free(tree2);
 +      *count = BLI_array_count(edges);
 +      
 +      return edges;
 +}
 +
 +static void knife_bgl_get_mats(knifetool_opdata *UNUSED(kcd), bglMats *mats)
 +{
 +      bgl_get_mats(mats);
 +      //copy_m4_m4(mats->modelview, kcd->vc.rv3d->viewmat);
 +      //copy_m4_m4(mats->projection, kcd->vc.rv3d->winmat);
 +}
 +
 +/*finds (visible) edges that intersects the current screen drag line*/
 +static void knife_find_line_hits(knifetool_opdata *kcd)
 +{
 +      bglMats mats;
 +      BMEdgeHit *e1, *e2;
 +      SmallHash hash, *ehash = &hash;
 +      float v1[3], v2[3], v3[3], v4[4], s1[3], s2[3];
 +      int i, c1, c2;
 +              
 +      knife_bgl_get_mats(kcd, &mats);
 +      
 +      if (kcd->linehits) {
 +              MEM_freeN(kcd->linehits);
 +              kcd->linehits = NULL;
 +              kcd->totlinehit = 0;
 +      }
 +      
 +      copy_v3_v3(v1, kcd->prevcage);
 +      copy_v3_v3(v2, kcd->vertcage);
 +      
 +      /*project screen line's 3d coordinates back into 2d*/
 +      knife_project_v3(kcd, v1, s1);
 +      knife_project_v3(kcd, v2, s2);
 +      
 +      if (len_v2v2(s1, s2) < 1)
 +              return; 
 +
 +      /*unproject screen line*/
 +      ED_view3d_win_to_segment_clip(kcd->ar, kcd->vc.v3d, s1, v1, v3);
 +      ED_view3d_win_to_segment_clip(kcd->ar, kcd->vc.v3d, s2, v2, v4);
 +              
 +      mul_m4_v3(kcd->ob->imat, v1);
 +      mul_m4_v3(kcd->ob->imat, v2);
 +      mul_m4_v3(kcd->ob->imat, v3);
 +      mul_m4_v3(kcd->ob->imat, v4);
 +      
 +      BLI_smallhash_init(ehash);
 +      
 +      /*test two triangles of sceen line's plane*/
 +      e1 = knife_edge_tri_isect(kcd, kcd->bmbvh, v1, v2, v3, ehash, &mats, &c1);
 +      e2 = knife_edge_tri_isect(kcd, kcd->bmbvh, v2, v3, v4, ehash, &mats, &c2);
 +      if (c1 && c2) {
 +              e1 = MEM_reallocN(e1, sizeof(BMEdgeHit)*(c1+c2));
 +              memcpy(e1+c1, e2, sizeof(BMEdgeHit)*c2);
 +              MEM_freeN(e2);
 +      } else if (c2) {
 +              e1 = e2;
 +      }
 +      
 +      kcd->linehits = e1;
 +      kcd->totlinehit = c1+c2;
 +
 +      /*find position along screen line, used for sorting*/
 +      for (i=0; i<kcd->totlinehit; i++) {
 +              BMEdgeHit *lh = e1+i;
 +              
 +              lh->l = len_v2v2(lh->schit, s1) / len_v2v2(s2, s1);
 +      }
 +      
 +      BLI_smallhash_release(ehash);
 +}
 +
 +static void knife_input_ray_cast(knifetool_opdata *kcd, const int mval_i[2],
 +                                 float r_origin[3], float r_ray[3])
 +{
 +      bglMats mats;
 +      float mval[2], imat[3][3];
 +
 +      knife_bgl_get_mats(kcd, &mats);
 +
 +      mval[0] = (float)mval_i[0];
 +      mval[1] = (float)mval_i[1];
 +
 +      /*unproject to find view ray*/
 +      view3d_unproject(&mats, r_origin, mval[0], mval[1], 0.0f);
 +
 +      if(kcd->is_ortho)
 +              negate_v3_v3(r_ray, kcd->vc.rv3d->viewinv[2]);
 +      else
 +              sub_v3_v3v3(r_ray, r_origin, kcd->vc.rv3d->viewinv[3]);
 +      normalize_v3(r_ray);
 +
 +      /*transform into object space*/
 +      invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
 +      copy_m3_m4(imat, kcd->ob->obmat);
 +      invert_m3(imat);
 +
 +      mul_m4_v3(kcd->ob->imat, r_origin);
 +      mul_m3_v3(imat, r_ray);
 +}
 +
 +
 +static BMFace *knife_find_closest_face(knifetool_opdata *kcd, float co[3], float cageco[3], int *is_space)
 +{
 +      BMFace *f;
 +      int dist = KMAXDIST; 
 +      float origin[3];
 +      float ray[3];
 +      
 +      /*unproject to find view ray*/
 +      knife_input_ray_cast(kcd, kcd->vc.mval, origin, ray);
 +      add_v3_v3v3(co, origin, ray);
 +
 +      f = BMBVH_RayCast(kcd->bmbvh, origin, ray, co, cageco);
 +      
 +      if (is_space)
 +              *is_space = !f; 
 +      
 +      if (!f) {
 +              /*try to use backbuffer selection method if ray casting failed*/
 +              f = EDBM_findnearestface(&kcd->vc, &dist);
 +              
 +              /* cheat for now; just put in the origin instead
 +               * of a true coordinate on the face.
 +               * This just puts a point 1.0f infront of the view. */
 +              add_v3_v3v3(co, origin, ray);
 +      }
 +      
 +      return f;
 +}
 +
 +/*find the 2d screen space density of vertices within a radius.  used to scale snapping
 +  distance for picking edges/verts.*/
 +static int knife_sample_screen_density(knifetool_opdata *kcd, float radius)
 +{
 +      BMFace *f;
 +      int is_space;
 +      float co[3], cageco[3], sco[3];
 +      
 +      f = knife_find_closest_face(kcd, co, cageco, &is_space);
 +      
 +      if (f && !is_space) {
 +              ListBase *lst;
 +              Ref *ref;
 +              float dis;
 +              int c = 0;
 +              
 +              knife_project_v3(kcd, cageco, sco);
 +              
 +              lst = knife_get_face_kedges(kcd, f);
 +              for (ref=lst->first; ref; ref=ref->next) {
 +                      KnifeEdge *kfe = ref->ref;
 +                      int i;
 +                      
 +                      for (i=0; i<2; i++) {
 +                              KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
 +                              
 +                              knife_project_v3(kcd, kfv->cageco, kfv->sco);
 +                              
 +                              dis = len_v2v2(kfv->sco, sco);
 +                              if (dis < radius) {
 +                                      if(kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
 +                                              float vec[3];
 +                                              
 +                                              copy_v3_v3(vec, kfv->cageco);
 +                                              mul_m4_v3(kcd->vc.obedit->obmat, vec);
 +                      
 +                                              if(ED_view3d_test_clipping(kcd->vc.rv3d, vec, 1)==0) {
 +                                                      c++;
 +                                              }
 +                                      } else {
 +                                              c++;
 +                                      }
 +                              }
 +                      }
 +              }
 +              
 +              return c;
 +      }
 +              
 +      return 0;
 +}
 +
 +/*returns snapping distance for edges/verts, scaled by the density of the
 +  surrounding mesh (in screen space)*/
 +static float knife_snap_size(knifetool_opdata *kcd, float maxsize)
 +{
 +      float density = (float)knife_sample_screen_density(kcd, maxsize*2.0f);
 +      
 +      density = MAX2(density, 1);
 +      
 +      return MIN2(maxsize / (density*0.5f), maxsize);
 +}
 +
 +/*p is closest point on edge to the mouse cursor*/
 +static KnifeEdge *knife_find_closest_edge(knifetool_opdata *kcd, float p[3], float cagep[3], BMFace **fptr, int *is_space)
 +{
 +      BMFace *f;
 +      float co[3], cageco[3], sco[3], maxdist = knife_snap_size(kcd, kcd->ethresh);
 +      
 +      if (kcd->ignore_vert_snapping)
 +              maxdist *= 0.5;
 +
 +      f = knife_find_closest_face(kcd, co, cageco, NULL);
 +      *is_space = !f;
 +      
 +      /*set p to co, in case we don't find anything, means a face cut*/
 +      copy_v3_v3(p, co);
 +      copy_v3_v3(cagep, cageco);
 +      
 +      kcd->curbmface = f;
 +      
 +      if (f) {
 +              KnifeEdge *cure = NULL;
 +              ListBase *lst;
 +              Ref *ref;
 +              float dis, curdis=FLT_MAX;
 +              
 +              knife_project_v3(kcd, cageco, sco);
 +              
 +              /*look through all edges associated with this face*/
 +              lst = knife_get_face_kedges(kcd, f);
 +              for (ref=lst->first; ref; ref=ref->next) {
 +                      KnifeEdge *kfe = ref->ref;
 +                      
 +                      /*project edge vertices into screen space*/
 +                      knife_project_v3(kcd, kfe->v1->cageco, kfe->v1->sco);
 +                      knife_project_v3(kcd, kfe->v2->cageco, kfe->v2->sco);
 +
 +                      dis = dist_to_line_segment_v2(sco, kfe->v1->sco, kfe->v2->sco);
 +                      if (dis < curdis && dis < maxdist) {
 +                              if(kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
 +                                      float labda= labda_PdistVL2Dfl(sco, kfe->v1->sco, kfe->v2->sco);
 +                                      float vec[3];
 +              
 +                                      vec[0]= kfe->v1->cageco[0] + labda*(kfe->v2->cageco[0] - kfe->v1->cageco[0]);
 +                                      vec[1]= kfe->v1->cageco[1] + labda*(kfe->v2->cageco[1] - kfe->v1->cageco[1]);
 +                                      vec[2]= kfe->v1->cageco[2] + labda*(kfe->v2->cageco[2] - kfe->v1->cageco[2]);
 +                                      mul_m4_v3(kcd->vc.obedit->obmat, vec);
 +              
 +                                      if(ED_view3d_test_clipping(kcd->vc.rv3d, vec, 1)==0) {
 +                                              cure = kfe;
 +                                              curdis = dis;
 +                                      }
 +                              } else {
 +                                      cure = kfe;
 +                                      curdis = dis;                           
 +                              }
 +                      }
 +              }
 +              
 +              if (fptr)
 +                      *fptr = f;
 +              
 +              if (cure && p) {
 +                      if (!kcd->ignore_edge_snapping || !(cure->e)) {
 +                              if (kcd->snap_midpoints) {
 +                                      mid_v3_v3v3(p, cure->v1->co, cure->v2->co);
 +                                      mid_v3_v3v3(cagep, cure->v1->cageco, cure->v2->cageco);
 +                              } else {
 +                                      float d;
 +                                      
 +                                      closest_to_line_segment_v3(cagep, cageco, cure->v1->cageco, cure->v2->cageco);
 +                                      d = len_v3v3(cagep, cure->v1->cageco) / len_v3v3(cure->v1->cageco, cure->v2->cageco);
 +                                      interp_v3_v3v3(p, cure->v1->co, cure->v2->co, d);
 +                              }
 +                      } else {
 +                              return NULL;
 +                      }
 +              }
 +              
 +              return cure;
 +      }
 +              
 +      if (fptr)
 +              *fptr = NULL;
 +      
 +      return NULL;
 +}
 +
 +/*find a vertex near the mouse cursor, if it exists*/
 +static KnifeVert *knife_find_closest_vert(knifetool_opdata *kcd, float p[3], float cagep[3], BMFace **fptr, int *is_space)
 +{
 +      BMFace *f;
 +      float co[3], cageco[3], sco[3], maxdist = knife_snap_size(kcd, kcd->vthresh);
 +      
 +      if (kcd->ignore_vert_snapping)
 +              maxdist *= 0.5;
 +      
 +      f = knife_find_closest_face(kcd, co, cageco, is_space);
 +      
 +      /*set p to co, in case we don't find anything, means a face cut*/
 +      copy_v3_v3(p, co);
 +      copy_v3_v3(cagep, p);
 +      kcd->curbmface = f;
 +      
 +      if (f) {
 +              ListBase *lst;
 +              Ref *ref;
 +              KnifeVert *curv = NULL;
 +              float dis, curdis=FLT_MAX;
 +              
 +              knife_project_v3(kcd, cageco, sco);
 +              
 +              lst = knife_get_face_kedges(kcd, f);
 +              for (ref=lst->first; ref; ref=ref->next) {
 +                      KnifeEdge *kfe = ref->ref;
 +                      int i;
 +                      
 +                      for (i=0; i<2; i++) {
 +                              KnifeVert *kfv = i ? kfe->v2 : kfe->v1;
 +                              
 +                              knife_project_v3(kcd, kfv->cageco, kfv->sco);
 +                              
 +                              dis = len_v2v2(kfv->sco, sco);
 +                              if (dis < curdis && dis < maxdist) {
 +                                      if(kcd->vc.rv3d->rflag & RV3D_CLIPPING) {
 +                                              float vec[3];
 +                                              
 +                                              copy_v3_v3(vec, kfv->cageco);
 +                                              mul_m4_v3(kcd->vc.obedit->obmat, vec);
 +                      
 +                                              if(ED_view3d_test_clipping(kcd->vc.rv3d, vec, 1)==0) {
 +                                                      curv = kfv;
 +                                                      curdis = dis;
 +                                              }
 +                                      } else {
 +                                              curv = kfv;
 +                                              curdis = dis;                           
 +                                      }
 +                              }
 +                      }
 +              }
 +              
 +              if (!kcd->ignore_vert_snapping || !(curv && curv->v)) {
 +                      if (fptr)
 +                              *fptr = f;
 +              
 +                      if (curv && p) {
 +                              copy_v3_v3(p, curv->co);
 +                              copy_v3_v3(cagep, curv->cageco);
 +                      }
 +                      
 +                      return curv;
 +              } else {
 +                      if (fptr)
 +                              *fptr = f;
 +                      
 +                      return NULL;
 +              }
 +      }
 +              
 +      if (fptr)
 +              *fptr = NULL;
 +      
 +      return NULL;
 +}
 +
 +/*update active knife edge/vert pointers*/
 +static int knife_update_active(knifetool_opdata *kcd)
 +{
 +      kcd->curvert = NULL; kcd->curedge = NULL; kcd->curbmface = NULL;
 +      
 +      kcd->curvert = knife_find_closest_vert(kcd, kcd->vertco, kcd->vertcage, &kcd->curbmface, &kcd->is_space);
 +      if (!kcd->curvert) {
 +              kcd->curedge = knife_find_closest_edge(kcd, kcd->vertco, kcd->vertcage, &kcd->curbmface, &kcd->is_space);
 +      }
 +      
 +      /* if no hits are found this would normally default to (0,0,0) so instead
 +       * get a point at the mouse ray closest to the previous point.
 +       * Note that drawing lines in `free-space` isn't properly supported
 +       * but theres no guarantee (0,0,0) has any geometry either - campell */
 +      if(kcd->curvert == NULL && kcd->curedge == NULL) {
 +                      float origin[3], ray[3], co[3];
 +
 +                      knife_input_ray_cast(kcd, kcd->vc.mval, origin, ray);
 +                      add_v3_v3v3(co, origin, ray);
 +
 +                      closest_to_line_v3(kcd->vertcage, kcd->prevcage, co, origin);
 +      }
 +
 +      if (kcd->mode == MODE_DRAGGING) {
 +              knife_find_line_hits(kcd);
 +      }
 +      return 1;
 +}
 +
 +#define MARK                  4
 +#define DEL                           8       
 +#define VERT_ON_EDGE  16
 +#define VERT_ORIG             32
 +#define FACE_FLIP             64
 +#define BOUNDARY              128
 +#define FACE_NEW              256
 +
 +typedef struct facenet_entry {
 +      struct facenet_entry *next, *prev;
 +      KnifeEdge *kfe;
 +} facenet_entry;
 +
 +static void rnd_offset_co(float co[3], float scale)
 +{
 +      int i;
 +      
 +      for (i=0; i<3; i++) {
 +              co[i] += (BLI_drand()-0.5)*scale;
 +      }
 +}
 +
 +static void remerge_faces(knifetool_opdata *kcd)
 +{
 +      BMesh *bm = kcd->em->bm;
 +      SmallHash svisit, *visit=&svisit;
 +      BMIter iter;
 +      BMFace *f;
 +      BMFace **stack = NULL;
 +      BLI_array_declare(stack);
 +      BMFace **faces = NULL;
 +      BLI_array_declare(faces);
 +      BMOperator bmop;
 +      int idx;
 +      
 +      BMO_InitOpf(bm, &bmop, "beautify_fill faces=%ff constrain_edges=%fe", FACE_NEW, BOUNDARY);
 +      
 +      BMO_Exec_Op(bm, &bmop);
 +      BMO_Flag_Buffer(bm, &bmop, "geomout", FACE_NEW, BM_FACE);
 +      
 +      BMO_Finish_Op(bm, &bmop);
 +      
 +      BLI_smallhash_init(visit);
 +      BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) {
 +              BMIter eiter;
 +              BMEdge *e;
 +              BMFace *f2;
 +              
 +              if (!BMO_TestFlag(bm, f, FACE_NEW))
 +                      continue;
 +              
 +              if (BLI_smallhash_haskey(visit, (intptr_t)f))
 +                      continue;
 +              
 +              BLI_array_empty(stack);
 +              BLI_array_empty(faces);
 +              BLI_array_append(stack, f);
 +              BLI_smallhash_insert(visit, (intptr_t)f, NULL);
 +              
 +              do {
 +                      f2 = BLI_array_pop(stack);
 +                      
 +                      BLI_array_append(faces, f2);
 +                      
 +                      BM_ITER(e, &eiter, bm, BM_EDGES_OF_FACE, f2) {
 +                              BMIter fiter;
 +                              BMFace *f3;
 +                              
 +                              if (BMO_TestFlag(bm, e, BOUNDARY))
 +                                      continue;
 +                              
 +                              BM_ITER(f3, &fiter, bm, BM_FACES_OF_EDGE, e) {
 +                                      if (!BMO_TestFlag(bm, f3, FACE_NEW))
 +                                              continue;
 +                                      if (BLI_smallhash_haskey(visit, (intptr_t)f3))
 +                                              continue;
 +                                      
 +                                      BLI_smallhash_insert(visit, (intptr_t)f3, NULL);
 +                                      BLI_array_append(stack, f3);
 +                              }
 +                      }       
 +              } while (BLI_array_count(stack) > 0);
 +              
 +              if (BLI_array_count(faces) > 0) {
 +                      idx = BM_GetIndex(faces[0]);
 +                      
 +                      f2 = BM_Join_Faces(bm, faces, BLI_array_count(faces));
 +                      if (f2)  {
 +                              BMO_SetFlag(bm, f2, FACE_NEW);
 +                              BM_SetIndex(f2, idx); /* set_dirty! */ /* BMESH_TODO, check if this is valid or not */
 +                      }
 +              }
 +      }
 +      /* BMESH_TODO, check if the code above validates the indicies */
 +      /* bm->elem_index_dirty &= ~BM_FACE; */
 +      bm->elem_index_dirty |= BM_FACE;
 +
 +      BLI_array_free(stack);
 +      BLI_array_free(faces);
 +}
 +
 +/*use edgenet to fill faces.  this is a bit annoying and convoluted.*/
 +static void knifenet_fill_faces(knifetool_opdata *kcd)
 +{
 +      BMesh *bm = kcd->em->bm;
 +      BMIter bmiter;
 +      BLI_mempool_iter iter;
 +      BMFace *f;
 +      BMEdge *e;
 +      KnifeVert *kfv;
 +      KnifeEdge *kfe;
 +      facenet_entry *entry;
 +      ListBase *face_nets = MEM_callocN(sizeof(ListBase)*bm->totface, "face_nets");
 +      BMFace **faces = MEM_callocN(sizeof(BMFace*)*bm->totface, "faces knife");
 +      MemArena *arena = BLI_memarena_new(1<<16, "knifenet_fill_faces");
 +      SmallHash shash, *hash = &shash;
 +      /* SmallHash shash2, *visited = &shash2; */ /*UNUSED*/
 +      int i, j, k=0, totface=bm->totface;
 +      
 +      BMO_push(bm, NULL);
 +      bmesh_begin_edit(bm, BMOP_UNTAN_MULTIRES);
 +
 +      /* BMESH_TODO this should be valid now, leaving here until we can ensure this - campbell */
 +      i = 0;
 +      BM_ITER(f, &bmiter, bm, BM_FACES_OF_MESH, NULL) {
 +              BM_SetIndex(f, i); /* set_inline */
 +              faces[i] = f;
 +              i++;
 +      }
 +      bm->elem_index_dirty &= ~BM_FACE;
 +      
 +      BM_ITER(e, &bmiter, bm, BM_EDGES_OF_MESH, NULL) {
 +              BMO_SetFlag(bm, e, BOUNDARY);
 +      }
 +
 +      /*turn knife verts into real verts, as necassary*/
 +      BLI_mempool_iternew(kcd->kverts, &iter);
 +      for (kfv=BLI_mempool_iterstep(&iter); kfv; kfv=BLI_mempool_iterstep(&iter)) {
 +              if (!kfv->v) {
 +                      /* shouldn't we be at least copying the normal? - if not some comment here should explain why - campbell */
 +                      kfv->v = BM_Make_Vert(bm, kfv->co, NULL);
 +                      kfv->flag = 1;
 +                      BMO_SetFlag(bm, kfv->v, DEL);
 +              } else {
 +                      kfv->flag = 0;
 +                      BMO_SetFlag(bm, kfv->v, VERT_ORIG);
 +              }
 +
 +              BMO_SetFlag(bm, kfv->v, MARK);
 +      }
 +      
 +      /*we want to only do changed faces.  first, go over new edges and add to
 +      face net lists.*/
 +      i=0; j=0; k=0;
 +      BLI_mempool_iternew(kcd->kedges, &iter);
 +      for (kfe=BLI_mempool_iterstep(&iter); kfe; kfe=BLI_mempool_iterstep(&iter)) {
 +              Ref *ref;
 +              if (!kfe->v1 || !kfe->v2 || kfe->v1->inspace || kfe->v2->inspace)
 +                      continue;
 +
 +              i++;
 +
 +              if (kfe->e && kfe->v1->v == kfe->e->v1 && kfe->v2->v == kfe->e->v2) {
 +                      kfe->oe = kfe->e;
 +                      continue;
 +              }
 +              
 +              j++;
 +              
 +              if (kfe->e) {
 +                      kfe->oe = kfe->e;
 +
 +                      BMO_SetFlag(bm, kfe->e, DEL);
 +                      BMO_ClearFlag(bm, kfe->e, BOUNDARY);
 +                      kfe->e = NULL;
 +              }
 +              
 +              kfe->e = BM_Make_Edge(bm, kfe->v1->v, kfe->v2->v, NULL, 1);
 +              BMO_SetFlag(bm, kfe->e, BOUNDARY);
 +              
 +              for (ref=kfe->faces.first; ref; ref=ref->next) {
 +                      f = ref->ref;
 +                      
 +                      entry = BLI_memarena_alloc(arena, sizeof(*entry));
 +                      entry->kfe = kfe;
 +                      BLI_addtail(face_nets+BM_GetIndex(f), entry);
 +              }
 +      }
 +      
 +      /*go over original edges, and add to faces with new geometry*/
 +      BLI_mempool_iternew(kcd->kedges, &iter);
 +      for (kfe=BLI_mempool_iterstep(&iter); kfe; kfe=BLI_mempool_iterstep(&iter)) {
 +              Ref *ref;
 +              
 +              if (!kfe->v1 || !kfe->v2 || kfe->v1->inspace || kfe->v2->inspace)
 +                      continue;
 +              if (!(kfe->oe && kfe->v1->v == kfe->oe->v1 && kfe->v2->v == kfe->oe->v2))
 +                      continue;
 +              
 +              k++;
 +              
 +              BMO_SetFlag(bm, kfe->e, BOUNDARY);
 +              kfe->oe = kfe->e;
 +              
 +              for (ref=kfe->faces.first; ref; ref=ref->next) {
 +                      f = ref->ref;
 +                      
 +                      if (face_nets[BM_GetIndex(f)].first) {
 +                              entry = BLI_memarena_alloc(arena, sizeof(*entry));
 +                              entry->kfe = kfe;
 +                              BLI_addtail(face_nets+BM_GetIndex(f), entry);
 +                      }
 +              }
 +      }
 +      
 +      for (i=0; i<totface; i++) {
 +              EditFace *efa;
 +              EditVert *eve, *lasteve;
 +              int j;
 +              float rndscale = FLT_EPSILON*25;
 +              
 +              f = faces[i];
 +              BLI_smallhash_init(hash);
 +              
 +              if (face_nets[i].first)
 +                      BMO_SetFlag(bm, f, DEL);
 +              
 +              BLI_begin_edgefill();
 +              
 +              for (entry=face_nets[i].first; entry; entry=entry->next) {
 +                      if (!BLI_smallhash_haskey(hash, (intptr_t)entry->kfe->v1)) {
 +                              eve = BLI_addfillvert(entry->kfe->v1->v->co);
 +                              eve->xs = 0;
 +                              rnd_offset_co(eve->co, rndscale);
 +                              eve->tmp.p = entry->kfe->v1->v;
 +                              BLI_smallhash_insert(hash, (intptr_t)entry->kfe->v1, eve);
 +                      }
 +
 +                      if (!BLI_smallhash_haskey(hash, (intptr_t)entry->kfe->v2)) {
 +                              eve = BLI_addfillvert(entry->kfe->v2->v->co);
 +                              eve->xs = 0;
 +                              rnd_offset_co(eve->co, rndscale);
 +                              eve->tmp.p = entry->kfe->v2->v;
 +                              BLI_smallhash_insert(hash, (intptr_t)entry->kfe->v2, eve);
 +                      }                                                
 +              }
 +              
 +              for (j=0, entry=face_nets[i].first; entry; entry=entry->next, j++) {
 +                      lasteve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v1);
 +                      eve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v2);
 +                      
 +                      eve->xs++;
 +                      lasteve->xs++;
 +              }
 +              
 +              for (j=0, entry=face_nets[i].first; entry; entry=entry->next, j++) {
 +                      lasteve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v1);
 +                      eve = BLI_smallhash_lookup(hash, (intptr_t)entry->kfe->v2);
 +                      
 +                      if (eve->xs > 1 && lasteve->xs > 1) {
 +                              BLI_addfilledge(lasteve, eve);
 +                              
 +                              BMO_ClearFlag(bm, entry->kfe->e->v1, DEL);
 +                              BMO_ClearFlag(bm, entry->kfe->e->v2, DEL);
 +                      } else {
 +                              if (lasteve->xs < 2)
 +                                      BLI_remlink(&fillvertbase, lasteve);
 +                              if (eve->xs < 2)
 +                                      BLI_remlink(&fillvertbase, eve);
 +                      }
 +              }
 +              
 +              BLI_edgefill(0);
 +              
 +              for (efa=fillfacebase.first; efa; efa=efa->next) {
 +                      BMVert *v1=efa->v3->tmp.p, *v2=efa->v2->tmp.p, *v3=efa->v1->tmp.p;
 +                      BMFace *f2;
 +                      BMLoop *l;
 +                      BMVert *verts[3] = {v1, v2, v3};
 +                      
 +                      if (v1 == v2 || v2 == v3 || v1 == v3)
 +                              continue;       
 +                      if (BM_Face_Exists(bm, verts, 3, &f2))
 +                              continue;
 +              
 +                      f2 = BM_Make_QuadTri(bm, v1, v2, v3, NULL, NULL, 0);
 +                      BMO_SetFlag(bm, f2, FACE_NEW);
 +                      
 +                      l = bm_firstfaceloop(f2);
 +                      do {
 +                              BMO_ClearFlag(bm, l->e, DEL);
 +                              l = l->next;
 +                      } while (l != bm_firstfaceloop(f2));
 +      
 +                      BMO_ClearFlag(bm, f2, DEL);
 +                      BM_SetIndex(f2, i); /* set_dirty! */ /* note, not 100% sure this is dirty? need to check */
 +
 +                      BM_Face_UpdateNormal(bm, f2);
 +                      if (dot_v3v3(f->no, f2->no) < 0.0f) {
 +                              BM_flip_normal(bm, f2);
 +                      }
 +              }
 +              
 +              BLI_end_edgefill();
 +              BLI_smallhash_release(hash);
 +      }
 +      bm->elem_index_dirty |= BM_FACE;
 +      
 +      /* interpolate customdata */
 +      BM_ITER(f, &bmiter, bm, BM_FACES_OF_MESH, NULL) {
 +              BMLoop *l1;
 +              BMFace *f2; 
 +              BMIter liter1;
 +
 +              if (!BMO_TestFlag(bm, f, FACE_NEW))
 +                      continue;
 +              
 +              f2 = faces[BM_GetIndex(f)];
 +              if (BM_GetIndex(f) < 0 || BM_GetIndex(f) >= totface) {
 +                      fprintf(stderr, "%s: face index out of range! (bmesh internal error)\n", __func__);
 +              }
 +
 +              BM_Copy_Attributes(bm, bm, f2, f);
 +              
 +              BM_ITER(l1, &liter1, bm, BM_LOOPS_OF_FACE, f) {
 +                      BM_loop_interp_from_face(bm, l1, f2, 1, 1);
 +              }
 +      }
 +
 +      /*merge triangles back into faces*/
 +      remerge_faces(kcd);
 +
 +      /*delete left over faces*/
 +      BMO_CallOpf(bm, "del geom=%ff context=%i", DEL, DEL_ONLYFACES);
 +      BMO_CallOpf(bm, "del geom=%fe context=%i", DEL, DEL_EDGES);
 +      BMO_CallOpf(bm, "del geom=%fv context=%i", DEL, DEL_VERTS);
 +
 +      if (face_nets) 
 +              MEM_freeN(face_nets);
 +      if (faces)
 +              MEM_freeN(faces);
 +      BLI_memarena_free(arena);
 +      BLI_smallhash_release(hash);    
 +      
 +      BMO_ClearStack(bm); /*remerge_faces sometimes raises errors, so make sure to clear them*/
 +
 +      bmesh_end_edit(bm, BMOP_UNTAN_MULTIRES);
 +      BMO_pop(bm);
 +}
 +
 +/*called on tool confirmation*/
 +static void knifetool_finish(bContext *C, wmOperator *op)
 +{
 +      knifetool_opdata *kcd= op->customdata;
 +      
 +      knifenet_fill_faces(kcd);
 +      
 +      DAG_id_tag_update(kcd->ob->data, OB_RECALC_DATA);
 +      WM_event_add_notifier(C, NC_GEOM|ND_DATA, kcd->ob->data);
 +}
 +
 +/*copied from paint_image.c*/
 +static int project_knife_view_clip(View3D *v3d, RegionView3D *rv3d, float *clipsta, float *clipend)
 +{
 +      int orth= ED_view3d_clip_range_get(v3d, rv3d, clipsta, clipend);
 +
 +      if (orth) { /* only needed for ortho */
 +              float fac = 2.0f / ((*clipend) - (*clipsta));
 +              *clipsta *= fac;
 +              *clipend *= fac;
 +      }
 +
 +      return orth;
 +}
 +
 +static void knife_recalc_projmat(knifetool_opdata *kcd)
 +{
 +      ARegion *ar = CTX_wm_region(kcd->C);
 +      
 +      if (!ar)
 +              return;
 +      
 +      invert_m4_m4(kcd->ob->imat, kcd->ob->obmat);
 +      ED_view3d_ob_project_mat_get(ar->regiondata, kcd->ob, kcd->projmat);
 +      //mul_m4_m4m4(kcd->projmat, kcd->vc.rv3d->viewmat, kcd->vc.rv3d->winmat);
 +      
 +      kcd->is_ortho = project_knife_view_clip(kcd->vc.v3d, kcd->vc.rv3d, 
 +                                              &kcd->clipsta, &kcd->clipend);
 +}
 +
 +/* called when modal loop selection is done... */
 +static void knifetool_exit (bContext *UNUSED(C), wmOperator *op)
 +{
 +      knifetool_opdata *kcd= op->customdata;
 +      
 +      if (!kcd)
 +              return;
 +      
 +      /* deactivate the extra drawing stuff in 3D-View */
 +      ED_region_draw_cb_exit(kcd->ar->type, kcd->draw_handle);
 +      
 +      /* free the custom data */
 +      BLI_mempool_destroy(kcd->refs);
 +      BLI_mempool_destroy(kcd->kverts);
 +      BLI_mempool_destroy(kcd->kedges);
 +
 +      BLI_ghash_free(kcd->origedgemap, NULL, NULL);
 +      BLI_ghash_free(kcd->origvertmap, NULL, NULL);
 +      BLI_ghash_free(kcd->kedgefacemap, NULL, NULL);
 +      
 +      BMBVH_FreeBVH(kcd->bmbvh);
 +      BLI_memarena_free(kcd->arena);
 +      
 +      /* tag for redraw */
 +      ED_region_tag_redraw(kcd->ar);
 +
 +      if (kcd->cagecos)
 +              MEM_freeN(kcd->cagecos);
 +
 +      /* destroy kcd itself */
 +      MEM_freeN(kcd);
 +      op->customdata= NULL;
 +}
 +
 +static void cage_mapped_verts_callback(void *userData, int index, float *co, 
 +      float *UNUSED(no_f), short *UNUSED(no_s))
 +{
 +      void **data = userData;
 +      BMEditMesh *em = data[0];
 +      float (*cagecos)[3] = data[1];
 +      SmallHash *hash = data[2];
 +      
 +      if (index >= 0 && index < em->bm->totvert && !BLI_smallhash_haskey(hash, index)) {
 +              BLI_smallhash_insert(hash, index, NULL);
 +              copy_v3_v3(cagecos[index], co);
 +      }
 +}
 +
 +/* called when modal loop selection gets set up... */
 +static int knifetool_init(bContext *C, wmOperator *op, int UNUSED(do_cut))
 +{
 +      knifetool_opdata *kcd;
 +      Scene *scene = CTX_data_scene(C);
 +      Object *obedit = CTX_data_edit_object(C);
 +      DerivedMesh *cage, *final;
 +      SmallHash shash;
 +      void *data[3];
 +      
 +      /* alloc new customdata */
 +      kcd= op->customdata= MEM_callocN(sizeof(knifetool_opdata), "knifetool Modal Op Data");
 +      
 +      /* assign the drawing handle for drawing preview line... */
 +      kcd->ob = obedit;
 +      kcd->ar= CTX_wm_region(C);
 +      kcd->C = C;
 +      kcd->draw_handle= ED_region_draw_cb_activate(kcd->ar->type, knifetool_draw, kcd, REGION_DRAW_POST_VIEW);
 +      em_setup_viewcontext(C, &kcd->vc);
 +
 +      kcd->em= ((Mesh *)kcd->ob->data)->edit_btmesh;
 +
 +      BM_ElemIndex_Ensure(kcd->em->bm, BM_VERT);
 +
 +      cage = editbmesh_get_derived_cage_and_final(scene, obedit, kcd->em, &final, CD_MASK_DERIVEDMESH);
 +      kcd->cagecos = MEM_callocN(sizeof(float)*3*kcd->em->bm->totvert, "knife cagecos");
 +      data[0] = kcd->em;
 +      data[1] = kcd->cagecos;
 +      data[2] = &shash;
 +      
 +      BLI_smallhash_init(&shash);
 +      cage->foreachMappedVert(cage, cage_mapped_verts_callback, data);
 +      BLI_smallhash_release(&shash);
 +      
 +      kcd->bmbvh = BMBVH_NewBVH(kcd->em, BMBVH_USE_CAGE|BMBVH_RETURN_ORIG, scene, obedit);
 +      kcd->arena = BLI_memarena_new(1<<15, "knife");
 +      kcd->vthresh = KMAXDIST-1;
 +      kcd->ethresh = KMAXDIST;
 +      
 +      kcd->extend = 1;
 +      
 +      knife_recalc_projmat(kcd);
 +      
 +      ED_region_tag_redraw(kcd->ar);
 +      
 +      kcd->refs = BLI_mempool_create(sizeof(Ref), 1, 2048, 0, 0);
 +      kcd->kverts = BLI_mempool_create(sizeof(KnifeVert), 1, 512, 0, 1);
 +      kcd->kedges = BLI_mempool_create(sizeof(KnifeEdge), 1, 512, 0, 1);
 +      
 +      kcd->origedgemap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origedgemap");
 +      kcd->origvertmap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origvertmap");
 +      kcd->kedgefacemap = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "knife origvertmap");
 +
 +      return 1;
 +}
 +
 +static int knifetool_cancel (bContext *C, wmOperator *op)
 +{
 +      /* this is just a wrapper around exit() */
 +      knifetool_exit(C, op);
 +      return OPERATOR_CANCELLED;
 +}
 +
 +static int knifetool_invoke (bContext *C, wmOperator *op, wmEvent *evt)
 +{
 +      knifetool_opdata *kcd;
 +
 +      view3d_operator_needs_opengl(C);
 +
 +      if (!knifetool_init(C, op, 0))
 +              return OPERATOR_CANCELLED;
 +      
 +      /* add a modal handler for this operator - handles loop selection */
 +      WM_event_add_modal_handler(C, op);
 +
 +      kcd = op->customdata;
 +      kcd->vc.mval[0] = evt->mval[0];
 +      kcd->vc.mval[1] = evt->mval[1];
 +      
 +      return OPERATOR_RUNNING_MODAL;
 +}
 +
 +enum {
 +      KNF_MODAL_CANCEL=1,
 +      KNF_MODAL_CONFIRM,
 +      KNF_MODAL_MIDPOINT_ON,
 +      KNF_MODAL_MIDPOINT_OFF,
 +      KNF_MODAL_NEW_CUT,
 +      KNF_MODEL_IGNORE_SNAP_ON,
 +      KNF_MODEL_IGNORE_SNAP_OFF,
 +      KNF_MODAL_ADD_CUT,
 +};
 +
 +wmKeyMap* knifetool_modal_keymap(wmKeyConfig *keyconf)
 +{
 +      static EnumPropertyItem modal_items[] = {
 +      {KNF_MODAL_CANCEL, "CANCEL", 0, "Cancel", ""},
 +      {KNF_MODAL_CONFIRM, "CONFIRM", 0, "Confirm", ""},
 +      {KNF_MODAL_MIDPOINT_ON, "SNAP_MIDPOINTS_ON", 0, "Snap To Midpoints On", ""},
 +      {KNF_MODAL_MIDPOINT_OFF, "SNAP_MIDPOINTS_OFF", 0, "Snap To Midpoints Off", ""},
 +      {KNF_MODEL_IGNORE_SNAP_ON, "IGNORE_SNAP_ON", 0, "Ignore Snapping On", ""},
 +      {KNF_MODEL_IGNORE_SNAP_OFF, "IGNORE_SNAP_OFF", 0, "Ignore Snapping Off", ""},
 +      {KNF_MODAL_NEW_CUT, "NEW_CUT", 0, "End Current Cut", ""},
 +      {KNF_MODAL_ADD_CUT, "ADD_CUT", 0, "Add Cut", ""},
 +
 +      {0, NULL, 0, NULL, NULL}};
 +      
 +      wmKeyMap *keymap= WM_modalkeymap_get(keyconf, "Knife Tool Modal Map");
 +      
 +      /* this function is called for each spacetype, only needs to add map once */
 +      if(keymap) return NULL;
 +      
 +      keymap= WM_modalkeymap_add(keyconf, "Knife Tool Modal Map", modal_items);
 +      
 +      /* items for modal map */
 +      WM_modalkeymap_add_item(keymap, ESCKEY,    KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
 +      WM_modalkeymap_add_item(keymap, LEFTMOUSE, KM_PRESS, KM_ANY, 0, KNF_MODAL_ADD_CUT);
 +      WM_modalkeymap_add_item(keymap, RIGHTMOUSE, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
 +      WM_modalkeymap_add_item(keymap, RETKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
 +      WM_modalkeymap_add_item(keymap, PADENTER, KM_PRESS, KM_ANY, 0, KNF_MODAL_CONFIRM);
 +      WM_modalkeymap_add_item(keymap, EKEY, KM_PRESS, 0, 0, KNF_MODAL_NEW_CUT);
 +
 +      WM_modalkeymap_add_item(keymap, LEFTCTRLKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_MIDPOINT_ON);
 +      WM_modalkeymap_add_item(keymap, LEFTCTRLKEY, KM_RELEASE, KM_ANY, 0, KNF_MODAL_MIDPOINT_OFF);
 +      WM_modalkeymap_add_item(keymap, RIGHTCTRLKEY, KM_PRESS, KM_ANY, 0, KNF_MODAL_MIDPOINT_ON);
 +      WM_modalkeymap_add_item(keymap, RIGHTCTRLKEY, KM_RELEASE, KM_ANY, 0, KNF_MODAL_MIDPOINT_OFF);
 +
 +      WM_modalkeymap_add_item(keymap, LEFTSHIFTKEY, KM_PRESS, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_ON);
 +      WM_modalkeymap_add_item(keymap, LEFTSHIFTKEY, KM_RELEASE, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_OFF);
 +      WM_modalkeymap_add_item(keymap, RIGHTSHIFTKEY, KM_PRESS, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_ON);
 +      WM_modalkeymap_add_item(keymap, RIGHTSHIFTKEY, KM_RELEASE, KM_ANY, 0, KNF_MODEL_IGNORE_SNAP_OFF);
 +      
 +      WM_modalkeymap_assign(keymap, "MESH_OT_knifetool");
 +      
 +      return keymap;
 +}
 +
 +static int knifetool_modal (bContext *C, wmOperator *op, wmEvent *event)
 +{
 +      Object *obedit;
 +      knifetool_opdata *kcd= op->customdata;
 +      
 +      if (!C) {
 +              return OPERATOR_FINISHED;
 +      }
 +      
 +      obedit = CTX_data_edit_object(C);
 +      if (!obedit || obedit->type != OB_MESH || ((Mesh*)obedit->data)->edit_btmesh != kcd->em) {
 +              knifetool_exit(C, op);
 +              return OPERATOR_FINISHED;
 +      }
 +
 +      view3d_operator_needs_opengl(C);
 +      
 +      if (kcd->mode == MODE_PANNING)
 +              kcd->mode = kcd->prevmode;
 +      
 +      /* handle modal keymap */
 +      if (event->type == EVT_MODAL_MAP) {
 +              switch (event->val) {
 +                      case KNF_MODAL_CANCEL:
 +                              /* finish */
 +                              ED_region_tag_redraw(kcd->ar);
 +                              
 +                              knifetool_exit(C, op);
 +                              
 +                              return OPERATOR_CANCELLED;
 +                      case KNF_MODAL_CONFIRM:
 +                              /* finish */
 +                              ED_region_tag_redraw(kcd->ar);
 +                              
 +                              knifetool_finish(C, op);
 +                              knifetool_exit(C, op);
 +                              
 +                              return OPERATOR_FINISHED;
 +                      case KNF_MODAL_MIDPOINT_ON:
 +                              kcd->snap_midpoints = 1;
 +
 +                              knife_recalc_projmat(kcd);
 +                              knife_update_active(kcd);
 +                              ED_region_tag_redraw(kcd->ar);
 +                              break;
 +                      case KNF_MODAL_MIDPOINT_OFF:
 +                              kcd->snap_midpoints = 0;
 +
 +                              knife_recalc_projmat(kcd);
 +                              knife_update_active(kcd);
 +                              ED_region_tag_redraw(kcd->ar);
 +                              break;
 +                      case KNF_MODEL_IGNORE_SNAP_ON:
 +                              ED_region_tag_redraw(kcd->ar);
 +                              kcd->ignore_vert_snapping = kcd->ignore_edge_snapping = 1;
 +                              break;
 +                      case KNF_MODEL_IGNORE_SNAP_OFF:
 +                              ED_region_tag_redraw(kcd->ar);
 +                              kcd->ignore_vert_snapping = kcd->ignore_edge_snapping = 0;
 +                              break;
 +                      case KNF_MODAL_NEW_CUT:
 +                              ED_region_tag_redraw(kcd->ar);
 +                              knife_finish_cut(kcd);
 +                              kcd->mode = MODE_IDLE;
 +                              break;
 +                      case KNF_MODAL_ADD_CUT:
 +                              knife_recalc_projmat(kcd);
 +
 +                              if (kcd->mode == MODE_DRAGGING) {
 +                                      knife_add_cut(kcd);
 +                                      if (!kcd->extend) {
 +                                              knife_finish_cut(kcd);
 +                                              kcd->mode = MODE_IDLE;
 +                                      }
 +                              } else if (kcd->mode != MODE_PANNING) {
 +                                      knife_start_cut(kcd);
 +                                      kcd->mode = MODE_DRAGGING;
 +                              }
 +              
 +                              ED_region_tag_redraw(kcd->ar);
 +                              break;
 +                      }
 +      } else { /*non-modal-mapped events*/
 +              switch (event->type) {
 +                      case WHEELUPMOUSE:
 +                      case WHEELDOWNMOUSE:
 +                              return OPERATOR_PASS_THROUGH;
 +                      case MIDDLEMOUSE:
 +                              if (event->val != KM_RELEASE) {
 +                                      if (kcd->mode != MODE_PANNING)
 +                                              kcd->prevmode = kcd->mode;
 +                                      kcd->mode = MODE_PANNING;
 +                              } else {
 +                                      kcd->mode = kcd->prevmode;
 +                              }
 +                              
 +                              ED_region_tag_redraw(kcd->ar);
 +                              return OPERATOR_PASS_THROUGH;
 +                              
 +                      case MOUSEMOVE:  /* mouse moved somewhere to select another loop */
 +                              if (kcd->mode != MODE_PANNING) {
 +                                      knife_recalc_projmat(kcd);
 +                                      kcd->vc.mval[0] = event->mval[0];
 +                                      kcd->vc.mval[1] = event->mval[1];
 +                                      
 +                                      if (knife_update_active(kcd))                                   
 +                                              ED_region_tag_redraw(kcd->ar);
 +                              }
 +      
 +                              break;
 +              }
 +      }
 +      
 +      /* keep going until the user confirms */
 +      return OPERATOR_RUNNING_MODAL;
 +}
 +
 +void MESH_OT_knifetool (wmOperatorType *ot)
 +{
 +      /* description */
 +      ot->name= "Knife Topology Tool";
 +      ot->idname= "MESH_OT_knifetool";
 +      ot->description= "Cut new topology";
 +      
 +      /* callbacks */
 +      ot->invoke= knifetool_invoke;
 +      ot->modal= knifetool_modal;
 +      ot->cancel= knifetool_cancel;
 +      ot->poll= ED_operator_editmesh_view3d;
 +      
 +      /* flags */
 +      ot->flag= OPTYPE_REGISTER|OPTYPE_UNDO|OPTYPE_BLOCKING;
 +}
index bdef3b7f17678eaf256e77e1701aa7d57d48b6cb,ce052b2c1bdb5f49eb1765954e44f85bab50af9c..e8979066d0bcaaf706f69cf32ce71b6f6a0374a6
@@@ -32,8 -37,8 +32,9 @@@
  
  #include "MEM_guardedalloc.h"
  
 -#include "BLI_math.h"
  #include "BLI_utildefines.h"
++#include "BLI_string.h"
 +#include "BLI_math.h"
  #include "BLI_ghash.h"
  #include "BLI_edgehash.h"