利用者:SaphireS/gsoc2016/selectshortestpath

Select/Pick shortest Path

This page documents how the Select/Pick Shortest Path Editmesh operator works. Actually those are 2 operators, the Select shortest path which is called from the menu via Select->shortest path and operates on the last 2 selected elements and Pick shortest path, which is called by Ctrl+RMB on a element to automatically connect it to the last selected element. This is very useful for quickly selecting edges to mark as seams when unwrapping.

Internally those are two operators who eventuelly call the same function for computation of the shortest path, which is the part we're interested in. The operators are defined in editmesh_path.c and look like this:

Select shortest path:

void MESH_OT_shortest_path_select(wmOperatorType *ot)
{
	/* identifiers */
	ot->name = "Select Shortest Path";
	ot->idname = "MESH_OT_shortest_path_select";
	ot->description = "Selected vertex path between two vertices";

	/* api callbacks */
	ot->exec = edbm_shortest_path_select_exec;
	ot->poll = ED_operator_editmesh;

	/* flags */
	ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;

	/* properties */
	path_select_properties(ot);
}

Pick shortest path:

void MESH_OT_shortest_path_pick(wmOperatorType *ot)
{
	PropertyRNA *prop;

	/* identifiers */
	ot->name = "Pick Shortest Path";
	ot->idname = "MESH_OT_shortest_path_pick";
	ot->description = "Select shortest path between two selections";

	/* api callbacks */
	ot->invoke = edbm_shortest_path_pick_invoke;
	ot->exec = edbm_shortest_path_pick_exec;
	ot->poll = ED_operator_editmesh_region_view3d;

	/* flags */
	ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;

	/* properties */
	path_select_properties(ot);

	/* use for redo */
	prop = RNA_def_int(ot->srna, "index", -1, -1, INT_MAX, "", "", 0, INT_MAX);
	RNA_def_property_flag(prop, PROP_HIDDEN | PROP_SKIP_SAVE);
}

Both of these call their respective *_invoke/ *_exec() function. These functions (edbm_shortest_path_select_exec & edbm_shortest_path_pick_exec) are mostly responsible for validating the current selection (eg. 2 similar elements to find the shortest path between) and fill the PathSelectParams struct, which mostly contains members for the operators toolsettings:

struct PathSelectParams {
	bool track_active;  /* ensure the active element is the last selected item (handy for picking) */
	bool use_topology_distance;
	bool use_face_step;
	bool use_fill;
	char edge_mode;
	struct CheckerIntervalParams interval_params;
};

After all that's done they both internally call edbm_shortest_path_pick_ex(...) which is also defined in editmesh_path.c and is the main operator for vert/edge/face tag.

static bool edbm_shortest_path_pick_ex(
        Scene *scene, const struct PathSelectParams *op_params,
        BMElem *ele_src, BMElem *ele_dst)

Parameters for this function are the Scene, aforementioned PathSelectParams, and the source/destination element, which are of type BMElem*, which is an element BMFace, BMEdge and BMVert and even BMLoop can be cast into. This function only checks the type of source/destination elements (Vert, edge or face?) and calls one of the corresponding path computation functions:

• mouse_mesh_shortest_path_vert()
• mouse_mesh_shortest_path_edge()
• mouse_mesh_shortest_path_face()

The src/dst BMElems are cast back into either BMVert/BMEdge/BMFace as parameters for these functions.

mouse_mesh_shortest_path_vert()

Shortest path computation between two vertices. The first thing after getting the current BMesh from the *scene parameter is creating an empty LinkNode* struct named "path":

LinkNode *path = NULL;

Then, depending if the "use_fill" member of the PathSelectParams is set or not, this path is eiter assigned the result of "BM_mesh_calc_path_region_vert()" or "BM_mesh_calc_path_vert()", which seem to do the main path calculation! I'll only examine the latter here, since region selection is not planned for the UV operator. It is declared in the file bmesh_path.h (the region one is defined in bmesh_path_region.h) and both of these files contain the declarations for the *_vert() as well as the _edge() and _face() variants:

mouse_mesh_shortest_path_vert() in editmesh_path.c:

path = BM_mesh_calc_path_vert(
			        bm, v_act, v_dst,
			        &(const struct BMCalcPathParams) {
			            .use_topology_distance = op_params->use_topology_distance,
			            .use_step_face = op_params->use_face_step,
			        },
			        verttag_filter_cb, &user_data);

The verttag_filter_cb parameter just checks if an element is hidden:

static bool verttag_filter_cb(BMVert *v, void *UNUSED(user_data_v))
{
	return !BM_elem_flag_test(v, BM_ELEM_HIDDEN);
}

bmesh_path.h:

struct LinkNode *BM_mesh_calc_path_vert(
        BMesh *bm, BMVert *v_src, BMVert *v_dst, const struct BMCalcPathParams *params,
        bool (*filter_fn)(BMVert *, void *), void *user_data)
ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3, 5);

The actual implementation can be found in bmesh_path.c. It calculates the shortest path between the two BMVerts v_src and v_dst. It starts with a couple declarations for often used structs like BMIter and LinkNode *path = NULL, among others.

Then it iterates over all vertices of the mesh and makes sure BM_ELEM_TAG is set for hidden vertices, because this tag is used to store visited vertices during the algorithm and makes sure we don't visit hidden ones.

BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
		BM_elem_flag_set(v, BM_ELEM_TAG, !filter_fn(v, user_data));
		BM_elem_index_set(v, i); /* set_inline */
	}
	bm->elem_index_dirty &= ~BM_VERT;

After that some memory allocations are done and the cost array is filled with the value 1e20f (high value since we're searching for lowest cost). 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.

The algorithm used is a regular dijkstra shortest path algorithm, 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 (!BLI_heap_is_empty(heap)) {
	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, params);
	}
}

It creates a heap and fills it with v_src as first element, then the cost of v_src is set to 0.0. Then it enters the main while loop which runs as long as the heap isn't empty or the current BMVert v isn't v_dst. First it pops the last element from the heap and assigns it to v. Then it checks if the BM_ELEM_TAG tag is set (which means the elements was already visited by the algorithm) and if not, it sets the BM_ELEM_TAG flag and calls verttag_add_adjacent(heap, v, verts_prev, cost, params) to add the adjacent vertices to the heap. Then the loop starts again.

Now verttag_add_adjacent() also deserves some closer look at. This function finds the adjacent elements to the BMVert v_a, adds them to the heap if they're not tagget with BM_ELEM_TAG and their computed cost is lower than the cost currently saved in cost[]. Computation of cost depends on the use_topology_distance parameter, if it's not set the cost per edge is simply 1.0 else the cost corresponds to the edge length. Note the curly bracktes around this code block, which are used to limit variables scope and prevent shadowing later on!

const int v_a_index = BM_elem_index_get(v_a);

{
	BMIter eiter;
	BMEdge *e;
	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! */
			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;

			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);
			}
		}
	}
}

After the shortest path is found and assigned to the path variable in mouse_mesh_shortest_path_vert() in editmesh_path.c, all the elements of the path are tested for BM_ELEM_SELECT and tagged using verttag_set_cb() if one or more of them aren't yet. After that EDBM_selectmode_flush() and EDBM_update_generic() are called. Lastly the *_exec() functions return OPERATOR_FINISHED.