diff options
Diffstat (limited to 'source/blender/blenkernel/intern/mesh_mapping.c')
| -rw-r--r-- | source/blender/blenkernel/intern/mesh_mapping.c | 380 |
1 files changed, 337 insertions, 43 deletions
diff --git a/source/blender/blenkernel/intern/mesh_mapping.c b/source/blender/blenkernel/intern/mesh_mapping.c index 53d1aae104c..8d9fbe46f19 100644 --- a/source/blender/blenkernel/intern/mesh_mapping.c +++ b/source/blender/blenkernel/intern/mesh_mapping.c @@ -32,10 +32,12 @@ #include "DNA_meshdata_types.h" #include "BLI_utildefines.h" +#include "BLI_bitmap.h" #include "BLI_math.h" #include "BKE_mesh_mapping.h" #include "BKE_customdata.h" +#include "BLI_memarena.h" #include "BLI_strict_flags.h" @@ -156,18 +158,25 @@ void BKE_mesh_uv_vert_map_free(UvVertMap *vmap) } } -/* Generates a map where the key is the vertex and the value is a list - * of polys that use that vertex as a corner. The lists are allocated - * from one memory pool. */ -void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem, - const MPoly *mpoly, const MLoop *mloop, - int totvert, int totpoly, int totloop) +/** + + + * Generates a map where the key is the vertex and the value is a list + * of polys or loops that use that vertex as a corner. The lists are allocated + * from one memory pool. + * + * Wrapped by #BKE_mesh_vert_poly_map_create & BKE_mesh_vert_loop_map_create + */ +static void mesh_vert_poly_or_loop_map_create( + MeshElemMap **r_map, int **r_mem, + const MPoly *mpoly, const MLoop *mloop, + int totvert, int totpoly, int totloop, const bool do_loops) { - MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * (size_t)totvert, "vert poly map"); + MeshElemMap *map = MEM_callocN(sizeof(MeshElemMap) * (size_t)totvert, __func__); int *indices, *index_iter; int i, j; - indices = index_iter = MEM_mallocN(sizeof(int) * (size_t)totloop, "vert poly map mem"); + indices = index_iter = MEM_mallocN(sizeof(int) * (size_t)totloop, __func__); /* Count number of polys for each vertex */ for (i = 0; i < totpoly; i++) { @@ -193,7 +202,7 @@ void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem, for (j = 0; j < p->totloop; j++) { unsigned int v = mloop[p->loopstart + j].v; - map[v].indices[map[v].count] = i; + map[v].indices[map[v].count] = do_loops ? p->loopstart + j : i; map[v].count++; } } @@ -202,6 +211,28 @@ void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem, *r_mem = indices; } +/** + * Generates a map where the key is the vertex and the value is a list of polys that use that vertex as a corner. + * The lists are allocated from one memory pool. + */ +void BKE_mesh_vert_poly_map_create(MeshElemMap **r_map, int **r_mem, + const MPoly *mpoly, const MLoop *mloop, + int totvert, int totpoly, int totloop) +{ + mesh_vert_poly_or_loop_map_create(r_map, r_mem, mpoly, mloop, totvert, totpoly, totloop, false); +} + +/** + * Generates a map where the key is the vertex and the value is a list of loops that use that vertex as a corner. + * The lists are allocated from one memory pool. + */ +void BKE_mesh_vert_loop_map_create(MeshElemMap **r_map, int **r_mem, + const MPoly *mpoly, const MLoop *mloop, + int totvert, int totpoly, int totloop) +{ + mesh_vert_poly_or_loop_map_create(r_map, r_mem, mpoly, mloop, totvert, totpoly, totloop, true); +} + /* Generates a map where the key is the vertex and the value is a list * of edges that use that vertex as an endpoint. The lists are allocated * from one memory pool. */ @@ -345,26 +376,30 @@ void BKE_mesh_origindex_map_create(MeshElemMap **r_map, int **r_mem, /** \} */ - /* -------------------------------------------------------------------- */ -/** \name Mesh Smooth Groups +/** \name Mesh loops/poly islands. + * Used currently for UVs and 'smooth groups'. * \{ */ -/** - * 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 (bitflags if use_bitflags is true), starting at 1. +/** Callback deciding whether the given poly/loop/edge define an island boundary or not. */ -int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge, - const MPoly *mpoly, const int totpoly, - const MLoop *mloop, const int totloop, - int *r_totgroup, const bool use_bitflags) +typedef bool (*MeshRemap_CheckIslandBoundary)( + const struct MPoly *mpoly, const struct MLoop *mloop, const struct MEdge *medge, + const int nbr_egde_users); + +static void poly_edge_loop_islands_calc( + const MEdge *medge, const int totedge, const MPoly *mpoly, const int totpoly, + const MLoop *mloop, const int totloop, MeshElemMap *edge_poly_map, + const bool use_bitflags, MeshRemap_CheckIslandBoundary edge_boundary_check, + int **r_poly_groups, int *r_totgroup, BLI_bitmap **r_edge_borders, int *r_totedgeborder) { int *poly_groups; int *poly_stack; + BLI_bitmap *edge_borders = NULL; + int num_edgeborders = 0; + int poly_prev = 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 */ @@ -372,18 +407,27 @@ int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge, bool group_id_overflow = false; /* map vars */ - MeshElemMap *edge_poly_map; - int *edge_poly_mem; + int *edge_poly_mem = NULL; if (totpoly == 0) { *r_totgroup = 0; - return NULL; + *r_poly_groups = NULL; + if (r_edge_borders) { + *r_edge_borders = NULL; + *r_totedgeborder = 0; + } + return; } - BKE_mesh_edge_poly_map_create(&edge_poly_map, &edge_poly_mem, - medge, totedge, - mpoly, totpoly, - mloop, totloop); + if (r_edge_borders) { + edge_borders = BLI_BITMAP_NEW(totedge, __func__); + *r_totedgeborder = 0; + } + + if (!edge_poly_map) { + BKE_mesh_edge_poly_map_create(&edge_poly_map, &edge_poly_mem, + medge, totedge, mpoly, totpoly, mloop, totloop); + } poly_groups = MEM_callocN(sizeof(int) * (size_t)totpoly, __func__); poly_stack = MEM_mallocN(sizeof(int) * (size_t)totpoly, __func__); @@ -416,22 +460,20 @@ int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge, while (ps_curr_idx != ps_end_idx) { const MPoly *mp; const MLoop *ml; - bool sharp_poly; int j; poly = poly_stack[ps_curr_idx++]; BLI_assert(poly_groups[poly] == poly_group_id); mp = &mpoly[poly]; - sharp_poly = !(mp->flag & ME_SMOOTH); for (ml = &mloop[mp->loopstart], j = mp->totloop; j--; ml++) { /* loop over poly users */ - const MeshElemMap *map_ele = &edge_poly_map[ml->e]; + const int me_idx = (int)ml->e; + const MEdge *me = &medge[me_idx]; + const MeshElemMap *map_ele = &edge_poly_map[me_idx]; const int *p = map_ele->indices; int i = map_ele->count; - /* Edge is smooth only if its poly is not sharp, edge is not sharp, - * and edge is used by exactly two polygons. */ - if (!sharp_poly && !(medge[ml->e].flag & ME_SHARP) && i == 2) { + if (!edge_boundary_check(mp, ml, me, i)) { for (; i--; p++) { /* if we meet other non initialized its a bug */ BLI_assert(ELEM(poly_groups[*p], 0, poly_group_id)); @@ -442,14 +484,20 @@ int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge, } } } - else if (use_bitflags) { - /* Find contiguous smooth groups already assigned, these are the values we can't reuse! */ - for (; i--; p++) { - int bit = poly_groups[*p]; - if (!ELEM(bit, 0, poly_group_id, poly_group_id_overflowed) && - !(bit_poly_group_mask & bit)) - { - bit_poly_group_mask |= bit; + else { + if (edge_borders && !BLI_BITMAP_TEST(edge_borders, me_idx)) { + BLI_BITMAP_ENABLE(edge_borders, me_idx); + num_edgeborders++; + } + if (use_bitflags) { + /* Find contiguous smooth groups already assigned, these are the values we can't reuse! */ + for (; i--; p++) { + int bit = poly_groups[*p]; + if (!ELEM(bit, 0, poly_group_id, poly_group_id_overflowed) && + !(bit_poly_group_mask & bit)) + { + bit_poly_group_mask |= bit; + } } } } @@ -502,12 +550,258 @@ int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge, tot_group++; } - MEM_freeN(edge_poly_map); - MEM_freeN(edge_poly_mem); + if (edge_poly_mem) { + MEM_freeN(edge_poly_map); + MEM_freeN(edge_poly_mem); + } MEM_freeN(poly_stack); *r_totgroup = tot_group; + *r_poly_groups = poly_groups; + if (r_edge_borders) { + *r_edge_borders = edge_borders; + *r_totedgeborder = num_edgeborders; + } +} + +static bool poly_is_island_boundary_smooth_cb( + const MPoly *mp, const MLoop *UNUSED(ml), const MEdge *me, + const int nbr_egde_users) +{ + /* Edge is sharp if its poly is sharp, or edge itself is sharp, or edge is not used by exactly two polygons. */ + return (!(mp->flag & ME_SMOOTH) || (me->flag & ME_SHARP) || (nbr_egde_users != 2)); +} + +/** + * 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 (bitflags if use_bitflags is true), starting at 1 + * (0 being used as 'invalid' flag). + * Note it's callers's responsibility to MEM_freeN returned array. + */ +int *BKE_mesh_calc_smoothgroups(const MEdge *medge, const int totedge, + const MPoly *mpoly, const int totpoly, + const MLoop *mloop, const int totloop, + int *r_totgroup, const bool use_bitflags) +{ + int *poly_groups = NULL; + + poly_edge_loop_islands_calc( + medge, totedge, mpoly, totpoly, mloop, totloop, NULL, use_bitflags, + poly_is_island_boundary_smooth_cb, &poly_groups, r_totgroup, NULL, NULL); return poly_groups; } + +#define MISLAND_DEFAULT_BUFSIZE 64 + +void BKE_mesh_loop_islands_init( + MeshIslandStore *island_store, + const short item_type, const int items_num, const short island_type, const short innercut_type) +{ + MemArena *mem = island_store->mem; + + if (mem == NULL) { + mem = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); + island_store->mem = mem; + } + /* else memarena should be cleared */ + + BLI_assert(ELEM(item_type, MISLAND_TYPE_VERT, MISLAND_TYPE_EDGE, MISLAND_TYPE_POLY, MISLAND_TYPE_LOOP)); + BLI_assert(ELEM(island_type, MISLAND_TYPE_VERT, MISLAND_TYPE_EDGE, MISLAND_TYPE_POLY, MISLAND_TYPE_LOOP)); + + island_store->item_type = item_type; + island_store->items_to_islands_num = items_num; + island_store->items_to_islands = BLI_memarena_alloc(mem, sizeof(*island_store->items_to_islands) * (size_t)items_num); + + island_store->island_type = island_type; + island_store->islands_num_alloc = MISLAND_DEFAULT_BUFSIZE; + island_store->islands = BLI_memarena_alloc(mem, sizeof(*island_store->islands) * island_store->islands_num_alloc); + + island_store->innercut_type = innercut_type; + island_store->innercuts = BLI_memarena_alloc(mem, sizeof(*island_store->innercuts) * island_store->islands_num_alloc); +} + +void BKE_mesh_loop_islands_clear(MeshIslandStore *island_store) +{ + island_store->item_type = MISLAND_TYPE_NONE; + island_store->items_to_islands_num = 0; + island_store->items_to_islands = NULL; + + island_store->island_type = MISLAND_TYPE_NONE; + island_store->islands_num = 0; + island_store->islands = NULL; + + island_store->innercut_type = MISLAND_TYPE_NONE; + island_store->innercuts = NULL; + + if (island_store->mem) { + BLI_memarena_clear(island_store->mem); + } + + island_store->islands_num_alloc = 0; +} + +void BKE_mesh_loop_islands_free(MeshIslandStore *island_store) +{ + if (island_store->mem) { + BLI_memarena_free(island_store->mem); + island_store->mem = NULL; + } +} + +void BKE_mesh_loop_islands_add( + MeshIslandStore *island_store, const int item_num, int *items_indices, + const int num_island_items, int *island_item_indices, + const int num_innercut_items, int *innercut_item_indices) +{ + MemArena *mem = island_store->mem; + + MeshElemMap *isld, *innrcut; + const int curr_island_idx = island_store->islands_num++; + const size_t curr_num_islands = (size_t)island_store->islands_num; + int i = item_num; + + island_store->items_to_islands_num = item_num; + while (i--) { + island_store->items_to_islands[items_indices[i]] = curr_island_idx; + } + + if (UNLIKELY(curr_num_islands > island_store->islands_num_alloc)) { + MeshElemMap **islds, **innrcuts; + + island_store->islands_num_alloc *= 2; + islds = BLI_memarena_alloc(mem, sizeof(*islds) * island_store->islands_num_alloc); + memcpy(islds, island_store->islands, sizeof(*islds) * (curr_num_islands - 1)); + island_store->islands = islds; + + innrcuts = BLI_memarena_alloc(mem, sizeof(*innrcuts) * island_store->islands_num_alloc); + memcpy(innrcuts, island_store->innercuts, sizeof(*innrcuts) * (curr_num_islands - 1)); + island_store->innercuts = innrcuts; + } + + island_store->islands[curr_island_idx] = isld = BLI_memarena_alloc(mem, sizeof(*isld)); + isld->count = num_island_items; + isld->indices = BLI_memarena_alloc(mem, sizeof(*isld->indices) * (size_t)num_island_items); + memcpy(isld->indices, island_item_indices, sizeof(*isld->indices) * (size_t)num_island_items); + + island_store->innercuts[curr_island_idx] = innrcut = BLI_memarena_alloc(mem, sizeof(*innrcut)); + innrcut->count = num_innercut_items; + innrcut->indices = BLI_memarena_alloc(mem, sizeof(*innrcut->indices) * (size_t)num_innercut_items); + memcpy(innrcut->indices, innercut_item_indices, sizeof(*innrcut->indices) * (size_t)num_innercut_items); +} + +/* TODO: I'm not sure edge seam flag is enough to define UV islands? Maybe we should also consider UVmaps values + * themselves (i.e. different UV-edges for a same mesh-edge => boundary edge too?). + * Would make things much more complex though, and each UVMap would then need its own mesh mapping, + * not sure we want that at all! + */ +static bool mesh_check_island_boundary_uv( + const MPoly *UNUSED(mp), const MLoop *UNUSED(ml), const MEdge *me, + const int UNUSED(nbr_egde_users)) +{ + /* Edge is UV boundary if tagged as seam. */ + return (me->flag & ME_SEAM) != 0; +} + +/** + * \note all this could be optimized... + * Not sure it would be worth the more complex code, though, those loops + * are supposed to be really quick to do... + */ +bool BKE_mesh_calc_islands_loop_poly_uv( + MVert *UNUSED(verts), const int UNUSED(totvert), + MEdge *edges, const int totedge, + MPoly *polys, const int totpoly, + MLoop *loops, const int totloop, + MeshIslandStore *r_island_store) +{ + int *poly_groups = NULL; + int num_poly_groups; + + /* map vars */ + MeshElemMap *edge_poly_map; + int *edge_poly_mem; + + int *poly_indices; + int *loop_indices; + int num_pidx, num_lidx; + + /* Those are used to detect 'inner cuts', i.e. edges that are borders, and yet have two or more polys of + * a same group using them (typical case: seam used to unwrap properly a cylinder). */ + BLI_bitmap *edge_borders; + int num_edge_borders; + char *edge_border_count = NULL; + int *edge_innercut_indices = NULL; + int num_einnercuts = 0; + + int grp_idx, p_idx, pl_idx, l_idx; + + BKE_mesh_loop_islands_clear(r_island_store); + BKE_mesh_loop_islands_init(r_island_store, MISLAND_TYPE_LOOP, totloop, MISLAND_TYPE_POLY, MISLAND_TYPE_EDGE); + + BKE_mesh_edge_poly_map_create(&edge_poly_map, &edge_poly_mem, + edges, totedge, polys, totpoly, loops, totloop); + + poly_edge_loop_islands_calc( + edges, totedge, polys, totpoly, loops, totloop, edge_poly_map, false, + mesh_check_island_boundary_uv, &poly_groups, &num_poly_groups, &edge_borders, &num_edge_borders); + + if (!num_poly_groups) { + /* Should never happen... */ + return false; + } + + if (num_edge_borders) { + edge_border_count = MEM_mallocN(sizeof(*edge_border_count) * (size_t)totedge, __func__); + edge_innercut_indices = MEM_mallocN(sizeof(*edge_innercut_indices) * (size_t)num_edge_borders, __func__); + } + + poly_indices = MEM_mallocN(sizeof(*poly_indices) * (size_t)totpoly, __func__); + loop_indices = MEM_mallocN(sizeof(*loop_indices) * (size_t)totloop, __func__); + + /* Note: here we ignore '0' invalid group - this should *never* happen in this case anyway? */ + for (grp_idx = 1; grp_idx <= num_poly_groups; grp_idx++) { + num_pidx = num_lidx = 0; + if (num_edge_borders) { + num_einnercuts = 0; + memset(edge_border_count, 0, sizeof(*edge_border_count) * (size_t)totedge); + } + + for (p_idx = 0; p_idx < totpoly; p_idx++) { + MPoly *mp; + + if (poly_groups[p_idx] != grp_idx) { + continue; + } + + mp = &polys[p_idx]; + poly_indices[num_pidx++] = p_idx; + for (l_idx = mp->loopstart, pl_idx = 0; pl_idx < mp->totloop; l_idx++, pl_idx++) { + MLoop *ml = &loops[l_idx]; + loop_indices[num_lidx++] = l_idx; + if (num_edge_borders && BLI_BITMAP_TEST(edge_borders, ml->e) && (edge_border_count[ml->e] < 2)) { + edge_border_count[ml->e]++; + if (edge_border_count[ml->e] == 2) { + edge_innercut_indices[num_einnercuts++] = (int)ml->e; + } + } + } + } + + BKE_mesh_loop_islands_add(r_island_store, num_lidx, loop_indices, num_pidx, poly_indices, + num_einnercuts, edge_innercut_indices); + } + + MEM_freeN(poly_indices); + MEM_freeN(loop_indices); + MEM_freeN(poly_groups); + if (num_edge_borders) { + MEM_freeN(edge_border_count); + MEM_freeN(edge_innercut_indices); + } + return true; +} + /** \} */ |