diff options
Diffstat (limited to 'source/blender/bmesh/tools')
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_beautify.c | 24 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_bevel.c | 535 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_bevel.h | 9 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_bisect_plane.c | 2 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_decimate.h | 25 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_decimate_collapse.c | 241 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_decimate_dissolve.c | 77 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_edgenet.c | 18 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_edgenet.h | 5 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_edgesplit.c | 112 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_edgesplit.h | 5 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_intersect.c | 14 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_path.c | 6 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_region_match.c | 54 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_triangulate.c | 1 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_triangulate.h | 5 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_wireframe.c | 7 |
17 files changed, 820 insertions, 320 deletions
diff --git a/source/blender/bmesh/tools/bmesh_beautify.c b/source/blender/bmesh/tools/bmesh_beautify.c index 990a2108bd7..19fe492c670 100644 --- a/source/blender/bmesh/tools/bmesh_beautify.c +++ b/source/blender/bmesh/tools/bmesh_beautify.c @@ -274,11 +274,12 @@ BLI_INLINE bool edge_in_array(const BMEdge *e, const BMEdge **edge_array, const } /* recalc an edge in the heap (surrounding geometry has changed) */ -static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GSet **edge_state_arr, - /* only for testing the edge is in the array */ - const BMEdge **edge_array, const int edge_array_len, +static void bm_edge_update_beauty_cost_single( + BMEdge *e, Heap *eheap, HeapNode **eheap_table, GSet **edge_state_arr, + /* only for testing the edge is in the array */ + const BMEdge **edge_array, const int edge_array_len, - const short flag, const short method) + const short flag, const short method) { if (edge_in_array(e, edge_array, edge_array_len)) { const int i = BM_elem_index_get(e); @@ -316,10 +317,11 @@ static void bm_edge_update_beauty_cost_single(BMEdge *e, Heap *eheap, HeapNode * } /* we have rotated an edge, tag other edges and clear this one */ -static void bm_edge_update_beauty_cost(BMEdge *e, Heap *eheap, HeapNode **eheap_table, GSet **edge_state_arr, - const BMEdge **edge_array, const int edge_array_len, - /* only for testing the edge is in the array */ - const short flag, const short method) +static void bm_edge_update_beauty_cost( + BMEdge *e, Heap *eheap, HeapNode **eheap_table, GSet **edge_state_arr, + const BMEdge **edge_array, const int edge_array_len, + /* only for testing the edge is in the array */ + const short flag, const short method) { int i; @@ -333,7 +335,7 @@ static void bm_edge_update_beauty_cost(BMEdge *e, Heap *eheap, HeapNode **eheap_ BLI_assert(e->l->f->len == 3 && e->l->radial_next->f->len == 3); - BLI_assert(BM_edge_face_count(e) == 2); + BLI_assert(BM_edge_face_count_is_equal(e, 2)); for (i = 0; i < 4; i++) { bm_edge_update_beauty_cost_single( @@ -389,11 +391,11 @@ void BM_mesh_beautify_fill( i = BM_elem_index_get(e); eheap_table[i] = NULL; - BLI_assert(BM_edge_face_count(e) == 2); + BLI_assert(BM_edge_face_count_is_equal(e, 2)); e = BM_edge_rotate(bm, e, false, BM_EDGEROT_CHECK_EXISTS); - BLI_assert(e == NULL || BM_edge_face_count(e) == 2); + BLI_assert(e == NULL || BM_edge_face_count_is_equal(e, 2)); if (LIKELY(e)) { GSet *e_state_set = edge_state_arr[i]; diff --git a/source/blender/bmesh/tools/bmesh_bevel.c b/source/blender/bmesh/tools/bmesh_bevel.c index 3c7a86a332f..3348afa3bfa 100644 --- a/source/blender/bmesh/tools/bmesh_bevel.c +++ b/source/blender/bmesh/tools/bmesh_bevel.c @@ -57,6 +57,9 @@ /* happens far too often, uncomment for development */ // #define BEVEL_ASSERT_PROJECT +/* will likely remove the code enabled by this soon, when sure that it is not needed */ +// #define PRE_275_ALGORITHM + /* for testing */ // #pragma GCC diagnostic error "-Wpadded" @@ -187,7 +190,7 @@ typedef struct BevelParams { bool limit_offset; /* should offsets be limited by collisions? */ const struct MDeformVert *dvert; /* vertex group array, maybe set if vertex_only */ int vertex_group; /* vertex group index, maybe set if vertex_only */ - int mat_nr; /* if >= 0, material number for bevel; else material comes from adjacent faces */ + int mat_nr; /* if >= 0, material number for bevel; else material comes from adjacent faces */ } BevelParams; // #pragma GCC diagnostic ignored "-Wpadded" @@ -244,8 +247,9 @@ static void create_mesh_bmvert(BMesh *bm, VMesh *vm, int i, int j, int k, BMVert BM_elem_flag_disable(nv->v, BM_ELEM_TAG); } -static void copy_mesh_vert(VMesh *vm, int ito, int jto, int kto, - int ifrom, int jfrom, int kfrom) +static void copy_mesh_vert( + VMesh *vm, int ito, int jto, int kto, + int ifrom, int jfrom, int kfrom) { NewVert *nvto, *nvfrom; @@ -361,8 +365,9 @@ static BMFace *boundvert_rep_face(BoundVert *v) * * \note ALL face creation goes through this function, this is important to keep! */ -static BMFace *bev_create_ngon(BMesh *bm, BMVert **vert_arr, const int totv, - BMFace **face_arr, BMFace *facerep, int mat_nr, bool do_interp) +static BMFace *bev_create_ngon( + BMesh *bm, BMVert **vert_arr, const int totv, + BMFace **face_arr, BMFace *facerep, int mat_nr, bool do_interp) { BMIter iter; BMLoop *l; @@ -402,15 +407,17 @@ static BMFace *bev_create_ngon(BMesh *bm, BMVert **vert_arr, const int totv, return f; } -static BMFace *bev_create_quad_tri(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4, - BMFace *facerep, int mat_nr, bool do_interp) +static BMFace *bev_create_quad_tri( + BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4, + BMFace *facerep, int mat_nr, bool do_interp) { BMVert *varr[4] = {v1, v2, v3, v4}; return bev_create_ngon(bm, varr, v4 ? 4 : 3, NULL, facerep, mat_nr, do_interp); } -static BMFace *bev_create_quad_tri_ex(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4, - BMFace *f1, BMFace *f2, BMFace *f3, BMFace *f4, int mat_nr) +static BMFace *bev_create_quad_tri_ex( + BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4, + BMFace *f1, BMFace *f2, BMFace *f3, BMFace *f4, int mat_nr) { BMVert *varr[4] = {v1, v2, v3, v4}; BMFace *farr[4] = {f1, f2, f3, f4}; @@ -419,8 +426,9 @@ static BMFace *bev_create_quad_tri_ex(BMesh *bm, BMVert *v1, BMVert *v2, BMVert /* Is Loop layer layer_index contiguous across shared vertex of l1 and l2? */ -static bool contig_ldata_across_loops(BMesh *bm, BMLoop *l1, BMLoop *l2, - int layer_index) +static bool contig_ldata_across_loops( + BMesh *bm, BMLoop *l1, BMLoop *l2, + int layer_index) { const int offset = bm->ldata.layers[layer_index].offset; const int type = bm->ldata.layers[layer_index].type; @@ -478,7 +486,9 @@ static bool contig_ldata_across_edge(BMesh *bm, BMEdge *e, BMFace *f1, BMFace *f return true; } -/* Like bev_create_quad_tri, but when verts straddle an old edge. +/** + * Like bev_create_quad_tri, but when verts straddle an old edge. + * <pre> * e * | * v1+---|---+v4 @@ -487,13 +497,16 @@ static bool contig_ldata_across_edge(BMesh *bm, BMEdge *e, BMFace *f1, BMFace *f * v2+---|---+v3 * | * f1 | f2 + * </pre> * * Most CustomData for loops can be interpolated in their respective * faces' loops, but for UVs and other 'has_math_cd' layers, only * do this if the UVs are continuous across the edge e, otherwise pick * one side (f1, arbitrarily), and interpolate them all on that side. - * For face data, use f1 (arbitrarily) as face representative. */ -static BMFace *bev_create_quad_straddle(BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4, + * For face data, use f1 (arbitrarily) as face representative. + */ +static BMFace *bev_create_quad_straddle( + BMesh *bm, BMVert *v1, BMVert *v2, BMVert *v3, BMVert *v4, BMFace *f1, BMFace *f2, int mat_nr, bool is_seam) { BMFace *f, *facerep; @@ -582,10 +595,42 @@ static bool is_outside_edge(EdgeHalf *e, const float co[3], BMVert **ret_closer_ } } +/* co should be approximately on the plane between e1 and e2, which share common vert v + * and common face f (which cannot be NULL). + * Is it between those edges, sweeping CCW? */ +static bool point_between_edges(float co[3], BMVert *v, BMFace *f, EdgeHalf *e1, EdgeHalf *e2) +{ + BMVert *v1, *v2; + float dir1[3], dir2[3], dirco[3], no[3]; + float ang11, ang1co; + + v1 = BM_edge_other_vert(e1->e, v); + v2 = BM_edge_other_vert(e2->e, v); + sub_v3_v3v3(dir1, v->co, v1->co); + sub_v3_v3v3(dir2, v->co, v2->co); + sub_v3_v3v3(dirco, v->co, co); + normalize_v3(dir1); + normalize_v3(dir2); + normalize_v3(dirco); + ang11 = angle_normalized_v3v3(dir1, dir2); + ang1co = angle_normalized_v3v3(dir1, dirco); + /* angles are in [0,pi]. need to compare cross product with normal to see if they are reflex */ + cross_v3_v3v3(no, dir1, dir2); + if (dot_v3v3(no, f->no) < 0.0f) + ang11 = (float)(M_PI * 2.0) - ang11; + cross_v3_v3v3(no, dir1, dirco); + if (dot_v3v3(no, f->no) < 0.0f) + ang1co = (float)(M_PI * 2.0) - ang1co; + return (ang11 - ang1co > -BEVEL_EPSILON_BIG); +} + /* * Calculate the meeting point between the offset edges for e1 and e2, putting answer in meetco. * e1 and e2 share vertex v and face f (may be NULL) and viewed from the normal side of * the bevel vertex, e1 precedes e2 in CCW order. + * Except: if edges_between is true, there are edges between e1 and e2 in CCW order so they + * don't share a common face. We want the meeting point to be on an existing face so it + * should be dropped onto one of the intermediate faces, if possible. * Offset edge is on right of both edges, where e1 enters v and e2 leave it. * When offsets are equal, the new point is on the edge bisector, with length offset/sin(angle/2), * but if the offsets are not equal (allowing for this, as bevel modifier has edge weights that may @@ -594,16 +639,27 @@ static bool is_outside_edge(EdgeHalf *e, const float co[3], BMVert **ret_closer_ * record the change in offset_l (or offset_r); later we can tell that a change has happened because * the offset will differ from its original value in offset_l_spec (or offset_r_spec). */ -static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, float meetco[3]) +static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, bool edges_between, float meetco[3]) { - float dir1[3], dir2[3], norm_v[3], norm_perp1[3], norm_perp2[3], - off1a[3], off1b[3], off2a[3], off2b[3], isect2[3], ang, d; + float dir1[3], dir2[3], dir1n[3], dir2p[3], norm_v[3], norm_v1[3], norm_v2[3], + norm_perp1[3], norm_perp2[3], off1a[3], off1b[3], off2a[3], off2b[3], + isect2[3], dropco[3], plane[4], ang, d; BMVert *closer_v; + EdgeHalf *e, *e1next, *e2prev; + BMFace *ff; + int isect_kind; /* get direction vectors for two offset lines */ sub_v3_v3v3(dir1, v->co, BM_edge_other_vert(e1->e, v)->co); sub_v3_v3v3(dir2, BM_edge_other_vert(e2->e, v)->co, v->co); + if (edges_between) { + e1next = e1->next; + e2prev = e2->prev; + sub_v3_v3v3(dir1n, BM_edge_other_vert(e1next->e, v)->co, v->co); + sub_v3_v3v3(dir2p, v->co, BM_edge_other_vert(e2prev->e, v)->co); + } + ang = angle_v3v3(dir1, dir2); if (ang < BEVEL_EPSILON_BIG) { /* special case: e1 and e2 are parallel; put offset point perp to both, from v. @@ -643,14 +699,31 @@ static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, float * If e1-v-e2 is a reflex angle (viewed from vertex normal side), need to flip. * Use f->no to figure out which side to look at angle from, as even if * f is non-planar, will be more accurate than vertex normal */ - cross_v3_v3v3(norm_v, dir2, dir1); - normalize_v3(norm_v); - if (dot_v3v3(norm_v, f ? f->no : v->no) < 0.0f) - negate_v3(norm_v); + if (!edges_between) { + cross_v3_v3v3(norm_v1, dir2, dir1); + normalize_v3(norm_v1); + if (dot_v3v3(norm_v1, f ? f->no : v->no) < 0.0f) + negate_v3(norm_v1); + copy_v3_v3(norm_v2, norm_v1); + } + else { + /* separate faces; get face norms at corners for each separately */ + cross_v3_v3v3(norm_v1, dir1n, dir1); + normalize_v3(norm_v1); + f = e1->fnext; + if (dot_v3v3(norm_v1, f ? f->no : v->no) < 0.0f) + negate_v3(norm_v1); + cross_v3_v3v3(norm_v2, dir2, dir2p); + normalize_v3(norm_v2); + f = e2->fprev; + if (dot_v3v3(norm_v2, f ? f->no : v->no) < 0.0f) + negate_v3(norm_v2); + } + /* get vectors perp to each edge, perp to norm_v, and pointing into face */ - cross_v3_v3v3(norm_perp1, dir1, norm_v); - cross_v3_v3v3(norm_perp2, dir2, norm_v); + cross_v3_v3v3(norm_perp1, dir1, norm_v1); + cross_v3_v3v3(norm_perp2, dir2, norm_v2); normalize_v3(norm_perp1); normalize_v3(norm_perp2); @@ -662,11 +735,10 @@ static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, float madd_v3_v3fl(off2a, norm_perp2, e2->offset_l); add_v3_v3v3(off2b, off2a, dir2); - /* intersect the lines; by construction they should be on the same plane and not parallel */ - if (!isect_line_line_v3(off1a, off1b, off2a, off2b, meetco, isect2)) { -#ifdef BEVEL_ASSERT_PROJECT - BLI_assert(!"offset_meet failure"); -#endif + /* intersect the lines */ + isect_kind = isect_line_line_v3(off1a, off1b, off2a, off2b, meetco, isect2); + if (isect_kind == 0) { + /* lines are colinear: we already tested for this, but this used a different epsilon */ copy_v3_v3(meetco, off1a); /* just to do something */ d = dist_to_line_v3(meetco, v->co, BM_edge_other_vert(e2->e, v)->co); if (fabsf(d - e2->offset_l) > BEVEL_EPSILON) @@ -686,15 +758,38 @@ static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, float copy_v3_v3(meetco, closer_v->co); e1->offset_r = len_v3v3(meetco, v->co); } + if (edges_between && e1->offset_r > 0.0 && e2->offset_l > 0.0) { + /* Try to drop meetco to a face between e1 and e2 */ + if (isect_kind == 2) { + /* lines didn't meet in 3d: get average of meetco and isect2 */ + mid_v3_v3v3(meetco, meetco, isect2); + } + for (e = e1; e != e2; e = e->next) { + ff = e->fnext; + if (!ff) + continue; + plane_from_point_normal_v3(plane, v->co, ff->no); + closest_to_plane_v3(dropco, plane, meetco); + if (point_between_edges(dropco, v, ff, e, e->next)) { + copy_v3_v3(meetco, dropco); + break; + } + } + e1->offset_r = dist_to_line_v3(meetco, v->co, BM_edge_other_vert(e1->e, v)->co); + e2->offset_l = dist_to_line_v3(meetco, v->co, BM_edge_other_vert(e2->e, v)->co); + } } } } +/* chosen so that 1/sin(BEVEL_GOOD_ANGLE) is about 4, giving that expansion factor to bevel width */ +#define BEVEL_GOOD_ANGLE 0.25f + /* Calculate the meeting point between e1 and e2 (one of which should have zero offsets), * where e1 precedes e2 in CCW order around their common vertex v (viewed from normal side). * If r_angle is provided, return the angle between e and emeet in *r_angle. * If the angle is 0, or it is 180 degrees or larger, there will be no meeting point; - * return false in that case, else true */ + * return false in that case, else true. */ static bool offset_meet_edge(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, float meetco[3], float *r_angle) { float dir1[3], dir2[3], fno[3], ang, sinang; @@ -706,7 +801,7 @@ static bool offset_meet_edge(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, float meetc /* find angle from dir1 to dir2 as viewed from vertex normal side */ ang = angle_normalized_v3v3(dir1, dir2); - if (ang < BEVEL_EPSILON) { + if (fabsf(ang) < BEVEL_GOOD_ANGLE) { if (r_angle) *r_angle = 0.0f; return false; @@ -717,10 +812,11 @@ static bool offset_meet_edge(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, float meetc if (r_angle) *r_angle = ang; - if (ang - (float)M_PI > BEVEL_EPSILON) + if (fabsf(ang - (float)M_PI) < BEVEL_GOOD_ANGLE) return false; sinang = sinf(ang); + copy_v3_v3(meetco, v->co); if (e1->offset_r == 0.0f) madd_v3_v3fl(meetco, dir1, e2->offset_l / sinang); @@ -729,6 +825,17 @@ static bool offset_meet_edge(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, float meetc return true; } +/* Return true if it will look good to put the meeting point where offset_on_edge_between + * would put it. This means that neither side sees a reflex angle */ +static bool good_offset_on_edge_between(EdgeHalf *e1, EdgeHalf *e2, EdgeHalf *emid, BMVert *v) +{ + float ang; + float meet[3]; + + return offset_meet_edge(e1, emid, v, meet, &ang) && + offset_meet_edge(emid, e2, v, meet, &ang); +} + /* Calculate the best place for a meeting point for the offsets from edges e1 and e2 * on the in-between edge emid. Viewed from the vertex normal side, the CCW * order of these edges is e1, emid, e2. @@ -737,8 +844,9 @@ static bool offset_meet_edge(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, float meetc * already, prefer to keep the offset the same on this end. * Otherwise, pick a point between the two intersection points on emid that minimizes * the sum of squares of errors from desired offset. */ -static void offset_on_edge_between(BevelParams *bp, EdgeHalf *e1, EdgeHalf *e2, EdgeHalf *emid, - BMVert *v, float meetco[3]) +static void offset_on_edge_between( + BevelParams *bp, EdgeHalf *e1, EdgeHalf *e2, EdgeHalf *emid, + BMVert *v, float meetco[3]) { float d, ang1, ang2, sina1, sina2, lambda; float meet1[3], meet2[3]; @@ -787,14 +895,16 @@ static void offset_on_edge_between(BevelParams *bp, EdgeHalf *e1, EdgeHalf *e2, e2->offset_l = d; } +#ifdef PRE_275_ALGORITHM /* Calculate the best place for a meeting point for the offsets from edges e1 and e2 * when there is an in-between edge emid, and we prefer to have a point that may not * be on emid if that does a better job of keeping offsets at the user spec. * Viewed from the vertex normal side, the CCW order of the edges is e1, emid, e2. * The offset lines may not meet exactly: the lines may be angled so that they can't meet. * In that case, pick the offset_on_edge_between. */ -static void offset_in_two_planes(BevelParams *bp, EdgeHalf *e1, EdgeHalf *e2, EdgeHalf *emid, - BMVert *v, float meetco[3]) +static void offset_in_two_planes( + BevelParams *bp, EdgeHalf *e1, EdgeHalf *e2, EdgeHalf *emid, + BMVert *v, float meetco[3]) { float dir1[3], dir2[3], dirmid[3], norm_perp1[3], norm_perp2[3], off1a[3], off1b[3], off2a[3], off2b[3], isect2[3], @@ -861,6 +971,7 @@ static void offset_in_two_planes(BevelParams *bp, EdgeHalf *e1, EdgeHalf *e2, Ed /* else iret == 1 and the lines are coplanar so meetco has the intersection */ } } +#endif /* Offset by e->offset in plane with normal plane_no, on left if left==true, * else on right. If no is NULL, choose an arbitrary plane different @@ -1079,8 +1190,9 @@ static int bev_ccw_test(BMEdge *a, BMEdge *b, BMFace *f) * and B has the right side as columns - both extended into homogeneous coords. * So M = B*(Ainverse). Doing Ainverse by hand gives the code below. */ -static bool make_unit_square_map(const float va[3], const float vmid[3], const float vb[3], - float r_mat[4][4]) +static bool make_unit_square_map( + const float va[3], const float vmid[3], const float vb[3], + float r_mat[4][4]) { float vo[3], vd[3], vb_vmid[3], va_vmid[3], vddir[3]; @@ -1128,8 +1240,9 @@ static bool make_unit_square_map(const float va[3], const float vmid[3], const f * and 1/2{va+vb+vc-vd} * and Blender matrices have cols at m[i][*]. */ -static void make_unit_cube_map(const float va[3], const float vb[3], const float vc[3], - const float vd[3], float r_mat[4][4]) +static void make_unit_cube_map( + const float va[3], const float vb[3], const float vc[3], + const float vd[3], float r_mat[4][4]) { copy_v3_v3(r_mat[0], va); sub_v3_v3(r_mat[0], vb); @@ -1410,6 +1523,325 @@ static void set_bound_vert_seams(BevVert *bv) } while ((v = v->next) != bv->vmesh->boundstart); } +#ifndef PRE_275_ALGORITHM +/* Is e between two planes where angle between is 180? */ +static bool eh_on_plane(EdgeHalf *e) +{ + float dot; + + if (e->fprev && e->fnext) { + dot = dot_v3v3(e->fprev->no, e->fnext->no); + if (fabsf(dot) <= BEVEL_EPSILON || + fabsf(dot - 1.0f) <= BEVEL_EPSILON) + { + return true; + } + } + return false; +} + +/* Calculate the profiles for all the BoundVerts of VMesh vm */ +static void calculate_vm_profiles(BevelParams *bp, BevVert *bv, VMesh *vm) +{ + BoundVert *v; + + v = vm->boundstart; + do { + set_profile_params(bp, bv, v); + calculate_profile(bp, v); + } while ((v = v->next) != vm->boundstart); +} + +/* Implements build_boundary for vertex-only case */ +static void build_boundary_vertex_only(BevelParams *bp, BevVert *bv, bool construct) +{ + VMesh *vm = bv->vmesh; + EdgeHalf *efirst, *e; + BoundVert *v; + float co[3]; + + BLI_assert(bp->vertex_only); + + e = efirst = &bv->edges[0]; + do { + slide_dist(e, bv->v, e->offset_l, co); + if (construct) { + v = add_new_bound_vert(bp->mem_arena, vm, co); + v->efirst = v->elast = e; + e->leftv = v; + } + else { + adjust_bound_vert(e->leftv, co); + } + } while ((e = e->next) != efirst); + + calculate_vm_profiles(bp, bv, vm); + + if (construct) { + set_bound_vert_seams(bv); + if (vm->count == 2) + vm->mesh_kind = M_NONE; + else if (bp->seg == 1) + vm->mesh_kind = M_POLY; + else + vm->mesh_kind = M_ADJ; + } +} + +/* Special case of build_boundary when a single edge is beveled. + * The 'width adjust' part of build_boundary has been done already, and + * efirst is the first beveled edge at vertex bv. */ +static void build_boundary_terminal_edge(BevelParams *bp, BevVert *bv, EdgeHalf *efirst, bool construct) +{ + MemArena *mem_arena = bp->mem_arena; + VMesh *vm = bv->vmesh; + BoundVert *v; + EdgeHalf *e; + const float *no; + float co[3], d; + + e = efirst; + if (bv->edgecount == 2) { + /* only 2 edges in, so terminate the edge with an artificial vertex on the unbeveled edge */ + no = e->fprev ? e->fprev->no : (e->fnext ? e->fnext->no : NULL); + offset_in_plane(e, no, true, co); + if (construct) { + v = add_new_bound_vert(mem_arena, vm, co); + v->efirst = v->elast = v->ebev = e; + e->leftv = v; + } + else { + adjust_bound_vert(e->leftv, co); + } + no = e->fnext ? e->fnext->no : (e->fprev ? e->fprev->no : NULL); + offset_in_plane(e, no, false, co); + if (construct) { + v = add_new_bound_vert(mem_arena, vm, co); + v->efirst = v->elast = e; + e->rightv = v; + } + else { + adjust_bound_vert(e->rightv, co); + } + /* make artifical extra point along unbeveled edge, and form triangle */ + slide_dist(e->next, bv->v, e->offset_l, co); + if (construct) { + v = add_new_bound_vert(mem_arena, vm, co); + v->efirst = v->elast = e->next; + e->next->leftv = e->next->rightv = v; + /* could use M_POLY too, but tri-fan looks nicer)*/ + vm->mesh_kind = M_TRI_FAN; + set_bound_vert_seams(bv); + } + else { + adjust_bound_vert(e->next->leftv, co); + } + } + else { + /* More than 2 edges in. Put on-edge verts on all the other edges + * and join with the beveled edge to make a poly or adj mesh, + * Because e->prev has offset 0, offset_meet will put co on that edge */ + /* TODO: should do something else if angle between e and e->prev > 180 */ + offset_meet(e->prev, e, bv->v, e->fprev, false, co); + if (construct) { + v = add_new_bound_vert(mem_arena, vm, co); + v->efirst = e->prev; + v->elast = v->ebev = e; + e->leftv = v; + e->prev->leftv = v; + } + else { + adjust_bound_vert(e->leftv, co); + } + e = e->next; + offset_meet(e->prev, e, bv->v, e->fprev, false, co); + if (construct) { + v = add_new_bound_vert(mem_arena, vm, co); + v->efirst = e->prev; + v->elast = e; + e->leftv = v; + e->prev->rightv = v; + } + else { + adjust_bound_vert(e->leftv, co); + } + d = len_v3v3(bv->v->co, co); + for (e = e->next; e->next != efirst; e = e->next) { + slide_dist(e, bv->v, d, co); + if (construct) { + v = add_new_bound_vert(mem_arena, vm, co); + v->efirst = v->elast = e; + e->leftv = v; + } + else { + adjust_bound_vert(e->leftv, co); + } + } + } + calculate_vm_profiles(bp, bv, vm); + + if (bv->edgecount >= 3) { + /* special case: snap profile to plane of adjacent two edges */ + v = vm->boundstart; + BLI_assert(v->ebev != NULL); + move_profile_plane(v, v->efirst, v->next->elast); + calculate_profile(bp, v); + } + + if (construct) { + set_bound_vert_seams(bv); + + if (vm->count == 2 && bv->edgecount == 3) { + vm->mesh_kind = M_NONE; + } + else if (vm->count == 3) { + vm->mesh_kind = M_TRI_FAN; + } + else { + vm->mesh_kind = M_POLY; + } + } +} + +/* Make a circular list of BoundVerts for bv, each of which has the coordinates + * of a vertex on the boundary of the beveled vertex bv->v. + * This may adjust some EdgeHalf widths, and there might have to be + * a subsequent pass to make the widths as consistent as possible. + * The first time through, construct will be true and we are making the BoundVerts + * and setting up the BoundVert and EdgeHalf pointers appropriately. + * For a width consistency path, we just recalculate the coordinates of the + * BoundVerts. If the other ends have been (re)built already, then we + * copy the offsets from there to match, else we use the ideal (user-specified) + * widths. + * Also, if construct, decide on the mesh pattern that will be used inside the boundary. + * Doesn't make the actual BMVerts */ +static void build_boundary(BevelParams *bp, BevVert *bv, bool construct) +{ + MemArena *mem_arena = bp->mem_arena; + EdgeHalf *efirst, *e, *e2, *e3, *enip, *eip, *eother; + BoundVert *v; + BevVert *bvother; + VMesh *vm; + float co[3]; + int nip, nnip; + + /* Current bevel does nothing if only one edge into a vertex */ + if (bv->edgecount <= 1) + return; + + if (bp->vertex_only) { + build_boundary_vertex_only(bp, bv, construct); + return; + } + + vm = bv->vmesh; + + /* Find a beveled edge to be efirst. Then for each edge, try matching widths to other end. */ + e = efirst = next_bev(bv, NULL); + BLI_assert(e->is_bev); + do { + eother = find_other_end_edge_half(bp, e, &bvother); + if (eother && bvother->visited && bp->offset_type != BEVEL_AMT_PERCENT) { + /* try to keep bevel even by matching other end offsets */ + e->offset_l = eother->offset_r; + e->offset_r = eother->offset_l; + } + else { + /* reset to user spec */ + e->offset_l = e->offset_l_spec; + e->offset_r = e->offset_r_spec; + } + } while ((e = e->next) != efirst); + + if (bv->selcount == 1) { + /* special case: only one beveled edge in */ + build_boundary_terminal_edge(bp, bv, efirst, construct); + return; + } + + /* Here: there is more than one beveled edge. + * We make BoundVerts to connect the sides of the beveled edges. + * Non-beveled edges in between will just join to the appropriate juncture point. */ + e = efirst; + do { + BLI_assert(e->is_bev); + /* Make the BoundVert for the right side of e; other side will be made + * when the beveled edge to the left of e is handled. + * Analyze edges until next beveled edge. + * They are either "in plane" (preceding and subsequent faces are coplanar) + * or not. The "non-in-plane" edges effect silhouette and we prefer to slide + * along one of those if possible. */ + nip = nnip = 0; /* counts of in-plane / not-in-plane */ + enip = eip = NULL; /* representatives of each */ + for (e2 = e->next; !e2->is_bev; e2 = e2->next) { + if (eh_on_plane(e2)) { + nip++; + eip = e2; + } + else { + nnip++; + enip = e2; + } + } + if (nip == 0 && nnip == 0) { + offset_meet(e, e2, bv->v, e->fnext, false, co); + } + else if (nnip > 0) { + if (nnip == 1 && good_offset_on_edge_between(e, e2, enip, bv->v)) { + offset_on_edge_between(bp, e, e2, enip, bv->v, co); + } + else { + offset_meet(e, e2, bv->v, NULL, true, co); + } + } + else { + /* nip > 0 and nnip == 0 */ + if (nip == 1 && good_offset_on_edge_between(e, e2, eip, bv->v)) { + offset_on_edge_between(bp, e, e2, eip, bv->v, co); + } + else { + offset_meet(e, e2, bv->v, NULL, true, co); + } + } + if (construct) { + v = add_new_bound_vert(mem_arena, vm, co); + v->efirst = e; + v->elast = e2; + v->ebev = e2; + e->rightv = v; + e2->leftv = v; + for (e3 = e->next; e3 != e2; e3 = e3->next) { + e3->leftv = e3->rightv = v; + } + } + else { + adjust_bound_vert(e->rightv, co); + } + e = e2; + } while (e != efirst); + + calculate_vm_profiles(bp, bv, vm); + + if (construct) { + set_bound_vert_seams(bv); + + if (vm->count == 2) { + vm->mesh_kind = M_NONE; + } + else if (efirst->seg == 1) { + vm->mesh_kind = M_POLY; + } + else { + vm->mesh_kind = M_ADJ; + } + } +} +#endif + +#ifdef PRE_275_ALGORITHM +/* This code was used prior to just before the 2.75 Blender release. + * It treated multiple non-beveled edges between beveled ones differently */ + /* Make a circular list of BoundVerts for bv, each of which has the coordinates * of a vertex on the boundary of the beveled vertex bv->v. * This may adjust some EdgeHalf widths, and there might have to be @@ -1504,7 +1936,7 @@ static void build_boundary(BevelParams *bp, BevVert *bv, bool construct) /* handle only left side of beveled edge e here: next iteration should do right side */ if (e->prev->is_bev) { BLI_assert(e->prev != e); /* see: wire edge special case */ - offset_meet(e->prev, e, bv->v, e->fprev, co); + offset_meet(e->prev, e, bv->v, e->fprev, false, co); if (construct) { v = add_new_bound_vert(mem_arena, vm, co); v->efirst = e->prev; @@ -1541,7 +1973,7 @@ static void build_boundary(BevelParams *bp, BevVert *bv, bool construct) } else { /* neither e->prev nor e->prev->prev are beveled: make on-edge on e->prev */ - offset_meet(e->prev, e, bv->v, e->fprev, co); + offset_meet(e->prev, e, bv->v, e->fprev, false, co); if (construct) { v = add_new_bound_vert(mem_arena, vm, co); v->efirst = e->prev; @@ -1565,7 +1997,7 @@ static void build_boundary(BevelParams *bp, BevVert *bv, bool construct) } else if (e->prev->is_bev) { /* on-edge meet between e->prev and e */ - offset_meet(e->prev, e, bv->v, e->fprev, co); + offset_meet(e->prev, e, bv->v, e->fprev, false, co); if (construct) { v = add_new_bound_vert(mem_arena, vm, co); v->efirst = e->prev; @@ -1642,6 +2074,7 @@ static void build_boundary(BevelParams *bp, BevVert *bv, bool construct) } } } +#endif /* Do a global pass to try to make offsets as even as possible. * Consider this graph: @@ -1861,9 +2294,10 @@ static void vmesh_center(VMesh *vm, float r_cent[3]) } } -static void avg4(float co[3], - const NewVert *v0, const NewVert *v1, - const NewVert *v2, const NewVert *v3) +static void avg4( + float co[3], + const NewVert *v0, const NewVert *v1, + const NewVert *v2, const NewVert *v3) { add_v3_v3v3(co, v0->co, v1->co); add_v3_v3(co, v2->co); @@ -2778,7 +3212,7 @@ static void bevel_vert_two_edges(BevelParams *bp, BMesh *bm, BevVert *bv) copy_mesh_vert(vm, 1, 0, ns - k, 0, 0, k); } - if (BM_vert_face_count(bv->v) == 0) { + if (BM_vert_face_check(bv->v) == false) { e_eg = bv->edges[0].e; BLI_assert(e_eg != NULL); for (k = 0; k < ns; k++) { @@ -3755,10 +4189,11 @@ static float bevel_limit_offset(BMesh *bm, BevelParams *bp) * * \warning all tagged edges _must_ be manifold. */ -void BM_mesh_bevel(BMesh *bm, const float offset, const int offset_type, - const float segments, const float profile, - const bool vertex_only, const bool use_weights, const bool limit_offset, - const struct MDeformVert *dvert, const int vertex_group, const int mat) +void BM_mesh_bevel( + BMesh *bm, const float offset, const int offset_type, + const float segments, const float profile, + const bool vertex_only, const bool use_weights, const bool limit_offset, + const struct MDeformVert *dvert, const int vertex_group, const int mat) { BMIter iter; BMVert *v, *v_next; diff --git a/source/blender/bmesh/tools/bmesh_bevel.h b/source/blender/bmesh/tools/bmesh_bevel.h index 52d8faa5401..b4bb6c56b7d 100644 --- a/source/blender/bmesh/tools/bmesh_bevel.h +++ b/source/blender/bmesh/tools/bmesh_bevel.h @@ -29,9 +29,10 @@ struct MDeformVert; -void BM_mesh_bevel(BMesh *bm, const float offset, const int offset_type, const float segments, - const float profile, const bool vertex_only, const bool use_weights, - const bool limit_offset, const struct MDeformVert *dvert, const int vertex_group, - const int mat); +void BM_mesh_bevel( + BMesh *bm, const float offset, const int offset_type, const float segments, + const float profile, const bool vertex_only, const bool use_weights, + const bool limit_offset, const struct MDeformVert *dvert, const int vertex_group, + const int mat); #endif /* __BMESH_BEVEL_H__ */ diff --git a/source/blender/bmesh/tools/bmesh_bisect_plane.c b/source/blender/bmesh/tools/bmesh_bisect_plane.c index e6e33c905da..fbcf573acd9 100644 --- a/source/blender/bmesh/tools/bmesh_bisect_plane.c +++ b/source/blender/bmesh/tools/bmesh_bisect_plane.c @@ -106,7 +106,7 @@ static int bm_vert_sortval_cb(const void *v_a_v, const void *v_b_v) if (val_a > val_b) return 1; else if (val_a < val_b) return -1; - return 0; + else return 0; } diff --git a/source/blender/bmesh/tools/bmesh_decimate.h b/source/blender/bmesh/tools/bmesh_decimate.h index a1b26990587..6415da9a0c2 100644 --- a/source/blender/bmesh/tools/bmesh_decimate.h +++ b/source/blender/bmesh/tools/bmesh_decimate.h @@ -27,21 +27,22 @@ * \ingroup bmesh */ -void BM_mesh_decimate_collapse(BMesh *bm, const float factor, float *vweights, const bool do_triangulate); +void BM_mesh_decimate_collapse( + BMesh *bm, const float factor, + float *vweights, float vweight_factor, + const bool do_triangulate); void BM_mesh_decimate_unsubdivide_ex(BMesh *bm, const int iterations, const bool tag_only); void BM_mesh_decimate_unsubdivide(BMesh *bm, const int iterations); -void BM_mesh_decimate_dissolve_ex(BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries, - const BMO_Delimit delimit, - BMVert **vinput_arr, const int vinput_len, - BMEdge **einput_arr, const int einput_len, - const short oflag_out); -void BM_mesh_decimate_dissolve(BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries, - const BMO_Delimit delimit); - -/* these weights are accumulated so too high values may reach 'inf' too quickly */ -#define BM_MESH_DECIM_WEIGHT_MAX 100000.0f -#define BM_MESH_DECIM_WEIGHT_EPS (1.0f / BM_MESH_DECIM_WEIGHT_MAX) +void BM_mesh_decimate_dissolve_ex( + BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries, + BMO_Delimit delimit, + BMVert **vinput_arr, const int vinput_len, + BMEdge **einput_arr, const int einput_len, + const short oflag_out); +void BM_mesh_decimate_dissolve( + BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries, + const BMO_Delimit delimit); #endif /* __BMESH_DECIMATE_H__ */ diff --git a/source/blender/bmesh/tools/bmesh_decimate_collapse.c b/source/blender/bmesh/tools/bmesh_decimate_collapse.c index 811a144fc39..c3533245d9b 100644 --- a/source/blender/bmesh/tools/bmesh_decimate_collapse.c +++ b/source/blender/bmesh/tools/bmesh_decimate_collapse.c @@ -47,6 +47,12 @@ #define USE_TRIANGULATE #define USE_VERT_NORMAL_INTERP /* has the advantage that flipped faces don't mess up vertex normals */ +/* if the cost from #BLI_quadric_evaluate is 'noise', fallback to topology */ +#define USE_TOPOLOGY_FALLBACK +#ifdef USE_TOPOLOGY_FALLBACK +# define TOPOLOGY_FALLBACK_EPS FLT_EPSILON +#endif + /* these checks are for rare cases that we can't avoid since they are valid meshes still */ #define USE_SAFETY_CHECKS @@ -77,12 +83,15 @@ static void bm_decim_build_quadrics(BMesh *bm, Quadric *vquadrics) BMLoop *l_first; BMLoop *l_iter; - const float *co = BM_FACE_FIRST_LOOP(f)->v->co; - const float *no = f->no; - const float offset = -dot_v3v3(no, co); + float center[3]; + double plane_db[4]; Quadric q; - BLI_quadric_from_v3_dist(&q, no, offset); + BM_face_calc_center_mean(f, center); + copy_v3db_v3fl(plane_db, f->no); + plane_db[3] = -dot_v3db_v3fl(plane_db, center); + + BLI_quadric_from_plane(&q, plane_db); l_iter = l_first = BM_FACE_FIRST_LOOP(f); do { @@ -94,14 +103,22 @@ static void bm_decim_build_quadrics(BMesh *bm, Quadric *vquadrics) BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { if (UNLIKELY(BM_edge_is_boundary(e))) { float edge_vector[3]; - float edge_cross[3]; + float edge_plane[3]; + double edge_plane_db[4]; sub_v3_v3v3(edge_vector, e->v2->co, e->v1->co); f = e->l->f; - cross_v3_v3v3(edge_cross, edge_vector, f->no); - if (normalize_v3(edge_cross) > FLT_EPSILON) { + cross_v3_v3v3(edge_plane, edge_vector, f->no); + copy_v3db_v3fl(edge_plane_db, edge_plane); + + if (normalize_v3_d(edge_plane_db) > FLT_EPSILON) { Quadric q; - BLI_quadric_from_v3_dist(&q, edge_cross, -dot_v3v3(edge_cross, e->v1->co)); + float center[3]; + + mid_v3_v3v3(center, e->v1->co, e->v2->co); + + edge_plane_db[3] = -dot_v3db_v3fl(edge_plane_db, center); + BLI_quadric_from_plane(&q, edge_plane_db); BLI_quadric_mul(&q, BOUNDARY_PRESERVE_WEIGHT); BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(e->v1)], &q); @@ -112,18 +129,19 @@ static void bm_decim_build_quadrics(BMesh *bm, Quadric *vquadrics) } -static void bm_decim_calc_target_co(BMEdge *e, float optimize_co[3], - const Quadric *vquadrics) +static void bm_decim_calc_target_co( + BMEdge *e, float optimize_co[3], + const Quadric *vquadrics) { /* compute an edge contraction target for edge 'e' * this is computed by summing it's vertices quadrics and * optimizing the result. */ Quadric q; - BLI_quadric_add_qu_ququ(&q, - &vquadrics[BM_elem_index_get(e->v1)], - &vquadrics[BM_elem_index_get(e->v2)]); - + BLI_quadric_add_qu_ququ( + &q, + &vquadrics[BM_elem_index_get(e->v1)], + &vquadrics[BM_elem_index_get(e->v2)]); if (BLI_quadric_optimize(&q, optimize_co, OPTIMIZE_EPS)) { return; /* all is good */ @@ -162,13 +180,15 @@ static bool bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_ cross_v3_v3v3(cross_exist, vec_other, vec_exist); cross_v3_v3v3(cross_optim, vec_other, vec_optim); - /* normalize isn't really needed, but ensures the value at a unit we can compare against */ - normalize_v3(cross_exist); - normalize_v3(cross_optim); + /* avoid normalize */ + if (dot_v3v3(cross_exist, cross_optim) <= + (len_squared_v3(cross_exist) + len_squared_v3(cross_optim)) * 0.01f) + { + return true; + } #else normal_tri_v3(cross_exist, v->co, co_prev, co_next); normal_tri_v3(cross_optim, optimize_co, co_prev, co_next); -#endif /* use a small value rather then zero so we don't flip a face in multiple steps * (first making it zero area, then flipping again) */ @@ -176,6 +196,8 @@ static bool bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_ //printf("no flip\n"); return true; } +#endif + } } } @@ -183,9 +205,29 @@ static bool bm_edge_collapse_is_degenerate_flip(BMEdge *e, const float optimize_ return false; } -static void bm_decim_build_edge_cost_single(BMEdge *e, - const Quadric *vquadrics, const float *vweights, - Heap *eheap, HeapNode **eheap_table) +#ifdef USE_TOPOLOGY_FALLBACK +/** + * when the cost is so small that its not useful (flat surfaces), + * fallback to using a 'topology' cost. + * + * This avoids cases where a flat (or near flat) areas get very un-even geometry. + */ +static float bm_decim_build_edge_cost_single_squared__topology(BMEdge *e) +{ + return fabsf(dot_v3v3(e->v1->no, e->v2->no)) / min_ff(-len_squared_v3v3(e->v1->co, e->v2->co), -FLT_EPSILON); +} +static float bm_decim_build_edge_cost_single__topology(BMEdge *e) +{ + return fabsf(dot_v3v3(e->v1->no, e->v2->no)) / min_ff(-len_v3v3(e->v1->co, e->v2->co), -FLT_EPSILON); +} + +#endif /* USE_TOPOLOGY_FALLBACK */ + +static void bm_decim_build_edge_cost_single( + BMEdge *e, + const Quadric *vquadrics, + const float *vweights, const float vweight_factor, + Heap *eheap, HeapNode **eheap_table) { const Quadric *q1, *q2; float optimize_co[3]; @@ -202,8 +244,7 @@ static void bm_decim_build_edge_cost_single(BMEdge *e, } else { /* only collapse tri's */ - eheap_table[BM_elem_index_get(e)] = NULL; - return; + goto clear; } } else if (BM_edge_is_manifold(e)) { @@ -212,23 +253,11 @@ static void bm_decim_build_edge_cost_single(BMEdge *e, } else { /* only collapse tri's */ - eheap_table[BM_elem_index_get(e)] = NULL; - return; + goto clear; } } else { - eheap_table[BM_elem_index_get(e)] = NULL; - return; - } - - if (vweights) { - if ((vweights[BM_elem_index_get(e->v1)] >= BM_MESH_DECIM_WEIGHT_MAX) && - (vweights[BM_elem_index_get(e->v2)] >= BM_MESH_DECIM_WEIGHT_MAX)) - { - /* skip collapsing this edge */ - eheap_table[BM_elem_index_get(e)] = NULL; - return; - } + goto clear; } /* end sanity check */ @@ -238,36 +267,71 @@ static void bm_decim_build_edge_cost_single(BMEdge *e, q1 = &vquadrics[BM_elem_index_get(e->v1)]; q2 = &vquadrics[BM_elem_index_get(e->v2)]; - if (vweights == NULL) { - cost = (BLI_quadric_evaluate(q1, optimize_co) + - BLI_quadric_evaluate(q2, optimize_co)); - } - else { - /* add 1.0 so planar edges are still weighted against */ - cost = (((BLI_quadric_evaluate(q1, optimize_co) + 1.0f) * vweights[BM_elem_index_get(e->v1)]) + - ((BLI_quadric_evaluate(q2, optimize_co) + 1.0f) * vweights[BM_elem_index_get(e->v2)])); - } - // print("COST %.12f\n"); + cost = (BLI_quadric_evaluate(q1, optimize_co) + + BLI_quadric_evaluate(q2, optimize_co)); + /* note, 'cost' shouldn't be negative but happens sometimes with small values. * this can cause faces that make up a flat surface to over-collapse, see [#37121] */ cost = fabsf(cost); + +#ifdef USE_TOPOLOGY_FALLBACK + if (UNLIKELY(cost < TOPOLOGY_FALLBACK_EPS)) { + /* subtract existing cost to further differentiate edges from one another + * + * keep topology cost below 0.0 so their values don't interfere with quadric cost, + * (and they get handled first). + * */ + if (vweights == NULL) { + cost = bm_decim_build_edge_cost_single_squared__topology(e) - cost; + } + else { + /* with weights we need to use the real length so we can scale them properly */ + const float e_weight = (vweights[BM_elem_index_get(e->v1)] + + vweights[BM_elem_index_get(e->v2)]); + cost = bm_decim_build_edge_cost_single__topology(e) - cost; + /* note, this is rather arbitrary max weight is 2 here, + * allow for skipping edges 4x the length, based on weights */ + if (e_weight) { + cost *= 1.0f + (e_weight * vweight_factor); + } + + BLI_assert(cost <= 0.0f); + } + } + else +#endif + if (vweights) { + const float e_weight = 2.0f - (vweights[BM_elem_index_get(e->v1)] + + vweights[BM_elem_index_get(e->v2)]); + if (e_weight) { + cost += (BM_edge_calc_length(e) * ((e_weight * vweight_factor))); + } + } + eheap_table[BM_elem_index_get(e)] = BLI_heap_insert(eheap, cost, e); + return; + +clear: + eheap_table[BM_elem_index_get(e)] = NULL; } /* use this for degenerate cases - add back to the heap with an invalid cost, * this way it may be calculated again if surrounding geometry changes */ -static void bm_decim_invalid_edge_cost_single(BMEdge *e, - Heap *eheap, HeapNode **eheap_table) +static void bm_decim_invalid_edge_cost_single( + BMEdge *e, + Heap *eheap, HeapNode **eheap_table) { BLI_assert(eheap_table[BM_elem_index_get(e)] == NULL); eheap_table[BM_elem_index_get(e)] = BLI_heap_insert(eheap, COST_INVALID, e); } -static void bm_decim_build_edge_cost(BMesh *bm, - const Quadric *vquadrics, const float *vweights, - Heap *eheap, HeapNode **eheap_table) +static void bm_decim_build_edge_cost( + BMesh *bm, + const Quadric *vquadrics, + const float *vweights, const float vweight_factor, + Heap *eheap, HeapNode **eheap_table) { BMIter iter; BMEdge *e; @@ -275,7 +339,7 @@ static void bm_decim_build_edge_cost(BMesh *bm, BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) { eheap_table[i] = NULL; /* keep sanity check happy */ - bm_decim_build_edge_cost_single(e, vquadrics, vweights, eheap, eheap_table); + bm_decim_build_edge_cost_single(e, vquadrics, vweights, vweight_factor, eheap, eheap_table); } } @@ -440,10 +504,11 @@ static void bm_decim_triangulate_end(BMesh *bm) #ifdef USE_CUSTOMDATA /** - * \param v is the target to merge into. + * \param l: defines the vert to collapse into. */ -static void bm_edge_collapse_loop_customdata(BMesh *bm, BMLoop *l, BMVert *v_clear, BMVert *v_other, - const float customdata_fac) +static void bm_edge_collapse_loop_customdata( + BMesh *bm, BMLoop *l, BMVert *v_clear, BMVert *v_other, + const float customdata_fac) { /* disable seam check - the seam check would have to be done per layer, its not really that important */ //#define USE_SEAM @@ -452,8 +517,6 @@ static void bm_edge_collapse_loop_customdata(BMesh *bm, BMLoop *l, BMVert *v_cle const bool is_manifold = BM_edge_is_manifold(l->e); int side; - /* l defines the vert to collapse into */ - /* first find the loop of 'v_other' thats attached to the face of 'l' */ if (l->v == v_clear) { l_clear = l; @@ -695,18 +758,19 @@ static bool bm_edge_collapse_is_degenerate_topology(BMEdge *e_first) * * Important - dont add vert/edge/face data on collapsing! * - * \param e_clear_other let caller know what edges we remove besides \a e_clear - * \param customdata_flag merge factor, scales from 0 - 1 ('v_clear' -> 'v_other') + * \param r_e_clear_other: Let caller know what edges we remove besides \a e_clear + * \param customdata_flag: Merge factor, scales from 0 - 1 ('v_clear' -> 'v_other') */ -static bool bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e_clear_other[2], +static bool bm_edge_collapse( + BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_e_clear_other[2], #ifdef USE_CUSTOMDATA - const CD_UseFlag customdata_flag, - const float customdata_fac + const CD_UseFlag customdata_flag, + const float customdata_fac #else - const CD_UseFlag UNUSED(customdata_flag), - const float UNUSED(customdata_fac) + const CD_UseFlag UNUSED(customdata_flag), + const float UNUSED(customdata_fac) #endif - ) + ) { BMVert *v_other; @@ -782,12 +846,12 @@ static bool bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_ BM_edge_kill(bm, e_clear); v_other->head.hflag |= v_clear->head.hflag; - BM_vert_splice(bm, v_clear, v_other); + BM_vert_splice(bm, v_other, v_clear); e_a_other[1]->head.hflag |= e_a_other[0]->head.hflag; e_b_other[1]->head.hflag |= e_b_other[0]->head.hflag; - BM_edge_splice(bm, e_a_other[0], e_a_other[1]); - BM_edge_splice(bm, e_b_other[0], e_b_other[1]); + BM_edge_splice(bm, e_a_other[1], e_a_other[0]); + BM_edge_splice(bm, e_b_other[1], e_b_other[0]); // BM_mesh_validate(bm); @@ -831,10 +895,10 @@ static bool bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_ BM_edge_kill(bm, e_clear); v_other->head.hflag |= v_clear->head.hflag; - BM_vert_splice(bm, v_clear, v_other); + BM_vert_splice(bm, v_other, v_clear); e_a_other[1]->head.hflag |= e_a_other[0]->head.hflag; - BM_edge_splice(bm, e_a_other[0], e_a_other[1]); + BM_edge_splice(bm, e_a_other[1], e_a_other[0]); // BM_mesh_validate(bm); @@ -847,14 +911,17 @@ static bool bm_edge_collapse(BMesh *bm, BMEdge *e_clear, BMVert *v_clear, int r_ /* collapse e the edge, removing e->v2 */ -static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e, - Quadric *vquadrics, float *vweights, - Heap *eheap, HeapNode **eheap_table, - const CD_UseFlag customdata_flag) +static void bm_decim_edge_collapse( + BMesh *bm, BMEdge *e, + Quadric *vquadrics, + float *vweights, const float vweight_factor, + Heap *eheap, HeapNode **eheap_table, + const CD_UseFlag customdata_flag) { int e_clear_other[2]; BMVert *v_other = e->v1; - int v_clear_index = BM_elem_index_get(e->v2); /* the vert is removed so only store the index */ + const int v_other_index = BM_elem_index_get(e->v1); + const int v_clear_index = BM_elem_index_get(e->v2); /* the vert is removed so only store the index */ float optimize_co[3]; float customdata_fac; @@ -897,7 +964,9 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e, int i; if (vweights) { - vweights[BM_elem_index_get(v_other)] += vweights[v_clear_index]; + float v_other_weight = interpf(vweights[v_other_index], vweights[v_clear_index], customdata_fac); + CLAMP(v_other_weight, 0.0f, 1.0f); + vweights[v_other_index] = v_other_weight; } e = NULL; /* paranoid safety check */ @@ -914,7 +983,7 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e, } /* update vertex quadric, add kept vertex from killed vertex */ - BLI_quadric_add_qu_qu(&vquadrics[BM_elem_index_get(v_other)], &vquadrics[v_clear_index]); + BLI_quadric_add_qu_qu(&vquadrics[v_other_index], &vquadrics[v_clear_index]); /* update connected normals */ @@ -935,7 +1004,7 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e, e_iter = e_first = v_other->e; do { BLI_assert(BM_edge_find_double(e_iter) == NULL); - bm_decim_build_edge_cost_single(e_iter, vquadrics, vweights, eheap, eheap_table); + bm_decim_build_edge_cost_single(e_iter, vquadrics, vweights, vweight_factor, eheap, eheap_table); } while ((e_iter = bmesh_disk_edge_next(e_iter, v_other)) != e_first); } @@ -957,7 +1026,7 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e, BLI_assert(BM_vert_in_edge(e_outer, l->v) == false); - bm_decim_build_edge_cost_single(e_outer, vquadrics, vweights, eheap, eheap_table); + bm_decim_build_edge_cost_single(e_outer, vquadrics, vweights, vweight_factor, eheap, eheap_table); } } } @@ -981,7 +1050,11 @@ static void bm_decim_edge_collapse(BMesh *bm, BMEdge *e, * \param vweights Optional array of vertex aligned weights [0 - 1], * a vertex group is the usual source for this. */ -void BM_mesh_decimate_collapse(BMesh *bm, const float factor, float *vweights, const bool do_triangulate) +void BM_mesh_decimate_collapse( + BMesh *bm, + const float factor, + float *vweights, float vweight_factor, + const bool do_triangulate) { Heap *eheap; /* edge heap */ HeapNode **eheap_table; /* edge index aligned table pointing to the eheap */ @@ -1009,7 +1082,7 @@ void BM_mesh_decimate_collapse(BMesh *bm, const float factor, float *vweights, c /* build initial edge collapse cost data */ bm_decim_build_quadrics(bm, vquadrics); - bm_decim_build_edge_cost(bm, vquadrics, vweights, eheap, eheap_table); + bm_decim_build_edge_cost(bm, vquadrics, vweights, vweight_factor, eheap, eheap_table); face_tot_target = bm->totface * factor; bm->elem_index_dirty |= BM_ALL; @@ -1031,13 +1104,11 @@ void BM_mesh_decimate_collapse(BMesh *bm, const float factor, float *vweights, c BMEdge *e = BLI_heap_popmin(eheap); BLI_assert(BM_elem_index_get(e) < tot_edge_orig); /* handy to detect corruptions elsewhere */ - // printf("COST %.10f\n", value); - /* under normal conditions wont be accessed again, * but NULL just incase so we don't use freed node */ eheap_table[BM_elem_index_get(e)] = NULL; - bm_decim_edge_collapse(bm, e, vquadrics, vweights, eheap, eheap_table, customdata_flag); + bm_decim_edge_collapse(bm, e, vquadrics, vweights, vweight_factor, eheap, eheap_table, customdata_flag); } diff --git a/source/blender/bmesh/tools/bmesh_decimate_dissolve.c b/source/blender/bmesh/tools/bmesh_decimate_dissolve.c index 096349e8e9c..a1460cec7d1 100644 --- a/source/blender/bmesh/tools/bmesh_decimate_dissolve.c +++ b/source/blender/bmesh/tools/bmesh_decimate_dissolve.c @@ -32,6 +32,8 @@ #include "BLI_math.h" #include "BLI_heap.h" +#include "BKE_customdata.h" + #include "bmesh.h" #include "bmesh_decimate.h" /* own include */ @@ -59,7 +61,32 @@ static float bm_vert_edge_face_angle(BMVert *v) #undef ANGLE_TO_UNIT } -static float bm_edge_calc_dissolve_error(const BMEdge *e, const BMO_Delimit delimit) +struct DelimitData { + int cd_loop_type; + int cd_loop_size; + int cd_loop_offset; + int cd_loop_offset_end; +}; + +static bool bm_edge_is_contiguous_loop_cd_all( + const BMEdge *e, const struct DelimitData *delimit_data) +{ + int cd_loop_offset; + for (cd_loop_offset = delimit_data->cd_loop_offset; + cd_loop_offset < delimit_data->cd_loop_offset_end; + cd_loop_offset += delimit_data->cd_loop_size) + { + if (BM_edge_is_contiguous_loop_cd(e, delimit_data->cd_loop_type, cd_loop_offset) == false) { + return false; + } + } + + return true; +} + +static float bm_edge_calc_dissolve_error( + const BMEdge *e, const BMO_Delimit delimit, + const struct DelimitData *delimit_data) { const bool is_contig = BM_edge_is_contiguous(e); float angle; @@ -74,6 +101,12 @@ static float bm_edge_calc_dissolve_error(const BMEdge *e, const BMO_Delimit deli goto fail; } + if ((delimit & BMO_DELIM_SHARP) && + (BM_elem_flag_test(e, BM_ELEM_SMOOTH) == 0)) + { + goto fail; + } + if ((delimit & BMO_DELIM_MATERIAL) && (e->l->f->mat_nr != e->l->radial_next->f->mat_nr)) { @@ -86,6 +119,12 @@ static float bm_edge_calc_dissolve_error(const BMEdge *e, const BMO_Delimit deli goto fail; } + if ((delimit & BMO_DELIM_UV) && + (bm_edge_is_contiguous_loop_cd_all(e, delimit_data) == 0)) + { + goto fail; + } + angle = BM_edge_calc_face_angle(e); if (is_contig == false) { angle = (float)M_PI - angle; @@ -98,17 +137,32 @@ fail: } -void BM_mesh_decimate_dissolve_ex(BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries, - const BMO_Delimit delimit, - BMVert **vinput_arr, const int vinput_len, - BMEdge **einput_arr, const int einput_len, - const short oflag_out) +void BM_mesh_decimate_dissolve_ex( + BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries, + BMO_Delimit delimit, + BMVert **vinput_arr, const int vinput_len, + BMEdge **einput_arr, const int einput_len, + const short oflag_out) { + struct DelimitData delimit_data = {0}; const int eheap_table_len = do_dissolve_boundaries ? einput_len : max_ii(einput_len, vinput_len); void *_heap_table = MEM_mallocN(sizeof(HeapNode *) * eheap_table_len, __func__); int i; + if (delimit & BMO_DELIM_UV) { + const int layer_len = CustomData_number_of_layers(&bm->ldata, CD_MLOOPUV); + if (layer_len == 0) { + delimit &= ~BMO_DELIM_UV; + } + else { + delimit_data.cd_loop_type = CD_MLOOPUV; + delimit_data.cd_loop_size = CustomData_sizeof(delimit_data.cd_loop_type); + delimit_data.cd_loop_offset = CustomData_get_n_offset(&bm->ldata, CD_MLOOPUV, 0); + delimit_data.cd_loop_offset_end = delimit_data.cd_loop_size * layer_len; + } + } + /* --- first edges --- */ if (1) { BMEdge **earray; @@ -133,7 +187,7 @@ void BM_mesh_decimate_dissolve_ex(BMesh *bm, const float angle_limit, const bool /* build heap */ for (i = 0; i < einput_len; i++) { BMEdge *e = einput_arr[i]; - const float cost = bm_edge_calc_dissolve_error(e, delimit); + const float cost = bm_edge_calc_dissolve_error(e, delimit, &delimit_data); eheap_table[i] = BLI_heap_insert(eheap, cost, e); BM_elem_index_set(e, i); /* set dirty */ } @@ -169,7 +223,7 @@ void BM_mesh_decimate_dissolve_ex(BMesh *bm, const float angle_limit, const bool do { const int j = BM_elem_index_get(l_iter->e); if (j != -1 && eheap_table[j]) { - const float cost = bm_edge_calc_dissolve_error(l_iter->e, delimit); + const float cost = bm_edge_calc_dissolve_error(l_iter->e, delimit, &delimit_data); BLI_heap_remove(eheap, eheap_table[j]); eheap_table[j] = BLI_heap_insert(eheap, cost, l_iter->e); } @@ -189,7 +243,7 @@ void BM_mesh_decimate_dissolve_ex(BMesh *bm, const float angle_limit, const bool /* prepare for cleanup */ BM_mesh_elem_index_ensure(bm, BM_VERT); vert_reverse_lookup = MEM_mallocN(sizeof(int) * bm->totvert, __func__); - fill_vn_i(vert_reverse_lookup, bm->totvert, -1); + copy_vn_i(vert_reverse_lookup, bm->totvert, -1); for (i = 0; i < vinput_len; i++) { BMVert *v = vinput_arr[i]; vert_reverse_lookup[BM_elem_index_get(v)] = i; @@ -316,8 +370,9 @@ void BM_mesh_decimate_dissolve_ex(BMesh *bm, const float angle_limit, const bool MEM_freeN(_heap_table); } -void BM_mesh_decimate_dissolve(BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries, - const BMO_Delimit delimit) +void BM_mesh_decimate_dissolve( + BMesh *bm, const float angle_limit, const bool do_dissolve_boundaries, + const BMO_Delimit delimit) { int vinput_len; int einput_len; diff --git a/source/blender/bmesh/tools/bmesh_edgenet.c b/source/blender/bmesh/tools/bmesh_edgenet.c index 1328b81b746..2a1946df7ae 100644 --- a/source/blender/bmesh/tools/bmesh_edgenet.c +++ b/source/blender/bmesh/tools/bmesh_edgenet.c @@ -166,8 +166,8 @@ static BMFace *bm_edgenet_face_from_path( { BMFace *f; LinkNode *v_lnk; - unsigned int i; - unsigned int i_prev; + int i; + bool ok; BMVert **vert_arr = BLI_array_alloca(vert_arr, path_len); BMEdge **edge_arr = BLI_array_alloca(edge_arr, path_len); @@ -176,11 +176,9 @@ static BMFace *bm_edgenet_face_from_path( vert_arr[i] = v_lnk->link; } - i_prev = path_len - 1; - for (i = 0; i < path_len; i++) { - edge_arr[i_prev] = BM_edge_exists(vert_arr[i], vert_arr[i_prev]); - i_prev = i; - } + ok = BM_edges_from_verts(edge_arr, vert_arr, i); + BLI_assert(ok); + UNUSED_VARS_NDEBUG(ok); /* no need for this, we do overlap checks before allowing the path to be used */ #if 0 @@ -448,10 +446,10 @@ static LinkNode *bm_edgenet_path_calc_best( * * \param bm The mesh to operate on. * \param use_edge_tag Only fill tagged edges. - * \param face_oflag if nonzero, apply all new faces with this bmo flag. */ -void BM_mesh_edgenet(BMesh *bm, - const bool use_edge_tag, const bool use_new_face_tag) +void BM_mesh_edgenet( + BMesh *bm, + const bool use_edge_tag, const bool use_new_face_tag) { VertNetInfo *vnet_info = MEM_callocN(sizeof(*vnet_info) * (size_t)bm->totvert, __func__); BLI_mempool *edge_queue_pool = BLI_mempool_create(sizeof(LinkNode), 0, 512, BLI_MEMPOOL_NOP); diff --git a/source/blender/bmesh/tools/bmesh_edgenet.h b/source/blender/bmesh/tools/bmesh_edgenet.h index 327a7f5aa23..1ad5cadae7c 100644 --- a/source/blender/bmesh/tools/bmesh_edgenet.h +++ b/source/blender/bmesh/tools/bmesh_edgenet.h @@ -27,7 +27,8 @@ * \ingroup bmesh */ -void BM_mesh_edgenet(BMesh *bm, - const bool use_edge_tag, const bool use_new_face_tag); +void BM_mesh_edgenet( + BMesh *bm, + const bool use_edge_tag, const bool use_new_face_tag); #endif /* __BMESH_EDGENET_H__ */ diff --git a/source/blender/bmesh/tools/bmesh_edgesplit.c b/source/blender/bmesh/tools/bmesh_edgesplit.c index 947b77675d8..a59a5c43c82 100644 --- a/source/blender/bmesh/tools/bmesh_edgesplit.c +++ b/source/blender/bmesh/tools/bmesh_edgesplit.c @@ -35,70 +35,15 @@ #include "bmesh_edgesplit.h" /* own include */ - /** - * Remove the BM_ELEM_TAG flag for edges we cant split - * - * un-tag edges not connected to other tagged edges, - * unless they are on a boundary + * \param use_verts Use flagged verts instead of edges. + * \param tag_only Only split tagged edges. + * \param copy_select Copy selection history. */ -static void bm_edgesplit_validate_seams(BMesh *bm) -{ - BMIter iter; - BMEdge *e; - - unsigned char *vtouch; - - BM_mesh_elem_index_ensure(bm, BM_VERT); - - vtouch = MEM_callocN(sizeof(char) * bm->totvert, __func__); - - /* tag all boundary verts so as not to untag an edge which is inbetween only 2 faces [] */ - BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { - - /* unrelated to flag assignment in this function - since this is the - * only place we loop over all edges, disable tag */ - BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG); - - if (e->l == NULL) { - BM_elem_flag_disable(e, BM_ELEM_TAG); - } - else if (BM_edge_is_boundary(e)) { - unsigned char *vt; - vt = &vtouch[BM_elem_index_get(e->v1)]; if (*vt < 2) (*vt)++; - vt = &vtouch[BM_elem_index_get(e->v2)]; if (*vt < 2) (*vt)++; - - /* while the boundary verts need to be tagged, - * the edge its self can't be split */ - BM_elem_flag_disable(e, BM_ELEM_TAG); - } - } - - /* single marked edges unconnected to any other marked edges - * are illegal, go through and unmark them */ - BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { - if (BM_elem_flag_test(e, BM_ELEM_TAG)) { - /* lame, but we don't want the count to exceed 255, - * so just count to 2, its all we need */ - unsigned char *vt; - vt = &vtouch[BM_elem_index_get(e->v1)]; if (*vt < 2) (*vt)++; - vt = &vtouch[BM_elem_index_get(e->v2)]; if (*vt < 2) (*vt)++; - } - } - BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { - if (BM_elem_flag_test(e, BM_ELEM_TAG)) { - if (vtouch[BM_elem_index_get(e->v1)] == 1 && - vtouch[BM_elem_index_get(e->v2)] == 1) - { - BM_elem_flag_disable(e, BM_ELEM_TAG); - } - } - } - - MEM_freeN(vtouch); -} - -void BM_mesh_edgesplit(BMesh *bm, const bool use_verts, const bool tag_only, const bool copy_select) +void BM_mesh_edgesplit( + BMesh *bm, + const bool use_verts, + const bool tag_only, const bool copy_select) { BMIter iter; BMEdge *e; @@ -142,43 +87,13 @@ void BM_mesh_edgesplit(BMesh *bm, const bool use_verts, const bool tag_only, con } } - bm_edgesplit_validate_seams(bm); - BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { if (BM_elem_flag_test(e, BM_ELEM_TAG)) { - /* this flag gets copied so we can be sure duplicate edges get it too (important) */ - BM_elem_flag_enable(e, BM_ELEM_INTERNAL_TAG); - - /* keep splitting until each loop has its own edge */ - while (!BM_edge_is_boundary(e)) { - BMLoop *l_sep = e->l; - bmesh_edge_separate(bm, e, l_sep, copy_select); - BLI_assert(l_sep->e != e); - - if (use_ese) { - BMEditSelection *ese = BLI_ghash_lookup(ese_gh, e); - if (UNLIKELY(ese)) { - BM_select_history_store_after_notest(bm, ese, l_sep->e); - } - } - } - BM_elem_flag_enable(e->v1, BM_ELEM_TAG); BM_elem_flag_enable(e->v2, BM_ELEM_TAG); } } - if (use_verts) { - BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { - if (BM_elem_flag_test(e->v1, BM_ELEM_TAG) == false) { - BM_elem_flag_disable(e->v1, BM_ELEM_TAG); - } - if (BM_elem_flag_test(e->v2, BM_ELEM_TAG) == false) { - BM_elem_flag_disable(e->v2, BM_ELEM_TAG); - } - } - } - BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { if (BM_elem_flag_test(e, BM_ELEM_TAG)) { unsigned int i; @@ -191,7 +106,7 @@ void BM_mesh_edgesplit(BMesh *bm, const bool use_verts, const bool tag_only, con BMVert **vtar; int vtar_len; - bmesh_vert_separate(bm, v, &vtar, &vtar_len, copy_select); + BM_vert_separate_hflag(bm, v, BM_ELEM_TAG, copy_select, &vtar, &vtar_len); /* first value is always in 'v' */ if (vtar_len > 1) { @@ -208,13 +123,22 @@ void BM_mesh_edgesplit(BMesh *bm, const bool use_verts, const bool tag_only, con MEM_freeN(vtar); } else { - bmesh_vert_separate(bm, v, NULL, NULL, copy_select); + BM_vert_separate_hflag(bm, v, BM_ELEM_TAG, copy_select, NULL, NULL); } } } } } +#ifndef NDEBUG + /* ensure we don't have any double edges! */ + BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + if (BM_elem_flag_test(e, BM_ELEM_TAG)) { + BLI_assert(BM_edge_find_double(e) == NULL); + } + } +#endif + if (use_ese) { BLI_ghash_free(ese_gh, NULL, NULL); } diff --git a/source/blender/bmesh/tools/bmesh_edgesplit.h b/source/blender/bmesh/tools/bmesh_edgesplit.h index bd66f6a9e2f..26040077f43 100644 --- a/source/blender/bmesh/tools/bmesh_edgesplit.h +++ b/source/blender/bmesh/tools/bmesh_edgesplit.h @@ -27,6 +27,9 @@ * \ingroup bmesh */ -void BM_mesh_edgesplit(BMesh *bm, const bool use_verts, const bool tag_only, const bool copy_select); +void BM_mesh_edgesplit( + BMesh *bm, + const bool use_verts, + const bool tag_only, const bool copy_select); #endif /* __BMESH_EDGESPLIT_H__ */ diff --git a/source/blender/bmesh/tools/bmesh_intersect.c b/source/blender/bmesh/tools/bmesh_intersect.c index 064dbd7405b..fc12bce8563 100644 --- a/source/blender/bmesh/tools/bmesh_intersect.c +++ b/source/blender/bmesh/tools/bmesh_intersect.c @@ -804,7 +804,7 @@ bool BM_mesh_intersect( s.edgetri_cache = BLI_ghash_new(BLI_ghashutil_inthash_v4_p, BLI_ghashutil_inthash_v4_cmp, __func__); s.edge_verts = BLI_ghash_ptr_new(__func__); - s.face_edges = BLI_ghash_ptr_new(__func__); + s.face_edges = BLI_ghash_int_new(__func__); s.wire_edges = BLI_gset_ptr_new(__func__); s.vert_dissolve = NULL; @@ -1006,7 +1006,7 @@ bool BM_mesh_intersect( !BM_vert_splice_check_double(v_prev, vi) && !BM_vert_pair_share_face_check(v_prev, vi)) { - BM_vert_splice(bm, v_prev, vi); + BM_vert_splice(bm, vi, v_prev); } else { copy_v3_v3(v_prev->co, vi->co); @@ -1040,8 +1040,8 @@ bool BM_mesh_intersect( } } - splice_ls = MEM_mallocN((unsigned int)BLI_gset_size(s.wire_edges) * sizeof(*splice_ls), __func__); - STACK_INIT(splice_ls, (unsigned int)BLI_gset_size(s.wire_edges)); + splice_ls = MEM_mallocN(BLI_gset_size(s.wire_edges) * sizeof(*splice_ls), __func__); + STACK_INIT(splice_ls, BLI_gset_size(s.wire_edges)); for (node = s.vert_dissolve; node; node = node->next) { BMEdge *e_pair[2]; @@ -1228,7 +1228,7 @@ bool BM_mesh_intersect( if (!BM_edge_exists(UNPACK2(splice_ls[i])) && !BM_vert_splice_check_double(UNPACK2(splice_ls[i]))) { - BM_vert_splice(bm, UNPACK2(splice_ls[i])); + BM_vert_splice(bm, splice_ls[i][1], splice_ls[i][0]); } } } @@ -1267,10 +1267,8 @@ bool BM_mesh_intersect( face_edges_split(bm, f, e_ls_base); } } -#else - (void)totface_orig; #endif /* USE_NET */ - + (void)totface_orig; #ifdef USE_SEPARATE if (use_separate) { diff --git a/source/blender/bmesh/tools/bmesh_path.c b/source/blender/bmesh/tools/bmesh_path.c index 8ae3507a738..6633803414b 100644 --- a/source/blender/bmesh/tools/bmesh_path.c +++ b/source/blender/bmesh/tools/bmesh_path.c @@ -126,7 +126,7 @@ LinkNode *BM_mesh_calc_path_vert( verts_prev = MEM_callocN(sizeof(*verts_prev) * totvert, __func__); cost = MEM_mallocN(sizeof(*cost) * totvert, __func__); - fill_vn_fl(cost, totvert, 1e20f); + copy_vn_fl(cost, totvert, 1e20f); /* * Arrays are now filled as follows: @@ -252,7 +252,7 @@ LinkNode *BM_mesh_calc_path_edge( edges_prev = MEM_callocN(sizeof(*edges_prev) * totedge, "SeamPathPrevious"); cost = MEM_mallocN(sizeof(*cost) * totedge, "SeamPathCost"); - fill_vn_fl(cost, totedge, 1e20f); + copy_vn_fl(cost, totedge, 1e20f); /* * Arrays are now filled as follows: @@ -378,7 +378,7 @@ LinkNode *BM_mesh_calc_path_face( faces_prev = MEM_callocN(sizeof(*faces_prev) * totface, __func__); cost = MEM_mallocN(sizeof(*cost) * totface, __func__); - fill_vn_fl(cost, totface, 1e20f); + copy_vn_fl(cost, totface, 1e20f); /* * Arrays are now filled as follows: diff --git a/source/blender/bmesh/tools/bmesh_region_match.c b/source/blender/bmesh/tools/bmesh_region_match.c index 43fd1368bb7..a6860a6614a 100644 --- a/source/blender/bmesh/tools/bmesh_region_match.c +++ b/source/blender/bmesh/tools/bmesh_region_match.c @@ -190,14 +190,18 @@ static bool ghashutil_bmelem_indexcmp(const void *a, const void *b) return (a != b); } -static GHash *ghash_bmelem_new_ex(const char *info, const unsigned int nentries_reserve) +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, false); + 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) +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, false); + return BLI_gset_new_ex(ghashutil_bmelem_indexhash, ghashutil_bmelem_indexcmp, info, nentries_reserve); } @@ -417,8 +421,8 @@ static void bm_uuidwalk_rehash( 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)); + unsigned int rehash_store_len_new = 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; @@ -507,7 +511,7 @@ static void bm_uuidwalk_pass_add( UUIDFaceStep *fstep; - BLI_assert(faces_pass_len == (unsigned int)BLI_linklist_length(faces_pass)); + BLI_assert(faces_pass_len == (unsigned int)BLI_linklist_count(faces_pass)); /* rehash faces now all their verts have been added */ bm_uuidwalk_rehash_facelinks(uuidwalk, faces_pass, faces_pass_len, true); @@ -532,12 +536,13 @@ static void bm_uuidwalk_pass_add( l_iter = l_first = BM_FACE_FIRST_LOOP(f); do { /* fill verts_new */ + void **val_p; if (!BLI_ghash_haskey(uuidwalk->verts_uuid, l_iter->v) && - !BLI_ghash_haskey(verts_uuid_pass, l_iter->v) && + !BLI_ghash_ensure_p(verts_uuid_pass, l_iter->v, &val_p) && (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); + *val_p = (void *)uuid; } /* fill faces_step_next */ @@ -612,15 +617,16 @@ static unsigned int bm_uuidwalk_init_from_edge( /* 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++) { + for (i = 0; i < f_arr_len; ) { LinkNode *faces_pass = NULL; + const unsigned int i_init = i; 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); + bm_uuidwalk_pass_add(uuidwalk, faces_pass, i - i_init); BLI_linklist_free_pool(faces_pass, NULL, uuidwalk->link_pool); fstep_num += 1; } @@ -665,13 +671,15 @@ static bool bm_uuidwalk_facestep_begin( if (!BLI_ghash_haskey(uuidwalk->faces_uuid, f)) { const UUID_Int uuid = bm_uuidwalk_calc_face_uuid(uuidwalk, f); UUIDFaceStepItem *fstep_item; + void **val_p; 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); + if (BLI_ghash_ensure_p(uuidwalk->cache.faces_from_uuid, (void *)uuid, &val_p)) { + fstep_item = *val_p; + } + else { + fstep_item = *val_p = BLI_mempool_alloc(uuidwalk->step_pool_items); /* add to start, so its handled on the next round of passes */ BLI_addhead(&fstep->items, fstep_item); @@ -856,7 +864,7 @@ static BMFace **bm_mesh_region_match_pair( break; } - found = ((unsigned int)BLI_ghash_size(w_dst->faces_uuid) == faces_src_region_len); + found = (BLI_ghash_size(w_dst->faces_uuid) == faces_src_region_len); if (found) { break; } @@ -869,7 +877,7 @@ static BMFace **bm_mesh_region_match_pair( if (found) { GHashIterator gh_iter; - const unsigned int faces_result_len = (unsigned int)BLI_ghash_size(w_dst->faces_uuid); + const unsigned int faces_result_len = BLI_ghash_size(w_dst->faces_uuid); unsigned int i; faces_result = MEM_mallocN(sizeof(*faces_result) * (faces_result_len + 1), __func__); @@ -1109,9 +1117,10 @@ static BMEdge *bm_face_region_pivot_edge_find( if (bm_edge_is_region_boundary(e)) { unsigned int j; for (j = 0; j < 2; j++) { - if (!BLI_ghash_haskey(gh, (&e->v1)[j])) { + void **val_p; + if (!BLI_ghash_ensure_p(gh, (&e->v1)[j], &val_p)) { SUID_Int v_id = bm_face_region_vert_boundary_id((&e->v1)[j]); - BLI_ghash_insert(gh, (&e->v1)[j], (void *)v_id); + *val_p = (void *)v_id; BLI_LINKSTACK_PUSH(vert_queue_prev, (&e->v1)[j]); vert_queue_used += 1; } @@ -1135,10 +1144,11 @@ static BMEdge *bm_face_region_pivot_edge_find( 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)) { + void **val_p; + if (!BLI_ghash_ensure_p(gh, v_other, &val_p)) { /* 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); + *val_p = (void *)v_id_other; BLI_LINKSTACK_PUSH(vert_queue_next, v_other); vert_queue_used += 1; } @@ -1449,7 +1459,7 @@ int BM_mesh_region_match( BMFace **faces_result; unsigned int faces_result_len_out; - if (BM_elem_flag_test(e_dst, BM_ELEM_TAG)) { + if (BM_elem_flag_test(e_dst, BM_ELEM_TAG) || BM_edge_is_wire(e_dst)) { continue; } diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c index 404776a0769..6f2aaf28179 100644 --- a/source/blender/bmesh/tools/bmesh_triangulate.c +++ b/source/blender/bmesh/tools/bmesh_triangulate.c @@ -34,7 +34,6 @@ #include "BLI_utildefines.h" #include "BLI_alloca.h" #include "BLI_memarena.h" -#include "BLI_listbase.h" #include "BLI_heap.h" #include "BLI_edgehash.h" diff --git a/source/blender/bmesh/tools/bmesh_triangulate.h b/source/blender/bmesh/tools/bmesh_triangulate.h index 550109ffef9..c6a5e04dfb2 100644 --- a/source/blender/bmesh/tools/bmesh_triangulate.h +++ b/source/blender/bmesh/tools/bmesh_triangulate.h @@ -30,7 +30,8 @@ #ifndef __BMESH_TRIANGULATE_H__ #define __BMESH_TRIANGULATE_H__ -void BM_mesh_triangulate(BMesh *bm, const int quad_method, const int ngon_method, const bool tag_only, - BMOperator *op, BMOpSlot *slot_facemap_out); +void BM_mesh_triangulate( + BMesh *bm, const int quad_method, const int ngon_method, const bool tag_only, + BMOperator *op, BMOpSlot *slot_facemap_out); #endif /* __BMESH_TRIANGULATE_H__ */ diff --git a/source/blender/bmesh/tools/bmesh_wireframe.c b/source/blender/bmesh/tools/bmesh_wireframe.c index 79fea3e5da1..e79ef52797b 100644 --- a/source/blender/bmesh/tools/bmesh_wireframe.c +++ b/source/blender/bmesh/tools/bmesh_wireframe.c @@ -55,8 +55,9 @@ static BMLoop *bm_edge_tag_faceloop(BMEdge *e) return NULL; } -static void bm_vert_boundary_tangent(BMVert *v, float r_no[3], float r_no_face[3], - BMVert **r_va_other, BMVert **r_vb_other) +static void bm_vert_boundary_tangent( + BMVert *v, float r_no[3], float r_no_face[3], + BMVert **r_va_other, BMVert **r_vb_other) { BMIter iter; BMEdge *e_iter; @@ -159,7 +160,7 @@ static bool bm_loop_is_radial_boundary(BMLoop *l_first) } /** - * \param def_nr -1 for no vertex groups. + * \param defgrp_index: Vertex group index, -1 for no vertex groups. * * \note All edge tags must be cleared. * \note Behavior matches MOD_solidify.c |