Merge branch 'blender2.7' into master.
[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 *UNUSED(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         bool is_path_ordered = false;
331
332         edgetag_ensure_cd_flag(obedit->data, op_params->edge_mode);
333
334         if (e_act && (e_act != e_dst)) {
335                 if (op_params->use_fill) {
336                         path = BM_mesh_calc_path_region_edge(
337                                 bm, (BMElem *)e_act, (BMElem *)e_dst,
338                                 edgetag_filter_cb, &user_data);
339                 }
340                 else {
341                         is_path_ordered = true;
342                         path = BM_mesh_calc_path_edge(
343                                 bm, e_act, e_dst,
344                                 &(const struct BMCalcPathParams) {
345                                     .use_topology_distance = op_params->use_topology_distance,
346                                     .use_step_face = op_params->use_face_step,
347                                 },
348                                 edgetag_filter_cb, &user_data);
349                 }
350
351                 if (path) {
352                         if (op_params->track_active) {
353                                 BM_select_history_remove(bm, e_act);
354                         }
355                 }
356         }
357
358         BMEdge *e_dst_last = e_dst;
359
360         if (path) {
361                 /* toggle the flag */
362                 bool all_set = true;
363                 LinkNode *node;
364
365                 node = path;
366                 do {
367                         if (!edgetag_test_cb((BMEdge *)node->link, &user_data)) {
368                                 all_set = false;
369                                 break;
370                         }
371                 } while ((node = node->next));
372
373                 /* We need to start as if just *after* a 'skip' block... */
374                 int depth = op_params->interval_params.skip;
375                 node = path;
376                 do {
377                         if ((is_path_ordered == false) ||
378                             WM_operator_properties_checker_interval_test(&op_params->interval_params, depth))
379                         {
380                                 edgetag_set_cb((BMEdge *)node->link, !all_set, &user_data);
381                                 if (is_path_ordered) {
382                                         e_dst_last = node->link;
383                                 }
384                         }
385                 } while ((void)depth++, (node = node->next));
386
387                 BLI_linklist_free(path, NULL);
388         }
389         else {
390                 const bool is_act = !edgetag_test_cb(e_dst, &user_data);
391                 edgetag_ensure_cd_flag(obedit->data, op_params->edge_mode);
392                 edgetag_set_cb(e_dst, is_act, &user_data); /* switch the edge option */
393         }
394
395         if (op_params->edge_mode != EDGE_MODE_SELECT) {
396                 if (op_params->track_active) {
397                         /* simple rules - last edge is _always_ active and selected */
398                         if (e_act)
399                                 BM_edge_select_set(bm, e_act, false);
400                         BM_edge_select_set(bm, e_dst_last, true);
401                         BM_select_history_store(bm, e_dst_last);
402                 }
403         }
404
405         EDBM_selectmode_flush(em);
406
407         if (op_params->track_active) {
408                 /* even if this is selected it may not be in the selection list */
409                 if (op_params->edge_mode == EDGE_MODE_SELECT) {
410                         if (edgetag_test_cb(e_dst_last, &user_data) == 0)
411                                 BM_select_history_remove(bm, e_dst_last);
412                         else
413                                 BM_select_history_store(bm, e_dst_last);
414                 }
415         }
416
417         EDBM_update_generic(em, false, false);
418 }
419
420 /** \} */
421
422 /* -------------------------------------------------------------------- */
423 /** \name Face Path
424  * \{ */
425
426 /* callbacks */
427 static bool facetag_filter_cb(BMFace *f, void *UNUSED(user_data_v))
428 {
429         return !BM_elem_flag_test(f, BM_ELEM_HIDDEN);
430 }
431 //static bool facetag_test_cb(Scene *UNUSED(scene), BMesh *UNUSED(bm), BMFace *f)
432 static bool facetag_test_cb(BMFace *f, void *UNUSED(user_data_v))
433 {
434         return BM_elem_flag_test_bool(f, BM_ELEM_SELECT);
435 }
436 //static void facetag_set_cb(BMesh *bm, Scene *UNUSED(scene), BMFace *f, const bool val)
437 static void facetag_set_cb(BMFace *f, bool val, void *user_data_v)
438 {
439         struct UserData *user_data = user_data_v;
440         BM_face_select_set(user_data->bm, f, val);
441 }
442
443 static void mouse_mesh_shortest_path_face(
444         Scene *UNUSED(scene), Object *obedit, const struct PathSelectParams *op_params,
445         BMFace *f_act, BMFace *f_dst)
446 {
447         BMEditMesh *em = BKE_editmesh_from_object(obedit);
448         BMesh *bm = em->bm;
449
450         struct UserData user_data = {bm, obedit->data, op_params};
451         LinkNode *path = NULL;
452         bool is_path_ordered = false;
453
454         if (f_act) {
455                 if (op_params->use_fill) {
456                         path = BM_mesh_calc_path_region_face(
457                                 bm, (BMElem *)f_act, (BMElem *)f_dst,
458                                 facetag_filter_cb, &user_data);
459                 }
460                 else {
461                         is_path_ordered = true;
462                         path = BM_mesh_calc_path_face(
463                                 bm, f_act, f_dst,
464                                 &(const struct BMCalcPathParams) {
465                                     .use_topology_distance = op_params->use_topology_distance,
466                                     .use_step_face = op_params->use_face_step,
467                                 },
468                                 facetag_filter_cb, &user_data);
469                 }
470
471                 if (f_act != f_dst) {
472                         if (path) {
473                                 if (op_params->track_active) {
474                                         BM_select_history_remove(bm, f_act);
475                                 }
476                         }
477                 }
478         }
479
480         BMFace *f_dst_last = f_dst;
481
482         if (path) {
483                 /* toggle the flag */
484                 bool all_set = true;
485                 LinkNode *node;
486
487                 node = path;
488                 do {
489                         if (!facetag_test_cb((BMFace *)node->link, &user_data)) {
490                                 all_set = false;
491                                 break;
492                         }
493                 } while ((node = node->next));
494
495                 /* We need to start as if just *after* a 'skip' block... */
496                 int depth = op_params->interval_params.skip;
497                 node = path;
498                 do {
499                         if ((is_path_ordered == false) ||
500                             WM_operator_properties_checker_interval_test(&op_params->interval_params, depth))
501                         {
502                                 facetag_set_cb((BMFace *)node->link, !all_set, &user_data);
503                                 if (is_path_ordered) {
504                                         f_dst_last = node->link;
505                                 }
506                         }
507                 } while ((void)depth++, (node = node->next));
508
509                 BLI_linklist_free(path, NULL);
510         }
511         else {
512                 const bool is_act = !facetag_test_cb(f_dst, &user_data);
513                 facetag_set_cb(f_dst, is_act, &user_data); /* switch the face option */
514         }
515
516         EDBM_selectmode_flush(em);
517
518         if (op_params->track_active) {
519                 /* even if this is selected it may not be in the selection list */
520                 if (facetag_test_cb(f_dst_last, &user_data) == 0) {
521                         BM_select_history_remove(bm, f_dst_last);
522                 }
523                 else {
524                         BM_select_history_store(bm, f_dst_last);
525                 }
526                 BM_mesh_active_face_set(bm, f_dst_last);
527         }
528
529         EDBM_update_generic(em, false, false);
530 }
531
532 /** \} */
533
534 /* -------------------------------------------------------------------- */
535 /** \name Main Operator for vert/edge/face tag
536  * \{ */
537
538 static bool edbm_shortest_path_pick_ex(
539         Scene *scene, Object *obedit, const struct PathSelectParams *op_params,
540         BMElem *ele_src, BMElem *ele_dst)
541 {
542         bool ok = false;
543
544         if (ELEM(NULL, ele_src, ele_dst) || (ele_src->head.htype != ele_dst->head.htype)) {
545                 /* pass */
546         }
547         else if (ele_src->head.htype == BM_VERT) {
548                 mouse_mesh_shortest_path_vert(scene, obedit, op_params, (BMVert *)ele_src, (BMVert *)ele_dst);
549                 ok = true;
550         }
551         else if (ele_src->head.htype == BM_EDGE) {
552                 mouse_mesh_shortest_path_edge(scene, obedit, op_params, (BMEdge *)ele_src, (BMEdge *)ele_dst);
553                 ok = true;
554         }
555         else if (ele_src->head.htype == BM_FACE) {
556                 mouse_mesh_shortest_path_face(scene, obedit, op_params, (BMFace *)ele_src, (BMFace *)ele_dst);
557                 ok = true;
558         }
559
560         if (ok) {
561                 DEG_id_tag_update(obedit->data, ID_RECALC_SELECT);
562                 WM_main_add_notifier(NC_GEOM | ND_SELECT, obedit->data);
563         }
564
565         return ok;
566 }
567
568 static int edbm_shortest_path_pick_exec(bContext *C, wmOperator *op);
569
570 static BMElem *edbm_elem_find_nearest(ViewContext *vc, const char htype)
571 {
572         BMEditMesh *em = vc->em;
573         float dist = ED_view3d_select_dist_px();
574
575         if ((em->selectmode & SCE_SELECT_VERTEX) && (htype == BM_VERT)) {
576                 return (BMElem *)EDBM_vert_find_nearest(vc, &dist);
577         }
578         else if ((em->selectmode & SCE_SELECT_EDGE) && (htype == BM_EDGE)) {
579                 return (BMElem *)EDBM_edge_find_nearest(vc, &dist);
580         }
581         else if ((em->selectmode & SCE_SELECT_FACE) && (htype == BM_FACE)) {
582                 return (BMElem *)EDBM_face_find_nearest(vc, &dist);
583         }
584
585         return NULL;
586 }
587
588 static BMElem *edbm_elem_active_elem_or_face_get(BMesh *bm)
589 {
590         BMElem *ele = BM_mesh_active_elem_get(bm);
591
592         if ((ele == NULL) && bm->act_face && BM_elem_flag_test(bm->act_face, BM_ELEM_SELECT)) {
593                 ele = (BMElem *)bm->act_face;
594         }
595
596         return ele;
597 }
598
599 static int edbm_shortest_path_pick_invoke(bContext *C, wmOperator *op, const wmEvent *event)
600 {
601         if (RNA_struct_property_is_set(op->ptr, "index")) {
602                 return edbm_shortest_path_pick_exec(C, op);
603         }
604
605         Base *basact = NULL;
606         BMVert *eve = NULL;
607         BMEdge *eed = NULL;
608         BMFace *efa = NULL;
609
610         ViewContext vc;
611         BMEditMesh *em;
612         bool track_active = true;
613
614         em_setup_viewcontext(C, &vc);
615         copy_v2_v2_int(vc.mval, event->mval);
616         em = vc.em;
617
618         view3d_operator_needs_opengl(C);
619
620         {
621                 int base_index = -1;
622                 uint bases_len = 0;
623                 Base **bases = BKE_view_layer_array_from_bases_in_edit_mode(vc.view_layer, vc.v3d, &bases_len);
624                 if (EDBM_unified_findnearest(&vc, bases, bases_len, &base_index, &eve, &eed, &efa)) {
625                         basact = bases[base_index];
626                         ED_view3d_viewcontext_init_object(&vc, basact->object);
627                         em = vc.em;
628                 }
629                 MEM_freeN(bases);
630         }
631
632         /* If nothing is selected, let's select the picked vertex/edge/face. */
633         if ((vc.em->bm->totvertsel == 0) && (eve || eed || efa)) {
634                 /* TODO (dfelinto) right now we try to find the closest element twice.
635                  * The ideal is to refactor EDBM_select_pick so it doesn't
636                  * have to pick the nearest vert/edge/face again.
637                  */
638                 EDBM_select_pick(C, event->mval, true, false, false);
639                 return OPERATOR_FINISHED;
640         }
641
642         BMElem *ele_src, *ele_dst;
643         if (!(ele_src = edbm_elem_active_elem_or_face_get(em->bm)) ||
644             !(ele_dst = edbm_elem_find_nearest(&vc, ele_src->head.htype)))
645         {
646                 /* special case, toggle edge tags even when we don't have a path */
647                 if (((em->selectmode & SCE_SELECT_EDGE) &&
648                      (vc.scene->toolsettings->edge_mode != EDGE_MODE_SELECT)) &&
649                     /* check if we only have a destination edge */
650                     ((ele_src == NULL) &&
651                      (ele_dst = edbm_elem_find_nearest(&vc, BM_EDGE))))
652                 {
653                         ele_src = ele_dst;
654                         track_active = false;
655                 }
656                 else {
657                         return OPERATOR_PASS_THROUGH;
658                 }
659         }
660
661         struct PathSelectParams op_params;
662
663         path_select_params_from_op(op, &op_params);
664         op_params.track_active = track_active;
665         op_params.edge_mode = vc.scene->toolsettings->edge_mode;
666
667         if (!edbm_shortest_path_pick_ex(vc.scene, vc.obedit, &op_params, ele_src, ele_dst)) {
668                 return OPERATOR_PASS_THROUGH;
669         }
670
671         if (vc.view_layer->basact != basact) {
672                 ED_object_base_activate(C, basact);
673         }
674
675         /* to support redo */
676         BM_mesh_elem_index_ensure(em->bm, ele_dst->head.htype);
677         int index = EDBM_elem_to_index_any(em, ele_dst);
678
679         RNA_int_set(op->ptr, "index", index);
680
681         return OPERATOR_FINISHED;
682 }
683
684 static int edbm_shortest_path_pick_exec(bContext *C, wmOperator *op)
685 {
686         Scene *scene = CTX_data_scene(C);
687         Object *obedit = CTX_data_edit_object(C);
688         BMEditMesh *em = BKE_editmesh_from_object(obedit);
689         BMesh *bm = em->bm;
690
691         const int index = RNA_int_get(op->ptr, "index");
692         if (index < 0 || index >= (bm->totvert + bm->totedge + bm->totface)) {
693                 return OPERATOR_CANCELLED;
694         }
695
696         BMElem *ele_src, *ele_dst;
697         if (!(ele_src = edbm_elem_active_elem_or_face_get(em->bm)) ||
698             !(ele_dst = EDBM_elem_from_index_any(em, index)))
699         {
700                 return OPERATOR_CANCELLED;
701         }
702
703         struct PathSelectParams op_params;
704         path_select_params_from_op(op, &op_params);
705         op_params.track_active = true;
706         op_params.edge_mode = scene->toolsettings->edge_mode;
707
708         if (!edbm_shortest_path_pick_ex(scene, obedit, &op_params, ele_src, ele_dst)) {
709                 return OPERATOR_CANCELLED;
710         }
711
712         return OPERATOR_FINISHED;
713 }
714
715 void MESH_OT_shortest_path_pick(wmOperatorType *ot)
716 {
717         PropertyRNA *prop;
718
719         /* identifiers */
720         ot->name = "Pick Shortest Path";
721         ot->idname = "MESH_OT_shortest_path_pick";
722         ot->description = "Select shortest path between two selections";
723
724         /* api callbacks */
725         ot->invoke = edbm_shortest_path_pick_invoke;
726         ot->exec = edbm_shortest_path_pick_exec;
727         ot->poll = ED_operator_editmesh_region_view3d;
728
729         /* flags */
730         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
731
732         /* properties */
733         path_select_properties(ot);
734
735         /* use for redo */
736         prop = RNA_def_int(ot->srna, "index", -1, -1, INT_MAX, "", "", 0, INT_MAX);
737         RNA_def_property_flag(prop, PROP_HIDDEN | PROP_SKIP_SAVE);
738 }
739
740 /** \} */
741
742 /* -------------------------------------------------------------------- */
743 /** \name Select Path Between Existing Selection
744  * \{ */
745
746 static int edbm_shortest_path_select_exec(bContext *C, wmOperator *op)
747 {
748         Scene *scene = CTX_data_scene(C);
749         bool found_valid_elements = false;
750
751         ViewLayer *view_layer = CTX_data_view_layer(C);
752         uint objects_len = 0;
753         Object **objects = BKE_view_layer_array_from_objects_in_edit_mode_unique_data(view_layer, CTX_wm_view3d(C), &objects_len);
754         for (uint ob_index = 0; ob_index < objects_len; ob_index++) {
755                 Object *obedit = objects[ob_index];
756                 BMEditMesh *em = BKE_editmesh_from_object(obedit);
757                 BMesh *bm = em->bm;
758                 BMIter iter;
759                 BMEditSelection *ese_src, *ese_dst;
760                 BMElem *ele_src = NULL, *ele_dst = NULL, *ele;
761
762                 if ((em->bm->totvertsel == 0) &&
763                     (em->bm->totedgesel == 0) &&
764                     (em->bm->totfacesel == 0))
765                 {
766                         continue;
767                 }
768
769                 /* first try to find vertices in edit selection */
770                 ese_src = bm->selected.last;
771                 if (ese_src && (ese_dst = ese_src->prev) && (ese_src->htype  == ese_dst->htype)) {
772                         ele_src = ese_src->ele;
773                         ele_dst = ese_dst->ele;
774                 }
775                 else {
776                         /* if selection history isn't available, find two selected elements */
777                         ele_src = ele_dst = NULL;
778                         if ((em->selectmode & SCE_SELECT_VERTEX) && (bm->totvertsel >= 2)) {
779                                 BM_ITER_MESH (ele, &iter, bm, BM_VERTS_OF_MESH) {
780                                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
781                                                 if      (ele_src == NULL) ele_src = ele;
782                                                 else if (ele_dst == NULL) ele_dst = ele;
783                                                 else                      break;
784                                         }
785                                 }
786                         }
787
788                         if ((ele_dst == NULL) && (em->selectmode & SCE_SELECT_EDGE) && (bm->totedgesel >= 2)) {
789                                 ele_src = NULL;
790                                 BM_ITER_MESH (ele, &iter, bm, BM_EDGES_OF_MESH) {
791                                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
792                                                 if      (ele_src == NULL) ele_src = ele;
793                                                 else if (ele_dst == NULL) ele_dst = ele;
794                                                 else                      break;
795                                         }
796                                 }
797                         }
798
799                         if ((ele_dst == NULL) && (em->selectmode & SCE_SELECT_FACE) && (bm->totfacesel >= 2)) {
800                                 ele_src = NULL;
801                                 BM_ITER_MESH (ele, &iter, bm, BM_FACES_OF_MESH) {
802                                         if (BM_elem_flag_test(ele, BM_ELEM_SELECT)) {
803                                                 if      (ele_src == NULL) ele_src = ele;
804                                                 else if (ele_dst == NULL) ele_dst = ele;
805                                                 else                      break;
806                                         }
807                                 }
808                         }
809                 }
810
811                 if (ele_src && ele_dst) {
812                         struct PathSelectParams op_params;
813                         path_select_params_from_op(op, &op_params);
814
815                         edbm_shortest_path_pick_ex(scene, obedit, &op_params, ele_src, ele_dst);
816
817                         found_valid_elements = true;
818                 }
819         }
820         MEM_freeN(objects);
821
822         if (!found_valid_elements) {
823                 BKE_report(op->reports,
824                            RPT_WARNING,
825                            "Path selection requires two matching elements to be selected");
826                 return OPERATOR_CANCELLED;
827         }
828
829         return OPERATOR_FINISHED;
830 }
831
832 void MESH_OT_shortest_path_select(wmOperatorType *ot)
833 {
834         /* identifiers */
835         ot->name = "Select Shortest Path";
836         ot->idname = "MESH_OT_shortest_path_select";
837         ot->description = "Selected shortest path between two vertices/edges/faces";
838
839         /* api callbacks */
840         ot->exec = edbm_shortest_path_select_exec;
841         ot->poll = ED_operator_editmesh;
842
843         /* flags */
844         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
845
846         /* properties */
847         path_select_properties(ot);
848 }
849
850 /** \} */