Merge branch 'blender2.7'
[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         /** ensure the active element is the last selected item (handy for picking) */
76         bool track_active;
77         bool use_topology_distance;
78         bool use_face_step;
79         bool use_fill;
80         char edge_mode;
81         struct CheckerIntervalParams interval_params;
82 };
83
84 static void path_select_properties(wmOperatorType *ot)
85 {
86         RNA_def_boolean(
87                 ot->srna, "use_face_step", false, "Face Stepping",
88                 "Traverse connected faces (includes diagonals and edge-rings)");
89         RNA_def_boolean(
90                 ot->srna, "use_topology_distance", false, "Topology Distance",
91                 "Find the minimum number of steps, ignoring spatial distance");
92         RNA_def_boolean(
93                 ot->srna, "use_fill", false, "Fill Region",
94                 "Select all paths between the source/destination elements");
95         WM_operator_properties_checker_interval(ot, true);
96 }
97
98 static void path_select_params_from_op(wmOperator *op, struct PathSelectParams *op_params)
99 {
100         op_params->edge_mode = EDGE_MODE_SELECT;
101         op_params->track_active = false;
102         op_params->use_face_step = RNA_boolean_get(op->ptr, "use_face_step");
103         op_params->use_fill = RNA_boolean_get(op->ptr, "use_fill");
104         op_params->use_topology_distance = RNA_boolean_get(op->ptr, "use_topology_distance");
105         WM_operator_properties_checker_interval_from_op(op, &op_params->interval_params);
106 }
107
108 struct UserData {
109         BMesh *bm;
110         Mesh  *me;
111         const struct PathSelectParams *op_params;
112 };
113
114 /** \} */
115
116 /* -------------------------------------------------------------------- */
117 /** \name Vert Path
118  * \{ */
119
120 /* callbacks */
121 static bool verttag_filter_cb(BMVert *v, void *UNUSED(user_data_v))
122 {
123         return !BM_elem_flag_test(v, BM_ELEM_HIDDEN);
124 }
125 static bool verttag_test_cb(BMVert *v, void *UNUSED(user_data_v))
126 {
127         return BM_elem_flag_test_bool(v, BM_ELEM_SELECT);
128 }
129 static void verttag_set_cb(BMVert *v, bool val, void *user_data_v)
130 {
131         struct UserData *user_data = user_data_v;
132         BM_vert_select_set(user_data->bm, v, val);
133 }
134
135 static void mouse_mesh_shortest_path_vert(
136         Scene *UNUSED(scene), Object *obedit, const struct PathSelectParams *op_params,
137         BMVert *v_act, BMVert *v_dst)
138 {
139         BMEditMesh *em = BKE_editmesh_from_object(obedit);
140         BMesh *bm = em->bm;
141
142         struct UserData user_data = {bm, obedit->data, op_params};
143         LinkNode *path = NULL;
144         bool is_path_ordered = false;
145
146         if (v_act && (v_act != v_dst)) {
147                 if (op_params->use_fill) {
148                         path = BM_mesh_calc_path_region_vert(
149                                 bm, (BMElem *)v_act, (BMElem *)v_dst,
150                                 verttag_filter_cb, &user_data);
151                 }
152                 else {
153                         is_path_ordered = true;
154                         path = BM_mesh_calc_path_vert(
155                                 bm, v_act, v_dst,
156                                 &(const struct BMCalcPathParams) {
157                                     .use_topology_distance = op_params->use_topology_distance,
158                                     .use_step_face = op_params->use_face_step,
159                                 },
160                                 verttag_filter_cb, &user_data);
161                 }
162
163                 if (path) {
164                         if (op_params->track_active) {
165                                 BM_select_history_remove(bm, v_act);
166                         }
167                 }
168         }
169
170         BMVert *v_dst_last = v_dst;
171
172         if (path) {
173                 /* toggle the flag */
174                 bool all_set = true;
175                 LinkNode *node;
176
177                 node = path;
178                 do {
179                         if (!verttag_test_cb((BMVert *)node->link, &user_data)) {
180                                 all_set = false;
181                                 break;
182                         }
183                 } while ((node = node->next));
184
185                 /* We need to start as if just *after* a 'skip' block... */
186                 int depth = op_params->interval_params.skip;
187                 node = path;
188                 do {
189                         if ((is_path_ordered == false) ||
190                             WM_operator_properties_checker_interval_test(&op_params->interval_params, depth))
191                         {
192                                 verttag_set_cb((BMVert *)node->link, !all_set, &user_data);
193                                 if (is_path_ordered) {
194                                         v_dst_last = node->link;
195                                 }
196                         }
197                 } while ((void)depth++, (node = node->next));
198
199                 BLI_linklist_free(path, NULL);
200         }
201         else {
202                 const bool is_act = !verttag_test_cb(v_dst, &user_data);
203                 verttag_set_cb(v_dst, is_act, &user_data); /* switch the face option */
204         }
205
206         EDBM_selectmode_flush(em);
207
208         if (op_params->track_active) {
209                 /* even if this is selected it may not be in the selection list */
210                 if (BM_elem_flag_test(v_dst_last, BM_ELEM_SELECT) == 0) {
211                         BM_select_history_remove(bm, v_dst_last);
212                 }
213                 else {
214                         BM_select_history_store(bm, v_dst_last);
215                 }
216         }
217
218         EDBM_update_generic(em, false, false);
219 }
220
221 /** \} */
222
223 /* -------------------------------------------------------------------- */
224 /** \name Edge Path
225  * \{ */
226
227 /* callbacks */
228 static bool edgetag_filter_cb(BMEdge *e, void *UNUSED(user_data_v))
229 {
230         return !BM_elem_flag_test(e, BM_ELEM_HIDDEN);
231 }
232 static bool edgetag_test_cb(BMEdge *e, void *user_data_v)
233 {
234         struct UserData *user_data = user_data_v;
235         const char edge_mode = user_data->op_params->edge_mode;
236         BMesh *bm = user_data->bm;
237
238         switch (edge_mode) {
239                 case EDGE_MODE_SELECT:
240                         return BM_elem_flag_test(e, BM_ELEM_SELECT) ? true : false;
241                 case EDGE_MODE_TAG_SEAM:
242                         return BM_elem_flag_test(e, BM_ELEM_SEAM) ? true : false;
243                 case EDGE_MODE_TAG_SHARP:
244                         return BM_elem_flag_test(e, BM_ELEM_SMOOTH) ? false : true;
245                 case EDGE_MODE_TAG_CREASE:
246                         return BM_elem_float_data_get(&bm->edata, e, CD_CREASE) ? true : false;
247                 case EDGE_MODE_TAG_BEVEL:
248                         return BM_elem_float_data_get(&bm->edata, e, CD_BWEIGHT) ? true : false;
249 #ifdef WITH_FREESTYLE
250                 case EDGE_MODE_TAG_FREESTYLE:
251                 {
252                         FreestyleEdge *fed = CustomData_bmesh_get(&bm->edata, e->head.data, CD_FREESTYLE_EDGE);
253                         return (!fed) ? false : (fed->flag & FREESTYLE_EDGE_MARK) ? true : false;
254                 }
255 #endif
256         }
257         return 0;
258 }
259 static void edgetag_set_cb(BMEdge *e, bool val, void *user_data_v)
260 {
261         struct UserData *user_data = user_data_v;
262         const char edge_mode = user_data->op_params->edge_mode;
263         BMesh *bm = user_data->bm;
264
265         switch (edge_mode) {
266                 case EDGE_MODE_SELECT:
267                         BM_edge_select_set(bm, e, val);
268                         break;
269                 case EDGE_MODE_TAG_SEAM:
270                         BM_elem_flag_set(e, BM_ELEM_SEAM, val);
271                         break;
272                 case EDGE_MODE_TAG_SHARP:
273                         BM_elem_flag_set(e, BM_ELEM_SMOOTH, !val);
274                         break;
275                 case EDGE_MODE_TAG_CREASE:
276                         BM_elem_float_data_set(&bm->edata, e, CD_CREASE, (val) ? 1.0f : 0.0f);
277                         break;
278                 case EDGE_MODE_TAG_BEVEL:
279                         BM_elem_float_data_set(&bm->edata, e, CD_BWEIGHT, (val) ? 1.0f : 0.0f);
280                         break;
281 #ifdef WITH_FREESTYLE
282                 case EDGE_MODE_TAG_FREESTYLE:
283                 {
284                         FreestyleEdge *fed;
285                         fed = CustomData_bmesh_get(&bm->edata, e->head.data, CD_FREESTYLE_EDGE);
286                         if (!val)
287                                 fed->flag &= ~FREESTYLE_EDGE_MARK;
288                         else
289                                 fed->flag |= FREESTYLE_EDGE_MARK;
290                         break;
291                 }
292 #endif
293         }
294 }
295
296 static void edgetag_ensure_cd_flag(Mesh *me, const char edge_mode)
297 {
298         BMesh *bm = me->edit_btmesh->bm;
299
300         switch (edge_mode) {
301                 case EDGE_MODE_TAG_CREASE:
302                         BM_mesh_cd_flag_ensure(bm, me, ME_CDFLAG_EDGE_CREASE);
303                         break;
304                 case EDGE_MODE_TAG_BEVEL:
305                         BM_mesh_cd_flag_ensure(bm, me, ME_CDFLAG_EDGE_BWEIGHT);
306                         break;
307 #ifdef WITH_FREESTYLE
308                 case EDGE_MODE_TAG_FREESTYLE:
309                         if (!CustomData_has_layer(&bm->edata, CD_FREESTYLE_EDGE)) {
310                                 BM_data_layer_add(bm, &bm->edata, CD_FREESTYLE_EDGE);
311                         }
312                         break;
313 #endif
314                 default:
315                         break;
316         }
317 }
318
319 /* mesh shortest path select, uses prev-selected edge */
320
321 /* since you want to create paths with multiple selects, it doesn't have extend option */
322 static void mouse_mesh_shortest_path_edge(
323         Scene *UNUSED(scene), Object *obedit, const struct PathSelectParams *op_params,
324         BMEdge *e_act, BMEdge *e_dst)
325 {
326         BMEditMesh *em = BKE_editmesh_from_object(obedit);
327         BMesh *bm = em->bm;
328
329         struct UserData user_data = {bm, obedit->data, op_params};
330         LinkNode *path = NULL;
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         EDBM_update_generic(em, false, false);
419 }
420
421 /** \} */
422
423 /* -------------------------------------------------------------------- */
424 /** \name Face Path
425  * \{ */
426
427 /* callbacks */
428 static bool facetag_filter_cb(BMFace *f, void *UNUSED(user_data_v))
429 {
430         return !BM_elem_flag_test(f, BM_ELEM_HIDDEN);
431 }
432 //static bool facetag_test_cb(Scene *UNUSED(scene), BMesh *UNUSED(bm), BMFace *f)
433 static bool facetag_test_cb(BMFace *f, void *UNUSED(user_data_v))
434 {
435         return BM_elem_flag_test_bool(f, BM_ELEM_SELECT);
436 }
437 //static void facetag_set_cb(BMesh *bm, Scene *UNUSED(scene), BMFace *f, const bool val)
438 static void facetag_set_cb(BMFace *f, bool val, void *user_data_v)
439 {
440         struct UserData *user_data = user_data_v;
441         BM_face_select_set(user_data->bm, f, val);
442 }
443
444 static void mouse_mesh_shortest_path_face(
445         Scene *UNUSED(scene), Object *obedit, const struct PathSelectParams *op_params,
446         BMFace *f_act, BMFace *f_dst)
447 {
448         BMEditMesh *em = BKE_editmesh_from_object(obedit);
449         BMesh *bm = em->bm;
450
451         struct UserData user_data = {bm, obedit->data, op_params};
452         LinkNode *path = NULL;
453         bool is_path_ordered = false;
454
455         if (f_act) {
456                 if (op_params->use_fill) {
457                         path = BM_mesh_calc_path_region_face(
458                                 bm, (BMElem *)f_act, (BMElem *)f_dst,
459                                 facetag_filter_cb, &user_data);
460                 }
461                 else {
462                         is_path_ordered = true;
463                         path = BM_mesh_calc_path_face(
464                                 bm, f_act, f_dst,
465                                 &(const struct BMCalcPathParams) {
466                                     .use_topology_distance = op_params->use_topology_distance,
467                                     .use_step_face = op_params->use_face_step,
468                                 },
469                                 facetag_filter_cb, &user_data);
470                 }
471
472                 if (f_act != f_dst) {
473                         if (path) {
474                                 if (op_params->track_active) {
475                                         BM_select_history_remove(bm, f_act);
476                                 }
477                         }
478                 }
479         }
480
481         BMFace *f_dst_last = f_dst;
482
483         if (path) {
484                 /* toggle the flag */
485                 bool all_set = true;
486                 LinkNode *node;
487
488                 node = path;
489                 do {
490                         if (!facetag_test_cb((BMFace *)node->link, &user_data)) {
491                                 all_set = false;
492                                 break;
493                         }
494                 } while ((node = node->next));
495
496                 /* We need to start as if just *after* a 'skip' block... */
497                 int depth = op_params->interval_params.skip;
498                 node = path;
499                 do {
500                         if ((is_path_ordered == false) ||
501                             WM_operator_properties_checker_interval_test(&op_params->interval_params, depth))
502                         {
503                                 facetag_set_cb((BMFace *)node->link, !all_set, &user_data);
504                                 if (is_path_ordered) {
505                                         f_dst_last = node->link;
506                                 }
507                         }
508                 } while ((void)depth++, (node = node->next));
509
510                 BLI_linklist_free(path, NULL);
511         }
512         else {
513                 const bool is_act = !facetag_test_cb(f_dst, &user_data);
514                 facetag_set_cb(f_dst, is_act, &user_data); /* switch the face option */
515         }
516
517         EDBM_selectmode_flush(em);
518
519         if (op_params->track_active) {
520                 /* even if this is selected it may not be in the selection list */
521                 if (facetag_test_cb(f_dst_last, &user_data) == 0) {
522                         BM_select_history_remove(bm, f_dst_last);
523                 }
524                 else {
525                         BM_select_history_store(bm, f_dst_last);
526                 }
527                 BM_mesh_active_face_set(bm, f_dst_last);
528         }
529
530         EDBM_update_generic(em, false, false);
531 }
532
533 /** \} */
534
535 /* -------------------------------------------------------------------- */
536 /** \name Main Operator for vert/edge/face tag
537  * \{ */
538
539 static bool edbm_shortest_path_pick_ex(
540         Scene *scene, Object *obedit, const struct PathSelectParams *op_params,
541         BMElem *ele_src, BMElem *ele_dst)
542 {
543         bool ok = false;
544
545         if (ELEM(NULL, ele_src, ele_dst) || (ele_src->head.htype != ele_dst->head.htype)) {
546                 /* pass */
547         }
548         else if (ele_src->head.htype == BM_VERT) {
549                 mouse_mesh_shortest_path_vert(scene, obedit, op_params, (BMVert *)ele_src, (BMVert *)ele_dst);
550                 ok = true;
551         }
552         else if (ele_src->head.htype == BM_EDGE) {
553                 mouse_mesh_shortest_path_edge(scene, obedit, op_params, (BMEdge *)ele_src, (BMEdge *)ele_dst);
554                 ok = true;
555         }
556         else if (ele_src->head.htype == BM_FACE) {
557                 mouse_mesh_shortest_path_face(scene, obedit, op_params, (BMFace *)ele_src, (BMFace *)ele_dst);
558                 ok = true;
559         }
560
561         if (ok) {
562                 DEG_id_tag_update(obedit->data, ID_RECALC_SELECT);
563                 WM_main_add_notifier(NC_GEOM | ND_SELECT, obedit->data);
564         }
565
566         return ok;
567 }
568
569 static int edbm_shortest_path_pick_exec(bContext *C, wmOperator *op);
570
571 static BMElem *edbm_elem_find_nearest(ViewContext *vc, const char htype)
572 {
573         BMEditMesh *em = vc->em;
574         float dist = ED_view3d_select_dist_px();
575
576         if ((em->selectmode & SCE_SELECT_VERTEX) && (htype == BM_VERT)) {
577                 return (BMElem *)EDBM_vert_find_nearest(vc, &dist);
578         }
579         else if ((em->selectmode & SCE_SELECT_EDGE) && (htype == BM_EDGE)) {
580                 return (BMElem *)EDBM_edge_find_nearest(vc, &dist);
581         }
582         else if ((em->selectmode & SCE_SELECT_FACE) && (htype == BM_FACE)) {
583                 return (BMElem *)EDBM_face_find_nearest(vc, &dist);
584         }
585
586         return NULL;
587 }
588
589 static BMElem *edbm_elem_active_elem_or_face_get(BMesh *bm)
590 {
591         BMElem *ele = BM_mesh_active_elem_get(bm);
592
593         if ((ele == NULL) && bm->act_face && BM_elem_flag_test(bm->act_face, BM_ELEM_SELECT)) {
594                 ele = (BMElem *)bm->act_face;
595         }
596
597         return ele;
598 }
599
600 static int edbm_shortest_path_pick_invoke(bContext *C, wmOperator *op, const wmEvent *event)
601 {
602         if (RNA_struct_property_is_set(op->ptr, "index")) {
603                 return edbm_shortest_path_pick_exec(C, op);
604         }
605
606         Base *basact = NULL;
607         BMVert *eve = NULL;
608         BMEdge *eed = NULL;
609         BMFace *efa = NULL;
610
611         ViewContext vc;
612         BMEditMesh *em;
613         bool track_active = true;
614
615         em_setup_viewcontext(C, &vc);
616         copy_v2_v2_int(vc.mval, event->mval);
617         em = vc.em;
618
619         view3d_operator_needs_opengl(C);
620
621         {
622                 int base_index = -1;
623                 uint bases_len = 0;
624                 Base **bases = BKE_view_layer_array_from_bases_in_edit_mode(vc.view_layer, vc.v3d, &bases_len);
625                 if (EDBM_unified_findnearest(&vc, bases, bases_len, &base_index, &eve, &eed, &efa)) {
626                         basact = bases[base_index];
627                         ED_view3d_viewcontext_init_object(&vc, basact->object);
628                         em = vc.em;
629                 }
630                 MEM_freeN(bases);
631         }
632
633         /* If nothing is selected, let's select the picked vertex/edge/face. */
634         if ((vc.em->bm->totvertsel == 0) && (eve || eed || efa)) {
635                 /* TODO (dfelinto) right now we try to find the closest element twice.
636                  * The ideal is to refactor EDBM_select_pick so it doesn't
637                  * have to pick the nearest vert/edge/face again.
638                  */
639                 EDBM_select_pick(C, event->mval, true, false, false);
640                 return OPERATOR_FINISHED;
641         }
642
643         BMElem *ele_src, *ele_dst;
644         if (!(ele_src = edbm_elem_active_elem_or_face_get(em->bm)) ||
645             !(ele_dst = edbm_elem_find_nearest(&vc, ele_src->head.htype)))
646         {
647                 /* special case, toggle edge tags even when we don't have a path */
648                 if (((em->selectmode & SCE_SELECT_EDGE) &&
649                      (vc.scene->toolsettings->edge_mode != EDGE_MODE_SELECT)) &&
650                     /* check if we only have a destination edge */
651                     ((ele_src == NULL) &&
652                      (ele_dst = edbm_elem_find_nearest(&vc, BM_EDGE))))
653                 {
654                         ele_src = ele_dst;
655                         track_active = false;
656                 }
657                 else {
658                         return OPERATOR_PASS_THROUGH;
659                 }
660         }
661
662         struct PathSelectParams op_params;
663
664         path_select_params_from_op(op, &op_params);
665         op_params.track_active = track_active;
666         op_params.edge_mode = vc.scene->toolsettings->edge_mode;
667
668         if (!edbm_shortest_path_pick_ex(vc.scene, vc.obedit, &op_params, ele_src, ele_dst)) {
669                 return OPERATOR_PASS_THROUGH;
670         }
671
672         if (vc.view_layer->basact != basact) {
673                 ED_object_base_activate(C, basact);
674         }
675
676         /* to support redo */
677         BM_mesh_elem_index_ensure(em->bm, ele_dst->head.htype);
678         int index = EDBM_elem_to_index_any(em, ele_dst);
679
680         RNA_int_set(op->ptr, "index", index);
681
682         return OPERATOR_FINISHED;
683 }
684
685 static int edbm_shortest_path_pick_exec(bContext *C, wmOperator *op)
686 {
687         Scene *scene = CTX_data_scene(C);
688         Object *obedit = CTX_data_edit_object(C);
689         BMEditMesh *em = BKE_editmesh_from_object(obedit);
690         BMesh *bm = em->bm;
691
692         const int index = RNA_int_get(op->ptr, "index");
693         if (index < 0 || index >= (bm->totvert + bm->totedge + bm->totface)) {
694                 return OPERATOR_CANCELLED;
695         }
696
697         BMElem *ele_src, *ele_dst;
698         if (!(ele_src = edbm_elem_active_elem_or_face_get(em->bm)) ||
699             !(ele_dst = EDBM_elem_from_index_any(em, index)))
700         {
701                 return OPERATOR_CANCELLED;
702         }
703
704         struct PathSelectParams op_params;
705         path_select_params_from_op(op, &op_params);
706         op_params.track_active = true;
707         op_params.edge_mode = scene->toolsettings->edge_mode;
708
709         if (!edbm_shortest_path_pick_ex(scene, obedit, &op_params, ele_src, ele_dst)) {
710                 return OPERATOR_CANCELLED;
711         }
712
713         return OPERATOR_FINISHED;
714 }
715
716 void MESH_OT_shortest_path_pick(wmOperatorType *ot)
717 {
718         PropertyRNA *prop;
719
720         /* identifiers */
721         ot->name = "Pick Shortest Path";
722         ot->idname = "MESH_OT_shortest_path_pick";
723         ot->description = "Select shortest path between two selections";
724
725         /* api callbacks */
726         ot->invoke = edbm_shortest_path_pick_invoke;
727         ot->exec = edbm_shortest_path_pick_exec;
728         ot->poll = ED_operator_editmesh_region_view3d;
729
730         /* flags */
731         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
732
733         /* properties */
734         path_select_properties(ot);
735
736         /* use for redo */
737         prop = RNA_def_int(ot->srna, "index", -1, -1, INT_MAX, "", "", 0, INT_MAX);
738         RNA_def_property_flag(prop, PROP_HIDDEN | PROP_SKIP_SAVE);
739 }
740
741 /** \} */
742
743 /* -------------------------------------------------------------------- */
744 /** \name Select Path Between Existing Selection
745  * \{ */
746
747 static int edbm_shortest_path_select_exec(bContext *C, wmOperator *op)
748 {
749         Scene *scene = CTX_data_scene(C);
750         bool found_valid_elements = false;
751
752         ViewLayer *view_layer = CTX_data_view_layer(C);
753         uint objects_len = 0;
754         Object **objects = BKE_view_layer_array_from_objects_in_edit_mode_unique_data(view_layer, CTX_wm_view3d(C), &objects_len);
755         for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
756                 Object *obedit = objects[ob_index];
757                 BMEditMesh *em = BKE_editmesh_from_object(obedit);
758                 BMesh *bm = em->bm;
759                 BMIter iter;
760                 BMEditSelection *ese_src, *ese_dst;
761                 BMElem *ele_src = NULL, *ele_dst = NULL, *ele;
762
763                 if ((em->bm->totvertsel == 0) &&
764                     (em->bm->totedgesel == 0) &&
765                     (em->bm->totfacesel == 0))
766                 {
767                         continue;
768                 }
769
770                 /* first try to find vertices in edit selection */
771                 ese_src = bm->selected.last;
772                 if (ese_src && (ese_dst = ese_src->prev) && (ese_src->htype  == ese_dst->htype)) {
773                         ele_src = ese_src->ele;
774                         ele_dst = ese_dst->ele;
775                 }
776                 else {
777                         /* if selection history isn't available, find two selected elements */
778                         ele_src = ele_dst = NULL;
779                         if ((em->selectmode & SCE_SELECT_VERTEX) && (bm->totvertsel >= 2)) {
780                                 BM_ITER_MESH (ele, &iter, bm, BM_VERTS_OF_MESH) {
781                                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
782                                                 if      (ele_src == NULL) ele_src = ele;
783                                                 else if (ele_dst == NULL) ele_dst = ele;
784                                                 else                      break;
785                                         }
786                                 }
787                         }
788
789                         if ((ele_dst == NULL) && (em->selectmode & SCE_SELECT_EDGE) && (bm->totedgesel >= 2)) {
790                                 ele_src = NULL;
791                                 BM_ITER_MESH (ele, &iter, bm, BM_EDGES_OF_MESH) {
792                                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
793                                                 if      (ele_src == NULL) ele_src = ele;
794                                                 else if (ele_dst == NULL) ele_dst = ele;
795                                                 else                      break;
796                                         }
797                                 }
798                         }
799
800                         if ((ele_dst == NULL) && (em->selectmode & SCE_SELECT_FACE) && (bm->totfacesel >= 2)) {
801                                 ele_src = NULL;
802                                 BM_ITER_MESH (ele, &iter, bm, BM_FACES_OF_MESH) {
803                                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
804                                                 if      (ele_src == NULL) ele_src = ele;
805                                                 else if (ele_dst == NULL) ele_dst = ele;
806                                                 else                      break;
807                                         }
808                                 }
809                         }
810                 }
811
812                 if (ele_src && ele_dst) {
813                         struct PathSelectParams op_params;
814                         path_select_params_from_op(op, &op_params);
815
816                         edbm_shortest_path_pick_ex(scene, obedit, &op_params, ele_src, ele_dst);
817
818                         found_valid_elements = true;
819                 }
820         }
821         MEM_freeN(objects);
822
823         if (!found_valid_elements) {
824                 BKE_report(op->reports,
825                            RPT_WARNING,
826                            "Path selection requires two matching elements to be selected");
827                 return OPERATOR_CANCELLED;
828         }
829
830         return OPERATOR_FINISHED;
831 }
832
833 void MESH_OT_shortest_path_select(wmOperatorType *ot)
834 {
835         /* identifiers */
836         ot->name = "Select Shortest Path";
837         ot->idname = "MESH_OT_shortest_path_select";
838         ot->description = "Selected shortest path between two vertices/edges/faces";
839
840         /* api callbacks */
841         ot->exec = edbm_shortest_path_select_exec;
842         ot->poll = ED_operator_editmesh;
843
844         /* flags */
845         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
846
847         /* properties */
848         path_select_properties(ot);
849 }
850
851 /** \} */