[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