[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [59743] trunk/blender/source/blender/ blenkernel/intern/mesh.c: Fix [#36636] Incorrect assignment of Smoothing Groups on export

Bastien Montagne montagne29 at wanadoo.fr
Mon Sep 2 19:14:41 CEST 2013


Revision: 59743
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=59743
Author:   mont29
Date:     2013-09-02 17:14:41 +0000 (Mon, 02 Sep 2013)
Log Message:
-----------
Fix [#36636] Incorrect assignment of Smoothing Groups on export

In fact, smooth groups are supposed to be bitflags, not simply integer values (would be far too much simple!). This adds quite a bit of work, as with only 32 values, we can't just assign one to each group. Somewhat related to the "Four colors theorem"! ;)

Here we simply use the first available bit for current smooth group (i.e. first bit not used by any of the already defined contiguous groups).

Modified Paths:
--------------
    trunk/blender/source/blender/blenkernel/intern/mesh.c

Modified: trunk/blender/source/blender/blenkernel/intern/mesh.c
===================================================================
--- trunk/blender/source/blender/blenkernel/intern/mesh.c	2013-09-02 17:08:03 UTC (rev 59742)
+++ trunk/blender/source/blender/blenkernel/intern/mesh.c	2013-09-02 17:14:41 UTC (rev 59743)
@@ -3312,7 +3312,7 @@
  * Calculate smooth groups from sharp edges.
  *
  * \param r_totgroup The total number of groups, 1 or more.
- * \return Polygon aligned array of group index values (starting at 1)
+ * \return Polygon aligned array of group index values (bitflags, starting at 1).
  */
 int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge,
                                 const MPoly *mpoly, const int totpoly,
@@ -3321,10 +3321,12 @@
 {
 	int *poly_groups;
 	int *poly_stack;
-	STACK_DECLARE(poly_stack);
 
 	int poly_prev = 0;
-	int poly_group_id = 0;
+	const int temp_poly_group_id = 3;  /* Placeholder value. */
+	const int poly_group_id_overflowed = 5;  /* Group we could not find any available bit, will be reset to 0 at end */
+	int tot_group = 0;
+	bool group_id_overflow = false;
 
 	/* map vars */
 	MeshElemMap *edge_poly_map;
@@ -3343,10 +3345,10 @@
 	poly_groups = MEM_callocN(sizeof(int) * totpoly, __func__);
 	poly_stack  = MEM_mallocN(sizeof(int) * totpoly, __func__);
 
-	STACK_INIT(poly_stack);
-
 	while (true) {
 		int poly;
+		int bit_poly_group_mask = 0;
+		int ps_curr_idx = 0, ps_end_idx = 0;  /* stack indices */
 
 		for (poly = poly_prev; poly < totpoly; poly++) {
 			if (poly_groups[poly] == 0) {
@@ -3362,49 +3364,92 @@
 		/* start searching from here next time */
 		poly_prev = poly + 1;
 
-		/* group starts at 1 */
-		poly_group_id++;
+		poly_groups[poly] = temp_poly_group_id;
+		poly_stack[ps_end_idx++] = poly;
 
-		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];
+		while (ps_curr_idx != ps_end_idx) {
+			const MPoly *mp;
 			const MLoop *ml;
-			int j = mp->totloop;
+			int j;
 
-			BLI_assert(poly_groups[poly] == poly_group_id);
+			poly = poly_stack[ps_curr_idx++];
+			BLI_assert(poly_groups[poly] == temp_poly_group_id);
 
-			for (ml = &mloop[mp->loopstart]; j--; ml++) {
+			mp = &mpoly[poly];
+			for (ml = &mloop[mp->loopstart], j = mp->totloop; j--; ml++) {
+				/* loop over poly users */
+				const MeshElemMap *map_ele = &edge_poly_map[ml->e];
+				int *p = map_ele->indices;
+				int i = map_ele->count;
 				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));
+						BLI_assert(ELEM(poly_groups[*p], 0, temp_poly_group_id));
 
 						if (poly_groups[*p] == 0) {
-							poly_groups[*p] = poly_group_id;
-							STACK_PUSH(poly_stack, *p);
+							poly_groups[*p] = temp_poly_group_id;
+							poly_stack[ps_end_idx++] = *p;
 						}
 					}
 				}
+				else {
+					/* Find contiguous smooth groups already assigned, these are the values we can't reuse! */
+					for (; i--; p++) {
+						int bit = poly_groups[*p];
+						if (!ELEM3(bit, 0, temp_poly_group_id, poly_group_id_overflowed) &&
+						    !(bit_poly_group_mask & bit))
+						{
+							bit_poly_group_mask |= bit;
+						}
+					}
+				}
 			}
 		}
+		/* And now, we have all our poly from current group in poly_stack (from 0 to (ps_end_idx - 1)), as well as
+		 * all smoothgroups bits we can't use in bit_poly_group_mask.
+		 */
+		{
+			int i, *p, gid_bit = 0, poly_group_id = 1;
+
+			/* Find first bit available! */
+			for (; (poly_group_id & bit_poly_group_mask) && (gid_bit < 32); gid_bit++) {
+				poly_group_id <<= 1;  /* will 'overflow' on last possible iteration. */
+			}
+			if (UNLIKELY(gid_bit > 31)) {
+				/* All bits used in contiguous smooth groups, we can't do much!
+				 * Note: this is *very* unlikely - theoretically, four groups are enough, I don't think we can reach
+				 *       this goal with such a simple algo, but I don't think either we'll never need all 32 groups!
+				 */
+				printf("Warning, could not find an available id for current smooth group, faces will me marked "
+				       "as out of any smooth group...\n");
+				poly_group_id = poly_group_id_overflowed; /* Can't use 0, will have to set them to this value later. */
+				group_id_overflow = true;
+			}
+			if (gid_bit > tot_group) {
+				tot_group = gid_bit;
+			}
+			/* And assign the final smooth group id to that poly group! */
+			for (i = ps_end_idx, p = poly_stack; i--; p++) {
+				poly_groups[*p] = poly_group_id;
+			}
+		}
 	}
 
+	if (UNLIKELY(group_id_overflow)) {
+		int i = totpoly, *gid = poly_groups;
+		for (; i--; gid++) {
+			if (*gid == poly_group_id_overflowed) {
+				*gid = 0;
+			}
+		}
+	}
+
 	MEM_freeN(edge_poly_map);
 	MEM_freeN(edge_poly_mem);
 	MEM_freeN(poly_stack);
 
-	STACK_FREE(poly_stack);
+	*r_totgroup = tot_group + 1;
 
-	*r_totgroup = poly_group_id;
-
 	return poly_groups;
 }
 




More information about the Bf-blender-cvs mailing list