#include "MEM_guardedalloc.h"
#include "BLI_alloca.h"
#include "BLI_math_geom.h"
#include "BLI_math_vector.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.hh"
#include "intern/bmesh_private.hh"
#include "bmesh_intersect.hh"
#include "tools/bmesh_edgesplit.hh"
#include "BLI_strict_flags.h"

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 BMEdge *	bm_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], LinkBase *v_ls_base)

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

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

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)

static void	vert_dissolve_add (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 ISectEpsilon e)

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)

static bool	bm_loop_filter_fn (const BMLoop l, void user_data)

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)

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

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

bool	BM_mesh_intersect (BMesh bm, const blender::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)

Detailed Description

Cut meshes along intersections.

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

Supported:

Concave faces.
Non-planar faces.
Custom-data (UVs etc).

Unsupported:

Intersecting between different meshes.
No support for holes (cutting a hole into a single face).

Definition in file bmesh_intersect.cc.

Macro Definition Documentation

◆ KEY_EDGE_TRI_ORDER

#define KEY_EDGE_TRI_ORDER ( k )

Value:

  { \
    if (k[2] > k[3]) { \
      std::swap(k[2], k[3]); \
    } \
    if (k[0] > k[2]) { \
      std::swap(k[0], k[2]); \
      std::swap(k[1], k[3]); \
    } \
  } \
  (void)0

Referenced by bm_isect_edge_tri().

◆ 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

Referenced by bm_isect_edge_tri().

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

Referenced by bm_isect_tri_tri().

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

Referenced by bm_isect_tri_tri().

◆ USE_BVH

#define USE_BVH

Definition at line 64 of file bmesh_intersect.cc.

◆ USE_DISSOLVE

#define USE_DISSOLVE

Definition at line 57 of file bmesh_intersect.cc.

◆ USE_NET

#define USE_NET

Definition at line 53 of file bmesh_intersect.cc.

Referenced by BM_mesh_intersect().

◆ USE_NET_ISLAND_CONNECT

#define USE_NET_ISLAND_CONNECT

Definition at line 59 of file bmesh_intersect.cc.

◆ USE_SEPARATE

#define USE_SEPARATE

Definition at line 55 of file bmesh_intersect.cc.

◆ USE_SPLICE

#define USE_SPLICE

Definition at line 51 of file bmesh_intersect.cc.

Referenced by BM_mesh_intersect().

◆ VERT_VISIT_A

#define VERT_VISIT_A _FLAG_WALK

Referenced by bm_isect_tri_tri().

◆ VERT_VISIT_B

#define VERT_VISIT_B _FLAG_WALK_ALT

Referenced by bm_isect_tri_tri().

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 93 of file bmesh_intersect.cc.

Function Documentation

◆ bm_isect_edge_tri()

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 )

static

Definition at line 336 of file bmesh_intersect.cc.

References ARRAY_SIZE, BLI_assert, BLI_ghash_insert(), BLI_ghash_lookup(), BLI_memarena_alloc(), bm, BM_edge_exists(), BM_elem_index_get, BM_vert_create(), BMVert::co, e, edge_verts_add(), intersect_line_tri(), IX_EDGE_TRI, IX_EDGE_TRI_EDGE0, IX_EDGE_TRI_EDGE1, IX_EDGE_TRI_EDGE2, IX_NONE, IX_TOT, KEY_EDGE_TRI_ORDER, KEY_SET, len_squared_v3v3(), printf, UNPACK3, UNPACK3_EX, UNPACK4, and vert_dissolve_add().

Referenced by bm_isect_tri_tri().

◆ bm_isect_tri_tri()

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 )

static

Return true if we have any intersections.

Definition at line 500 of file bmesh_intersect.cc.

References ARRAY_SIZE, b, BLI_gset_add(), BLI_gset_insert(), BM_edge_create(), BM_edge_exists(), BM_edge_in_face(), BM_ELEM_API_FLAG_DISABLE, BM_ELEM_API_FLAG_TEST, BM_elem_index_get, BM_face_share_edge_check(), bm_isect_edge_tri(), copy_v3_v3(), e, edge_verts_add(), ELEM, face_edges_add(), interp_v3_v3v3(), isect_point_tri_v3(), len_squared_v3v3(), line_point_factor_v3(), normal_tri_v3(), printf, STACK_DECLARE, STACK_INIT, STACK_PUSH_TEST_A, STACK_PUSH_TEST_B, STACK_SIZE, tri_v3_scale(), UNLIKELY, UNPACK2, UNPACK3, UNPACK3_EX, v, VERT_VISIT_A, and VERT_VISIT_B.

