Knifetool uses direct cutting instead of scanfill: fixes bugs 29908, 28963, 30333.

Knifetool accumulates a bunch of proposed cuts and when the user
confirms, it makes them all. The old code did this by using scanfill
to triangulate the cutting edges in their faces, and then merging
triangles where possible. This sometimes ended up with strange
lost faces, and also made it so that when holes were cut, the
surrounding face ended up totally triangulated. But 29908 was
an example of a lost face.

This new code directly finds chains of cutting edges that go from
one side of a face to the other and using BM_edge_split_n to make
the cuts. Holes are handled by finding two good places where
the hole can be connected to the containing face (using two
because I think some other code in bmesh assumes that there are
no edges that appear twice in a face).

The old code is still there with #if SCANFILL_CUTS, so can easily revert
if this proves to be a bad idea.

Also, a small fix to previously added BM_split_n (forgot to
copy face attributes to new face).

2 files changed, 683 insertions, 103 deletions

diff --git a/source/blender/bmesh/intern/bmesh_mods.c b/source/blender/bmesh/intern/bmesh_mods.c
index f00f6fa07b7..f47d9c0bc36 100644
--- a/source/blender/bmesh/intern/bmesh_mods.c
+++ b/source/blender/bmesh/intern/bmesh_mods.c
@@ -417,6 +417,9 @@ BMFace *BM_face_split_n(BMesh *bm, BMFace *f, BMVert *v1, BMVert *v2, float cos[
 	 * The radial_next is for f and goes from v2 to v1  */
 
 	if (nf) {
+		BM_elem_attrs_copy(bm, bm, f, nf);
+		copy_v3_v3(nf->no, f->no);
+
 		e = (*r_l)->e;
 		for (i = 0; i < n; i++) {
 			newv = bmesh_semv(bm, v2, e, &newe);
diff --git a/source/blender/editors/mesh/knifetool.c b/source/blender/editors/mesh/knifetool.c
index b026ddd19fb..5bea8a2ff5b 100644
--- a/source/blender/editors/mesh/knifetool.c
+++ b/source/blender/editors/mesh/knifetool.c
@@ -198,6 +198,18 @@ static void knife_append_list(knifetool_opdata *kcd, ListBase *lst, void *elem)
 	BLI_addtail(lst, ref);
 }
 
+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 KnifeEdge *new_knife_edge(knifetool_opdata *kcd)
 {
 	kcd->totkedge++;
@@ -213,9 +225,9 @@ static void knife_add_to_vert_edges(knifetool_opdata *kcd, KnifeEdge* kfe)
 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);
@@ -229,13 +241,13 @@ static KnifeVert *new_knife_vert(knifetool_opdata *kcd, float *co, float *cageco
 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_elem_index_get(v)]);
 		kfv->v = v;
 		BLI_ghash_insert(kcd->origvertmap, v, kfv);
 	}
-	
+
 	return kfv;
 }
 
@@ -246,7 +258,7 @@ static KnifeEdge *get_bm_knife_edge(knifetool_opdata *kcd, BMEdge *e)
 	if (!kfe) {
 		BMIter iter;
 		BMFace *f;
-		
+	
 		kfe = new_knife_edge(kcd);
 		kfe->e = e;
 		kfe->v1 = get_bm_knife_vert(kcd, e->v1);
@@ -264,7 +276,7 @@ static KnifeEdge *get_bm_knife_edge(knifetool_opdata *kcd, BMEdge *e)
 			knife_get_face_kedges(kcd, f);
 		}
 	}
-	
+
 	return kfe;
 }
 
@@ -278,7 +290,7 @@ static void knife_start_cut(knifetool_opdata *kcd)
 	kcd->is_space = 0;
 	kcd->prevmval[0] = kcd->vc.mval[0];
 	kcd->prevmval[1] = kcd->vc.mval[1];
-	
+
 	copy_v3_v3(kcd->prevco, kcd->vertco);
 	copy_v3_v3(kcd->prevcage, kcd->vertcage);
 
@@ -299,35 +311,23 @@ static void knife_start_cut(knifetool_opdata *kcd)
 	}
 }
 
-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 = knife_empty_list(kcd);
 		
 		BM_ITER(e, &iter, kcd->em->bm, BM_EDGES_OF_FACE, f) {
 			knife_append_list(kcd, lst, get_bm_knife_edge(kcd, e));
 		}
-		
+
 		BLI_ghash_insert(kcd->kedgefacemap, f, lst);
 	}
