[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [57224] trunk/blender: edit-mesh improvements to select shortest path
Campbell Barton
ideasman42 at gmail.com
Tue Jun 4 03:23:52 CEST 2013
Revision: 57224
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=57224
Author: campbellbarton
Date: 2013-06-04 01:23:51 +0000 (Tue, 04 Jun 2013)
Log Message:
-----------
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).
Modified Paths:
--------------
trunk/blender/release/scripts/startup/bl_ui/space_view3d.py
trunk/blender/source/blender/bmesh/CMakeLists.txt
trunk/blender/source/blender/bmesh/bmesh.h
trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c
trunk/blender/source/blender/bmesh/intern/bmesh_operators.h
trunk/blender/source/blender/bmesh/operators/bmo_utils.c
trunk/blender/source/blender/editors/mesh/CMakeLists.txt
trunk/blender/source/blender/editors/mesh/editmesh_select.c
trunk/blender/source/blender/editors/mesh/mesh_intern.h
trunk/blender/source/blender/editors/mesh/mesh_ops.c
trunk/blender/source/blender/makesrna/intern/rna_scene.c
Added Paths:
-----------
trunk/blender/source/blender/bmesh/tools/bmesh_path.c
trunk/blender/source/blender/bmesh/tools/bmesh_path.h
trunk/blender/source/blender/editors/mesh/editmesh_path.c
Modified: trunk/blender/release/scripts/startup/bl_ui/space_view3d.py
===================================================================
--- trunk/blender/release/scripts/startup/bl_ui/space_view3d.py 2013-06-03 19:52:53 UTC (rev 57223)
+++ trunk/blender/release/scripts/startup/bl_ui/space_view3d.py 2013-06-04 01:23:51 UTC (rev 57224)
@@ -624,7 +624,7 @@
layout.operator("mesh.select_axis", text="Side of Active")
layout.operator("mesh.select_linked", text="Linked")
- layout.operator("mesh.select_vertex_path", text="Vertex Path")
+ layout.operator("mesh.shortest_path_select", text="Shortest Path")
layout.operator("mesh.loop_multi_select", text="Edge Loop").ring = False
layout.operator("mesh.loop_multi_select", text="Edge Ring").ring = True
@@ -1829,7 +1829,7 @@
layout.operator("mesh.blend_from_shape")
layout.operator("mesh.shape_propagate_to_all")
- layout.operator("mesh.select_vertex_path")
+ layout.operator("mesh.shortest_path_select")
layout.operator("mesh.sort_elements")
layout.operator("mesh.symmetrize")
@@ -1902,8 +1902,6 @@
layout.operator("mesh.remove_doubles")
layout.operator("mesh.sort_elements", text="Sort Vertices").elements = {'VERT'}
- layout.operator("mesh.select_vertex_path")
-
layout.operator("mesh.blend_from_shape")
layout.operator("object.vertex_group_blend")
Modified: trunk/blender/source/blender/bmesh/CMakeLists.txt
===================================================================
--- trunk/blender/source/blender/bmesh/CMakeLists.txt 2013-06-03 19:52:53 UTC (rev 57223)
+++ trunk/blender/source/blender/bmesh/CMakeLists.txt 2013-06-04 01:23:51 UTC (rev 57224)
@@ -122,6 +122,8 @@
tools/bmesh_decimate.h
tools/bmesh_edgesplit.c
tools/bmesh_edgesplit.h
+ tools/bmesh_path.c
+ tools/bmesh_path.h
tools/bmesh_triangulate.c
tools/bmesh_triangulate.h
Modified: trunk/blender/source/blender/bmesh/bmesh.h
===================================================================
--- trunk/blender/source/blender/bmesh/bmesh.h 2013-06-03 19:52:53 UTC (rev 57223)
+++ trunk/blender/source/blender/bmesh/bmesh.h 2013-06-04 01:23:51 UTC (rev 57224)
@@ -271,6 +271,7 @@
#include "tools/bmesh_bevel.h"
#include "tools/bmesh_decimate.h"
+#include "tools/bmesh_path.h"
#include "tools/bmesh_triangulate.h"
#ifdef __cplusplus
Modified: trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c 2013-06-03 19:52:53 UTC (rev 57223)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c 2013-06-04 01:23:51 UTC (rev 57224)
@@ -1276,27 +1276,6 @@
};
/*
- * Shortest Path.
- *
- * Select the shortest path between 2 verts.
- */
-static BMOpDefine bmo_shortest_path_def = {
- "shortest_path",
- /* slots_in */
- {{"vert_start", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT | BMO_OP_SLOT_SUBTYPE_ELEM_IS_SINGLE}}, /* start vertex */
- {"vert_end", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT | BMO_OP_SLOT_SUBTYPE_ELEM_IS_SINGLE}}, /* end vertex */
- {"type", BMO_OP_SLOT_INT}, /* type of selection */
- {{'\0'}},
- },
- /* slots_out */
- {{"verts.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT}}, /* output vertices */
- {{'\0'}},
- },
- bmo_shortest_path_exec,
- BMO_OPTYPE_FLAG_SELECT_FLUSH,
-};
-
-/*
* Edge Split.
*
* Disconnects faces along input edges.
@@ -1769,7 +1748,6 @@
&bmo_rotate_edges_def,
&bmo_rotate_uvs_def,
&bmo_scale_def,
- &bmo_shortest_path_def,
&bmo_similar_edges_def,
&bmo_similar_faces_def,
&bmo_similar_verts_def,
Modified: trunk/blender/source/blender/bmesh/intern/bmesh_operators.h
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_operators.h 2013-06-03 19:52:53 UTC (rev 57223)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_operators.h 2013-06-04 01:23:51 UTC (rev 57224)
@@ -110,12 +110,6 @@
SIMVERT_EDGE
};
-/* vertex path selection values */
-enum {
- VPATH_SELECT_EDGE_LENGTH = 0,
- VPATH_SELECT_TOPOLOGICAL
-};
-
/* Poke face center calculation */
enum {
BMOP_POKE_MEAN_WEIGHTED = 0,
Modified: trunk/blender/source/blender/bmesh/operators/bmo_utils.c
===================================================================
--- trunk/blender/source/blender/bmesh/operators/bmo_utils.c 2013-06-03 19:52:53 UTC (rev 57223)
+++ trunk/blender/source/blender/bmesh/operators/bmo_utils.c 2013-06-04 01:23:51 UTC (rev 57224)
@@ -673,111 +673,3 @@
}
}
}
-
-
-/*************************************************************************** *
- * shortest vertex path select
- *************************************************************************** */
-
-typedef struct ElemNode {
- BMVert *v; /* vertex */
- BMVert *parent; /* node parent id */
- float weight; /* node weight */
- HeapNode *hn; /* heap node */
-} ElemNode;
-
-#define VERT_MARK 1
-
-void bmo_shortest_path_exec(BMesh *bm, BMOperator *op)
-{
- BMIter v_iter; /* mesh verts iterator */
- BMVert *sv, *ev; /* starting vertex, ending vertex */
- BMVert *v; /* mesh vertex */
- Heap *h = NULL;
-
- ElemNode *vert_list = NULL;
-
- int num_total = 0 /*, num_sels = 0 */, i = 0;
- const int type = BMO_slot_int_get(op->slots_in, "type");
-
- sv = BMO_slot_buffer_get_single(BMO_slot_get(op->slots_in, "vert_start"));
- ev = BMO_slot_buffer_get_single(BMO_slot_get(op->slots_in, "vert_end"));
-
- num_total = BM_mesh_elem_count(bm, BM_VERT);
-
- /* allocate memory for the nodes */
- vert_list = (ElemNode *)MEM_mallocN(sizeof(ElemNode) * num_total, "vertex nodes");
-
- /* iterate through all the mesh vertices */
- /* loop through all the vertices and fill the vertices/indices structure */
- i = 0;
- BM_ITER_MESH (v, &v_iter, bm, BM_VERTS_OF_MESH) {
- vert_list[i].v = v;
- vert_list[i].parent = NULL;
- vert_list[i].weight = FLT_MAX;
- BM_elem_index_set(v, i); /* set_inline */
- i++;
- }
- bm->elem_index_dirty &= ~BM_VERT;
-
- /*
- * we now have everything we need, start Dijkstra path finding algorithm
- */
-
- /* set the distance/weight of the start vertex to 0 */
- vert_list[BM_elem_index_get(sv)].weight = 0.0f;
-
- h = BLI_heap_new();
-
- for (i = 0; i < num_total; i++) {
- vert_list[i].hn = BLI_heap_insert(h, vert_list[i].weight, vert_list[i].v);
- }
-
- while (!BLI_heap_is_empty(h)) {
- BMEdge *e;
- BMIter e_i;
- float v_weight;
-
- /* take the vertex with the lowest weight out of the heap */
- BMVert *v = (BMVert *)BLI_heap_popmin(h);
-
- if (vert_list[BM_elem_index_get(v)].weight == FLT_MAX) /* this means that there is no path */
- break;
-
- v_weight = vert_list[BM_elem_index_get(v)].weight;
-
- BM_ITER_ELEM (e, &e_i, v, BM_EDGES_OF_VERT) {
- BMVert *u;
- float e_weight = v_weight;
-
- if (type == VPATH_SELECT_EDGE_LENGTH)
- e_weight += len_v3v3(e->v1->co, e->v2->co);
- else e_weight += 1.0f;
-
- u = (e->v1 == v) ? e->v2 : e->v1;
-
- if (e_weight < vert_list[BM_elem_index_get(u)].weight) { /* is this path shorter ? */
- /* add it if so */
- vert_list[BM_elem_index_get(u)].parent = v;
- vert_list[BM_elem_index_get(u)].weight = e_weight;
-
- /* we should do a heap update node function!!! :-/ */
- BLI_heap_remove(h, vert_list[BM_elem_index_get(u)].hn);
- BLI_heap_insert(h, e_weight, u);
- }
- }
- }
-
- /* now we trace the path (if it exists) */
- v = ev;
-
- while (vert_list[BM_elem_index_get(v)].parent != NULL) {
- BMO_elem_flag_enable(bm, v, VERT_MARK);
- v = vert_list[BM_elem_index_get(v)].parent;
- }
-
- BLI_heap_free(h, NULL);
- MEM_freeN(vert_list);
-
- BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "verts.out", BM_VERT, VERT_MARK);
-}
Added: trunk/blender/source/blender/bmesh/tools/bmesh_path.c
===================================================================
--- trunk/blender/source/blender/bmesh/tools/bmesh_path.c (rev 0)
+++ trunk/blender/source/blender/bmesh/tools/bmesh_path.c 2013-06-04 01:23:51 UTC (rev 57224)
@@ -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) {
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list