[Bf-blender-cvs] [77257405437] master: UV: Edge support for select shortest path operator
Siddhartha Jejurkar
noreply at git.blender.org
Fri Jul 22 03:54:41 CEST 2022
Commit: 77257405437336dbd91a481926013f8c747cacae
Author: Siddhartha Jejurkar
Date: Fri Jul 22 10:47:28 2022 +1000
Branches: master
https://developer.blender.org/rB77257405437336dbd91a481926013f8c747cacae
UV: Edge support for select shortest path operator
Calculating shortest path selection in UV edge mode was done using vertex
path logic. Since the UV editor now supports proper edge selection [0],
this approach can sometimes give incorrect results.
This problem is now fixed by adding separate logic to calculate the
shortest path in UV edge mode.
Resolves T99344.
[0]: ffaaa0bcbf477c30cf3665b9330bbbb767397169
Reviewed By: campbellbarton
Ref D15511.
===================================================================
M source/blender/bmesh/tools/bmesh_path_uv.c
M source/blender/bmesh/tools/bmesh_path_uv.h
M source/blender/editors/uvedit/uvedit_path.c
===================================================================
diff --git a/source/blender/bmesh/tools/bmesh_path_uv.c b/source/blender/bmesh/tools/bmesh_path_uv.c
index 76697f51ac7..3d736cdc3b8 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,7 +58,7 @@ 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,
@@ -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 uint 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;
+}
/** \} */
diff --git a/source/blender/bmesh/tools/bmesh_path_uv.h b/source/blender/bmesh/tools/bmesh_path_uv.h
index af7341e2219..d7b5faa70e5 100644
--- a/source/blender/bmesh/tools/bmesh_path_uv.h
+++ b/source/blender/bmesh/tools/bmesh_path_uv.h
@@ -21,6 +21,14 @@ struct LinkNode *BM_mesh_calc_path_uv_vert(BMesh *bm,
void *user_data) ATTR_WARN_UNUSED_RESULT
ATTR_NONNULL(1, 2, 3, 5);
+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) ATTR_WARN_UNUSED_RESULT
+ ATTR_NONNULL(1, 2, 3, 5);
+
struct LinkNode *BM_mesh_calc_path_uv_face(BMesh *bm,
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list