Printf-style method of calling operations now take a modified format string,

like so:

[opname] [slotname]=%[format code]

Before it was relying on the input format codes being in the same proper
order as the slots, which seemed like a potential maintainance nightmare to
me.  Also the flags for creating buffers from bmop flags or header flags,
now support additional modifiers for combining vert/edge/face inputs.
E.g. %hfvef would accept all geometry with a header flag, and 
%fef would accept edges and faces with a certain bmop flag set.

Example from the UI code:

if (!EDBM_CallOpf(em, op, "del geom=%hf context=%d", BM_SELECT, DEL_ONLYFACES))
			return OPERATOR_CANCELLED;
			
(remember EDBM_CallOpf is the UI wrapper for this that does conversion, 
 error reporting, etc).  
 
 On todo is cleaning up/splitting bmesh_operators.h,
 since it's kindof a mesh right now.  I'm thinking of adding the slot
 names in comments next to the slot ids, but I definitely would have to
 clean up bmesh_operators.h first, or it'd just be too chaotic for me.
 BTW, the operator API should now have enough meta info to wrap with
 a scripting language, not that it matters since that's not happening till
 much much later.
 
 Also hopefully corrected some SConscripts, fix mostly provided by Elia Sarti,
 though I also copied some SConscripts from 2.5 (not sure if doing
 so was especially helpful).
 
 Finally, I refactored a few places to use the new operator calling api,
 as an example of how this is beneficial.

12 files changed, 517 insertions, 114 deletions

