Blender V5.3
bmesh_region_match.cc File Reference
#include <algorithm>
#include <cstring>
#include "BLI_array.hh"
#include "BLI_ghash.hh"
#include "BLI_linklist.hh"
#include "BLI_linklist_stack.hh"
#include "BLI_listbase.hh"
#include "BLI_mempool.hh"
#include "MEM_guardedalloc.h"
#include "bmesh.hh"
#include "tools/bmesh_region_match.hh"
#include "BLI_strict_flags.hh"

Go to the source code of this file.

Classes

struct  blender::BMElemIndexHash
struct  blender::BMElemIndexEq
struct  blender::UIDWalk
struct  blender::UIDFaceStep
struct  blender::UIDFaceStepItem

Namespaces

namespace  blender
 BMesh Iterators.

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 ** blender::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 blender::bm_face_array_visit (BMFace **faces, const uint faces_len, uint *r_verts_len, bool visit_faces)
int blender::BM_mesh_region_match (BMesh *bm, BMFace **faces_region, uint faces_region_len, ListBaseT< LinkData > *r_face_regions)
Internal UIDFaceStep API
static int blender::facestep_sort (const void *a, const void *b)
static bool blender::bm_uidwalk_facestep_begin (UIDWalk *uidwalk, UIDFaceStep *fstep)
static void blender::bm_uidwalk_facestep_end (UIDWalk *uidwalk, UIDFaceStep *fstep)
static void blender::bm_uidwalk_facestep_free (UIDWalk *uidwalk, UIDFaceStep *fstep)

Internal UIDWalk API

#define PRIME_VERT_INIT   100003
using blender::UID_Int = uintptr_t
using blender::BMFaceIndexSet = Set<BMFace *, 4, DefaultProbingStrategy, BMElemIndexHash, BMElemIndexEq>
using blender::SUID_Int = intptr_t
BLI_INLINE bool blender::bm_uidwalk_face_test (UIDWalk *uidwalk, BMFace *f)
BLI_INLINE bool blender::bm_uidwalk_vert_lookup (UIDWalk *uidwalk, BMVert *v, UID_Int *r_uid)
BLI_INLINE bool blender::bm_uidwalk_face_lookup (UIDWalk *uidwalk, BMFace *f, UID_Int *r_uid)
static uint blender::ghashutil_bmelem_indexhash (const void *key)
static bool blender::ghashutil_bmelem_indexcmp (const void *a, const void *b)
static GHash * blender::ghash_bmelem_new_ex (const char *info, const uint nentries_reserve)
static GHash * blender::ghash_bmelem_new (const char *info)
static void blender::bm_uidwalk_init (UIDWalk *uidwalk, const uint faces_src_region_len, const uint verts_src_region_len)
static void blender::bm_uidwalk_clear (UIDWalk *uidwalk)
static void blender::bm_uidwalk_free (UIDWalk *uidwalk)
static UID_Int blender::bm_uidwalk_calc_vert_uid (UIDWalk *uidwalk, BMVert *v)
static UID_Int blender::bm_uidwalk_calc_face_uid (UIDWalk *uidwalk, BMFace *f)
static void blender::bm_uidwalk_rehash_reserve (UIDWalk *uidwalk, uint rehash_store_len_new)
static void blender::bm_uidwalk_rehash (UIDWalk *uidwalk)
static void blender::bm_uidwalk_rehash_facelinks (UIDWalk *uidwalk, LinkNode *faces, const uint faces_len, const bool is_init)
static bool blender::bm_vert_is_uid_connect (UIDWalk *uidwalk, BMVert *v)
static void blender::bm_uidwalk_pass_add (UIDWalk *uidwalk, LinkNode *faces_pass, const uint faces_pass_len)
static uint blender::bm_uidwalk_init_from_edge (UIDWalk *uidwalk, BMEdge *e)
BLI_INLINE intptr_t blender::abs_intptr (intptr_t a)
static bool blender::bm_edge_is_region_boundary (BMEdge *e)
static void blender::bm_face_region_pivot_edge_use_best (const Map< BMVert *, SUID_Int > &gh, BMEdge *e_test, BMEdge **r_e_pivot_best, SUID_Int e_pivot_best_id[2])
static SUID_Int blender::bm_face_region_vert_boundary_id (BMVert *v)
static SUID_Int blender::bm_face_region_vert_pass_id (const Map< BMVert *, SUID_Int > &gh, BMVert *v)
static BMEdge * blender::bm_face_region_pivot_edge_find (BMFace **faces_region, uint faces_region_len, uint verts_region_len, uint *r_depth)

Fast Match

using blender::UIDFashMatch = uintptr_t
static UIDFashMatch blender::bm_vert_fasthash_single (BMVert *v)
static UIDFashMatch * blender::bm_vert_fasthash_create (BMesh *bm, const uint depth)
static void blender::bm_vert_fasthash_edge_order (const UIDFashMatch *fm, const BMEdge *e, UIDFashMatch e_fm[2])
static bool blender::bm_vert_fasthash_edge_is_match (UIDFashMatch *fm, const BMEdge *e_a, const BMEdge *e_b)
static void blender::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

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

◆ PRIME_FACE_SMALL [2/2]

#define PRIME_FACE_SMALL   13

◆ PRIME_LOOP

#define PRIME_LOOP   61

◆ PRIME_VERT_INIT

#define PRIME_VERT_INIT   100003

Definition at line 65 of file bmesh_region_match.cc.

Referenced by blender::bm_uidwalk_init_from_edge().

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

◆ PRIME_VERT_MID_A [2/2]

#define PRIME_VERT_MID_A   103

◆ PRIME_VERT_MID_B [1/2]

#define PRIME_VERT_MID_B   31

◆ PRIME_VERT_MID_B [2/2]

#define PRIME_VERT_MID_B   131

◆ PRIME_VERT_SMALL [1/2]

#define PRIME_VERT_SMALL   11

◆ PRIME_VERT_SMALL [2/2]

#define PRIME_VERT_SMALL   7

◆ 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 44 of file bmesh_region_match.cc.

◆ USE_PIVOT_SEARCH

#define USE_PIVOT_SEARCH

Definition at line 47 of file bmesh_region_match.cc.

◆ USE_WALKER_REUSE

#define USE_WALKER_REUSE