diff options
Diffstat (limited to 'source/blender/bmesh/tools/bmesh_path_uv.c')
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_path_uv.c | 207 |
1 files changed, 198 insertions, 9 deletions
diff --git a/source/blender/bmesh/tools/bmesh_path_uv.c b/source/blender/bmesh/tools/bmesh_path_uv.c index 76697f51ac7..6531677fce6 100644 --- a/source/blender/bmesh/tools/bmesh_path_uv.c +++ b/source/blender/bmesh/tools/bmesh_path_uv.c @@ -47,9 +47,7 @@ static float step_cost_3_v2_ex( return cost * (1.0f + 0.5f * (2.0f - sqrtf(fabsf(dot_v2v2(d1, d2))))); } -static float UNUSED_FUNCTION(step_cost_3_v2)(const float v1[2], - const float v2[2], - const float v3[2]) +static float step_cost_3_v2(const float v1[2], const float v2[2], const float v3[2]) { return step_cost_3_v2_ex(v1, v2, v3, false, false); } @@ -60,14 +58,14 @@ static float UNUSED_FUNCTION(step_cost_3_v2)(const float v1[2], /** \name BM_mesh_calc_path_uv_vert * \{ */ -static void looptag_add_adjacent_uv(HeapSimple *heap, +static void verttag_add_adjacent_uv(HeapSimple *heap, BMLoop *l_a, BMLoop **loops_prev, float *cost, const struct BMCalcPathUVParams *params) { BLI_assert(params->aspect_y != 0.0f); - const uint cd_loop_uv_offset = params->cd_loop_uv_offset; + const int cd_loop_uv_offset = params->cd_loop_uv_offset; const int l_a_index = BM_elem_index_get(l_a); const MLoopUV *luv_a = BM_ELEM_CD_GET_VOID_P(l_a, cd_loop_uv_offset); const float uv_a[2] = {luv_a->uv[0], luv_a->uv[1] / params->aspect_y}; @@ -162,7 +160,7 @@ struct LinkNode *BM_mesh_calc_path_uv_vert(BMesh *bm, if (!BM_elem_flag_test(l, BM_ELEM_TAG)) { /* Adjacent loops are tagged while stepping to avoid 2x loops. */ BM_elem_flag_enable(l, BM_ELEM_TAG); - looptag_add_adjacent_uv(heap, l, loops_prev, cost, params); + verttag_add_adjacent_uv(heap, l, loops_prev, cost, params); } } @@ -185,8 +183,199 @@ struct LinkNode *BM_mesh_calc_path_uv_vert(BMesh *bm, /** \name BM_mesh_calc_path_uv_edge * \{ */ -/* TODO(@sidd017): Setting this as todo, since we now support proper UV edge selection (D12028). - * Till then, continue using vertex path to fake shortest path calculation for edges. */ +static float edgetag_cut_cost_vert_uv( + BMLoop *l_e_a, BMLoop *l_e_b, BMLoop *l_v, const float aspect_y, const int cd_loop_uv_offset) +{ + BMLoop *l_v1 = (l_v->v == l_e_a->v) ? l_e_a->next : l_e_a; + BMLoop *l_v2 = (l_v->v == l_e_b->v) ? l_e_b->next : l_e_b; + + MLoopUV *luv_v1 = BM_ELEM_CD_GET_VOID_P(l_v1, cd_loop_uv_offset); + MLoopUV *luv_v2 = BM_ELEM_CD_GET_VOID_P(l_v2, cd_loop_uv_offset); + MLoopUV *luv_v = BM_ELEM_CD_GET_VOID_P(l_v, cd_loop_uv_offset); + + float uv_v1[2] = {luv_v1->uv[0], luv_v1->uv[1] / aspect_y}; + float uv_v2[2] = {luv_v2->uv[0], luv_v2->uv[1] / aspect_y}; + float uv_v[2] = {luv_v->uv[0], luv_v->uv[1] / aspect_y}; + + return step_cost_3_v2(uv_v1, uv_v, uv_v2); +} + +static float edgetag_cut_cost_face_uv( + BMLoop *l_e_a, BMLoop *l_e_b, BMFace *f, const float aspect_v2[2], const int cd_loop_uv_offset) +{ + float l_e_a_cent[2], l_e_b_cent[2], f_cent[2]; + MLoopUV *luv_e_a = BM_ELEM_CD_GET_VOID_P(l_e_a, cd_loop_uv_offset); + MLoopUV *luv_e_b = BM_ELEM_CD_GET_VOID_P(l_e_b, cd_loop_uv_offset); + + mid_v2_v2v2(l_e_a_cent, luv_e_a->uv, luv_e_a->uv); + mid_v2_v2v2(l_e_b_cent, luv_e_b->uv, luv_e_b->uv); + + mul_v2_v2(l_e_a_cent, aspect_v2); + mul_v2_v2(l_e_b_cent, aspect_v2); + + BM_face_uv_calc_center_median_weighted(f, aspect_v2, cd_loop_uv_offset, f_cent); + + return step_cost_3_v2(l_e_a_cent, l_e_b_cent, f_cent); +} + +static void edgetag_add_adjacent_uv(HeapSimple *heap, + BMLoop *l_a, + BMLoop **loops_prev, + float *cost, + const struct BMCalcPathUVParams *params) +{ + BLI_assert(params->aspect_y != 0.0f); + const int cd_loop_uv_offset = params->cd_loop_uv_offset; + BMLoop *l_a_verts[2] = {l_a, l_a->next}; + const int l_a_index = BM_elem_index_get(l_a); + + if (params->use_step_face == false) { + for (int i = 0; i < ARRAY_SIZE(l_a_verts); i++) { + + /* Skip current UV vert if it is part of the previous UV edge in the path. */ + if (loops_prev[l_a_index]) { + BMLoop *l_prev = loops_prev[l_a_index]; + if (l_a_verts[i]->v != l_prev->v) { + l_prev = (l_a_verts[i]->v == l_prev->next->v) ? l_prev->next : NULL; + } + if (l_prev && BM_loop_uv_share_vert_check(l_a_verts[i], l_prev, cd_loop_uv_offset)) { + continue; + } + } + + BMEdge *e_b; + BMIter eiter; + BM_ITER_ELEM (e_b, &eiter, l_a_verts[i]->v, BM_EDGES_OF_VERT) { + BMLoop *l_first, *l_b; + l_first = l_b = e_b->l; + do { + if (!BM_elem_flag_test(l_b, BM_ELEM_TAG)) { + BMLoop *l_b_vert = (l_a_verts[i]->v == l_b->v) ? l_b : l_b->next; + if (BM_loop_uv_share_vert_check(l_a_verts[i], l_b_vert, cd_loop_uv_offset)) { + /* We know 'l_b' is not visited, check it out! */ + const int l_b_index = BM_elem_index_get(l_b); + const float cost_cut = params->use_topology_distance ? + 1.0f : + edgetag_cut_cost_vert_uv(l_a, + l_b, + l_a_verts[i], + params->aspect_y, + cd_loop_uv_offset); + const float cost_new = cost[l_a_index] + cost_cut; + + if (cost[l_b_index] > cost_new) { + cost[l_b_index] = cost_new; + loops_prev[l_b_index] = l_a; + BLI_heapsimple_insert(heap, cost_new, l_b); + } + } + } + } while ((l_b = l_b->radial_next) != l_first); + } + } + } + else { + const float aspect_v2[2] = {1.0f, 1.0f / params->aspect_y}; + BMLoop *l_first, *l_iter; + l_iter = l_first = l_a; + do { + /* Ensures connected UVs and that they lie on the same island. */ + if (!BM_loop_uv_share_edge_check(l_a, l_iter, cd_loop_uv_offset)) { + continue; + } + + BMLoop *l_cycle_iter, *l_cycle_end; + l_cycle_iter = l_iter->next; + l_cycle_end = l_iter; + do { + BMLoop *l_b = l_cycle_iter; + if (!BM_elem_flag_test(l_b, BM_ELEM_TAG)) { + /* We know 'l_b' is not visited, check it out! */ + const int l_b_index = BM_elem_index_get(l_b); + const float cost_cut = params->use_topology_distance ? + 1.0f : + edgetag_cut_cost_face_uv(l_a, + l_b, + l_iter->f, + aspect_v2, + params->cd_loop_uv_offset); + const float cost_new = cost[l_a_index] + cost_cut; + + if (cost[l_b_index] > cost_new) { + cost[l_b_index] = cost_new; + loops_prev[l_b_index] = l_a; + BLI_heapsimple_insert(heap, cost_new, l_b); + } + } + } while ((l_cycle_iter = l_cycle_iter->next) != l_cycle_end); + } while ((l_iter = l_iter->radial_next) != l_first); + } +} + +struct LinkNode *BM_mesh_calc_path_uv_edge(BMesh *bm, + BMLoop *l_src, + BMLoop *l_dst, + const struct BMCalcPathUVParams *params, + bool (*filter_fn)(BMLoop *, void *), + void *user_data) +{ + LinkNode *path = NULL; + + BMFace *f; + BMIter iter; + HeapSimple *heap; + float *cost; + BMLoop **loops_prev; + int i = 0, totloop; + + BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) { + BMLoop *l_first = BM_FACE_FIRST_LOOP(f); + BMLoop *l_iter = l_first; + do { + BM_elem_flag_set(l_iter, BM_ELEM_TAG, !filter_fn(l_iter, user_data)); + BM_elem_index_set(l_iter, i); + i += 1; + } while ((l_iter = l_iter->next) != l_first); + } + bm->elem_index_dirty &= ~BM_LOOP; + + totloop = bm->totloop; + loops_prev = MEM_callocN(sizeof(*loops_prev) * totloop, __func__); + cost = MEM_mallocN(sizeof(*cost) * totloop, __func__); + + copy_vn_fl(cost, totloop, COST_INIT_MAX); + + /* Regular dijkstra shortest path, but over UV loops/edges instead of vertices. */ + heap = BLI_heapsimple_new(); + BLI_heapsimple_insert(heap, 0.0f, l_src); + cost[BM_elem_index_get(l_src)] = 0.0f; + + BMLoop *l = NULL; + while (!BLI_heapsimple_is_empty(heap)) { + l = BLI_heapsimple_pop_min(heap); + + if ((l->e == l_dst->e) && (BM_loop_uv_share_edge_check(l, l_dst, params->cd_loop_uv_offset))) { + break; + } + + if (!BM_elem_flag_test(l, BM_ELEM_TAG)) { + BM_elem_flag_enable(l, BM_ELEM_TAG); + edgetag_add_adjacent_uv(heap, l, loops_prev, cost, params); + } + } + + if ((l->e == l_dst->e) && (BM_loop_uv_share_edge_check(l, l_dst, params->cd_loop_uv_offset))) { + do { + BLI_linklist_prepend(&path, l); + } while ((l = loops_prev[BM_elem_index_get(l)])); + } + + MEM_freeN(loops_prev); + MEM_freeN(cost); + BLI_heapsimple_free(heap, NULL); + + return path; +} /** \} */ @@ -273,7 +462,7 @@ static void facetag_add_adjacent_uv(HeapSimple *heap, const float aspect_v2[2], const struct BMCalcPathUVParams *params) { - const uint cd_loop_uv_offset = params->cd_loop_uv_offset; + const int cd_loop_uv_offset = params->cd_loop_uv_offset; const int f_a_index = BM_elem_index_get(f_a); /* Loop over faces of face, but do so by first looping over loops. */ |