diff --git a/source/blender/SConscript b/source/blender/SConscript
index f9bafcd804a..8cbed8c1045 100644
--- a/source/blender/SConscript
+++ b/source/blender/SConscript
@@ -3,7 +3,7 @@ Import ('env')
 import sys
 
 SConscript(['avi/SConscript',
-			'bmesh/SConscript',
+            'bmesh/SConscript',
             'blenkernel/SConscript',
             'blenlib/SConscript',
             'blenloader/SConscript',
diff --git a/source/blender/bmesh/bmesh_operators.h b/source/blender/bmesh/bmesh_operators.h
index 0c11b3c09e3..30e7e4c9317 100644
--- a/source/blender/bmesh/bmesh_operators.h
+++ b/source/blender/bmesh/bmesh_operators.h
@@ -51,10 +51,17 @@ typedef struct BMOperator{
 	MemArena *arena;
 }BMOperator;
 
+#define MAX_SLOTNAME	32
+
+typedef struct slottype {
+	int type;
+	char name[MAX_SLOTNAME];
+} slottype;
+
 /*need to refactor code to use this*/
 typedef struct BMOpDefine {
 	char *name;
-	int slottypes[BMOP_MAX_SLOTS];
+	slottype slottypes[BMOP_MAX_SLOTS];
 	void (*exec)(BMesh *bm, BMOperator *op);
 	int totslot;
 	int flag;
@@ -326,7 +333,9 @@ void BM_esubdivideflag(struct Object *obedit, struct BMesh *bm, int selflag, flo
 	       int flag, int numcuts, int seltype);
 void BM_extrudefaceflag(BMesh *bm, int flag);
 
-/*these next two return 1 if they did anything, or zero otherwise.*/
+/*these next two return 1 if they did anything, or zero otherwise.
+  they're kindof a hackish way to integrate with fkey, until
+  such time as fkey is completely bmeshafied.*/
 int BM_DissolveFaces(struct EditMesh *em, int flag);
 /*this doesn't display errors to the user, btw*/
 int BM_ConnectVerts(struct EditMesh *em, int flag);
diff --git a/source/blender/bmesh/intern/bmesh_mods.c b/source/blender/bmesh/intern/bmesh_mods.c
index 16e4909fe8a..29653b24b61 100644
--- a/source/blender/bmesh/intern/bmesh_mods.c
+++ b/source/blender/bmesh/intern/bmesh_mods.c
@@ -103,10 +103,11 @@ int BM_Dissolve_Disk(BMesh *bm, BMVert *v) {
 		  increasing valence to four.  this may be hackish. . .*/
 		loop = e->loop;
 		if (loop->v == v) loop = (BMLoop*) loop->head.next;
-		BM_Split_Face(bm, loop->f, v, loop->v, NULL, NULL, 0);
+		if (!BM_Split_Face(bm, loop->f, v, loop->v, NULL, NULL, 0))
+			return 0;
 
 		BM_Dissolve_Disk(bm, v);
-		return;
+		return 1;
 	} else if (keepedge == NULL && len == 2) {
 		/*handle two-valence*/
 		f = v->edge->loop->f;
@@ -114,6 +115,8 @@ int BM_Dissolve_Disk(BMesh *bm, BMVert *v) {
 		/*collapse the vertex*/
 		BM_Collapse_Vert(bm, v->edge, v, 1.0, 0);
 		BM_Join_Faces(bm, f, f2, NULL, 0, 0);
+
+		return 1;
 	}
 
 	if(keepedge){
@@ -143,11 +146,14 @@ int BM_Dissolve_Disk(BMesh *bm, BMVert *v) {
 		/*get remaining two faces*/
 		f = v->edge->loop->f;
 		f2 = ((BMLoop*)v->edge->loop->radial.next->data)->f;
+
 		/*collapse the vertex*/
 		BM_Collapse_Vert(bm, baseedge, v, 1.0, 0);
-
-		/*join two remaining faces*/
-		BM_Join_Faces(bm, f, f2, NULL, 0, 0);
+		
+		if (f != f2) {
+			/*join two remaining faces*/
+			if (!BM_Join_Faces(bm, f, f2, NULL, 0, 0)) return 0;
+		}
 	}
 
 	return 1;
diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c
index 3c7504c869e..28cf5d881c8 100644
--- a/source/blender/bmesh/intern/bmesh_opdefines.c
+++ b/source/blender/bmesh/intern/bmesh_opdefines.c
@@ -5,8 +5,8 @@
 
 BMOpDefine def_connectverts = {
 	"connectvert",
-	{BMOP_OPSLOT_PNT_BUF,
-	 BMOP_OPSLOT_PNT_BUF},
+	{{BMOP_OPSLOT_PNT_BUF, "verts"},
+	{BMOP_OPSLOT_PNT_BUF, "edgeout"}},
 	connectverts_exec,
 	BM_CONVERTS_TOTSLOT,
 	0
@@ -14,9 +14,9 @@ BMOpDefine def_connectverts = {
 
 BMOpDefine def_extrudefaceregion = {
 	"extrudefaceregion",
-	{BMOP_OPSLOT_PNT_BUF,
-	 BMOP_OPSLOT_MAPPING,
-	 BMOP_OPSLOT_PNT_BUF},
+	{{BMOP_OPSLOT_PNT_BUF, "edgefacein"},
+	{BMOP_OPSLOT_MAPPING, "exclude"},
+	{BMOP_OPSLOT_PNT_BUF, "geomout"}},
 	extrude_edge_context_exec,
 	BMOP_EXFACE_TOTSLOT,
 	0
@@ -32,7 +32,7 @@ BMOpDefine def_makefgonsop = {
 
 BMOpDefine def_dissolvevertsop = {
 	"dissolveverts",
-	{BMOP_OPSLOT_PNT_BUF},
+	{{BMOP_OPSLOT_PNT_BUF, "verts"}},
 	dissolveverts_exec,
 	BMOP_DISVERTS_TOTSLOT,
 	0
@@ -40,8 +40,8 @@ BMOpDefine def_dissolvevertsop = {
 
 BMOpDefine def_dissolvefacesop = {
 	"dissolvefaces",
-	{BMOP_OPSLOT_PNT_BUF,
-	 BMOP_OPSLOT_PNT_BUF},
+	{{BMOP_OPSLOT_PNT_BUF, "faces"},
+	{BMOP_OPSLOT_PNT_BUF, "regionnout"}},
 	dissolvefaces_exec,
 	BMOP_DISFACES_TOTSLOT,
 	0
@@ -50,9 +50,9 @@ BMOpDefine def_dissolvefacesop = {
 
 BMOpDefine def_triangop = {
 	"triangulate",
-	{BMOP_OPSLOT_PNT_BUF, 
-	 BMOP_OPSLOT_PNT_BUF,
-	 BMOP_OPSLOT_PNT_BUF},
+	{{BMOP_OPSLOT_PNT_BUF, "faces"},
+	{BMOP_OPSLOT_PNT_BUF, "edgeout"},
+	{BMOP_OPSLOT_PNT_BUF, "faceout"}},
 	triangulate_exec,
 	BMOP_TRIANG_TOTSLOT,
 	0
@@ -60,15 +60,15 @@ BMOpDefine def_triangop = {
 
 BMOpDefine def_subdop = {
 	"esubd",
-	{BMOP_OPSLOT_PNT_BUF,
-	 BMOP_OPSLOT_INT,
-	 BMOP_OPSLOT_INT,
-	 BMOP_OPSLOT_FLT,
-	 BMOP_OPSLOT_MAPPING,
-	 BMOP_OPSLOT_MAPPING,
-	 BMOP_OPSLOT_PNT_BUF,
-	 BMOP_OPSLOT_PNT_BUF,
-	 },
+	{{BMOP_OPSLOT_PNT_BUF, "edges"},
+	{BMOP_OPSLOT_INT, "numcuts"},
+	{BMOP_OPSLOT_INT, "flag"},
+	{BMOP_OPSLOT_FLT, "radius"},
+	{BMOP_OPSLOT_MAPPING, "custompatterns"},
+	{BMOP_OPSLOT_MAPPING, "edgepercents"},
+	{BMOP_OPSLOT_PNT_BUF, "outinner"},
+	{BMOP_OPSLOT_PNT_BUF, "outsplit"},
+	},
 	esubdivide_exec,
 	BMOP_ESUBDIVIDE_TOTSLOT,
 	0
@@ -76,7 +76,7 @@ BMOpDefine def_subdop = {
 
 BMOpDefine def_edit2bmesh = {
 	"editmesh_to_bmesh",
-	{BMOP_OPSLOT_PNT},
+	{{BMOP_OPSLOT_PNT, "emout"}},
 	edit2bmesh_exec,
 	BMOP_TO_EDITMESH_TOTSLOT,
 	0
@@ -84,7 +84,7 @@ BMOpDefine def_edit2bmesh = {
 
 BMOpDefine def_bmesh2edit = {
 	"bmesh_to_editmesh",
-	{BMOP_OPSLOT_PNT},
+	{{BMOP_OPSLOT_PNT, "em"}},
 	bmesh2edit_exec,
 	BMOP_FROM_EDITMESH_TOTSLOT,
 	0
@@ -92,7 +92,7 @@ BMOpDefine def_bmesh2edit = {
 
 BMOpDefine def_delop = {
 	"del",
-	{BMOP_OPSLOT_PNT_BUF, BMOP_OPSLOT_INT},
+	{{BMOP_OPSLOT_PNT_BUF, "geom"}, {BMOP_OPSLOT_INT, "context"}},
 	delop_exec,
 	BMOP_DEL_TOTSLOT,
 	0
@@ -100,8 +100,10 @@ BMOpDefine def_delop = {
 
 BMOpDefine def_dupeop = {
 	"dupe",
-	{BMOP_OPSLOT_PNT_BUF, BMOP_OPSLOT_PNT_BUF,
-	 BMOP_OPSLOT_PNT_BUF, BMOP_OPSLOT_MAPPING},
+	{{BMOP_OPSLOT_PNT_BUF, "geom"},
+	{BMOP_OPSLOT_PNT_BUF, "origout"},
+	{BMOP_OPSLOT_PNT_BUF, "newout"},
+	{BMOP_OPSLOT_MAPPING, "boundarymap"}},
 	dupeop_exec,
 	BMOP_DUPE_TOTSLOT,
 	0
@@ -109,8 +111,9 @@ BMOpDefine def_dupeop = {
 
 BMOpDefine def_splitop = {
 	"split",
-	{BMOP_OPSLOT_PNT_BUF,
-	 BMOP_OPSLOT_PNT_BUF, BMOP_OPSLOT_MAPPING},
+	{{BMOP_OPSLOT_PNT_BUF, "geom"},
+	{BMOP_OPSLOT_PNT_BUF, "geomout"},
+	{BMOP_OPSLOT_MAPPING, "boundarymap"}},
 	splitop_exec,
 	BMOP_SPLIT_TOTSLOT,
 	0
diff --git a/source/blender/bmesh/intern/bmesh_operators.c b/source/blender/bmesh/intern/bmesh_operators.c
index 2ece55c7e91..ef45284a1ff 100644
--- a/source/blender/bmesh/intern/bmesh_operators.c
+++ b/source/blender/bmesh/intern/bmesh_operators.c
@@ -93,7 +93,7 @@ void BMO_Init_Op(BMOperator *op, int opcode)
 	
 	/*initialize the operator slot types*/
 	for(i = 0; i < opdefines[opcode]->totslot; i++) {
-		op->slots[i].slottype = opdefines[opcode]->slottypes[i];
+		op->slots[i].slottype = opdefines[opcode]->slottypes[i].type;
 		op->slots[i].index = i;
 	}
 
@@ -369,8 +369,8 @@ void *BMO_Grow_Array(BMesh *bm, BMOperator *op, int slotcode, int totadd) {
 			slot->size = (slot->size+1+totadd)*2;
 
 			tmp = slot->data.buf;
-			slot->data.buf = MEM_callocN(BMOP_OPSLOT_TYPEINFO[opdefines[op->type]->slottypes[slotcode]] * slot->size, "opslot dynamic array");
-			memcpy(slot->data.buf, tmp, BMOP_OPSLOT_TYPEINFO[opdefines[op->type]->slottypes[slotcode]] * slot->size);
+			slot->data.buf = MEM_callocN(BMOP_OPSLOT_TYPEINFO[opdefines[op->type]->slottypes[slotcode].type] * slot->size, "opslot dynamic array");
+			memcpy(slot->data.buf, tmp, BMOP_OPSLOT_TYPEINFO[opdefines[op->type]->slottypes[slotcode].type] * slot->size);
 			MEM_freeN(tmp);
 		}
 
@@ -380,8 +380,8 @@ void *BMO_Grow_Array(BMesh *bm, BMOperator *op, int slotcode, int totadd) {
 		slot->len += totadd;
 		slot->size = slot->len+2;
 		tmp = slot->data.buf;
-		slot->data.buf = MEM_callocN(BMOP_OPSLOT_TYPEINFO[opdefines[op->type]->slottypes[slotcode]] * slot->len, "opslot dynamic array");
-		memcpy(slot->data.buf, tmp, BMOP_OPSLOT_TYPEINFO[opdefines[op->type]->slottypes[slotcode]] * slot->len);
+		slot->data.buf = MEM_callocN(BMOP_OPSLOT_TYPEINFO[opdefines[op->type]->slottypes[slotcode].type] * slot->len, "opslot dynamic array");
+		memcpy(slot->data.buf, tmp, BMOP_OPSLOT_TYPEINFO[opdefines[op->type]->slottypes[slotcode].type] * slot->len);
 	}
 
 	return slot->data.buf;
@@ -493,7 +493,7 @@ static void *alloc_slot_buffer(BMOperator *op, int slotcode, int len){
 	
 	op->slots[slotcode].len = len;
 	if(len)
-		op->slots[slotcode].data.buf = BLI_memarena_alloc(op->arena, BMOP_OPSLOT_TYPEINFO[opdefines[op->type]->slottypes[slotcode]] * len);
+		op->slots[slotcode].data.buf = BLI_memarena_alloc(op->arena, BMOP_OPSLOT_TYPEINFO[opdefines[op->type]->slottypes[slotcode].type] * len);
 	return op->slots[slotcode].data.buf;
 }
 
@@ -882,11 +882,27 @@ int bmesh_str_to_flag(char *str)
 
 #define nextc(fmt) ((fmt)[0] != 0 ? (fmt)[1] : 0)
 
+static int bmesh_name_to_slotcode(BMOpDefine *def, char *name)
+{
+	int i;
+
+	for (i=0; i<def->totslot; i++) {
+		if (!strcmp(name, def->slottypes[i].name)) return i;
+	}
+
+	return -1;
+}
+
 int BMO_VInitOpf(BMesh *bm, BMOperator *op, char *fmt, va_list vlist)
 {
-	int i, n=strlen(fmt), slotcode = -1, ret, type;
-	char *opname;
+	int i, n=strlen(fmt), stop, slotcode = -1, ret, type, state, c;
+	char *opname, *ofmt;
+	BMOpDefine *def;
+
+	/*we muck around in here, so dup it*/
+	fmt = ofmt = strdup(fmt);
 	
+	/*find operator name*/
 	i = strcspn(fmt, " \t");
 
 	opname = fmt;
@@ -899,52 +915,95 @@ int BMO_VInitOpf(BMesh *bm, BMOperator *op, char *fmt, va_list vlist)
 	}
 
 	if (i == bmesh_total_ops) return 0;
+	
 	BMO_Init_Op(op, i);
+	def = opdefines[i];
 	
 	i = 0;
+	state = 1; //0: not inside slotcode name, 1: inside slotcode name
+	c = 0;
+	
 	while (*fmt) {
-		switch (*fmt) {
-		case ' ':
-		case '\t':
-			break;
-		case '%':
-			slotcode += 1;
-			break;
-		case 'i':
-		case 'd':
-			BMO_Set_Int(op, slotcode, va_arg(vlist, int));
-			break;
-		case 'f':
-		case 'h':
-			type = *fmt;
-
-			if (nextc(fmt) == ' ' || nextc(fmt) == '\t') {
-				BMO_Set_Float(op,slotcode,va_arg(vlist,float));
-			} else {
-				switch (nextc(fmt)) {
-					case 'f': ret = BM_FACE; break;
-					case 'e': ret = BM_EDGE; break;
-					case 'v': ret = BM_VERT; break;
-					default: goto error;
+		if (state) {
+			/*jump past leading whitespace*/
+			i = strspn(fmt, " \t");
+			fmt += i;
+			
+			/*ignore trailing whitespace*/
+			if (!fmt[i])
+				break;
+
+			/*find end of slot name.  currently this is
+			  a little flexible, allowing "slot=%f", 
+			  "slot %f", "slot%f", and "slot\t%f". */
+			i = strcspn(fmt, "= \t%");
+			if (!fmt[i]) goto error;
+
+			fmt[i] = 0;
+			slotcode = bmesh_name_to_slotcode(def, fmt);
+			if (slotcode < 0) goto error;
+
+			state = 0;
+			fmt += i;
+		} else {
+			switch (*fmt) {
+			case ' ':
+			case '\t':
+			case '=':
+			case '%':
+				break;
+			case 'i':
+			case 'd':
+				BMO_Set_Int(op, slotcode, va_arg(vlist, int));
+				state = 1;
+				break;
+			case 'f':
+			case 'h':
+				type = *fmt;
+
+				if (nextc(fmt) == ' ' || nextc(fmt) == '\t' || 
+				    nextc(fmt)==0) 
+				{
+					BMO_Set_Float(op,slotcode,va_arg(vlist,double));
+				} else {
+					ret = 0;
+					stop = 0;
+					while (1) {
+					switch (nextc(fmt)) {
+						case 'f': ret |= BM_FACE;break;
+						case 'e': ret |= BM_EDGE;break;
+						case 'v': ret |= BM_VERT;break;
+						default:
+							stop = 1;
+							break;
+					}
+					if (stop) break;
+					fmt++;
+					}
+					
+					if (type == 'h')
+						BMO_HeaderFlag_To_Slot(bm, op, 
+						   slotcode, va_arg(vlist, int), ret);
+					else
+						BMO_Flag_To_Slot(bm, op, slotcode, 
+							     va_arg(vlist, int), ret);
 				}
-				
-				if (type == 'h')
-					BMO_HeaderFlag_To_Slot(bm, op, 
-					   slotcode, va_arg(vlist, int), ret);
-				else
-					BMO_Flag_To_Slot(bm, op, slotcode, 
-					             va_arg(vlist, int), ret);
-				fmt++;
+
+				state = 1;
+				break;
+			default:
+				printf("unrecognized bmop format char: %c\n", *fmt);
+				break;
 			}
-			break;
 		}
 		fmt++;
 	}
 
-
+	free(ofmt);
 	return 1;
 error:
 	BMO_Finish_Op(bm, op);
+	free(fmt);
 	return 0;
 }
 
diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c
index 149a356b5a6..dcd108f7edf 100644
--- a/source/blender/bmesh/intern/bmesh_polygon.c
+++ b/source/blender/bmesh/intern/bmesh_polygon.c
@@ -1,9 +1,14 @@
-#include "bmesh.h"
-#include "bmesh_private.h"
+#include <string.h>
 
-#include "BLI_arithb.h"
 #include "BKE_utildefines.h"
-#include <string.h>
+
+#include "BLI_arithb.h"
+#include "BLI_blenlib.h"
+
+#include "MEM_guardedalloc.h"
+
+#include "bmesh.h"
+#include "bmesh_private.h"
 
 /*
  *
@@ -99,6 +104,16 @@ static void compute_poly_normal(float normal[3], float (*verts)[3], int nverts)
 		u = verts[i];
 		v = verts[(i+1) % nverts];
 		
+		/* newell's method
+		
+		so thats?:
+		(a[1] - b[1]) * (a[2] + b[2]);
+		a[1]*b[2] - b[1]*a[2] - b[1]*b[2] + a[1]*a[2]
+
+		odd.  half of that is the cross product. . .what's the
+		other half?
+		*/
+
 		normal[0] += (u[1] - v[1]) * (u[2] + v[2]);
 		normal[1] += (u[2] - v[2]) * (u[0] + v[0]);
 		normal[2] += (u[0] - v[0]) * (u[1] + v[1]);
@@ -395,7 +410,260 @@ cleanup:
 	return ret;
 }
 
-static int goodline(float (*projectverts)[3], int v1i, int v2i, int nvert, float *outv)
+typedef struct qline {
+	struct qline *next, *prev;
+
+	float *a;
+	float *b;
+} qline;
+
+typedef struct quadnode {
+	float min[3], max[3];
+	struct quadnode *children[2][2];
+	ListBase lines;
+	int len;
+	int leaf;
+	int depth;
+} quadnode;
+
+typedef struct quadtree {
+	BLI_mempool *linepool, *nodepool;
+	quadnode *root;
+} quadtree;
+
+#define MAX_CHILD	5
+#define MAX_DEPTH	1
+
+#define D 0.0001f
+#define AABB(min, max, p) (p[0] >= min[0]-D && p[0] <= max[0]+D && p[1] >= min[1]-D && p[1] <= max[1]+D)
+
+static int quadnode_intersect_line(quadnode *node, qline *line) {
+	if (AABB(node->min, node->max, line->a)) return 1;
+	if (AABB(node->min, node->max, line->b)) return 1;
+	else {	
+		float v1[3], v2[3], v3[3], v4[3];
+		
+		VECCOPY(v1, node->min);
+		v2[0] = node->min[0];
+		v2[1] = node->max[1];
+		v2[2] = 0.0f;
+		VECCOPY(v3, node->max);
+		v4[0] = node->max[0];
+		v4[1] = node->min[1];
+		v4[2] = 0.0f;
+
+		if (linecrosses(v1, v2, line->a, line->b)) return 1;
+		if (linecrosses(v2, v3, line->a, line->b)) return 1;
+		if (linecrosses(v3, v4, line->a, line->b)) return 1;
+		if (linecrosses(v4, v1, line->a, line->b)) return 1;
+	}
+
+	return 0;
+}
+
+static void quadnode_insert(quadtree *tree, quadnode *node, qline *line) {
+	if (!node->leaf) {
+		int x, y;
+		for (x=0; x<2; x++) {
+			for (y=0; y<2; y++) {
+				if (quadnode_intersect_line(node->children[x][y], line)) {
+					quadnode_insert(tree, node->children[x][y], line);
+				}
+			}
+		}
+	} else {
+		if (node->len > MAX_CHILD && node->depth != MAX_DEPTH) {
+			qline *cline, *cnext;
+			quadnode *c;
+			int x, y;
+			float cell[2] = {(node->max[0]-node->min[0])/2, (node->max[1] - node->min[1])/2};
+
+			node->leaf = 0;
+			for (x=0; x<2; x++) {
+				for (y=0; y<2; y++) {
+					c = BLI_mempool_calloc(tree->nodepool);
+					node->children[x][y] = c;
+					c->min[0] = node->min[0] + cell[0]*x - 0.001f;
+					c->min[1] = node->min[1] + cell[1]*y - 0.001f;
+					c->min[2] = 0.0f;
+					c->max[0] = c->min[0] + cell[0] + 0.001f;
+					c->max[1] = c->min[1] + cell[1] + 0.001f;
+					c->max[2] = 0.0f;
+					c->leaf = 1;
+					c->depth = node->depth + 1;
+					c->lines.first = c->lines.last = NULL;
+				}
+			}
+
+			for (cline=node->lines.first; cline; cline=cnext) {
+				cnext = cline->next;
+
+				quadnode_insert(tree, node, cline);
+				BLI_mempool_free(tree->linepool, cline);
+			}
+			node->lines.first = node->lines.last = NULL;
+
+			quadnode_insert(tree, node, line);
+		} else {
+			qline *cpy = BLI_mempool_calloc(tree->linepool);
+			*cpy = *line;
+			BLI_addtail(&node->lines, cpy);
+			node->len++;
+		}
+	}
+}
+
+void quadtree_insert(quadtree *tree, float *a, float *b) {
+	qline line;
+
+	line.a = a;
+	line.b = b;
+	
+	quadnode_insert(tree, tree->root, &line);
+}
+
+quadtree *quadree_new(float *min, float *max) {
+	quadtree *tree = MEM_callocN(sizeof(*tree), "quadtree");
+	tree->linepool = BLI_mempool_create(sizeof(qline), 10, 32);
+	tree->nodepool = BLI_mempool_create(sizeof(quadnode), 10, 32);
+	
+	tree->root = BLI_mempool_calloc(tree->nodepool);
+	tree->root->leaf = 1;
+	VECCOPY(tree->root->min, min);
+	VECCOPY(tree->root->max, max);
+
+	return tree;
+}
+
+void quadtree_free(quadtree *tree) {
+	BLI_mempool_destroy(tree->linepool);
+	BLI_mempool_destroy(tree->nodepool);
+	MEM_freeN(tree);
+}
+
+
+static int goodline_one(quadnode *node, float *p, float *outv)
+{
+	if (!node->leaf) {
+		int x, y, ret=0;
+		qline line = {NULL, NULL, p, outv};
+
+		for (x=0; x<2; x++) {
+			for (y=0; y<2; y++) {
+				if (quadnode_intersect_line(node->children[x][y], &line)) {
+					ret += goodline_one(node->children[x][y], 
+					                    p, outv);
+				}
+			}
+		}
+
+		return ret;
+	} else {
+		float vv1[3], vv2[3], mid[3], a[3], b[3];
+		float v1[3], v2[3];
+		int lcount=0;
+		qline *line;
+		
+		for (line=node->lines.first; line; line=line->next) {
+			VECCOPY(vv1, line->a);
+			VECCOPY(vv2, line->b);
+			
+			VecAddf(mid, vv1, vv2);
+			VecMulf(mid, 0.5f);
+			
+			VecSubf(a, vv1, mid);
+			VecSubf(b, vv2, mid);
+			
+			VecMulf(a, 1.00001f);
+			VecMulf(b, 1.00001f);
+			
+			VecAddf(vv1, mid, a);
+			VecAddf(vv2, mid, b);
+					
+			if (linecrosses(vv1, vv2, p, outv)) lcount += 1;
+		}
+
+		return lcount;
+	}
+
+	return 0;
+}
+
+static int goodline_two(quadnode *node, float *v1, float *v2)
+{
+	/*the hardcoded stuff here, 0.999 and 1.0001, may be problems
+	  in the future, not sure. - joeedh*/
+
+	if (!node->leaf) {
+		int x, y, ret;
+		qline line = {NULL, NULL, v1, v2};
+
+		for (x=0; x<2; x++) {
+			for (y=0; y<2; y++) {
+				if (quadnode_intersect_line(node->children[x][y], &line)) {
+					ret = goodline_two(node->children[x][y], 
+					                   v1, v2);
+					if (!ret) return 0;
+				}
+			}
+		}
+
+		return 1;
+	} else {
+		float vv1[3], vv2[3], mid[3], a[3], b[3];
+		qline *line;
+
+		for (line=node->lines.first; line; line=line->next) {
+			VECCOPY(vv1, line->a);
+			VECCOPY(vv2, line->b);
+			
+			/*VecAddf(mid, vv1, vv2);
+			VecMulf(mid, 0.5f);
+			
+			VecSubf(a, vv1, mid);
+			VecSubf(b, vv2, mid);
+			
+			VecMulf(a, 0.999f);
+			VecMulf(b, 0.999f);
+			
+			VecAddf(vv1, mid, a);
+			VecAddf(vv2, mid, b);*/
+
+			if (linecrosses(vv1, vv2, v1, v2)) return 0;
+
+		}
+
+		return 1;
+	}
+
+	return 1;
+}
+
+static int goodline(quadnode *node, float (*projectverts)[3], int v1i,
+		    int v2i, int nvert, float *outv)
+{
+	float v1[3], v2[3], p[3], a[3], b[3];
+
+	VECCOPY(v1, projectverts[v1i]);
+	VECCOPY(v2, projectverts[v2i]);
+	VecAddf(p, v1, v2);
+	VecMulf(p, 0.5f);
+
+	VecSubf(a, v1, p);
+	VecSubf(b, v2, p);
+	VecMulf(a, 0.999f);
+	VecMulf(b, 0.999f);
+	
+	VecAddf(v1, a, p);
+	VecAddf(v2, b, p);
+
+	if (goodline_one(node, p, outv) % 2 == 0) return 0;
+	//if (!goodline_two(node, v1, v2)) return 0;
+
+	return 1;
+}
+
+static int goodline_old(float (*projectverts)[3], int v1i, int v2i, int nvert, float *outv)
 {
 	/*the hardcoded stuff here, 0.999 and 1.0001, may be problems
 	  in the future, not sure. - joeedh*/
@@ -453,7 +721,8 @@ static int goodline(float (*projectverts)[3], int v1i, int v2i, int nvert, float
  *
 */
 
-static BMLoop *find_ear(BMesh *bm, BMFace *f, float (*verts)[3], int nvert, float *outv)
+static BMLoop *find_ear(BMesh *bm, BMFace *f, quadtree *tree, 
+			float (*verts)[3], int nvert, float *outv)
 {
 	BMVert *v1, *v2, *v3;
 	BMLoop *bestear = NULL, *l;
@@ -470,7 +739,8 @@ static BMLoop *find_ear(BMesh *bm, BMFace *f, float (*verts)[3], int nvert, floa
 
 		if (BM_Edge_Exist(v1, v3)) isear = 0;
 
-		if (isear && !goodline(verts, v1->head.eflag2, v3->head.eflag2, nvert, outv))
+		if (isear && !goodline(tree->root, verts, v1->head.eflag2,
+		                       v3->head.eflag2, nvert, outv))
 			isear = 0;
 
 		if(isear){
@@ -510,7 +780,10 @@ void BM_Triangulate_Face(BMesh *bm, BMFace *f, float (*projectverts)[3], int new
 {
 	int i, done, nvert;
 	BMLoop *l, *newl, *nextloop;
+	BMVert *v;
+	quadtree *tree;
 	float outv[3] = {-1.0e30f, -1.0e30f, -1.0e30f};
+	float min[3] = {1.0e30f, 1.0e30f, 1.0e30f};;
 
 	/*copy vertex coordinates to vertspace array*/
 	i = 0;
@@ -519,15 +792,9 @@ void BM_Triangulate_Face(BMesh *bm, BMFace *f, float (*projectverts)[3], int new
 		VECCOPY(projectverts[i], l->v->co);
 		l->v->head.eflag2 = i; /*warning, abuse! never duplicate in tools code! never you hear?*/ /*actually, get rid of this completely, use a new structure for this....*/
 		i++;
-
-		outv[0] = MAX2(outv[0], l->v->co[0])+1.0f;
-		outv[1] = MAX2(outv[1], l->v->co[1])+1.0f;
-		outv[2] = MAX2(outv[2], l->v->co[2])+1.0f;
-
 		l = (BMLoop*)(l->head.next);
 	}while(l != f->loopbase);
 	
-	
 	//bmesh_update_face_normal(bm, f, projectverts);
 
 	compute_poly_normal(f->no, projectverts, f->len);	
@@ -535,21 +802,53 @@ void BM_Triangulate_Face(BMesh *bm, BMFace *f, float (*projectverts)[3], int new
 	poly_rotate_plane(f->no, projectverts, i);
 	
 	nvert = f->len;
-	
+
+	for (i=0; i<nvert; i++) {
+		outv[0] = MAX2(outv[0], projectverts[i][0]+0.01f);
+		outv[1] = MAX2(outv[1], projectverts[i][1]+0.01f);
+		outv[2] = MAX2(outv[2], projectverts[i][2]+0.01f);
+
+		min[0] = MIN2(min[0], projectverts[i][0]-0.01f);
+		min[1] = MIN2(min[1], projectverts[i][1]-0.01f);
+		min[2] = MIN2(min[2], projectverts[i][2]-0.01f);
+	}
+
+	outv[2] = 0.0f;
+	min[2] = 0.0f;
+
+	tree = quadree_new(min, outv);
+
+	outv[0] += 1.0f;
+	outv[1] += 1.0f;
+	for (i=0; i<nvert; i++) {
+		quadtree_insert(tree, projectverts[i], projectverts[(i+1)%nvert]);
+	}
+
 	done = 0;
 	while(!done && f->len > 3){
 		done = 1;
-		l = find_ear(bm, f, projectverts, nvert, outv);
+		l = find_ear(bm, f, tree, projectverts, nvert, outv);
 		if(l) {
 			done = 0;
+			v = l->v;
 			f = bmesh_sfme(bm, f, ((BMLoop*)(l->head.prev))->v, ((BMLoop*)(l->head.next))->v, &newl);
 			if (!f) {
 				printf("yeek! triangulator failed to split face!\n");
+				quadtree_free(tree);
 				break;
 			}
 
 			BMO_SetFlag(bm, newl->e, newedgeflag);
 			BMO_SetFlag(bm, f, newfaceflag);
+
+			/*l = f->loopbase;
+			do {
+				if (l->v == v) {
+					f->loopbase = l;
+					break;
+				}
+				l = l->head.next;
+			} while (l != f->loopbase);*/
 		}
 	}
 
@@ -560,6 +859,7 @@ void BM_Triangulate_Face(BMesh *bm, BMFace *f, float (*projectverts)[3], int new
 			f = bmesh_sfme(bm, l->f, l->v,nextloop->v, &newl);
 			if (!f) {
 				printf("triangle fan step of triangulator failed.\n");
+				quadtree_free(tree);
 				return;
 			}
 
@@ -568,4 +868,6 @@ void BM_Triangulate_Face(BMesh *bm, BMFace *f, float (*projectverts)[3], int new
 			l = nextloop;
 		}
 	}
+
+	quadtree_free(tree);
 }
diff --git a/source/blender/bmesh/operators/extrudeops.c b/source/blender/bmesh/operators/extrudeops.c
index dcc5d70e04e..316161eec9f 100644
--- a/source/blender/bmesh/operators/extrudeops.c
+++ b/source/blender/bmesh/operators/extrudeops.c
@@ -27,7 +27,6 @@ void extrude_edge_context_exec(BMesh *bm, BMOperator *op)
 
 	/*initialize our sub-operators*/
 	BMO_Init_Op(&dupeop, BMOP_DUPE);
-	BMO_Init_Op(&delop, BMOP_DEL);
 	
 	BMO_Flag_Buffer(bm, op, BMOP_EXFACE_EDGEFACEIN, EXT_INPUT);
 
@@ -76,8 +75,12 @@ void extrude_edge_context_exec(BMesh *bm, BMOperator *op)
 			BMO_SetFlag(bm, f, EXT_DEL);
 	}
 #endif
-	if (delorig) BMO_Flag_To_Slot(bm, &delop, BMOP_DEL_MULTIN, EXT_DEL, BM_ALL);
-	BMO_Set_Int(&delop, BMOP_DEL_CONTEXT, DEL_ONLYTAGGED);
+	//if (delorig) BMO_Flag_To_Slot(bm, &delop, BMOP_DEL_MULTIN, EXT_DEL, BM_ALL);
+	//BMO_Set_Int(&delop, BMOP_DEL_CONTEXT, DEL_ONLYTAGGED);
+	
+	if (delorig) BMO_InitOpf(bm, &delop, "del geom=%fvef context=%d", 
+	                         EXT_DEL, DEL_ONLYTAGGED);
+	else BMO_InitOpf(bm, &delop, "del context=%d", DEL_ONLYTAGGED);
 
 	BMO_CopySlot(op, &dupeop, BMOP_EXFACE_EDGEFACEIN, BMOP_DUPE_MULTIN);
 	
diff --git a/source/blender/bmesh/operators/subdivideop.c b/source/blender/bmesh/operators/subdivideop.c
index 11f52b38d16..41ec2593195 100644
--- a/source/blender/bmesh/operators/subdivideop.c
+++ b/source/blender/bmesh/operators/subdivideop.c
@@ -642,6 +642,7 @@ void esubdivide_exec(BMesh *bmesh, BMOperator *op)
 					b = V_COUNT(facedata)-1;
 					facedata[b].pat = pat;
 					facedata[b].start = verts[i];
+					BMO_SetFlag(bmesh, face, SUBD_SPLIT);
 					break;
 				}
 			}
@@ -743,24 +744,19 @@ void esubdivide_exec(BMesh *bmesh, BMOperator *op)
 void BM_esubdivideflag(Object *obedit, BMesh *bm, int selflag, float rad, 
 		       int flag, int numcuts, int seltype) {
 	BMOperator op;
-
-	BMO_Init_Op(&op, BMOP_ESUBDIVIDE);
-	
-	BMO_Set_Int(&op, BMOP_ESUBDIVIDE_NUMCUTS, numcuts);
-	BMO_Set_Int(&op, BMOP_ESUBDIVIDE_FLAG, flag);
-	BMO_Set_Float(&op, BMOP_ESUBDIVIDE_RADIUS, rad);
-	BMO_HeaderFlag_To_Slot(bm, &op, BMOP_ESUBDIVIDE_EDGES, selflag, BM_EDGE);
 	
+	BMO_InitOpf(bm, &op, "esubd edges=%he flag=%d radius=%f numcuts=%d",
+	            selflag, flag, rad, numcuts);
+
 	BMO_Exec_Op(bm, &op);
 
 	if (seltype == SUBDIV_SELECT_INNER) {
-		BMOpSlot *einput;
+		BMOIter iter;
 		BMHeader *ele;
 		int i;
 		
-		einput = BMO_GetSlot(&op, BMOP_ESUBDIVIDE_INNER_MULTOUT);
-		for (i=0; i<einput->len; i++) {
-			ele = ((BMHeader**)einput->data.p)[i];
+		ele = BMO_IterNew(&iter,bm,&op,BMOP_ESUBDIVIDE_INNER_MULTOUT);
+		for (; ele; ele=BMO_IterStep(&iter)) {
 			BM_Select(bm, ele, 1);
 		}
 	}
diff --git a/source/blender/editors/mesh/bmeshutils.c b/source/blender/editors/mesh/bmeshutils.c
index 2d3a3c9b193..c2f79c835c8 100644
--- a/source/blender/editors/mesh/bmeshutils.c
+++ b/source/blender/editors/mesh/bmeshutils.c
@@ -109,17 +109,37 @@ int EDBM_CallOpf(EditMesh *em, wmOperator *op, char *fmt, ...)
 
 	va_end(list);
 
-	return EDBM_Finish(bm, em, op);
-	return 1;
+	return EDBM_Finish(bm, em, op, 1);
+}
+
+int EDBM_CallOpfSilent(EditMesh *em, char *fmt, ...)
+{
+	BMesh *bm = editmesh_to_bmesh(em);
+	BMOperator bmop;
+	va_list list;
+
+	va_start(list, fmt);
+
+	if (!BMO_VInitOpf(bm, &bmop, fmt, list)) {
+		va_end(list);
+		return 0;
+	}
+
+	BMO_Exec_Op(bm, &bmop);
+	BMO_Finish_Op(bm, &bmop);
+
+	va_end(list);
+
+	return EDBM_Finish(bm, em, NULL, 0);
 }
 
 /*returns 0 on error, 1 on success*/
-int EDBM_Finish(BMesh *bm, EditMesh *em, wmOperator *op) {
+int EDBM_Finish(BMesh *bm, EditMesh *em, wmOperator *op, int report) {
 	EditMesh *em2;
 	char *errmsg;
 
 	if (BMO_GetError(bm, &errmsg, NULL)) {
-		BKE_report(op->reports, RPT_ERROR, errmsg);
+		if (report) BKE_report(op->reports, RPT_ERROR, errmsg);
 		BM_Free_Mesh(bm);
 		return 0;
 	}
diff --git a/source/blender/editors/mesh/editmesh_tools.c b/source/blender/editors/mesh/editmesh_tools.c
index cd6f208f6f0..bd4cd1ae705 100644
--- a/source/blender/editors/mesh/editmesh_tools.c
+++ b/source/blender/editors/mesh/editmesh_tools.c
@@ -1135,7 +1135,7 @@ static int delete_mesh_exec(bContext *C, wmOperator *op)
 		erase_vertices(em, &em->verts);
 	} 
 	else if(event==7) {
-		if (!EDBM_CallOpf(em, op, "dissolveverts %hv", BM_SELECT))
+		if (!EDBM_CallOpf(em, op, "dissolveverts verts=%hv",BM_SELECT))
 			return OPERATOR_CANCELLED;
 	}
 	else if(event==6) {
@@ -1243,7 +1243,8 @@ static int delete_mesh_exec(bContext *C, wmOperator *op)
 		if(em->selected.first) BLI_freelistN(&(em->selected));
 	}
 	else if(event==5) {
-		if (!EDBM_CallOpf(em, op, "del %hf %d", BM_SELECT, DEL_ONLYFACES))
+		if (!EDBM_CallOpf(em, op, "del geom=%hf context=%d",
+		                  BM_SELECT, DEL_ONLYFACES))
 			return OPERATOR_CANCELLED;
 		str= "Erase Only Faces";
 	}
diff --git a/source/blender/editors/mesh/mesh_intern.h b/source/blender/editors/mesh/mesh_intern.h
index 3d6a249ddc3..268a5596ba7 100644
--- a/source/blender/editors/mesh/mesh_intern.h
+++ b/source/blender/editors/mesh/mesh_intern.h
@@ -45,14 +45,18 @@ struct BMesh;
 #define UVCOPY(t, s) memcpy(t, s, 2 * sizeof(float));
 
 /* ******************** bmeshutils.c */
-/*calls EDBM_Finish*/
+/*calls a bmesh op, reporting errors to the user, doing conversions,
+  etc.*/
 int EDBM_CallOpf(EditMesh *em, struct wmOperator *op, char *fmt, ...);
+/*same as above, but doesn't report errors.*/
+int EDBM_CallOpfSilent(EditMesh *em, char *fmt, ...);
 
 /*called after bmesh tool exec.  checks for errors and does conversions.
   if any errors are raised by bmesh, it displays the error to the user and
   returns 0 (and does not convert).  otherwise, it converts the bmesh back
   into the editmesh, and returns 1.*/
-int EDBM_Finish(struct BMesh *bm, EditMesh *em, struct wmOperator *op);
+int EDBM_Finish(struct BMesh *bm, EditMesh *em, 
+                struct wmOperator *op, int report);
 
 
 /* ******************** editface.c */
diff --git a/source/blender/windowmanager/SConscript b/source/blender/windowmanager/SConscript
index 9f87272ee20..862235d7b4b 100644
--- a/source/blender/windowmanager/SConscript
+++ b/source/blender/windowmanager/SConscript
@@ -19,4 +19,4 @@ defs = []
 if not env['WITH_BF_PYTHON']:
 	defs.append('DISABLE_PYTHON')
 
-env.BlenderLib ( 'bf_windowmanager', sources, Split(incs), defs, libtype=['core'], priority=[100] )
+env.BlenderLib ( 'bf_windowmanager', sources, Split(incs), defs, libtype=['core'], priority=[5] )