Improvements for knife tool execute function (code was a bit sloppy & could leak memory).

- vertex to screenspace projections were not checking for failure to project (vertex behind the view for eg).
- vertex screenspace 2d vectors were each malloc'd and added to own ghash, then fetched for each edge.
  now just store a vertex aligned array and do index lookups.
- projections were done in global space, now do them in object space (avoids a matrix multiply).
- error cases were commented out and would fail silently, now report them to the operator.
- remove MAX_CUTS hard coded limit, dynamically allocate the mouse path.
- add missing free calls in error cases.

1 files changed, 74 insertions, 65 deletions

diff --git a/source/blender/editors/mesh/editmesh_tools.c b/source/blender/editors/mesh/editmesh_tools.c
index 1d96a3a958d..23348eed2b4 100644
--- a/source/blender/editors/mesh/editmesh_tools.c
+++ b/source/blender/editors/mesh/editmesh_tools.c
@@ -2527,11 +2527,6 @@ void MESH_OT_solidify(wmOperatorType *ot)
 	RNA_def_property_ui_range(prop, -10, 10, 0.1, 4);
 }
 
-typedef struct CutCurve {
-	float x;
-	float y;
-} CutCurve;
-
 /* ******************************************************************** */
 /* Knife Subdivide Tool.  Subdivides edges intersected by a mouse trail
  * drawn by user.
@@ -2565,15 +2560,14 @@ static EnumPropertyItem knife_items[] = {
 
 /* bm_edge_seg_isect() Determines if and where a mouse trail intersects an BMEdge */
 
