62#define USE_NET_ISLAND_CONNECT
71static void tri_v3_scale(
float v1[3],
float v2[3],
float v3[3],
const float t)
142 ls_base->
list =
nullptr;
146 ls_base =
static_cast<LinkBase *
>(*ls_base_p);
176 for (i = 0,
node = v_ls_base->
list; i < v_ls_base->list_len; i++,
node =
node->next) {
185 for (i = 0,
node = v_ls_base->
list; i < v_ls_base->list_len; i++,
node =
node->next) {
186 node->link = vert_sort[i].v;
212 bool use_island_connect,
213 bool use_partial_connect,
224 for (i = 0,
node = e_ls_base->
list; i < e_ls_base->list_len; i++,
node =
node->next) {
225 edge_arr[i] =
static_cast<BMEdge *
>(
node->link);
233# ifdef USE_NET_ISLAND_CONNECT
234 if (use_island_connect) {
235 uint edge_arr_holes_len;
244 &edge_arr_holes_len))
246 edge_arr_len = edge_arr_holes_len;
247 edge_arr = edge_arr_holes;
251 UNUSED_VARS(use_island_connect, mem_arena_edgenet);
272 const float *t_cos[3],
273 const float t_nor[3],
284 for (i_t0 = 0; i_t0 < 3; i_t0++) {
285 const uint i_t1 = (i_t0 + 1) % 3;
298 p0, p1, t_cos[i_t0], t_cos[i_t1], ix_pair[0], ix_pair[1], 0.0f);
300 if (ix_pair_type != 0) {
301 if (ix_pair_type == 1) {
305 if ((ix_pair_type == 1) || (
len_squared_v3v3(ix_pair[0], ix_pair[1]) <=
e->eps_margin_sq))
308 if ((fac >=
e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
310 if ((fac >=
e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
323 p0, p1, t_cos[0], t_cos[1], t_cos[2], &fac,
nullptr, 0.0f))
325 if ((fac >=
e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
346 const float *t_cos[3],
347 const float t_nor[3],
357 std::swap(e_v0, e_v1);
369#define KEY_SET(k, i0, i1, i2, i3) \
379#define KEY_EDGE_TRI_ORDER(k) \
382 std::swap(k[2], k[3]); \
385 std::swap(k[0], k[2]); \
386 std::swap(k[1], k[3]); \
405#undef KEY_EDGE_TRI_ORDER
416 *r_side =
static_cast<enum
ISectType>(i);
426 printf(
"# new vertex (%.6f, %.6f, %.6f) %d\n",
UNPACK3(ix), *r_side);
461 memcpy(k, k_arr[*r_side],
sizeof(
int[4]));
487 const int face_side =
data->test_fn(
l->
f,
data->user_data);
489 const int face_side_other =
data->test_fn(l_iter->
f,
data->user_data);
490 if (face_side_other == -1) [[unlikely]] {
493 else if (face_side_other != face_side) {
508 const std::array<BMLoop *, 3> &a,
509 const std::array<BMLoop *, 3> &
b,
516 const float *f_a_cos[3] = {
UNPACK3_EX(, fv_a, ->co)};
517 const float *f_b_cos[3] = {
UNPACK3_EX(, fv_b, ->co)};
544#define VERT_VISIT_A _FLAG_WALK
545#define VERT_VISIT_B _FLAG_WALK_ALT
547#define STACK_PUSH_TEST_A(ele) \
548 if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_A) == 0) { \
549 BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_A); \
550 STACK_PUSH(iv_ls_a, ele); \
554#define STACK_PUSH_TEST_B(ele) \
555 if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_B) == 0) { \
556 BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_B); \
557 STACK_PUSH(iv_ls_b, ele); \
568 for (i_a = 0; i_a < 3; i_a++) {
570 for (i_b = 0; i_b < 3; i_b++) {
591 for (i_a = 0; i_a < 3; i_a++) {
594 for (i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) {
595 uint i_b_e1 = (i_b_e0 + 1) % 3;
604 fv_a[i_a]->co, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co);
605 if ((fac > 0.0f - s->
epsilon.
eps) && (fac < 1.0f + s->epsilon.eps)) {
614 printf(
" ('VERT-EDGE-A', %d, %d),\n",
634 for (i_b = 0; i_b < 3; i_b++) {
637 for (i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) {
638 uint i_a_e1 = (i_a_e0 + 1) % 3;
647 fv_b[i_b]->co, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co);
648 if ((fac > 0.0f - s->
epsilon.
eps) && (fac < 1.0f + s->epsilon.eps)) {
657 printf(
" ('VERT-EDGE-B', %d, %d),\n",
688 for (i_a = 0; i_a < 3; i_a++) {
699 printf(
" 'VERT TRI-A',\n");
715 for (i_b = 0; i_b < 3; i_b++) {
726 printf(
" 'VERT TRI-B',\n");
746 for (
uint i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) {
747 uint i_a_e1 = (i_a_e0 + 1) % 3;
758 s, fv_a[i_a_e0], fv_a[i_a_e1], fv_b, b_index, f_b_cos, f_b_nor, &side);
763 printf(
" ('EDGE-TRI-A', %d),\n", side);
768 for (
uint i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) {
769 uint i_b_e1 = (i_b_e0 + 1) % 3;
780 s, fv_b[i_b_e0], fv_b[i_b_e1], fv_a, a_index, f_a_cos, f_a_nor, &side);
785 printf(
" ('EDGE-TRI-B', %d),\n", side);
792 for (i = 0; i < 2; i++) {
855# ifdef USE_KDOPBVH_WATERTIGHT
865 const float **looptris = raycast_data->
looptris;
866 const float *v0 = looptris[
index * 3 + 0];
867 const float *v1 = looptris[
index * 3 + 1];
868 const float *
v2 = looptris[
index * 3 + 2];
882 printf(
"%s:\n", __func__);
885 printf(
" dist %f\n", dist);
892 printf(
"%s: Adding depth %f\n", __func__, dist);
908 const float dir[3] = {1.0f, 0.0f, 0.0f};
920 printf(
"%s: Total intersections: %zu\n", __func__, z_buffer.count);
928 else if (z_buffer.
size() == 1) {
936 std::ranges::sort(z_buffer);
938 const float *depth_arr = z_buffer.
data();
939 float depth_last = depth_arr[0];
941 for (
uint i = 1; i < z_buffer.
size(); i++) {
942 if (depth_arr[i] - depth_last >
eps) {
943 depth_last = depth_arr[i];
956 const Span<std::array<BMLoop *, 3>> looptris,
957 int (*test_fn)(
BMFace *f,
void *user_data),
960 const bool use_separate,
961 const bool use_dissolve,
962 const bool use_island_connect,
963 const bool use_partial_connect,
964 const bool use_edge_tag,
965 const int boolean_mode,
972 bool has_edit_isect =
false, has_edit_boolean =
false;
975 const float **looptri_coords =
nullptr;
979 uint tree_overlap_tot;
992 s.
wire_edges = MEM_new<Set<BMEdge *>>(__func__);
1040 for (i = 0, j = 0; i < int(looptris.size()); i++) {
1041 cos[j++] = looptris[i][0]->v->co;
1042 cos[j++] = looptris[i][1]->v->co;
1043 cos[j++] = looptris[i][2]->v->co;
1045 looptri_coords = (
const float **)
cos;
1052 for (i = 0; i < int(looptris.size()); i++) {
1053 if (test_fn(looptris[i][0]->f, user_data) == 0) {
1054 const float t_cos[3][3] = {
1066 if (use_self ==
false) {
1069 for (i = 0; i < int(looptris.size()); i++) {
1070 if (test_fn(looptris[i][0]->f, user_data) == 1) {
1071 const float t_cos[3][3] = {
1096 if (looptris.size() < 1024) {
1105 for (i = 0; i < tree_overlap_tot; i++) {
1107 printf(
" ((%d, %d), (\n", overlap[i].indexA, overlap[i].indexB);
1112 looptris[overlap[i].indexA],
1113 looptris[overlap[i].indexB],
1114 isect_tri_tri_no_shared);
1119 MEM_delete(overlap);
1125 if (tree_a != tree_b) {
1132 for (i_a = 0; i_a < looptris.size(); i_a++) {
1133 const int t_a = test_fn(looptris[i_a][0]->f, user_data);
1134 for (i_b = i_a + 1; i_b < looptris.size(); i_b++) {
1135 const int t_b = test_fn(looptris[i_b][0]->f, user_data);
1138 if ((t_a != 0) || (t_b != 0)) {
1143 if ((t_a != t_b) && !
ELEM(-1, t_a, t_b)) {
1149 printf(
" ((%d, %d), (", i_a, i_b);
1151 bm_isect_tri_tri(&s, i_a, i_b, looptris[i_a], looptris[i_b], isect_tri_tri_no_shared);
1292 splice_pair[1] = v_b;
1294 printf(
"# Simple Case!\n");
1313 std::swap(v_a, v_b);
1337 splice_pair[1] = v_next;
1349 printf(
"# walk step %p %p\n", e_next, v_next);
1366 node_prev_p = &e_ls_base->
list;
1371 *node_prev_p =
node->next;
1375 node_prev_p = &
node->next;
1402 faces[f_index] =
nullptr;
1422 verts_invalid.
add(
v);
1430 for (i = 0; i <
STACK_SIZE(splice_ls); i++) {
1431 if (!verts_invalid.
contains(splice_ls[i][0]) && !verts_invalid.
contains(splice_ls[i][1]))
1444 MEM_delete(splice_ls);
1463 BLI_assert(f_index >= 0 && f_index < totface_orig);
1466 if (f ==
nullptr) [[unlikely]] {
1473 bm, f, e_ls_base, use_island_connect, use_partial_connect, mem_arena_edgenet);
1506 BVHTree *tree_pair[2] = {tree_a, tree_b};
1510 int (*group_index)[2];
1520 user_data_wrap.
test_fn = test_fn;
1528 printf(
"%s: Total face-groups: %d\n", __func__, group_tot);
1532 for (i = 0; i < group_tot; i++) {
1533 int fg = group_index[i][0];
1534 int fg_end = group_index[i][1] + fg;
1535 bool do_remove, do_flip;
1539 BMFace *f = ftable[groups_array[fg]];
1542 int side = test_fn(f, user_data);
1555 switch (boolean_mode) {
1557 do_remove = ((hits & 1) != 1);
1561 do_remove = ((hits & 1) == 1);
1565 do_remove = ((hits & 1) == 1) == side;
1566 do_flip = (side == 0);
1572 for (; fg != fg_end; fg++) {
1575 ftable[groups_array[fg]]->
mat_nr = -1;
1579 for (; fg != fg_end; fg++) {
1584 has_edit_boolean |= (do_flip || do_remove);
1587 MEM_delete(groups_array);
1588 MEM_delete(group_index);
1606 if (l_iter->
f->
len == 3) {
1634 for (i = 0; i < tot; i++) {
1635 if (ftable[i]->mat_nr == -1) {
1643 MEM_delete(looptri_coords);
1647 if (tree_a != tree_b) {
1667 return (has_edit_isect || has_edit_boolean);
#define BLI_ghashutil_inthash_v4_cmp
#define GHASH_ITER(gh_iter_, ghash_)
#define BLI_ghashutil_inthash_v4_p
#define BVH_RAYCAST_DIST_MAX
#define USE_KDOPBVH_WATERTIGHT
#define BLI_MEMARENA_STD_BUFSIZE
#define STACK_DECLARE(stack)
#define STACK_SIZE(stack)
#define STACK_INIT(stack, stack_num)
#define STACK_PUSH_RET(stack)
Read Blender memory allocation and freeing.
#define UNPACK3_EX(pre, a, post)
#define POINTER_FROM_INT(i)
#define UNUSED_VARS_NDEBUG(...)
#define POINTER_AS_INT(i)
#define BM_DISK_EDGE_NEXT(e, v)
#define BM_elem_index_get(ele)
#define BM_elem_flag_disable(ele, hflag)
#define BM_elem_flag_test(ele, hflag)
#define BM_elem_flag_enable(ele, hflag)
#define KEY_EDGE_TRI_ORDER(k)
#define KEY_SET(k, i0, i1, i2, i3)
#define STACK_PUSH_TEST_B(ele)
#define STACK_PUSH_TEST_A(ele)
#define BM_ITER_MESH_MUTABLE(ele, ele_next, iter, bm, itype)
#define BM_ELEM_API_FLAG_DISABLE(element, f)
#define BM_ELEM_API_FLAG_TEST(element, f)
bool contains(const Key &key) const
void append(const T &value)
static enum ISectType intersect_line_tri(const float p0[3], const float p1[3], const float *t_cos[3], const float t_nor[3], float r_ix[3], const ISectEpsilon *e)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
MINLINE float len_squared_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
bool isect_point_tri_v3(const float p[3], const float v1[3], const float v2[3], const float v3[3], float r_isect_co[3])
BVHTreeOverlap * BLI_bvhtree_overlap_ex(const BVHTree *tree1, const BVHTree *tree2, uint *r_overlap_num, BVHTree_OverlapCallback callback, void *userdata, uint max_interactions, int flag)
void BM_mesh_elem_index_ensure(BMesh *bm, const char htype)
float line_point_factor_v3(const float p[3], const float l1[3], const float l2[3])
BLI_INLINE void * BLI_ghashIterator_getKey(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
int isect_line_line_epsilon_v3(const float v1[3], const float v2[3], const float v3[3], const float v4[3], float r_i1[3], float r_i2[3], float epsilon)
bool BM_edge_in_face(const BMEdge *e, const BMFace *f)
MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
GHash * BLI_ghash_int_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
static void bm_isect_tri_tri(ISectState *s, int a_index, int b_index, const std::array< BMLoop *, 3 > &a, const std::array< BMLoop *, 3 > &b, bool no_shared)
void BM_face_normal_flip(BMesh *bm, BMFace *f)
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
ATTR_WARN_UNUSED_RESULT const BMLoop * l
void BM_mesh_elem_table_ensure(BMesh *bm, const char htype)
bool isect_ray_tri_watertight_v3(const float ray_origin[3], const struct IsectRayPrecalc *isect_precalc, const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2])
void BM_vert_kill(BMesh *bm, BMVert *v)
void mid_v3_v3v3v3(float v[3], const float v1[3], const float v2[3], const float v3[3])
void * BLI_ghash_lookup(const GHash *gh, const void *key) ATTR_WARN_UNUSED_RESULT
void BLI_bvhtree_free(BVHTree *tree)
void BLI_bvhtree_balance(BVHTree *tree)
void BLI_linklist_prepend_arena(LinkNode **listp, void *ptr, struct MemArena *ma) ATTR_NONNULL(1
void BM_mesh_elem_hflag_disable_all(BMesh *bm, const char htype, const char hflag, const bool respecthide)
ATTR_WARN_UNUSED_RESULT const BMVert * v
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.
float normal_tri_v3(float n[3], const float v1[3], const float v2[3], const float v3[3])
int BLI_bvhtree_ray_cast(const BVHTree *tree, const float co[3], const float dir[3], float radius, BVHTreeRayHit *hit, BVHTree_RayCastCallback callback, void *userdata)
void print_v3(const char *str, const float v[3])
static void raycast_callback(void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *)
BLI_INLINE bool BM_vert_in_edge(const BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
BLI_INLINE BMVert * BM_edge_other_vert(BMEdge *e, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL()
void BLI_ghash_insert(GHash *gh, void *key, void *val)
BLI_INLINE void * BLI_ghashIterator_getValue(GHashIterator *ghi) ATTR_WARN_UNUSED_RESULT
bool BM_face_share_edge_check(BMFace *f_a, BMFace *f_b)
int BLI_linklist_index(const LinkNode *list, const void *ptr) ATTR_WARN_UNUSED_RESULT
static void edge_verts_add(ISectState *s, BMEdge *e, BMVert *v, const bool use_test)
void BLI_ghash_free(GHash *gh, GHashKeyFreeFP keyfreefp, GHashValFreeFP valfreefp)
void BM_edge_kill(BMesh *bm, BMEdge *e)
BMesh const char void * data
bool BM_mesh_intersect(BMesh *bm, const Span< std::array< BMLoop *, 3 > > looptris, int(*test_fn)(BMFace *f, void *user_data), void *user_data, const bool use_self, const bool use_separate, const bool use_dissolve, const bool use_island_connect, const bool use_partial_connect, const bool use_edge_tag, const int boolean_mode, const float eps)
bool BLI_ghash_ensure_p(GHash *gh, void *key, void ***r_val) ATTR_WARN_UNUSED_RESULT
void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
static void edge_verts_sort(const float co[3], LinkBase *v_ls_base)
BVHTree * BLI_bvhtree_new(int maxsize, float epsilon, char tree_type, char axis)
@ BMESH_ISECT_BOOLEAN_NONE
@ BMESH_ISECT_BOOLEAN_DIFFERENCE
@ BMESH_ISECT_BOOLEAN_UNION
@ BMESH_ISECT_BOOLEAN_ISECT
bool BM_vert_pair_share_face_check(BMVert *v_a, BMVert *v_b)
constexpr size_t ARRAY_SIZE(const T(&arg)[N]) noexcept
static BMVert * bm_isect_edge_tri(ISectState *s, BMVert *e_v0, BMVert *e_v1, BMVert *t[3], const int t_index, const float *t_cos[3], const float t_nor[3], enum ISectType *r_side)
GHash * BLI_ghash_ptr_new(const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
void BM_face_kill_loose(BMesh *bm, BMFace *f)
bool BM_vert_splice(BMesh *bm, BMVert *v_dst, BMVert *v_src)
Splice Vert.
void interp_v3_v3v3(float r[3], const float a[3], const float b[3], float t)
static void tri_v3_scale(float v1[3], float v2[3], float v3[3], const float t)
unsigned int BLI_ghash_len(const GHash *gh) ATTR_WARN_UNUSED_RESULT
@ BVH_OVERLAP_USE_THREADING
@ BVH_OVERLAP_RETURN_PAIRS
static bool ghash_insert_link(GHash *gh, void *key, void *val, bool use_test, MemArena *mem_arena)
void BM_face_calc_point_in_face(const BMFace *f, float r_co[3])
BMEdge * BM_vert_collapse_edge(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, const bool kill_degenerate_faces, const bool kill_duplicate_faces)
Vert Collapse Faces.
bool BM_vert_splice_check_double_edge(BMVert *v_a, BMVert *v_b)
static bool bm_loop_filter_fn(const BMLoop *l, void *user_data)
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)
MINLINE float normalize_v3(float n[3])
static int isect_bvhtree_point_v3(BVHTree *tree, const float **looptris, const float co[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.
bool isect_line_segment_tri_epsilon_v3(const float p1[3], const float p2[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2], float epsilon)
ATTR_WARN_UNUSED_RESULT const BMVert * v2
static void vert_dissolve_add(ISectState *s, BMVert *v)
int BM_mesh_calc_face_groups(BMesh *bm, int *r_groups_array, int(**r_group_index)[2], BMLoopFilterFunc filter_fn, BMLoopPairFilterFunc filter_pair_fn, void *user_data, const char hflag_test, const char htype_step)
void BM_mesh_edgesplit(BMesh *bm, const bool use_verts, const bool tag_only, const bool copy_select)
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)
bool BM_vert_is_edge_pair(const BMVert *v)
void BLI_bvhtree_insert(BVHTree *tree, int index, const float co[3], int numpoints)
bool BM_face_split_edgenet(BMesh *bm, BMFace *f, BMEdge **edge_net, const int edge_net_len, Vector< BMFace * > *r_face_arr)
static BMEdge * bm_vert_other_edge(BMVert *v, BMEdge *e)
void BM_select_history_clear(BMesh *bm)
bool BM_vert_splice_check_double_face(BMVert *v_a, BMVert *v_b)
bool isect_ray_tri_epsilon_v3(const float ray_origin[3], const float ray_direction[3], const float v0[3], const float v1[3], const float v2[3], float *r_lambda, float r_uv[2], float epsilon)
bool BM_vert_collapse_check_double_face(BMVert *v_collapse)
GHash * BLI_ghash_new(GHashHashFP hashfp, GHashCmpFP cmpfp, const char *info) ATTR_MALLOC ATTR_WARN_UNUSED_RESULT
MINLINE float dot_v3v3(const float a[3], const float b[3]) ATTR_WARN_UNUSED_RESULT
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.
static void face_edges_split(BMesh *bm, BMFace *f, LinkBase *e_ls_base, bool use_island_connect, bool use_partial_connect, MemArena *mem_arena_edgenet)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
void BLI_memarena_free(MemArena *ma) ATTR_NONNULL(1)
static void face_edges_add(ISectState *s, const int f_index, BMEdge *e, const bool use_test)
MINLINE float clamp_f(float value, float min, float max)
struct BMLoop * radial_next
Set< BMEdge * > * wire_edges
int(*) test_fn(BMFace *f, void *user_data)
Vector< float, 64 > * z_buffer
struct BMLoop * radial_next