Blender
V3.3
|
#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) |
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) |
Given a contiguous region of faces, find multiple matching regions (based on topology) and return them.
Implementation:
Definition in file bmesh_region_match.c.
#define PRIME_EDGE 7 |
#define PRIME_FACE 31 |
#define PRIME_FACE_LARGE 1013 |
#define PRIME_FACE_MID 53 |
#define PRIME_FACE_SMALL 13 |
#define PRIME_FACE_SMALL 17 |
#define PRIME_LOOP 61 |
#define PRIME_VERT_INIT 100003 |
Definition at line 59 of file bmesh_region_match.c.
#define PRIME_VERT_LARGE 1031 |
#define PRIME_VERT_MID 43 |
#define PRIME_VERT_MID_A 103 |
#define PRIME_VERT_MID_A 23 |
#define PRIME_VERT_MID_B 131 |
#define PRIME_VERT_MID_B 31 |
#define PRIME_VERT_SMALL 7 |
#define PRIME_VERT_SMALL 11 |
#define PRIME_VERT_SMALL_A 7 |
#define PRIME_VERT_SMALL_B 13 |
#define USE_PIVOT_FASTMATCH |
Definition at line 40 of file bmesh_region_match.c.
#define USE_PIVOT_SEARCH |
Definition at line 43 of file bmesh_region_match.c.
#define USE_WALKER_REUSE |
Definition at line 35 of file bmesh_region_match.c.
Definition at line 901 of file bmesh_region_match.c.
Definition at line 61 of file bmesh_region_match.c.
typedef struct UUIDFaceStep UUIDFaceStep |
typedef struct UUIDFaceStepItem UUIDFaceStepItem |
typedef uintptr_t UUIDFashMatch |
Definition at line 1225 of file bmesh_region_match.c.
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().
Definition at line 908 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().
|
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().
Definition at line 540 of file bmesh_region_match.c.
References BMFace::len, v1, and v2.
Referenced by bm_uuidwalk_init_from_edge().
|
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 1037 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().
|
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().
Definition at line 948 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().
Accumulate id's from a previous pass (swap sign each pass)
Definition at line 980 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().
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.
faces_region | A single, contiguous face-region. |
Definition at line 1322 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, USE_WALKER_REUSE, and void.
Referenced by edbm_select_similar_region_exec().
|
static |
Given a face region and 2 candidate verts to begin mapping. return the matching region or NULL.
Definition at line 706 of file bmesh_region_match.c.
References BLI_assert, BLI_ghash_len(), BLI_ghashIterator_getKey(), BLI_linklist_free_pool(), BLI_listbase_count(), bm_uuidwalk_clear(), bm_uuidwalk_facestep_begin(), bm_uuidwalk_facestep_end(), bm_uuidwalk_facestep_free(), bm_uuidwalk_free(), bm_uuidwalk_init(), bm_uuidwalk_init_from_edge(), bm_uuidwalk_pass_add(), bm_uuidwalk_rehash(), bm_uuidwalk_rehash_reserve(), UUIDFaceStep::faces, UUIDWalk::faces_step, UUIDWalk::faces_uuid, ListBase::first, GHASH_ITER_INDEX, UUIDFaceStep::items, UUIDWalk::link_pool, UUIDFaceStepItem::list, UUIDFaceStepItem::list_len, MAX2, MEM_mallocN, UUIDFaceStep::next, UUIDFaceStepItem::next, NULL, UNLIKELY, and UUIDFaceStepItem::uuid.
Referenced by BM_mesh_region_match().
Definition at line 313 of file bmesh_region_match.c.
References BM_FACE_FIRST_LOOP, bm_uuidwalk_vert_lookup(), BMFace::len, UUIDWalk::pass, PRIME_FACE_LARGE, PRIME_VERT_SMALL, and UUIDFaceStepItem::uuid.
Referenced by bm_uuidwalk_facestep_begin(), bm_uuidwalk_rehash(), and bm_uuidwalk_rehash_facelinks().
Definition at line 258 of file bmesh_region_match.c.
References BM_edge_other_vert(), BM_EDGES_OF_VERT, BM_FACES_OF_VERT, BM_ITER_ELEM, bm_uuidwalk_face_lookup(), bm_uuidwalk_vert_lookup(), e, UUIDWalk::pass, PRIME_FACE_MID, PRIME_FACE_SMALL, PRIME_VERT_LARGE, PRIME_VERT_MID, PRIME_VERT_SMALL, UUIDFaceStepItem::uuid, and v.
Referenced by bm_uuidwalk_pass_add(), and bm_uuidwalk_rehash().
Definition at line 214 of file bmesh_region_match.c.
References BLI_ghash_clear(), BLI_gset_clear(), BLI_listbase_clear(), BLI_mempool_clear(), UUIDWalk::cache, UUIDWalk::faces_from_uuid, UUIDWalk::faces_step, UUIDWalk::faces_uuid, UUIDWalk::link_pool, NULL, UUIDWalk::pass, UUIDWalk::step_pool, UUIDWalk::step_pool_items, UUIDWalk::use_face_isolate, and UUIDWalk::verts_uuid.
Referenced by BM_mesh_region_match(), and bm_mesh_region_match_pair().
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().
BLI_INLINE bool bm_uuidwalk_face_test | ( | UUIDWalk * | uuidwalk, |
BMFace * | f | ||
) |
Definition at line 121 of file bmesh_region_match.c.
References BM_elem_flag_test_bool, BM_ELEM_TAG, and UUIDWalk::use_face_isolate.
Referenced by bm_uuidwalk_init_from_edge(), and bm_uuidwalk_pass_add().
|
static |
Put faces in lists based on their uuid's, re-run for each pass since rehashing may differentiate face-groups.
Definition at line 618 of file bmesh_region_match.c.
References BLI_addhead(), BLI_assert, BLI_ghash_clear(), BLI_ghash_ensure_p(), BLI_ghash_haskey(), BLI_ghash_len(), BLI_linklist_prepend_pool(), BLI_listbase_is_empty(), BLI_listbase_sort(), BLI_mempool_alloc(), BLI_mempool_free(), bm_uuidwalk_calc_face_uuid(), UUIDWalk::cache, UUIDFaceStep::faces, UUIDWalk::faces_from_uuid, UUIDWalk::faces_uuid, facestep_sort(), UUIDFaceStep::items, LinkNode::link, UUIDWalk::link_pool, UUIDFaceStepItem::list, UUIDFaceStepItem::list_len, LinkNode::next, NULL, UUIDWalk::step_pool_items, and UUIDFaceStepItem::uuid.
Referenced by bm_mesh_region_match_pair().
|
static |
Cleans up temp data from bm_uuidwalk_facestep_begin
Definition at line 673 of file bmesh_region_match.c.
References BLI_mempool_free(), BLI_pophead(), UUIDFaceStep::items, and UUIDWalk::step_pool_items.
Referenced by bm_mesh_region_match_pair().
|
static |
Definition at line 682 of file bmesh_region_match.c.
References BLI_assert, BLI_listbase_is_empty(), BLI_mempool_free(), BLI_remlink(), UUIDFaceStep::faces, UUIDWalk::faces_step, UUIDFaceStep::items, UUIDWalk::link_pool, LinkNode::next, and UUIDWalk::step_pool.
Referenced by bm_mesh_region_match_pair().
Handled by pools
Definition at line 236 of file bmesh_region_match.c.
References BLI_ghash_free(), BLI_gset_free(), BLI_mempool_destroy(), UUIDWalk::cache, UUIDWalk::faces_from_uuid, UUIDWalk::faces_step, UUIDWalk::faces_uuid, UUIDWalk::link_pool, MEM_SAFE_FREE, NULL, UUIDWalk::rehash_store, UUIDWalk::step_pool, UUIDWalk::step_pool_items, and UUIDWalk::verts_uuid.
Referenced by BM_mesh_region_match(), and bm_mesh_region_match_pair().
|
static |
Definition at line 185 of file bmesh_region_match.c.
References BLI_ghash_int_new(), BLI_listbase_clear(), BLI_mempool_create(), BLI_MEMPOOL_NOP, UUIDWalk::cache, UUIDWalk::faces_from_uuid, UUIDWalk::faces_step, UUIDWalk::faces_uuid, ghash_bmelem_new(), ghash_bmelem_new_ex(), gset_bmelem_new(), UUIDWalk::link_pool, NULL, UUIDWalk::pass, UUIDWalk::rehash_store, UUIDWalk::rehash_store_len, UUIDWalk::step_pool, UUIDWalk::step_pool_items, UUIDWalk::use_face_isolate, and UUIDWalk::verts_uuid.
Referenced by BM_mesh_region_match(), and bm_mesh_region_match_pair().
Definition at line 554 of file bmesh_region_match.c.
References BLI_array_alloca, BLI_assert, BLI_ghash_insert(), BLI_linklist_free_pool(), BLI_linklist_prepend_pool(), BM_edge_face_count(), bm_face_len_cmp(), bm_uuidwalk_face_test(), bm_uuidwalk_pass_add(), e, BMLoop::f, BMFace::len, len, UUIDWalk::link_pool, NULL, PRIME_VERT_INIT, BMLoop::radial_next, UUIDFaceStepItem::uuid, and UUIDWalk::verts_uuid.
Referenced by bm_mesh_region_match_pair().
|
static |
Definition at line 463 of file bmesh_region_match.c.
References BLI_addhead(), BLI_assert, BLI_ghash_clear(), BLI_ghash_ensure_p(), BLI_ghash_haskey(), BLI_ghash_insert(), BLI_ghash_len(), BLI_ghashIterator_getKey(), BLI_ghashIterator_getValue(), BLI_gset_clear(), BLI_gset_haskey(), BLI_gset_insert(), BLI_gset_len(), BLI_linklist_count(), BLI_linklist_prepend_pool(), BLI_listbase_clear(), BLI_mempool_alloc(), BM_FACE_FIRST_LOOP, bm_uuidwalk_calc_vert_uuid(), bm_uuidwalk_face_test(), bm_uuidwalk_rehash_facelinks(), bm_vert_is_uuid_connect(), UUIDWalk::cache, BMLoop::f, UUIDFaceStep::faces, UUIDWalk::faces_step, UUIDWalk::faces_uuid, GHASH_ITER, UUIDFaceStep::items, LinkNode::link, UUIDWalk::link_pool, LinkNode::next, BMLoop::next, NULL, UUIDWalk::pass, BMLoop::radial_next, UUIDWalk::step_pool, UUIDFaceStepItem::uuid, BMLoop::v, v, and UUIDWalk::verts_uuid.
Referenced by bm_mesh_region_match_pair(), and bm_uuidwalk_init_from_edge().
Re-hash all elements, delay updating so as not to create feedback loop.
Definition at line 378 of file bmesh_region_match.c.
References BLI_ghash_len(), BLI_ghashIterator_getKey(), BLI_ghashIterator_getValue_p(), bm_uuidwalk_calc_face_uuid(), bm_uuidwalk_calc_vert_uuid(), bm_uuidwalk_rehash_reserve(), UUIDWalk::cache, UUIDWalk::faces_uuid, GHASH_ITER, MAX2, UUIDWalk::rehash_store, v, and UUIDWalk::verts_uuid.
Referenced by bm_mesh_region_match_pair().
|
static |
Definition at line 415 of file bmesh_region_match.c.
References BLI_ghash_insert(), BLI_ghash_lookup_p(), bm_uuidwalk_calc_face_uuid(), bm_uuidwalk_rehash_reserve(), UUIDWalk::cache, faces, UUIDWalk::faces_uuid, LinkNode::link, LinkNode::next, and UUIDWalk::rehash_store.
Referenced by bm_uuidwalk_pass_add().
Definition at line 363 of file bmesh_region_match.c.
References UUIDWalk::cache, MEM_reallocN, UUIDWalk::rehash_store, UUIDWalk::rehash_store_len, and UNLIKELY.
Referenced by bm_mesh_region_match_pair(), bm_uuidwalk_rehash(), and bm_uuidwalk_rehash_facelinks().
BLI_INLINE bool bm_uuidwalk_vert_lookup | ( | UUIDWalk * | uuidwalk, |
BMVert * | v, | ||
UUID_Int * | r_uuid | ||
) |
Definition at line 129 of file bmesh_region_match.c.
References BLI_ghash_lookup_p(), ret, v, and UUIDWalk::verts_uuid.
Referenced by bm_uuidwalk_calc_face_uuid(), and bm_uuidwalk_calc_vert_uuid().
|
static |
Definition at line 1255 of file bmesh_region_match.c.
References bm, BM_edge_is_wire(), BM_EDGES_OF_MESH, BM_elem_index_get, BM_ITER_MESH, BM_ITER_MESH_INDEX, bm_vert_fasthash_single(), BM_VERTS_OF_MESH, e, i1, MEM_freeN, MEM_mallocN, BMesh::totvert, and v.
Referenced by BM_mesh_region_match().
|
static |
Definition at line 1313 of file bmesh_region_match.c.
References MEM_freeN.
Referenced by BM_mesh_region_match().
|
static |
Definition at line 1302 of file bmesh_region_match.c.
References bm_vert_fasthash_edge_order().
Referenced by BM_mesh_region_match().
|
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().
|
static |
Definition at line 1227 of file bmesh_region_match.c.
References BM_edge_is_wire(), BM_EDGES_OF_VERT, BM_ITER_ELEM, e, BMLoop::f, BMFace::len, PRIME_EDGE, PRIME_FACE, PRIME_LOOP, BMLoop::radial_next, and v.
Referenced by bm_vert_fasthash_create().
Definition at line 449 of file bmesh_region_match.c.
References BLI_ghash_haskey(), BM_edge_other_vert(), BM_EDGES_OF_VERT, BM_ITER_ELEM, e, v, and UUIDWalk::verts_uuid.
Referenced by bm_uuidwalk_pass_add().
Definition at line 607 of file bmesh_region_match.c.
References Freestyle::a, usdtokens::b(), and UUIDFaceStepItem::uuid.
Referenced by bm_uuidwalk_facestep_begin().
|
static |
Definition at line 175 of file bmesh_region_match.c.
References ghash_bmelem_new_ex().
Referenced by bm_uuidwalk_init().
Definition at line 163 of file bmesh_region_match.c.
References BLI_ghash_new_ex(), ghashutil_bmelem_indexcmp(), and ghashutil_bmelem_indexhash().
Referenced by bm_uuidwalk_init(), and ghash_bmelem_new().
Definition at line 157 of file bmesh_region_match.c.
References Freestyle::a, usdtokens::b(), BLI_assert, and BM_elem_index_get.
Referenced by ghash_bmelem_new_ex(), and gset_bmelem_new_ex().
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().
|
static |
Definition at line 180 of file bmesh_region_match.c.
References gset_bmelem_new_ex().
Referenced by bm_uuidwalk_init().
Definition at line 169 of file bmesh_region_match.c.
References BLI_gset_new_ex(), ghashutil_bmelem_indexcmp(), and ghashutil_bmelem_indexhash().
Referenced by gset_bmelem_new().