Blender  V3.3
Classes | Macros
bmesh_polygon_edgenet.c File Reference
#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
 

Macros

#define USE_FASTPATH_NOFORK
 
#define EDGE_NOT_IN_STACK   BM_ELEM_INTERNAL_TAG
 
#define VERT_NOT_IN_STACK   BM_ELEM_INTERNAL_TAG
 
#define FOREACH_VERT_EDGE(v_, e_, body_)
 
#define EDGE_NOT_IN_STACK   BM_ELEM_INTERNAL_TAG
 
#define VERT_NOT_IN_STACK   BM_ELEM_INTERNAL_TAG
 
#define VERT_IN_ARRAY   BM_ELEM_INTERNAL_TAG
 

Face Split Edge-Net

BM_face_split_edgenet and helper functions.

Note
Don't use BM_edge_is_wire or BM_edge_is_boundary since we need to take flagged faces into account. Also take care accessing e->l directly.
#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 BMLoopbm_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.

Warning
Currently this risks running out of stack memory (#alloca), likely we'll pass in a memory arena (cleared each use) eventually.
#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 BMEdgetest_edges_isect_2d_vert (const struct EdgeGroup_FindConnection_Args *args, BMVert *v_origin, BMVert *v_other)
 
static BMEdgetest_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 BMVertbm_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)
 

Detailed Description

This file contains functions for splitting faces into isolated regions, defined by connected edges.

Definition in file bmesh_polygon_edgenet.c.

Macro Definition Documentation

◆ EDGE_NET

#define EDGE_NET   _FLAG_WALK

Definition at line 43 of file bmesh_polygon_edgenet.c.

◆ EDGE_NOT_IN_STACK [1/2]

#define EDGE_NOT_IN_STACK   BM_ELEM_INTERNAL_TAG

◆ EDGE_NOT_IN_STACK [2/2]

#define EDGE_NOT_IN_STACK   BM_ELEM_INTERNAL_TAG

◆ FACE_NET

#define FACE_NET   _FLAG_WALK

Definition at line 41 of file bmesh_polygon_edgenet.c.

◆ FOREACH_VERT_EDGE

#define FOREACH_VERT_EDGE (   v_,
  e_,
  body_ 
)
Value:
{ \
BMEdge *e_ = v_->e; \
do { \
body_ \
} while ((e_ = BM_DISK_EDGE_NEXT(e_, v_)) != v_->e); \
} \
((void)0)
#define BM_DISK_EDGE_NEXT(e, v)
Definition: bmesh_class.h:625
SyclQueue void void size_t num_bytes void

◆ SORT_AXIS

#define SORT_AXIS   0

Definition at line 701 of file bmesh_polygon_edgenet.c.

◆ USE_FASTPATH_NOFORK

#define USE_FASTPATH_NOFORK

◆ USE_PARTIAL_CONNECT

#define USE_PARTIAL_CONNECT

Definition at line 696 of file bmesh_polygon_edgenet.c.

◆ VERT_IN_ARRAY

#define VERT_IN_ARRAY   BM_ELEM_INTERNAL_TAG

◆ VERT_IN_QUEUE

#define VERT_IN_QUEUE   _FLAG_WALK_ALT

Definition at line 46 of file bmesh_polygon_edgenet.c.

◆ VERT_IS_VALID

#define VERT_IS_VALID   BM_ELEM_INTERNAL_TAG

Definition at line 698 of file bmesh_polygon_edgenet.c.

◆ VERT_NOT_IN_STACK [1/2]

#define VERT_NOT_IN_STACK   BM_ELEM_INTERNAL_TAG

◆ VERT_NOT_IN_STACK [2/2]

#define VERT_NOT_IN_STACK   BM_ELEM_INTERNAL_TAG

◆ VERT_VISIT

#define VERT_VISIT   _FLAG_WALK

Definition at line 45 of file bmesh_polygon_edgenet.c.

Function Documentation

◆ axis_pt_cmp()

