#include <string.h>
#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.h"
#include "tools/bmesh_region_match.h"
#include "BLI_strict_flags.h"

Classes
struct	UUIDWalk

struct	UUIDFaceStep

struct	UUIDFaceStepItem

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 (UUIDWalk w_src, UUIDWalk 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 UUIDFaceStep API
static int	facestep_sort (const void a, const void b)

static bool	bm_uuidwalk_facestep_begin (UUIDWalk uuidwalk, UUIDFaceStep fstep)

static void	bm_uuidwalk_facestep_end (UUIDWalk uuidwalk, UUIDFaceStep fstep)

static void	bm_uuidwalk_facestep_free (UUIDWalk uuidwalk, UUIDFaceStep fstep)

Internal UUIDWalk API
#define	PRIME_VERT_INIT 100003

typedef uintptr_t	UUID_Int

typedef struct UUIDWalk	UUIDWalk

typedef struct UUIDFaceStep	UUIDFaceStep

typedef struct UUIDFaceStepItem	UUIDFaceStepItem

typedef intptr_t	SUID_Int

BLI_INLINE bool	bm_uuidwalk_face_test (UUIDWalk uuidwalk, BMFace f)

BLI_INLINE bool	bm_uuidwalk_vert_lookup (UUIDWalk uuidwalk, BMVert v, UUID_Int *r_uuid)

BLI_INLINE bool	bm_uuidwalk_face_lookup (UUIDWalk uuidwalk, BMFace f, UUID_Int *r_uuid)

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_uuidwalk_init (UUIDWalk *uuidwalk, const uint faces_src_region_len, const uint verts_src_region_len)

static void	bm_uuidwalk_clear (UUIDWalk *uuidwalk)

static void	bm_uuidwalk_free (UUIDWalk *uuidwalk)

static UUID_Int	bm_uuidwalk_calc_vert_uuid (UUIDWalk uuidwalk, BMVert v)

static UUID_Int	bm_uuidwalk_calc_face_uuid (UUIDWalk uuidwalk, BMFace f)

static void	bm_uuidwalk_rehash_reserve (UUIDWalk *uuidwalk, uint rehash_store_len_new)

static void	bm_uuidwalk_rehash (UUIDWalk *uuidwalk)

static void	bm_uuidwalk_rehash_facelinks (UUIDWalk uuidwalk, LinkNode faces, const uint faces_len, const bool is_init)

static bool	bm_vert_is_uuid_connect (UUIDWalk uuidwalk, BMVert v)

static void	bm_uuidwalk_pass_add (UUIDWalk uuidwalk, LinkNode faces_pass, const uint faces_pass_len)

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

static uint	bm_uuidwalk_init_from_edge (UUIDWalk uuidwalk, 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
typedef uintptr_t	UUIDFashMatch

static UUIDFashMatch	bm_vert_fasthash_single (BMVert *v)

static UUIDFashMatch *	bm_vert_fasthash_create (BMesh *bm, const uint depth)

static void	bm_vert_fasthash_edge_order (const UUIDFashMatch fm, const BMEdge e, UUIDFashMatch e_fm[2])

static bool	bm_vert_fasthash_edge_is_match (UUIDFashMatch fm, const BMEdge e_a, const BMEdge *e_b)

static void	bm_vert_fasthash_destroy (UUIDFashMatch *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 UUID here doesn't mean each ID is initially unique. (uniqueness is improved by re-hashing with connected data).

Definition in file bmesh_region_match.c.

Macro Definition Documentation

◆ PRIME_EDGE

#define PRIME_EDGE 7

◆ PRIME_FACE

#define PRIME_FACE 31

◆ PRIME_FACE_LARGE

#define PRIME_FACE_LARGE 1013

◆ PRIME_FACE_MID

#define PRIME_FACE_MID 53

◆ PRIME_FACE_SMALL [1/2]

#define PRIME_FACE_SMALL 13

◆ PRIME_FACE_SMALL [2/2]

#define PRIME_FACE_SMALL 17

◆ PRIME_LOOP

#define PRIME_LOOP 61

◆ PRIME_VERT_INIT

#define PRIME_VERT_INIT 100003

Definition at line 73 of file bmesh_region_match.c.

◆ PRIME_VERT_LARGE

#define PRIME_VERT_LARGE 1031

◆ PRIME_VERT_MID

#define PRIME_VERT_MID 43

◆ PRIME_VERT_MID_A [1/2]

#define PRIME_VERT_MID_A 103

◆ PRIME_VERT_MID_A [2/2]

#define PRIME_VERT_MID_A 23

◆ PRIME_VERT_MID_B [1/2]

#define PRIME_VERT_MID_B 131

◆ PRIME_VERT_MID_B [2/2]

#define PRIME_VERT_MID_B 31

◆ PRIME_VERT_SMALL [1/2]

#define PRIME_VERT_SMALL 7

◆ PRIME_VERT_SMALL [2/2]

#define PRIME_VERT_SMALL 11

◆ PRIME_VERT_SMALL_A

#define PRIME_VERT_SMALL_A 7

◆ PRIME_VERT_SMALL_B

#define PRIME_VERT_SMALL_B 13

◆ USE_PIVOT_FASTMATCH

#define USE_PIVOT_FASTMATCH

Definition at line 54 of file bmesh_region_match.c.

◆ USE_PIVOT_SEARCH

#define USE_PIVOT_SEARCH

Definition at line 57 of file bmesh_region_match.c.

◆ USE_WALKER_REUSE

#define USE_WALKER_REUSE

Definition at line 49 of file bmesh_region_match.c.

Typedef Documentation

◆ SUID_Int

typedef intptr_t SUID_Int

Definition at line 915 of file bmesh_region_match.c.

◆ UUID_Int

typedef uintptr_t UUID_Int

Definition at line 75 of file bmesh_region_match.c.

◆ UUIDFaceStep

typedef struct UUIDFaceStep UUIDFaceStep

◆ UUIDFaceStepItem

typedef struct UUIDFaceStepItem UUIDFaceStepItem

◆ UUIDFashMatch

typedef uintptr_t UUIDFashMatch

Definition at line 1238 of file bmesh_region_match.c.

◆ UUIDWalk

typedef struct UUIDWalk UUIDWalk

Function Documentation

◆ abs_intptr()

BLI_INLINE intptr_t abs_intptr ( intptr_t a )

Definition at line 917 of file bmesh_region_match.c.

References Freestyle::a.

Referenced by bm_face_region_vert_boundary_id(), and bm_face_region_vert_pass_id().

◆ bm_edge_is_region_boundary()

static bool bm_edge_is_region_boundary ( BMEdge * e )

static

Definition at line 922 of file bmesh_region_match.c.

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

static 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 876 of file bmesh_region_match.c.

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

Referenced by BM_mesh_region_match().

◆ bm_face_len_cmp()

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

static

Definition at line 554 of file bmesh_region_match.c.

References BMFace::len, v1, and v2.

Referenced by bm_uuidwalk_init_from_edge().

◆ bm_face_region_pivot_edge_find()

static 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 1051 of file bmesh_region_match.c.

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, LinkNode::link, LinkNode::next, BMLoop::next, NULL, and v.

Referenced by BM_mesh_region_match().

◆ bm_face_region_pivot_edge_use_best()

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

Definition at line 937 of file bmesh_region_match.c.

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

Referenced by bm_face_region_pivot_edge_find().

◆ bm_face_region_vert_boundary_id()

static SUID_Int bm_face_region_vert_boundary_id ( BMVert * v )

static

Definition at line 962 of file bmesh_region_match.c.

References abs_intptr(), bm_edge_is_region_boundary(), BM_ITER_ELEM, BM_LOOPS_OF_VERT, BMLoop::e, BMLoop::f, l, BMFace::len, BMLoop::prev, 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()

static 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 994 of file bmesh_region_match.c.

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, id, 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 1341 of file bmesh_region_match.c.

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_uuidwalk_clear(), bm_uuidwalk_free(), bm_uuidwalk_init(), BM_VERT, bm_vert_fasthash_create(), bm_vert_fasthash_destroy(), bm_vert_fasthash_edge_is_match(), NULL, TIMEIT_END, TIMEIT_START, and USE_WALKER_REUSE.

Referenced by edbm_select_similar_region_exec().

◆ bm_mesh_region_match_pair()

static BMFace** bm_mesh_region_match_pair	(	UUIDWalk *	w_src,
		UUIDWalk *	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
	)