-	
+
 	return lst;
 }
 
@@ -336,7 +336,7 @@ 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;
@@ -373,69 +373,69 @@ static KnifeVert *knife_split_edge(knifetool_opdata *kcd, KnifeEdge *kfe, float
 {
 	KnifeEdge *newkfe = new_knife_edge(kcd);
 	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);
-	
+	float perc, cageco[3], l12;
+
+	l12 = len_v3v3(kfe->v1->co, kfe->v2->co);
+	if (l12 < FLT_EPSILON * 80) {
+		copy_v3_v3(cageco, kfe->v1->cageco);
+	} else {
+		perc = len_v3v3(co, kfe->v1->co) / l12;
+		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)
 		knife_edge_append_face(kcd, newkfe, ref->ref);
 
 	knife_add_to_vert_edges(kcd, newkfe);
-	
+
 	newkfe->draw = kfe->draw;
 	newkfe->e = kfe->e;
-	
+
 	*newkfe_out = newkfe;
-			
+
 	return newkfe->v2;
 }
 
 static void knife_add_single_cut(knifetool_opdata *kcd)
 {
 	KnifeEdge *kfe = new_knife_edge(kcd), *kfe2 = NULL, *kfe3 = NULL;
-	
+
 	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) {
+	} else if (kcd->prevedge) {
 		kfe->v1 = knife_split_edge(kcd, kcd->prevedge, kcd->prevco, &kfe2);
-	}
-	else {
+	} 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) {
+	} else if (kcd->curedge) {
 		kfe->v2 = knife_split_edge(kcd, kcd->curedge, kcd->vertco, &kfe3);
-	
 		kcd->curvert = kfe->v2;
-	}
-	else {
+	} else {
 		kfe->v2 = new_knife_vert(kcd, kcd->vertco, kcd->vertco);
 		kfe->v2->draw = !kcd->is_space;
 		kfe->v2->isface = 1;
@@ -446,11 +446,11 @@ static void knife_add_single_cut(knifetool_opdata *kcd)
 
 		kcd->curvert = kfe->v2;
 	}
-	
+
 	knife_find_basef(kcd, kfe);
-	
+
 	knife_add_to_vert_edges(kcd, kfe);
-	
+
 	if (kfe->basef && !find_ref(&kfe->faces, kfe->basef))
 		knife_edge_append_face(kcd, kfe, kfe->basef);
 
@@ -466,7 +466,7 @@ static void knife_add_single_cut(knifetool_opdata *kcd)
 			}
 		}
 	}
-		
+
 	/* set up for next cut */
 	kcd->prevbmface = kcd->curbmface;
 	kcd->prevvert = kcd->curvert;
@@ -657,29 +657,26 @@ static void knife_cut_through(knifetool_opdata *kcd)
 
 static void knife_add_cut(knifetool_opdata *kcd)
 {
-	/* BMEditMesh *em = kcd->em;*/ /* UNUSED */
 	knifetool_opdata oldkcd = *kcd;
-	
+
 	if (kcd->cut_through) {
 		knife_cut_through(kcd);
-	}
-	else if (kcd->linehits) {
+	} else 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) {
+			} else if (lastlh && firstlh) {
 				if (firstlh->v || lastlh->v) {
 					KnifeVert *kfv = firstlh->v ? firstlh->v : lastlh->v;
 					
@@ -691,21 +688,22 @@ static void knife_add_cut(knifetool_opdata *kcd)
 				}
 				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->prev_is_space = 0;
 				copy_v3_v3(kcd->prevco, lh->hit);
 				copy_v3_v3(kcd->prevcage, lh->cagehit);
+				kcd->prevvert = NULL;
 				kcd->prevedge = lh->kfe;
 				kcd->prevbmface = lh->f;
 				continue;
 			}			
-			
+
 			kcd->is_space = 0;
 			kcd->curedge = lh->kfe;
 			kcd->curbmface = lh->f;
@@ -715,7 +713,7 @@ static void knife_add_cut(knifetool_opdata *kcd)
 
 			knife_add_single_cut(kcd);
 		}
