#include <cstring>
#include "BLI_alloca.h"
#include "BLI_ghash.h"
#include "BLI_linklist.h"
#include "BLI_linklist_stack.h"
#include "BLI_listbase.h"
#include "BLI_mempool.h"
#include "MEM_guardedalloc.h"
#include "bmesh.hh"
#include "tools/bmesh_region_match.hh"
#include "BLI_strict_flags.h"

Classes
struct	UIDWalk
struct	UIDFaceStep
struct	UIDFaceStepItem

Macros
#define	USE_WALKER_REUSE
#define	USE_PIVOT_FASTMATCH
#define	USE_PIVOT_SEARCH
#define	PRIME_VERT_SMALL 7
#define	PRIME_VERT_MID 43
#define	PRIME_VERT_LARGE 1031
#define	PRIME_FACE_SMALL 13
#define	PRIME_FACE_MID 53
#define	PRIME_VERT_SMALL 11
#define	PRIME_FACE_SMALL 17
#define	PRIME_FACE_LARGE 1013
#define	PRIME_VERT_SMALL_A 7
#define	PRIME_VERT_SMALL_B 13
#define	PRIME_VERT_MID_A 103
#define	PRIME_VERT_MID_B 131
#define	PRIME_VERT_MID_A 23
#define	PRIME_VERT_MID_B 31
#define	PRIME_EDGE 7
#define	PRIME_FACE 31
#define	PRIME_LOOP 61

Functions
static BMFace **	bm_mesh_region_match_pair (UIDWalk w_src, UIDWalk w_dst, BMEdge e_src, BMEdge e_dst, const uint faces_src_region_len, const uint verts_src_region_len, uint *r_faces_result_len)
static void	bm_face_array_visit (BMFace *faces, const uint faces_len, uint r_verts_len, bool visit_faces)
int	BM_mesh_region_match (BMesh bm, BMFace faces_region, uint faces_region_len, ListBase r_face_regions)
Internal UIDFaceStep API
static int	facestep_sort (const void a, const void b)
static bool	bm_uidwalk_facestep_begin (UIDWalk uidwalk, UIDFaceStep fstep)
static void	bm_uidwalk_facestep_end (UIDWalk uidwalk, UIDFaceStep fstep)
static void	bm_uidwalk_facestep_free (UIDWalk uidwalk, UIDFaceStep fstep)

Internal UIDWalk API
#define	PRIME_VERT_INIT 100003
using	UID_Int = uintptr_t
using	SUID_Int = intptr_t
BLI_INLINE bool	bm_uidwalk_face_test (UIDWalk uidwalk, BMFace f)
BLI_INLINE bool	bm_uidwalk_vert_lookup (UIDWalk uidwalk, BMVert v, UID_Int *r_uid)
BLI_INLINE bool	bm_uidwalk_face_lookup (UIDWalk uidwalk, BMFace f, UID_Int *r_uid)
static uint	ghashutil_bmelem_indexhash (const void *key)
static bool	ghashutil_bmelem_indexcmp (const void a, const void b)
static GHash *	ghash_bmelem_new_ex (const char *info, const uint nentries_reserve)
static GSet *	gset_bmelem_new_ex (const char *info, const uint nentries_reserve)
static GHash *	ghash_bmelem_new (const char *info)
static GSet *	gset_bmelem_new (const char *info)
static void	bm_uidwalk_init (UIDWalk *uidwalk, const uint faces_src_region_len, const uint verts_src_region_len)
static void	bm_uidwalk_clear (UIDWalk *uidwalk)
static void	bm_uidwalk_free (UIDWalk *uidwalk)
static UID_Int	bm_uidwalk_calc_vert_uid (UIDWalk uidwalk, BMVert v)
static UID_Int	bm_uidwalk_calc_face_uid (UIDWalk uidwalk, BMFace f)
static void	bm_uidwalk_rehash_reserve (UIDWalk *uidwalk, uint rehash_store_len_new)
static void	bm_uidwalk_rehash (UIDWalk *uidwalk)
static void	bm_uidwalk_rehash_facelinks (UIDWalk uidwalk, LinkNode faces, const uint faces_len, const bool is_init)
static bool	bm_vert_is_uid_connect (UIDWalk uidwalk, BMVert v)
static void	bm_uidwalk_pass_add (UIDWalk uidwalk, LinkNode faces_pass, const uint faces_pass_len)
static int	bm_face_len_cmp (const void v1, const void v2)
static uint	bm_uidwalk_init_from_edge (UIDWalk uidwalk, BMEdge e)
BLI_INLINE intptr_t	abs_intptr (intptr_t a)
static bool	bm_edge_is_region_boundary (BMEdge *e)
static void	bm_face_region_pivot_edge_use_best (GHash gh, BMEdge e_test, BMEdge **r_e_pivot_best, SUID_Int e_pivot_best_id[2])
static SUID_Int	bm_face_region_vert_boundary_id (BMVert *v)
static SUID_Int	bm_face_region_vert_pass_id (GHash gh, BMVert v)
static BMEdge *	bm_face_region_pivot_edge_find (BMFace *faces_region, uint faces_region_len, uint verts_region_len, uint r_depth)