-static float bm_edge_seg_isect(BMEdge *e, CutCurve *c, int len, char mode,
-                               struct GHash *gh, int *isected)
+static float bm_edge_seg_isect(const float sco_a[2], const float sco_b[2],
+                               float (*mouse_path)[2], int len, char mode, int *isected)
 {
 #define MAXSLOPE 100000
 	float x11, y11, x12 = 0, y12 = 0, x2max, x2min, y2max;
 	float y2min, dist, lastdist = 0, xdiff2, xdiff1;
 	float m1, b1, m2, b2, x21, x22, y21, y22, xi;
 	float yi, x1min, x1max, y1max, y1min, perc = 0;
-	float  *scr;
 	float threshold = 0.0;
 	int i;
 	
@@ -2581,13 +2575,11 @@ static float bm_edge_seg_isect(BMEdge *e, CutCurve *c, int len, char mode,
 	// XXX threshold = scene->toolsettings->select_thresh / 100;
 	
 	/* Get screen coords of verts */
-	scr = BLI_ghash_lookup(gh, e->v1);
-	x21 = scr[0];
-	y21 = scr[1];
+	x21 = sco_a[0];
+	y21 = sco_a[1];
 	
-	scr = BLI_ghash_lookup(gh, e->v2);
-	x22 = scr[0];
-	y22 = scr[1];
+	x22 = sco_b[0];
+	y22 = sco_b[1];
 	
 	xdiff2 = (x22 - x21);
 	if (xdiff2) {
@@ -2609,11 +2601,11 @@ static float bm_edge_seg_isect(BMEdge *e, CutCurve *c, int len, char mode,
 				y11 = y12;
 			}
 			else {
-				x11 = c[i].x;
-				y11 = c[i].y;
+				x11 = mouse_path[i][0];
+				y11 = mouse_path[i][1];
 			}
-			x12 = c[i].x;
-			y12 = c[i].y;
+			x12 = mouse_path[i][0];
+			y12 = mouse_path[i][1];
 			
 			/* test e->v1 */
 			if ((x11 == x21 && y11 == y21) || (x12 == x21 && y12 == y21)) {
@@ -2637,11 +2629,11 @@ static float bm_edge_seg_isect(BMEdge *e, CutCurve *c, int len, char mode,
 			y11 = y12;
 		}
 		else {
-			x11 = c[i].x;
-			y11 = c[i].y;
+			x11 = mouse_path[i][0];
+			y11 = mouse_path[i][1];
 		}
-		x12 = c[i].x;
-		y12 = c[i].y;
+		x12 = mouse_path[i][0];
+		y12 = mouse_path[i][1];
 		
 		/* Perp. Distance from point to line */
 		if (m2 != MAXSLOPE) dist = (y12 - m2 * x12 - b2);  /* /sqrt(m2 * m2 + 1); Only looking for */
@@ -2719,9 +2711,9 @@ static float bm_edge_seg_isect(BMEdge *e, CutCurve *c, int len, char mode,
 		lastdist = dist;
 	}
 	return perc;
-} 
+}
 
-#define MAX_CUTS 2048
+#define ELE_EDGE_CUT 1
 
 static int edbm_knife_cut_exec(bContext *C, wmOperator *op)
 {
@@ -2733,76 +2725,93 @@ static int edbm_knife_cut_exec(bContext *C, wmOperator *op)
 	BMIter iter;
 	BMEdge *be;
 	BMOperator bmop;
-	CutCurve curve[MAX_CUTS];
-	struct GHash *gh;
 	float isect = 0.0f;
-	float  *scr, co[4];
-	int len = 0, isected;
+	int len = 0, isected, i;
 	short numcuts = 1, mode = RNA_int_get(op->ptr, "type");
+
+	/* allocd vars */
+	float (*screen_vert_coords)[2], (*sco)[2], (*mouse_path)[2];
 	
 	/* edit-object needed for matrix, and ar->regiondata for projections to work */
 	if (ELEM3(NULL, obedit, ar, ar->regiondata))
 		return OPERATOR_CANCELLED;
 	
 	if (bm->totvertsel < 2) {
-		//error("No edges are selected to operate on");
+		BKE_report(op->reports, RPT_ERROR, "No edges are selected to operate on");
 		return OPERATOR_CANCELLED;
 	}
 
+	len = RNA_collection_length(op->ptr, "path");
+
+	if (len < 2) {
+		BKE_report(op->reports, RPT_ERROR, "Mouse path too short");
+		return OPERATOR_CANCELLED;
+	}
+
+	mouse_path = MEM_mallocN(len * sizeof(*mouse_path), __func__);
+
 	/* get the cut curve */
 	RNA_BEGIN(op->ptr, itemptr, "path")
 	{
-		RNA_float_get_array(&itemptr, "loc", (float *)&curve[len]);
-		len++;
-		if (len >= MAX_CUTS) {
-			break;
-		}
+		RNA_float_get_array(&itemptr, "loc", (float *)&mouse_path[len]);
 	}
 	RNA_END;
-	
-	if (len < 2) {
-		return OPERATOR_CANCELLED;
-	}
+
+	/* for ED_view3d_project_float_object */
+	ED_view3d_init_mats_rv3d(obedit, ar->regiondata);
+
+	/* TODO, investigate using index lookup for screen_vert_coords() rather then a hash table */
 
 	/* the floating point coordinates of verts in screen space will be stored in a hash table according to the vertices pointer */
-	gh = BLI_ghash_ptr_new("knife cut exec");
-	for (bv = BM_iter_new(&iter, bm, BM_VERTS_OF_MESH, NULL); bv; bv = BM_iter_step(&iter)) {
-		scr = MEM_mallocN(sizeof(float) * 2, "Vertex Screen Coordinates");
-		copy_v3_v3(co, bv->co);
-		co[3] = 1.0f;
-		mul_m4_v4(obedit->obmat, co);
-		ED_view3d_project_float(ar, co, scr);
-		BLI_ghash_insert(gh, bv, scr);
+	screen_vert_coords = sco = MEM_mallocN(bm->totvert * sizeof(float) * 2, __func__);
+
+	BM_ITER_MESH_INDEX (bv, &iter, bm, BM_VERTS_OF_MESH, i) {
+		if (ED_view3d_project_float_object(ar, bv->co, *sco, V3D_PROJ_TEST_NOP) != V3D_PROJ_RET_SUCCESS) {
+			copy_v2_fl(*sco, FLT_MAX);  /* set error value */
+		}
+		BM_elem_index_set(bv, i); /* set_ok */
+		sco++;
+
 	}
+	bm->elem_index_dirty &= ~BM_VERT; /* clear dirty flag */
 
 	if (!EDBM_op_init(em, &bmop, op, "subdivide_edges")) {
+		MEM_freeN(mouse_path);
+		MEM_freeN(screen_vert_coords);
 		return OPERATOR_CANCELLED;
 	}
 
 	/* store percentage of edge cut for KNIFE_EXACT here.*/
 	for (be = BM_iter_new(&iter, bm, BM_EDGES_OF_MESH, NULL); be; be = BM_iter_step(&iter)) {
+		int is_cut = FALSE;
 		if (BM_elem_flag_test(be, BM_ELEM_SELECT)) {
-			isect = bm_edge_seg_isect(be, curve, len, mode, gh, &isected);
-			
-			if (isect != 0.0f) {
-				if (mode != KNIFE_MULTICUT && mode != KNIFE_MIDPOINT) {
-					BMO_slot_map_float_insert(bm, &bmop,
-					                          "edgepercents",
-					                          be, isect);
-
+			const float *sco_a = screen_vert_coords[BM_elem_index_get(be->v1)];
+			const float *sco_b = screen_vert_coords[BM_elem_index_get(be->v2)];
+
+			/* check for error value (vert cant be projected) */
+			if ((sco_a[0] != FLT_MAX) && (sco_b[0] != FLT_MAX)) {
+				isect = bm_edge_seg_isect(sco_a, sco_b, mouse_path, len, mode, &isected);
+
+				if (isect != 0.0f) {
+					if (mode != KNIFE_MULTICUT && mode != KNIFE_MIDPOINT) {
+						BMO_slot_map_float_insert(bm, &bmop,
+						                          "edgepercents",
+						                          be, isect);
+					}
 				}
-				BMO_elem_flag_enable(bm, be, 1);
 			}
-			else {
-				BMO_elem_flag_disable(bm, be, 1);
-			}
-		}
-		else {
-			BMO_elem_flag_disable(bm, be, 1);
 		}
+
+		BMO_elem_flag_set(bm, be, ELE_EDGE_CUT, is_cut);
 	}
-	
-	BMO_slot_buffer_from_enabled_flag(bm, &bmop, "edges", BM_EDGE, 1);
+
+
+	/* free all allocs */
+	MEM_freeN(screen_vert_coords);
+	MEM_freeN(mouse_path);
+
+
+	BMO_slot_buffer_from_enabled_flag(bm, &bmop, "edges", BM_EDGE, ELE_EDGE_CUT);
 
 	if (mode == KNIFE_MIDPOINT) numcuts = 1;
 	BMO_slot_int_set(&bmop, "numcuts", numcuts);
@@ -2817,14 +2826,14 @@ static int edbm_knife_cut_exec(bContext *C, wmOperator *op)
 	if (!EDBM_op_finish(em, &bmop, op, TRUE)) {
 		return OPERATOR_CANCELLED;
 	}
-	
-	BLI_ghash_free(gh, NULL, (GHashValFreeFP)MEM_freeN);
 
 	EDBM_update_generic(C, em, TRUE);
 
 	return OPERATOR_FINISHED;
 }
 
+#undef ELE_EDGE_CUT
+
 void MESH_OT_knife_cut(wmOperatorType *ot)
 {
 	PropertyRNA *prop;