=BMesh: Super Knife Tool Alpha=

Implemented a new "super knife".  Activate with k.  Holding CTRL
will allow extended cutting ala old lines mode.  Confirm with enter 
and escape. You cannot cancel, btw, you can only confirm (and undo 
later if you want). Hopefully I'll support undo within the tool soon.

* Supports cutting edges, into faces, etc.  You can pretty much do whatever 
  you want.  Will snap to vertices too.
* Note that if you cut into a face, it must be valid topologically when 
  you press enter to confirm.
* It's pretty and graphical :)
* You can only cut visible geometry.
* UVs/vcols are a little buggy still

Now, thou shalt all cease and desist all lack of motivation for
testing!  No longer shall users put off testing until "it's cooler"!

:P

5 files changed, 286 insertions, 29 deletions

diff --git a/source/blender/blenlib/BLI_array.h b/source/blender/blenlib/BLI_array.h
index 7c1dfb1d3a4..b1db2538e6f 100644
--- a/source/blender/blenlib/BLI_array.h
+++ b/source/blender/blenlib/BLI_array.h
@@ -1,6 +1,5 @@
 /**
- * Array library
- * 
+ * Array Library
  *
  * ***** BEGIN GPL LICENSE BLOCK *****
  *
@@ -23,7 +22,7 @@
  *
  * The Original Code is: all of this file.
  *
- * Contributor(s): Geoffrey Bantle.
+ * Contributor(s): Joseph Eagar.
  *
  * ***** END GPL LICENSE BLOCK *****
  */
@@ -90,6 +89,7 @@ behaviour, though it may not be the best in practice.
 #define BLI_array_growitems(arr, num) {int _i; for (_i=0; _i<(num); _i++) {BLI_array_growone(arr);}}
 #define BLI_array_free(arr) if (arr && arr != _##arr##_static) MEM_freeN(arr)
 
+#define BLI_array_pop(arr) ((arr&&_##arr##_count) ? arr[--_##arr##_count] : NULL)
 /*resets the logical size of an array to zero, but doesn't
   free the memory.*/
 #define BLI_array_empty(arr) _##arr##_count=0
