diff options
Diffstat (limited to 'source/blender/bmesh')
21 files changed, 1677 insertions, 158 deletions
diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt index a43e835f022..50d3ac30ddc 100644 --- a/source/blender/bmesh/CMakeLists.txt +++ b/source/blender/bmesh/CMakeLists.txt @@ -140,6 +140,8 @@ set(SRC tools/bmesh_intersect.h tools/bmesh_path.c tools/bmesh_path.h + tools/bmesh_region_match.c + tools/bmesh_region_match.h tools/bmesh_triangulate.c tools/bmesh_triangulate.h tools/bmesh_wireframe.c diff --git a/source/blender/bmesh/bmesh.h b/source/blender/bmesh/bmesh.h index 8b5250b7c1e..4efc6aa16f8 100644 --- a/source/blender/bmesh/bmesh.h +++ b/source/blender/bmesh/bmesh.h @@ -58,8 +58,8 @@ * * \subsection bm_loop The Loop * - * Loops define the boundary loop of a face. Each loop logically corresponds to an edge, - * which is defined by the loop and next loop's vertices. + * Each loop connects the face to one of its corner vertices, + * and also references an edge which connects this loop's vertex to the next loop's vertex. * * Loops store several handy pointers: * diff --git a/source/blender/bmesh/bmesh_tools.h b/source/blender/bmesh/bmesh_tools.h index baffeb774b6..f7f767f91bf 100644 --- a/source/blender/bmesh/bmesh_tools.h +++ b/source/blender/bmesh/bmesh_tools.h @@ -41,6 +41,7 @@ extern "C" { #include "tools/bmesh_edgenet.h" #include "tools/bmesh_edgesplit.h" #include "tools/bmesh_path.h" +#include "tools/bmesh_region_match.h" #include "tools/bmesh_triangulate.h" #ifdef __cplusplus diff --git a/source/blender/bmesh/intern/bmesh_construct.c b/source/blender/bmesh/intern/bmesh_construct.c index eef1e7bbb4f..e0348fea636 100644 --- a/source/blender/bmesh/intern/bmesh_construct.c +++ b/source/blender/bmesh/intern/bmesh_construct.c @@ -505,7 +505,7 @@ static void bm_vert_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, return; } copy_v3_v3(target_vertex->no, source_vertex->no); - CustomData_bmesh_free_block_data(&target_mesh->vdata, &target_vertex->head.data); + CustomData_bmesh_free_block_data(&target_mesh->vdata, target_vertex->head.data); CustomData_bmesh_copy_data(&source_mesh->vdata, &target_mesh->vdata, source_vertex->head.data, &target_vertex->head.data); } @@ -517,7 +517,7 @@ static void bm_edge_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, BLI_assert(!"BMEdge: source and targer match"); return; } - CustomData_bmesh_free_block_data(&target_mesh->edata, &target_edge->head.data); + CustomData_bmesh_free_block_data(&target_mesh->edata, target_edge->head.data); CustomData_bmesh_copy_data(&source_mesh->edata, &target_mesh->edata, source_edge->head.data, &target_edge->head.data); } @@ -529,7 +529,7 @@ static void bm_loop_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, BLI_assert(!"BMLoop: source and targer match"); return; } - CustomData_bmesh_free_block_data(&target_mesh->ldata, &target_loop->head.data); + CustomData_bmesh_free_block_data(&target_mesh->ldata, target_loop->head.data); CustomData_bmesh_copy_data(&source_mesh->ldata, &target_mesh->ldata, source_loop->head.data, &target_loop->head.data); } @@ -542,7 +542,7 @@ static void bm_face_attrs_copy(BMesh *source_mesh, BMesh *target_mesh, return; } copy_v3_v3(target_face->no, source_face->no); - CustomData_bmesh_free_block_data(&target_mesh->pdata, &target_face->head.data); + CustomData_bmesh_free_block_data(&target_mesh->pdata, target_face->head.data); CustomData_bmesh_copy_data(&source_mesh->pdata, &target_mesh->pdata, source_face->head.data, &target_face->head.data); target_face->mat_nr = source_face->mat_nr; diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c index 1f942dad048..eb7b9f78ef4 100644 --- a/source/blender/bmesh/intern/bmesh_core.c +++ b/source/blender/bmesh/intern/bmesh_core.c @@ -1473,8 +1473,10 @@ BMVert *bmesh_semv(BMesh *bm, BMVert *tv, BMEdge *e, BMEdge **r_e) valence2 = bmesh_disk_count(tv); #endif + /* order of 'e_new' verts should match 'e' + * (so extruded faces don't flip) */ v_new = BM_vert_create(bm, tv->co, tv, BM_CREATE_NOP); - e_new = BM_edge_create(bm, v_new, tv, e, BM_CREATE_NOP); + e_new = BM_edge_create(bm, tv, v_new, e, BM_CREATE_NOP); bmesh_disk_edge_remove(e_new, tv); bmesh_disk_edge_remove(e_new, v_new); diff --git a/source/blender/bmesh/intern/bmesh_interp.c b/source/blender/bmesh/intern/bmesh_interp.c index 306b6e74350..a32f28169f6 100644 --- a/source/blender/bmesh/intern/bmesh_interp.c +++ b/source/blender/bmesh/intern/bmesh_interp.c @@ -54,7 +54,7 @@ static void bm_data_interp_from_elem(CustomData *data_layer, BMElem *ele1, BMEle /* do nothing */ } else { - CustomData_bmesh_free_block_data(data_layer, &ele_dst->head.data); + CustomData_bmesh_free_block_data(data_layer, ele_dst->head.data); CustomData_bmesh_copy_data(data_layer, data_layer, ele1->head.data, &ele_dst->head.data); } } @@ -63,7 +63,7 @@ static void bm_data_interp_from_elem(CustomData *data_layer, BMElem *ele1, BMEle /* do nothing */ } else { - CustomData_bmesh_free_block_data(data_layer, &ele_dst->head.data); + CustomData_bmesh_free_block_data(data_layer, ele_dst->head.data); CustomData_bmesh_copy_data(data_layer, data_layer, ele2->head.data, &ele_dst->head.data); } } diff --git a/source/blender/bmesh/intern/bmesh_iterators.c b/source/blender/bmesh/intern/bmesh_iterators.c index 91b9774634d..476878ad38c 100644 --- a/source/blender/bmesh/intern/bmesh_iterators.c +++ b/source/blender/bmesh/intern/bmesh_iterators.c @@ -338,50 +338,18 @@ int BM_iter_mesh_count_flag(const char itype, BMesh *bm, const char hflag, const # define USE_IMMUTABLE_ASSERT #endif -void bmiter__vert_of_mesh_begin(struct BMIter__vert_of_mesh *iter) +void bmiter__elem_of_mesh_begin(struct BMIter__elem_of_mesh *iter) { #ifdef USE_IMMUTABLE_ASSERT - ((BMIter *)iter)->count = iter->bm->totvert; + ((BMIter *)iter)->count = BLI_mempool_count(iter->pooliter.pool); #endif - BLI_mempool_iternew(iter->bm->vpool, &iter->pooliter); + BLI_mempool_iternew(iter->pooliter.pool, &iter->pooliter); } -void *bmiter__vert_of_mesh_step(struct BMIter__vert_of_mesh *iter) +void *bmiter__elem_of_mesh_step(struct BMIter__elem_of_mesh *iter) { #ifdef USE_IMMUTABLE_ASSERT - BLI_assert(((BMIter *)iter)->count <= iter->bm->totvert); -#endif - return BLI_mempool_iterstep(&iter->pooliter); -} - -void bmiter__edge_of_mesh_begin(struct BMIter__edge_of_mesh *iter) -{ -#ifdef USE_IMMUTABLE_ASSERT - ((BMIter *)iter)->count = iter->bm->totedge; -#endif - BLI_mempool_iternew(iter->bm->epool, &iter->pooliter); -} - -void *bmiter__edge_of_mesh_step(struct BMIter__edge_of_mesh *iter) -{ -#ifdef USE_IMMUTABLE_ASSERT - BLI_assert(((BMIter *)iter)->count <= iter->bm->totedge); -#endif - return BLI_mempool_iterstep(&iter->pooliter); -} - -void bmiter__face_of_mesh_begin(struct BMIter__face_of_mesh *iter) -{ -#ifdef USE_IMMUTABLE_ASSERT - ((BMIter *)iter)->count = iter->bm->totface; -#endif - BLI_mempool_iternew(iter->bm->fpool, &iter->pooliter); -} - -void *bmiter__face_of_mesh_step(struct BMIter__face_of_mesh *iter) -{ -#ifdef USE_IMMUTABLE_ASSERT - BLI_assert(((BMIter *)iter)->count <= iter->bm->totface); + BLI_assert(((BMIter *)iter)->count <= BLI_mempool_count(iter->pooliter.pool)); #endif return BLI_mempool_iterstep(&iter->pooliter); } diff --git a/source/blender/bmesh/intern/bmesh_iterators.h b/source/blender/bmesh/intern/bmesh_iterators.h index fdf0f27f05f..44be7072e71 100644 --- a/source/blender/bmesh/intern/bmesh_iterators.h +++ b/source/blender/bmesh/intern/bmesh_iterators.h @@ -110,16 +110,7 @@ extern const char bm_iter_itype_htype_map[BM_ITYPE_MAX]; for (ele = BM_iter_new(iter, NULL, itype, data), indexvar = 0; ele; ele = BM_iter_step(iter), (indexvar)++) /* iterator type structs */ -struct BMIter__vert_of_mesh { - BMesh *bm; - BLI_mempool_iter pooliter; -}; -struct BMIter__edge_of_mesh { - BMesh *bm; - BLI_mempool_iter pooliter; -}; -struct BMIter__face_of_mesh { - BMesh *bm; +struct BMIter__elem_of_mesh { BLI_mempool_iter pooliter; }; struct BMIter__edge_of_vert { @@ -173,9 +164,7 @@ typedef void *(*BMIter__step_cb) (void *); typedef struct BMIter { /* keep union first */ union { - struct BMIter__vert_of_mesh vert_of_mesh; - struct BMIter__edge_of_mesh edge_of_mesh; - struct BMIter__face_of_mesh face_of_mesh; + struct BMIter__elem_of_mesh elem_of_mesh; struct BMIter__edge_of_vert edge_of_vert; struct BMIter__face_of_vert face_of_vert; @@ -219,9 +208,7 @@ int BM_iter_mesh_count_flag(const char itype, BMesh *bm, const char hflag, c void bmiter__##name##_begin(struct BMIter__##name *iter); \ void *bmiter__##name##_step(struct BMIter__##name *iter) -BMITER_CB_DEF(vert_of_mesh); -BMITER_CB_DEF(edge_of_mesh); -BMITER_CB_DEF(face_of_mesh); +BMITER_CB_DEF(elem_of_mesh); BMITER_CB_DEF(edge_of_vert); BMITER_CB_DEF(face_of_vert); BMITER_CB_DEF(loop_of_vert); @@ -237,4 +224,12 @@ BMITER_CB_DEF(loop_of_face); #include "intern/bmesh_iterators_inline.h" +#define BM_ITER_CHECK_TYPE_DATA(data) \ + CHECK_TYPE_ANY(data, void *, BMFace *, BMEdge *, BMVert *, BMLoop *, BMElem *) + +#define BM_iter_new(iter, bm, itype, data) \ + (BM_ITER_CHECK_TYPE_DATA(data), BM_iter_new(iter, bm, itype, data)) +#define BM_iter_init(iter, bm, itype, data) \ + (BM_ITER_CHECK_TYPE_DATA(data), BM_iter_init(iter, bm, itype, data)) + #endif /* __BMESH_ITERATORS_H__ */ diff --git a/source/blender/bmesh/intern/bmesh_iterators_inline.h b/source/blender/bmesh/intern/bmesh_iterators_inline.h index b9733d4702f..d3e18b97acb 100644 --- a/source/blender/bmesh/intern/bmesh_iterators_inline.h +++ b/source/blender/bmesh/intern/bmesh_iterators_inline.h @@ -60,23 +60,23 @@ BLI_INLINE bool BM_iter_init(BMIter *iter, BMesh *bm, const char itype, void *da case BM_VERTS_OF_MESH: BLI_assert(bm != NULL); BLI_assert(data == NULL); - iter->begin = (BMIter__begin_cb)bmiter__vert_of_mesh_begin; - iter->step = (BMIter__step_cb)bmiter__vert_of_mesh_step; - iter->data.vert_of_mesh.bm = bm; + iter->begin = (BMIter__begin_cb)bmiter__elem_of_mesh_begin; + iter->step = (BMIter__step_cb)bmiter__elem_of_mesh_step; + iter->data.elem_of_mesh.pooliter.pool = bm->vpool; break; case BM_EDGES_OF_MESH: BLI_assert(bm != NULL); BLI_assert(data == NULL); - iter->begin = (BMIter__begin_cb)bmiter__edge_of_mesh_begin; - iter->step = (BMIter__step_cb)bmiter__edge_of_mesh_step; - iter->data.edge_of_mesh.bm = bm; + iter->begin = (BMIter__begin_cb)bmiter__elem_of_mesh_begin; + iter->step = (BMIter__step_cb)bmiter__elem_of_mesh_step; + iter->data.elem_of_mesh.pooliter.pool = bm->epool; break; case BM_FACES_OF_MESH: BLI_assert(bm != NULL); BLI_assert(data == NULL); - iter->begin = (BMIter__begin_cb)bmiter__face_of_mesh_begin; - iter->step = (BMIter__step_cb)bmiter__face_of_mesh_step; - iter->data.face_of_mesh.bm = bm; + iter->begin = (BMIter__begin_cb)bmiter__elem_of_mesh_begin; + iter->step = (BMIter__step_cb)bmiter__elem_of_mesh_step; + iter->data.elem_of_mesh.pooliter.pool = bm->fpool; break; case BM_EDGES_OF_VERT: BLI_assert(data != NULL); diff --git a/source/blender/bmesh/intern/bmesh_marking.c b/source/blender/bmesh/intern/bmesh_marking.c index 19e6f646564..ee35d8cd1d2 100644 --- a/source/blender/bmesh/intern/bmesh_marking.c +++ b/source/blender/bmesh/intern/bmesh_marking.c @@ -537,7 +537,7 @@ void BM_mesh_select_mode_set(BMesh *bm, int selectmode) * counts number of elements with flag enabled/disabled */ static int bm_mesh_flag_count(BMesh *bm, const char htype, const char hflag, - const short respecthide, const bool test_for_enabled) + const bool respecthide, const bool test_for_enabled) { BMElem *ele; BMIter iter; diff --git a/source/blender/bmesh/intern/bmesh_mods.c b/source/blender/bmesh/intern/bmesh_mods.c index 6e8591da0f3..72d25413f09 100644 --- a/source/blender/bmesh/intern/bmesh_mods.c +++ b/source/blender/bmesh/intern/bmesh_mods.c @@ -265,7 +265,8 @@ BMFace *BM_faces_join_pair(BMesh *bm, BMFace *f_a, BMFace *f_b, BMEdge *e, const * * \param bm The bmesh * \param f the original face - * \param v1, v2 vertices which define the split edge, must be different + * \param l_a, l_b Loops of this face, their vertices define + * the split edge to be created (must be differ and not can't be adjacent in the face). * \param r_l pointer which will receive the BMLoop for the split edge in the new face * \param example Edge used for attributes of splitting edge, if non-NULL * \param nodouble Use an existing edge if found @@ -348,7 +349,7 @@ BMFace *BM_face_split(BMesh *bm, BMFace *f, * \param l_a, l_b vertices which define the split edge, must be different * \param cos Array of coordinates for intermediate points * \param n Length of \a cos (must be > 0) - * \param r_l pointer which will receive the BMLoop for the first split edge (from \a v1) in the new face + * \param r_l pointer which will receive the BMLoop for the first split edge (from \a l_a) in the new face * \param example Edge used for attributes of splitting edge, if non-NULL * * \return Pointer to the newly created face representing one side of the split diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c index d8be55ce7c2..e2be90e7baf 100644 --- a/source/blender/bmesh/intern/bmesh_opdefines.c +++ b/source/blender/bmesh/intern/bmesh_opdefines.c @@ -104,6 +104,7 @@ static BMOpDefine bmo_smooth_vert_def = { "smooth_vert", /* slots_in */ {{"verts", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT}}, /* input vertices */ + {"factor", BMO_OP_SLOT_FLT}, /* smoothing factor */ {"mirror_clip_x", BMO_OP_SLOT_BOOL}, /* set vertices close to the x axis before the operation to 0 */ {"mirror_clip_y", BMO_OP_SLOT_BOOL}, /* set vertices close to the y axis before the operation to 0 */ {"mirror_clip_z", BMO_OP_SLOT_BOOL}, /* set vertices close to the z axis before the operation to 0 */ diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index 9a1914b5596..a8e1acd9c71 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -666,49 +666,25 @@ static bool line_crosses_v2f(const float v1[2], const float v2[2], const float v */ bool BM_face_point_inside_test(BMFace *f, const float co[3]) { - int ax, ay; - float co2[2], cent[2] = {0.0f, 0.0f}, out[2] = {FLT_MAX * 0.5f, FLT_MAX * 0.5f}; + float axis_mat[3][3]; + float (*projverts)[2] = BLI_array_alloca(projverts, f->len); + + float co_2d[2]; BMLoop *l_iter; - BMLoop *l_first; - int crosses = 0; - float onepluseps = 1.0f + (float)FLT_EPSILON * 150.0f; + int i; if (is_zero_v3(f->no)) BM_face_normal_update(f); - - /* find best projection of face XY, XZ or YZ: barycentric weights of - * the 2d projected coords are the same and faster to compute - * - * this probably isn't all that accurate, but it has the advantage of - * being fast (especially compared to projecting into the face orientation) - */ - axis_dominant_v3(&ax, &ay, f->no); - - co2[0] = co[ax]; - co2[1] = co[ay]; - - l_iter = l_first = BM_FACE_FIRST_LOOP(f); - do { - cent[0] += l_iter->v->co[ax]; - cent[1] += l_iter->v->co[ay]; - } while ((l_iter = l_iter->next) != l_first); - - mul_v2_fl(cent, 1.0f / (float)f->len); - - l_iter = l_first = BM_FACE_FIRST_LOOP(f); - do { - float v1[2], v2[2]; - - v1[0] = (l_iter->prev->v->co[ax] - cent[0]) * onepluseps + cent[0]; - v1[1] = (l_iter->prev->v->co[ay] - cent[1]) * onepluseps + cent[1]; - - v2[0] = (l_iter->v->co[ax] - cent[0]) * onepluseps + cent[0]; - v2[1] = (l_iter->v->co[ay] - cent[1]) * onepluseps + cent[1]; - - crosses += line_crosses_v2f(v1, v2, co2, out) != 0; - } while ((l_iter = l_iter->next) != l_first); - - return crosses % 2 != 0; + + axis_dominant_v3_to_m3(axis_mat, f->no); + + mul_v2_m3v3(co_2d, axis_mat, co); + + for (i = 0, l_iter = BM_FACE_FIRST_LOOP(f); i < f->len; i++, l_iter = l_iter->next) { + mul_v2_m3v3(projverts[i], axis_mat, l_iter->v->co); + } + + return isect_point_poly_v2(co_2d, (const float (*)[2])projverts, f->len, false); } /** diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c index 685e5443583..40e0356e14c 100644 --- a/source/blender/bmesh/intern/bmesh_queries.c +++ b/source/blender/bmesh/intern/bmesh_queries.c @@ -311,7 +311,7 @@ BMLoop *BM_vert_find_first_loop(BMVert *v) { BMEdge *e; - if (!v || !v->e) + if (!v->e) return NULL; e = bmesh_disk_faceedge_find_first(v->e, v); diff --git a/source/blender/bmesh/intern/bmesh_structure.c b/source/blender/bmesh/intern/bmesh_structure.c index d8313dab36f..3e8002c0192 100644 --- a/source/blender/bmesh/intern/bmesh_structure.c +++ b/source/blender/bmesh/intern/bmesh_structure.c @@ -108,6 +108,7 @@ bool bmesh_edge_swapverts(BMEdge *e, BMVert *v_orig, BMVert *v_new) * - #bmesh_radial_append * - #bmesh_radial_loop_remove * - #bmesh_radial_facevert_count + * - #bmesh_radial_facevert_check * - #bmesh_radial_faceloop_find_first * - #bmesh_radial_faceloop_find_next * - #bmesh_radial_validate @@ -265,7 +266,7 @@ BMEdge *bmesh_disk_faceedge_find_first(const BMEdge *e, const BMVert *v) { const BMEdge *e_find = e; do { - if (e_find->l && bmesh_radial_facevert_count(e_find->l, v)) { + if (e_find->l && bmesh_radial_facevert_check(e_find->l, v)) { return (BMEdge *)e_find; } } while ((e_find = bmesh_disk_edge_next(e_find, v)) != e); @@ -275,10 +276,10 @@ BMEdge *bmesh_disk_faceedge_find_first(const BMEdge *e, const BMVert *v) BMEdge *bmesh_disk_faceedge_find_next(const BMEdge *e, const BMVert *v) { - BMEdge *e_find = NULL; + BMEdge *e_find; e_find = bmesh_disk_edge_next(e, v); do { - if (e_find->l && bmesh_radial_facevert_count(e_find->l, v)) { + if (e_find->l && bmesh_radial_facevert_check(e_find->l, v)) { return e_find; } } while ((e_find = bmesh_disk_edge_next(e_find, v)) != e); @@ -455,6 +456,24 @@ int bmesh_radial_facevert_count(const BMLoop *l, const BMVert *v) return count; } +/** + * \brief RADIAL CHECK FACE VERT + * + * Quicker check for ``bmesh_radial_facevert_count(...) != 0`` + */ +bool bmesh_radial_facevert_check(const BMLoop *l, const BMVert *v) +{ + const BMLoop *l_iter; + l_iter = l; + do { + if (l_iter->v == v) { + return true; + } + } while ((l_iter = l_iter->radial_next) != l); + + return false; +} + /*****loop cycle functions, e.g. loops surrounding a face**** */ bool bmesh_loop_validate(BMFace *f) { diff --git a/source/blender/bmesh/intern/bmesh_structure.h b/source/blender/bmesh/intern/bmesh_structure.h index d2ad655ae75..29868194bbf 100644 --- a/source/blender/bmesh/intern/bmesh_structure.h +++ b/source/blender/bmesh/intern/bmesh_structure.h @@ -61,6 +61,7 @@ void bmesh_radial_loop_remove(BMLoop *l, BMEdge *e) ATTR_NONNULL(1); * just use member access l->radial_next, l->radial_prev now */ int bmesh_radial_facevert_count(const BMLoop *l, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +bool bmesh_radial_facevert_check(const BMLoop *l, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BMLoop *bmesh_radial_faceloop_find_first(const BMLoop *l, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BMLoop *bmesh_radial_faceloop_find_next(const BMLoop *l, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); BMLoop *bmesh_radial_faceloop_find_vert(const BMFace *f, const BMVert *v) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); diff --git a/source/blender/bmesh/operators/bmo_subdivide.c b/source/blender/bmesh/operators/bmo_subdivide.c index fc507cdbd21..0d9ce4b2731 100644 --- a/source/blender/bmesh/operators/bmo_subdivide.c +++ b/source/blender/bmesh/operators/bmo_subdivide.c @@ -32,6 +32,7 @@ #include "BLI_rand.h" #include "BLI_array.h" #include "BLI_noise.h" +#include "BLI_stack.h" #include "BKE_customdata.h" @@ -766,8 +767,7 @@ void bmo_subdivide_edges_exec(BMesh *bm, BMOperator *op) BMOpSlot *einput; const SubDPattern *pat; SubDParams params; - SubDFaceData *facedata = NULL; - BLI_array_declare(facedata); + BLI_Stack *facedata; BMIter viter, fiter, liter; BMVert *v, **verts = NULL; BMEdge *edge; @@ -782,7 +782,7 @@ void bmo_subdivide_edges_exec(BMesh *bm, BMOperator *op) BLI_array_declare(verts); float smooth, fractal, along_normal; bool use_sphere, use_single_edge, use_grid_fill, use_only_quads; - int cornertype, seed, i, j, matched, a, b, numcuts, totesel, smooth_falloff; + int cornertype, seed, i, j, a, b, numcuts, totesel, smooth_falloff; BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, SUBD_SPLIT); @@ -875,9 +875,12 @@ void bmo_subdivide_edges_exec(BMesh *bm, BMOperator *op) BM_EDGE, EDGE_PERCENT); + facedata = BLI_stack_new(sizeof(SubDFaceData), __func__); + BM_ITER_MESH (face, &fiter, bm, BM_FACES_OF_MESH) { BMEdge *e1 = NULL, *e2 = NULL; float vec1[3], vec2[3]; + bool matched = false; /* skip non-quads if requested */ if (use_only_quads && face->len != 4) @@ -891,8 +894,6 @@ void bmo_subdivide_edges_exec(BMesh *bm, BMOperator *op) BLI_array_grow_items(edges, face->len); BLI_array_grow_items(verts, face->len); - matched = 0; - totesel = 0; BM_ITER_ELEM_INDEX (l_new, &liter, face, BM_LOOPS_OF_FACE, i) { edges[i] = l_new->e; @@ -930,12 +931,13 @@ void bmo_subdivide_edges_exec(BMesh *bm, BMOperator *op) } } if (matched) { - BLI_array_grow_one(facedata); - b = BLI_array_count(facedata) - 1; - facedata[b].pat = pat; - facedata[b].start = verts[i]; - facedata[b].face = face; - facedata[b].totedgesel = totesel; + SubDFaceData *fd; + + fd = BLI_stack_push_r(facedata); + fd->pat = pat; + fd->start = verts[i]; + fd->face = face; + fd->totedgesel = totesel; BMO_elem_flag_enable(bm, face, SUBD_SPLIT); break; } @@ -966,15 +968,15 @@ void bmo_subdivide_edges_exec(BMesh *bm, BMOperator *op) } } if (matched) { - BLI_array_grow_one(facedata); - j = BLI_array_count(facedata) - 1; + SubDFaceData *fd; BMO_elem_flag_enable(bm, face, SUBD_SPLIT); - facedata[j].pat = pat; - facedata[j].start = verts[a]; - facedata[j].face = face; - facedata[j].totedgesel = totesel; + fd = BLI_stack_push_r(facedata); + fd->pat = pat; + fd->start = verts[a]; + fd->face = face; + fd->totedgesel = totesel; break; } } @@ -982,16 +984,16 @@ void bmo_subdivide_edges_exec(BMesh *bm, BMOperator *op) } if (!matched && totesel) { - BLI_array_grow_one(facedata); - j = BLI_array_count(facedata) - 1; + SubDFaceData *fd; BMO_elem_flag_enable(bm, face, SUBD_SPLIT); /* must initialize all members here */ - facedata[j].start = NULL; - facedata[j].pat = NULL; - facedata[j].totedgesel = totesel; - facedata[j].face = face; + fd = BLI_stack_push_r(facedata); + fd->start = NULL; + fd->pat = NULL; + fd->totedgesel = totesel; + fd->face = face; } } @@ -1009,16 +1011,17 @@ void bmo_subdivide_edges_exec(BMesh *bm, BMOperator *op) copy_v3_v3(v->co, co); } - i = 0; - for (i = 0; i < BLI_array_count(facedata); i++) { - face = facedata[i].face; + for (; !BLI_stack_is_empty(facedata); BLI_stack_discard(facedata)) { + SubDFaceData *fd = BLI_stack_peek(facedata); + + face = fd->face; /* figure out which pattern to use */ BLI_array_empty(verts); - pat = facedata[i].pat; + pat = fd->pat; - if (!pat && facedata[i].totedgesel == 2) { + if (!pat && fd->totedgesel == 2) { int vlen; /* ok, no pattern. we still may be able to do something */ @@ -1131,7 +1134,7 @@ void bmo_subdivide_edges_exec(BMesh *bm, BMOperator *op) a = 0; BM_ITER_ELEM_INDEX (l_new, &liter, face, BM_LOOPS_OF_FACE, j) { - if (l_new->v == facedata[i].start) { + if (l_new->v == fd->start) { a = j + 1; break; } @@ -1156,7 +1159,7 @@ void bmo_subdivide_edges_exec(BMesh *bm, BMOperator *op) BM_data_layer_free_n(bm, &bm->vdata, CD_SHAPEKEY, params.shape_info.tmpkey); - if (facedata) BLI_array_free(facedata); + BLI_stack_free(facedata); if (edges) BLI_array_free(edges); if (verts) BLI_array_free(verts); BLI_array_free(loops_split); diff --git a/source/blender/bmesh/operators/bmo_utils.c b/source/blender/bmesh/operators/bmo_utils.c index d2d1c0854de..a06d40c8c0f 100644 --- a/source/blender/bmesh/operators/bmo_utils.c +++ b/source/blender/bmesh/operators/bmo_utils.c @@ -291,6 +291,7 @@ void bmo_smooth_vert_exec(BMesh *UNUSED(bm), BMOperator *op) BMEdge *e; float (*cos)[3] = MEM_mallocN(sizeof(*cos) * BMO_slot_buffer_count(op->slots_in, "verts"), __func__); float *co, *co2, clip_dist = BMO_slot_float_get(op->slots_in, "clip_dist"); + const float fac = BMO_slot_float_get(op->slots_in, "factor"); int i, j, clipx, clipy, clipz; int xaxis, yaxis, zaxis; @@ -322,7 +323,7 @@ void bmo_smooth_vert_exec(BMesh *UNUSED(bm), BMOperator *op) } mul_v3_fl(co, 1.0f / (float)j); - mid_v3_v3v3(co, co, v->co); + interp_v3_v3v3(co, v->co, co, fac); if (clipx && fabsf(v->co[0]) <= clip_dist) co[0] = 0.0f; diff --git a/source/blender/bmesh/tools/bmesh_bisect_plane.c b/source/blender/bmesh/tools/bmesh_bisect_plane.c index ae9b882cea0..ed9e8783037 100644 --- a/source/blender/bmesh/tools/bmesh_bisect_plane.c +++ b/source/blender/bmesh/tools/bmesh_bisect_plane.c @@ -53,7 +53,7 @@ /* -------------------------------------------------------------------- */ /* Math utils */ -static int plane_point_test_v3(const float plane[4], const float co[3], const float eps, float *r_depth) +static short plane_point_test_v3(const float plane[4], const float co[3], const float eps, float *r_depth) { const float f = plane_point_side_v3(plane, co); *r_depth = f; @@ -69,7 +69,8 @@ static int plane_point_test_v3(const float plane[4], const float co[3], const fl * later we may want to move this into some hash lookup * to a separate struct, but for now we can store in BMesh data */ -#define BM_VERT_DIR(v) ((v)->head.index) /* Direction -1/0/1 */ +#define BM_VERT_DIR(v) ((short *)(&(v)->head.index))[0] /* Direction -1/0/1 */ +#define BM_VERT_SKIP(v) ((short *)(&(v)->head.index))[1] /* Skip Vert 0/1 */ #define BM_VERT_DIST(v) ((v)->no[0]) /* Distance from the plane. */ #define BM_VERT_SORTVAL(v) ((v)->no[1]) /* Temp value for sorting. */ #define BM_VERT_LOOPINDEX(v) /* The verts index within a face (temp var) */ \ @@ -117,6 +118,7 @@ static void bm_face_bisect_verts(BMesh *bm, BMFace *f, const float plane[4], con STACK_DECLARE(vert_split_arr); BMLoop *l_iter, *l_first; bool use_dirs[3] = {false, false, false}; + bool is_inside = false; STACK_INIT(vert_split_arr, f_len_orig); @@ -129,6 +131,11 @@ static void bm_face_bisect_verts(BMesh *bm, BMFace *f, const float plane[4], con do { if (vert_is_center_test(l_iter->v)) { BLI_assert(BM_VERT_DIR(l_iter->v) == 0); + + /* if both are -1 or 1, or both are zero: + * don't flip 'inside' var while walking */ + BM_VERT_SKIP(l_iter->v) = (((BM_VERT_DIR(l_iter->prev->v) ^ BM_VERT_DIR(l_iter->next->v))) == 0); + STACK_PUSH(vert_split_arr, l_iter->v); } use_dirs[BM_VERT_DIR(l_iter->v) + 1] = true; @@ -230,15 +237,12 @@ static void bm_face_bisect_verts(BMesh *bm, BMFace *f, const float plane[4], con for (i = 0; i < STACK_SIZE(vert_split_arr) - 1; i++) { BMVert *v_a = vert_split_arr[i]; BMVert *v_b = vert_split_arr[i + 1]; - float co_mid[2]; - /* geometric test before doing face lookups, - * find if the split spans a filled region of the polygon. */ - mid_v2_v2v2(co_mid, - face_verts_proj_2d[BM_VERT_LOOPINDEX(v_a)], - face_verts_proj_2d[BM_VERT_LOOPINDEX(v_b)]); + if (!BM_VERT_SKIP(v_a)) { + is_inside = !is_inside; + } - if (isect_point_poly_v2(co_mid, (const float (*)[2])face_verts_proj_2d, f_len_orig, false)) { + if (is_inside) { BMLoop *l_a, *l_b; bool found = false; unsigned int j; @@ -254,7 +258,8 @@ static void bm_face_bisect_verts(BMesh *bm, BMFace *f, const float plane[4], con } } - BLI_assert(found == true); + /* ideally wont happen, but it can for self intersecting faces */ + // BLI_assert(found == true); /* in fact this simple test is good enough, * test if the loops are adjacent */ diff --git a/source/blender/bmesh/tools/bmesh_region_match.c b/source/blender/bmesh/tools/bmesh_region_match.c new file mode 100644 index 00000000000..050d5ae4808 --- /dev/null +++ b/source/blender/bmesh/tools/bmesh_region_match.c @@ -0,0 +1,1511 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/bmesh/tools/bmesh_region_match.c + * \ingroup bmesh + * + * 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). + */ + +#include <string.h> + +#include "MEM_guardedalloc.h" +#include "BLI_listbase.h" +#include "BLI_linklist.h" +#include "BLI_alloca.h" +#include "BLI_ghash.h" +#include "BLI_mempool.h" +#include "BLI_linklist_stack.h" + +#include "bmesh.h" + +#include "tools/bmesh_region_match.h" /* own incldue */ + +/* avoid re-creating ghash and pools for each search */ +#define USE_WALKER_REUSE + +/* do a first-pass id of all vertices, + * this avoids expensive checks on every item later on + * (works fine without, just slower) */ +#define USE_PIVOT_FASTMATCH + +/* otherwise use active element as pivot, for quick tests only */ +#define USE_PIVOT_SEARCH + +// #define DEBUG_TIME +// #define DEBUG_PRINT + +#ifdef DEBUG_TIME +# include "PIL_time.h" +# include "PIL_time_utildefines.h" +#endif + +#include "BLI_strict_flags.h" + + +/* -------------------------------------------------------------------- */ +/* UUID-Walk API */ + +/** \name Internal UUIDWalk API + * \{ */ + +#define PRIME_VERT_INIT 100003 + +typedef uintptr_t UUID_Int; + +typedef struct UUIDWalk { + + /* List of faces we can step onto (UUIDFaceStep's) */ + ListBase faces_step; + + /* Face & Vert UUID's */ + GHash *verts_uuid; + GHash *faces_uuid; + + /* memory pool for LinkNode's */ + BLI_mempool *link_pool; + + /* memory pool for LinkBase's */ + BLI_mempool *lbase_pool; + + /* memory pool for UUIDFaceStep's */ + BLI_mempool *step_pool; + BLI_mempool *step_pool_items; + + /* Optionaly use face-tag to isolate search */ + bool use_face_isolate; + + /* Increment for each pass added */ + UUID_Int pass; + + /* runtime vars, aviod re-creating each pass */ + struct { + GHash *verts_uuid; /* BMVert -> UUID */ + GSet *faces_step; /* BMFace */ + + GHash *faces_from_uuid; /* UUID -> UUIDFaceStepItem */ + + UUID_Int *rehash_store; + unsigned int rehash_store_len; + } cache; + +} UUIDWalk; + +/* stores a set of potential faces to step onto */ +typedef struct UUIDFaceStep { + struct UUIDFaceStep *next, *prev; + + /* unsorted 'BMFace' */ + LinkNode *faces; + + /* faces sorted into 'UUIDFaceStepItem' */ + ListBase items; +} UUIDFaceStep; + +/* store face-lists with same uuid */ +typedef struct UUIDFaceStepItem { + struct UUIDFaceStepItem *next, *prev; + uintptr_t uuid; + + LinkNode *list; + unsigned int list_len; +} UUIDFaceStepItem; + +BLI_INLINE bool bm_uuidwalk_face_test( + UUIDWalk *uuidwalk, BMFace *f) +{ + if (uuidwalk->use_face_isolate) { + return BM_elem_flag_test_bool(f, BM_ELEM_TAG); + } + else { + return true; + } +} + +BLI_INLINE bool bm_uuidwalk_vert_lookup( + UUIDWalk *uuidwalk, BMVert *v, UUID_Int *r_uuid) +{ + void **ret; + ret = BLI_ghash_lookup_p(uuidwalk->verts_uuid, v); + if (ret) { + *r_uuid = (UUID_Int)(*ret); + return true; + } + else { + return false; + } +} + +BLI_INLINE bool bm_uuidwalk_face_lookup( + UUIDWalk *uuidwalk, BMFace *f, UUID_Int *r_uuid) +{ + void **ret; + ret = BLI_ghash_lookup_p(uuidwalk->faces_uuid, f); + if (ret) { + *r_uuid = (UUID_Int)(*ret); + return true; + } + else { + return false; + } +} + +static unsigned int ghashutil_bmelem_indexhash(const void *key) +{ + const BMElem *ele = key; + return (unsigned int)BM_elem_index_get(ele); +} + +static bool ghashutil_bmelem_indexcmp(const void *a, const void *b) +{ + BLI_assert((a != b) == (BM_elem_index_get((BMElem *)a) != BM_elem_index_get((BMElem *)b))); + return (a != b); +} + +static GHash *ghash_bmelem_new_ex(const char *info, + const unsigned int nentries_reserve) +{ + return BLI_ghash_new_ex(ghashutil_bmelem_indexhash, ghashutil_bmelem_indexcmp, info, nentries_reserve); +} + +static GSet *gset_bmelem_new_ex(const char *info, + const unsigned int nentries_reserve) +{ + return BLI_gset_new_ex(ghashutil_bmelem_indexhash, ghashutil_bmelem_indexcmp, info, nentries_reserve); +} + + +static GHash *ghash_bmelem_new(const char *info) +{ + return ghash_bmelem_new_ex(info, 0); +} + +static GSet *gset_bmelem_new(const char *info) +{ + return gset_bmelem_new_ex(info, 0); +} + + +static void bm_uuidwalk_init( + UUIDWalk *uuidwalk, + const unsigned int faces_src_region_len, + const unsigned int verts_src_region_len) +{ + BLI_listbase_clear(&uuidwalk->faces_step); + + uuidwalk->verts_uuid = ghash_bmelem_new_ex(__func__, verts_src_region_len); + uuidwalk->faces_uuid = ghash_bmelem_new_ex(__func__, faces_src_region_len); + + uuidwalk->cache.verts_uuid = ghash_bmelem_new(__func__); + uuidwalk->cache.faces_step = gset_bmelem_new(__func__); + + /* works because 'int' ghash works for intptr_t too */ + uuidwalk->cache.faces_from_uuid = BLI_ghash_int_new(__func__); + + uuidwalk->cache.rehash_store = NULL; + uuidwalk->cache.rehash_store_len = 0; + + uuidwalk->use_face_isolate = false; + + /* smaller pool's for faster clearing */ + uuidwalk->link_pool = BLI_mempool_create(sizeof(LinkNode), 64, 64, BLI_MEMPOOL_NOP); + uuidwalk->step_pool = BLI_mempool_create(sizeof(UUIDFaceStep), 64, 64, BLI_MEMPOOL_NOP); + uuidwalk->step_pool_items = BLI_mempool_create(sizeof(UUIDFaceStepItem), 64, 64, BLI_MEMPOOL_NOP); + + uuidwalk->pass = 1; +} + +static void bm_uuidwalk_clear( + UUIDWalk *uuidwalk) +{ + BLI_listbase_clear(&uuidwalk->faces_step); + + BLI_ghash_clear(uuidwalk->verts_uuid, NULL, NULL); + BLI_ghash_clear(uuidwalk->faces_uuid, NULL, NULL); + + BLI_ghash_clear(uuidwalk->cache.verts_uuid, NULL, NULL); + BLI_gset_clear(uuidwalk->cache.faces_step, NULL); + BLI_ghash_clear(uuidwalk->cache.faces_from_uuid, NULL, NULL); + + /* keep rehash_store as-is, for reuse */ + + uuidwalk->use_face_isolate = false; + + BLI_mempool_clear(uuidwalk->link_pool); + BLI_mempool_clear(uuidwalk->step_pool); + BLI_mempool_clear(uuidwalk->step_pool_items); + + uuidwalk->pass = 1; +} + +static void bm_uuidwalk_free( + UUIDWalk *uuidwalk) +{ + /** + * Handled by pools + * + * - uuidwalk->faces_step + */ + + BLI_ghash_free(uuidwalk->verts_uuid, NULL, NULL); + BLI_ghash_free(uuidwalk->faces_uuid, NULL, NULL); + + /* cache */ + BLI_ghash_free(uuidwalk->cache.verts_uuid, NULL, NULL); + BLI_gset_free(uuidwalk->cache.faces_step, NULL); + BLI_ghash_free(uuidwalk->cache.faces_from_uuid, NULL, NULL); + MEM_SAFE_FREE(uuidwalk->cache.rehash_store); + + BLI_mempool_destroy(uuidwalk->link_pool); + BLI_mempool_destroy(uuidwalk->step_pool); + BLI_mempool_destroy(uuidwalk->step_pool_items); +} + +static UUID_Int bm_uuidwalk_calc_vert_uuid( + UUIDWalk *uuidwalk, BMVert *v) +{ +#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 + + UUID_Int uuid; + + uuid = uuidwalk->pass * PRIME_VERT_LARGE; + + /* vert -> other */ + { + unsigned int tot = 0; + BMIter eiter; + BMEdge *e; + BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { + BMVert *v_other = BM_edge_other_vert(e, v); + UUID_Int uuid_other; + if (bm_uuidwalk_vert_lookup(uuidwalk, v_other, &uuid_other)) { + uuid ^= (uuid_other * PRIME_VERT_SMALL); + tot += 1; + } + } + uuid ^= (tot * PRIME_VERT_MID); + } + + /* faces */ + { + unsigned int tot = 0; + BMIter iter; + BMFace *f; + + BM_ITER_ELEM (f, &iter, v, BM_FACES_OF_VERT) { + UUID_Int uuid_other; + if (bm_uuidwalk_face_lookup(uuidwalk, f, &uuid_other)) { + uuid ^= (uuid_other * PRIME_FACE_SMALL); + tot += 1; + } + } + uuid ^= (tot * PRIME_FACE_MID); + } + + return uuid; + +#undef PRIME_VERT_SMALL +#undef PRIME_VERT_MID +#undef PRIME_VERT_LARGE + +#undef PRIME_FACE_SMALL +#undef PRIME_FACE_MID +} + +static UUID_Int bm_uuidwalk_calc_face_uuid( + UUIDWalk *uuidwalk, BMFace *f) +{ +#define PRIME_VERT_SMALL 11 + +#define PRIME_FACE_SMALL 17 +#define PRIME_FACE_LARGE 1013 + + UUID_Int uuid; + + uuid = uuidwalk->pass * (unsigned int)f->len * PRIME_FACE_LARGE; + + /* face-verts */ + { + BMLoop *l_iter, *l_first; + + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + UUID_Int uuid_other; + if (bm_uuidwalk_vert_lookup(uuidwalk, l_iter->v, &uuid_other)) { + uuid ^= (uuid_other * PRIME_VERT_SMALL); + } + } while ((l_iter = l_iter->next) != l_first); + } + + /* face-faces (connected by edge) */ + { + BMLoop *l_iter, *l_first; + + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + if (l_iter->radial_next != l_iter) { + BMLoop *l_iter_radial = l_iter->radial_next; + do { + UUID_Int uuid_other; + if (bm_uuidwalk_face_lookup(uuidwalk, l_iter_radial->f, &uuid_other)) { + uuid ^= (uuid_other * PRIME_FACE_SMALL); + } + } while ((l_iter_radial = l_iter_radial->radial_next) != l_iter); + } + } while ((l_iter = l_iter->next) != l_first); + } + + return uuid; + +#undef PRIME_VERT_SMALL + +#undef PRIME_FACE_SMALL +#undef PRIME_FACE_LARGE +} + +static void bm_uuidwalk_rehash_reserve( + UUIDWalk *uuidwalk, unsigned int rehash_store_len_new) +{ + if (UNLIKELY(rehash_store_len_new > uuidwalk->cache.rehash_store_len)) { + /* avoid re-allocs */ + rehash_store_len_new *= 2; + uuidwalk->cache.rehash_store = + MEM_reallocN(uuidwalk->cache.rehash_store, + rehash_store_len_new * sizeof(*uuidwalk->cache.rehash_store)); + uuidwalk->cache.rehash_store_len = rehash_store_len_new; + } +} + +/** + * Re-hash all elements, delay updating so as not to create feedback loop. + */ +static void bm_uuidwalk_rehash( + UUIDWalk *uuidwalk) +{ + GHashIterator gh_iter; + UUID_Int *uuid_store; + unsigned int i; + + unsigned int rehash_store_len_new = (unsigned int)MAX2(BLI_ghash_size(uuidwalk->verts_uuid), + BLI_ghash_size(uuidwalk->faces_uuid)); + + bm_uuidwalk_rehash_reserve(uuidwalk, rehash_store_len_new); + uuid_store = uuidwalk->cache.rehash_store; + + /* verts */ + i = 0; + GHASH_ITER (gh_iter, uuidwalk->verts_uuid) { + BMVert *v = BLI_ghashIterator_getKey(&gh_iter); + uuid_store[i++] = bm_uuidwalk_calc_vert_uuid(uuidwalk, v); + } + i = 0; + GHASH_ITER (gh_iter, uuidwalk->verts_uuid) { + void **uuid_p = BLI_ghashIterator_getValue_p(&gh_iter); + *((UUID_Int *)uuid_p) = uuid_store[i++]; + } + + /* faces */ + i = 0; + GHASH_ITER (gh_iter, uuidwalk->faces_uuid) { + BMFace *f = BLI_ghashIterator_getKey(&gh_iter); + uuid_store[i++] = bm_uuidwalk_calc_face_uuid(uuidwalk, f); + } + i = 0; + GHASH_ITER (gh_iter, uuidwalk->faces_uuid) { + void **uuid_p = BLI_ghashIterator_getValue_p(&gh_iter); + *((UUID_Int *)uuid_p) = uuid_store[i++]; + } +} + +static void bm_uuidwalk_rehash_facelinks( + UUIDWalk *uuidwalk, + LinkNode *faces, const unsigned int faces_len, + const bool is_init) +{ + UUID_Int *uuid_store; + LinkNode *f_link; + unsigned int i; + + bm_uuidwalk_rehash_reserve(uuidwalk, faces_len); + uuid_store = uuidwalk->cache.rehash_store; + + i = 0; + for (f_link = faces; f_link; f_link = f_link->next) { + BMFace *f = f_link->link; + uuid_store[i++] = bm_uuidwalk_calc_face_uuid(uuidwalk, f); + } + + i = 0; + if (is_init) { + for (f_link = faces; f_link; f_link = f_link->next) { + BMFace *f = f_link->link; + BLI_ghash_insert(uuidwalk->faces_uuid, f, (void *)uuid_store[i++]); + } + } + else { + for (f_link = faces; f_link; f_link = f_link->next) { + BMFace *f = f_link->link; + void **uuid_p = BLI_ghash_lookup_p(uuidwalk->faces_uuid, f); + *((UUID_Int *)uuid_p) = uuid_store[i++]; + } + } +} + +static bool bm_vert_is_uuid_connect( + UUIDWalk *uuidwalk, BMVert *v) +{ + BMIter eiter; + BMEdge *e; + + BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { + BMVert *v_other = BM_edge_other_vert(e, v); + if (BLI_ghash_haskey(uuidwalk->verts_uuid, v_other)) { + return true; + } + } + return false; +} + +static void bm_uuidwalk_pass_add( + UUIDWalk *uuidwalk, LinkNode *faces_pass, const unsigned int faces_pass_len) +{ + GHashIterator gh_iter; + GHash *verts_uuid_pass; + GSet *faces_step_next; + LinkNode *f_link; + + UUIDFaceStep *fstep; + + BLI_assert(faces_pass_len == (unsigned int)BLI_linklist_length(faces_pass)); + + /* rehash faces now all their verts have been added */ + bm_uuidwalk_rehash_facelinks(uuidwalk, faces_pass, faces_pass_len, true); + + /* create verts_new */ + verts_uuid_pass = uuidwalk->cache.verts_uuid; + faces_step_next = uuidwalk->cache.faces_step; + + BLI_assert(BLI_ghash_size(verts_uuid_pass) == 0); + BLI_assert(BLI_gset_size(faces_step_next) == 0); + + /* Add the face_step data from connected faces, creating new passes */ + fstep = BLI_mempool_alloc(uuidwalk->step_pool); + BLI_addhead(&uuidwalk->faces_step, fstep); + fstep->faces = NULL; + BLI_listbase_clear(&fstep->items); + + for (f_link = faces_pass; f_link; f_link = f_link->next) { + BMFace *f = f_link->link; + BMLoop *l_iter, *l_first; + + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + /* fill verts_new */ + if (!BLI_ghash_haskey(uuidwalk->verts_uuid, l_iter->v) && + !BLI_ghash_haskey(verts_uuid_pass, l_iter->v) && + (bm_vert_is_uuid_connect(uuidwalk, l_iter->v) == true)) + { + const UUID_Int uuid = bm_uuidwalk_calc_vert_uuid(uuidwalk, l_iter->v); + BLI_ghash_insert(verts_uuid_pass, l_iter->v, (void *)uuid); + } + + /* fill faces_step_next */ + if (l_iter->radial_next != l_iter) { + BMLoop *l_iter_radial = l_iter->radial_next; + do { + if (!BLI_ghash_haskey(uuidwalk->faces_uuid, l_iter_radial->f) && + !BLI_gset_haskey(faces_step_next, l_iter_radial->f) && + (bm_uuidwalk_face_test(uuidwalk, l_iter_radial->f))) + { + BLI_gset_insert(faces_step_next, l_iter_radial->f); + + /* add to fstep */ + BLI_linklist_prepend_pool(&fstep->faces, l_iter_radial->f, uuidwalk->link_pool); + } + } while ((l_iter_radial = l_iter_radial->radial_next) != l_iter); + } + } while ((l_iter = l_iter->next) != l_first); + } + + /* faces_uuid.update(verts_new) */ + GHASH_ITER (gh_iter, verts_uuid_pass) { + BMVert *v = BLI_ghashIterator_getKey(&gh_iter); + void *uuid_p = BLI_ghashIterator_getValue(&gh_iter); + BLI_ghash_insert(uuidwalk->verts_uuid, v, uuid_p); + } + + /* rehash faces now all their verts have been added */ + bm_uuidwalk_rehash_facelinks(uuidwalk, faces_pass, faces_pass_len, false); + + uuidwalk->pass += 1; + + BLI_ghash_clear(uuidwalk->cache.verts_uuid, NULL, NULL); + BLI_gset_clear(uuidwalk->cache.faces_step, NULL); +} + +static int bm_face_len_cmp(const void *v1, const void *v2) +{ + const BMFace *f1 = v1, *f2 = v2; + + if (f1->len > f2->len) return 1; + else if (f1->len < f2->len) return -1; + else return 0; +} + +static unsigned int bm_uuidwalk_init_from_edge( + UUIDWalk *uuidwalk, BMEdge *e) +{ + BMLoop *l_iter = e->l; + unsigned int f_arr_len = (unsigned int)BM_edge_face_count(e); + BMFace **f_arr = BLI_array_alloca(f_arr, f_arr_len); + unsigned int fstep_num = 0, i = 0; + + do { + BMFace *f = l_iter->f; + if (bm_uuidwalk_face_test(uuidwalk, f)) { + f_arr[i++] = f; + } + } while ((l_iter = l_iter->radial_next) != e->l); + BLI_assert(i <= f_arr_len); + f_arr_len = i; + + qsort(f_arr, f_arr_len, sizeof(*f_arr), bm_face_len_cmp); + + /* start us off! */ + { + const UUID_Int uuid = PRIME_VERT_INIT; + BLI_ghash_insert(uuidwalk->verts_uuid, e->v1, (void *)uuid); + BLI_ghash_insert(uuidwalk->verts_uuid, e->v2, (void *)uuid); + } + + /* turning an array into LinkNode's seems odd, + * but this is just for initialization, + * elsewhere using LinkNode's makes more sense */ + for (i = 0; i < f_arr_len; i++) { + LinkNode *faces_pass = NULL; + const int f_len = f_arr[i]->len; + + do { + BLI_linklist_prepend_pool(&faces_pass, f_arr[i++], uuidwalk->link_pool); + } while (i < f_arr_len && (f_len == f_arr[i]->len)); + + bm_uuidwalk_pass_add(uuidwalk, faces_pass, i); + BLI_linklist_free_pool(faces_pass, NULL, uuidwalk->link_pool); + fstep_num += 1; + } + + return fstep_num; +} + +#undef PRIME_VERT_INIT + +/** \} */ + + +/** \name Internal UUIDFaceStep API + * \{ */ + +static int facestep_sort(const void *a, const void *b) +{ + const UUIDFaceStepItem *fstep_a = a; + const UUIDFaceStepItem *fstep_b = b; + return (fstep_a->uuid > fstep_b->uuid) ? 1 : 0; +} + +/** + * Put faces in lists based on their uuid's, + * re-run for each pass since rehashing may differentiate face-groups. + */ +static bool bm_uuidwalk_facestep_begin( + UUIDWalk *uuidwalk, UUIDFaceStep *fstep) +{ + LinkNode *f_link, *f_link_next, **f_link_prev_p; + bool ok = false; + + BLI_assert(BLI_ghash_size(uuidwalk->cache.faces_from_uuid) == 0); + BLI_assert(BLI_countlist(&fstep->items) == 0); + + f_link_prev_p = &fstep->faces; + for (f_link = fstep->faces; f_link; f_link = f_link_next) { + BMFace *f = f_link->link; + f_link_next = f_link->next; + + /* possible another pass added this face already, free in that case */ + if (!BLI_ghash_haskey(uuidwalk->faces_uuid, f)) { + const UUID_Int uuid = bm_uuidwalk_calc_face_uuid(uuidwalk, f); + UUIDFaceStepItem *fstep_item; + + ok = true; + + fstep_item = BLI_ghash_lookup(uuidwalk->cache.faces_from_uuid, (void *)uuid); + if (UNLIKELY(fstep_item == NULL)) { + fstep_item = BLI_mempool_alloc(uuidwalk->step_pool_items); + BLI_ghash_insert(uuidwalk->cache.faces_from_uuid, (void *)uuid, fstep_item); + + /* add to start, so its handled on the next round of passes */ + BLI_addhead(&fstep->items, fstep_item); + fstep_item->uuid = uuid; + fstep_item->list = NULL; + fstep_item->list_len = 0; + } + + BLI_linklist_prepend_pool(&fstep_item->list, f, uuidwalk->link_pool); + fstep_item->list_len += 1; + + f_link_prev_p = &f_link->next; + } + else { + *f_link_prev_p = f_link->next; + BLI_mempool_free(uuidwalk->link_pool, f_link); + } + } + + BLI_ghash_clear(uuidwalk->cache.faces_from_uuid, NULL, NULL); + + BLI_sortlist(&fstep->items, facestep_sort); + + return ok; +} + +/** + * Cleans up temp data from #bm_uuidwalk_facestep_begin + */ +static void bm_uuidwalk_facestep_end( + UUIDWalk *uuidwalk, UUIDFaceStep *fstep) +{ + UUIDFaceStepItem *fstep_item; + + while ((fstep_item = BLI_pophead(&fstep->items))) { + BLI_mempool_free(uuidwalk->step_pool_items, fstep_item); + } +} + +static void bm_uuidwalk_facestep_free( + UUIDWalk *uuidwalk, UUIDFaceStep *fstep) +{ + LinkNode *f_link, *f_link_next; + + BLI_assert(BLI_listbase_is_empty(&fstep->items)); + + for (f_link = fstep->faces; f_link; f_link = f_link_next) { + f_link_next = f_link->next; + BLI_mempool_free(uuidwalk->link_pool, f_link); + } + + BLI_remlink(&uuidwalk->faces_step, fstep); + BLI_mempool_free(uuidwalk->step_pool, fstep); +} + +/** \} */ + + +/* -------------------------------------------------------------------- */ +/* Main Loop to match up regions */ + +/** + * Given a face region and 2 candidate verts to begin mapping. + * return the matching region or NULL. + */ +static BMFace **bm_mesh_region_match_pair( +#ifdef USE_WALKER_REUSE + UUIDWalk *w_src, UUIDWalk *w_dst, +#endif + BMEdge *e_src, BMEdge *e_dst, + const unsigned int faces_src_region_len, + const unsigned int verts_src_region_len, + unsigned int *r_faces_result_len) +{ +#ifndef USE_WALKER_REUSE + UUIDWalk w_src_, w_dst_; + UUIDWalk *w_src = &w_src_, *w_dst = &w_dst_; +#endif + BMFace **faces_result = NULL; + bool found = false; + + BLI_assert(e_src != e_dst); + +#ifndef USE_WALKER_REUSE + bm_uuidwalk_init(w_src, faces_src_region_len, verts_src_region_len); + bm_uuidwalk_init(w_dst, faces_src_region_len, verts_src_region_len); +#endif + + w_src->use_face_isolate = true; + + /* setup the initial state */ + if (UNLIKELY(bm_uuidwalk_init_from_edge(w_src, e_src) != + bm_uuidwalk_init_from_edge(w_dst, e_dst))) + { + /* should never happen, if verts passed are compatible, but to be safe... */ + goto finally; + } + + bm_uuidwalk_rehash_reserve(w_src, MAX2(faces_src_region_len, verts_src_region_len)); + bm_uuidwalk_rehash_reserve(w_dst, MAX2(faces_src_region_len, verts_src_region_len)); + + while (true) { + bool ok = false; + + UUIDFaceStep *fstep_src = w_src->faces_step.first; + UUIDFaceStep *fstep_dst = w_dst->faces_step.first; + + BLI_assert(BLI_countlist(&w_src->faces_step) == BLI_countlist(&w_dst->faces_step)); + + while (fstep_src) { + + /* even if the destination has faces, + * it's not important, since the source doesn't, free and move-on. */ + if (fstep_src->faces == NULL) { + UUIDFaceStep *fstep_src_next = fstep_src->next; + UUIDFaceStep *fstep_dst_next = fstep_dst->next; + bm_uuidwalk_facestep_free(w_src, fstep_src); + bm_uuidwalk_facestep_free(w_dst, fstep_dst); + fstep_src = fstep_src_next; + fstep_dst = fstep_dst_next; + continue; + } + + if (bm_uuidwalk_facestep_begin(w_src, fstep_src) && + bm_uuidwalk_facestep_begin(w_dst, fstep_dst)) + { + /* Step over face-lists with matching UUID's + * both lists are sorted, so no need for lookups. + * The data is created on 'begin' and cleared on 'end' */ + UUIDFaceStepItem *fstep_item_src; + UUIDFaceStepItem *fstep_item_dst; + for (fstep_item_src = fstep_src->items.first, + fstep_item_dst = fstep_dst->items.first; + fstep_item_src && fstep_item_dst; + fstep_item_src = fstep_item_src->next, + fstep_item_dst = fstep_item_dst->next) + { + while ((fstep_item_dst != NULL) && + (fstep_item_dst->uuid < fstep_item_src->uuid)) + { + fstep_item_dst = fstep_item_dst->next; + } + + if ((fstep_item_dst == NULL) || + (fstep_item_src->uuid != fstep_item_dst->uuid) || + (fstep_item_src->list_len > fstep_item_dst->list_len)) + { + /* if the target walker has less than the source + * then the islands don't match, bail early */ + ok = false; + break; + } + + if (fstep_item_src->list_len == fstep_item_dst->list_len) { + /* found a match */ + bm_uuidwalk_pass_add(w_src, fstep_item_src->list, fstep_item_src->list_len); + bm_uuidwalk_pass_add(w_dst, fstep_item_dst->list, fstep_item_dst->list_len); + + BLI_linklist_free_pool(fstep_item_src->list, NULL, w_src->link_pool); + BLI_linklist_free_pool(fstep_item_dst->list, NULL, w_dst->link_pool); + + fstep_item_src->list = NULL; + fstep_item_src->list_len = 0; + + fstep_item_dst->list = NULL; + fstep_item_dst->list_len = 0; + + ok = true; + } + } + } + + bm_uuidwalk_facestep_end(w_src, fstep_src); + bm_uuidwalk_facestep_end(w_dst, fstep_dst); + + /* lock-step */ + fstep_src = fstep_src->next; + fstep_dst = fstep_dst->next; + } + + if (!ok) { + break; + } + + found = ((unsigned int)BLI_ghash_size(w_dst->faces_uuid) == faces_src_region_len); + if (found) { + break; + } + + /* Expensive! but some cases fails without. + * (also faster in other cases since it can rule-out invalid regions) */ + bm_uuidwalk_rehash(w_src); + bm_uuidwalk_rehash(w_dst); + } + + if (found) { + GHashIterator gh_iter; + const unsigned int faces_result_len = (unsigned int)BLI_ghash_size(w_dst->faces_uuid); + unsigned int i; + + faces_result = MEM_mallocN(sizeof(faces_result) * (faces_result_len + 1), __func__); + GHASH_ITER_INDEX (gh_iter, w_dst->faces_uuid, i) { + BMFace *f = BLI_ghashIterator_getKey(&gh_iter); + faces_result[i] = f; + } + faces_result[faces_result_len] = NULL; + *r_faces_result_len = faces_result_len; + } + else { + *r_faces_result_len = 0; + } + +finally: + +#ifdef USE_WALKER_REUSE + bm_uuidwalk_clear(w_src); + bm_uuidwalk_clear(w_dst); +#else + bm_uuidwalk_free(w_src); + bm_uuidwalk_free(w_dst); +#endif + + return faces_result; +} + +/** + * Tag as visited, avoid re-use. + */ +static void bm_face_array_visit( + BMFace **faces, const unsigned int faces_len, + unsigned int *r_verts_len, + bool visit_faces) +{ + unsigned int verts_len = 0; + unsigned int i; + for (i = 0; i < faces_len; i++) { + BMFace *f = faces[i]; + BMLoop *l_iter, *l_first; + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + if (r_verts_len) { + if (!BM_elem_flag_test(l_iter->v, BM_ELEM_TAG)) { + verts_len += 1; + } + } + + BM_elem_flag_enable(l_iter->e, BM_ELEM_TAG); + BM_elem_flag_enable(l_iter->v, BM_ELEM_TAG); + } while ((l_iter = l_iter->next) != l_first); + + if (visit_faces) { + BM_elem_flag_enable(f, BM_ELEM_TAG); + } + } + + if (r_verts_len) { + *r_verts_len = verts_len; + } +} + +#ifdef USE_PIVOT_SEARCH + +/** \name Internal UUIDWalk API + * \{ */ + +/* signed user id */ +typedef intptr_t SUID_Int; + +static bool bm_edge_is_region_boundary(BMEdge *e) +{ + if (e->l->radial_next != e->l) { + BMLoop *l_iter = e->l; + do { + if (!BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) { + return true; + } + } while ((l_iter = l_iter->radial_next) != e->l); + return false; + } + else { + /* boundary */ + return true; + } +} + +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]) +{ + SUID_Int e_pivot_test_id[2]; + + e_pivot_test_id[0] = (SUID_Int)BLI_ghash_lookup(gh, e_test->v1); + e_pivot_test_id[1] = (SUID_Int)BLI_ghash_lookup(gh, e_test->v2); + if (e_pivot_test_id[0] > e_pivot_test_id[1]) { + SWAP(SUID_Int, e_pivot_test_id[0], e_pivot_test_id[1]); + } + + if ((*r_e_pivot_best == NULL) || + ((e_pivot_best_id[0] != e_pivot_test_id[0]) ? + (e_pivot_best_id[0] < e_pivot_test_id[0]) : + (e_pivot_best_id[1] < e_pivot_test_id[1]))) + { + e_pivot_best_id[0] = e_pivot_test_id[0]; + e_pivot_best_id[1] = e_pivot_test_id[1]; + + /* both verts are from the same pass, record this! */ + *r_e_pivot_best = e_test; + } +} + +/* quick id from a boundary vertex */ +static SUID_Int bm_face_region_vert_boundary_id(BMVert *v) +{ +#define PRIME_VERT_SMALL_A 7 +#define PRIME_VERT_SMALL_B 13 +#define PRIME_VERT_MID_A 103 +#define PRIME_VERT_MID_B 131 + + int tot = 0; + BMIter iter; + BMLoop *l; + SUID_Int id = PRIME_VERT_MID_A; + + BM_ITER_ELEM (l, &iter, v, BM_LOOPS_OF_VERT) { + const bool is_boundary_vert = (bm_edge_is_region_boundary(l->e) || bm_edge_is_region_boundary(l->prev->e)); + id ^= l->f->len * (is_boundary_vert ? PRIME_VERT_SMALL_A : PRIME_VERT_SMALL_B); + tot += 1; + } + + id ^= (tot * PRIME_VERT_MID_B); + + return id ? ABS(id) : 1; + +#undef PRIME_VERT_SMALL_A +#undef PRIME_VERT_SMALL_B +#undef PRIME_VERT_MID_A +#undef PRIME_VERT_MID_B +} + +/** + * Accumulate id's from a previous pass (swap sign each pass) + */ +static SUID_Int bm_face_region_vert_pass_id(GHash *gh, BMVert *v) +{ + BMIter eiter; + BMEdge *e; + SUID_Int tot = 0; + SUID_Int v_sum_face_len = 0; + SUID_Int v_sum_id = 0; + SUID_Int id; + SUID_Int id_min = INTPTR_MIN + 1; + +#define PRIME_VERT_MID_A 23 +#define PRIME_VERT_MID_B 31 + + BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { + if (BM_elem_flag_test(e, BM_ELEM_TAG)) { + BMVert *v_other = BM_edge_other_vert(e, v); + if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) { + /* non-zero values aren't allowed... so no need to check haskey */ + SUID_Int v_other_id = (SUID_Int)BLI_ghash_lookup(gh, v_other); + if (v_other_id > 0) { + v_sum_id += v_other_id; + tot += 1; + + /* face-count */ + { + BMLoop *l_iter = e->l; + do { + if (BM_elem_flag_test(l_iter->f, BM_ELEM_TAG)) { + v_sum_face_len += l_iter->f->len; + } + } while ((l_iter = l_iter->radial_next) != e->l); + } + } + } + } + } + + id = (tot * PRIME_VERT_MID_A); + id ^= (v_sum_face_len * PRIME_VERT_MID_B); + id ^= v_sum_id; + + /* disallow 0 & min (since it can't be flipped) */ + id = (UNLIKELY(id == 0) ? 1 : UNLIKELY(id < id_min) ? id_min : id); + + return ABS(id); + +#undef PRIME_VERT_MID_A +#undef PRIME_VERT_MID_B +} + +/** + * 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). + */ +static BMEdge *bm_face_region_pivot_edge_find( + BMFace **faces_region, unsigned int faces_region_len, + unsigned int verts_region_len, + unsigned int *r_depth) +{ + /* note, keep deterministic where possible (geometry order independent) + * this function assumed all visit faces & edges are tagged */ + + BLI_LINKSTACK_DECLARE(vert_queue_prev, BMVert *); + BLI_LINKSTACK_DECLARE(vert_queue_next, BMVert *); + + GHash *gh = BLI_ghash_ptr_new(__func__); + unsigned int i; + + BMEdge *e_pivot = NULL; + /* pick any non-boundary edge (not ideal) */ + BMEdge *e_pivot_fallback = NULL; + + SUID_Int pass = 0; + + /* total verts in 'gs' we have visited - aka - not v_init_none */ + unsigned int vert_queue_used = 0; + + BLI_LINKSTACK_INIT(vert_queue_prev); + BLI_LINKSTACK_INIT(vert_queue_next); + + /* face-verts */ + for (i = 0; i < faces_region_len; i++) { + BMFace *f = faces_region[i]; + + BMLoop *l_iter, *l_first; + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + BMEdge *e = l_iter->e; + if (bm_edge_is_region_boundary(e)) { + unsigned int j; + for (j = 0; j < 2; j++) { + if (!BLI_ghash_haskey(gh, (&e->v1)[j])) { + SUID_Int v_id = bm_face_region_vert_boundary_id((&e->v1)[j]); + BLI_ghash_insert(gh, (&e->v1)[j], (void *)v_id); + BLI_LINKSTACK_PUSH(vert_queue_prev, (&e->v1)[j]); + vert_queue_used += 1; + } + } + } + else { + /* use incase (depth == 0), no interior verts */ + e_pivot_fallback = e; + } + } while ((l_iter = l_iter->next) != l_first); + } + + while (BLI_LINKSTACK_SIZE(vert_queue_prev)) { + BMVert *v; + while ((v = BLI_LINKSTACK_POP(vert_queue_prev))) { + BMIter eiter; + BMEdge *e; + BLI_assert(BLI_ghash_haskey(gh, v)); + BLI_assert((SUID_Int)BLI_ghash_lookup(gh, v) > 0); + BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { + if (BM_elem_flag_test(e, BM_ELEM_TAG)) { + BMVert *v_other = BM_edge_other_vert(e, v); + if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) { + if (!BLI_ghash_haskey(gh, v_other)) { + /* add as negative, so we know not to read from them this pass */ + const SUID_Int v_id_other = -bm_face_region_vert_pass_id(gh, v_other); + BLI_ghash_insert(gh, v_other, (void *)v_id_other); + BLI_LINKSTACK_PUSH(vert_queue_next, v_other); + vert_queue_used += 1; + } + } + } + } + } + + /* flip all the newly added hashes to positive */ + { + LinkNode *v_link; + for (v_link = vert_queue_next; v_link; v_link = v_link->next) { + SUID_Int *v_id_p = (SUID_Int *)BLI_ghash_lookup_p(gh, v_link->link); + *v_id_p = -(*v_id_p); + BLI_assert(*v_id_p > 0); + } + } + + BLI_LINKSTACK_SWAP(vert_queue_prev, vert_queue_next); + pass += 1; + + if (vert_queue_used == verts_region_len) { + break; + } + } + + if (BLI_LINKSTACK_SIZE(vert_queue_prev) >= 2) { + /* common case - we managed to find some interior verts */ + LinkNode *v_link; + BMEdge *e_pivot_best = NULL; + SUID_Int e_pivot_best_id[2] = {0, 0}; + + /* temp untag, so we can quickly know what other verts are in this last pass */ + for (v_link = vert_queue_prev; v_link; v_link = v_link->next) { + BMVert *v = v_link->link; + BM_elem_flag_disable(v, BM_ELEM_TAG); + } + + /* restore correct tagging */ + for (v_link = vert_queue_prev; v_link; v_link = v_link->next) { + BMIter eiter; + BMEdge *e_test; + + BMVert *v = v_link->link; + BM_elem_flag_enable(v, BM_ELEM_TAG); + + BM_ITER_ELEM (e_test, &eiter, v, BM_EDGES_OF_VERT) { + if (BM_elem_flag_test(e_test, BM_ELEM_TAG)) { + BMVert *v_other = BM_edge_other_vert(e_test, v); + if (BM_elem_flag_test(v_other, BM_ELEM_TAG) == false) { + bm_face_region_pivot_edge_use_best(gh, e_test, &e_pivot_best, e_pivot_best_id); + } + } + } + } + + e_pivot = e_pivot_best; + } + + if ((e_pivot == NULL) && BLI_LINKSTACK_SIZE(vert_queue_prev)) { + /* find the best single edge */ + BMEdge *e_pivot_best = NULL; + SUID_Int e_pivot_best_id[2] = {0, 0}; + + LinkNode *v_link; + + /* reduce a pass since we're having to step into a previous passes vert, + * and will be closer to the boundary */ + BLI_assert(pass != 0); + pass -= 1; + + for (v_link = vert_queue_prev; v_link; v_link = v_link->next) { + BMVert *v = v_link->link; + + BMIter eiter; + BMEdge *e_test; + BM_ITER_ELEM (e_test, &eiter, v, BM_EDGES_OF_VERT) { + if (BM_elem_flag_test(e_test, BM_ELEM_TAG)) { + BMVert *v_other = BM_edge_other_vert(e_test, v); + if (BM_elem_flag_test(v_other, BM_ELEM_TAG)) { + bm_face_region_pivot_edge_use_best(gh, e_test, &e_pivot_best, e_pivot_best_id); + } + } + } + } + + e_pivot = e_pivot_best; + } + + BLI_LINKSTACK_FREE(vert_queue_prev); + BLI_LINKSTACK_FREE(vert_queue_next); + + BLI_ghash_free(gh, NULL, NULL); + + if (e_pivot == NULL) { +#ifdef DEBUG_PRINT + printf("%s: using fallback edge!\n", __func__); +#endif + e_pivot = e_pivot_fallback; + pass = 0; + } + + *r_depth = (unsigned int)pass; + + return e_pivot; +} +/** \} */ + +#endif /* USE_PIVOT_SEARCH */ + + +/* -------------------------------------------------------------------- */ +/* Quick UUID pass - identify candidates */ + +#ifdef USE_PIVOT_FASTMATCH + +/** \name Fast Match + * \{ */ + +typedef uintptr_t UUIDFashMatch; + +static UUIDFashMatch bm_vert_fasthash_single(BMVert *v) +{ + BMIter eiter; + BMEdge *e; + UUIDFashMatch e_num = 0, f_num = 0, l_num = 0; + +#define PRIME_EDGE 7 +#define PRIME_FACE 31 +#define PRIME_LOOP 61 + + BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) { + if (!BM_edge_is_wire(e)) { + BMLoop *l_iter = e->l; + e_num += 1; + do { + f_num += 1; + l_num += (unsigned int)l_iter->f->len; + } while ((l_iter = l_iter->radial_next) != e->l); + } + } + + return ((e_num * PRIME_EDGE) ^ + (f_num * PRIME_FACE) * + (l_num * PRIME_LOOP)); + +#undef PRIME_EDGE +#undef PRIME_FACE +#undef PRIME_LOOP +} + +static UUIDFashMatch *bm_vert_fasthash_create( + BMesh *bm, const unsigned int depth) +{ + UUIDFashMatch *id_prev; + UUIDFashMatch *id_curr; + unsigned int pass, i; + BMVert *v; + BMIter iter; + + id_prev = MEM_mallocN(sizeof(*id_prev) * (unsigned int)bm->totvert, __func__); + id_curr = MEM_mallocN(sizeof(*id_curr) * (unsigned int)bm->totvert, __func__); + + BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) { + id_prev[i] = bm_vert_fasthash_single(v); + } + + for (pass = 0; pass < depth; pass++) { + BMEdge *e; + + memcpy(id_curr, id_prev, sizeof(*id_prev) * (unsigned int)bm->totvert); + + BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + if (BM_edge_is_wire(e) == false) { + const int i1 = BM_elem_index_get(e->v1); + const int i2 = BM_elem_index_get(e->v2); + + id_curr[i1] += id_prev[i2]; + id_curr[i2] += id_prev[i1]; + } + } + } + MEM_freeN(id_prev); + + return id_curr; +} + +static void bm_vert_fasthash_edge_order( + UUIDFashMatch *fm, const BMEdge *e, UUIDFashMatch e_fm[2]) +{ + e_fm[0] = fm[BM_elem_index_get(e->v1)]; + e_fm[1] = fm[BM_elem_index_get(e->v2)]; + + if (e_fm[0] > e_fm[1]) { + SWAP(UUIDFashMatch, e_fm[0], e_fm[1]); + } +} + +static bool bm_vert_fasthash_edge_is_match( + UUIDFashMatch *fm, const BMEdge *e_a, const BMEdge *e_b) +{ + UUIDFashMatch e_a_fm[2]; + UUIDFashMatch e_b_fm[2]; + + bm_vert_fasthash_edge_order(fm, e_a, e_a_fm); + bm_vert_fasthash_edge_order(fm, e_b, e_b_fm); + + return ((e_a_fm[0] == e_b_fm[0]) && + (e_a_fm[1] == e_b_fm[1])); +} + +static void bm_vert_fasthash_destroy( + UUIDFashMatch *fm) +{ + MEM_freeN(fm); +} + +/** \} */ + +#endif /* USE_PIVOT_FASTMATCH */ + + +/** + * Take a face-region and return a list of matching face-regions. + * + * \param faces_region A single, contiguous face-region. + * \return A list of matching null-terminated face-region arrays. + */ +int BM_mesh_region_match( + BMesh *bm, + BMFace **faces_region, unsigned int faces_region_len, + ListBase *r_face_regions) +{ + BMEdge *e_src; + BMEdge *e_dst; + BMIter iter; + unsigned int verts_region_len = 0; + unsigned int faces_result_len = 0; + /* number of steps from e_src to a boundary vert */ + unsigned int depth; + + +#ifdef USE_WALKER_REUSE + UUIDWalk w_src, w_dst; +#endif + +#ifdef USE_PIVOT_FASTMATCH + UUIDFashMatch *fm; +#endif + +#ifdef DEBUG_PRINT + int search_num = 0; +#endif + +#ifdef DEBUG_TIME + TIMEIT_START(region_match); +#endif + + /* initialize visited verts */ + BM_mesh_elem_hflag_disable_all(bm, BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_TAG, false); + bm_face_array_visit(faces_region, faces_region_len, &verts_region_len, true); + + /* needed for 'ghashutil_bmelem_indexhash' */ + BM_mesh_elem_index_ensure(bm, BM_VERT | BM_FACE); + +#ifdef USE_PIVOT_SEARCH + e_src = bm_face_region_pivot_edge_find( + faces_region, faces_region_len, + verts_region_len, &depth); + + /* see which edge is added */ +#if 0 + BM_select_history_clear(bm); + if (e_src) { + BM_select_history_store(bm, e_src); + } +#endif + +#else + /* quick test only! */ + e_src = BM_mesh_active_edge_get(bm); +#endif + + if (e_src == NULL) { +#ifdef DEBUG_PRINT + printf("Couldn't find 'e_src'"); +#endif + return 0; + } + + BLI_listbase_clear(r_face_regions); + +#ifdef USE_PIVOT_FASTMATCH + if (depth > 0) { + fm = bm_vert_fasthash_create(bm, depth); + } + else { + fm = NULL; + } +#endif + +#ifdef USE_WALKER_REUSE + bm_uuidwalk_init(&w_src, faces_region_len, verts_region_len); + bm_uuidwalk_init(&w_dst, faces_region_len, verts_region_len); +#endif + + BM_ITER_MESH (e_dst, &iter, bm, BM_EDGES_OF_MESH) { + BMFace **faces_result; + unsigned int faces_result_len_out; + + if (BM_elem_flag_test(e_dst, BM_ELEM_TAG)) { + continue; + } + +#ifdef USE_PIVOT_FASTMATCH + if (fm && !bm_vert_fasthash_edge_is_match(fm, e_src, e_dst)) { + continue; + } +#endif + +#ifdef DEBUG_PRINT + search_num += 1; +#endif + + faces_result = bm_mesh_region_match_pair( +#ifdef USE_WALKER_REUSE + &w_src, &w_dst, +#endif + e_src, e_dst, + faces_region_len, + verts_region_len, + &faces_result_len_out); + + /* tag verts as visited */ + if (faces_result) { + LinkData *link; + + bm_face_array_visit(faces_result, faces_result_len_out, NULL, false); + + link = BLI_genericNodeN(faces_result); + BLI_addtail(r_face_regions, link); + faces_result_len += 1; + } + } + +#ifdef USE_WALKER_REUSE + bm_uuidwalk_free(&w_src); + bm_uuidwalk_free(&w_dst); +#else + (void)bm_uuidwalk_clear; +#endif + +#ifdef USE_PIVOT_FASTMATCH + if (fm) { + bm_vert_fasthash_destroy(fm); + } +#endif + +#ifdef DEBUG_PRINT + printf("%s: search: %d, found %d\n", __func__, search_num, faces_result_len); +#endif + +#ifdef DEBUG_TIME + TIMEIT_END(region_match); +#endif + + return (int)faces_result_len; +} diff --git a/source/blender/bmesh/tools/bmesh_region_match.h b/source/blender/bmesh/tools/bmesh_region_match.h new file mode 100644 index 00000000000..edf8369b070 --- /dev/null +++ b/source/blender/bmesh/tools/bmesh_region_match.h @@ -0,0 +1,33 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BMESH_REGION_MATCH_H__ +#define __BMESH_REGION_MATCH_H__ + +/** \file blender/bmesh/tools/bmesh_region_match.h + * \ingroup bmesh + */ + +int BM_mesh_region_match( + BMesh *bm, + BMFace **faces_region, unsigned int faces_region_len, + ListBase *r_face_regions); + +#endif /* __BMESH_REGION_MATCH_H__ */ |