-		
+
 		if (oldkcd.is_space) {
 			kcd->prevbmface = oldkcd.curbmface;
 			kcd->prevvert = oldkcd.curvert;
@@ -730,10 +728,10 @@ static void knife_add_cut(knifetool_opdata *kcd)
 			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;
@@ -991,30 +989,6 @@ static void knifetool_draw(const bContext *UNUSED(C), ARegion *UNUSED(ar), void
 	glEnable(GL_DEPTH_TEST);
 }
 
-/* do we need to keep these functions? - campbell */
-
-static int UNUSED_FUNCTION(kfe_vert_in_edge)(KnifeEdge *e, KnifeVert *v)
-{
-	return e->v1 == v || e->v2 == v;
-}
-
-static int UNUSED_FUNCTION(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 float len_v3_tri_side_max(const float v1[3], const float v2[3], const float v3[3])
 {
 	const float s1 = len_v3v3(v1, v2);
@@ -1181,36 +1155,36 @@ static void knife_find_line_hits(knifetool_opdata *kcd)
 	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);
 	
+	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);
@@ -1222,17 +1196,17 @@ static void knife_find_line_hits(knifetool_opdata *kcd)
 	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);
 }
 
@@ -1569,12 +1543,12 @@ static int knife_update_active(knifetool_opdata *kcd)
 		knife_snap_angle(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
@@ -1602,6 +1576,9 @@ static int knife_update_active(knifetool_opdata *kcd)
 #define BOUNDARY		128
 #define FACE_NEW		256
 
+#define SCANFILL_CUTS 0
+#if SCANFILL_CUTS
+
 typedef struct facenet_entry {
 	struct facenet_entry *next, *prev;
 	KnifeEdge *kfe;
@@ -1952,12 +1929,612 @@ static void knifenet_fill_faces(knifetool_opdata *kcd)
 	BMO_pop(bm);
 }
 
+#else  /* use direct (non-scanfill) method for cuts */
+
+/* assuming v is on line ab, what fraction of the way is v from a to b? */
+static float frac_along(const float a[3], const float b[3], const float v[3]) {
+	float lab;
+
+	lab = len_v3v3(a, b);
+	if (lab == 0.0f)
+		return 0.0f;
+	else
+		return len_v3v3(a, v) / lab;
+}
+
+/* sort list of kverts by fraction along edge e */
+static void sort_by_frac_along(ListBase *lst, BMEdge *e) {
+	KnifeVert *vcur, *vprev;
+	float *v1co, *v2co;
+	Ref *cur = NULL, *prev = NULL, *next = NULL;
+
+	if (lst->first == lst->last)
+		return;
+
+	v1co = e->v1->co;
+	v2co = e->v2->co;
+
+	for (cur = ((Ref*)lst->first)->next; cur; cur = next) {
+		next = cur->next;
+		prev = cur->prev;
+
+		BLI_remlink(lst, cur);
+
+		vcur = cur->ref;
+		while (prev) {
+			vprev = prev->ref;
+			if (frac_along(v1co, v2co, vprev->co) <= frac_along(v1co, v2co, vcur->co))
+				break;
+			prev = prev->prev;
+		}
+
+		BLI_insertlinkafter(lst, prev, cur);
+	}
+}
+
+/* The chain so far goes from an instantiated vertex to kfv (some may be reversed).
+ * If possible, complete the chain to another instantiated vertex and return 1, else return 0.
+ * The visited hash says which KnifeVert's have already been tried, not including kfv. */
+static int find_chain_search(knifetool_opdata *kcd, KnifeVert *kfv,
+							 ListBase *fedges, SmallHash *visited, ListBase *chain) {
+	Ref *r;
+	KnifeEdge *kfe;
+	KnifeVert *kfv_other;
+
+	if (kfv->v)
+		return TRUE;
+
+	BLI_smallhash_insert(visited, (uintptr_t)kfv, NULL);
+	/* Try all possible next edges. Could either go through fedges
+	 * (all the KnifeEdges for the face being cut) or could go through
+	 * kve->edges and restrict to cutting face and uninstantiated edges.
+	 * Not clear which is better. Let's do the first. */
+	for (r = fedges->first; r; r = r->next) {
+		kfe = r->ref;
+		kfv_other = NULL;
+		if (kfe->v1 == kfv)
+			kfv_other = kfe->v2;
+		else if (kfe->v2 == kfv)
+			kfv_other = kfe->v1;
+		if (kfv_other && !BLI_smallhash_haskey(visited, (uintptr_t)kfv_other)) {
+			knife_append_list(kcd, chain, kfe);
+			if (find_chain_search(kcd, kfv_other, fedges, visited, chain))
+				return TRUE;
+			BLI_remlink(chain, chain->last);
+		}
+	}
+	return FALSE;
+}
+
+static ListBase * find_chain_from_vertex(knifetool_opdata *kcd, KnifeEdge *kfe,
+										 BMVert *v, ListBase *fedges) {
+	SmallHash visited_, *visited = &visited_;
+	ListBase *ans;
+	int found;
+
+	ans = knife_empty_list(kcd);
+	knife_append_list(kcd, ans, kfe);
+	found = 0;
+	BLI_smallhash_init(visited);
+	if (kfe->v1->v == v) {
+		BLI_smallhash_insert(visited, (uintptr_t)(kfe->v1), NULL);
+		found = find_chain_search(kcd, kfe->v2, fedges, visited, ans);
+	} else {
+		BLI_assert(kfe->v2->v == v);
+		BLI_smallhash_insert(visited, (uintptr_t)(kfe->v2), NULL);
+		found = find_chain_search(kcd, kfe->v1, fedges, visited, ans);
+	}
+
+	BLI_smallhash_release(visited);
+
+	if (found)
+		return ans;
+	else
+		return NULL;
+}
+
+/* Find a chain in fedges from one instantiated vertex to another.
+ * Remove the edges in the chain from fedges and return a separate list of the chain. */
+static ListBase * find_chain(knifetool_opdata *kcd, ListBase *fedges) {
+	Ref *r, *ref;
+	KnifeEdge *kfe;
+	BMVert *v1, *v2;
+	ListBase *ans;
+
+	ans = NULL;
+
+	for (r = fedges->first; r; r = r->next) {
+		kfe = r->ref;
+		v1 = kfe->v1->v;
+		v2 = kfe->v2->v;
+		if (v1 && v2) {
+			ans = knife_empty_list(kcd);
+			knife_append_list(kcd, ans, kfe);
+			break;
+		}
+		if (v1)
+			ans = find_chain_from_vertex(kcd, kfe, v1, fedges);
+		else if (v2)
+			ans = find_chain_from_vertex(kcd, kfe, v2, fedges);
+		if (ans)
+			break;
+	}
+	if (ans) {
+		BLI_assert(BLI_countlist(ans) > 0);
+		for (r = ans->first; r; r = r->next) {
+			ref = find_ref(fedges, r->ref);
+			BLI_assert(ref != NULL);
+			BLI_remlink(fedges, ref);
+		}
+	}
+	return ans;
+}
+
+/* The hole so far goes from kfvfirst to kfv (some may be reversed).
+ * If possible, complete the hole back to kfvfirst and return 1, else return 0.
+ * The visited hash says which KnifeVert's have already been tried, not including kfv or kfvfirst. */
+static int find_hole_search(knifetool_opdata *kcd, KnifeVert *kfvfirst, KnifeVert *kfv,
+							ListBase *fedges, SmallHash *visited, ListBase *hole) {
+	Ref *r;
+	KnifeEdge *kfe, *kfelast;
+	KnifeVert *kfv_other;
+
+	if (kfv == kfvfirst)
+		return TRUE;
+
+	BLI_smallhash_insert(visited, (uintptr_t)kfv, NULL);
+	kfelast = ((Ref*)hole->last)->ref;
+	for (r = fedges->first; r; r = r->next) {
+		kfe = r->ref;
+		if (kfe == kfelast)
+			continue;
+		kfv_other = NULL;
+		if (kfe->v1 == kfv)
+			kfv_other = kfe->v2;
+		else if (kfe->v2 == kfv)
+			kfv_other = kfe->v1;
+		if (kfv_other && !BLI_smallhash_haskey(visited, (uintptr_t)kfv_other)) {
+			knife_append_list(kcd, hole, kfe);
+			if (find_hole_search(kcd, kfvfirst, kfv_other, fedges, visited, hole))
+				return TRUE;
+			BLI_remlink(hole, hole->last);
+		}
+	}
+	return FALSE;
+}
+
+/* Find a hole (simple cycle with no instantiated vertices).
+ * Remove the edges in the cycle from fedges and return a separate list of the cycle */
+static ListBase *find_hole(knifetool_opdata *kcd, ListBase *fedges) {
+	ListBase *ans;
+	Ref *r, *ref;
+	KnifeEdge *kfe;
+	SmallHash visited_, *visited = &visited_;
+	int found;
+
+	ans = NULL;
+	found = FALSE;
+
+	for (r = fedges->first; r && !found; r = r->next) {
+		kfe = r->ref;
+		if (kfe->v1->v || kfe->v2->v || kfe->v1 == kfe->v2)
+			continue;
+
+		BLI_smallhash_init(visited);
+		ans = knife_empty_list(kcd);
+		knife_append_list(kcd, ans, kfe);
+
+		found = find_hole_search(kcd, kfe->v1, kfe->v2, fedges, visited, ans);
+
+		BLI_smallhash_release(visited);
+	}
+
+	if (found) {
+		for (r = ans->first; r; r = r->next) {
+			kfe = r->ref;
+			ref = find_ref(fedges, r->ref);
+			if (ref)
+				BLI_remlink(fedges, ref);
+		}
+		return ans;
+	} else {
+		return NULL;
+	}
+}
+
+/* Try to find "nice" diagonals - short, and far apart from each other.
+ * If found, return TRUE and make a 'main chain' going across f which uses
+ * the two diagonals and one part of the hole, and a 'side chain' that
+ * completes the hole. */
+static int find_hole_chains(knifetool_opdata *kcd, ListBase *hole, BMFace *f,
+					  ListBase **mainchain, ListBase **sidechain) {
+	float **fco, **hco;
+	BMVert **fv;
+	KnifeVert **hv;
+	KnifeEdge **he;
+	Ref *r;
+	KnifeVert *kfv;
+	KnifeEdge *kfe;
+	ListBase *chain;
+	BMVert *v;
+	BMIter iter;
+	int nh, nf, i, j, k, m, ax, ay, ok, sep, bestsep;
+	int besti[2], bestj[2];
+	float d, bestd;
+
+	nh = BLI_countlist(hole);
+	nf = f->len;
+	if (nh < 2 || nf < 3)
+		return 0;
+
+	/* Gather 2d projections of hole and face vertex coordinates.
+	 * Use best-axis projection - not completely accurate, maybe revisit */
+	axis_dominant_v3(&ax, &ay, f->no);
+	hco = BLI_memarena_alloc(kcd->arena, nh * sizeof(float*));
+	fco = BLI_memarena_alloc(kcd->arena, nf * sizeof(float*));
+	hv = BLI_memarena_alloc(kcd->arena, nh * sizeof(KnifeVert*));
+	fv = BLI_memarena_alloc(kcd->arena, nf * sizeof(BMVert*));
+	he = BLI_memarena_alloc(kcd->arena, nh * sizeof(KnifeEdge*));
+
+	i = 0;
+	kfv = NULL;
+	for (r = hole->first; r; r = r->next) {
+		kfe = r->ref;
+		he[i] = kfe;
+		kfv = (kfv == kfe->v1)? kfe->v2 : kfe->v1;
+		hco[i] = BLI_memarena_alloc(kcd->arena, 2*sizeof(float));
+		hco[i][0] = kfv->co[ax];
+		hco[i][1] = kfv->co[ay];
+		hv[i] = kfv;
+		i++;
+	}
+
+	j = 0;
+	BM_ITER(v, &iter, kcd->em->bm, BM_VERTS_OF_FACE, f) {
+		fco[j] = BLI_memarena_alloc(kcd->arena, 2*sizeof(float));
+		fco[j][0] = v->co[ax];
+		fco[j][1] = v->co[ay];
+		fv[j] = v;
+		j++;
+	}
+
+	/* For first diagonal (m==0), want shortest length.
+	 * For second diagonal (m==1), want max separation of index of hole
+	 * vertex from the hole vertex used in the first diagonal, and from there
+	 * want the one with shortest length. */
+	for (m = 0; m < 2; m++) {
+		besti[m] = -1;
+		bestj[m] = -1;
+		bestd = FLT_MAX;
+		bestsep = 0;
+		for (i = 0; i < nh; i++) {
+			if (m == 1) {
+				if (i == besti[0])
+					continue;
+				sep = (i + nh - besti[0]) % nh;
+				sep = MIN2(sep, nh - sep);
+				if (sep < bestsep)
+					continue;
+				bestd = FLT_MAX;
+			}
+			for (j = 0; j < nf; j++) {
+				d = len_squared_v2v2(hco[i], fco[j]);
+				if (d > bestd)
+					continue;
+
+				ok = TRUE;
+				for (k = 0; k < nh && ok; k++) {
+					if (k == i || (k+1) % nh == i)
+						continue;
+					if (isect_line_line_v2(hco[i], fco[j], hco[k], hco[(k+1) % nh]))
+						ok = FALSE;
+				}
+				if (!ok)
+					continue;
+				for (k = 0; k < nf && ok; k++) {
+					if (k == j || (k+1) % nf == j)
+						continue;
+					if (isect_line_line_v2(hco[i], fco[j], fco[k], fco[(k+1) % nf]))
+						ok = FALSE;
+				}
+				if (ok) {
+					besti[m] = i;
+					bestj[m] = j;
+					if (m == 1)
+						bestsep = sep;
+					bestd = d;
+				}
+			}
+		}
+	}
+
+	if (besti[0] != -1 && besti[1] != -1) {
+		kfe = new_knife_edge(kcd);
+		kfe->v1 = get_bm_knife_vert(kcd, fv[bestj[0]]);
+		kfe->v2 = hv[besti[0]];
+		chain = knife_empty_list(kcd);
+		knife_append_list(kcd, chain, kfe);
+		for (i = besti[0]; i != besti[1]; i = (i+1) % nh) {
+			knife_append_list(kcd, chain, he[i]);
+		}
+		kfe = new_knife_edge(kcd);
+		kfe->v1 = hv[besti[1]];
+		kfe->v2 = get_bm_knife_vert(kcd, fv[bestj[1]]);
+		knife_append_list(kcd, chain, kfe);
+		*mainchain = chain;
+
+		chain = knife_empty_list(kcd);
+		for (i = besti[1]; i != besti[0]; i = (i+1) % nh) {
+			knife_append_list(kcd, chain, he[i]);
+		}
+		*sidechain = chain;
+
+		return TRUE;
+	} else {
+		return FALSE;
+	}
+}
+
+static int knife_edge_in_face(knifetool_opdata *kcd, KnifeEdge *kfe, BMFace *f) {
+	BMesh *bm = kcd->em->bm;
+	BMVert *v1, *v2;
+	BMLoop *l1, *l2, *l, *loops[2];
+	BMIter iter;
+	int v1inside, v2inside;
+
+	v1 = kfe->v1->v;
+	v2 = kfe->v2->v;
+	l1 = NULL;
+	l2 = NULL;
+
+	/* find out if v1 and v2, if set, are part of the face */
+	BM_ITER(l, &iter, bm, BM_LOOPS_OF_FACE, f) {
+		if (v1 && l->v == v1)
+			l1 = l;
+		if (v2 && l->v == v2)
+			l2 = l;
+	}
+
+	/* BM_face_point_inside_test uses best-axis projection so this isn't most accurate test... */
+	v1inside = l1 ? 0 : BM_face_point_inside_test(bm, f, kfe->v1->co);
+	v2inside = l2 ? 0 : BM_face_point_inside_test(bm, f, kfe->v2->co);
+	if ((l1 && v2inside) || (l2 && v1inside) || (v1inside && v2inside))
+		return TRUE;
+	if (l1 && l2) {
+		/* Can have case where v1 and v2 are on shared chain between two faces.
+		 * BM_face_legal_splits does visibility and self-intersection tests. */
+		loops[0] = l1;
+		loops[1] = l2;
+		BM_face_legal_splits(bm, f, (BMLoop *(*)[2])loops, 1);
+		return (loops[0] != NULL);
+	}
+	return FALSE;
+}
+
+/* Split face f with KnifeEdges on chain.  f remains as one side, the face formed is put in *newface.
+ * The new face will be on the left side of the chain as viewed from the normal-out side of f. */
+static void knife_make_chain_cut(knifetool_opdata *kcd, BMFace *f, ListBase *chain, BMFace **newface) {
+	BMesh *bm = kcd->em->bm;
+	KnifeEdge *kfe, *kfelast;
+	BMVert *v1, *v2;
+	BMFace *fnew;
+	Ref *ref;
+	KnifeVert  *kfv, *kfvprev;
+	BMLoop *lnew, *l_iter;
+	int i;
+	int nco = BLI_countlist(chain) - 1;
+	float (*cos)[3] = NULL;
+	KnifeVert **kverts;
+	BLI_array_fixedstack_declare(cos, BM_NGON_STACK_SIZE, nco, __func__);
+	BLI_array_fixedstack_declare(kverts, BM_NGON_STACK_SIZE, nco, __func__);
+
+	kfe = ((Ref*)chain->first)->ref;
+	v1 = kfe->v1->v? kfe->v1->v : kfe->v2->v;
+	kfelast = ((Ref*)chain->last)->ref;
+	v2 = kfelast->v2->v? kfelast->v2->v : kfelast->v1->v;
+	BLI_assert(v1 != NULL && v2 != NULL);
+	kfvprev = kfe->v1->v == v1? kfe->v1 : kfe->v2;
+	for (ref = chain->first, i=0; i < nco && ref != chain->last; ref = ref->next, i++) {
+		kfe = ref->ref;
+		BLI_assert(kfvprev == kfe->v1 || kfvprev == kfe->v2);
+		kfv = kfe->v1 == kfvprev? kfe->v2 : kfe->v1;
+		copy_v3_v3(cos[i], kfv->co);
+		kverts[i] = kfv;
+		kfvprev = kfv;
+	}
+	BLI_assert(i == nco);
+	fnew = BM_face_split_n(bm, f, v1, v2, cos, nco, &lnew, NULL);
+	*newface = fnew;
+
+	/* Now go through lnew chain matching up chain kv's and assign real v's to them */
+	for (l_iter = lnew->next, i = 0; i < nco; l_iter = l_iter->next, i++) {
+		BLI_assert(equals_v3v3(cos[i], l_iter->v->co));
+		kverts[i]->v = l_iter->v;
+	}
+
+	BLI_array_fixedstack_free(cos);
+	BLI_array_fixedstack_free(kverts);
+}
+
+static void knife_make_face_cuts(knifetool_opdata *kcd, BMFace *f, ListBase *kfedges) {
+	BMesh *bm = kcd->em->bm;
+	KnifeEdge *kfe;
+	BMFace *fnew, *fnew2, *fhole;
+	ListBase *chain, *hole, *sidechain;
+	ListBase *fnew_kfedges, *fnew2_kfedges;
+	Ref *ref, *refnext;
+	int count, oldcount;
+
+	oldcount = BLI_countlist(kfedges);
+	while ((chain = find_chain(kcd, kfedges)) != NULL) {
+		knife_make_chain_cut(kcd, f, chain, &fnew);
+
+		/* Move kfedges to fnew_kfedges if they are now in fnew.
+		 * The chain edges were removed already */
+		fnew_kfedges = knife_empty_list(kcd);
+		for (ref = kfedges->first; ref; ref = refnext) {
+			kfe = ref->ref;
+			refnext = ref->next;
+			if (knife_edge_in_face(kcd, kfe, fnew)) {
+				BLI_remlink(kfedges, ref);
+				kfe->basef = fnew;
+				knife_append_list(kcd, fnew_kfedges, kfe);
+			}
+		}
+		if (fnew_kfedges->first)
+			knife_make_face_cuts(kcd, fnew, fnew_kfedges);
+
+		/* find_chain should always remove edges if it returns TRUE,
+		 * but guard against infinite loop anyway */
+		count = BLI_countlist(kfedges);
+		if (count >= oldcount) {
+			BLI_assert(!"knife find_chain infinite loop");
+			return;
+		}
+		oldcount = count;
+	}
+
+	while ((hole = find_hole(kcd, kfedges)) != NULL) {
+		if (find_hole_chains(kcd, hole, f, &chain, &sidechain)) {
+			/* chain goes across f and sidechain comes back
+			 * from the second last vertex to the second vertex.
+			  */
+			knife_make_chain_cut(kcd, f, chain, &fnew);
+			kfe = ((Ref*)sidechain->first)->ref;
+			if (knife_edge_in_face(kcd, kfe, f)) {
+				knife_make_chain_cut(kcd, f, sidechain, &fnew2);
+				fhole = f;
+			} else if (knife_edge_in_face(kcd, kfe, fnew)) {
+				knife_make_chain_cut(kcd, fnew, sidechain, &fnew2);
+				fhole = fnew2;
+			} else {
+				/* shouldn't happen */
+				BLI_assert(0);
+			}
+			BM_face_kill(bm, fhole);
+			/* Move kfedges to either fnew or fnew2 if appropriate.
+			 * The hole edges were removed already */
+			fnew_kfedges = knife_empty_list(kcd);
+			fnew2_kfedges = knife_empty_list(kcd);
+			for (ref = kfedges->first; ref; ref = refnext) {
+				kfe = ref->ref;
+				refnext = ref->next;
+				if (knife_edge_in_face(kcd, kfe, fnew)) {
+					BLI_remlink(kfedges, ref);
+					kfe->basef = fnew;
+					knife_append_list(kcd, fnew_kfedges, kfe);
+				} else if (knife_edge_in_face(kcd, kfe, fnew2)) {
+					BLI_remlink(kfedges, ref);
+					kfe->basef = fnew2;
+					knife_append_list(kcd, fnew2_kfedges, kfe);
+				}
+			}
+			/* We'll skip knife edges that are in the newly formed hole.
+			 * (Maybe we shouldn't have made a hole in the first place?) */
+			if (fnew != fhole && fnew_kfedges->first)
+				knife_make_face_cuts(kcd, fnew, fnew_kfedges);
+			if (fnew2 != fhole && fnew2_kfedges->first)
+				knife_make_face_cuts(kcd, fnew2, fnew2_kfedges);
+			if (f == fhole)
+				break;
+			/* find_hole should always remove edges if it returns TRUE,
+			 * but guard against infinite loop anyway */
+			count = BLI_countlist(kfedges);
+			if (count >= oldcount) {
+				BLI_assert(!"knife find_hole infinite loop");
+				return;
+			}
+			oldcount = count;
+		}
+	}
+}
+
+/* Use the network of KnifeEdges and KnifeVerts accumulated to make real BMVerts and BMEdedges */
+static void knife_make_cuts(knifetool_opdata *kcd)
+{
+	BMesh *bm = kcd->em->bm;
+	KnifeEdge *kfe;
+	KnifeVert *kfv;
+	BMFace *f;
+	BMEdge *e, *enew;
+	ListBase *lst;
+	Ref *ref;
+	float pct;
+	SmallHashIter hiter;
+	BLI_mempool_iter iter;
+	SmallHash fhash_, *fhash = &fhash_;
+	SmallHash ehash_, *ehash = &ehash_;
+
+	BLI_smallhash_init(fhash);
+	BLI_smallhash_init(ehash);
+
+	/* put list of cutting edges for a face into fhash, keyed by face */
+	BLI_mempool_iternew(kcd->kedges, &iter);
+	for (kfe = BLI_mempool_iterstep(&iter); kfe; kfe = BLI_mempool_iterstep(&iter)) {
+		f = kfe->basef;
+		if (!f || kfe->e)
+			continue;
+		lst = BLI_smallhash_lookup(fhash, (uintptr_t)f);
+		if (!lst) {
+			lst = knife_empty_list(kcd);
+			BLI_smallhash_insert(fhash, (uintptr_t)f, lst);
+		}
+		knife_append_list(kcd, lst, kfe);
+	}
+
+	/* put list of splitting vertices for an edge into ehash, keyed by edge */
+	BLI_mempool_iternew(kcd->kverts, &iter);
+	for (kfv = BLI_mempool_iterstep(&iter); kfv; kfv = BLI_mempool_iterstep(&iter)) {
+		if (kfv->v)
+			continue;  /* already have a BMVert */
+		for (ref = kfv->edges.first; ref; ref = ref->next) {
+			kfe = ref->ref;
+			e = kfe->e;
+			if (!e)
+				continue;
+			lst = BLI_smallhash_lookup(ehash, (uintptr_t)e);
+			if (!lst) {
+				lst = knife_empty_list(kcd);
+				BLI_smallhash_insert(ehash, (uintptr_t)e, lst);
+			}
+			/* there can be more than one kfe in kfv's list with same e */
+			if (!find_ref(lst, kfv))
+				knife_append_list(kcd, lst, kfv);
+		}
+	}
+
+	/* split bmesh edges where needed */
+	for (lst = BLI_smallhash_iternew(ehash, &hiter, (uintptr_t*)&e); lst;
+			lst = BLI_smallhash_iternext(&hiter, (uintptr_t*)&e)) {
+		sort_by_frac_along(lst, e);
+		for (ref = lst->first; ref; ref = ref->next) {
+			kfv = ref->ref;
+			pct = frac_along(e->v1->co, e->v2->co, kfv->co);
+			kfv->v = BM_edge_split(bm, e, e->v1, &enew, pct);
+		}
+	}
+
+	/* do cuts for each face */
+	for (lst = BLI_smallhash_iternew(fhash, &hiter, (uintptr_t*)&f); lst;
+			lst = BLI_smallhash_iternext(&hiter, (uintptr_t*)&f)) {
+		knife_make_face_cuts(kcd, f, lst);
+	}
+
+	BLI_smallhash_release(fhash);
+	BLI_smallhash_release(ehash);
+}
+#endif
+
 /* called on tool confirmation */
 static void knifetool_finish(bContext *C, wmOperator *op)
 {
 	knifetool_opdata *kcd = op->customdata;
 	
+#if SCANFILL_CUTS
 	knifenet_fill_faces(kcd);
+#else
+	knife_make_cuts(kcd);
+#endif
 	
 	DAG_id_tag_update(kcd->ob->data, OB_RECALC_DATA);
 	WM_event_add_notifier(C, NC_GEOM|ND_DATA, kcd->ob->data);