From 1fe21f29ec9134175aeb6ba9bf4bf3ddf9753e89 Mon Sep 17 00:00:00 2001
From: Campbell Barton <ideasman42@gmail.com>
Date: Fri, 14 Jun 2013 08:28:27 +0000
Subject: utility function for calculating smooth groups from sharp edges:
 BKE_mesh_calc_smoothgroups

---
 source/blender/blenkernel/BKE_mesh.h     |  4 ++
 source/blender/blenkernel/intern/mesh.c  | 85 ++++++++++++++++++++++++++++++++
 source/blender/blenlib/BLI_utildefines.h |  3 +-
 3 files changed, 91 insertions(+), 1 deletion(-)

(limited to 'source/blender')

diff --git a/source/blender/blenkernel/BKE_mesh.h b/source/blender/blenkernel/BKE_mesh.h
index 42ad9146b19..4f4a5a0c693 100644
--- a/source/blender/blenkernel/BKE_mesh.h
+++ b/source/blender/blenkernel/BKE_mesh.h
@@ -105,6 +105,10 @@ float BKE_mesh_calc_poly_area(struct MPoly *mpoly, struct MLoop *loopstart,
 void BKE_mesh_calc_poly_angles(struct MPoly *mpoly, struct MLoop *loopstart,
                                struct MVert *mvarray, float angles[]);
 
+int *BKE_mesh_calc_smoothgroups(const struct MEdge *medge, const int totedge,
+                                const struct MPoly *mpoly, const int totpoly,
+                                const struct MLoop *mloop, const int totloop);
+
 void BKE_mesh_calc_relative_deform(
         const struct MPoly *mpoly, const int totpoly,
         const struct MLoop *mloop, const int totvert,
diff --git a/source/blender/blenkernel/intern/mesh.c b/source/blender/blenkernel/intern/mesh.c
index 134b696e57d..aa45c8fd0aa 100644
--- a/source/blender/blenkernel/intern/mesh.c
+++ b/source/blender/blenkernel/intern/mesh.c
@@ -3203,6 +3203,91 @@ static float mesh_calc_poly_planar_area_centroid(MPoly *mpoly, MLoop *loopstart,
 	return total_area;
 }
 
+
+int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge,
+                                const MPoly *mpoly, const int totpoly,
+                                const MLoop *mloop, const int totloop)
+{
+	int *poly_groups = MEM_callocN(sizeof(int) * totpoly, __func__);
+	int *poly_stack  = MEM_mallocN(sizeof(int) * totpoly, __func__);
+	STACK_DECLARE(poly_stack);
+
+	int poly_prev = 0;
+	int poly_group_id = 1;
+
+	/* map vars */
+	MeshElemMap *edge_poly_map;
+	int *edge_poly_mem;
+
+	BKE_mesh_edge_poly_map_create(&edge_poly_map, &edge_poly_mem,
+	                              medge, totedge,
+	                              mpoly, totpoly,
+	                              mloop, totloop);
+
+	STACK_INIT(poly_stack);
+
+	while (true) {
+		int poly;
+
+		for (poly = poly_prev; poly < totpoly; poly++) {
+			if (poly_groups[poly] == 0) {
+				break;
+			}
+		}
+
+		if (poly == totpoly) {
+			/* all done */
+			break;
+		}
+
+		/* start searching from here next time */
+		poly_prev = poly + 1;
+
+		poly_groups[poly] = poly_group_id;
+		STACK_PUSH(poly_stack, poly);
+
+		while ((poly = STACK_POP_ELSE(poly_stack, -1)) != -1) {
+
+			const MPoly *mp = &mpoly[poly];
+			const MLoop *ml;
+			int j = mp->totloop;
+
+			BLI_assert(poly_groups[poly] == poly_group_id);
+
+			for (ml = &mloop[mp->loopstart]; j--; ml++) {
+				if (!(medge[ml->e].flag & ME_SHARP)) {
+					/* loop over poly users */
+					const MeshElemMap *map_ele = &edge_poly_map[ml->e];
+					int *p = map_ele->indices;
+					int i = map_ele->count;
+
+					for (; i--; p++) {
+						/* if we meet other non initialized its a bug */
+						BLI_assert(ELEM(poly_groups[*p], 0, poly_group_id));
+
+						if (poly_groups[*p] == 0) {
+							poly_groups[*p] = poly_group_id;
+							STACK_PUSH(poly_stack, *p);
+						}
+					}
+				}
+			}
+		}
+
+		poly_group_id++;
+	}
+
+	MEM_freeN(edge_poly_map);
+	MEM_freeN(edge_poly_mem);
+	MEM_freeN(poly_stack);
+
+	STACK_FREE(poly_stack);
+
+	return poly_groups;
+}
+
+
+
 /**
  * This function takes the difference between 2 vertex-coord-arrays
  * (\a vert_cos_src, \a vert_cos_dst),
diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h
index b49333fbb3c..224d02163cb 100644
--- a/source/blender/blenlib/BLI_utildefines.h
+++ b/source/blender/blenlib/BLI_utildefines.h
@@ -263,7 +263,8 @@
 #define STACK_PUSH(stack, val)  (void)((stack)[(_##stack##_index)++] = val)
 #define STACK_PUSH_RET(stack)  ((void)stack, ((stack)[(_##stack##_index)++]))
 #define STACK_PUSH_RET_PTR(stack)  ((void)stack, &((stack)[(_##stack##_index)++]))
-#define STACK_POP(stack)       ((_##stack##_index) ? ((stack)[--(_##stack##_index)]) : NULL)
+#define STACK_POP(stack)         ((_##stack##_index) ? ((stack)[--(_##stack##_index)]) : NULL)
+#define STACK_POP_ELSE(stack, r) ((_##stack##_index) ? ((stack)[--(_##stack##_index)]) : r)
 #define STACK_FREE(stack)      ((void)stack)
 
 /* array helpers */
-- 
cgit v1.2.3