diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-06-04 05:23:51 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-06-04 05:23:51 +0400 |
commit | 48fd740096c283243498d6271b6bff5da275cb36 (patch) | |
tree | 2a871557ced1ed6e4e02334fd3249db30e461b4d /source/blender/bmesh/tools/bmesh_path.c | |
parent | b537bc011be07a860d2acd1b61f5660195935327 (diff) |
edit-mesh improvements to select shortest path
- Ctrl+RMB only worked for edges & faces
- Menu item 'Select Shortest Path' only worked for vertices.
Now Ctrl+RMB works for vertices and the menu item works for verts/edges/faces (depending on the current selection).
Diffstat (limited to 'source/blender/bmesh/tools/bmesh_path.c')
-rw-r--r-- | source/blender/bmesh/tools/bmesh_path.c | 411 |
1 files changed, 411 insertions, 0 deletions
diff --git a/source/blender/bmesh/tools/bmesh_path.c b/source/blender/bmesh/tools/bmesh_path.c new file mode 100644 index 00000000000..eda252f18f5 --- /dev/null +++ b/source/blender/bmesh/tools/bmesh_path.c @@ -0,0 +1,411 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * 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. + * + * The Original Code is Copyright (C) 2004 Blender Foundation. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): none yet. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/bmesh/tools/bmesh_path.c + * \ingroup bmesh + * + * Find a path between 2 elements. + * + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_math.h" +#include "BLI_linklist.h" +#include "BLI_heap.h" + +#include "bmesh.h" +#include "bmesh_path.h" /* own include */ + +/* -------------------------------------------------------------------- */ +/* Generic Helpers */ + +static float step_cost_3_v3(const float v1[3], const float v2[3], const float v3[3]) +{ + float cost, d1[3], d2[3]; + + + /* The cost is based on the simple sum of the length of the two edgees... */ + sub_v3_v3v3(d1, v2, v1); + sub_v3_v3v3(d2, v3, v2); + cost = normalize_v3(d1) + normalize_v3(d2); + + /* 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 */ + cost = cost * (1.0f + 0.5f * (2.0f - sqrtf(fabsf(dot_v3v3(d1, d2))))); + + return cost; +} + + + +/* -------------------------------------------------------------------- */ +/* BM_mesh_calc_path_vert */ + +static void verttag_add_adjacent(Heap *heap, BMVert *v_a, BMVert **verts_prev, float *cost, const bool use_length) +{ + BMIter eiter; + BMEdge *e; + BMVert *v_b; + + const int v_a_index = BM_elem_index_get(v_a); + + /* loop over faces of face, but do so by first looping over loops */ + BM_ITER_ELEM (e, &eiter, v_a, BM_EDGES_OF_VERT) { + v_b = BM_edge_other_vert(e, v_a); + if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) { + /* we know 'f_b' is not visited, check it out! */ + const int v_b_index = BM_elem_index_get(v_b); + const float cost_cut = use_length ? len_v3v3(v_a->co, v_b->co) : 1.0f; + const float cost_new = cost[v_a_index] + cost_cut; + + if (cost[v_b_index] > cost_new) { + cost[v_b_index] = cost_new; + verts_prev[v_b_index] = v_a; + BLI_heap_insert(heap, cost_new, v_b); + } + } + } +} + +LinkNode *BM_mesh_calc_path_vert( + BMesh *bm, BMVert *v_src, BMVert *v_dst, const bool use_length, + void *user_data, bool (*test_fn)(BMVert *, void *user_data)) +{ + LinkNode *path = NULL; + /* BM_ELEM_TAG flag is used to store visited edges */ + BMVert *v; + BMIter viter; + Heap *heap; + float *cost; + BMVert **verts_prev; + int i, totvert; + + /* 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) { + if (test_fn(v, user_data)) { + BM_elem_flag_disable(v, BM_ELEM_TAG); + } + else { + BM_elem_flag_enable(v, BM_ELEM_TAG); + } + + BM_elem_index_set(v, i); /* set_inline */ + } + bm->elem_index_dirty &= ~BM_VERT; + + /* alloc */ + totvert = bm->totvert; + verts_prev = MEM_callocN(sizeof(*verts_prev) * totvert, __func__); + cost = MEM_mallocN(sizeof(*cost) * totvert, __func__); + + fill_vn_fl(cost, totvert, 1e20f); + + /* + * 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 + * 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 + * by the shortest path found so far to the face. + */ + + /* regular dijkstra shortest path, but over faces instead of vertices */ + heap = BLI_heap_new(); + BLI_heap_insert(heap, 0.0f, v_src); + cost[BM_elem_index_get(v_src)] = 0.0f; + + while ((v = BLI_heap_popmin(heap))) { + + if (v == v_dst) + break; + + if (!BM_elem_flag_test(v, BM_ELEM_TAG)) { + BM_elem_flag_enable(v, BM_ELEM_TAG); + verttag_add_adjacent(heap, v, verts_prev, cost, use_length); + } + } + + if (v == v_dst) { + do { + BLI_linklist_prepend(&path, v); + } while ((v = verts_prev[BM_elem_index_get(v)])); + } + + MEM_freeN(verts_prev); + MEM_freeN(cost); + BLI_heap_free(heap, NULL); + + return path; +} + + + +/* -------------------------------------------------------------------- */ +/* BM_mesh_calc_path_edge */ + + +static float edgetag_cut_cost(BMEdge *e1, BMEdge *e2, BMVert *v) +{ + BMVert *v1 = BM_edge_other_vert(e1, v); + BMVert *v2 = BM_edge_other_vert(e2, v); + return step_cost_3_v3(v1->co, v->co, v2->co); +} + +static void edgetag_add_adjacent(Heap *heap, BMEdge *e1, BMEdge **edges_prev, float *cost, const bool use_length) +{ + BMIter viter; + BMVert *v; + + BMIter eiter; + BMEdge *e2; + + const int e1_index = BM_elem_index_get(e1); + + BM_ITER_ELEM (v, &viter, e1, BM_VERTS_OF_EDGE) { + BM_ITER_ELEM (e2, &eiter, v, BM_EDGES_OF_VERT) { + if (!BM_elem_flag_test(e2, BM_ELEM_TAG)) { + /* we know 'e2' is not visited, check it out! */ + const int e2_index = BM_elem_index_get(e2); + const float cost_cut = use_length ? edgetag_cut_cost(e1, e2, v) : 1.0f; + const float cost_new = cost[e1_index] + cost_cut; + + if (cost[e2_index] > cost_new) { + cost[e2_index] = cost_new; + edges_prev[e2_index] = e1; + BLI_heap_insert(heap, cost_new, e2); + } + } + } + } +} + + +LinkNode *BM_mesh_calc_path_edge( + BMesh *bm, BMEdge *e_src, BMEdge *e_dst, const bool use_length, + void *user_data, bool (*filter_fn)(BMEdge *, void *user_data)) +{ + LinkNode *path = NULL; + /* BM_ELEM_TAG flag is used to store visited edges */ + BMEdge *e; + BMIter eiter; + Heap *heap; + float *cost; + BMEdge **edges_prev; + int i, totedge; + + /* 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) { + if (filter_fn(e, user_data)) { + BM_elem_flag_disable(e, BM_ELEM_TAG); + } + else { + BM_elem_flag_enable(e, BM_ELEM_TAG); + } + + BM_elem_index_set(e, i); /* set_inline */ + } + bm->elem_index_dirty &= ~BM_EDGE; + + /* alloc */ + totedge = bm->totedge; + edges_prev = MEM_callocN(sizeof(*edges_prev) * totedge, "SeamPathPrevious"); + cost = MEM_mallocN(sizeof(*cost) * totedge, "SeamPathCost"); + + fill_vn_fl(cost, totedge, 1e20f); + + /* + * 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 + * 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 + * by the shortest path found so far to the edge. + */ + + /* regular dijkstra shortest path, but over edges instead of vertices */ + heap = BLI_heap_new(); + BLI_heap_insert(heap, 0.0f, e_src); + cost[BM_elem_index_get(e_src)] = 0.0f; + + while ((e = BLI_heap_popmin(heap))) { + + if (e == e_dst) + break; + + if (!BM_elem_flag_test(e, BM_ELEM_TAG)) { + BM_elem_flag_enable(e, BM_ELEM_TAG); + edgetag_add_adjacent(heap, e, edges_prev, cost, use_length); + } + } + + if (e == e_dst) { + do { + BLI_linklist_prepend(&path, e); + } while ((e = edges_prev[BM_elem_index_get(e)])); + } + + MEM_freeN(edges_prev); + MEM_freeN(cost); + BLI_heap_free(heap, NULL); + + return path; +} + + + +/* -------------------------------------------------------------------- */ +/* BM_mesh_calc_path_face */ + +static float facetag_cut_cost(BMFace *f_a, BMFace *f_b, BMEdge *e) +{ + float f_a_cent[3]; + float f_b_cent[3]; + float e_cent[3]; + + BM_face_calc_center_mean(f_a, f_a_cent); + BM_face_calc_center_mean(f_b, f_b_cent); + mid_v3_v3v3(e_cent, e->v1->co, e->v2->co); + + return step_cost_3_v3(f_a_cent, e_cent, f_b_cent); +} + +static void facetag_add_adjacent(Heap *heap, BMFace *f_a, BMFace **faces_prev, float *cost, const bool use_length) +{ + BMIter liter; + BMLoop *l_a; + BMFace *f_b; + + const int f_a_index = BM_elem_index_get(f_a); + + /* loop over faces of face, but do so by first looping over loops */ + BM_ITER_ELEM (l_a, &liter, f_a, BM_LOOPS_OF_FACE) { + BMLoop *l_first; + BMLoop *l_iter; + + l_iter = l_first = l_a; + do { + 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! */ + const int f_b_index = BM_elem_index_get(f_b); + const float cost_cut = use_length ? facetag_cut_cost(f_a, f_b, l_iter->e) : 1.0f; + 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_heap_insert(heap, cost_new, f_b); + } + } + } while ((l_iter = l_iter->radial_next) != l_first); + } +} + +LinkNode *BM_mesh_calc_path_face( + BMesh *bm, BMFace *f_src, BMFace *f_dst, const bool use_length, + void *user_data, bool (*test_fn)(BMFace *, void *user_data)) +{ + LinkNode *path = NULL; + /* BM_ELEM_TAG flag is used to store visited edges */ + BMFace *f; + BMIter fiter; + Heap *heap; + float *cost; + BMFace **faces_prev; + int i, totface; + + /* 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) { + if (test_fn(f, user_data)) { + BM_elem_flag_disable(f, BM_ELEM_TAG); + } + else { + BM_elem_flag_enable(f, BM_ELEM_TAG); + } + + BM_elem_index_set(f, i); /* set_inline */ + } + bm->elem_index_dirty &= ~BM_FACE; + + /* alloc */ + totface = bm->totface; + faces_prev = MEM_callocN(sizeof(*faces_prev) * totface, __func__); + cost = MEM_mallocN(sizeof(*cost) * totface, __func__); + + fill_vn_fl(cost, totface, 1e20f); + + /* + * 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 + * 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 + * by the shortest path found so far to the face. + */ + + /* regular dijkstra shortest path, but over faces instead of vertices */ + heap = BLI_heap_new(); + BLI_heap_insert(heap, 0.0f, f_src); + cost[BM_elem_index_get(f_src)] = 0.0f; + + while ((f = BLI_heap_popmin(heap))) { + + if (f == f_dst) + break; + + if (!BM_elem_flag_test(f, BM_ELEM_TAG)) { + BM_elem_flag_enable(f, BM_ELEM_TAG); + facetag_add_adjacent(heap, f, faces_prev, cost, use_length); + } + } + + 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_heap_free(heap, NULL); + + return path; +} |