From 13c5f6e08ff783b2bf8060e36b73affa28a5e7ac Mon Sep 17 00:00:00 2001 From: Chris Blackbourn Date: Wed, 10 Aug 2022 20:13:17 +1200 Subject: Cleanup: refactoring uvislands to prepare for python api Migrate island calculation to #bm_uv_build_islands. Simplify connectedness calculation. Reduce memory pressure. No functional changes. See also: D15598 --- source/blender/editors/mesh/editmesh_utils.c | 261 ++++++++++++++------------- 1 file changed, 140 insertions(+), 121 deletions(-) (limited to 'source/blender/editors/mesh') diff --git a/source/blender/editors/mesh/editmesh_utils.c b/source/blender/editors/mesh/editmesh_utils.c index 208022326d3..c446fb8b3e1 100644 --- a/source/blender/editors/mesh/editmesh_utils.c +++ b/source/blender/editors/mesh/editmesh_utils.c @@ -721,6 +721,120 @@ static int bm_uv_edge_select_build_islands(UvElementMap *element_map, return nislands; } +static void bm_uv_build_islands(UvElementMap *element_map, + BMesh *bm, + const Scene *scene, + bool uv_selected) +{ + int totuv = element_map->total_uvs; + int nislands = 0; + int islandbufsize = 0; + + /* map holds the map from current vmap->buf to the new, sorted map */ + uint *map = MEM_mallocN(sizeof(*map) * totuv, "uvelement_remap"); + BMFace **stack = MEM_mallocN(sizeof(*stack) * bm->totface, "uv_island_face_stack"); + UvElement *islandbuf = MEM_callocN(sizeof(*islandbuf) * totuv, "uvelement_island_buffer"); + /* Island number for BMFaces. */ + int *island_number = MEM_callocN(sizeof(*island_number) * bm->totface, "uv_island_number_face"); + copy_vn_i(island_number, bm->totface, INVALID_ISLAND); + + const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); + + 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; + } + + for (int i = 0; i < totuv; i++) { + if (element_map->storage[i].island == INVALID_ISLAND) { + int stacksize = 0; + element_map->storage[i].island = nislands; + stack[0] = element_map->storage[i].l->f; + island_number[BM_elem_index_get(stack[0])] = nislands; + stacksize = 1; + + while (stacksize > 0) { + BMFace *efa = stack[--stacksize]; + + BMLoop *l; + BMIter liter; + BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) { + if (uv_selected && !uvedit_uv_select_test(scene, l, cd_loop_uv_offset)) { + continue; + } + + UvElement *initelement = element_map->vertex[BM_elem_index_get(l->v)]; + + for (UvElement *element = initelement; element; element = element->next) { + if (element->separate) { + initelement = element; + } + + if (element->l->f == efa) { + /* found the uv corresponding to our face and vertex. + * Now fill it to the buffer */ + bm_uv_assign_island(element_map, element, nislands, map, islandbuf, islandbufsize++); + + for (element = initelement; element; element = element->next) { + if (element->separate && element != initelement) { + break; + } + + if (island_number[BM_elem_index_get(element->l->f)] == INVALID_ISLAND) { + stack[stacksize++] = element->l->f; + island_number[BM_elem_index_get(element->l->f)] = nislands; + } + } + break; + } + } + } + } + + nislands++; + } + } + + MEM_SAFE_FREE(island_number); + + /* remap */ + for (int i = 0; i < bm->totvert; i++) { + /* important since we may do selection only. Some of these may be NULL */ + if (element_map->vertex[i]) { + element_map->vertex[i] = &islandbuf[map[element_map->vertex[i] - element_map->storage]]; + } + } + + element_map->islandIndices = MEM_callocN(sizeof(*element_map->islandIndices) * nislands, + "UvElementMap_island_indices"); + int j = 0; + for (int i = 0; i < totuv; i++) { + UvElement *element = element_map->storage[i].next; + if (element == NULL) { + islandbuf[map[i]].next = NULL; + } + else { + islandbuf[map[i]].next = &islandbuf[map[element - element_map->storage]]; + } + + if (islandbuf[i].island != j) { + j++; + element_map->islandIndices[j] = i; + } + } + + MEM_SAFE_FREE(element_map->storage); + element_map->storage = islandbuf; + islandbuf = NULL; + element_map->totalIslands = nislands; + MEM_SAFE_FREE(stack); + MEM_SAFE_FREE(map); +} + UvElementMap *BM_uv_element_map_create(BMesh *bm, const Scene *scene, const bool uv_selected, @@ -824,6 +938,7 @@ UvElementMap *BM_uv_element_map_create(BMesh *bm, winding[j] = cross_poly_v2(tf_uv, efa->len) > 0; } } + BLI_buffer_free(&tf_uv_buf); /* For each BMVert, sort associated linked list into unique uvs. */ int ev_index; @@ -845,21 +960,32 @@ UvElementMap *BM_uv_element_map_create(BMesh *bm, UvElement *lastv = NULL; UvElement *iterv = vlist; - /* Scan through unsorted list, finding UvElements which match `v`. */ + /* Scan through unsorted list, finding UvElements which are connected to `v`. */ while (iterv) { UvElement *next = iterv->next; - luv = BM_ELEM_CD_GET_VOID_P(iterv->l, cd_loop_uv_offset); - const float *uv2 = luv->uv; - const bool uv2_vert_sel = uvedit_uv_select_test(scene, iterv->l, cd_loop_uv_offset); - /* Check if the uv loops share the same selection state (if not, they are not connected as - * they have been ripped or other edit commands have separated them). */ - const bool connected = (uv_vert_sel == uv2_vert_sel) && - compare_v2v2(uv2, uv, STD_UV_CONNECT_LIMIT); + bool connected = true; /* Assume connected unless we can prove otherwise. */ + + if (connected) { + /* Are the two UVs close together? */ + const float *uv2 = luv->uv; + connected = compare_v2v2(uv2, uv, STD_UV_CONNECT_LIMIT); + } + + if (connected) { + /* Check if the uv loops share the same selection state (if not, they are not connected + * as they have been ripped or other edit commands have separated them). */ + const bool uv2_vert_sel = uvedit_uv_select_test(scene, iterv->l, cd_loop_uv_offset); + connected = (uv_vert_sel == uv2_vert_sel); + } + + if (connected && use_winding) { + connected = winding[BM_elem_index_get(iterv->l->f)] == + winding[BM_elem_index_get(v->l->f)]; + } - if (connected && (!use_winding || winding[BM_elem_index_get(iterv->l->f)] == - winding[BM_elem_index_get(v->l->f)])) { + if (connected) { if (lastv) { lastv->next = next; } @@ -886,120 +1012,13 @@ UvElementMap *BM_uv_element_map_create(BMesh *bm, MEM_SAFE_FREE(winding); + /* at this point, every UvElement in vert points to a UvElement sharing the same vertex. + * Now we should sort uv's in islands. */ if (do_islands) { - uint *map; - UvElement *islandbuf; - - int nislands = 0, islandbufsize = 0; - - /* map holds the map from current vmap->buf to the new, sorted map */ - map = MEM_mallocN(sizeof(*map) * totuv, "uvelement_remap"); - BMFace **stack = MEM_mallocN(sizeof(*stack) * bm->totface, "uv_island_face_stack"); - islandbuf = MEM_callocN(sizeof(*islandbuf) * totuv, "uvelement_island_buffer"); - /* Island number for BMFaces. */ - int *island_number = MEM_callocN(sizeof(*island_number) * bm->totface, - "uv_island_number_face"); - copy_vn_i(island_number, bm->totface, 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 (int i = 0; i < totuv; i++) { - if (element_map->storage[i].island == INVALID_ISLAND) { - int stacksize = 0; - element_map->storage[i].island = nislands; - stack[0] = element_map->storage[i].l->f; - island_number[BM_elem_index_get(stack[0])] = nislands; - stacksize = 1; - - while (stacksize > 0) { - efa = stack[--stacksize]; - - BMLoop *l; - BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) { - if (uv_selected && !uvedit_uv_select_test(scene, l, cd_loop_uv_offset)) { - continue; - } - - UvElement *initelement = element_map->vertex[BM_elem_index_get(l->v)]; - - for (UvElement *element = initelement; element; element = element->next) { - if (element->separate) { - initelement = element; - } - - if (element->l->f == efa) { - /* found the uv corresponding to our face and vertex. - * Now fill it to the buffer */ - bm_uv_assign_island( - element_map, element, nislands, map, islandbuf, islandbufsize++); - - for (element = initelement; element; element = element->next) { - if (element->separate && element != initelement) { - break; - } - - if (island_number[BM_elem_index_get(element->l->f)] == INVALID_ISLAND) { - stack[stacksize++] = element->l->f; - island_number[BM_elem_index_get(element->l->f)] = nislands; - } - } - break; - } - } - } - } - - nislands++; - } - } - - MEM_SAFE_FREE(island_number); - - /* remap */ - for (int i = 0; i < bm->totvert; i++) { - /* important since we may do selection only. Some of these may be NULL */ - if (element_map->vertex[i]) { - element_map->vertex[i] = &islandbuf[map[element_map->vertex[i] - element_map->storage]]; - } - } - - element_map->islandIndices = MEM_callocN(sizeof(*element_map->islandIndices) * nislands, - "UvElementMap_island_indices"); - j = 0; - for (int i = 0; i < totuv; i++) { - UvElement *element = element_map->storage[i].next; - if (element == NULL) { - islandbuf[map[i]].next = NULL; - } - else { - islandbuf[map[i]].next = &islandbuf[map[element - element_map->storage]]; - } - - if (islandbuf[i].island != j) { - j++; - element_map->islandIndices[j] = i; - } - } - - MEM_SAFE_FREE(element_map->storage); - element_map->storage = islandbuf; - islandbuf = NULL; - element_map->totalIslands = nislands; - MEM_SAFE_FREE(stack); - MEM_SAFE_FREE(map); + bm_uv_build_islands(element_map, bm, scene, uv_selected); } - BLI_buffer_free(&tf_uv_buf); - + /* TODO: Confirm element_map->total_unique_uvs doesn't require recalculating. */ element_map->total_unique_uvs = 0; for (int i = 0; i < element_map->total_uvs; i++) { if (element_map->storage[i].separate) { -- cgit v1.2.3 From fb7ef40006b938bab25f4bb60d8a23fc9ef2e8dc Mon Sep 17 00:00:00 2001 From: Chris Blackbourn Date: Thu, 11 Aug 2022 11:20:00 +1200 Subject: Cleanup: refactoring uvislands to prepare for python api Add #bm_uv_ensure_head_table See also: D15598 --- source/blender/editors/mesh/editmesh_utils.c | 50 +++++++++++++++++----------- 1 file changed, 31 insertions(+), 19 deletions(-) (limited to 'source/blender/editors/mesh') diff --git a/source/blender/editors/mesh/editmesh_utils.c b/source/blender/editors/mesh/editmesh_utils.c index c446fb8b3e1..a0e20e4db8a 100644 --- a/source/blender/editors/mesh/editmesh_utils.c +++ b/source/blender/editors/mesh/editmesh_utils.c @@ -593,6 +593,31 @@ UvMapVert *BM_uv_vert_map_at_index(UvVertMap *vmap, uint v) return vmap->vert[v]; } +static void bm_uv_ensure_head_table(UvElementMap *element_map) +{ + if (element_map->head_table) { + return; + } + + /* For each UvElement, locate the "separate" UvElement that precedes it in the linked list. */ + element_map->head_table = MEM_mallocN(sizeof(*element_map->head_table) * element_map->total_uvs, + "uv_element_map_head_table"); + UvElement **head_table = element_map->head_table; + for (int i = 0; i < element_map->total_uvs; i++) { + UvElement *head = element_map->storage + i; + if (head->separate) { + UvElement *element = head; + while (element) { + head_table[element - element_map->storage] = head; + element = element->next; + if (element && element->separate) { + break; + } + } + } + } +} + #define INVALID_ISLAND ((unsigned int)-1) static void bm_uv_assign_island(UvElementMap *element_map, @@ -620,23 +645,9 @@ static int bm_uv_edge_select_build_islands(UvElementMap *element_map, bool uv_selected, int cd_loop_uv_offset) { - int total_uvs = element_map->total_uvs; + bm_uv_ensure_head_table(element_map); - /* For each UvElement, locate the "separate" UvElement that precedes it in the linked list. */ - UvElement **head_table = MEM_mallocN(sizeof(*head_table) * total_uvs, "uv_island_head_table"); - for (int i = 0; i < total_uvs; i++) { - UvElement *head = element_map->storage + i; - if (head->separate) { - UvElement *element = head; - while (element) { - head_table[element - element_map->storage] = head; - element = element->next; - if (element && element->separate) { - break; - } - } - } - } + int total_uvs = element_map->total_uvs; /* Depth first search the graph, building islands as we go. */ int nislands = 0; @@ -676,7 +687,7 @@ static int bm_uv_edge_select_build_islands(UvElementMap *element_map, 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->storage]; + UvElement *tail = element_map->head_table[next - element_map->storage]; stack_uv[stacksize_uv++] = tail; while (tail) { bm_uv_assign_island(element_map, tail, nislands, map, islandbuf, islandbufsize++); @@ -692,7 +703,7 @@ static int bm_uv_edge_select_build_islands(UvElementMap *element_map, 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->storage]; + UvElement *tail = element_map->head_table[prev - element_map->storage]; stack_uv[stacksize_uv++] = tail; while (tail) { bm_uv_assign_island(element_map, tail, nislands, map, islandbuf, islandbufsize++); @@ -716,7 +727,7 @@ static int bm_uv_edge_select_build_islands(UvElementMap *element_map, BLI_assert(islandbufsize == total_uvs); MEM_SAFE_FREE(stack_uv); - MEM_SAFE_FREE(head_table); + MEM_SAFE_FREE(element_map->head_table); return nislands; } @@ -1047,6 +1058,7 @@ void BM_uv_element_map_free(UvElementMap *element_map) if (element_map) { MEM_SAFE_FREE(element_map->storage); MEM_SAFE_FREE(element_map->vertex); + MEM_SAFE_FREE(element_map->head_table); MEM_SAFE_FREE(element_map->islandIndices); MEM_SAFE_FREE(element_map); } -- cgit v1.2.3 From f35d671f466da324ebe70eef3edf12bd3b2b63c9 Mon Sep 17 00:00:00 2001 From: Chris Blackbourn Date: Thu, 11 Aug 2022 14:18:31 +1200 Subject: Cleanup: refactoring uvislands to prepare for python api Add element_map->island_total_uvs. Add element_map->island_total_unique_uvs. Simplify callers based on new members. Add comments. Resolves: D15598 --- source/blender/editors/mesh/editmesh_utils.c | 30 +++++++++++++++++----------- 1 file changed, 18 insertions(+), 12 deletions(-) (limited to 'source/blender/editors/mesh') diff --git a/source/blender/editors/mesh/editmesh_utils.c b/source/blender/editors/mesh/editmesh_utils.c index a0e20e4db8a..e931dd02a9e 100644 --- a/source/blender/editors/mesh/editmesh_utils.c +++ b/source/blender/editors/mesh/editmesh_utils.c @@ -820,28 +820,32 @@ static void bm_uv_build_islands(UvElementMap *element_map, } } - element_map->islandIndices = MEM_callocN(sizeof(*element_map->islandIndices) * nislands, - "UvElementMap_island_indices"); + element_map->island_indices = MEM_callocN(sizeof(*element_map->island_indices) * nislands, + __func__); + element_map->island_total_uvs = MEM_callocN(sizeof(*element_map->island_total_uvs) * nislands, + __func__); + element_map->island_total_unique_uvs = MEM_callocN( + sizeof(*element_map->island_total_unique_uvs) * nislands, __func__); int j = 0; for (int i = 0; i < totuv; i++) { - UvElement *element = element_map->storage[i].next; - if (element == NULL) { - islandbuf[map[i]].next = NULL; - } - else { - islandbuf[map[i]].next = &islandbuf[map[element - element_map->storage]]; - } + UvElement *next = element_map->storage[i].next; + islandbuf[map[i]].next = next ? &islandbuf[map[next - element_map->storage]] : NULL; if (islandbuf[i].island != j) { j++; - element_map->islandIndices[j] = i; + element_map->island_indices[j] = i; + } + BLI_assert(islandbuf[i].island == j); + element_map->island_total_uvs[j]++; + if (islandbuf[i].separate) { + element_map->island_total_unique_uvs[j]++; } } MEM_SAFE_FREE(element_map->storage); element_map->storage = islandbuf; islandbuf = NULL; - element_map->totalIslands = nislands; + element_map->total_islands = nislands; MEM_SAFE_FREE(stack); MEM_SAFE_FREE(map); } @@ -1059,7 +1063,9 @@ void BM_uv_element_map_free(UvElementMap *element_map) MEM_SAFE_FREE(element_map->storage); MEM_SAFE_FREE(element_map->vertex); MEM_SAFE_FREE(element_map->head_table); - MEM_SAFE_FREE(element_map->islandIndices); + MEM_SAFE_FREE(element_map->island_indices); + MEM_SAFE_FREE(element_map->island_total_uvs); + MEM_SAFE_FREE(element_map->island_total_unique_uvs); MEM_SAFE_FREE(element_map); } } -- cgit v1.2.3