Fast Match
using	UIDFashMatch = uintptr_t
static UIDFashMatch	bm_vert_fasthash_single (BMVert *v)
static UIDFashMatch *	bm_vert_fasthash_create (BMesh *bm, const uint depth)
static void	bm_vert_fasthash_edge_order (const UIDFashMatch fm, const BMEdge e, UIDFashMatch e_fm[2])
static bool	bm_vert_fasthash_edge_is_match (UIDFashMatch fm, const BMEdge e_a, const BMEdge *e_b)
static void	bm_vert_fasthash_destroy (UIDFashMatch *fm)

Detailed Description

Given a contiguous region of faces, find multiple matching regions (based on topology) and return them.

Implementation:

Given a face region, find its topological center.
Compare this with other vertices surrounding geometry with this ones. (reduce the search space by creating a connectivity ID per vertex and only run comprehensive tests on those).
All hashes must be order independent so matching topology can be identified.
The term UID here doesn't mean each ID is initially unique. (uniqueness is improved by re-hashing with connected data).

Definition in file bmesh_region_match.cc.

Macro Definition Documentation

◆ PRIME_EDGE

#define PRIME_EDGE 7

Referenced by bm_vert_fasthash_single().

◆ PRIME_FACE

#define PRIME_FACE 31

Referenced by bm_vert_fasthash_single().

◆ PRIME_FACE_LARGE

#define PRIME_FACE_LARGE 1013

Referenced by bm_uidwalk_calc_face_uid().

◆ PRIME_FACE_MID

#define PRIME_FACE_MID 53

Referenced by bm_uidwalk_calc_vert_uid().

◆ PRIME_FACE_SMALL [1/2]

#define PRIME_FACE_SMALL 17

◆ PRIME_FACE_SMALL [2/2]

#define PRIME_FACE_SMALL 13

Referenced by bm_uidwalk_calc_face_uid(), and bm_uidwalk_calc_vert_uid().

◆ PRIME_LOOP

#define PRIME_LOOP 61

Referenced by bm_vert_fasthash_single().

◆ PRIME_VERT_INIT

#define PRIME_VERT_INIT 100003

Definition at line 62 of file bmesh_region_match.cc.

Referenced by bm_uidwalk_init_from_edge().

◆ PRIME_VERT_LARGE

#define PRIME_VERT_LARGE 1031

Referenced by bm_uidwalk_calc_vert_uid().

◆ PRIME_VERT_MID

#define PRIME_VERT_MID 43

Referenced by bm_uidwalk_calc_vert_uid().

◆ PRIME_VERT_MID_A [1/2]

#define PRIME_VERT_MID_A 23

◆ PRIME_VERT_MID_A [2/2]

#define PRIME_VERT_MID_A 103

Referenced by bm_face_region_vert_boundary_id(), and bm_face_region_vert_pass_id().

◆ PRIME_VERT_MID_B [1/2]

#define PRIME_VERT_MID_B 31

