diff options
Diffstat (limited to 'source/blender/bmesh/tools')
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_bevel.c | 5 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_intersect_edges.c | 24 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_path.c | 126 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_path_uv.c | 433 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_path_uv.h | 47 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_region_match.c | 4 |
6 files changed, 579 insertions, 60 deletions
diff --git a/source/blender/bmesh/tools/bmesh_bevel.c b/source/blender/bmesh/tools/bmesh_bevel.c index b109dc3199a..626d58f75f8 100644 --- a/source/blender/bmesh/tools/bmesh_bevel.c +++ b/source/blender/bmesh/tools/bmesh_bevel.c @@ -1353,8 +1353,9 @@ static void offset_meet(EdgeHalf *e1, /** * Calculate the meeting point between e1 and e2 (one of which should have zero offsets), - * where e1 precedes e2 in CCW order around their common vertex v (viewed from normal side). - * If r_angle is provided, return the angle between e and emeet in *r_angle. + * where \a e1 precedes \a e2 in CCW order around their common vertex \a v + * (viewed from normal side). + * If \a r_angle is provided, return the angle between \a e and \a meetco in `*r_angle`. * If the angle is 0, or it is 180 degrees or larger, there will be no meeting point; * return false in that case, else true. */ diff --git a/source/blender/bmesh/tools/bmesh_intersect_edges.c b/source/blender/bmesh/tools/bmesh_intersect_edges.c index 99a5a9edb57..52231033fd3 100644 --- a/source/blender/bmesh/tools/bmesh_intersect_edges.c +++ b/source/blender/bmesh/tools/bmesh_intersect_edges.c @@ -833,15 +833,37 @@ bool BM_mesh_intersect_edges( } if (pair_array) { + BMVert *v_key, *v_val; pair_iter = &pair_array[0]; for (i = 0; i < pair_len; i++, pair_iter++) { BLI_assert((*pair_iter)[0].elem->head.htype == BM_VERT); BLI_assert((*pair_iter)[1].elem->head.htype == BM_VERT); BLI_assert((*pair_iter)[0].elem != (*pair_iter)[1].elem); - BMVert *v_key, *v_val; v_key = (*pair_iter)[0].vert; v_val = (*pair_iter)[1].vert; BLI_ghash_insert(r_targetmap, v_key, v_val); + } + + /** + * The weld_verts operator works best when all keys in the same group of + * collapsed vertices point to the same vertex. + * That is, if the pairs of vertices are: + * [1, 2], [2, 3] and [3, 4], + * They are better adjusted to: + * [1, 4], [2, 4] and [3, 4]. + */ + pair_iter = &pair_array[0]; + for (i = 0; i < pair_len; i++, pair_iter++) { + v_key = (*pair_iter)[0].vert; + v_val = (*pair_iter)[1].vert; + BMVert *v_target; + while ((v_target = BLI_ghash_lookup(r_targetmap, v_val))) { + v_val = v_target; + } + if (v_val != (*pair_iter)[1].vert) { + BMVert **v_val_p = (BMVert **)BLI_ghash_lookup_p(r_targetmap, v_key); + *v_val_p = (*pair_iter)[1].vert = v_val; + } if (split_faces) { /* The vertex index indicates its position in the pair_array flat. */ BM_elem_index_set(v_key, i * 2); diff --git a/source/blender/bmesh/tools/bmesh_path.c b/source/blender/bmesh/tools/bmesh_path.c index 713a68969e5..cb75f47acf3 100644 --- a/source/blender/bmesh/tools/bmesh_path.c +++ b/source/blender/bmesh/tools/bmesh_path.c @@ -18,6 +18,8 @@ * \ingroup bmesh * * Find a path between 2 elements. + * + * \note All 3 functions are similar, changes to one most likely apply to another. */ #include "MEM_guardedalloc.h" @@ -29,8 +31,11 @@ #include "bmesh.h" #include "bmesh_path.h" /* own include */ +#define COST_INIT_MAX FLT_MAX + /* -------------------------------------------------------------------- */ -/* Generic Helpers */ +/** \name Generic Helpers + * \{ */ /** * Use skip options when we want to start measuring from a boundary. @@ -40,16 +45,15 @@ static float step_cost_3_v3_ex( { float d1[3], d2[3]; - /* The cost is based on the simple sum of the length of the two edgees... */ + /* The cost is based on the simple sum of the length of the two edges. */ sub_v3_v3v3(d1, v2, v1); sub_v3_v3v3(d2, v3, v2); const float cost_12 = normalize_v3(d1); const float cost_23 = normalize_v3(d2); const float cost = ((skip_12 ? 0.0f : cost_12) + (skip_23 ? 0.0f : cost_23)); - /* but is biased to give higher values to sharp turns, so that it will take - * paths with fewer "turns" when selecting between equal-weighted paths between - * the two edges */ + /* But is biased to give higher values to sharp turns, so that it will take paths with + * fewer "turns" when selecting between equal-weighted paths between the two edges. */ return cost * (1.0f + 0.5f * (2.0f - sqrtf(fabsf(dot_v3v3(d1, d2))))); } @@ -58,8 +62,11 @@ static float step_cost_3_v3(const float v1[3], const float v2[3], const float v3 return step_cost_3_v3_ex(v1, v2, v3, false, false); } +/** \} */ + /* -------------------------------------------------------------------- */ -/* BM_mesh_calc_path_vert */ +/** \name BM_mesh_calc_path_vert + * \{ */ static void verttag_add_adjacent(HeapSimple *heap, BMVert *v_a, @@ -72,11 +79,11 @@ static void verttag_add_adjacent(HeapSimple *heap, { BMIter eiter; BMEdge *e; - /* loop over faces of face, but do so by first looping over loops */ + /* Loop over faces of face, but do so by first looping over loops. */ BM_ITER_ELEM (e, &eiter, v_a, BM_EDGES_OF_VERT) { BMVert *v_b = BM_edge_other_vert(e, v_a); if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) { - /* we know 'v_b' is not visited, check it out! */ + /* We know 'v_b' is not visited, check it out! */ const int v_b_index = BM_elem_index_get(v_b); const float cost_cut = params->use_topology_distance ? 1.0f : len_v3v3(v_a->co, v_b->co); const float cost_new = cost[v_a_index] + cost_cut; @@ -93,15 +100,15 @@ static void verttag_add_adjacent(HeapSimple *heap, if (params->use_step_face) { BMIter liter; BMLoop *l; - /* loop over faces of face, but do so by first looping over loops */ + /* Loop over faces of face, but do so by first looping over loops. */ BM_ITER_ELEM (l, &liter, v_a, BM_LOOPS_OF_VERT) { if (l->f->len > 3) { - /* skip loops on adjacent edges */ + /* Skip loops on adjacent edges. */ BMLoop *l_iter = l->next->next; do { BMVert *v_b = l_iter->v; if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) { - /* we know 'v_b' is not visited, check it out! */ + /* We know 'v_b' is not visited, check it out! */ const int v_b_index = BM_elem_index_get(v_b); const float cost_cut = params->use_topology_distance ? 1.0f : len_v3v3(v_a->co, v_b->co); @@ -127,7 +134,7 @@ LinkNode *BM_mesh_calc_path_vert(BMesh *bm, void *user_data) { LinkNode *path = NULL; - /* BM_ELEM_TAG flag is used to store visited edges */ + /* #BM_ELEM_TAG flag is used to store visited edges. */ BMVert *v; BMIter viter; HeapSimple *heap; @@ -135,7 +142,7 @@ LinkNode *BM_mesh_calc_path_vert(BMesh *bm, BMVert **verts_prev; int i, totvert; - /* note, would pass BM_EDGE except we are looping over all faces anyway */ + /* Note, would pass #BM_EDGE except we are looping over all faces anyway. */ // BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); // NOT NEEDED FOR FACETAG BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) { @@ -144,25 +151,25 @@ LinkNode *BM_mesh_calc_path_vert(BMesh *bm, } bm->elem_index_dirty &= ~BM_VERT; - /* alloc */ + /* Allocate. */ totvert = bm->totvert; verts_prev = MEM_callocN(sizeof(*verts_prev) * totvert, __func__); cost = MEM_mallocN(sizeof(*cost) * totvert, __func__); - copy_vn_fl(cost, totvert, 1e20f); + copy_vn_fl(cost, totvert, COST_INIT_MAX); /* * Arrays are now filled as follows: * - * As the search continues, verts_prev[n] will be the previous verts on the shortest - * path found so far to face n. BM_ELEM_TAG is used to tag elements we have visited, - * cost[n] will contain the length of the shortest + * As the search continues, `verts_prev[n]` will be the previous verts on the shortest + * path found so far to face `n`. #BM_ELEM_TAG is used to tag elements we have visited, + * `cost[n]` will contain the length of the shortest * path to face n found so far, Finally, heap is a priority heap which is built on the - * the same data as the cost array, but inverted: it is a worklist of faces prioritized + * the same data as the cost array, but inverted: it is a work-list of faces prioritized * by the shortest path found so far to the face. */ - /* regular dijkstra shortest path, but over faces instead of vertices */ + /* Regular dijkstra shortest path, but over faces instead of vertices. */ heap = BLI_heapsimple_new(); BLI_heapsimple_insert(heap, 0.0f, v_src); cost[BM_elem_index_get(v_src)] = 0.0f; @@ -193,8 +200,11 @@ LinkNode *BM_mesh_calc_path_vert(BMesh *bm, return path; } +/** \} */ + /* -------------------------------------------------------------------- */ -/* BM_mesh_calc_path_edge */ +/** \name BM_mesh_calc_path_edge + * \{ */ static float edgetag_cut_cost_vert(BMEdge *e_a, BMEdge *e_b, BMVert *v) { @@ -223,8 +233,8 @@ static void edgetag_add_adjacent(HeapSimple *heap, { const int e_a_index = BM_elem_index_get(e_a); - /* unlike vert/face, stepping faces disables scanning connected edges - * and only steps over faces (selecting a ring of edges instead of a loop) */ + /* Unlike vert/face, stepping faces disables scanning connected edges + * and only steps over faces (selecting a ring of edges instead of a loop). */ if (params->use_step_face == false || e_a->l == NULL) { BMIter viter; BMVert *v; @@ -234,14 +244,14 @@ static void edgetag_add_adjacent(HeapSimple *heap, BM_ITER_ELEM (v, &viter, e_a, BM_VERTS_OF_EDGE) { - /* don't walk over previous vertex */ + /* Don't walk over previous vertex. */ if ((edges_prev[e_a_index]) && (BM_vert_in_edge(edges_prev[e_a_index], v))) { continue; } BM_ITER_ELEM (e_b, &eiter, v, BM_EDGES_OF_VERT) { if (!BM_elem_flag_test(e_b, BM_ELEM_TAG)) { - /* we know 'e_b' is not visited, check it out! */ + /* We know 'e_b' is not visited, check it out! */ const int e_b_index = BM_elem_index_get(e_b); const float cost_cut = params->use_topology_distance ? 1.0f : @@ -267,7 +277,7 @@ static void edgetag_add_adjacent(HeapSimple *heap, l_cycle_iter = l_iter->next; l_cycle_end = l_iter; - /* good, but we need to allow this otherwise paths may fail to connect at all */ + /* Good, but we need to allow this otherwise paths may fail to connect at all. */ #if 0 if (l_iter->f->len > 3) { l_cycle_iter = l_cycle_iter->next; @@ -278,7 +288,7 @@ static void edgetag_add_adjacent(HeapSimple *heap, do { BMEdge *e_b = l_cycle_iter->e; if (!BM_elem_flag_test(e_b, BM_ELEM_TAG)) { - /* we know 'e_b' is not visited, check it out! */ + /* We know 'e_b' is not visited, check it out! */ const int e_b_index = BM_elem_index_get(e_b); const float cost_cut = params->use_topology_distance ? 1.0f : @@ -304,7 +314,7 @@ LinkNode *BM_mesh_calc_path_edge(BMesh *bm, void *user_data) { LinkNode *path = NULL; - /* BM_ELEM_TAG flag is used to store visited edges */ + /* #BM_ELEM_TAG flag is used to store visited edges. */ BMEdge *e; BMIter eiter; HeapSimple *heap; @@ -312,7 +322,7 @@ LinkNode *BM_mesh_calc_path_edge(BMesh *bm, BMEdge **edges_prev; int i, totedge; - /* note, would pass BM_EDGE except we are looping over all edges anyway */ + /* Note, would pass #BM_EDGE except we are looping over all edges anyway. */ BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) { @@ -321,25 +331,25 @@ LinkNode *BM_mesh_calc_path_edge(BMesh *bm, } bm->elem_index_dirty &= ~BM_EDGE; - /* alloc */ + /* Allocate. */ totedge = bm->totedge; - edges_prev = MEM_callocN(sizeof(*edges_prev) * totedge, "SeamPathPrevious"); - cost = MEM_mallocN(sizeof(*cost) * totedge, "SeamPathCost"); + edges_prev = MEM_callocN(sizeof(*edges_prev) * totedge, __func__); + cost = MEM_mallocN(sizeof(*cost) * totedge, __func__); - copy_vn_fl(cost, totedge, 1e20f); + copy_vn_fl(cost, totedge, COST_INIT_MAX); /* * Arrays are now filled as follows: * - * As the search continues, prevedge[n] will be the previous edge on the shortest - * path found so far to edge n. BM_ELEM_TAG is used to tag elements we have visited, - * cost[n] will contain the length of the shortest + * As the search continues, `edges_prev[n]` will be the previous edge on the shortest + * path found so far to edge `n`. #BM_ELEM_TAG is used to tag elements we have visited, + * `cost[n]` will contain the length of the shortest * path to edge n found so far, Finally, heap is a priority heap which is built on the - * the same data as the cost array, but inverted: it is a worklist of edges prioritized + * the same data as the cost array, but inverted: it is a work-list of edges prioritized * by the shortest path found so far to the edge. */ - /* regular dijkstra shortest path, but over edges instead of vertices */ + /* Regular dijkstra shortest path, but over edges instead of vertices. */ heap = BLI_heapsimple_new(); BLI_heapsimple_insert(heap, 0.0f, e_src); cost[BM_elem_index_get(e_src)] = 0.0f; @@ -370,8 +380,11 @@ LinkNode *BM_mesh_calc_path_edge(BMesh *bm, return path; } +/** \} */ + /* -------------------------------------------------------------------- */ -/* BM_mesh_calc_path_face */ +/** \name BM_mesh_calc_path_face + * \{ */ static float facetag_cut_cost_edge(BMFace *f_a, BMFace *f_b, @@ -387,15 +400,15 @@ static float facetag_cut_cost_edge(BMFace *f_a, #if 0 mid_v3_v3v3(e_cent, e->v1->co, e->v2->co); #else - /* for triangle fans it gives better results to pick a point on the edge */ + /* For triangle fans it gives better results to pick a point on the edge. */ { - float ix_e[3], ix_f[3], f; + float ix_e[3], ix_f[3]; isect_line_line_v3(e->v1->co, e->v2->co, f_a_cent, f_b_cent, ix_e, ix_f); - f = line_point_factor_v3(ix_e, e->v1->co, e->v2->co); - if (f < 0.0f) { + const float factor = line_point_factor_v3(ix_e, e->v1->co, e->v2->co); + if (factor < 0.0f) { copy_v3_v3(e_cent, e->v1->co); } - else if (f > 1.0f) { + else if (factor > 1.0f) { copy_v3_v3(e_cent, e->v2->co); } else { @@ -432,7 +445,7 @@ static void facetag_add_adjacent(HeapSimple *heap, { const int f_a_index = BM_elem_index_get(f_a); - /* loop over faces of face, but do so by first looping over loops */ + /* Loop over faces of face, but do so by first looping over loops. */ { BMIter liter; BMLoop *l_a; @@ -444,7 +457,7 @@ static void facetag_add_adjacent(HeapSimple *heap, do { BMFace *f_b = l_iter->f; if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) { - /* we know 'f_b' is not visited, check it out! */ + /* We know 'f_b' is not visited, check it out! */ const int f_b_index = BM_elem_index_get(f_b); const float cost_cut = params->use_topology_distance ? 1.0f : @@ -472,7 +485,7 @@ static void facetag_add_adjacent(HeapSimple *heap, if ((l_a != l_b) && !BM_loop_share_edge_check(l_a, l_b)) { BMFace *f_b = l_b->f; if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) { - /* we know 'f_b' is not visited, check it out! */ + /* We know 'f_b' is not visited, check it out! */ const int f_b_index = BM_elem_index_get(f_b); const float cost_cut = params->use_topology_distance ? 1.0f : @@ -499,7 +512,7 @@ LinkNode *BM_mesh_calc_path_face(BMesh *bm, void *user_data) { LinkNode *path = NULL; - /* BM_ELEM_TAG flag is used to store visited edges */ + /* #BM_ELEM_TAG flag is used to store visited edges. */ BMFace *f; BMIter fiter; HeapSimple *heap; @@ -510,7 +523,7 @@ LinkNode *BM_mesh_calc_path_face(BMesh *bm, /* Start measuring face path at the face edges, ignoring their centers. */ const void *const f_endpoints[2] = {f_src, f_dst}; - /* note, would pass BM_EDGE except we are looping over all faces anyway */ + /* Note, would pass #BM_EDGE except we are looping over all faces anyway. */ // BM_mesh_elem_index_ensure(bm, BM_VERT /* | BM_EDGE */); // NOT NEEDED FOR FACETAG BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) { @@ -519,25 +532,25 @@ LinkNode *BM_mesh_calc_path_face(BMesh *bm, } bm->elem_index_dirty &= ~BM_FACE; - /* alloc */ + /* Allocate. */ totface = bm->totface; faces_prev = MEM_callocN(sizeof(*faces_prev) * totface, __func__); cost = MEM_mallocN(sizeof(*cost) * totface, __func__); - copy_vn_fl(cost, totface, 1e20f); + copy_vn_fl(cost, totface, COST_INIT_MAX); /* * Arrays are now filled as follows: * - * As the search continues, faces_prev[n] will be the previous face on the shortest - * path found so far to face n. BM_ELEM_TAG is used to tag elements we have visited, - * cost[n] will contain the length of the shortest + * As the search continues, `faces_prev[n]` will be the previous face on the shortest + * path found so far to face `n`. #BM_ELEM_TAG is used to tag elements we have visited, + * `cost[n]` will contain the length of the shortest * path to face n found so far, Finally, heap is a priority heap which is built on the - * the same data as the cost array, but inverted: it is a worklist of faces prioritized + * the same data as the cost array, but inverted: it is a work-list of faces prioritized * by the shortest path found so far to the face. */ - /* regular dijkstra shortest path, but over faces instead of vertices */ + /* Regular dijkstra shortest path, but over faces instead of vertices. */ heap = BLI_heapsimple_new(); BLI_heapsimple_insert(heap, 0.0f, f_src); cost[BM_elem_index_get(f_src)] = 0.0f; @@ -567,3 +580,4 @@ LinkNode *BM_mesh_calc_path_face(BMesh *bm, return path; } +/** \} */ diff --git a/source/blender/bmesh/tools/bmesh_path_uv.c b/source/blender/bmesh/tools/bmesh_path_uv.c new file mode 100644 index 00000000000..57a70645187 --- /dev/null +++ b/source/blender/bmesh/tools/bmesh_path_uv.c @@ -0,0 +1,433 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +/** \file + * \ingroup bmesh + * + * Find a path between 2 elements in UV space. + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_heap_simple.h" +#include "BLI_linklist.h" +#include "BLI_math.h" + +#include "DNA_meshdata_types.h" + +#include "bmesh.h" +#include "bmesh_path_uv.h" /* own include */ +#include "intern/bmesh_query.h" +#include "intern/bmesh_query_uv.h" + +#define COST_INIT_MAX FLT_MAX + +/* -------------------------------------------------------------------- */ +/** \name Generic Helpers + * \{ */ + +/** + * Use skip options when we want to start measuring from a boundary. + * + * See #step_cost_3_v3_ex in bmesh_path.c which follows the same logic. + */ +static float step_cost_3_v2_ex( + const float v1[2], const float v2[2], const float v3[2], bool skip_12, bool skip_23) +{ + float d1[2], d2[2]; + + /* The cost is based on the simple sum of the length of the two edges. */ + sub_v2_v2v2(d1, v2, v1); + sub_v2_v2v2(d2, v3, v2); + const float cost_12 = normalize_v2(d1); + const float cost_23 = normalize_v2(d2); + const float cost = ((skip_12 ? 0.0f : cost_12) + (skip_23 ? 0.0f : cost_23)); + + /* But is biased to give higher values to sharp turns, so that it will take paths with + * fewer "turns" when selecting between equal-weighted paths between the two edges. */ + 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]) +{ + return step_cost_3_v2_ex(v1, v2, v3, false, false); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name BM_mesh_calc_path_uv_vert + * \{ */ + +static void looptag_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 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}; + + { + BMIter liter; + BMLoop *l; + /* Loop over faces of face, but do so by first looping over loops. */ + BM_ITER_ELEM (l, &liter, l_a->v, BM_LOOPS_OF_VERT) { + const MLoopUV *luv = BM_ELEM_CD_GET_VOID_P(l, cd_loop_uv_offset); + if (equals_v2v2(luv_a->uv, luv->uv)) { + /* 'l_a' is already tagged, tag all adjacent. */ + BM_elem_flag_enable(l, BM_ELEM_TAG); + BMLoop *l_b = l->next; + do { + if (!BM_elem_flag_test(l_b, BM_ELEM_TAG)) { + const MLoopUV *luv_b = BM_ELEM_CD_GET_VOID_P(l_b, cd_loop_uv_offset); + const float uv_b[2] = {luv_b->uv[0], luv_b->uv[1] / params->aspect_y}; + /* 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 : len_v2v2(uv_a, uv_b); + 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); + } + } + /* This means we only step onto `l->prev` & `l->next`. */ + if (params->use_step_face == false) { + if (l_b == l->next) { + l_b = l->prev->prev; + } + } + } while ((l_b = l_b->next) != l); + } + } + } +} + +struct LinkNode *BM_mesh_calc_path_uv_vert(BMesh *bm, + BMLoop *l_src, + BMLoop *l_dst, + const struct BMCalcPathUVParams *params, + bool (*filter_fn)(BMLoop *, void *), + void *user_data) +{ + LinkNode *path = NULL; + /* BM_ELEM_TAG flag is used to store visited edges */ + BMIter viter; + HeapSimple *heap; + float *cost; + BMLoop **loops_prev; + int i = 0, totloop; + BMFace *f; + + /* Note, would pass BM_EDGE except we are looping over all faces anyway. */ + // BM_mesh_elem_index_ensure(bm, BM_LOOP); // NOT NEEDED FOR FACETAG + + BM_ITER_MESH (f, &viter, 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); /* set_inline */ + i += 1; + } while ((l_iter = l_iter->next) != l_first); + } + bm->elem_index_dirty &= ~BM_LOOP; + + /* Allocate. */ + 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 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->v == l_dst->v) && BM_loop_uv_share_vert_check(l, l_dst, params->cd_loop_uv_offset)) { + break; + } + + 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); + } + } + + if ((l->v == l_dst->v) && BM_loop_uv_share_vert_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; +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name BM_mesh_calc_path_uv_edge + * \{ */ +/* TODO(campbell): not very urgent, since the operator fakes this using vertex path. */ + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name BM_mesh_calc_path_uv_face + * \{ */ + +static float facetag_cut_cost_edge_uv(BMFace *f_a, + BMFace *f_b, + BMLoop *l_edge, + const void *const f_endpoints[2], + const float aspect_v2[2], + const int cd_loop_uv_offset) +{ + float f_a_cent[2]; + float f_b_cent[2]; + float e_cent[2]; + + BM_face_uv_calc_center_median_weighted(f_a, aspect_v2, cd_loop_uv_offset, f_a_cent); + BM_face_uv_calc_center_median_weighted(f_b, aspect_v2, cd_loop_uv_offset, f_b_cent); + + const float *co_v1 = ((const MLoopUV *)BM_ELEM_CD_GET_VOID_P(l_edge, cd_loop_uv_offset))->uv; + const float *co_v2 = + ((const MLoopUV *)BM_ELEM_CD_GET_VOID_P(l_edge->next, cd_loop_uv_offset))->uv; + +#if 0 + mid_v2_v2v2(e_cent, co_v1, co_v2); +#else + /* For triangle fans it gives better results to pick a point on the edge. */ + { + float ix_e[2]; + isect_line_line_v2_point(co_v1, co_v2, f_a_cent, f_b_cent, ix_e); + const float factor = line_point_factor_v2(ix_e, co_v1, co_v2); + if (factor < 0.0f) { + copy_v2_v2(e_cent, co_v1); + } + else if (factor > 1.0f) { + copy_v2_v2(e_cent, co_v2); + } + else { + copy_v2_v2(e_cent, ix_e); + } + } +#endif + + /* Apply aspect before calculating cost. */ + mul_v2_v2(f_a_cent, aspect_v2); + mul_v2_v2(f_b_cent, aspect_v2); + mul_v2_v2(e_cent, aspect_v2); + + return step_cost_3_v2_ex( + f_a_cent, e_cent, f_b_cent, (f_a == f_endpoints[0]), (f_b == f_endpoints[1])); +} + +static float facetag_cut_cost_vert_uv(BMFace *f_a, + BMFace *f_b, + BMLoop *l_vert, + const void *const f_endpoints[2], + const float aspect_v2[2], + const int cd_loop_uv_offset) +{ + float f_a_cent[2]; + float f_b_cent[2]; + float v_cent[2]; + + BM_face_uv_calc_center_median_weighted(f_a, aspect_v2, cd_loop_uv_offset, f_a_cent); + BM_face_uv_calc_center_median_weighted(f_b, aspect_v2, cd_loop_uv_offset, f_b_cent); + + copy_v2_v2(v_cent, ((const MLoopUV *)BM_ELEM_CD_GET_VOID_P(l_vert, cd_loop_uv_offset))->uv); + + mul_v2_v2(f_a_cent, aspect_v2); + mul_v2_v2(f_b_cent, aspect_v2); + mul_v2_v2(v_cent, aspect_v2); + + return step_cost_3_v2_ex( + f_a_cent, v_cent, f_b_cent, (f_a == f_endpoints[0]), (f_b == f_endpoints[1])); +} + +static void facetag_add_adjacent_uv(HeapSimple *heap, + BMFace *f_a, + BMFace **faces_prev, + float *cost, + const void *const f_endpoints[2], + const float aspect_v2[2], + const struct BMCalcPathUVParams *params) +{ + const uint 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. */ + { + BMIter liter; + BMLoop *l_a; + + BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) { + BMLoop *l_first, *l_iter; + + /* Check there is an adjacent face to loop over. */ + if (l_a != l_a->radial_next) { + l_iter = l_first = l_a->radial_next; + do { + BMFace *f_b = l_iter->f; + if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) { + if (BM_loop_uv_share_edge_check(l_a, l_iter, cd_loop_uv_offset)) { + /* We know 'f_b' is not visited, check it out! */ + const int f_b_index = BM_elem_index_get(f_b); + const float cost_cut = + params->use_topology_distance ? + 1.0f : + facetag_cut_cost_edge_uv( + f_a, f_b, l_iter, f_endpoints, aspect_v2, cd_loop_uv_offset); + const float cost_new = cost[f_a_index] + cost_cut; + + if (cost[f_b_index] > cost_new) { + cost[f_b_index] = cost_new; + faces_prev[f_b_index] = f_a; + BLI_heapsimple_insert(heap, cost_new, f_b); + } + } + } + } while ((l_iter = l_iter->radial_next) != l_first); + } + } + } + + if (params->use_step_face) { + BMIter liter; + BMLoop *l_a; + + BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) { + BMIter litersub; + BMLoop *l_b; + BM_ITER_ELEM (l_b, &litersub, l_a->v, BM_LOOPS_OF_VERT) { + if ((l_a != l_b) && !BM_loop_share_edge_check(l_a, l_b)) { + BMFace *f_b = l_b->f; + if (!BM_elem_flag_test(f_b, BM_ELEM_TAG)) { + if (BM_loop_uv_share_vert_check(l_a, l_b, cd_loop_uv_offset)) { + /* We know 'f_b' is not visited, check it out! */ + const int f_b_index = BM_elem_index_get(f_b); + const float cost_cut = + params->use_topology_distance ? + 1.0f : + facetag_cut_cost_vert_uv( + f_a, f_b, l_a, f_endpoints, aspect_v2, cd_loop_uv_offset); + const float cost_new = cost[f_a_index] + cost_cut; + + if (cost[f_b_index] > cost_new) { + cost[f_b_index] = cost_new; + faces_prev[f_b_index] = f_a; + BLI_heapsimple_insert(heap, cost_new, f_b); + } + } + } + } + } + } + } +} + +struct LinkNode *BM_mesh_calc_path_uv_face(BMesh *bm, + BMFace *f_src, + BMFace *f_dst, + const struct BMCalcPathUVParams *params, + bool (*filter_fn)(BMFace *, void *), + void *user_data) +{ + const float aspect_v2[2] = {1.0f, 1.0f / params->aspect_y}; + LinkNode *path = NULL; + /* BM_ELEM_TAG flag is used to store visited edges */ + BMIter fiter; + HeapSimple *heap; + float *cost; + BMFace **faces_prev; + int i = 0, totface; + + /* Start measuring face path at the face edges, ignoring their centers. */ + const void *const f_endpoints[2] = {f_src, f_dst}; + + /* Note, would pass BM_EDGE except we are looping over all faces anyway. */ + // BM_mesh_elem_index_ensure(bm, BM_LOOP); // NOT NEEDED FOR FACETAG + + { + BMFace *f; + BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { + BM_elem_flag_set(f, BM_ELEM_TAG, !filter_fn(f, user_data)); + BM_elem_index_set(f, i); /* set_inline */ + i += 1; + } + bm->elem_index_dirty &= ~BM_FACE; + } + + /* Allocate. */ + totface = bm->totface; + faces_prev = MEM_callocN(sizeof(*faces_prev) * totface, __func__); + cost = MEM_mallocN(sizeof(*cost) * totface, __func__); + + copy_vn_fl(cost, totface, COST_INIT_MAX); + + /* Regular dijkstra shortest path, but over UV faces instead of vertices. */ + heap = BLI_heapsimple_new(); + BLI_heapsimple_insert(heap, 0.0f, f_src); + cost[BM_elem_index_get(f_src)] = 0.0f; + + BMFace *f = NULL; + while (!BLI_heapsimple_is_empty(heap)) { + f = BLI_heapsimple_pop_min(heap); + + if (f == f_dst) { + break; + } + + if (!BM_elem_flag_test(f, BM_ELEM_TAG)) { + /* Adjacent loops are tagged while stepping to avoid 2x loops. */ + BM_elem_flag_enable(f, BM_ELEM_TAG); + facetag_add_adjacent_uv(heap, f, faces_prev, cost, f_endpoints, aspect_v2, params); + } + } + + if (f == f_dst) { + do { + BLI_linklist_prepend(&path, f); + } while ((f = faces_prev[BM_elem_index_get(f)])); + } + + MEM_freeN(faces_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 new file mode 100644 index 00000000000..c7c5768f7d0 --- /dev/null +++ b/source/blender/bmesh/tools/bmesh_path_uv.h @@ -0,0 +1,47 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#ifndef __BMESH_PATH_UV_H__ +#define __BMESH_PATH_UV_H__ + +/** \file + * \ingroup bmesh + */ + +struct BMCalcPathUVParams { + uint use_topology_distance : 1; + uint use_step_face : 1; + uint cd_loop_uv_offset; + float aspect_y; +}; + +struct LinkNode *BM_mesh_calc_path_uv_vert(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, + BMFace *f_src, + BMFace *f_dst, + const struct BMCalcPathUVParams *params, + bool (*filter_fn)(BMFace *, void *), + void *user_data) ATTR_WARN_UNUSED_RESULT + ATTR_NONNULL(1, 2, 3, 5); + +#endif /* __BMESH_PATH_UV_H__ */ diff --git a/source/blender/bmesh/tools/bmesh_region_match.c b/source/blender/bmesh/tools/bmesh_region_match.c index 8de23b696bf..d222ea214c4 100644 --- a/source/blender/bmesh/tools/bmesh_region_match.c +++ b/source/blender/bmesh/tools/bmesh_region_match.c @@ -1299,7 +1299,9 @@ static UUIDFashMatch *bm_vert_fasthash_create(BMesh *bm, const uint depth) return id_curr; } -static void bm_vert_fasthash_edge_order(UUIDFashMatch *fm, const BMEdge *e, UUIDFashMatch e_fm[2]) +static void bm_vert_fasthash_edge_order(const UUIDFashMatch *fm, + const BMEdge *e, + UUIDFashMatch e_fm[2]) { e_fm[0] = fm[BM_elem_index_get(e->v1)]; e_fm[1] = fm[BM_elem_index_get(e->v2)]; |