diff options
author | Bastien Montagne <montagne29@wanadoo.fr> | 2013-09-02 21:14:41 +0400 |
---|---|---|
committer | Bastien Montagne <montagne29@wanadoo.fr> | 2013-09-02 21:14:41 +0400 |
commit | 6ac7b03b2c74ce00d2e5b4bed58355d243adaff8 (patch) | |
tree | 2c9fe13f8022ec22a8a7053e16d87b748c0aa765 /source/blender/blenkernel/intern/mesh.c | |
parent | 834e47dbacbc063ed134c4657ba929da2e6e5a14 (diff) |
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).
Diffstat (limited to 'source/blender/blenkernel/intern/mesh.c')
-rw-r--r-- | source/blender/blenkernel/intern/mesh.c | 99 |
1 files changed, 72 insertions, 27 deletions
diff --git a/source/blender/blenkernel/intern/mesh.c b/source/blender/blenkernel/intern/mesh.c index 0d3bc1b71e3..05edeebfafc 100644 --- a/source/blender/blenkernel/intern/mesh.c +++ b/source/blender/blenkernel/intern/mesh.c @@ -3312,7 +3312,7 @@ static float mesh_calc_poly_planar_area_centroid(MPoly *mpoly, MLoop *loopstart, * 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 *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge, { 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 @@ int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge, 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,48 +3364,91 @@ int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge, /* start searching from here next time */ poly_prev = poly + 1; - /* group starts at 1 */ - poly_group_id++; - - poly_groups[poly] = poly_group_id; - STACK_PUSH(poly_stack, poly); - - while ((poly = STACK_POP_ELSE(poly_stack, -1)) != -1) { + poly_groups[poly] = temp_poly_group_id; + poly_stack[ps_end_idx++] = poly; - 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 = poly_group_id; + *r_totgroup = tot_group + 1; return poly_groups; } |