From 66d51d461e9e4f7e069a6e7bb3feef19cabead94 Mon Sep 17 00:00:00 2001
From: Brecht Van Lommel <brechtvanlommel@pandora.be>
Date: Tue, 30 Sep 2008 17:06:41 +0000
Subject: Fix for bug #17691: edgesplit was crashing on windows on large meshes
 due to stack overflow.

---
 source/blender/blenkernel/intern/modifier.c | 71 +++++++++++++++++++++++++----
 1 file changed, 63 insertions(+), 8 deletions(-)

diff --git a/source/blender/blenkernel/intern/modifier.c b/source/blender/blenkernel/intern/modifier.c
index 2db4d66bd20..b9a60ca9329 100644
--- a/source/blender/blenkernel/intern/modifier.c
+++ b/source/blender/blenkernel/intern/modifier.c
@@ -2139,6 +2139,8 @@ typedef struct SmoothMesh {
 	DerivedMesh *dm;
 	float threshold; /* the cosine of the smoothing angle */
 	int flags;
+	MemArena *arena;
+	ListBase propagatestack, reusestack;
 } SmoothMesh;
 
 static SmoothVert *smoothvert_copy(SmoothVert *vert, SmoothMesh *mesh)
@@ -2221,6 +2223,9 @@ static void smoothmesh_free(SmoothMesh *mesh)
 
 	for(i = 0; i < mesh->num_edges; ++i)
 		BLI_linklist_free(mesh->edges[i].faces, NULL);
+	
+	if(mesh->arena)
+		BLI_memarena_free(mesh->arena);
 
 	MEM_freeN(mesh->verts);
 	MEM_freeN(mesh->edges);
@@ -2872,6 +2877,49 @@ static void split_single_vert(SmoothVert *vert, SmoothFace *face,
 	face_replace_vert(face, &repdata);
 }
 
+typedef struct PropagateEdge {
+	struct PropagateEdge *next, *prev;
+	SmoothEdge *edge;
+	SmoothVert *vert;
+} PropagateEdge;
+
+static void push_propagate_stack(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh)
+{
+	PropagateEdge *pedge = mesh->reusestack.first;
+
+	if(pedge) {
+		BLI_remlink(&mesh->reusestack, pedge);
+	}
+	else {
+		if(!mesh->arena) {
+			mesh->arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE);
+			BLI_memarena_use_calloc(mesh->arena);
+		}
+
+		pedge = BLI_memarena_alloc(mesh->arena, sizeof(PropagateEdge));
+	}
+
+	pedge->edge = edge;
+	pedge->vert = vert;
+	BLI_addhead(&mesh->propagatestack, pedge);
+}
+
+static void pop_propagate_stack(SmoothEdge **edge, SmoothVert **vert, SmoothMesh *mesh)
+{
+	PropagateEdge *pedge = mesh->propagatestack.first;
+
+	if(pedge) {
+		*edge = pedge->edge;
+		*vert = pedge->vert;
+		BLI_remlink(&mesh->propagatestack, pedge);
+		BLI_addhead(&mesh->reusestack, pedge);
+	}
+	else {
+		*edge = NULL;
+		*vert = NULL;
+	}
+}
+
 static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh);
 
 static void propagate_split(SmoothEdge *edge, SmoothVert *vert,
@@ -2949,7 +2997,7 @@ static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh)
 	if(!edge2) {
 		/* didn't find a sharp or loose edge, so try the other vert */
 		vert2 = other_vert(edge, vert);
-		propagate_split(edge, vert2, mesh);
+		push_propagate_stack(edge, vert2, mesh);
 	} else if(!edge_is_loose(edge2)) {
 		/* edge2 is not loose, so it must be sharp */
 		SmoothEdge *copy_edge = smoothedge_copy(edge, mesh);
@@ -2978,11 +3026,11 @@ static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh)
 		/* all copying and replacing is done; the mesh should be consistent.
 		* now propagate the split to the vertices at either end
 		*/
-		propagate_split(copy_edge, other_vert(copy_edge, vert2), mesh);
-		propagate_split(copy_edge2, other_vert(copy_edge2, vert2), mesh);
+		push_propagate_stack(copy_edge, other_vert(copy_edge, vert2), mesh);
+		push_propagate_stack(copy_edge2, other_vert(copy_edge2, vert2), mesh);
 
 		if(smoothedge_has_vert(edge, vert))
-			propagate_split(edge, vert, mesh);
+			push_propagate_stack(edge, vert, mesh);
 	} else {
 		/* edge2 is loose */
 		SmoothEdge *copy_edge = smoothedge_copy(edge, mesh);
@@ -3005,10 +3053,10 @@ static void split_edge(SmoothEdge *edge, SmoothVert *vert, SmoothMesh *mesh)
 		/* copying and replacing is done; the mesh should be consistent.
 		* now propagate the split to the vertex at the other end
 		*/
-		propagate_split(copy_edge, other_vert(copy_edge, vert2), mesh);
+		push_propagate_stack(copy_edge, other_vert(copy_edge, vert2), mesh);
 
 		if(smoothedge_has_vert(edge, vert))
-			propagate_split(edge, vert, mesh);
+			push_propagate_stack(edge, vert, mesh);
 	}
 
 	BLI_linklist_free(visited_faces, NULL);
@@ -3080,6 +3128,7 @@ static void tag_and_count_extra_edges(SmoothMesh *mesh, float split_angle,
 
 static void split_sharp_edges(SmoothMesh *mesh, float split_angle, int flags)
 {
+	SmoothVert *vert;
 	int i;
 	/* if normal1 dot normal2 < threshold, angle is greater, so split */
 	/* FIXME not sure if this always works */
@@ -3092,10 +3141,16 @@ static void split_sharp_edges(SmoothMesh *mesh, float split_angle, int flags)
 	for(i = 0; i < mesh->num_edges; i++) {
 		SmoothEdge *edge = &mesh->edges[i];
 
-		if(edge_is_sharp(edge, flags, mesh->threshold))
+		if(edge_is_sharp(edge, flags, mesh->threshold)) {
 			split_edge(edge, edge->verts[0], mesh);
-	}
 
+			do {
+				pop_propagate_stack(&edge, &vert, mesh);
+				if(edge && smoothedge_has_vert(edge, vert))
+					propagate_split(edge, vert, mesh);
+			} while(edge);
+		}
+	}
 }
 
 static int count_bridge_verts(SmoothMesh *mesh)
-- 
cgit v1.2.3