diff --git a/source/blender/blenlib/BLI_mempool.h b/source/blender/blenlib/BLI_mempool.h
index c7be8f50cf3..62714defd21 100644
--- a/source/blender/blenlib/BLI_mempool.h
+++ b/source/blender/blenlib/BLI_mempool.h
@@ -36,19 +36,42 @@ extern "C"
 {
 #endif
 
+#include "BKE_utildefines.h"
+#include "BLI_listbase.h"
+#include "BLI_blenlib.h"
+#include <string.h>
+
 #ifndef BLI_MEMPOOL_INTERN
-struct BLI_mempool;
-struct BLI_mempool_chunk;
-typedef struct BLI_mempool BLI_mempool;
+//struct BLI_mempool;
+//struct BLI_mempool_chunk;
+//typedef struct BLI_mempool BLI_mempool;
 #endif
 
+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;
+
 /*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);
+//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);
@@ -69,6 +92,55 @@ 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);
 
+/************ 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;
+	int j;
+	
+	if (!pool) return NULL;
+	
+	pool->totused++;
+
+	if(!(pool->free)){
+		/*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
diff --git a/source/blender/blenlib/BLI_smallhash.h b/source/blender/blenlib/BLI_smallhash.h
new file mode 100755
index 00000000000..5badff062b7
--- /dev/null
+++ b/source/blender/blenlib/BLI_smallhash.h
@@ -0,0 +1,204 @@
+/**
+ * ***** 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) 2008 Blender Foundation.
+ * All rights reserved.
+ *
+ * The Original Code is: all of this file.
+ *
+ * Contributor(s): Joseph Eagar.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+ 
+#ifndef BLI_SMALLHASH_H
+#define BLI_SMALLHASH_H
+
+/*******a light stack-friendly hash library******
+ *      (it uses stack space for smallish hash tables)     */
+
+/*based on a doubling non-chaining approach */
+
+#include "MEM_guardedalloc.h"
+#include "BLO_sys_types.h"
+#include "BKE_utildefines.h"
+
+extern unsigned int hashsizes[];
+#define NONHASH	-25436536
+typedef struct entry {intptr_t key; void *val;} entry;
+
+#define SMSTACKSIZE	521
+typedef struct SmallHash {
+	entry *table, _stacktable[SMSTACKSIZE], _copytable[SMSTACKSIZE];
+	entry *stacktable, *copytable;
+	int used;
+	int curhash;
+	int size;
+} SmallHash;
+
+/*CELL_UNUSED means this cell is inside a key series, while CELL_FREE
+  means this cell terminates a key series.
+  
+  no chance of anyone shoving INT32_MAX-2 into a *val pointer, I
+  imagine.  hopefully. */
+#define CELL_UNUSED	((void*)0x7FFFFFFD)
+#define CELL_FREE	((void*)0x7FFFFFFD)
+
+#define HASHNEXT(h) (((h) + ((h)==0))*2)
+
+BM_INLINE void BLI_smallhash_init(SmallHash *hash)
+{
+	int i;
+	
+	memset(hash, 0, sizeof(*hash));
+	
+	hash->table = hash->_stacktable;
+	hash->curhash = 2;
+	hash->size = hashsizes[hash->curhash];
+	
+	hash->copytable = hash->_copytable;
+	hash->stacktable = hash->_stacktable;
+	
+	for (i=0; i<hash->size; i++) {
+		hash->table[i].val = CELL_FREE;
+	}
+}
+
+/*NOTE: does *not* free *hash itself!  only the direct data!*/
+BM_INLINE void BLI_smallhash_release(SmallHash *hash)
+{
+	if (!hash)
+		return;
+	
+	if (hash->table != hash->stacktable)
+		MEM_freeN(hash->table);
+}
+
+BM_INLINE void BLI_smallhash_insert(SmallHash *hash, intptr_t key, void *item) 
+{
+	int h;
+	
+	if (hash->size < hash->used*3) {
+		int newsize = hashsizes[++hash->curhash];
+		entry *tmp;
+		int i = 0;
+		
+		if (hash->table != hash->stacktable || newsize > SMSTACKSIZE) {
+			tmp = MEM_callocN(sizeof(*hash->table)*newsize, "new hashkeys");
+		} else {
+			SWAP(entry*, hash->stacktable, hash->copytable);
+			tmp = hash->stacktable;
+		}
+		
+		SWAP(entry*, tmp, hash->table);
+		
+		hash->size = newsize;
+		
+		for (i=0; i<hash->size; i++) {
+			hash->table[i].val = CELL_FREE;
+		}
+		
+		for (i=0; i<hashsizes[hash->curhash-1]; i++) {
+			if (ELEM(tmp[i].val, CELL_UNUSED, CELL_FREE))
+				continue;
+			
+			h = tmp[i].key;
+			while (!ELEM(hash->table[h % newsize].val, CELL_UNUSED, CELL_FREE))
+				h = HASHNEXT(h);
+			
+			h %= newsize;
+			
+			hash->table[h].key = tmp[i].key;
+			hash->table[h].val = tmp[i].val;
+		}
+		
+		if (tmp != hash->stacktable && tmp != hash->copytable) {
+			MEM_freeN(tmp);
+		}
+	}
+	
+	h = key;
+	while (!ELEM(hash->table[h % hash->size].val, CELL_UNUSED, CELL_FREE))
+		h = HASHNEXT(h);
+	
+	h %= hash->size;
+	hash->table[h].key = key;
+	hash->table[h].val = item;
+	
+	hash->used++;
+}
+
+BM_INLINE void BLI_smallhash_remove(SmallHash *hash, intptr_t key)
+{
+	int h = key;
+	
+	while (hash->table[h % hash->size].key != key 
+	      || hash->table[h % hash->size].val == CELL_UNUSED)
+	{
+		if (hash->table[h % hash->size].val == CELL_FREE)
+			return;
+		h = HASHNEXT(h);
+	}
+	
+	h %= hash->size;
+	hash->table[h].key = 0;
+	hash->table[h].val = CELL_UNUSED;
+}
+
+BM_INLINE void *BLI_smallhash_lookup(SmallHash *hash, intptr_t key)
+{
+	int h = key;
+	
+	if (!hash->table)
+		return NULL;
+	
+	while (hash->table[h % hash->size].key != key 
+	      || hash->table[h % hash->size].val == CELL_UNUSED)
+	{
+		if (hash->table[h % hash->size].val == CELL_FREE)
+			return NULL;
+		h = HASHNEXT(h);
+	}
+	
+	return hash->table[h % hash->size].val;
+}
+
+
+BM_INLINE int BLI_smallhash_haskey(SmallHash *hash, intptr_t key)
+{
+	int h = key;
+	
+	if (!hash->table)
+		return 0;
+	
+	while (hash->table[h % hash->size].key != key 
+	      || hash->table[h % hash->size].val == CELL_UNUSED)
+	{
+		if (hash->table[h % hash->size].val == CELL_FREE)
+			return 0;
+		h = HASHNEXT(h);
+	}
+	
+	return 1;
+}
+
+BM_INLINE int BLI_smallhash_count(SmallHash *hash)
+{
+	return hash->used;
+}
+
+#endif // BLI_SMALLHASH_H
diff --git a/source/blender/blenlib/intern/BLI_mempool.c b/source/blender/blenlib/intern/BLI_mempool.c
index ed56a390719..686709d8879 100644
--- a/source/blender/blenlib/intern/BLI_mempool.c
+++ b/source/blender/blenlib/intern/BLI_mempool.c
@@ -42,26 +42,6 @@
 
 #include <string.h> 
 
-#define FREEWORD MAKE_ID('f', 'r', 'e', 'e')
-
-typedef struct BLI_freenode{
-	struct BLI_freenode *next;
-	intptr_t 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.*/
-	int totalloc, totused; /*total number of elements allocated in total, and currently in use*/
-	int use_sysmalloc, allow_iter;
-}BLI_mempool;
-
 #define BLI_MEMPOOL_INTERN
 #include "BLI_mempool.h"
 
@@ -132,7 +112,7 @@ BLI_mempool *BLI_mempool_create(int esize, int tote, int pchunk,
 	curnode->next = NULL;
 	return pool;
 }
-
+#if 0
 void *BLI_mempool_alloc(BLI_mempool *pool){
 	void *retval=NULL;
 	BLI_freenode *curnode=NULL;
@@ -177,6 +157,7 @@ void *BLI_mempool_alloc(BLI_mempool *pool){
 	//memset(retval, 0, pool->esize);
 	return retval;
 }
+#endif
 
 void *BLI_mempool_calloc(BLI_mempool *pool){
 	void *retval=NULL;
diff --git a/source/blender/blenlib/intern/math_geom.c b/source/blender/blenlib/intern/math_geom.c
index 68b1feea632..6756f42bf35 100644
--- a/source/blender/blenlib/intern/math_geom.c
+++ b/source/blender/blenlib/intern/math_geom.c
@@ -1568,7 +1568,7 @@ void interp_weights_poly_v3(float *w,float v[][3], int n, float *co)
 		t2= mean_value_half_tan(co, vmid, vnext);
 
 		len= len_v3v3(co, vmid);
-		w[i]= (t1+t2)/len;
+		w[i]= (t1+t2)/(len+FLT_EPSILON*2);
 		totweight += w[i];
 	}