Blender V5.3
bmo_connect_pair.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
10
11#include "MEM_guardedalloc.h"
12
13#include "BLI_heap_simple.hh"
14#include "BLI_math_matrix_c.hh"
15#include "BLI_math_vector_c.hh"
16#include "BLI_utildefines.hh"
17
18#include "bmesh.hh"
19
20#include "intern/bmesh_operators_private.hh" /* own include */
21
22#include "BLI_mempool.hh"
23
24namespace blender {
25
44
45#define CONNECT_EPS 0.0001f
46#define VERT_OUT 1
47#define VERT_EXCLUDE 2
48
49/* typically hidden faces */
50#define FACE_EXCLUDE 2
51
52/* any element we've walked over (only do it once!) */
53#define ELE_TOUCHED 4
54
55#define FACE_WALK_TEST(f) \
56 (CHECK_TYPE_INLINE(f, BMFace *), BMO_face_flag_test(pc->bm_bmoflag, f, FACE_EXCLUDE) == 0)
57#define VERT_WALK_TEST(v) \
58 (CHECK_TYPE_INLINE(v, BMVert *), BMO_vert_flag_test(pc->bm_bmoflag, v, VERT_EXCLUDE) == 0)
59
60#if 0
61# define ELE_TOUCH_TEST(e) \
62 (CHECK_TYPE_ANY(e, BMVert *, BMEdge *, BMElem *, BMElemF *), \
63 BMO_elem_flag_test(pc->bm_bmoflag, (BMElemF *)e, ELE_TOUCHED))
64#endif
65#define ELE_TOUCH_MARK(e) \
66 { \
67 CHECK_TYPE_ANY(e, BMVert *, BMEdge *, BMElem *, BMElemF *); \
68 BMO_elem_flag_enable(pc->bm_bmoflag, (BMElemF *)e, ELE_TOUCHED); \
69 } \
70 ((void)0)
71
72#define ELE_TOUCH_TEST_VERT(v) BMO_vert_flag_test(pc->bm_bmoflag, v, ELE_TOUCHED)
73// #define ELE_TOUCH_MARK_VERT(v) BMO_vert_flag_enable(pc->bm_bmoflag, (BMElemF *)v, ELE_TOUCHED)
74
75#define ELE_TOUCH_TEST_EDGE(e) BMO_edge_flag_test(pc->bm_bmoflag, e, ELE_TOUCHED)
76// #define ELE_TOUCH_MARK_EDGE(e) BMO_edge_flag_enable(pc->bm_bmoflag, (BMElemF *)e, ELE_TOUCHED)
77
78// #define ELE_TOUCH_TEST_FACE(f) BMO_face_flag_test(pc->bm_bmoflag, f, ELE_TOUCHED)
79// #define ELE_TOUCH_MARK_FACE(f) BMO_face_flag_enable(pc->bm_bmoflag, (BMElemF *)f, ELE_TOUCHED)
80
81// #define DEBUG_PRINT
82
85 float matrix[3][3];
86 float axis_sep;
87
88 /* only to access BMO flags */
90
92
94};
95
99struct PathLink {
101 BMElem *ele; /* edge or vert */
102 BMElem *ele_from; /* edge or face we came from (not 'next->ele') */
103};
104
106 /* chain of links */
108
109 /* length along links */
110 float dist;
111 float co_prev[3];
112};
113
114static void state_free(void *state)
115{
116 MEM_delete(static_cast<PathLinkState *>(state));
117}
118
119/* -------------------------------------------------------------------- */
132
134 /* distance in both directions (FLT_MAX == uninitialized) */
135 float dist_min[2];
136 /* direction of the first intersection found */
137 float dir[3];
138};
139
140#define MIN_DIST_DIR_INIT \
141 { \
142 { \
143 FLT_MAX, FLT_MAX \
144 } \
145 }
146
147static int min_dist_dir_test(MinDistDir *mddir, const float dist_dir[3], const float dist_sq)
148{
149
150 if (mddir->dist_min[0] == FLT_MAX) {
151 return 0;
152 }
153 if (dot_v3v3(dist_dir, mddir->dir) > 0.0f) {
154 if (dist_sq < mddir->dist_min[0]) {
155 return 0;
156 }
157 }
158 else {
159 if (dist_sq < mddir->dist_min[1]) {
160 return 1;
161 }
162 }
163
164 return -1;
165}
166
167static void min_dist_dir_update(MinDistDir *dist, const float dist_dir[3])
168{
169 if (dist->dist_min[0] == FLT_MAX) {
170 copy_v3_v3(dist->dir, dist_dir);
171 }
172}
173
175
176static int state_isect_co_pair(const PathContext *pc, const float co_a[3], const float co_b[3])
177{
178 const float diff_a = dot_m3_v3_row_x(pc->matrix, co_a) - pc->axis_sep;
179 const float diff_b = dot_m3_v3_row_x(pc->matrix, co_b) - pc->axis_sep;
180
181 const int test_a = (fabsf(diff_a) < CONNECT_EPS) ? 0 : (diff_a < 0.0f) ? -1 : 1;
182 const int test_b = (fabsf(diff_b) < CONNECT_EPS) ? 0 : (diff_b < 0.0f) ? -1 : 1;
183
184 if ((test_a && test_b) && (test_a != test_b)) {
185 return 1; /* on either side */
186 }
187 return 0;
188}
189
190static int state_isect_co_exact(const PathContext *pc, const float co[3])
191{
192 const float diff = dot_m3_v3_row_x(pc->matrix, co) - pc->axis_sep;
193 return (fabsf(diff) <= CONNECT_EPS);
194}
195
196static float state_calc_co_pair_fac(const PathContext *pc,
197 const float co_a[3],
198 const float co_b[3])
199{
200 float diff_a, diff_b, diff_tot;
201
202 diff_a = fabsf(dot_m3_v3_row_x(pc->matrix, co_a) - pc->axis_sep);
203 diff_b = fabsf(dot_m3_v3_row_x(pc->matrix, co_b) - pc->axis_sep);
204 diff_tot = (diff_a + diff_b);
205 return (diff_tot > FLT_EPSILON) ? (diff_a / diff_tot) : 0.5f;
206}
207
208static void state_calc_co_pair(const PathContext *pc,
209 const float co_a[3],
210 const float co_b[3],
211 float r_co[3])
212{
213 const float fac = state_calc_co_pair_fac(pc, co_a, co_b);
214 interp_v3_v3v3(r_co, co_a, co_b, fac);
215}
216
217#ifndef NDEBUG
222static bool state_link_find(const PathLinkState *state, BMElem *ele)
223{
224 PathLink *link = state->link_last;
226 if (link) {
227 do {
228 if (link->ele == ele) {
229 return true;
230 }
231 } while ((link = link->next));
232 }
233 return false;
234}
235#endif
236
237static void state_link_add(PathContext *pc, PathLinkState *state, BMElem *ele, BMElem *ele_from)
238{
239 PathLink *step_new = static_cast<PathLink *>(BLI_mempool_alloc(pc->link_pool));
240 BLI_assert(ele != ele_from);
241 BLI_assert(state_link_find(state, ele) == false);
242
243 /* never walk onto this again */
244 ELE_TOUCH_MARK(ele);
245
246#ifdef DEBUG_PRINT
247 printf("%s: adding to state %p, %.4f - ", __func__, state, state->dist);
248 if (ele->head.htype == BM_VERT) {
249 printf("vert %d, ", BM_elem_index_get(ele));
250 }
251 else if (ele->head.htype == BM_EDGE) {
252 printf("edge %d, ", BM_elem_index_get(ele));
253 }
254 else {
255 BLI_assert(0);
256 }
257
258 if (ele_from == nullptr) {
259 printf("from nullptr\n");
260 }
261 else if (ele_from->head.htype == BM_EDGE) {
262 printf("from edge %d\n", BM_elem_index_get(ele_from));
263 }
264 else if (ele_from->head.htype == BM_FACE) {
265 printf("from face %d\n", BM_elem_index_get(ele_from));
266 }
267 else {
268 BLI_assert(0);
269 }
270#endif
271
272 /* track distance */
273 {
274 float co[3];
275 if (ele->head.htype == BM_VERT) {
276 copy_v3_v3(co, (reinterpret_cast<BMVert *>(ele))->co);
277 }
278 else if (ele->head.htype == BM_EDGE) {
280 (reinterpret_cast<BMEdge *>(ele))->v1->co,
281 (reinterpret_cast<BMEdge *>(ele))->v2->co,
282 co);
283 }
284 else {
285 BLI_assert(0);
286 }
287
288 /* tally distance */
289 if (ele_from) {
290 state->dist += len_v3v3(state->co_prev, co);
291 }
292 copy_v3_v3(state->co_prev, co);
293 }
294
295 step_new->ele = ele;
296 step_new->ele_from = ele_from;
297 step_new->next = state->link_last;
298 state->link_last = step_new;
299}
300
302{
304 *state = *state_orig;
305 return state;
306}
307
310 const PathLinkState *state_orig,
311 BMElem *ele,
312 BMElem *ele_from)
313{
314 const bool is_new = (state_orig->link_last != state->link_last);
315 if (is_new) {
316 state = state_dupe_add(state, state_orig);
317 }
318
319 state_link_add(pc, state, ele, ele_from);
320
321 /* after adding a link so we use the updated 'state->dist' */
322 if (is_new) {
324 }
325
326 return state;
327}
328
329/* walk around the face edges */
332 const PathLinkState *state_orig,
333 BMLoop *l_iter,
334 BMLoop *l_last,
335 MinDistDir *mddir)
336{
337
338 BMLoop *l_iter_best[2] = {nullptr, nullptr};
339 int i;
340
341 do {
342 if (state_isect_co_pair(pc, l_iter->v->co, l_iter->next->v->co)) {
343 float dist_test;
344 float co_isect[3];
345 float dist_dir[3];
346 int index;
347
348 state_calc_co_pair(pc, l_iter->v->co, l_iter->next->v->co, co_isect);
349
350 sub_v3_v3v3(dist_dir, co_isect, state_orig->co_prev);
351 dist_test = len_squared_v3(dist_dir);
352 if ((index = min_dist_dir_test(mddir, dist_dir, dist_test)) != -1) {
353 BMElem *ele_next = reinterpret_cast<BMElem *>(l_iter->e);
354 BMElem *ele_next_from = reinterpret_cast<BMElem *>(l_iter->f);
355
356 if (FACE_WALK_TEST((BMFace *)ele_next_from) &&
357 (ELE_TOUCH_TEST_EDGE((BMEdge *)ele_next) == false))
358 {
359 min_dist_dir_update(mddir, dist_dir);
360 mddir->dist_min[index] = dist_test;
361 l_iter_best[index] = l_iter;
362 }
363 }
364 }
365 } while ((l_iter = l_iter->next) != l_last);
366
367 for (i = 0; i < 2; i++) {
368 if ((l_iter = l_iter_best[i])) {
369 BMElem *ele_next = reinterpret_cast<BMElem *>(l_iter->e);
370 BMElem *ele_next_from = reinterpret_cast<BMElem *>(l_iter->f);
371 state = state_link_add_test(pc, state, state_orig, ele_next, ele_next_from);
372 }
373 }
374
375 return state;
376}
377
378/* walk around the face verts */
381 const PathLinkState *state_orig,
382 BMLoop *l_iter,
383 BMLoop *l_last,
384 MinDistDir *mddir)
385{
386 BMLoop *l_iter_best[2] = {nullptr, nullptr};
387 int i;
388
389 do {
390 if (state_isect_co_exact(pc, l_iter->v->co)) {
391 float dist_test;
392 const float *co_isect = l_iter->v->co;
393 float dist_dir[3];
394 int index;
395
396 sub_v3_v3v3(dist_dir, co_isect, state_orig->co_prev);
397 dist_test = len_squared_v3(dist_dir);
398 if ((index = min_dist_dir_test(mddir, dist_dir, dist_test)) != -1) {
399 BMElem *ele_next = reinterpret_cast<BMElem *>(l_iter->v);
400 BMElem *ele_next_from = reinterpret_cast<BMElem *>(l_iter->f);
401
402 if (FACE_WALK_TEST((BMFace *)ele_next_from) &&
403 (ELE_TOUCH_TEST_VERT((BMVert *)ele_next) == false))
404 {
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 = reinterpret_cast<BMElem *>(l_iter->v);
416 BMElem *ele_next_from = reinterpret_cast<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
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 = reinterpret_cast<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)) {
439 /* Very similar to block below. */
440 state = state_step__face_edges(pc, state, &state_orig, l_start->next, l_start, &mddir);
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 = reinterpret_cast<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)) {
457 /* Very similar to block above. */
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. */
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 ((reinterpret_cast<BMElem *>(e) != ele_from) && VERT_WALK_TEST(v_other)) {
476 if (state_isect_co_exact(pc, v_other->co)) {
477 BMElem *ele_next = reinterpret_cast<BMElem *>(v_other);
478 BMElem *ele_next_from = reinterpret_cast<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
496static 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 (#46784). */
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 (normalize_v3(basis_tmp) < eps) [[unlikely]] {
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 (normalize_v3(basis_tmp) < eps) [[unlikely]] {
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
599{
600 BMOpSlot *op_verts_slot = BMO_slot_get(op->slots_in, "verts");
601
602 PathContext pc;
603 PathLinkState state_best = {nullptr};
604
605 if (op_verts_slot->len != 2) {
606 /* fail! */
607 return;
608 }
609
610 pc.bm_bmoflag = bm;
611 pc.v_pair[0] = (static_cast<BMVert **>(op_verts_slot->data.p))[0];
612 pc.v_pair[1] = (static_cast<BMVert **>(op_verts_slot->data.p))[1];
613
614 /* fail! */
615 if (!(pc.v_pair[0] && pc.v_pair[1])) {
616 return;
617 }
618
619#ifdef DEBUG_PRINT
620 printf("%s: v_pair[0]: %d\n", __func__, BM_elem_index_get(pc.v_pair[0]));
621 printf("%s: v_pair[1]: %d\n", __func__, BM_elem_index_get(pc.v_pair[1]));
622#endif
623
624 /* tag so we won't touch ever (typically hidden faces) */
627
628 /* setup context */
629 {
632 }
633
634 /* calculate matrix */
635 {
637 pc.axis_sep = dot_m3_v3_row_x(pc.matrix, pc.v_pair[0]->co);
638 }
639
640 /* add first vertex */
641 {
644 state_link_add(&pc, state, reinterpret_cast<BMElem *>(pc.v_pair[0]), nullptr);
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)) {
656
657 /* either we insert this into 'pc.states' or its freed */
658 bool continue_search;
659
660 if (state->link_last->ele == reinterpret_cast<BMElem *>(pc.v_pair[1])) {
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 */
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) {
686 }
687 else {
688 MEM_delete(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 = reinterpret_cast<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, nullptr, e_fac);
704 /* Adding vertices makes the face-normals stale.
705 * These are used for the `connect_verts` call next for projecting onto the face,
706 * so the normals must be recalculated here. */
707 if (e->l) {
708 BMLoop *l_iter = e->l;
709 do {
710 BM_face_normal_update(l_iter->f);
711 } while ((l_iter = l_iter->radial_next) != e->l);
712 }
714 }
715 else if (link->ele->head.htype == BM_VERT) {
716 BMVert *v = reinterpret_cast<BMVert *>(link->ele);
718 }
719 else {
720 BLI_assert(0);
721 }
722 } while ((link = link->next));
723 }
724
727
729
731
732#if 1
733 if (state_best.link_last) {
736 &op_sub,
737 0,
738 "connect_verts verts=%fv faces_exclude=%s check_degenerate=%b",
739 VERT_OUT,
740 op,
741 "faces_exclude",
742 true);
744 BMO_slot_copy(&op_sub, slots_out, "edges.out", op, slots_out, "edges.out");
746 }
747#endif
748}
749
750} // namespace blender
A min-heap / priority queue ADT.
Read Blender memory allocation and freeing.
#define ELEM(...)
#define BM_elem_index_get(ele)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define BMO_vert_flag_enable(bm, e, oflag)
#define BMO_slot_copy(op_src, slots_src, slot_name_src, op_dst, slots_dst, slot_name_dst)
#define FACE_EXCLUDE
#define ELE_TOUCH_TEST_VERT(v)
#define CONNECT_EPS
#define VERT_EXCLUDE
#define FACE_WALK_TEST(f)
#define VERT_OUT
#define VERT_WALK_TEST(v)
#define ELE_TOUCH_MARK(e)
#define ELE_TOUCH_TEST_EDGE(e)
#define MIN_DIST_DIR_INIT
IMETHOD Vector diff(const Vector &a, const Vector &b, double dt)
Definition frames.inl:1166
#define FLT_MAX
#define FLT_EPSILON
const int state
BMesh Iterators.
void BLI_heapsimple_clear(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
void * MEM_new_uninitialized(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
static double op_sub(double a, double b)
static float state_calc_co_pair_fac(const PathContext *pc, const float co_a[3], const float co_b[3])
static int state_isect_co_pair(const PathContext *pc, const float co_a[3], const float co_b[3])
MINLINE void copy_v3_v3(float r[3], const float a[3])
ATTR_WARN_UNUSED_RESULT const BMLoop * l
MINLINE void add_v3_v3v3(float r[3], const float a[3], const float b[3])
void BMO_slot_buffer_flag_enable(BMesh *bm, BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *slot_name, char htype, short oflag)
BMO_FLAG_BUFFER.
uint BLI_heapsimple_len(const HeapSimple *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
bool BMO_op_initf(BMesh *bm, BMOperator *op, int flag, const char *fmt,...)
void project_plane_normalized_v3_v3v3(float out[3], const float p[3], const float v_plane[3])
ATTR_WARN_UNUSED_RESULT const BMVert * v
void BMO_op_exec(BMesh *bm, BMOperator *op)
BMESH OPSTACK EXEC OP.
static void state_link_add(PathContext *pc, PathLinkState *state, BMElem *ele, BMElem *ele_from)
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static void min_dist_dir_update(MinDistDir *dist, const float dist_dir[3])
static PathLinkState * state_step__face_verts(PathContext *pc, PathLinkState *state, const PathLinkState *state_orig, BMLoop *l_iter, BMLoop *l_last, MinDistDir *mddir)
void BLI_mempool_destroy(BLI_mempool *pool) ATTR_NONNULL(1)
void * BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1)
static PathLinkState * state_dupe_add(PathLinkState *state, const PathLinkState *state_orig)
void * MEM_new_zeroed(size_t len, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1) ATTR_NONNULL(2)
MINLINE void cross_v3_v3v3(float r[3], const float a[3], const float b[3])
void BM_face_normal_update(BMFace *f)
static bool state_link_find(const PathLinkState *state, BMElem *ele)
BLI_mempool * BLI_mempool_create(unsigned int esize, unsigned int elem_num, unsigned int pchunk, unsigned int flag) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL
static PathLinkState * state_link_add_test(PathContext *pc, PathLinkState *state, const PathLinkState *state_orig, BMElem *ele, BMElem *ele_from)
void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op)
MINLINE float dot_m3_v3_row_x(const float M[3][3], const float a[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void negate_v3(float r[3])
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
static int min_dist_dir_test(MinDistDir *mddir, const float dist_dir[3], const float dist_sq)
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
static void state_free(void *state)
HeapSimple * BLI_heapsimple_new() ATTR_WARN_UNUSED_RESULT
void ortho_v3_v3(float out[3], const float v[3])
BMOpSlot * BMO_slot_get(BMOpSlot slot_args[BMO_OP_MAX_SLOTS], const char *identifier)
BMESH OPSTACK GET SLOT.
bool invert_m3(float mat[3][3])
static bool state_step(PathContext *pc, PathLinkState *state)
MINLINE float normalize_v3(float n[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
BMVert * BM_edge_split(BMesh *bm, BMEdge *e, BMVert *v, BMEdge **r_e, float fac)
Edge Split.
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
void unit_m3(float m[3][3])
static void bm_vert_pair_to_matrix(BMVert *v_pair[2], float r_unit_mat[3][3])
@ BLI_MEMPOOL_NOP
bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1)
MINLINE float len_squared_v3(const float v[3]) ATTR_WARN_UNUSED_RESULT
static void state_calc_co_pair(const PathContext *pc, const float co_a[3], const float co_b[3], float r_co[3])
static int state_isect_co_exact(const PathContext *pc, const float co[3])
void * BLI_mempool_alloc(BLI_mempool *pool) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(1)
void BMO_op_finish(BMesh *bm, BMOperator *op)
BMESH OPSTACK FINISH OP.
MINLINE float len_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
static PathLinkState * state_step__face_edges(PathContext *pc, PathLinkState *state, const PathLinkState *state_orig, BMLoop *l_iter, BMLoop *l_last, MinDistDir *mddir)
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void zero_v2(float r[2])
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
const btScalar eps
Definition poly34.cpp:11
#define fabsf
struct BMLoop * next
struct BMLoop * prev
struct BMEdge * e
struct BMVert * v
struct BMLoop * radial_next
struct BMFace * f
union blender::BMOpSlot::@376352321363166111241172004263244043165250166277 data
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]