doxygen: add newline after \file
[blender.git] / source / blender / editors / mesh / editmesh_path.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2004 Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup edmesh
22  */
23
24 #include "MEM_guardedalloc.h"
25
26 #include "DNA_scene_types.h"
27 #include "DNA_object_types.h"
28 #include "DNA_mesh_types.h"
29 #include "DNA_windowmanager_types.h"
30
31 #ifdef WITH_FREESTYLE
32 #  include "DNA_meshdata_types.h"
33 #endif
34
35 #include "BLI_math.h"
36 #include "BLI_linklist.h"
37
38 #include "BKE_layer.h"
39 #include "BKE_context.h"
40 #include "BKE_editmesh.h"
41 #include "BKE_report.h"
42
43 #include "ED_object.h"
44 #include "ED_mesh.h"
45 #include "ED_screen.h"
46 #include "ED_uvedit.h"
47 #include "ED_view3d.h"
48
49 #include "RNA_access.h"
50 #include "RNA_define.h"
51
52 #include "WM_api.h"
53 #include "WM_types.h"
54
55 #include "bmesh.h"
56 #include "bmesh_tools.h"
57
58 #include "DEG_depsgraph.h"
59
60 #include "mesh_intern.h"  /* own include */
61
62 /* -------------------------------------------------------------------- */
63 /** \name Path Select Struct & Properties
64  * \{ */
65
66 struct PathSelectParams {
67         /** ensure the active element is the last selected item (handy for picking) */
68         bool track_active;
69         bool use_topology_distance;
70         bool use_face_step;
71         bool use_fill;
72         char edge_mode;
73         struct CheckerIntervalParams interval_params;
74 };
75
76 static void path_select_properties(wmOperatorType *ot)
77 {
78         RNA_def_boolean(
79                 ot->srna, "use_face_step", false, "Face Stepping",
80                 "Traverse connected faces (includes diagonals and edge-rings)");
81         RNA_def_boolean(
82                 ot->srna, "use_topology_distance", false, "Topology Distance",
83                 "Find the minimum number of steps, ignoring spatial distance");
84         RNA_def_boolean(
85                 ot->srna, "use_fill", false, "Fill Region",
86                 "Select all paths between the source/destination elements");
87         WM_operator_properties_checker_interval(ot, true);
88 }
89
90 static void path_select_params_from_op(wmOperator *op, struct PathSelectParams *op_params)
91 {
92         op_params->edge_mode = EDGE_MODE_SELECT;
93         op_params->track_active = false;
94         op_params->use_face_step = RNA_boolean_get(op->ptr, "use_face_step");
95         op_params->use_fill = RNA_boolean_get(op->ptr, "use_fill");
96         op_params->use_topology_distance = RNA_boolean_get(op->ptr, "use_topology_distance");
97         WM_operator_properties_checker_interval_from_op(op, &op_params->interval_params);
98 }
99
100 struct UserData {
101         BMesh *bm;
102         Mesh  *me;
103         const struct PathSelectParams *op_params;
104 };
105
106 /** \} */
107
108 /* -------------------------------------------------------------------- */
109 /** \name Vert Path
110  * \{ */
111
112 /* callbacks */
113 static bool verttag_filter_cb(BMVert *v, void *UNUSED(user_data_v))
114 {
115         return !BM_elem_flag_test(v, BM_ELEM_HIDDEN);
116 }
117 static bool verttag_test_cb(BMVert *v, void *UNUSED(user_data_v))
118 {
119         return BM_elem_flag_test_bool(v, BM_ELEM_SELECT);
120 }
121 static void verttag_set_cb(BMVert *v, bool val, void *user_data_v)
122 {
123         struct UserData *user_data = user_data_v;
124         BM_vert_select_set(user_data->bm, v, val);
125 }
126
127 static void mouse_mesh_shortest_path_vert(
128         Scene *UNUSED(scene), Object *obedit, const struct PathSelectParams *op_params,
129         BMVert *v_act, BMVert *v_dst)
130 {
131         BMEditMesh *em = BKE_editmesh_from_object(obedit);
132         BMesh *bm = em->bm;
133
134         struct UserData user_data = {bm, obedit->data, op_params};
135         LinkNode *path = NULL;
136         bool is_path_ordered = false;
137
138         if (v_act && (v_act != v_dst)) {
139                 if (op_params->use_fill) {
140                         path = BM_mesh_calc_path_region_vert(
141                                 bm, (BMElem *)v_act, (BMElem *)v_dst,
142                                 verttag_filter_cb, &user_data);
143                 }
144                 else {
145                         is_path_ordered = true;
146                         path = BM_mesh_calc_path_vert(
147                                 bm, v_act, v_dst,
148                                 &(const struct BMCalcPathParams) {
149                                     .use_topology_distance = op_params->use_topology_distance,
150                                     .use_step_face = op_params->use_face_step,
151                                 },
152                                 verttag_filter_cb, &user_data);
153                 }
154
155                 if (path) {
156                         if (op_params->track_active) {
157                                 BM_select_history_remove(bm, v_act);
158                         }
159                 }
160         }
161
162         BMVert *v_dst_last = v_dst;
163
164         if (path) {
165                 /* toggle the flag */
166                 bool all_set = true;
167                 LinkNode *node;
168
169                 node = path;
170                 do {
171                         if (!verttag_test_cb((BMVert *)node->link, &user_data)) {
172                                 all_set = false;
173                                 break;
174                         }
175                 } while ((node = node->next));
176
177                 /* We need to start as if just *after* a 'skip' block... */
178                 int depth = op_params->interval_params.skip;
179                 node = path;
180                 do {
181                         if ((is_path_ordered == false) ||
182                             WM_operator_properties_checker_interval_test(&op_params->interval_params, depth))
183                         {
184                                 verttag_set_cb((BMVert *)node->link, !all_set, &user_data);
185                                 if (is_path_ordered) {
186                                         v_dst_last = node->link;
187                                 }
188                         }
189                 } while ((void)depth++, (node = node->next));
190
191                 BLI_linklist_free(path, NULL);
192         }
193         else {
194                 const bool is_act = !verttag_test_cb(v_dst, &user_data);
195                 verttag_set_cb(v_dst, is_act, &user_data); /* switch the face option */
196         }
197
198         EDBM_selectmode_flush(em);
199
200         if (op_params->track_active) {
201                 /* even if this is selected it may not be in the selection list */
202                 if (BM_elem_flag_test(v_dst_last, BM_ELEM_SELECT) == 0) {
203                         BM_select_history_remove(bm, v_dst_last);
204                 }
205                 else {
206                         BM_select_history_store(bm, v_dst_last);
207                 }
208         }
209
210         EDBM_update_generic(em, false, false);
211 }
212
213 /** \} */
214
215 /* -------------------------------------------------------------------- */
216 /** \name Edge Path
217  * \{ */
218
219 /* callbacks */
220 static bool edgetag_filter_cb(BMEdge *e, void *UNUSED(user_data_v))
221 {
222         return !BM_elem_flag_test(e, BM_ELEM_HIDDEN);
223 }
224 static bool edgetag_test_cb(BMEdge *e, void *user_data_v)
225 {
226         struct UserData *user_data = user_data_v;
227         const char edge_mode = user_data->op_params->edge_mode;
228         BMesh *bm = user_data->bm;
229
230         switch (edge_mode) {
231                 case EDGE_MODE_SELECT:
232                         return BM_elem_flag_test(e, BM_ELEM_SELECT) ? true : false;
233                 case EDGE_MODE_TAG_SEAM:
234                         return BM_elem_flag_test(e, BM_ELEM_SEAM) ? true : false;
235                 case EDGE_MODE_TAG_SHARP:
236                         return BM_elem_flag_test(e, BM_ELEM_SMOOTH) ? false : true;
237                 case EDGE_MODE_TAG_CREASE:
238                         return BM_elem_float_data_get(&bm->edata, e, CD_CREASE) ? true : false;
239                 case EDGE_MODE_TAG_BEVEL:
240                         return BM_elem_float_data_get(&bm->edata, e, CD_BWEIGHT) ? true : false;
241 #ifdef WITH_FREESTYLE
242                 case EDGE_MODE_TAG_FREESTYLE:
243                 {
244                         FreestyleEdge *fed = CustomData_bmesh_get(&bm->edata, e->head.data, CD_FREESTYLE_EDGE);
245                         return (!fed) ? false : (fed->flag & FREESTYLE_EDGE_MARK) ? true : false;
246                 }
247 #endif
248         }
249         return 0;
250 }
251 static void edgetag_set_cb(BMEdge *e, bool val, void *user_data_v)
252 {
253         struct UserData *user_data = user_data_v;
254         const char edge_mode = user_data->op_params->edge_mode;
255         BMesh *bm = user_data->bm;
256
257         switch (edge_mode) {
258                 case EDGE_MODE_SELECT:
259                         BM_edge_select_set(bm, e, val);
260                         break;
261                 case EDGE_MODE_TAG_SEAM:
262                         BM_elem_flag_set(e, BM_ELEM_SEAM, val);
263                         break;
264                 case EDGE_MODE_TAG_SHARP:
265                         BM_elem_flag_set(e, BM_ELEM_SMOOTH, !val);
266                         break;
267                 case EDGE_MODE_TAG_CREASE:
268                         BM_elem_float_data_set(&bm->edata, e, CD_CREASE, (val) ? 1.0f : 0.0f);
269                         break;
270                 case EDGE_MODE_TAG_BEVEL:
271                         BM_elem_float_data_set(&bm->edata, e, CD_BWEIGHT, (val) ? 1.0f : 0.0f);
272                         break;
273 #ifdef WITH_FREESTYLE
274                 case EDGE_MODE_TAG_FREESTYLE:
275                 {
276                         FreestyleEdge *fed;
277                         fed = CustomData_bmesh_get(&bm->edata, e->head.data, CD_FREESTYLE_EDGE);
278                         if (!val)
279                                 fed->flag &= ~FREESTYLE_EDGE_MARK;
280                         else
281                                 fed->flag |= FREESTYLE_EDGE_MARK;
282                         break;
283                 }
284 #endif
285         }
286 }
287
288 static void edgetag_ensure_cd_flag(Mesh *me, const char edge_mode)
289 {
290         BMesh *bm = me->edit_mesh->bm;
291
292         switch (edge_mode) {
293                 case EDGE_MODE_TAG_CREASE:
294                         BM_mesh_cd_flag_ensure(bm, me, ME_CDFLAG_EDGE_CREASE);
295                         break;
296                 case EDGE_MODE_TAG_BEVEL:
297                         BM_mesh_cd_flag_ensure(bm, me, ME_CDFLAG_EDGE_BWEIGHT);
298                         break;
299 #ifdef WITH_FREESTYLE
300                 case EDGE_MODE_TAG_FREESTYLE:
301                         if (!CustomData_has_layer(&bm->edata, CD_FREESTYLE_EDGE)) {
302                                 BM_data_layer_add(bm, &bm->edata, CD_FREESTYLE_EDGE);
303                         }
304                         break;
305 #endif
306                 default:
307                         break;
308         }
309 }
310
311 /* mesh shortest path select, uses prev-selected edge */
312
313 /* since you want to create paths with multiple selects, it doesn't have extend option */
314 static void mouse_mesh_shortest_path_edge(
315         Scene *UNUSED(scene), Object *obedit, const struct PathSelectParams *op_params,
316         BMEdge *e_act, BMEdge *e_dst)
317 {
318         BMEditMesh *em = BKE_editmesh_from_object(obedit);
319         BMesh *bm = em->bm;
320
321         struct UserData user_data = {bm, obedit->data, op_params};
322         LinkNode *path = NULL;
323         bool is_path_ordered = false;
324
325         edgetag_ensure_cd_flag(obedit->data, op_params->edge_mode);
326
327         if (e_act && (e_act != e_dst)) {
328                 if (op_params->use_fill) {
329                         path = BM_mesh_calc_path_region_edge(
330                                 bm, (BMElem *)e_act, (BMElem *)e_dst,
331                                 edgetag_filter_cb, &user_data);
332                 }
333                 else {
334                         is_path_ordered = true;
335                         path = BM_mesh_calc_path_edge(
336                                 bm, e_act, e_dst,
337                                 &(const struct BMCalcPathParams) {
338                                     .use_topology_distance = op_params->use_topology_distance,
339                                     .use_step_face = op_params->use_face_step,
340                                 },
341                                 edgetag_filter_cb, &user_data);
342                 }
343
344                 if (path) {
345                         if (op_params->track_active) {
346                                 BM_select_history_remove(bm, e_act);
347                         }
348                 }
349         }
350
351         BMEdge *e_dst_last = e_dst;
352
353         if (path) {
354                 /* toggle the flag */
355                 bool all_set = true;
356                 LinkNode *node;
357
358                 node = path;
359                 do {
360                         if (!edgetag_test_cb((BMEdge *)node->link, &user_data)) {
361                                 all_set = false;
362                                 break;
363                         }
364                 } while ((node = node->next));
365
366                 /* We need to start as if just *after* a 'skip' block... */
367                 int depth = op_params->interval_params.skip;
368                 node = path;
369                 do {
370                         if ((is_path_ordered == false) ||
371                             WM_operator_properties_checker_interval_test(&op_params->interval_params, depth))
372                         {
373                                 edgetag_set_cb((BMEdge *)node->link, !all_set, &user_data);
374                                 if (is_path_ordered) {
375                                         e_dst_last = node->link;
376                                 }
377                         }
378                 } while ((void)depth++, (node = node->next));
379
380                 BLI_linklist_free(path, NULL);
381         }
382         else {
383                 const bool is_act = !edgetag_test_cb(e_dst, &user_data);
384                 edgetag_ensure_cd_flag(obedit->data, op_params->edge_mode);
385                 edgetag_set_cb(e_dst, is_act, &user_data); /* switch the edge option */
386         }
387
388         if (op_params->edge_mode != EDGE_MODE_SELECT) {
389                 if (op_params->track_active) {
390                         /* simple rules - last edge is _always_ active and selected */
391                         if (e_act)
392                                 BM_edge_select_set(bm, e_act, false);
393                         BM_edge_select_set(bm, e_dst_last, true);
394                         BM_select_history_store(bm, e_dst_last);
395                 }
396         }
397
398         EDBM_selectmode_flush(em);
399
400         if (op_params->track_active) {
401                 /* even if this is selected it may not be in the selection list */
402                 if (op_params->edge_mode == EDGE_MODE_SELECT) {
403                         if (edgetag_test_cb(e_dst_last, &user_data) == 0)
404                                 BM_select_history_remove(bm, e_dst_last);
405                         else
406                                 BM_select_history_store(bm, e_dst_last);
407                 }
408         }
409
410         EDBM_update_generic(em, false, false);
411 }
412
413 /** \} */
414
415 /* -------------------------------------------------------------------- */
416 /** \name Face Path
417  * \{ */
418
419 /* callbacks */
420 static bool facetag_filter_cb(BMFace *f, void *UNUSED(user_data_v))
421 {
422         return !BM_elem_flag_test(f, BM_ELEM_HIDDEN);
423 }
424 //static bool facetag_test_cb(Scene *UNUSED(scene), BMesh *UNUSED(bm), BMFace *f)
425 static bool facetag_test_cb(BMFace *f, void *UNUSED(user_data_v))
426 {
427         return BM_elem_flag_test_bool(f, BM_ELEM_SELECT);
428 }
429 //static void facetag_set_cb(BMesh *bm, Scene *UNUSED(scene), BMFace *f, const bool val)
430 static void facetag_set_cb(BMFace *f, bool val, void *user_data_v)
431 {
432         struct UserData *user_data = user_data_v;
433         BM_face_select_set(user_data->bm, f, val);
434 }
435
436 static void mouse_mesh_shortest_path_face(
437         Scene *UNUSED(scene), Object *obedit, const struct PathSelectParams *op_params,
438         BMFace *f_act, BMFace *f_dst)
439 {
440         BMEditMesh *em = BKE_editmesh_from_object(obedit);
441         BMesh *bm = em->bm;
442
443         struct UserData user_data = {bm, obedit->data, op_params};
444         LinkNode *path = NULL;
445         bool is_path_ordered = false;
446
447         if (f_act) {
448                 if (op_params->use_fill) {
449                         path = BM_mesh_calc_path_region_face(
450                                 bm, (BMElem *)f_act, (BMElem *)f_dst,
451                                 facetag_filter_cb, &user_data);
452                 }
453                 else {
454                         is_path_ordered = true;
455                         path = BM_mesh_calc_path_face(
456                                 bm, f_act, f_dst,
457                                 &(const struct BMCalcPathParams) {
458                                     .use_topology_distance = op_params->use_topology_distance,
459                                     .use_step_face = op_params->use_face_step,
460                                 },
461                                 facetag_filter_cb, &user_data);
462                 }
463
464                 if (f_act != f_dst) {
465                         if (path) {
466                                 if (op_params->track_active) {
467                                         BM_select_history_remove(bm, f_act);
468                                 }
469                         }
470                 }
471         }
472
473         BMFace *f_dst_last = f_dst;
474
475         if (path) {
476                 /* toggle the flag */
477                 bool all_set = true;
478                 LinkNode *node;
479
480                 node = path;
481                 do {
482                         if (!facetag_test_cb((BMFace *)node->link, &user_data)) {
483                                 all_set = false;
484                                 break;
485                         }
486                 } while ((node = node->next));
487
488                 /* We need to start as if just *after* a 'skip' block... */
489                 int depth = op_params->interval_params.skip;
490                 node = path;
491                 do {
492                         if ((is_path_ordered == false) ||
493                             WM_operator_properties_checker_interval_test(&op_params->interval_params, depth))
494                         {
495                                 facetag_set_cb((BMFace *)node->link, !all_set, &user_data);
496                                 if (is_path_ordered) {
497                                         f_dst_last = node->link;
498                                 }
499                         }
500                 } while ((void)depth++, (node = node->next));
501
502                 BLI_linklist_free(path, NULL);
503         }
504         else {
505                 const bool is_act = !facetag_test_cb(f_dst, &user_data);
506                 facetag_set_cb(f_dst, is_act, &user_data); /* switch the face option */
507         }
508
509         EDBM_selectmode_flush(em);
510
511         if (op_params->track_active) {
512                 /* even if this is selected it may not be in the selection list */
513                 if (facetag_test_cb(f_dst_last, &user_data) == 0) {
514                         BM_select_history_remove(bm, f_dst_last);
515                 }
516                 else {
517                         BM_select_history_store(bm, f_dst_last);
518                 }
519                 BM_mesh_active_face_set(bm, f_dst_last);
520         }
521
522         EDBM_update_generic(em, false, false);
523 }
524
525 /** \} */
526
527 /* -------------------------------------------------------------------- */
528 /** \name Main Operator for vert/edge/face tag
529  * \{ */
530
531 static bool edbm_shortest_path_pick_ex(
532         Scene *scene, Object *obedit, const struct PathSelectParams *op_params,
533         BMElem *ele_src, BMElem *ele_dst)
534 {
535         bool ok = false;
536
537         if (ELEM(NULL, ele_src, ele_dst) || (ele_src->head.htype != ele_dst->head.htype)) {
538                 /* pass */
539         }
540         else if (ele_src->head.htype == BM_VERT) {
541                 mouse_mesh_shortest_path_vert(scene, obedit, op_params, (BMVert *)ele_src, (BMVert *)ele_dst);
542                 ok = true;
543         }
544         else if (ele_src->head.htype == BM_EDGE) {
545                 mouse_mesh_shortest_path_edge(scene, obedit, op_params, (BMEdge *)ele_src, (BMEdge *)ele_dst);
546                 ok = true;
547         }
548         else if (ele_src->head.htype == BM_FACE) {
549                 mouse_mesh_shortest_path_face(scene, obedit, op_params, (BMFace *)ele_src, (BMFace *)ele_dst);
550                 ok = true;
551         }
552
553         if (ok) {
554                 DEG_id_tag_update(obedit->data, ID_RECALC_SELECT);
555                 WM_main_add_notifier(NC_GEOM | ND_SELECT, obedit->data);
556         }
557
558         return ok;
559 }
560
561 static int edbm_shortest_path_pick_exec(bContext *C, wmOperator *op);
562
563 static BMElem *edbm_elem_find_nearest(ViewContext *vc, const char htype)
564 {
565         BMEditMesh *em = vc->em;
566         float dist = ED_view3d_select_dist_px();
567
568         if ((em->selectmode & SCE_SELECT_VERTEX) && (htype == BM_VERT)) {
569                 return (BMElem *)EDBM_vert_find_nearest(vc, &dist);
570         }
571         else if ((em->selectmode & SCE_SELECT_EDGE) && (htype == BM_EDGE)) {
572                 return (BMElem *)EDBM_edge_find_nearest(vc, &dist);
573         }
574         else if ((em->selectmode & SCE_SELECT_FACE) && (htype == BM_FACE)) {
575                 return (BMElem *)EDBM_face_find_nearest(vc, &dist);
576         }
577
578         return NULL;
579 }
580
581 static BMElem *edbm_elem_active_elem_or_face_get(BMesh *bm)
582 {
583         BMElem *ele = BM_mesh_active_elem_get(bm);
584
585         if ((ele == NULL) && bm->act_face && BM_elem_flag_test(bm->act_face, BM_ELEM_SELECT)) {
586                 ele = (BMElem *)bm->act_face;
587         }
588
589         return ele;
590 }
591
592 static int edbm_shortest_path_pick_invoke(bContext *C, wmOperator *op, const wmEvent *event)
593 {
594         if (RNA_struct_property_is_set(op->ptr, "index")) {
595                 return edbm_shortest_path_pick_exec(C, op);
596         }
597
598         Base *basact = NULL;
599         BMVert *eve = NULL;
600         BMEdge *eed = NULL;
601         BMFace *efa = NULL;
602
603         ViewContext vc;
604         BMEditMesh *em;
605         bool track_active = true;
606
607         em_setup_viewcontext(C, &vc);
608         copy_v2_v2_int(vc.mval, event->mval);
609         em = vc.em;
610
611         view3d_operator_needs_opengl(C);
612
613         {
614                 int base_index = -1;
615                 uint bases_len = 0;
616                 Base **bases = BKE_view_layer_array_from_bases_in_edit_mode(vc.view_layer, vc.v3d, &bases_len);
617                 if (EDBM_unified_findnearest(&vc, bases, bases_len, &base_index, &eve, &eed, &efa)) {
618                         basact = bases[base_index];
619                         ED_view3d_viewcontext_init_object(&vc, basact->object);
620                         em = vc.em;
621                 }
622                 MEM_freeN(bases);
623         }
624
625         /* If nothing is selected, let's select the picked vertex/edge/face. */
626         if ((vc.em->bm->totvertsel == 0) && (eve || eed || efa)) {
627                 /* TODO (dfelinto) right now we try to find the closest element twice.
628                  * The ideal is to refactor EDBM_select_pick so it doesn't
629                  * have to pick the nearest vert/edge/face again.
630                  */
631                 EDBM_select_pick(C, event->mval, true, false, false);
632                 return OPERATOR_FINISHED;
633         }
634
635         BMElem *ele_src, *ele_dst;
636         if (!(ele_src = edbm_elem_active_elem_or_face_get(em->bm)) ||
637             !(ele_dst = edbm_elem_find_nearest(&vc, ele_src->head.htype)))
638         {
639                 /* special case, toggle edge tags even when we don't have a path */
640                 if (((em->selectmode & SCE_SELECT_EDGE) &&
641                      (vc.scene->toolsettings->edge_mode != EDGE_MODE_SELECT)) &&
642                     /* check if we only have a destination edge */
643                     ((ele_src == NULL) &&
644                      (ele_dst = edbm_elem_find_nearest(&vc, BM_EDGE))))
645                 {
646                         ele_src = ele_dst;
647                         track_active = false;
648                 }
649                 else {
650                         return OPERATOR_PASS_THROUGH;
651                 }
652         }
653
654         struct PathSelectParams op_params;
655
656         path_select_params_from_op(op, &op_params);
657         op_params.track_active = track_active;
658         op_params.edge_mode = vc.scene->toolsettings->edge_mode;
659
660         if (!edbm_shortest_path_pick_ex(vc.scene, vc.obedit, &op_params, ele_src, ele_dst)) {
661                 return OPERATOR_PASS_THROUGH;
662         }
663
664         if (vc.view_layer->basact != basact) {
665                 ED_object_base_activate(C, basact);
666         }
667
668         /* to support redo */
669         BM_mesh_elem_index_ensure(em->bm, ele_dst->head.htype);
670         int index = EDBM_elem_to_index_any(em, ele_dst);
671
672         RNA_int_set(op->ptr, "index", index);
673
674         return OPERATOR_FINISHED;
675 }
676
677 static int edbm_shortest_path_pick_exec(bContext *C, wmOperator *op)
678 {
679         Scene *scene = CTX_data_scene(C);
680         Object *obedit = CTX_data_edit_object(C);
681         BMEditMesh *em = BKE_editmesh_from_object(obedit);
682         BMesh *bm = em->bm;
683
684         const int index = RNA_int_get(op->ptr, "index");
685         if (index < 0 || index >= (bm->totvert + bm->totedge + bm->totface)) {
686                 return OPERATOR_CANCELLED;
687         }
688
689         BMElem *ele_src, *ele_dst;
690         if (!(ele_src = edbm_elem_active_elem_or_face_get(em->bm)) ||
691             !(ele_dst = EDBM_elem_from_index_any(em, index)))
692         {
693                 return OPERATOR_CANCELLED;
694         }
695
696         struct PathSelectParams op_params;
697         path_select_params_from_op(op, &op_params);
698         op_params.track_active = true;
699         op_params.edge_mode = scene->toolsettings->edge_mode;
700
701         if (!edbm_shortest_path_pick_ex(scene, obedit, &op_params, ele_src, ele_dst)) {
702                 return OPERATOR_CANCELLED;
703         }
704
705         return OPERATOR_FINISHED;
706 }
707
708 void MESH_OT_shortest_path_pick(wmOperatorType *ot)
709 {
710         PropertyRNA *prop;
711
712         /* identifiers */
713         ot->name = "Pick Shortest Path";
714         ot->idname = "MESH_OT_shortest_path_pick";
715         ot->description = "Select shortest path between two selections";
716
717         /* api callbacks */
718         ot->invoke = edbm_shortest_path_pick_invoke;
719         ot->exec = edbm_shortest_path_pick_exec;
720         ot->poll = ED_operator_editmesh_region_view3d;
721
722         /* flags */
723         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
724
725         /* properties */
726         path_select_properties(ot);
727
728         /* use for redo */
729         prop = RNA_def_int(ot->srna, "index", -1, -1, INT_MAX, "", "", 0, INT_MAX);
730         RNA_def_property_flag(prop, PROP_HIDDEN | PROP_SKIP_SAVE);
731 }
732
733 /** \} */
734
735 /* -------------------------------------------------------------------- */
736 /** \name Select Path Between Existing Selection
737  * \{ */
738
739 static int edbm_shortest_path_select_exec(bContext *C, wmOperator *op)
740 {
741         Scene *scene = CTX_data_scene(C);
742         bool found_valid_elements = false;
743
744         ViewLayer *view_layer = CTX_data_view_layer(C);
745         uint objects_len = 0;
746         Object **objects = BKE_view_layer_array_from_objects_in_edit_mode_unique_data(view_layer, CTX_wm_view3d(C), &objects_len);
747         for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
748                 Object *obedit = objects[ob_index];
749                 BMEditMesh *em = BKE_editmesh_from_object(obedit);
750                 BMesh *bm = em->bm;
751                 BMIter iter;
752                 BMEditSelection *ese_src, *ese_dst;
753                 BMElem *ele_src = NULL, *ele_dst = NULL, *ele;
754
755                 if ((em->bm->totvertsel == 0) &&
756                     (em->bm->totedgesel == 0) &&
757                     (em->bm->totfacesel == 0))
758                 {
759                         continue;
760                 }
761
762                 /* first try to find vertices in edit selection */
763                 ese_src = bm->selected.last;
764                 if (ese_src && (ese_dst = ese_src->prev) && (ese_src->htype  == ese_dst->htype)) {
765                         ele_src = ese_src->ele;
766                         ele_dst = ese_dst->ele;
767                 }
768                 else {
769                         /* if selection history isn't available, find two selected elements */
770                         ele_src = ele_dst = NULL;
771                         if ((em->selectmode & SCE_SELECT_VERTEX) && (bm->totvertsel >= 2)) {
772                                 BM_ITER_MESH (ele, &iter, bm, BM_VERTS_OF_MESH) {
773                                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
774                                                 if      (ele_src == NULL) ele_src = ele;
775                                                 else if (ele_dst == NULL) ele_dst = ele;
776                                                 else                      break;
777                                         }
778                                 }
779                         }
780
781                         if ((ele_dst == NULL) && (em->selectmode & SCE_SELECT_EDGE) && (bm->totedgesel >= 2)) {
782                                 ele_src = NULL;
783                                 BM_ITER_MESH (ele, &iter, bm, BM_EDGES_OF_MESH) {
784                                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
785                                                 if      (ele_src == NULL) ele_src = ele;
786                                                 else if (ele_dst == NULL) ele_dst = ele;
787                                                 else                      break;
788                                         }
789                                 }
790                         }
791
792                         if ((ele_dst == NULL) && (em->selectmode & SCE_SELECT_FACE) && (bm->totfacesel >= 2)) {
793                                 ele_src = NULL;
794                                 BM_ITER_MESH (ele, &iter, bm, BM_FACES_OF_MESH) {
795                                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
796                                                 if      (ele_src == NULL) ele_src = ele;
797                                                 else if (ele_dst == NULL) ele_dst = ele;
798                                                 else                      break;
799                                         }
800                                 }
801                         }
802                 }
803
804                 if (ele_src && ele_dst) {
805                         struct PathSelectParams op_params;
806                         path_select_params_from_op(op, &op_params);
807
808                         edbm_shortest_path_pick_ex(scene, obedit, &op_params, ele_src, ele_dst);
809
810                         found_valid_elements = true;
811                 }
812         }
813         MEM_freeN(objects);
814
815         if (!found_valid_elements) {
816                 BKE_report(op->reports,
817                            RPT_WARNING,
818                            "Path selection requires two matching elements to be selected");
819                 return OPERATOR_CANCELLED;
820         }
821
822         return OPERATOR_FINISHED;
823 }
824
825 void MESH_OT_shortest_path_select(wmOperatorType *ot)
826 {
827         /* identifiers */
828         ot->name = "Select Shortest Path";
829         ot->idname = "MESH_OT_shortest_path_select";
830         ot->description = "Selected shortest path between two vertices/edges/faces";
831
832         /* api callbacks */
833         ot->exec = edbm_shortest_path_select_exec;
834         ot->poll = ED_operator_editmesh;
835
836         /* flags */
837         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
838
839         /* properties */
840         path_select_properties(ot);
841 }
842
843 /** \} */