Merge remote-tracking branch 'origin/master' into blender2.8
[blender.git] / source / blender / bmesh / operators / bmo_connect_pair.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  * Contributor(s): Campbell Barton.
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/bmesh/operators/bmo_connect_pair.c
24  *  \ingroup bmesh
25  *
26  * Connect vertex pair across multiple faces (splits faces).
27  */
28
29 #include "MEM_guardedalloc.h"
30
31 #include "BLI_math.h"
32 #include "BLI_utildefines.h"
33 #include "BLI_heap_simple.h"
34
35 #include "bmesh.h"
36
37 #include "intern/bmesh_operators_private.h" /* own include */
38
39 #include "BLI_mempool.h"
40 #include "BLI_listbase.h"
41
42 /**
43  * Method for connecting across many faces.
44  *
45  * - use the line between both verts and their normal average to construct a matrix.
46  * - using the matrix, we can find all intersecting verts/edges.
47  * - walk the connected data and find the shortest path.
48  *   - store a heap of paths which are being scanned (#PathContext.states).
49  *   - continuously search the shortest path in the heap.
50  *   - never step over the same element twice (tag elements as #ELE_TOUCHED).
51  *     this avoids going into an eternal loop if there are many possible branches (see T45582).
52  *   - when running into a branch, create a new #PathLinkState state and add to the heap.
53  *   - when the target is reached, finish - since none of the other paths can be shorter then the one just found.
54  * - if the connection can't be found - fail.
55  * - with the connection found, split all edges tagging verts (or tag verts that sit on the intersection).
56  * - run the standard connect operator.
57  */
58
59 #define CONNECT_EPS 0.0001f
60 #define VERT_OUT 1
61 #define VERT_EXCLUDE 2
62
63 /* typically hidden faces */
64 #define FACE_EXCLUDE 2
65
66 /* any element we've walked over (only do it once!) */
67 #define ELE_TOUCHED 4
68
69 #define FACE_WALK_TEST(f)  (CHECK_TYPE_INLINE(f, BMFace *), \
70         BMO_face_flag_test(pc->bm_bmoflag, f, FACE_EXCLUDE) == 0)
71 #define VERT_WALK_TEST(v)  (CHECK_TYPE_INLINE(v, BMVert *), \
72         BMO_vert_flag_test(pc->bm_bmoflag, v, VERT_EXCLUDE) == 0)
73
74 #if 0
75 #define ELE_TOUCH_TEST(e) ( \
76         CHECK_TYPE_ANY(e, BMVert *, BMEdge *, BMElem *, BMElemF *), \
77         BMO_elem_flag_test(pc->bm_bmoflag, (BMElemF *)e, ELE_TOUCHED) \
78 )
79 #endif
80 #define ELE_TOUCH_MARK(e) { \
81         CHECK_TYPE_ANY(e, BMVert *, BMEdge *, BMElem *, BMElemF *); \
82         BMO_elem_flag_enable(pc->bm_bmoflag, (BMElemF *)e, ELE_TOUCHED); \
83 } ((void)0)
84
85 #define ELE_TOUCH_TEST_VERT(v) BMO_vert_flag_test(pc->bm_bmoflag, v, ELE_TOUCHED)
86 // #define ELE_TOUCH_MARK_VERT(v) BMO_vert_flag_enable(pc->bm_bmoflag, (BMElemF *)v, ELE_TOUCHED)
87
88 #define ELE_TOUCH_TEST_EDGE(e) BMO_edge_flag_test(pc->bm_bmoflag, e, ELE_TOUCHED)
89 // #define ELE_TOUCH_MARK_EDGE(e) BMO_edge_flag_enable(pc->bm_bmoflag, (BMElemF *)e, ELE_TOUCHED)
90
91 // #define ELE_TOUCH_TEST_FACE(f) BMO_face_flag_test(pc->bm_bmoflag, f, ELE_TOUCHED)
92 // #define ELE_TOUCH_MARK_FACE(f) BMO_face_flag_enable(pc->bm_bmoflag, (BMElemF *)f, ELE_TOUCHED)
93
94 // #define DEBUG_PRINT
95
96 typedef struct PathContext {
97         HeapSimple *states;
98         float matrix[3][3];
99         float axis_sep;
100
101         /* only to access BMO flags */
102         BMesh *bm_bmoflag;
103
104         BMVert *v_a, *v_b;
105
106         BLI_mempool *link_pool;
107 } PathContext;
108
109 /**
110  * Single linked list where each item contains state and points to previous path item.
111  */
112 typedef struct PathLink {
113         struct PathLink *next;
114         BMElem *ele;       /* edge or vert */
115         BMElem *ele_from;  /* edge or face we came from (not 'next->ele') */
116 } PathLink;
117
118 typedef struct PathLinkState {
119         /* chain of links */
120         struct PathLink *link_last;
121
122         /* length along links */
123         float dist;
124         float co_prev[3];
125 } PathLinkState;
126
127 /**
128  * \name Min Dist Dir Util
129  *
130  * Simply getting the closest intersecting vert/edge is _not_ good enough. see T43792
131  * we need to get the closest in both directions since the absolute closest may be a dead-end.
132  *
133  * Logic is simple:
134  *
135  * - first intersection, store the direction.
136  * - successive intersections will update the first distance if its aligned with the first hit.
137  *   otherwise update the opposite distance.
138  * - caller stores best outcome in both directions.
139  *
140  * \{ */
141
142 typedef struct MinDistDir {
143         /* distance in both directions (FLT_MAX == uninitialized) */
144         float dist_min[2];
145         /* direction of the first intersection found */
146         float dir[3];
147 } MinDistDir;
148
149 #define MIN_DIST_DIR_INIT {{FLT_MAX, FLT_MAX}}
150
151 static int min_dist_dir_test(MinDistDir *mddir, const float dist_dir[3], const float dist_sq)
152 {
153
154         if (mddir->dist_min[0] == FLT_MAX) {
155                 return 0;
156         }
157         else {
158                 if (dot_v3v3(dist_dir, mddir->dir) > 0.0f) {
159                         if (dist_sq < mddir->dist_min[0]) {
160                                 return 0;
161                         }
162                 }
163                 else {
164                         if (dist_sq < mddir->dist_min[1]) {
165                                 return 1;
166                         }
167                 }
168         }
169
170         return -1;
171 }
172
173 static void min_dist_dir_update(MinDistDir *dist, const float dist_dir[3])
174 {
175         if (dist->dist_min[0] == FLT_MAX) {
176                 copy_v3_v3(dist->dir, dist_dir);
177         }
178 }
179
180 /** \} */
181
182
183 static int state_isect_co_pair(
184         const PathContext *pc,
185         const float co_a[3], const float co_b[3])
186 {
187         const float diff_a = dot_m3_v3_row_x((float (*)[3])pc->matrix, co_a) - pc->axis_sep;
188         const float diff_b = dot_m3_v3_row_x((float (*)[3])pc->matrix, co_b) - pc->axis_sep;
189
190         const int test_a = (fabsf(diff_a) < CONNECT_EPS) ? 0 : (diff_a < 0.0f) ? -1 : 1;
191         const int test_b = (fabsf(diff_b) < CONNECT_EPS) ? 0 : (diff_b < 0.0f) ? -1 : 1;
192
193         if ((test_a && test_b) && (test_a != test_b)) {
194                 return 1;  /* on either side */
195         }
196         else {
197                 return 0;
198         }
199 }
200
201 static int state_isect_co_exact(
202         const PathContext *pc,
203         const float co[3])
204 {
205         const float diff = dot_m3_v3_row_x((float (*)[3])pc->matrix, co) - pc->axis_sep;
206         return (fabsf(diff) <= CONNECT_EPS);
207 }
208
209 static float state_calc_co_pair_fac(
210         const PathContext *pc,
211         const float co_a[3], const float co_b[3])
212 {
213         float diff_a, diff_b, diff_tot;
214
215         diff_a = fabsf(dot_m3_v3_row_x((float (*)[3])pc->matrix, co_a) - pc->axis_sep);
216         diff_b = fabsf(dot_m3_v3_row_x((float (*)[3])pc->matrix, co_b) - pc->axis_sep);
217         diff_tot = (diff_a + diff_b);
218         return (diff_tot > FLT_EPSILON) ? (diff_a / diff_tot) : 0.5f;
219 }
220
221 static void state_calc_co_pair(
222         const PathContext *pc,
223         const float co_a[3], const float co_b[3],
224         float r_co[3])
225 {
226         const float fac = state_calc_co_pair_fac(pc, co_a, co_b);
227         interp_v3_v3v3(r_co, co_a, co_b, fac);
228 }
229
230 #ifndef NDEBUG
231 /**
232  * Ideally we wouldn't need this and for most cases we don't.
233  * But when a face has vertices that are on the boundary more than once this becomes tricky.
234  */
235 static bool state_link_find(const PathLinkState *state, BMElem *ele)
236 {
237         PathLink *link = state->link_last;
238         BLI_assert(ELEM(ele->head.htype, BM_VERT, BM_EDGE, BM_FACE));
239         if (link) {
240                 do {
241                         if (link->ele == ele) {
242                                 return true;
243                         }
244                 } while ((link = link->next));
245         }
246         return false;
247 }
248 #endif
249
250 static void state_link_add(
251         PathContext *pc, PathLinkState *state,
252         BMElem *ele, BMElem *ele_from)
253 {
254         PathLink *step_new = BLI_mempool_alloc(pc->link_pool);
255         BLI_assert(ele != ele_from);
256         BLI_assert(state_link_find(state, ele) == false);
257
258         /* never walk onto this again */
259         ELE_TOUCH_MARK(ele);
260
261 #ifdef DEBUG_PRINT
262         printf("%s: adding to state %p, %.4f - ", __func__, state, state->dist);
263         if (ele->head.htype == BM_VERT) {
264                 printf("vert %d, ", BM_elem_index_get(ele));
265         }
266         else if (ele->head.htype == BM_EDGE) {
267                 printf("edge %d, ", BM_elem_index_get(ele));
268         }
269         else {
270                 BLI_assert(0);
271         }
272
273         if (ele_from == NULL) {
274                 printf("from NULL\n");
275         }
276         else if (ele_from->head.htype == BM_EDGE) {
277                 printf("from edge %d\n", BM_elem_index_get(ele_from));
278         }
279         else if (ele_from->head.htype == BM_FACE) {
280                 printf("from face %d\n", BM_elem_index_get(ele_from));
281         }
282         else {
283                 BLI_assert(0);
284         }
285 #endif
286
287         /* track distance */
288         {
289                 float co[3];
290                 if (ele->head.htype == BM_VERT) {
291                         copy_v3_v3(co, ((BMVert *)ele)->co);
292                 }
293                 else if (ele->head.htype == BM_EDGE) {
294                         state_calc_co_pair(pc, ((BMEdge *)ele)->v1->co, ((BMEdge *)ele)->v2->co, co);
295                 }
296                 else {
297                         BLI_assert(0);
298                 }
299
300                 /* tally distance */
301                 if (ele_from) {
302                         state->dist += len_v3v3(state->co_prev, co);
303                 }
304                 copy_v3_v3(state->co_prev, co);
305         }
306
307         step_new->ele = ele;
308         step_new->ele_from = ele_from;
309         step_new->next = state->link_last;
310         state->link_last = step_new;
311 }
312
313 static PathLinkState *state_dupe_add(
314         PathLinkState *state, const PathLinkState *state_orig)
315 {
316         state = MEM_mallocN(sizeof(*state), __func__);
317         *state = *state_orig;
318         return state;
319 }
320
321 static PathLinkState *state_link_add_test(
322         PathContext *pc, PathLinkState *state, const PathLinkState *state_orig,
323         BMElem *ele, BMElem *ele_from)
324 {
325         const bool is_new = (state_orig->link_last != state->link_last);
326         if (is_new) {
327                 state = state_dupe_add(state, state_orig);
328         }
329
330         state_link_add(pc, state, ele, ele_from);
331
332         /* after adding a link so we use the updated 'state->dist' */
333         if (is_new) {
334                 BLI_heapsimple_insert(pc->states, state->dist, state);
335         }
336
337         return state;
338 }
339
340 /* walk around the face edges */
341 static PathLinkState *state_step__face_edges(
342         PathContext *pc,
343         PathLinkState *state, const PathLinkState *state_orig,
344         BMLoop *l_iter, BMLoop *l_last,
345         MinDistDir *mddir)
346 {
347
348         BMLoop *l_iter_best[2] = {NULL, NULL};
349         int i;
350
351         do {
352                 if (state_isect_co_pair(pc, l_iter->v->co, l_iter->next->v->co)) {
353                         float dist_test;
354                         float co_isect[3];
355                         float dist_dir[3];
356                         int index;
357
358                         state_calc_co_pair(pc, l_iter->v->co, l_iter->next->v->co, co_isect);
359
360                         sub_v3_v3v3(dist_dir, co_isect, state_orig->co_prev);
361                         dist_test = len_squared_v3(dist_dir);
362                         if ((index = min_dist_dir_test(mddir, dist_dir, dist_test)) != -1) {
363                                 BMElem *ele_next      = (BMElem *)l_iter->e;
364                                 BMElem *ele_next_from = (BMElem *)l_iter->f;
365
366                                 if (FACE_WALK_TEST((BMFace *)ele_next_from) &&
367                                     (ELE_TOUCH_TEST_EDGE((BMEdge *)ele_next) == false))
368                                 {
369                                         min_dist_dir_update(mddir, dist_dir);
370                                         mddir->dist_min[index] = dist_test;
371                                         l_iter_best[index] = l_iter;
372                                 }
373                         }
374                 }
375         } while ((l_iter = l_iter->next) != l_last);
376
377         for (i = 0; i < 2; i++) {
378                 if ((l_iter = l_iter_best[i])) {
379                         BMElem *ele_next      = (BMElem *)l_iter->e;
380                         BMElem *ele_next_from = (BMElem *)l_iter->f;
381                         state = state_link_add_test(pc, state, state_orig, ele_next, ele_next_from);
382                 }
383         }
384
385         return state;
386 }
387
388 /* walk around the face verts */
389 static PathLinkState *state_step__face_verts(
390         PathContext *pc,
391         PathLinkState *state, const PathLinkState *state_orig,
392         BMLoop *l_iter, BMLoop *l_last,
393         MinDistDir *mddir)
394 {
395         BMLoop *l_iter_best[2] = {NULL, NULL};
396         int i;
397
398         do {
399                 if (state_isect_co_exact(pc, l_iter->v->co)) {
400                         float dist_test;
401                         const float *co_isect = l_iter->v->co;
402                         float dist_dir[3];
403                         int index;
404
405                         sub_v3_v3v3(dist_dir, co_isect, state_orig->co_prev);
406                         dist_test = len_squared_v3(dist_dir);
407                         if ((index = min_dist_dir_test(mddir, dist_dir, dist_test)) != -1) {
408                                 BMElem *ele_next      = (BMElem *)l_iter->v;
409                                 BMElem *ele_next_from = (BMElem *)l_iter->f;
410
411                                 if (FACE_WALK_TEST((BMFace *)ele_next_from) &&
412                                     (ELE_TOUCH_TEST_VERT((BMVert *)ele_next) == false))
413                                 {
414                                         min_dist_dir_update(mddir, dist_dir);
415                                         mddir->dist_min[index] = dist_test;
416                                         l_iter_best[index] = l_iter;
417                                 }
418                         }
419                 }
420         } while ((l_iter = l_iter->next) != l_last);
421
422         for (i = 0; i < 2; i++) {
423                 if ((l_iter = l_iter_best[i])) {
424                         BMElem *ele_next      = (BMElem *)l_iter->v;
425                         BMElem *ele_next_from = (BMElem *)l_iter->f;
426                         state = state_link_add_test(pc, state, state_orig, ele_next, ele_next_from);
427                 }
428         }
429
430         return state;
431 }
432
433 static bool state_step(PathContext *pc, PathLinkState *state)
434 {
435         PathLinkState state_orig = *state;
436         BMElem *ele = state->link_last->ele;
437         const void *ele_from = state->link_last->ele_from;
438
439         if (ele->head.htype == BM_EDGE) {
440                 BMEdge *e = (BMEdge *)ele;
441
442                 BMIter liter;
443                 BMLoop *l_start;
444
445                 BM_ITER_ELEM (l_start, &liter, e, BM_LOOPS_OF_EDGE) {
446                         if ((l_start->f != ele_from) &&
447                             FACE_WALK_TEST(l_start->f))
448                         {
449                                 MinDistDir mddir = MIN_DIST_DIR_INIT;
450                                 /* very similar to block below */
451                                 state = state_step__face_edges(pc, state, &state_orig,
452                                                                l_start->next, l_start, &mddir);
453                                 state = state_step__face_verts(pc, state, &state_orig,
454                                                                l_start->next->next, l_start, &mddir);
455                         }
456                 }
457         }
458         else if (ele->head.htype == BM_VERT) {
459                 BMVert *v = (BMVert *)ele;
460
461                 /* vert loops */
462                 {
463                         BMIter liter;
464                         BMLoop *l_start;
465
466                         BM_ITER_ELEM (l_start, &liter, v, BM_LOOPS_OF_VERT) {
467                                 if ((l_start->f != ele_from) &&
468                                     FACE_WALK_TEST(l_start->f))
469                                 {
470                                         MinDistDir mddir = MIN_DIST_DIR_INIT;
471                                         /* very similar to block above */
472                                         state = state_step__face_edges(pc, state, &state_orig,
473                                                                        l_start->next, l_start->prev, &mddir);
474                                         if (l_start->f->len > 3) {
475                                                 /* adjacent verts are handled in state_step__vert_edges */
476                                                 state = state_step__face_verts(pc, state, &state_orig,
477                                                                                l_start->next->next, l_start->prev, &mddir);
478                                         }
479                                 }
480                         }
481                 }
482
483                 /* vert edges  */
484                 {
485                         BMIter eiter;
486                         BMEdge *e;
487                         BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
488                                 BMVert *v_other = BM_edge_other_vert(e, v);
489                                 if (((BMElem *)e != ele_from) &&
490                                     VERT_WALK_TEST(v_other))
491                                 {
492                                         if (state_isect_co_exact(pc, v_other->co)) {
493                                                 BMElem *ele_next      = (BMElem *)v_other;
494                                                 BMElem *ele_next_from = (BMElem *)e;
495                                                 if (ELE_TOUCH_TEST_VERT((BMVert *)ele_next) == false) {
496                                                         state = state_link_add_test(pc, state, &state_orig, ele_next, ele_next_from);
497                                                 }
498                                         }
499                                 }
500                         }
501                 }
502         }
503         else {
504                 BLI_assert(0);
505         }
506         return (state_orig.link_last != state->link_last);
507 }
508
509 /**
510  * Get a orientation matrix from 2 vertices.
511  */
512 static void bm_vert_pair_to_matrix(BMVert *v_pair[2], float r_unit_mat[3][3])
513 {
514         const float eps = 1e-8f;
515
516         float basis_dir[3];
517         float basis_tmp[3];
518         float basis_nor[3];
519
520         sub_v3_v3v3(basis_dir, v_pair[0]->co, v_pair[1]->co);
521         normalize_v3(basis_dir);
522
523 #if 0
524         add_v3_v3v3(basis_nor, v_pair[0]->no, v_pair[1]->no);
525         cross_v3_v3v3(basis_tmp, basis_nor, basis_dir);
526         cross_v3_v3v3(basis_nor, basis_tmp, basis_dir);
527 #else
528         /* align both normals to the directions before combining */
529         {
530                 float basis_nor_a[3];
531                 float basis_nor_b[3];
532
533                 /* align normal to direction */
534                 project_plane_normalized_v3_v3v3(basis_nor_a, v_pair[0]->no, basis_dir);
535                 project_plane_normalized_v3_v3v3(basis_nor_b, v_pair[1]->no, basis_dir);
536
537                 /* don't normalize before combining so as normals approach the direction, they have less effect (T46784). */
538
539                 /* combine the normals */
540                 /* for flipped faces */
541                 if (dot_v3v3(basis_nor_a, basis_nor_b) < 0.0f) {
542                         negate_v3(basis_nor_b);
543                 }
544                 add_v3_v3v3(basis_nor, basis_nor_a, basis_nor_b);
545         }
546 #endif
547
548         /* get third axis */
549         normalize_v3(basis_nor);
550         cross_v3_v3v3(basis_tmp, basis_dir, basis_nor);
551
552
553         /* Try get the axis from surrounding faces, fallback to 'ortho_v3_v3' */
554         if (UNLIKELY(normalize_v3(basis_tmp) < eps)) {
555                 /* vertex normals are directly opposite */
556
557                 /* find the loop with the lowest angle */
558                 struct { float nor[3]; float angle_cos; } axis_pair[2];
559                 int i;
560
561                 for (i = 0; i < 2; i++) {
562                         BMIter liter;
563                         BMLoop *l;
564
565                         zero_v2(axis_pair[i].nor);
566                         axis_pair[i].angle_cos = -FLT_MAX;
567
568                         BM_ITER_ELEM (l, &liter, v_pair[i], BM_LOOPS_OF_VERT) {
569                                 float basis_dir_proj[3];
570                                 float angle_cos_test;
571
572                                 /* project basis dir onto the normal to find its closest angle */
573                                 project_plane_normalized_v3_v3v3(basis_dir_proj, basis_dir, l->f->no);
574
575                                 if (normalize_v3(basis_dir_proj) > eps) {
576                                         angle_cos_test = dot_v3v3(basis_dir_proj, basis_dir);
577
578                                         if (angle_cos_test > axis_pair[i].angle_cos) {
579                                                 axis_pair[i].angle_cos = angle_cos_test;
580                                                 copy_v3_v3(axis_pair[i].nor, basis_dir_proj);
581                                         }
582                                 }
583                         }
584                 }
585
586                 /* create a new 'basis_nor' from the best direction.
587                  * note: we could add the directions,
588                  * but this more often gives 45d rotated matrix, so just use the best one. */
589                 copy_v3_v3(basis_nor, axis_pair[axis_pair[0].angle_cos < axis_pair[1].angle_cos].nor);
590                 project_plane_normalized_v3_v3v3(basis_nor, basis_nor, basis_dir);
591
592                 cross_v3_v3v3(basis_tmp, basis_dir, basis_nor);
593
594                 /* last resort, pick _any_ ortho axis */
595                 if (UNLIKELY(normalize_v3(basis_tmp) < eps)) {
596                         ortho_v3_v3(basis_nor, basis_dir);
597                         normalize_v3(basis_nor);
598                         cross_v3_v3v3(basis_tmp, basis_dir, basis_nor);
599                         normalize_v3(basis_tmp);
600                 }
601         }
602
603         copy_v3_v3(r_unit_mat[0], basis_tmp);
604         copy_v3_v3(r_unit_mat[1], basis_dir);
605         copy_v3_v3(r_unit_mat[2], basis_nor);
606         if (invert_m3(r_unit_mat) == false) {
607                 unit_m3(r_unit_mat);
608         }
609 }
610
611 void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op)
612 {
613         BMOpSlot *op_verts_slot = BMO_slot_get(op->slots_in, "verts");
614
615         PathContext pc;
616         PathLinkState state_best = {NULL};
617
618         if (op_verts_slot->len != 2) {
619                 /* fail! */
620                 return;
621         }
622
623         pc.bm_bmoflag = bm;
624         pc.v_a = ((BMVert **)op_verts_slot->data.p)[0];
625         pc.v_b = ((BMVert **)op_verts_slot->data.p)[1];
626
627         /* fail! */
628         if (!(pc.v_a && pc.v_b)) {
629                 return;
630         }
631
632 #ifdef DEBUG_PRINT
633         printf("%s: v_a: %d\n", __func__, BM_elem_index_get(pc.v_a));
634         printf("%s: v_b: %d\n", __func__, BM_elem_index_get(pc.v_b));
635 #endif
636
637         /* tag so we won't touch ever (typically hidden faces) */
638         BMO_slot_buffer_flag_enable(bm, op->slots_in, "faces_exclude", BM_FACE, FACE_EXCLUDE);
639         BMO_slot_buffer_flag_enable(bm, op->slots_in, "verts_exclude", BM_VERT, VERT_EXCLUDE);
640
641         /* setup context */
642         {
643                 pc.states = BLI_heapsimple_new();
644                 pc.link_pool = BLI_mempool_create(sizeof(PathLink), 0, 512, BLI_MEMPOOL_NOP);
645         }
646
647         /* calculate matrix */
648         {
649                 bm_vert_pair_to_matrix(&pc.v_a, pc.matrix);
650                 pc.axis_sep = dot_m3_v3_row_x(pc.matrix, pc.v_a->co);
651         }
652
653         /* add first vertex */
654         {
655                 PathLinkState *state;
656                 state = MEM_callocN(sizeof(*state), __func__);
657                 state_link_add(&pc, state, (BMElem *)pc.v_a, NULL);
658                 BLI_heapsimple_insert(pc.states, state->dist, state);
659         }
660
661
662         while (!BLI_heapsimple_is_empty(pc.states)) {
663
664 #ifdef DEBUG_PRINT
665                 printf("\n%s: stepping %u\n", __func__, BLI_heapsimple_len(pc.states));
666 #endif
667
668                 while (!BLI_heapsimple_is_empty(pc.states)) {
669                         PathLinkState *state = BLI_heapsimple_pop_min(pc.states);
670
671                         /* either we insert this into 'pc.states' or its freed */
672                         bool continue_search;
673
674                         if (state->link_last->ele == (BMElem *)pc.v_b) {
675                                 /* pass, wait until all are found */
676 #ifdef DEBUG_PRINT
677                                 printf("%s: state %p loop found %.4f\n", __func__, state, state->dist);
678 #endif
679                                 state_best = *state;
680
681                                 /* we're done, exit all loops */
682                                 BLI_heapsimple_clear(pc.states, MEM_freeN);
683                                 continue_search = false;
684                         }
685                         else if (state_step(&pc, state)) {
686                                 continue_search = true;
687                         }
688                         else {
689                                 /* didn't reach the end, remove it,
690                                  * links are shared between states so just free the link_pool at the end */
691
692 #ifdef DEBUG_PRINT
693                                 printf("%s: state %p removed\n", __func__, state);
694 #endif
695                                 continue_search = false;
696                         }
697
698                         if (continue_search) {
699                                 BLI_heapsimple_insert(pc.states, state->dist, state);
700                         }
701                         else {
702                                 MEM_freeN(state);
703                         }
704                 }
705         }
706
707         if (state_best.link_last) {
708                 PathLink *link;
709
710                 /* find the best state */
711                 link = state_best.link_last;
712                 do {
713                         if (link->ele->head.htype == BM_EDGE) {
714                                 BMEdge *e = (BMEdge *)link->ele;
715                                 BMVert *v_new;
716                                 float e_fac = state_calc_co_pair_fac(&pc, e->v1->co, e->v2->co);
717                                 v_new = BM_edge_split(bm, e, e->v1, NULL, e_fac);
718                                 BMO_vert_flag_enable(bm, v_new, VERT_OUT);
719                         }
720                         else if (link->ele->head.htype == BM_VERT) {
721                                 BMVert *v = (BMVert *)link->ele;
722                                 BMO_vert_flag_enable(bm, v, VERT_OUT);
723                         }
724                         else {
725                                 BLI_assert(0);
726                         }
727                 } while ((link = link->next));
728         }
729
730         BMO_vert_flag_enable(bm, pc.v_a, VERT_OUT);
731         BMO_vert_flag_enable(bm, pc.v_b, VERT_OUT);
732
733         BLI_mempool_destroy(pc.link_pool);
734
735         BLI_heapsimple_free(pc.states, MEM_freeN);
736
737 #if 1
738         if (state_best.link_last) {
739                 BMOperator op_sub;
740                 BMO_op_initf(bm, &op_sub, 0,
741                              "connect_verts verts=%fv faces_exclude=%s check_degenerate=%b",
742                              VERT_OUT, op, "faces_exclude", true);
743                 BMO_op_exec(bm, &op_sub);
744                 BMO_slot_copy(&op_sub, slots_out, "edges.out",
745                               op,      slots_out, "edges.out");
746                 BMO_op_finish(bm, &op_sub);
747         }
748 #endif
749 }