◆ PRIME_VERT_MID_B [2/2]

#define PRIME_VERT_MID_B 131

Referenced by bm_face_region_vert_boundary_id(), and bm_face_region_vert_pass_id().

◆ PRIME_VERT_SMALL [1/2]

#define PRIME_VERT_SMALL 11

◆ PRIME_VERT_SMALL [2/2]

#define PRIME_VERT_SMALL 7

Referenced by bm_uidwalk_calc_face_uid(), and bm_uidwalk_calc_vert_uid().

◆ PRIME_VERT_SMALL_A

#define PRIME_VERT_SMALL_A 7

Referenced by bm_face_region_vert_boundary_id().

◆ PRIME_VERT_SMALL_B

#define PRIME_VERT_SMALL_B 13

Referenced by bm_face_region_vert_boundary_id().

◆ USE_PIVOT_FASTMATCH

#define USE_PIVOT_FASTMATCH

Definition at line 43 of file bmesh_region_match.cc.

◆ USE_PIVOT_SEARCH

#define USE_PIVOT_SEARCH

Definition at line 46 of file bmesh_region_match.cc.

◆ USE_WALKER_REUSE

#define USE_WALKER_REUSE

Definition at line 38 of file bmesh_region_match.cc.

Referenced by BM_mesh_region_match(), and bm_mesh_region_match_pair().

Typedef Documentation

◆ SUID_Int

using SUID_Int = intptr_t

Definition at line 906 of file bmesh_region_match.cc.

◆ UID_Int

using UID_Int = uintptr_t

Definition at line 64 of file bmesh_region_match.cc.

◆ UIDFashMatch

using UIDFashMatch = uintptr_t

Definition at line 1231 of file bmesh_region_match.cc.

Function Documentation

◆ abs_intptr()

BLI_INLINE intptr_t abs_intptr ( intptr_t a )

Definition at line 908 of file bmesh_region_match.cc.

References BLI_INLINE.

Referenced by bm_face_region_vert_boundary_id(), and bm_face_region_vert_pass_id().

◆ bm_edge_is_region_boundary()

bool bm_edge_is_region_boundary ( BMEdge * e )

static

Definition at line 913 of file bmesh_region_match.cc.

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

Referenced by bm_face_region_pivot_edge_find(), and bm_face_region_vert_boundary_id().

◆ bm_face_array_visit()

void bm_face_array_visit	(	BMFace **	faces,
		const uint	faces_len,
		uint *	r_verts_len,
		bool	visit_faces )

static

Tag as visited, avoid re-use.

Definition at line 867 of file bmesh_region_match.cc.

References BM_elem_flag_enable, BM_elem_flag_test, BM_ELEM_TAG, BM_FACE_FIRST_LOOP, BMLoop::e, faces, i, BMLoop::next, and BMLoop::v.

Referenced by BM_mesh_region_match().

◆ bm_face_len_cmp()

int bm_face_len_cmp	(	const void *	v1,
		const void *	v2 )

static

Definition at line 540 of file bmesh_region_match.cc.

References BMFace::len, and v2.

Referenced by bm_uidwalk_init_from_edge().

◆ bm_face_region_pivot_edge_find()

BMEdge * bm_face_region_pivot_edge_find	(	BMFace **	faces_region,
		uint	faces_region_len,
		uint	verts_region_len,
		uint *	r_depth )

static

Take a face region and find the inner-most vertex. also calculate the number of connections to the boundary, and the total number unique of verts used by this face region.

This is only called once on the source region (no need to be highly optimized).

Definition at line 1043 of file bmesh_region_match.cc.

