Blender  V3.3
Classes | Macros | Enumerations | Functions
bmesh_intersect.c File Reference
#include "MEM_guardedalloc.h"
#include "BLI_alloca.h"
#include "BLI_math.h"
#include "BLI_memarena.h"
#include "BLI_sort_utils.h"
#include "BLI_utildefines.h"
#include "BLI_linklist_stack.h"
#include "BLI_utildefines_stack.h"
#include "BLI_buffer.h"
#include "BLI_kdopbvh.h"
#include "bmesh.h"
#include "intern/bmesh_private.h"
#include "bmesh_intersect.h"
#include "tools/bmesh_edgesplit.h"
#include "BLI_strict_flags.h"

Go to the source code of this file.

Classes

struct  ISectEpsilon
 
struct  ISectState
 
struct  LinkBase
 
struct  vert_sort_t
 
struct  LoopFilterWrap
 
struct  RaycastData
 

Macros

#define USE_SPLICE
 
#define USE_NET
 
#define USE_SEPARATE
 
#define USE_DISSOLVE
 
#define USE_NET_ISLAND_CONNECT
 
#define USE_BVH
 
#define KEY_SET(k, i0, i1, i2, i3)
 
#define KEY_EDGE_TRI_ORDER(k)
 
#define VERT_VISIT_A   _FLAG_WALK
 
#define VERT_VISIT_B   _FLAG_WALK_ALT
 
#define STACK_PUSH_TEST_A(ele)
 
#define STACK_PUSH_TEST_B(ele)
 

Enumerations

enum  ISectType {
  IX_NONE = -1 , IX_EDGE_TRI_EDGE0 , IX_EDGE_TRI_EDGE1 , IX_EDGE_TRI_EDGE2 ,
  IX_EDGE_TRI , IX_TOT
}
 

Functions

static void tri_v3_scale (float v1[3], float v2[3], float v3[3], const float t)
 
static BMEdgebm_vert_other_edge (BMVert *v, BMEdge *e)
 
static bool ghash_insert_link (GHash *gh, void *key, void *val, bool use_test, MemArena *mem_arena)
 
static void edge_verts_sort (const float co[3], struct LinkBase *v_ls_base)
 
static void edge_verts_add (struct ISectState *s, BMEdge *e, BMVert *v, const bool use_test)
 
static void face_edges_add (struct ISectState *s, const int f_index, BMEdge *e, const bool use_test)
 
static void face_edges_split (BMesh *bm, BMFace *f, struct LinkBase *e_ls_base, bool use_island_connect, bool use_partial_connect, MemArena *mem_arena_edgenet)
 
static void vert_dissolve_add (struct ISectState *s, BMVert *v)
 
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 struct ISectEpsilon *e)
 
static BMVertbm_isect_edge_tri (struct 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)
 
static bool bm_loop_filter_fn (const BMLoop *l, void *user_data)
 
static void bm_isect_tri_tri (struct ISectState *s, int a_index, int b_index, BMLoop **a, BMLoop **b, bool no_shared)
 
static void raycast_callback (void *userdata, int index, const BVHTreeRay *ray, BVHTreeRayHit *UNUSED(hit))
 
static int isect_bvhtree_point_v3 (BVHTree *tree, const float **looptris, const float co[3])
 
bool BM_mesh_intersect (BMesh *bm, struct BMLoop *(*looptris)[3], const int looptris_tot, 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)
 

Detailed Description

Cut meshes along intersections.

Boolean-like modeling operation (without calculating inside/outside).

Supported:

Unsupported:

Definition in file bmesh_intersect.c.

Macro Definition Documentation

◆ KEY_EDGE_TRI_ORDER

#define KEY_EDGE_TRI_ORDER (   k)
Value:
{ \
if (k[2] > k[3]) { \
SWAP(int, k[2], k[3]); \
} \
if (k[0] > k[2]) { \
SWAP(int, k[0], k[2]); \
SWAP(int, k[1], k[3]); \
} \
} \
(void)0
SyclQueue void void size_t num_bytes void

◆ KEY_SET

