From 178868cf42594bf7eedfa4db93ba8b7f3bf017ce Mon Sep 17 00:00:00 2001 From: Chris Blackbourn Date: Thu, 14 Jul 2022 12:40:43 +1200 Subject: Fix T79304: improve uv island calculation when in edge selection mode Differential Revision: https://developer.blender.org/D15419 --- source/blender/editors/mesh/editmesh_utils.c | 144 +++++++++++++++++++++++++-- 1 file changed, 137 insertions(+), 7 deletions(-) diff --git a/source/blender/editors/mesh/editmesh_utils.c b/source/blender/editors/mesh/editmesh_utils.c index 60a666ee755..ac5530c8ea9 100644 --- a/source/blender/editors/mesh/editmesh_utils.c +++ b/source/blender/editors/mesh/editmesh_utils.c @@ -595,6 +595,132 @@ UvMapVert *BM_uv_vert_map_at_index(UvVertMap *vmap, uint v) #define INVALID_ISLAND ((unsigned int)-1) +static void bm_uv_assign_island(UvElementMap *element_map, + UvElement *element, + int nisland, + uint *map, + UvElement *islandbuf, + int islandbufsize) +{ + element->island = nisland; + map[element - element_map->buf] = islandbufsize; + + /* Copy *element to islandbuf[islandbufsize]. */ + islandbuf[islandbufsize].l = element->l; + islandbuf[islandbufsize].separate = element->separate; + islandbuf[islandbufsize].loop_of_poly_index = element->loop_of_poly_index; + islandbuf[islandbufsize].island = element->island; + islandbuf[islandbufsize].flag = element->flag; +} + +static int bm_uv_edge_select_build_islands(UvElementMap *element_map, + const Scene *scene, + UvElement *islandbuf, + uint *map, + bool uv_selected, + int cd_loop_uv_offset) +{ + int totuv = element_map->totalUVs; + + /* For each UvElement, locate the "separate" UvElement that precedes it in the linked list. */ + UvElement **head_table = MEM_mallocN(sizeof(*head_table) * totuv, "uv_island_head_table"); + for (int i = 0; i < totuv; i++) { + UvElement *head = element_map->buf + i; + if (head->separate) { + UvElement *element = head; + while (element) { + head_table[element - element_map->buf] = head; + element = element->next; + if (element && element->separate) { + break; + } + } + } + } + + /* Depth first search the graph, building islands as we go. */ + int nislands = 0; + int islandbufsize = 0; + int stack_upper_bound = totuv; + UvElement **stack_uv = MEM_mallocN(sizeof(*stack_uv) * stack_upper_bound, + "uv_island_element_stack"); + int stacksize_uv = 0; + for (int i = 0; i < totuv; i++) { + UvElement *element = element_map->buf + i; + if (element->island != INVALID_ISLAND) { + /* Unique UV (element and all it's children) are already part of an island. */ + continue; + } + + /* Create a new island, i.e. nislands++. */ + + BLI_assert(element->separate); /* Ensure we're the head of this unique UV. */ + + /* Seed the graph search. */ + stack_uv[stacksize_uv++] = element; + while (element) { + bm_uv_assign_island(element_map, element, nislands, map, islandbuf, islandbufsize++); + element = element->next; + if (element && element->separate) { + break; + } + } + + /* Traverse the graph. */ + while (stacksize_uv) { + BLI_assert(stacksize_uv < stack_upper_bound); + element = stack_uv[--stacksize_uv]; + while (element) { + + /* Scan forwards around the BMFace that contains element->l. */ + if (!uv_selected || uvedit_edge_select_test(scene, element->l, cd_loop_uv_offset)) { + UvElement *next = BM_uv_element_get(element_map, element->l->next->f, element->l->next); + if (next->island == INVALID_ISLAND) { + UvElement *tail = head_table[next - element_map->buf]; + stack_uv[stacksize_uv++] = tail; + while (tail) { + bm_uv_assign_island(element_map, tail, nislands, map, islandbuf, islandbufsize++); + tail = tail->next; + if (tail && tail->separate) { + break; + } + } + } + } + + /* Scan backwards around the BMFace that contains element->l. */ + if (!uv_selected || uvedit_edge_select_test(scene, element->l->prev, cd_loop_uv_offset)) { + UvElement *prev = BM_uv_element_get(element_map, element->l->prev->f, element->l->prev); + if (prev->island == INVALID_ISLAND) { + UvElement *tail = head_table[prev - element_map->buf]; + stack_uv[stacksize_uv++] = tail; + while (tail) { + bm_uv_assign_island(element_map, tail, nislands, map, islandbuf, islandbufsize++); + tail = tail->next; + if (tail && tail->separate) { + break; + } + } + } + } + + /* The same for all the UvElements in this unique UV. */ + element = element->next; + if (element && element->separate) { + break; + } + } + } + nislands++; + } + BLI_assert(islandbufsize == totuv); + + MEM_SAFE_FREE(stack_uv); + MEM_SAFE_FREE(head_table); + + return nislands; +} + UvElementMap *BM_uv_element_map_create(BMesh *bm, const Scene *scene, const bool uv_selected, @@ -783,6 +909,15 @@ UvElementMap *BM_uv_element_map_create(BMesh *bm, island_number = MEM_mallocN(sizeof(*island_number) * totfaces, "uv_island_number_face"); copy_vn_i(island_number, totfaces, INVALID_ISLAND); + const bool use_uv_edge_connectivity = scene->toolsettings->uv_flag & UV_SYNC_SELECTION ? + scene->toolsettings->selectmode & SCE_SELECT_EDGE : + scene->toolsettings->uv_selectmode & UV_SELECT_EDGE; + if (use_uv_edge_connectivity) { + nislands = bm_uv_edge_select_build_islands( + element_map, scene, islandbuf, map, uv_selected, cd_loop_uv_offset); + islandbufsize = totuv; + } + /* at this point, every UvElement in vert points to a UvElement sharing the same vertex. * Now we should sort uv's in islands. */ for (i = 0; i < totuv; i++) { @@ -810,13 +945,8 @@ UvElementMap *BM_uv_element_map_create(BMesh *bm, if (element->l->f == efa) { /* found the uv corresponding to our face and vertex. * Now fill it to the buffer */ - element->island = nislands; - map[element - element_map->buf] = islandbufsize; - islandbuf[islandbufsize].l = element->l; - islandbuf[islandbufsize].separate = element->separate; - islandbuf[islandbufsize].loop_of_poly_index = element->loop_of_poly_index; - islandbuf[islandbufsize].island = nislands; - islandbufsize++; + bm_uv_assign_island( + element_map, element, nislands, map, islandbuf, islandbufsize++); for (element = initelement; element; element = element->next) { if (element->separate && element != initelement) { -- cgit v1.2.3