References BLI_assert, BLI_ghash_ensure_p(), BLI_ghash_free(), BLI_ghash_haskey(), BLI_ghash_lookup(), BLI_ghash_lookup_p(), BLI_ghash_ptr_new(), BLI_LINKSTACK_DECLARE, BLI_LINKSTACK_FREE, BLI_LINKSTACK_INIT, BLI_LINKSTACK_POP, BLI_LINKSTACK_PUSH, BLI_LINKSTACK_SIZE, BLI_LINKSTACK_SWAP, bm_edge_is_region_boundary(), BM_edge_other_vert(), BM_EDGES_OF_VERT, BM_elem_flag_disable, BM_elem_flag_enable, BM_elem_flag_test, BM_ELEM_TAG, BM_FACE_FIRST_LOOP, bm_face_region_pivot_edge_use_best(), bm_face_region_vert_boundary_id(), bm_face_region_vert_pass_id(), BM_ITER_ELEM, BMLoop::e, e, i, LinkNode::link, BMLoop::next, LinkNode::next, printf, and v.

Referenced by BM_mesh_region_match().

◆ bm_face_region_pivot_edge_use_best()

void bm_face_region_pivot_edge_use_best	(	GHash *	gh,
		BMEdge *	e_test,
		BMEdge **	r_e_pivot_best,
		SUID_Int	e_pivot_best_id[2] )

static

Definition at line 928 of file bmesh_region_match.cc.

References BLI_ghash_lookup(), BMEdge::v1, and BMEdge::v2.

Referenced by bm_face_region_pivot_edge_find().

◆ bm_face_region_vert_boundary_id()

SUID_Int bm_face_region_vert_boundary_id ( BMVert * v )

static

Definition at line 954 of file bmesh_region_match.cc.

References abs_intptr(), bm_edge_is_region_boundary(), BM_ITER_ELEM, BM_LOOPS_OF_VERT, l, PRIME_VERT_MID_A, PRIME_VERT_MID_B, PRIME_VERT_SMALL_A, PRIME_VERT_SMALL_B, and v.

Referenced by bm_face_region_pivot_edge_find().

◆ bm_face_region_vert_pass_id()

SUID_Int bm_face_region_vert_pass_id	(	GHash *	gh,
		BMVert *	v )

static

Accumulate id's from a previous pass (swap sign each pass)

Definition at line 986 of file bmesh_region_match.cc.

References abs_intptr(), BLI_ghash_lookup(), BM_edge_other_vert(), BM_EDGES_OF_VERT, BM_elem_flag_test, BM_ELEM_TAG, BM_ITER_ELEM, e, BMLoop::f, INTPTR_MIN, BMFace::len, PRIME_VERT_MID_A, PRIME_VERT_MID_B, BMLoop::radial_next, UNLIKELY, and v.

Referenced by bm_face_region_pivot_edge_find().

◆ BM_mesh_region_match()

int BM_mesh_region_match	(	BMesh *	bm,
		BMFace **	faces_region,
		uint	faces_region_len,
		ListBase *	r_face_regions )

Take a face-region and return a list of matching face-regions.

Parameters

faces_region A single, contiguous face-region.

Returns: A list of matching null-terminated face-region arrays.

Definition at line 1328 of file bmesh_region_match.cc.

References BLI_addtail(), BLI_genericNodeN(), BLI_listbase_clear(), bm, BM_EDGE, BM_edge_is_wire(), BM_EDGES_OF_MESH, BM_elem_flag_test, BM_ELEM_TAG, BM_FACE, bm_face_array_visit(), bm_face_region_pivot_edge_find(), BM_ITER_MESH, BM_mesh_active_edge_get(), BM_mesh_elem_hflag_disable_all(), BM_mesh_elem_index_ensure(), bm_mesh_region_match_pair(), BM_select_history_clear(), BM_select_history_store, bm_uidwalk_clear(), bm_uidwalk_free(), bm_uidwalk_init(), BM_VERT, bm_vert_fasthash_create(), bm_vert_fasthash_destroy(), bm_vert_fasthash_edge_is_match(), printf, TIMEIT_END, TIMEIT_START, and USE_WALKER_REUSE.

Referenced by edbm_select_similar_region_exec().

◆ bm_mesh_region_match_pair()

BMFace ** bm_mesh_region_match_pair	(	UIDWalk *	w_src,
		UIDWalk *	w_dst,
		BMEdge *	e_src,
		BMEdge *	e_dst,
		const uint	faces_src_region_len,
		const uint	verts_src_region_len,
		uint *	r_faces_result_len )