diff options
Diffstat (limited to 'source/blender/editors/mesh/editmesh_utils.c')
| -rw-r--r-- | source/blender/editors/mesh/editmesh_utils.c | 448 |
1 files changed, 246 insertions, 202 deletions
diff --git a/source/blender/editors/mesh/editmesh_utils.c b/source/blender/editors/mesh/editmesh_utils.c index ac5530c8ea9..a6a6b095c31 100644 --- a/source/blender/editors/mesh/editmesh_utils.c +++ b/source/blender/editors/mesh/editmesh_utils.c @@ -593,6 +593,32 @@ UvMapVert *BM_uv_vert_map_at_index(UvVertMap *vmap, uint v) return vmap->vert[v]; } +struct UvElement **BM_uv_element_map_ensure_head_table(struct UvElementMap *element_map) +{ + if (element_map->head_table) { + return element_map->head_table; + } + + /* 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; + } + } + } + } + return element_map->head_table; +} + #define INVALID_ISLAND ((unsigned int)-1) static void bm_uv_assign_island(UvElementMap *element_map, @@ -603,7 +629,7 @@ static void bm_uv_assign_island(UvElementMap *element_map, int islandbufsize) { element->island = nisland; - map[element - element_map->buf] = islandbufsize; + map[element - element_map->storage] = islandbufsize; /* Copy *element to islandbuf[islandbufsize]. */ islandbuf[islandbufsize].l = element->l; @@ -618,35 +644,21 @@ static int bm_uv_edge_select_build_islands(UvElementMap *element_map, UvElement *islandbuf, uint *map, bool uv_selected, - int cd_loop_uv_offset) + const int cd_loop_uv_offset) { - int totuv = element_map->totalUVs; + BM_uv_element_map_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) * 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; - } - } - } - } + int total_uvs = element_map->total_uvs; /* Depth first search the graph, building islands as we go. */ int nislands = 0; int islandbufsize = 0; - int stack_upper_bound = totuv; + int stack_upper_bound = total_uvs; 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; + for (int i = 0; i < total_uvs; i++) { + UvElement *element = element_map->storage + i; if (element->island != INVALID_ISLAND) { /* Unique UV (element and all it's children) are already part of an island. */ continue; @@ -676,7 +688,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->buf]; + 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 +704,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->buf]; + 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++); @@ -713,14 +725,132 @@ static int bm_uv_edge_select_build_islands(UvElementMap *element_map, } nislands++; } - BLI_assert(islandbufsize == totuv); + BLI_assert(islandbufsize == total_uvs); MEM_SAFE_FREE(stack_uv); - MEM_SAFE_FREE(head_table); + MEM_SAFE_FREE(element_map->head_table); 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->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 *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->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->total_islands = nislands; + MEM_SAFE_FREE(stack); + MEM_SAFE_FREE(map); +} + UvElementMap *BM_uv_element_map_create(BMesh *bm, const Scene *scene, const bool uv_selected, @@ -732,26 +862,18 @@ UvElementMap *BM_uv_element_map_create(BMesh *bm, BMVert *ev; BMFace *efa; - BMLoop *l; BMIter iter, liter; - /* vars from original func */ - UvElementMap *element_map; - UvElement *buf; - bool *winding = NULL; BLI_buffer_declare_static(vec2f, tf_uv_buf, BLI_BUFFER_NOP, BM_DEFAULT_NGON_STACK_SIZE); - MLoopUV *luv; - int totverts, totfaces, i, totuv, j; - const int cd_loop_uv_offset = CustomData_get_offset(&bm->ldata, CD_MLOOPUV); + if (cd_loop_uv_offset < 0) { + return NULL; + } BM_mesh_elem_index_ensure(bm, BM_VERT | BM_FACE); - totfaces = bm->totface; - totverts = bm->totvert; - totuv = 0; - - /* generate UvElement array */ + /* Count total uvs. */ + int totuv = 0; BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { if (BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) { continue; @@ -765,6 +887,7 @@ UvElementMap *BM_uv_element_map_create(BMesh *bm, totuv += efa->len; } else { + BMLoop *l; BM_ITER_ELEM (l, &liter, efa, BM_LOOPS_OF_FACE) { if (uvedit_uv_select_test(scene, l, cd_loop_uv_offset)) { totuv++; @@ -777,17 +900,17 @@ UvElementMap *BM_uv_element_map_create(BMesh *bm, return NULL; } - element_map = (UvElementMap *)MEM_callocN(sizeof(*element_map), "UvElementMap"); - element_map->totalUVs = totuv; - element_map->vert = (UvElement **)MEM_callocN(sizeof(*element_map->vert) * totverts, - "UvElementVerts"); - buf = element_map->buf = (UvElement *)MEM_callocN(sizeof(*element_map->buf) * totuv, - "UvElement"); + UvElementMap *element_map = (UvElementMap *)MEM_callocN(sizeof(*element_map), "UvElementMap"); + element_map->total_uvs = totuv; + element_map->vertex = (UvElement **)MEM_callocN(sizeof(*element_map->vertex) * bm->totvert, + "UvElementVerts"); + element_map->storage = (UvElement *)MEM_callocN(sizeof(*element_map->storage) * totuv, + "UvElement"); - if (use_winding) { - winding = MEM_callocN(sizeof(*winding) * totfaces, "winding"); - } + bool *winding = use_winding ? MEM_callocN(sizeof(*winding) * bm->totface, "winding") : NULL; + UvElement *buf = element_map->storage; + int j; BM_ITER_MESH_INDEX (efa, &iter, bm, BM_FACES_OF_MESH, j) { if (BM_elem_flag_test(efa, BM_ELEM_HIDDEN)) { @@ -804,18 +927,20 @@ UvElementMap *BM_uv_element_map_create(BMesh *bm, tf_uv = (float(*)[2])BLI_buffer_reinit_data(&tf_uv_buf, vec2f, efa->len); } + int i; + BMLoop *l; BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, i) { if (uv_selected && !uvedit_uv_select_test(scene, l, cd_loop_uv_offset)) { continue; } buf->l = l; - buf->separate = 0; buf->island = INVALID_ISLAND; buf->loop_of_poly_index = i; - buf->next = element_map->vert[BM_elem_index_get(l->v)]; - element_map->vert[BM_elem_index_get(l->v)] = buf; + /* Insert to head of linked list associated with BMVert. */ + buf->next = element_map->vertex[BM_elem_index_get(l->v)]; + element_map->vertex[BM_elem_index_get(l->v)] = buf; if (use_winding) { luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset); @@ -829,43 +954,54 @@ UvElementMap *BM_uv_element_map_create(BMesh *bm, winding[j] = cross_poly_v2(tf_uv, efa->len) > 0; } } + BLI_buffer_free(&tf_uv_buf); - /* sort individual uvs for each vert */ - BM_ITER_MESH_INDEX (ev, &iter, bm, BM_VERTS_OF_MESH, i) { - UvElement *newvlist = NULL, *vlist = element_map->vert[i]; - UvElement *iterv, *v, *lastv, *next; - const float *uv, *uv2; - bool uv_vert_sel, uv2_vert_sel; - + /* For each BMVert, sort associated linked list into unique uvs. */ + int ev_index; + BM_ITER_MESH_INDEX (ev, &iter, bm, BM_VERTS_OF_MESH, ev_index) { + UvElement *newvlist = NULL; + UvElement *vlist = element_map->vertex[ev_index]; while (vlist) { - v = vlist; + + /* Detach head from unsorted list. */ + UvElement *v = vlist; vlist = vlist->next; v->next = newvlist; newvlist = v; - l = v->l; - luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset); - uv = luv->uv; - uv_vert_sel = uvedit_uv_select_test(scene, l, cd_loop_uv_offset); + luv = BM_ELEM_CD_GET_VOID_P(v->l, cd_loop_uv_offset); + const float *uv = luv->uv; + bool uv_vert_sel = uvedit_uv_select_test(scene, v->l, cd_loop_uv_offset); - lastv = NULL; - iterv = vlist; + UvElement *lastv = NULL; + UvElement *iterv = vlist; + /* Scan through unsorted list, finding UvElements which are connected to `v`. */ while (iterv) { - next = iterv->next; + UvElement *next = iterv->next; + luv = BM_ELEM_CD_GET_VOID_P(iterv->l, cd_loop_uv_offset); - l = iterv->l; - luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset); - uv2 = luv->uv; - uv2_vert_sel = uvedit_uv_select_test(scene, l, cd_loop_uv_offset); + 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); + } - /* 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); + 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; } @@ -882,130 +1018,30 @@ UvElementMap *BM_uv_element_map_create(BMesh *bm, iterv = next; } - newvlist->separate = 1; + element_map->total_unique_uvs++; + newvlist->separate = true; } - element_map->vert[i] = newvlist; + /* Write back sorted list. */ + element_map->vertex[ev_index] = newvlist; } - if (use_winding) { - MEM_freeN(winding); - } + 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; - BMFace **stack; - int stacksize = 0; - UvElement *islandbuf; - /* island number for faces */ - int *island_number = NULL; - - 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"); - stack = MEM_mallocN(sizeof(*stack) * bm->totface, "uv_island_face_stack"); - islandbuf = MEM_callocN(sizeof(*islandbuf) * totuv, "uvelement_island_buffer"); - 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++) { - if (element_map->buf[i].island == INVALID_ISLAND) { - element_map->buf[i].island = nislands; - stack[0] = element_map->buf[i].l->f; - island_number[BM_elem_index_get(stack[0])] = nislands; - stacksize = 1; - - while (stacksize > 0) { - efa = stack[--stacksize]; - - 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 *element, *initelement = element_map->vert[BM_elem_index_get(l->v)]; - - for (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_freeN(island_number); - - /* remap */ - for (i = 0; i < bm->totvert; i++) { - /* important since we may do selection only. Some of these may be NULL */ - if (element_map->vert[i]) { - element_map->vert[i] = &islandbuf[map[element_map->vert[i] - element_map->buf]]; - } - } - - element_map->islandIndices = MEM_callocN(sizeof(*element_map->islandIndices) * nislands, - "UvElementMap_island_indices"); - j = 0; - for (i = 0; i < totuv; i++) { - UvElement *element = element_map->buf[i].next; - if (element == NULL) { - islandbuf[map[i]].next = NULL; - } - else { - islandbuf[map[i]].next = &islandbuf[map[element - element_map->buf]]; - } + bm_uv_build_islands(element_map, bm, scene, uv_selected); + } - if (islandbuf[i].island != j) { - j++; - element_map->islandIndices[j] = i; - } + /* 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) { + element_map->total_unique_uvs++; } - - MEM_freeN(element_map->buf); - - element_map->buf = islandbuf; - element_map->totalIslands = nislands; - MEM_freeN(stack); - MEM_freeN(map); } - BLI_buffer_free(&tf_uv_buf); - return element_map; } @@ -1025,30 +1061,38 @@ void BM_uv_vert_map_free(UvVertMap *vmap) void BM_uv_element_map_free(UvElementMap *element_map) { if (element_map) { - if (element_map->vert) { - MEM_freeN(element_map->vert); - } - if (element_map->buf) { - MEM_freeN(element_map->buf); - } - if (element_map->islandIndices) { - MEM_freeN(element_map->islandIndices); - } - MEM_freeN(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->island_indices); + MEM_SAFE_FREE(element_map->island_total_uvs); + MEM_SAFE_FREE(element_map->island_total_unique_uvs); + MEM_SAFE_FREE(element_map); } } -UvElement *BM_uv_element_get(UvElementMap *map, BMFace *efa, BMLoop *l) +UvElement *BM_uv_element_get(const UvElementMap *element_map, const BMFace *efa, const BMLoop *l) { - for (UvElement *element = map->vert[BM_elem_index_get(l->v)]; element; element = element->next) { + UvElement *element = element_map->vertex[BM_elem_index_get(l->v)]; + while (element) { if (element->l->f == efa) { return element; } + element = element->next; } return NULL; } +UvElement *BM_uv_element_get_head(UvElementMap *element_map, UvElement *child) +{ + if (!child) { + return NULL; + } + + return element_map->vertex[BM_elem_index_get(child->l->v)]; +} + /** \} */ /* -------------------------------------------------------------------- */ @@ -1518,7 +1562,7 @@ void EDBM_update(Mesh *mesh, const struct EDBMUpdate_Params *params) } if (params->is_destructive) { - /* TODO(campbell): we may be able to remove this now! */ + /* TODO(@campbellbarton): we may be able to remove this now! */ // BM_mesh_elem_table_free(em->bm, BM_ALL_NOLOOP); } else { |