Referenced by BM_mesh_intersect().

◆ bm_loop_filter_fn()

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

static

Definition at line 473 of file bmesh_intersect.cc.

References BM_elem_flag_test, BM_ELEM_TAG, BMLoop::e, BMLoop::f, l, BMLoop::radial_next, and UNLIKELY.

Referenced by BM_mesh_intersect().

◆ BM_mesh_intersect()

bool BM_mesh_intersect	(	BMesh *	bm,
		const blender::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 )

Definition at line 952 of file bmesh_intersect.cc.

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, 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(), cos(), BMVert::e, e, edge_verts_sort(), ELEM, eps, BMLoop::f, face_edges_split(), faces, flag, BMesh::ftable, GHASH_ITER, GSET_ITER, int, isect_bvhtree_point_v3(), BMEdge::l, BMFace::len, len_squared_v3v3(), line_point_factor_v3(), LinkBase::list, LinkBase::list_len, BMFace::mat_nr, MEM_freeN(), MEM_mallocN, LinkNode::next, node, POINTER_AS_INT, printf, BMLoop::radial_next, STACK_DECLARE, STACK_INIT, STACK_PUSH_RET, STACK_SIZE, LoopFilterWrap::test_fn, BMesh::totface, UNLIKELY, UNPACK2, UNPACK3, UNUSED_VARS, UNUSED_VARS_NDEBUG, USE_NET, USE_SPLICE, and v.

Referenced by blender::ed::sculpt_paint::trim::apply_trim(), BMD_mesh_intersection(), edbm_intersect_boolean_exec(), edbm_intersect_exec(), and blender::geometry::boolean::mesh_boolean_float().

◆ bm_vert_other_edge()

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

static

Definition at line 81 of file bmesh_intersect.cc.

References BLI_assert, BM_DISK_EDGE_NEXT, BM_vert_in_edge(), BM_vert_is_edge_pair(), BMVert::e, e, and v.

Referenced by BM_mesh_intersect().

◆ edge_verts_add()

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

static

Definition at line 188 of file bmesh_intersect.cc.

References BLI_assert, BM_EDGE, BM_VERT, e, ghash_insert_link(), BMVert::head, BMHeader::htype, and v.

Referenced by bm_isect_edge_tri(), and bm_isect_tri_tri().

◆ edge_verts_sort()

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

static

Definition at line 164 of file bmesh_intersect.cc.

References BLI_array_alloca, BLI_assert, BLI_sortutil_cmp_float(), BM_VERT, BMVert::co, BMVert::head, BMHeader::htype, len_squared_v3v3(), LinkBase::list, LinkBase::list_len, node, v, vert_sort_t::v, and vert_sort_t::val.

Referenced by BM_mesh_intersect().

◆ face_edges_add()

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

static

Definition at line 195 of file bmesh_intersect.cc.

References BLI_assert, BM_EDGE, BM_edge_in_face(), BM_elem_index_get, e, ghash_insert_link(), BMVert::head, BMHeader::htype, and POINTER_FROM_INT.

Referenced by bm_isect_tri_tri().

◆ face_edges_split()

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 )

static

Definition at line 206 of file bmesh_intersect.cc.

References BLI_array_alloca, BLI_assert, bm, BM_elem_index_get, BM_FACE, BM_face_split_edgenet(), BM_face_split_edgenet_connect_islands(), BMFace::head, BMHeader::htype, LinkBase::list, LinkBase::list_len, node, printf, and UNUSED_VARS.

Referenced by BM_mesh_intersect().

◆ ghash_insert_link()

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

static

Definition at line 130 of file bmesh_intersect.cc.

References BLI_ghash_ensure_p(), BLI_linklist_index(), BLI_memarena_alloc(), LinkNode::link, LinkBase::list, LinkBase::list_len, mem_arena, and LinkNode::next.

Referenced by edge_verts_add(), and face_edges_add().

◆ 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 ISectEpsilon *	e )