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