49#define FACE_NET _FLAG_WALK
51#define EDGE_NET _FLAG_WALK
53#define VERT_VISIT _FLAG_WALK
54#define VERT_IN_QUEUE _FLAG_WALK_ALT
91 const float axis_mat[3][3],
106 const float face_normal[3],
107 const float face_normal_matrix[3][3],
120 int edges_boundary_len = 0;
121 int edges_wire_len = 0;
125 e = e_first = v_init->
e;
131 edges_boundary_len++;
133 else if (count == 0) {
142 if (edges_boundary_len == 0) {
151 if (edges_wire_len == 0) {
152 if (edges_boundary_len > 1) {
155 if (edges_boundary_len > 2) {
166 if (edges_wire_len > 1) {
177 float dir_prev[2], dir_next[2];
181 float angle_best_cos =
dot_v2v2(dir_next, dir_prev);
189 const float angle_test_cos =
dot_v2v2(dir_prev, dir_test);
191 if (angle_test_cos > angle_best_cos) {
192 angle_best_cos = angle_test_cos;
201 if (face_normal == l_walk->
f->
no) {
204 if (l_walk->
v != v_init) {
208 std::swap(e_pair[0], e_pair[1]);
224 int edges_boundary_len = 0;
225 int edges_wire_len = 0;
229 e = e_first = v_init->
e;
234 edges_boundary_len++;
236 else if (count == 0) {
244 if (edges_boundary_len == 0) {
249 if (edges_wire_len == 0) {
250 if (edges_boundary_len >= 2) {
266 const float face_normal[3],
269 const uint edge_order_len,
277#define USE_FASTPATH_NOFORK
314#ifdef USE_FASTPATH_NOFORK
334 if (e_next != e_first) {
350 printf(
"vert %d -> %d (add=%d)\n",
367#ifdef USE_FASTPATH_NOFORK
381 for (j = 0; j <
STACK_SIZE(edge_order); j++) {
383 v_prev->
co,
v->
co, edge_order[j].
v->
co, face_normal);
387#ifdef USE_FASTPATH_NOFORK
411#undef USE_FASTPATH_NOFORK
415 const float face_normal[3],
416 const float face_normal_matrix[3][3],
419 const uint edge_order_len,
422 int *r_face_verts_len,
423 bool *r_check_face_exists)
435 v_init, face_normal, edge_order, edge_order_len, e_pair))
441 bool check_face_exists =
true;
445 face_verts[i] = v_init;
446 face_edges[i] = e_pair[1];
448 check_face_exists =
false;
454 face_edges[i] =
v->
e;
456 check_face_exists =
false;
466 for (
int j = 0, j_prev = i - 1; j < i; j_prev = j++) {
471 *r_face_verts_len = i;
473 *r_check_face_exists = check_face_exists;
490 const uint edge_order_len = edge_net_len + 2;
520 for (i = 0; i < edge_net_len; i++) {
527 }
while ((l_iter = l_iter->
next) != l_first);
536 for (i = 0; i < edge_net_len; i++) {
545 }
while ((l_iter = l_iter->
next) != l_first);
547 float face_normal_matrix[3][3];
556 bool check_face_exists =
false;
570 if (check_face_exists &&
BM_face_exists(face_verts, face_verts_len)) [[unlikely]] {
577 for (i = 0; i < edge_net_len; i++) {
606 }
while ((l_iter = l_iter->
next) != l_first);
620 void **blocks = blocks_buf.
data();
621 float (*cos_2d)[2] =
reinterpret_cast<float (*)[2]
>(cos_2d_buf.
data());
622 float axis_mat[3][3];
643 }
while ((
void)i++, (l_iter = l_iter->
next) != l_first);
645 for (i = 0; i < edge_net_len; i++) {
657 if (l_first ==
nullptr) {
675 for (i = 0; i < edge_net_len; i++) {
686 }
while ((l_iter = l_iter->
next) != l_first);
697 for (
BMFace *face : face_arr) {
702 *r_face_arr = std::move(face_arr);
705 MEM_delete(edge_order);
706 MEM_delete(face_verts);
707 MEM_delete(face_edges);
708 MEM_delete(vert_queue);
733#define USE_PARTIAL_CONNECT
735#define VERT_IS_VALID BM_ELEM_INTERNAL_TAG
747 const float endpoint_bias = 1e-4f;
749 v_a->
co, v_b->
co,
e->v1->
co,
e->v2->
co, endpoint_bias, r_isect) == 1) &&
750 ((
e->v1 != v_a) && (
e->v2 != v_a) && (
e->v1 != v_b) && (
e->v2 != v_b)));
755 if (pt_a[0] < pt_b[0]) {
758 if (pt_a[0] > pt_b[0]) {
761 if (pt_a[1] < pt_b[1]) {
764 if (pt_a[1] > pt_b[1]) {
801 if (test == 0) [[unlikely]] {
837 const float dist_new =
data->dist_orig * t;
841 if ((dist_new < hit->dist) && (dist_new > 0.0f)) [[likely]] {
843 if (v1_index <
int(
data->vert_range[0]) || v1_index >=
int(
data->vert_range[1])) {
844 hit->
dist = dist_new;
867 if (dist_new < hit->dist && (dist_new > 0.0f)) [[likely]] {
868 if (
e->v1 !=
data->v_origin &&
e->v2 !=
data->v_origin) {
871 if (v1_index <
int(
data->vert_range[0]) || v1_index >=
int(
data->vert_range[1])) {
872 hit->
dist = dist_new;
930 if (
index == -1) [[likely]] {
938 if (t_test < t_best) {
983 if (
index != -1) [[likely]] {
988 if (
e->v1 != v_origin &&
e->v2 != v_origin) {
990 if (dist_new < hit.
dist) [[likely]] {
1006 bool direction_sign)
1022 float dir[3] = {0, 0, 0};
1023 dir[
SORT_AXIS] = direction_sign ? 1.0f : -1.0f;
1025 BMVert *v_other =
nullptr;
1028 BMVert *v_other_fallback =
nullptr;
1047 for (
int j = 0; j < 2; j++) {
1048 BMVert *v_iter = v_pair[j];
1059 v_other_fallback = v_other;
1064 if (v_other ==
nullptr) {
1066 printf(
"Using fallback\n");
1068 v_other = v_other_fallback;
1086#ifdef USE_PARTIAL_CONNECT
1112 LinkNode *e_delimit_list =
nullptr;
1113 uint e_delimit_list_len = 0;
1115# define EDGE_NOT_IN_STACK BM_ELEM_INTERNAL_TAG
1116# define VERT_NOT_IN_STACK BM_ELEM_INTERNAL_TAG
1118# define FOREACH_VERT_EDGE(v_, e_, body_) \
1120 BMEdge *e_ = v_->e; \
1123 } while ((e_ = BM_DISK_EDGE_NEXT(e_, v_)) != v_->e); \
1128 BMEdge *e_face_init =
nullptr;
1134 e_delimit_list_len++;
1136 e_face_init = e_iter;
1142 if (e_delimit_list_len <= 2) [[likely]] {
1183 bool is_delimit =
false;
1195# undef FOREACH_VERT_EDGE
1198 BMVert *v_split =
nullptr;
1210 if (v_split->e ==
nullptr) [[unlikely]] {
1220 }
while ((vert_stack = vert_stack->
next));
1224 }
while ((e_delimit_list = e_delimit_list->
next));
1226# undef EDGE_NOT_IN_STACK
1227# undef VERT_NOT_IN_STACK
1236 const int v_a_index,
1237 const int v_b_index)
1240 if ((remap[v_a_index] == v_b_index) || (remap[v_b_index] == v_a_index)) [[unlikely]] {
1251 const uint edge_net_init_len,
1252 bool use_partial_connect,
1254 BMEdge ***r_edge_net_new,
1255 uint *r_edge_net_new_len)
1274 uint edge_net_new_len =
uint(edge_net_init_len);
1276 memcpy(edge_arr, edge_net_init,
sizeof(*edge_arr) *
size_t(edge_net_init_len));
1279#define EDGE_NOT_IN_STACK BM_ELEM_INTERNAL_TAG
1280#define VERT_NOT_IN_STACK BM_ELEM_INTERNAL_TAG
1283 uint i = edge_net_init_len;
1284 BMLoop *l_iter, *l_first;
1289 edge_arr[i++] = l_iter->
e;
1290 }
while ((l_iter = l_iter->
next) != l_first);
1294 for (
uint i = 0; i < edge_arr_len; i++) {
1300#ifdef USE_PARTIAL_CONNECT
1302 struct TempVertPair {
1312 } temp_vert_pairs = {
nullptr};
1314 if (use_partial_connect) {
1315 for (
uint i = 0; i < edge_net_init_len; i++) {
1316 for (
uint j = 0; j < 2; j++) {
1317 BMVert *v_delimit = (&edge_arr[i]->
v1)[j];
1322 TempVertPair *tvp =
static_cast<TempVertPair *
>(
1324 tvp->next = temp_vert_pairs.list;
1325 tvp->v_orig = v_delimit;
1326 tvp->v_temp = v_other;
1327 temp_vert_pairs.list = tvp;
1328 temp_vert_pairs.len++;
1333 if (temp_vert_pairs.len == 0) {
1334 use_partial_connect =
false;
1339 uint group_arr_len = 0;
1344 uint edge_index = (edge_arr_len - 1);
1345 uint edge_in_group_tot = 0;
1351 uint unique_verts_in_group = 0, unique_edges_in_group = 0;
1360 unique_verts_in_group++;
1366 unique_edges_in_group++;
1381 g->
vert_len = unique_verts_in_group;
1382 g->
edge_len = unique_edges_in_group;
1383 edge_in_group_tot += unique_edges_in_group;
1389 if (edge_in_group_tot == edge_arr_len) {
1402 BMEdge **edge_net_new =
nullptr;
1404 float (*vert_coords_backup)[3] =
nullptr;
1405 uint *verts_group_table =
nullptr;
1406 BMVert **vert_arr =
nullptr;
1407 uint vert_arr_len = 0;
1411 if (group_arr_len == 1) {
1421 float axis_mat[3][3];
1424#define VERT_IN_ARRAY BM_ELEM_INTERNAL_TAG
1427#define EDGE_IS_NEW BM_ELEM_SELECT_UV
1442 g->vert_span.min = (
static_cast<BMEdge *
>(edge_links->
link))->v1;
1443 g->vert_span.max = (
static_cast<BMEdge *
>(edge_links->
link))->
v2;
1451 for (
int j = 0; j < 2; j++) {
1456 const float axis_value[2] = {
1467 g->vert_span.min = v_iter;
1471 g->vert_span.max = v_iter;
1475 }
while ((edge_links = edge_links->
next));
1480 g->has_prev_edge =
false;
1482 vert_arr_len += g->vert_len;
1484 *(--group_arr_p) = g;
1491 vert_arr =
static_cast<BMVert **
>(
1494 verts_group_table =
static_cast<uint *
>(
1497 vert_coords_backup =
static_cast<float (*)[3]
>(
1505 for (
uint g_index = 0; g_index < group_arr_len; g_index++) {
1509 for (
int j = 0; j < 2; j++) {
1523 v_iter->
co[0] = co_2d[0];
1524 v_iter->
co[1] = co_2d[1];
1525 v_iter->
co[2] = 0.0f;
1530 vert_arr[v_index] = v_iter;
1531 verts_group_table[v_index] = g_index;
1535 }
while ((edge_links = edge_links->
next));
1546 for (
uint i = 0; i < edge_arr_len; i++) {
1547 const float e_cos[2][3] = {
1548 {
UNPACK2(edge_arr[i]->v1->co), 0.0f},
1555#ifdef USE_PARTIAL_CONNECT
1556 if (use_partial_connect) {
1558 temp_vert_pairs.remap =
static_cast<int *
>(
1560 std::fill_n(temp_vert_pairs.remap, vert_arr_len, -1);
1562 TempVertPair *tvp = temp_vert_pairs.list;
1565 }
while ((tvp = tvp->next));
1572 edge_net_new_len =
uint(edge_net_init_len) + ((group_arr_len - 1) * 2);
1573 edge_net_new =
static_cast<BMEdge **
>(
1575 memcpy(edge_net_new, edge_net_init,
sizeof(*edge_net_new) *
size_t(edge_net_init_len));
1578 uint edge_net_new_index = edge_net_init_len;
1584 vert_range[1] = group_arr[0]->
vert_len;
1599 for (
uint g_index = 1; g_index < group_arr_len; g_index++) {
1603 vert_range[0] = vert_range[1];
1613 if (index_other != -1) {
1614#ifdef USE_PARTIAL_CONNECT
1615 if ((use_partial_connect ==
false) ||
1620 BMVert *v_end = vert_arr[index_other];
1626 if ((edge_net_new[edge_net_new_index] = e_new)) {
1627#ifdef USE_PARTIAL_CONNECT
1631 edge_net_new_index++;
1645 if (index_other != -1) {
1646#ifdef USE_PARTIAL_CONNECT
1647 if ((use_partial_connect ==
false) ||
1652 BMVert *v_end = vert_arr[index_other];
1658 if ((edge_net_new[edge_net_new_index] = e_new)) {
1659#ifdef USE_PARTIAL_CONNECT
1663 edge_net_new_index++;
1669 uint g_index_other = verts_group_table[index_other];
1674 BLI_assert(edge_net_new_len >= edge_net_new_index);
1675 edge_net_new_len = edge_net_new_index;
1680 *r_edge_net_new = edge_net_new;
1681 *r_edge_net_new_len = edge_net_new_len;
1684 for (
uint i = 0; i < vert_arr_len; i++) {
1685 copy_v3_v3(vert_arr[i]->co, vert_coords_backup[i]);
1690#ifdef USE_PARTIAL_CONNECT
1692 if (use_partial_connect) {
1697 TempVertPair *tvp = temp_vert_pairs.list;
1702 }
while ((tvp = tvp->next));
1706 TempVertPair *tvp = temp_vert_pairs.list;
1715 }
while ((tvp = tvp->next));
1724 for (
uint i = edge_net_init_len; i < edge_net_new_len; i++) {
1730 if (i == edge_net_new_len) {
1733 edge_net_new[i] = edge_net_new[edge_net_new_len];
1737 *r_edge_net_new_len = edge_net_new_len;
1741 for (
uint i = 0; i < edge_arr_len; i++) {
1749#undef VERT_NOT_IN_STACK
1750#undef EDGE_NOT_IN_STACK
CustomData interface, see also DNA_customdata_types.h.
#define BVH_RAYCAST_DIST_MAX
#define BLI_linklist_prepend_alloca(listp, ptr)
BLI_LINKSTACK_*** wrapper macros for using a LinkNode to store a stack of pointers,...
#define BLI_SMALLSTACK_DECLARE(var, type)
#define BLI_SMALLSTACK_POP(var)
#define BLI_SMALLSTACK_PUSH(var, data)
#define BLI_SMALLSTACK_POP_EX(var_src, var_dst)
#define BLI_SMALLSTACK_IS_EMPTY(var)
#define BLI_SMALLSTACK_SWAP(var_a, var_b)
#define BLI_ASSERT_UNIT_V2(v)
#define STACK_POP_PTR(stack)
#define STACK_PUSH(stack, val)
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_PUSH_RET_PTR(stack)
#define STACK_INIT(stack, stack_num)
Read Blender memory allocation and freeing.
#define ARRAY_SET_ITEMS(...)
#define UNUSED_VARS_NDEBUG(...)
#define BM_DISK_EDGE_NEXT(e, v)
#define BM_FACE_FIRST_LOOP(p)
#define BM_elem_index_get(ele)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_flag_set(ele, hflag, val)
#define BM_elem_index_set(ele, index)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define BM_ITER_ELEM(ele, iter, data, itype)
#define VERT_NOT_IN_STACK
#define EDGE_NOT_IN_STACK
#define FOREACH_VERT_EDGE(v_, e_, body_)
#define BM_ELEM_API_FLAG_DISABLE(element, f)
#define BM_ELEM_API_FLAG_TEST(element, f)
#define BM_ELEM_API_FLAG_ENABLE(element, f)
SIMD_FORCE_INLINE const btScalar & w() const
Return the w value.
void append(const T &value)
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
static BMVert * bm_face_split_edgenet_partial_connect(BMesh *bm, BMVert *v_delimit, BMFace *f)
BLI_INLINE bool BM_edge_is_wire(const BMEdge *e) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
bool BM_edge_in_face(const BMEdge *e, const BMFace *f)
bool isect_ray_seg_v2(const float ray_origin[2], const float ray_direction[2], const float v0[2], const float v1[2], float *r_lambda, float *r_u)
MINLINE float dot_m3_v3_row_y(const float M[3][3], const float a[3]) ATTR_WARN_UNUSED_RESULT
MINLINE void copy_v3_v3(float r[3], const float a[3])
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
static bool bm_face_split_edgenet_find_loop_walk(BMVert *v_init, const float face_normal[3], VertOrder *edge_order, const uint edge_order_len, BMEdge *e_pair[2])
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void BM_vert_kill(BMesh *bm, BMVert *v)
static BMLoop * bm_edge_flagged_radial_first(BMEdge *e)
MINLINE void copy_v2_v2(float r[2], const float a[2])
void BLI_bvhtree_free(BVHTree *tree)
void CustomData_bmesh_interp(CustomData *data, const void **src_blocks, const float *weights, int count, void *dst_block)
int BLI_bvhtree_ray_cast_ex(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata, int flag)
void mul_v2_m3v3(float r[2], const float M[3][3], const float a[3])
static bool bm_vert_partial_connect_check_overlap(const int *remap, const int v_a_index, const int v_b_index)
int isect_seg_seg_v2_point_ex(const float v0[2], const float v1[2], const float v2[2], const float v3[2], float endpoint_bias, float r_vi[2])
void BLI_bvhtree_balance(BVHTree *tree)
void BLI_linklist_prepend_arena(LinkNode **listp, void *ptr, struct MemArena *ma) ATTR_NONNULL(1
MINLINE void sub_v2_v2v2(float r[2], const float a[2], const float b[2])
static void bvhtree_test_edges_isect_2d_vert_cb(void *user_data, int index, const BVHTreeRay *, BVHTreeRayHit *hit)
MINLINE float normalize_v2(float n[2])
ATTR_WARN_UNUSED_RESULT const BMVert * v
void CustomData_bmesh_copy_block(CustomData &data, void *src_block, void **dst_block)
BMVert * BM_vert_create(BMesh *bm, const float co[3], const BMVert *v_example, const eBMCreateFlag create_flag)
Main function for creating a new vertex.
BMFace * BM_face_create(BMesh *bm, BMVert *const *verts, BMEdge *const *edges, const int len, const BMFace *f_example, const eBMCreateFlag create_flag)
void BM_vert_separate_tested_edges(BMesh *, BMVert *v_dst, BMVert *v_src, bool(*testfn)(BMEdge *, void *arg), void *arg)
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
static bool test_tagged_and_notface(BMEdge *e, void *fptr)
MINLINE void sub_v3_v3(float r[3], const float a[3])
float angle_signed_on_axis_v3v3v3_v3(const float v1[3], const float v2[3], const float v3[3], const float axis[3]) ATTR_WARN_UNUSED_RESULT
void BM_edge_kill(BMesh *bm, BMEdge *e)
BMesh const char void * data
float line_point_factor_v2(const float p[2], const float l1[2], const float l2[2])
void BLI_linklist_prepend_nlink(LinkNode **listp, void *ptr, LinkNode *nlink) ATTR_NONNULL(1
static uint bm_edge_flagged_radial_count(BMEdge *e)
static BMEdge * test_edges_isect_2d_vert(const EdgeGroup_FindConnection_Args *args, BMVert *v_origin, BMVert *v_other)
static bool bm_face_split_edgenet_find_loop_pair_exists(BMVert *v_init)
MINLINE axis_t min_axis(axis_t a, axis_t b)
int BLI_sortutil_cmp_float_reverse(const void *a_, const void *b_)
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
MINLINE float dot_m3_v3_row_x(const float M[3][3], const float a[3]) ATTR_WARN_UNUSED_RESULT
bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src)
Splice Vert.
static int group_min_cmp_fn(const void *p1, const void *p2)
MINLINE float dot_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT
void interp_weights_poly_v2(float w[], float v[][2], int n, const float co[2])
BMFace * BM_face_exists(BMVert *const *varr, int len)
void * BLI_memarena_alloc(MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
BMEdge * BM_edge_exists(BMVert *v_a, BMVert *v_b)
static BMEdge * test_edges_isect_2d_ray(const EdgeGroup_FindConnection_Args *args, BMVert *v_origin, const float dir[3])
MINLINE void sub_v3_v3v3(float r[3], const float a[3], const float b[3])
BLI_INLINE bool edge_isect_verts_point_2d(const BMEdge *e, const BMVert *v_a, const BMVert *v_b, float r_isect[2])
ATTR_WARN_UNUSED_RESULT const BMVert * v2
void BM_face_kill(BMesh *bm, BMFace *f)
bool BM_face_split_edgenet_connect_islands(BMesh *bm, BMFace *f, BMEdge **edge_net_init, const uint edge_net_init_len, bool use_partial_connect, MemArena *mem_arena, BMEdge ***r_edge_net_new, uint *r_edge_net_new_len)
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
static bool bm_face_split_edgenet_find_loop_pair(BMVert *v_init, const float face_normal[3], const float face_normal_matrix[3][3], BMEdge *e_pair[2])
bool BM_face_split_edgenet(BMesh *bm, BMFace *f, BMEdge **edge_net, const int edge_net_len, Vector< BMFace * > *r_face_arr)
BMEdge * BM_edge_find_double(BMEdge *e)
bool BM_vert_splice_check_double_face(BMVert *v_a, BMVert *v_b)
static void normalize_v2_m3_v3v3(float out[2], const float axis_mat[3][3], const float v1[3], const float v2[3])
bool CustomData_has_math(const CustomData *data)
MINLINE float len_squared_v2v2(const float a[2], const float b[2]) ATTR_WARN_UNUSED_RESULT
static int bm_face_split_edgenet_find_connection(const EdgeGroup_FindConnection_Args *args, BMVert *v_origin, bool direction_sign)
static void bvhtree_test_edges_isect_2d_ray_cb(void *user_data, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
BLI_INLINE int axis_pt_cmp(const float pt_a[2], const float pt_b[2])
BMEdge * BM_edge_create(BMesh *bm, BMVert *v1, BMVert *v2, const BMEdge *e_example, const eBMCreateFlag create_flag)
Main function for creating a new edge.
void bmesh_face_swap_data(BMFace *f_a, BMFace *f_b)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void axis_dominant_v3_to_m3(float r_mat[3][3], const float normal[3])
Normal to x,y matrix.
static bool bm_face_split_edgenet_find_loop(BMVert *v_init, const float face_normal[3], const float face_normal_matrix[3][3], VertOrder *edge_order, const uint edge_order_len, BMVert **face_verts, BMEdge **face_edges, int *r_face_verts_len, bool *r_check_face_exists)
KERNEL_FEATURE_LIGHT_PASSES KERNEL_FEATURE_PATH_GUIDING float
struct blender::EdgeGroupIsland::@263354005325326233205312234055326163323057041077 vert_span
struct BMLoop * radial_next