45#define CONNECT_EPS 0.0001f
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)
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))
65#define ELE_TOUCH_MARK(e) \
67 CHECK_TYPE_ANY(e, BMVert *, BMEdge *, BMElem *, BMElemF *); \
68 BMO_elem_flag_enable(pc->bm_bmoflag, (BMElemF *)e, ELE_TOUCHED); \
72#define ELE_TOUCH_TEST_VERT(v) BMO_vert_flag_test(pc->bm_bmoflag, v, ELE_TOUCHED)
75#define ELE_TOUCH_TEST_EDGE(e) BMO_edge_flag_test(pc->bm_bmoflag, e, ELE_TOUCHED)
140#define MIN_DIST_DIR_INIT \
154 if (dist_sq < mddir->dist_min[0]) {
159 if (dist_sq < mddir->dist_min[1]) {
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;
184 if ((test_a && test_b) && (test_a != test_b)) {
200 float diff_a, diff_b, diff_tot;
204 diff_tot = (diff_a + diff_b);
205 return (diff_tot >
FLT_EPSILON) ? (diff_a / diff_tot) : 0.5f;
228 if (link->
ele == ele) {
231 }
while ((link = link->
next));
258 if (ele_from ==
nullptr) {
280 (
reinterpret_cast<BMEdge *
>(ele))->v1->co,
281 (
reinterpret_cast<BMEdge *
>(ele))->v2->co,
298 state->link_last = step_new;
304 *
state = *state_orig;
338 BMLoop *l_iter_best[2] = {
nullptr,
nullptr};
354 BMElem *ele_next_from =
reinterpret_cast<BMElem *
>(l_iter->
f);
361 l_iter_best[
index] = l_iter;
365 }
while ((l_iter = l_iter->
next) != l_last);
367 for (i = 0; i < 2; i++) {
368 if ((l_iter = l_iter_best[i])) {
370 BMElem *ele_next_from =
reinterpret_cast<BMElem *
>(l_iter->
f);
386 BMLoop *l_iter_best[2] = {
nullptr,
nullptr};
392 const float *co_isect = l_iter->
v->
co;
400 BMElem *ele_next_from =
reinterpret_cast<BMElem *
>(l_iter->
f);
407 l_iter_best[
index] = l_iter;
411 }
while ((l_iter = l_iter->
next) != l_last);
413 for (i = 0; i < 2; i++) {
414 if ((l_iter = l_iter_best[i])) {
416 BMElem *ele_next_from =
reinterpret_cast<BMElem *
>(l_iter->
f);
428 const void *ele_from =
state->link_last->ele_from;
442 pc,
state, &state_orig, l_start->
next->
next, l_start, &mddir);
459 pc,
state, &state_orig, l_start->
next, l_start->
prev, &mddir);
460 if (l_start->
f->
len > 3) {
498 const float eps = 1e-8f;
504 sub_v3_v3v3(basis_dir, v_pair[0]->co, v_pair[1]->co);
508 add_v3_v3v3(basis_nor, v_pair[0]->no, v_pair[1]->no);
514 float basis_nor_a[3];
515 float basis_nor_b[3];
526 if (
dot_v3v3(basis_nor_a, basis_nor_b) < 0.0f) {
548 for (i = 0; i < 2; i++) {
553 axis_pair[i].angle_cos = -
FLT_MAX;
556 float basis_dir_proj[3];
557 float angle_cos_test;
563 angle_cos_test =
dot_v3v3(basis_dir_proj, basis_dir);
565 if (angle_cos_test > axis_pair[i].angle_cos) {
566 axis_pair[i].angle_cos = angle_cos_test;
576 copy_v3_v3(basis_nor, axis_pair[axis_pair[0].angle_cos < axis_pair[1].angle_cos].nor);
605 if (op_verts_slot->
len != 2) {
658 bool continue_search;
669 continue_search =
false;
672 continue_search =
true;
681 continue_search =
false;
684 if (continue_search) {
722 }
while ((link = link->
next));
738 "connect_verts verts=%fv faces_exclude=%s check_degenerate=%b",
A min-heap / priority queue ADT.
Read Blender memory allocation and freeing.
#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 ELE_TOUCH_TEST_VERT(v)
#define FACE_WALK_TEST(f)
#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)
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])
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
struct BMLoop * radial_next
union blender::BMOpSlot::@376352321363166111241172004263244043165250166277 data
struct BMOpSlot slots_in[BMO_OP_MAX_SLOTS]