Blender
V3.3
|
#include "MEM_guardedalloc.h"
#include "BLI_alloca.h"
#include "BLI_array.h"
#include "BLI_kdopbvh.h"
#include "BLI_linklist_stack.h"
#include "BLI_math.h"
#include "BLI_memarena.h"
#include "BLI_sort_utils.h"
#include "BLI_utildefines_stack.h"
#include "BKE_customdata.h"
#include "bmesh.h"
#include "intern/bmesh_private.h"
Go to the source code of this file.
Classes | |
struct | VertOrder |
struct | EdgeGroupIsland |
struct | Edges_VertVert_BVHTreeTest |
struct | Edges_VertRay_BVHTreeTest |
struct | EdgeGroup_FindConnection_Args |
Face Split Edge-Net | |
BM_face_split_edgenet and helper functions.
| |
#define | FACE_NET _FLAG_WALK |
#define | EDGE_NET _FLAG_WALK |
#define | VERT_VISIT _FLAG_WALK |
#define | VERT_IN_QUEUE _FLAG_WALK_ALT |
static uint | bm_edge_flagged_radial_count (BMEdge *e) |
static BMLoop * | bm_edge_flagged_radial_first (BMEdge *e) |
static void | normalize_v2_m3_v3v3 (float out[2], const float axis_mat[3][3], const float v1[3], const float v2[3]) |
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]) |
static bool | bm_face_split_edgenet_find_loop_pair_exists (BMVert *v_init) |
static bool | bm_face_split_edgenet_find_loop_walk (BMVert *v_init, const float face_normal[3], struct VertOrder *edge_order, const uint edge_order_len, BMEdge *e_pair[2]) |
static bool | bm_face_split_edgenet_find_loop (BMVert *v_init, const float face_normal[3], const float face_normal_matrix[3][3], struct VertOrder *edge_order, const uint edge_order_len, BMVert **r_face_verts, int *r_face_verts_len) |
bool | BM_face_split_edgenet (BMesh *bm, BMFace *f, BMEdge **edge_net, const int edge_net_len, BMFace ***r_face_arr, int *r_face_arr_len) |
Face Split Edge-Net Connect Islands | |
BM_face_split_edgenet_connect_islands and helper functions. Connect isolated mesh 'islands' so they form legal regions from which we can create faces. Intended to be used as a pre-processing step for BM_face_split_edgenet.
| |
#define | USE_PARTIAL_CONNECT |
#define | VERT_IS_VALID BM_ELEM_INTERNAL_TAG |
#define | SORT_AXIS 0 |
BLI_INLINE bool | edge_isect_verts_point_2d (const BMEdge *e, const BMVert *v_a, const BMVert *v_b, float r_isect[2]) |
BLI_INLINE int | axis_pt_cmp (const float pt_a[2], const float pt_b[2]) |
static int | group_min_cmp_fn (const void *p1, const void *p2) |
static void | bvhtree_test_edges_isect_2d_vert_cb (void *user_data, int index, const BVHTreeRay *UNUSED(ray), BVHTreeRayHit *hit) |
static void | bvhtree_test_edges_isect_2d_ray_cb (void *user_data, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit) |
static BMEdge * | test_edges_isect_2d_vert (const struct EdgeGroup_FindConnection_Args *args, BMVert *v_origin, BMVert *v_other) |
static BMEdge * | test_edges_isect_2d_ray (const struct EdgeGroup_FindConnection_Args *args, BMVert *v_origin, const float dir[3]) |
static int | bm_face_split_edgenet_find_connection (const struct EdgeGroup_FindConnection_Args *args, BMVert *v_origin, bool direction_sign) |
static bool | test_tagged_and_notface (BMEdge *e, void *fptr) |
static BMVert * | bm_face_split_edgenet_partial_connect (BMesh *bm, BMVert *v_delimit, BMFace *f) |
static bool | bm_vert_partial_connect_check_overlap (const int *remap, const int v_a_index, const int v_b_index) |
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) |
This file contains functions for splitting faces into isolated regions, defined by connected edges.
Definition in file bmesh_polygon_edgenet.c.
#define EDGE_NET _FLAG_WALK |
Definition at line 43 of file bmesh_polygon_edgenet.c.
#define EDGE_NOT_IN_STACK BM_ELEM_INTERNAL_TAG |
#define EDGE_NOT_IN_STACK BM_ELEM_INTERNAL_TAG |
#define FACE_NET _FLAG_WALK |
Definition at line 41 of file bmesh_polygon_edgenet.c.
#define FOREACH_VERT_EDGE | ( | v_, | |
e_, | |||
body_ | |||
) |
#define SORT_AXIS 0 |
Definition at line 701 of file bmesh_polygon_edgenet.c.
#define USE_FASTPATH_NOFORK |
#define USE_PARTIAL_CONNECT |
Definition at line 696 of file bmesh_polygon_edgenet.c.
#define VERT_IN_ARRAY BM_ELEM_INTERNAL_TAG |
#define VERT_IN_QUEUE _FLAG_WALK_ALT |
Definition at line 46 of file bmesh_polygon_edgenet.c.
#define VERT_IS_VALID BM_ELEM_INTERNAL_TAG |
Definition at line 698 of file bmesh_polygon_edgenet.c.
#define VERT_NOT_IN_STACK BM_ELEM_INTERNAL_TAG |
#define VERT_NOT_IN_STACK BM_ELEM_INTERNAL_TAG |
#define VERT_VISIT _FLAG_WALK |
Definition at line 45 of file bmesh_polygon_edgenet.c.
BLI_INLINE int axis_pt_cmp | ( | const float | pt_a[2], |
const float | pt_b[2] | ||
) |
Definition at line 716 of file bmesh_polygon_edgenet.c.
Referenced by BM_face_split_edgenet_connect_islands(), and group_min_cmp_fn().
Definition at line 53 of file bmesh_polygon_edgenet.c.
References BM_ELEM_API_FLAG_TEST, count, e, BMLoop::f, FACE_NET, l, and BMLoop::radial_next.
Referenced by bm_face_split_edgenet_find_loop(), bm_face_split_edgenet_find_loop_pair(), bm_face_split_edgenet_find_loop_pair_exists(), and bm_face_split_edgenet_find_loop_walk().
Definition at line 68 of file bmesh_polygon_edgenet.c.
References BM_ELEM_API_FLAG_TEST, e, BMLoop::f, FACE_NET, l, NULL, and BMLoop::radial_next.
Referenced by bm_face_split_edgenet_find_loop_pair().
bool BM_face_split_edgenet | ( | BMesh * | bm, |
BMFace * | f, | ||
BMEdge ** | edge_net, | ||
int | edge_net_len, | ||
BMFace *** | r_face_arr, | ||
int * | r_face_arr_len | ||
) |
Splits a face into many smaller faces defined by an edge-net. handle customdata and degenerate cases.
Definition at line 441 of file bmesh_polygon_edgenet.c.
References axis_dominant_v3_to_m3(), BLI_array_alloca, BLI_array_append, BLI_array_declare, BLI_array_len, BLI_assert, bm, BM_CREATE_NOP, BM_edge_in_face(), BM_ELEM_API_FLAG_DISABLE, BM_ELEM_API_FLAG_ENABLE, BM_ELEM_API_FLAG_TEST, BM_ELEM_SELECT, BM_face_create_verts(), BM_FACE_FIRST_LOOP, BM_face_kill(), bm_face_split_edgenet_find_loop(), bm_face_split_edgenet_find_loop_pair_exists(), BM_ITER_ELEM, BM_LOOPS_OF_VERT, BM_VERTS_OF_EDGE, bmesh_face_swap_data(), BMVert::co, copy_v3_v3(), CustomData_bmesh_copy_data(), CustomData_bmesh_interp(), CustomData_has_math(), BMHeader::data, BMLoop::e, EDGE_NET, BMLoop::f, FACE_NET, float(), BMLoop::head, BMFace::head, BMHeader::hflag, interp_weights_poly_v2(), BMesh::ldata, BMFace::len, MEM_freeN, MEM_mallocN, mul_v2_m3v3(), BMLoop::next, BMFace::no, NULL, STACK_DECLARE, STACK_INIT, STACK_POP, STACK_PUSH, BMesh::totfacesel, BMLoop::v, v, v1, v2, VERT_IN_QUEUE, VERT_VISIT, and w().
Referenced by bm_face_split_by_edges(), bm_face_split_by_edges_island_connect(), BM_mesh_intersect_edges(), bpy_bm_utils_face_split_edgenet(), face_edges_split(), and knife_make_face_cuts().
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 | ||
) |
This function has 2 main parts.
Keep the first part fast since it will run very often for edge-nets that have no holes.
Definition at line 1204 of file bmesh_polygon_edgenet.c.
References axis_dominant_v3_to_m3(), axis_pt_cmp(), BLI_assert, BLI_bvhtree_balance(), BLI_bvhtree_free(), BLI_bvhtree_insert(), BLI_bvhtree_new(), BLI_linklist_prepend_arena(), BLI_linklist_prepend_nlink(), BLI_memarena_alloc(), BLI_SMALLSTACK_DECLARE, BLI_SMALLSTACK_POP, BLI_SMALLSTACK_PUSH, bm, BM_DISK_EDGE_NEXT, BM_EDGE, BM_edge_create(), BM_edge_exists(), BM_edge_find_double(), BM_edge_kill(), BM_edge_other_vert(), BM_elem_flag_disable, BM_elem_flag_enable, BM_elem_flag_test, BM_elem_index_get, BM_elem_index_set, BM_FACE_FIRST_LOOP, bm_face_split_edgenet_find_connection(), bm_face_split_edgenet_partial_connect(), BM_VERT, bm_vert_partial_connect_check_overlap(), BM_vert_splice(), EdgeGroup_FindConnection_Args::bvhtree, BMVert::co, copy_v2_v2(), copy_v3_v3(), copy_vn_i(), dot_m3_v3_row_x(), dot_m3_v3_row_y(), BMVert::e, BMLoop::e, e, Edges_VertRay_BVHTreeTest::edge_arr, EdgeGroup_FindConnection_Args::edge_arr, EdgeGroup_FindConnection_Args::edge_arr_len, EdgeGroup_FindConnection_Args::edge_arr_new_len, EdgeGroupIsland::edge_links, EDGE_NOT_IN_STACK, BMesh::elem_index_dirty, float(), usdtokens::g(), group_min_cmp_fn(), EdgeGroupIsland::has_prev_edge, BMVert::head, BMHeader::htype, BMFace::len, len, LinkNode::link, EdgeGroupIsland::max_axis, mem_arena, min_axis(), mul_v2_m3v3(), LinkNode::next, BMLoop::next, next, BMFace::no, NULL, sub_v3_v3(), UNLIKELY, UNPACK2, UNPACK3, BMLoop::v, v, BMEdge::v1, v1, v2, VERT_IN_ARRAY, EdgeGroupIsland::vert_len, VERT_NOT_IN_STACK, and EdgeGroup_FindConnection_Args::vert_range.
Referenced by bm_face_split_by_edges_island_connect(), face_edges_split(), and knife_make_face_cuts().
|
static |
Method for finding connection is as follows:
Definition at line 964 of file bmesh_polygon_edgenet.c.
References ARRAY_SET_ITEMS, BLI_SMALLSTACK_DECLARE, BLI_SMALLSTACK_POP, BLI_SMALLSTACK_PUSH, BM_elem_flag_disable, BM_elem_flag_enable, BM_elem_flag_test, BM_elem_index_get, BMVert::co, len_squared_v2v2(), NULL, SORT_AXIS, test_edges_isect_2d_ray(), test_edges_isect_2d_vert(), v, BMEdge::v1, BMEdge::v2, Edges_VertRay_BVHTreeTest::v_origin, and VERT_IS_VALID.
Referenced by BM_face_split_edgenet_connect_islands().
|
static |
Definition at line 407 of file bmesh_polygon_edgenet.c.
References BLI_assert, bm_edge_flagged_radial_count(), BM_edge_other_vert(), bm_face_split_edgenet_find_loop_pair(), bm_face_split_edgenet_find_loop_walk(), BMVert::e, and v.
Referenced by BM_face_split_edgenet().
|
static |
Definition at line 97 of file bmesh_polygon_edgenet.c.
References BLI_SMALLSTACK_DECLARE, BLI_SMALLSTACK_IS_EMPTY, BLI_SMALLSTACK_POP, BLI_SMALLSTACK_PUSH, BLI_SMALLSTACK_SWAP, BM_DISK_EDGE_NEXT, bm_edge_flagged_radial_count(), bm_edge_flagged_radial_first(), BM_edge_other_vert(), BM_ELEM_API_FLAG_TEST, BMVert::co, count, dot_v2v2(), BMVert::e, e, EDGE_NET, BMLoop::f, BMFace::no, normalize_v2_m3_v3v3(), swap(), SWAP, and BMLoop::v.
Referenced by bm_face_split_edgenet_find_loop().
A reduced version of bm_face_split_edgenet_find_loop_pair that only checks if it would return true.
Definition at line 214 of file bmesh_polygon_edgenet.c.
References BM_DISK_EDGE_NEXT, bm_edge_flagged_radial_count(), BM_ELEM_API_FLAG_TEST, count, BMVert::e, e, and EDGE_NET.
Referenced by BM_face_split_edgenet().
|
static |
Definition at line 257 of file bmesh_polygon_edgenet.c.
References VertOrder::angle, angle_signed_on_axis_v3v3v3_v3(), BLI_assert, BLI_SMALLSTACK_DECLARE, BLI_SMALLSTACK_IS_EMPTY, BLI_SMALLSTACK_POP, BLI_SMALLSTACK_POP_EX, BLI_SMALLSTACK_PUSH, BLI_SMALLSTACK_SWAP, BLI_sortutil_cmp_float_reverse(), BM_DISK_EDGE_NEXT, bm_edge_flagged_radial_count(), BM_edge_other_vert(), BM_ELEM_API_FLAG_DISABLE, BM_ELEM_API_FLAG_ENABLE, BM_ELEM_API_FLAG_TEST, BM_elem_index_get, BMVert::co, BMVert::e, EDGE_NET, STACK_DECLARE, STACK_INIT, STACK_POP_PTR, STACK_PUSH_RET_PTR, STACK_SIZE, VertOrder::v, v, and VERT_VISIT.
Referenced by bm_face_split_edgenet_find_loop().
|
static |
Split vertices which are part of a partial connection (only a single vertex connecting an island).
Definition at line 1061 of file bmesh_polygon_edgenet.c.
References BLI_assert, BLI_linklist_prepend_alloca, BLI_SMALLSTACK_DECLARE, BLI_SMALLSTACK_POP, BLI_SMALLSTACK_PUSH, bm, BM_DISK_EDGE_NEXT, BM_edge_in_face(), BM_edge_other_vert(), BM_elem_flag_disable, BM_elem_flag_enable, BM_elem_flag_test, BM_vert_create(), BM_vert_kill(), BM_vert_separate_tested_edges(), BMVert::co, BMVert::e, EDGE_NOT_IN_STACK, FOREACH_VERT_EDGE, LIKELY, LinkNode::link, LinkNode::next, NULL, test_tagged_and_notface(), UNLIKELY, and VERT_NOT_IN_STACK.
Referenced by BM_face_split_edgenet_connect_islands().
|
static |
Check if connecting vertices would cause an edge with duplicate verts.
Definition at line 1191 of file bmesh_polygon_edgenet.c.
References UNLIKELY.
Referenced by BM_face_split_edgenet_connect_islands().
|
static |
Definition at line 814 of file bmesh_polygon_edgenet.c.
References BM_elem_index_get, BMVert::co, data, BVHTreeRay::direction, BVHTreeRayHit::dist, e, BVHTreeRayHit::index, isect_ray_seg_v2(), LIKELY, NULL, and user_data.
Referenced by test_edges_isect_2d_ray().
|
static |
Definition at line 788 of file bmesh_polygon_edgenet.c.
References BM_elem_index_get, data, BVHTreeRayHit::dist, e, edge_isect_verts_point_2d(), BVHTreeRayHit::index, LIKELY, line_point_factor_v2(), t, and user_data.
Referenced by test_edges_isect_2d_vert().
BLI_INLINE bool edge_isect_verts_point_2d | ( | const BMEdge * | e, |
const BMVert * | v_a, | ||
const BMVert * | v_b, | ||
float | r_isect[2] | ||
) |
Definition at line 703 of file bmesh_polygon_edgenet.c.
References BMVert::co, e, and isect_seg_seg_v2_point_ex().
Referenced by bvhtree_test_edges_isect_2d_vert_cb(), and test_edges_isect_2d_vert().
Definition at line 758 of file bmesh_polygon_edgenet.c.
References axis_pt_cmp(), EdgeGroupIsland::max_axis, EdgeGroupIsland::min_axis, UNLIKELY, and EdgeGroupIsland::vert_span.
Referenced by BM_face_split_edgenet_connect_islands().
|
static |
Definition at line 82 of file bmesh_polygon_edgenet.c.
References mul_v2_m3v3(), normalize_v2(), usdtokens::out(), sub_v3_v3v3(), v1, and v2.
Referenced by bm_face_split_edgenet_find_loop_pair().
|
static |
Similar to test_edges_isect_2d_vert but we're casting into a direction, (not to a vertex)
Definition at line 915 of file bmesh_polygon_edgenet.c.
References BLI_ASSERT_UNIT_V2, BLI_bvhtree_ray_cast_ex(), BVH_RAYCAST_DIST_MAX, EdgeGroup_FindConnection_Args::bvhtree, bvhtree_test_edges_isect_2d_ray_cb(), BMVert::co, BVHTreeRayHit::dist, e, EdgeGroup_FindConnection_Args::edge_arr, EdgeGroup_FindConnection_Args::edge_arr_new, EdgeGroup_FindConnection_Args::edge_arr_new_len, if(), BVHTreeRayHit::index, isect_ray_seg_v2(), LIKELY, NULL, user_data, Edges_VertRay_BVHTreeTest::v_origin, and EdgeGroup_FindConnection_Args::vert_range.
Referenced by bm_face_split_edgenet_find_connection().
|
static |
Definition at line 859 of file bmesh_polygon_edgenet.c.
References BLI_bvhtree_ray_cast_ex(), EdgeGroup_FindConnection_Args::bvhtree, bvhtree_test_edges_isect_2d_vert_cb(), BMVert::co, BVHTreeRayHit::dist, EdgeGroup_FindConnection_Args::edge_arr, EdgeGroup_FindConnection_Args::edge_arr_new, EdgeGroup_FindConnection_Args::edge_arr_new_len, edge_isect_verts_point_2d(), if(), BVHTreeRayHit::index, LIKELY, line_point_factor_v2(), normalize_v2(), NULL, sub_v2_v2v2(), UNLIKELY, user_data, Edges_VertVert_BVHTreeTest::v_origin, Edges_VertVert_BVHTreeTest::v_other, and EdgeGroup_FindConnection_Args::vert_range.
Referenced by bm_face_split_edgenet_find_connection().
Support for connecting islands that have single-edge connections. This options is not very optimal (however its not needed for booleans either). Used to identify edges that get split off when making island from partial connection. fptr should be a BMFace*, but is a void* for general interface to BM_vert_separate_tested_edges
Definition at line 1048 of file bmesh_polygon_edgenet.c.
References BM_edge_in_face(), BM_elem_flag_test, BM_ELEM_INTERNAL_TAG, and e.
Referenced by bm_face_split_edgenet_partial_connect().