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

Go to the source code of this file.

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 GHashghash_bmelem_new_ex (const char *info, const uint nentries_reserve)
 
static GSetgset_bmelem_new_ex (const char *info, const uint nentries_reserve)
 
static GHashghash_bmelem_new (const char *info)
 
static GSetgset_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 BMEdgebm_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 UUIDFashMatchbm_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:

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 59 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 40 of file bmesh_region_match.c.

◆ USE_PIVOT_SEARCH

#define USE_PIVOT_SEARCH

Definition at line 43 of file bmesh_region_match.c.

◆ USE_WALKER_REUSE

#define USE_WALKER_REUSE

Definition at line 35 of file bmesh_region_match.c.

Typedef Documentation

◆ SUID_Int

typedef intptr_t SUID_Int

Definition at line 901 of file bmesh_region_match.c.

◆ UUID_Int

Definition at line 61 of file bmesh_region_match.c.

◆ UUIDFaceStep

typedef struct UUIDFaceStep UUIDFaceStep

◆ UUIDFaceStepItem

◆ UUIDFashMatch

Definition at line 1225 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 903 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

◆ 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 862 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 540 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

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

◆ bm_face_region_vert_pass_id()

static SUID_Int bm_face_region_vert_pass_id ( GHash gh,
BMVert v 
)
static

◆ BM_mesh_region_match()

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

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

◆ bm_uuidwalk_calc_face_uuid()

static UUID_Int bm_uuidwalk_calc_face_uuid ( UUIDWalk uuidwalk,
BMFace f 
)
static

◆ bm_uuidwalk_calc_vert_uuid()

static UUID_Int bm_uuidwalk_calc_vert_uuid ( UUIDWalk uuidwalk,
BMVert v 
)
static

◆ bm_uuidwalk_clear()

static void bm_uuidwalk_clear ( UUIDWalk uuidwalk)
static

◆ bm_uuidwalk_face_lookup()

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

Definition at line 140 of file bmesh_region_match.c.

References BLI_ghash_lookup_p(), UUIDWalk::faces_uuid, and ret.

Referenced by bm_uuidwalk_calc_vert_uuid().

◆ bm_uuidwalk_face_test()

BLI_INLINE bool bm_uuidwalk_face_test ( UUIDWalk uuidwalk,
BMFace f 
)

◆ bm_uuidwalk_facestep_begin()

static bool bm_uuidwalk_facestep_begin ( UUIDWalk uuidwalk,
UUIDFaceStep fstep 
)
static

◆ bm_uuidwalk_facestep_end()

static void bm_uuidwalk_facestep_end ( UUIDWalk uuidwalk,
UUIDFaceStep fstep 
)
static

◆ bm_uuidwalk_facestep_free()

static void bm_uuidwalk_facestep_free ( UUIDWalk uuidwalk,
UUIDFaceStep fstep 
)
static

◆ bm_uuidwalk_free()

static void bm_uuidwalk_free ( UUIDWalk uuidwalk)
static

◆ bm_uuidwalk_init()

static void bm_uuidwalk_init ( UUIDWalk uuidwalk,
const uint  faces_src_region_len,
const uint  verts_src_region_len 
)
static

◆ bm_uuidwalk_init_from_edge()

static uint bm_uuidwalk_init_from_edge ( UUIDWalk uuidwalk,
BMEdge e 
)
static

◆ bm_uuidwalk_pass_add()

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

◆ bm_uuidwalk_rehash()

static void bm_uuidwalk_rehash ( UUIDWalk uuidwalk)
static

◆ bm_uuidwalk_rehash_facelinks()

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

◆ bm_uuidwalk_rehash_reserve()

static void bm_uuidwalk_rehash_reserve ( UUIDWalk uuidwalk,
uint  rehash_store_len_new 
)
static

◆ bm_uuidwalk_vert_lookup()

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

◆ bm_vert_fasthash_create()

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

◆ bm_vert_fasthash_destroy()

static void bm_vert_fasthash_destroy ( UUIDFashMatch fm)
static

Definition at line 1313 of file bmesh_region_match.c.

References MEM_freeN.

Referenced by BM_mesh_region_match().

◆ bm_vert_fasthash_edge_is_match()

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

Definition at line 1302 of file bmesh_region_match.c.

References bm_vert_fasthash_edge_order().

Referenced by BM_mesh_region_match().

◆ bm_vert_fasthash_edge_order()

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

Definition at line 1290 of file bmesh_region_match.c.

References BM_elem_index_get, e, and SWAP.

Referenced by bm_vert_fasthash_edge_is_match().

◆ bm_vert_fasthash_single()

static UUIDFashMatch bm_vert_fasthash_single ( BMVert v)
static

◆ bm_vert_is_uuid_connect()

static bool bm_vert_is_uuid_connect ( UUIDWalk uuidwalk,
BMVert v 
)
static

◆ facestep_sort()

static int facestep_sort ( const void a,
const void b 
)
static

Definition at line 607 of file bmesh_region_match.c.

References Freestyle::a, usdtokens::b(), and UUIDFaceStepItem::uuid.

Referenced by bm_uuidwalk_facestep_begin().

◆ ghash_bmelem_new()

static GHash* ghash_bmelem_new ( const char *  info)
static

Definition at line 175 of file bmesh_region_match.c.

References ghash_bmelem_new_ex().

Referenced by bm_uuidwalk_init().

◆ ghash_bmelem_new_ex()

static GHash* ghash_bmelem_new_ex ( const char *  info,
const uint  nentries_reserve 
)
static

◆ ghashutil_bmelem_indexcmp()

static bool ghashutil_bmelem_indexcmp ( const void a,
const void b 
)
static

◆ ghashutil_bmelem_indexhash()

static uint ghashutil_bmelem_indexhash ( const void key)
static

Definition at line 151 of file bmesh_region_match.c.

References BM_elem_index_get.

Referenced by ghash_bmelem_new_ex(), and gset_bmelem_new_ex().

◆ gset_bmelem_new()

static GSet* gset_bmelem_new ( const char *  info)
static

Definition at line 180 of file bmesh_region_match.c.

References gset_bmelem_new_ex().

Referenced by bm_uuidwalk_init().

◆ gset_bmelem_new_ex()

static GSet* gset_bmelem_new_ex ( const char *  info,
const uint  nentries_reserve 
)
static