BLI_INLINE int axis_pt_cmp ( const float  pt_a[2],
const float  pt_b[2] 
)

◆ bm_edge_flagged_radial_count()

static uint bm_edge_flagged_radial_count ( BMEdge e)
static

◆ bm_edge_flagged_radial_first()

static BMLoop* bm_edge_flagged_radial_first ( BMEdge e)
static

◆ BM_face_split_edgenet()

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 
)

◆ BM_face_split_edgenet_connect_islands()

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.

  • Check if there are any holes.
  • Connect the holes with edges (if any are found).

Keep the first part fast since it will run very often for edge-nets that have no holes.

Note
Don't use the mem_arena unless we have holes to fill. (avoid thrashing the area when the initial check isn't so intensive on the stack).

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().

◆ bm_face_split_edgenet_find_connection()

static int bm_face_split_edgenet_find_connection ( const struct EdgeGroup_FindConnection_Args args,
BMVert v_origin,
bool  direction_sign 
)
static

Method for finding connection is as follows:

  • Cast a ray along either the positive or negative directions.
  • Take the hit-edge, and cast rays to their vertices checking those rays don't intersect a closer edge.
  • Keep taking the hit-edge and testing its verts until a vertex is found which isn't blocked by an edge.
Note
It's possible none of the verts can be accessed (with self-intersecting lines). In that case there's no right answer (without subdividing edges), so return a fall-back vertex in that case.

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().

◆ bm_face_split_edgenet_find_loop()

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 
)
static

◆ bm_face_split_edgenet_find_loop_pair()

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

◆ bm_face_split_edgenet_find_loop_pair_exists()

static bool bm_face_split_edgenet_find_loop_pair_exists ( BMVert v_init)
static

A reduced version of bm_face_split_edgenet_find_loop_pair that only checks if it would return true.

Note
There is no use in caching resulting edges here, since between this check and running bm_face_split_edgenet_find_loop, the selected edges may have had faces attached.

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().

◆ bm_face_split_edgenet_find_loop_walk()

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

◆ bm_face_split_edgenet_partial_connect()

static BMVert* bm_face_split_edgenet_partial_connect ( BMesh bm,
BMVert v_delimit,
BMFace f 
)
static

◆ bm_vert_partial_connect_check_overlap()

static bool bm_vert_partial_connect_check_overlap ( const int *  remap,
const int  v_a_index,
const int  v_b_index 
)
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().

◆ bvhtree_test_edges_isect_2d_ray_cb()

static void bvhtree_test_edges_isect_2d_ray_cb ( void user_data,
int  index,
const BVHTreeRay ray,
BVHTreeRayHit hit 
)
static

◆ bvhtree_test_edges_isect_2d_vert_cb()

static void bvhtree_test_edges_isect_2d_vert_cb ( void user_data,
int  index,
const BVHTreeRay UNUSEDray,
BVHTreeRayHit hit 
)
static

◆ edge_isect_verts_point_2d()

BLI_INLINE bool edge_isect_verts_point_2d ( const BMEdge e,
const BMVert v_a,
const BMVert v_b,
float  r_isect[2] 
)

◆ group_min_cmp_fn()

static int group_min_cmp_fn ( const void p1,
const void p2 
)
static

◆ normalize_v2_m3_v3v3()

static void normalize_v2_m3_v3v3 ( float  out[2],
const float  axis_mat[3][3],
const float  v1[3],
const float  v2[3] 
)
static

◆ test_edges_isect_2d_ray()

static BMEdge* test_edges_isect_2d_ray ( const struct EdgeGroup_FindConnection_Args args,
BMVert v_origin,
const float  dir[3] 
)
static

◆ test_edges_isect_2d_vert()

static BMEdge* test_edges_isect_2d_vert ( const struct EdgeGroup_FindConnection_Args args,
BMVert v_origin,
BMVert v_other 
)
static

◆ test_tagged_and_notface()

static bool test_tagged_and_notface ( BMEdge e,
void fptr 
)
static

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().