#define KEY_SET (   k,
  i0,
  i1,
  i2,
  i3 
)
Value:
{ \
(k)[0] = i0; \
(k)[1] = i1; \
(k)[2] = i2; \
(k)[3] = i3; \
} \
(void)0
_GL_VOID GLfloat value _GL_VOID_RET _GL_VOID const GLuint GLboolean *residences _GL_BOOL_RET _GL_VOID GLsizei GLfloat GLfloat GLfloat GLfloat const GLubyte *bitmap _GL_VOID_RET _GL_VOID GLenum const void *lists _GL_VOID_RET _GL_VOID const GLdouble *equation _GL_VOID_RET _GL_VOID GLdouble GLdouble blue _GL_VOID_RET _GL_VOID GLfloat GLfloat blue _GL_VOID_RET _GL_VOID GLint GLint blue _GL_VOID_RET _GL_VOID GLshort GLshort blue _GL_VOID_RET _GL_VOID GLubyte GLubyte blue _GL_VOID_RET _GL_VOID GLuint GLuint blue _GL_VOID_RET _GL_VOID GLushort GLushort blue _GL_VOID_RET _GL_VOID GLbyte GLbyte GLbyte alpha _GL_VOID_RET _GL_VOID GLdouble GLdouble GLdouble alpha _GL_VOID_RET _GL_VOID GLfloat GLfloat GLfloat alpha _GL_VOID_RET _GL_VOID GLint GLint GLint alpha _GL_VOID_RET _GL_VOID GLshort GLshort GLshort alpha _GL_VOID_RET _GL_VOID GLubyte GLubyte GLubyte alpha _GL_VOID_RET _GL_VOID GLuint GLuint GLuint alpha _GL_VOID_RET _GL_VOID GLushort GLushort GLushort alpha _GL_VOID_RET _GL_VOID GLenum mode _GL_VOID_RET _GL_VOID GLint GLsizei GLsizei GLenum type _GL_VOID_RET _GL_VOID GLsizei GLenum GLenum const void *pixels _GL_VOID_RET _GL_VOID const void *pointer _GL_VOID_RET _GL_VOID GLdouble v _GL_VOID_RET _GL_VOID GLfloat v _GL_VOID_RET _GL_VOID GLint i1

◆ STACK_PUSH_TEST_A

#define STACK_PUSH_TEST_A (   ele)
Value:
if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_A) == 0) { \
BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_A); \
STACK_PUSH(iv_ls_a, ele); \
} \
((void)0)
#define VERT_VISIT_A
#define BM_ELEM_API_FLAG_TEST(element, f)
Definition: bmesh_private.h:76

◆ STACK_PUSH_TEST_B

#define STACK_PUSH_TEST_B (   ele)
Value:
if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_B) == 0) { \
BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_B); \
STACK_PUSH(iv_ls_b, ele); \
} \
((void)0)
#define VERT_VISIT_B

◆ USE_BVH

#define USE_BVH

Definition at line 63 of file bmesh_intersect.c.

◆ USE_DISSOLVE

#define USE_DISSOLVE

Definition at line 56 of file bmesh_intersect.c.

◆ USE_NET

#define USE_NET

Definition at line 52 of file bmesh_intersect.c.

◆ USE_NET_ISLAND_CONNECT

#define USE_NET_ISLAND_CONNECT

Definition at line 58 of file bmesh_intersect.c.

◆ USE_SEPARATE

#define USE_SEPARATE

Definition at line 54 of file bmesh_intersect.c.

◆ USE_SPLICE

#define USE_SPLICE

Definition at line 50 of file bmesh_intersect.c.

◆ VERT_VISIT_A

#define VERT_VISIT_A   _FLAG_WALK

◆ VERT_VISIT_B

#define VERT_VISIT_B   _FLAG_WALK_ALT

Enumeration Type Documentation

◆ ISectType

enum ISectType
Enumerator
IX_NONE 
IX_EDGE_TRI_EDGE0 
IX_EDGE_TRI_EDGE1 
IX_EDGE_TRI_EDGE2 
IX_EDGE_TRI 
IX_TOT 

Definition at line 92 of file bmesh_intersect.c.

Function Documentation

◆ bm_isect_edge_tri()

static BMVert* bm_isect_edge_tri ( struct 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 
)
static

◆ bm_isect_tri_tri()

static void bm_isect_tri_tri ( struct ISectState s,
int  a_index,
int  b_index,
BMLoop **  a,
BMLoop **  b,
bool  no_shared 
)
static

◆ bm_loop_filter_fn()

static bool bm_loop_filter_fn ( const BMLoop l,
void user_data 
)
static

◆ BM_mesh_intersect()

