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