bool BM_mesh_intersect ( BMesh bm,
struct BMLoop *(*)  looptris[3],
int  looptris_tot,
int(*)(BMFace *f, void *user_data test_fn,
void user_data,
bool  use_self,
bool  use_separate,
bool  use_dissolve,
bool  use_island_connect,
bool  use_partial_connect,
bool  use_edge_tag,
int  boolean_mode,
float  eps 
)

Intersect tessellated faces leaving the resulting edges tagged.

Parameters
test_fnReturn value: -1: skip, 0: tree_a, 1: tree_b (use_self == false)
boolean_mode-1: no-boolean, 0: intersection... see BMESH_ISECT_BOOLEAN_ISECT.
Returns
true if the mesh is changed (intersections cut or faces removed from boolean).

Definition at line 936 of file bmesh_intersect.c.

References BLI_assert, BLI_bvhtree_balance(), BLI_bvhtree_free(), BLI_bvhtree_insert(), BLI_bvhtree_new(), BLI_bvhtree_overlap_ex(), BLI_ghash_free(), BLI_ghash_int_new(), BLI_ghash_len(), BLI_ghash_new(), BLI_ghash_ptr_new(), BLI_ghashIterator_getKey(), BLI_ghashIterator_getValue(), BLI_ghashutil_inthash_v4_cmp, BLI_ghashutil_inthash_v4_p, BLI_gset_add(), BLI_gset_free(), BLI_gset_haskey(), BLI_gset_insert(), BLI_gset_len(), BLI_gset_ptr_new(), BLI_gset_remove(), BLI_gsetIterator_getKey(), BLI_memarena_clear(), BLI_memarena_free(), BLI_memarena_new(), BLI_MEMARENA_STD_BUFSIZE, bm, ISectState::bm, BM_DISK_EDGE_NEXT, BM_EDGE, BM_edge_exists(), BM_edge_kill(), BM_edge_other_vert(), BM_edge_split(), BM_EDGES_OF_MESH, BM_elem_flag_disable, BM_elem_flag_enable, BM_elem_flag_test, BM_elem_index_get, BM_ELEM_TAG, BM_FACE, BM_face_calc_point_in_face(), BM_face_kill_loose(), BM_face_normal_flip(), bm_isect_tri_tri(), BM_ITER_MESH_MUTABLE, bm_loop_filter_fn(), BM_mesh_calc_face_groups(), BM_mesh_edgesplit(), BM_mesh_elem_hflag_disable_all(), BM_mesh_elem_index_ensure(), BM_mesh_elem_table_ensure(), BM_select_history_clear(), BM_VERT, BM_vert_collapse_edge(), BM_vert_in_edge(), BM_vert_is_edge_pair(), BM_vert_kill(), bm_vert_other_edge(), BM_vert_pair_share_face_check(), BM_vert_splice(), BM_vert_splice_check_double(), BMESH_ISECT_BOOLEAN_DIFFERENCE, BMESH_ISECT_BOOLEAN_ISECT, BMESH_ISECT_BOOLEAN_NONE, BMESH_ISECT_BOOLEAN_UNION, BVH_OVERLAP_RETURN_PAIRS, BVH_OVERLAP_USE_THREADING, clamp_f(), BMVert::co, copy_v3_v3(), KDL::cos(), BMVert::e, e, ISectState::edge_verts, edge_verts_sort(), ISectState::edgetri_cache, ELEM, eps, ISectEpsilon::eps, ISectEpsilon::eps2x, ISectEpsilon::eps2x_sq, ISectEpsilon::eps_margin, ISectEpsilon::eps_margin_sq, ISectEpsilon::eps_sq, ISectState::epsilon, BMLoop::f, ISectState::face_edges, face_edges_split(), faces, BMesh::ftable, GHASH_ITER, GSET_ITER, isect_bvhtree_point_v3(), BMEdge::l, BMFace::len, len_squared_v3v3(), line_point_factor_v3(), LinkBase::list, LinkBase::list_len, BMFace::mat_nr, ISectState::mem_arena, MEM_freeN, MEM_mallocN, node, NULL, POINTER_AS_INT, BMLoop::radial_next, STACK_DECLARE, STACK_INIT, STACK_PUSH_RET, STACK_SIZE, SWAP, LoopFilterWrap::test_fn, BMesh::totface, UNLIKELY, UNPACK2, UNPACK3, UNUSED_VARS, UNUSED_VARS_NDEBUG, USE_NET, USE_SPLICE, user_data, v, ISectState::vert_dissolve, void, and ISectState::wire_edges.

Referenced by BMD_mesh_intersection(), edbm_intersect_boolean_exec(), and edbm_intersect_exec().

◆ bm_vert_other_edge()

static BMEdge* bm_vert_other_edge ( BMVert v,
BMEdge e 
)
static

◆ edge_verts_add()

static void edge_verts_add ( struct ISectState s,
BMEdge e,
BMVert v,
const bool  use_test 
)
static

◆ edge_verts_sort()

static void edge_verts_sort ( const float  co[3],
struct LinkBase v_ls_base 
)
static

◆ face_edges_add()

static void face_edges_add ( struct ISectState s,
const int  f_index,
BMEdge e,
const bool  use_test 
)
static

◆ face_edges_split()

static void face_edges_split ( BMesh bm,
BMFace f,
struct LinkBase e_ls_base,
bool  use_island_connect,
bool  use_partial_connect,
MemArena mem_arena_edgenet 
)
static

◆ ghash_insert_link()

static bool ghash_insert_link ( GHash gh,
void key,
void val,
bool  use_test,
MemArena mem_arena 
)
static

◆ intersect_line_tri()

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 struct ISectEpsilon e 
)
static

◆ isect_bvhtree_point_v3()

static int isect_bvhtree_point_v3 ( BVHTree tree,
const float **  looptris,
const float  co[3] 
)
static

◆ raycast_callback()

static void raycast_callback ( void userdata,
int  index,
const BVHTreeRay ray,
BVHTreeRayHit UNUSEDhit 
)
static

◆ tri_v3_scale()

static void tri_v3_scale ( float  v1[3],
float  v2[3],
float  v3[3],
const float  t 
)
static

Definition at line 67 of file bmesh_intersect.c.

References interp_v3_v3v3(), mid_v3_v3v3v3(), t, v1, and v2.

Referenced by bm_isect_tri_tri().

◆ vert_dissolve_add()

static void vert_dissolve_add ( struct ISectState s,
BMVert v 
)
static

Definition at line 251 of file bmesh_intersect.c.

Referenced by bm_isect_edge_tri().