diff options
author | Howard Trickey <howard.trickey@gmail.com> | 2018-01-29 03:19:02 +0300 |
---|---|---|
committer | Howard Trickey <howard.trickey@gmail.com> | 2018-01-29 03:19:02 +0300 |
commit | 561d738eaa2f64044f5266a480d9bc822bd0296e (patch) | |
tree | 7e2565822625c7ab03b7660d76feca39417bb145 /source/blender/bmesh | |
parent | d099b1073baa77f1c8da656eabe932f6ec5b06d8 (diff) |
Fix T53459, inconsistent bevel on identical edges.
The old algorithm depended on vertex order.
The new one uses a global least squares solution on chains
and cycles of edges where loop slide induces a dependency.
See https://wiki.blender.org/index.php/Dev:Source/Modeling/Bevel
in the "Consistent Widths for Even Bevels" for derivation of
the new algorithm.
Diffstat (limited to 'source/blender/bmesh')
-rw-r--r-- | source/blender/bmesh/tools/bmesh_bevel.c | 554 |
1 files changed, 351 insertions, 203 deletions
diff --git a/source/blender/bmesh/tools/bmesh_bevel.c b/source/blender/bmesh/tools/bmesh_bevel.c index 18b2b4db2bf..35167835646 100644 --- a/source/blender/bmesh/tools/bmesh_bevel.c +++ b/source/blender/bmesh/tools/bmesh_bevel.c @@ -44,6 +44,8 @@ #include "BKE_customdata.h" #include "BKE_deform.h" +#include "eigen_capi.h" + #include "bmesh.h" #include "bmesh_bevel.h" /* own include */ @@ -58,6 +60,7 @@ #define BEVEL_SMALL_ANG DEG2RADF(10.0f) #define BEVEL_MAX_ADJUST_PCT 10.0f #define BEVEL_MAX_AUTO_ADJUST_PCT 300.0f +#define BEVEL_MATCH_SPEC_WEIGHT 0.2 /* happens far too often, uncomment for development */ // #define BEVEL_ASSERT_PROJECT @@ -139,10 +142,14 @@ typedef struct BoundVert { NewVert nv; EdgeHalf *efirst; /* first of edges attached here: in CCW order */ EdgeHalf *elast; + EdgeHalf *eon; /* the "edge between" that this is on, in offset_on_edge_between case */ EdgeHalf *ebev; /* beveled edge whose left side is attached here, if any */ int index; /* used for vmesh indexing */ + float sinratio; /* when eon set, ratio of sines of angles to eon edge */ + struct BoundVert *adjchain; /* adjustment chain or cycle link pointer */ Profile profile; /* edge profile between this and next BoundVert */ bool any_seam; /* are any of the edges attached here seams? */ + bool visited; /* used during delta adjust pass */ // int _pad; } BoundVert; @@ -192,6 +199,7 @@ typedef struct BevelParams { bool use_weights; /* bevel amount affected by weights on edges or verts */ bool loop_slide; /* should bevel prefer to slide along edges rather than keep widths spec? */ bool limit_offset; /* should offsets be limited by collisions? */ + bool offset_adjust; /* should offsets be adjusted to try to get even widths? */ 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 */ @@ -207,6 +215,7 @@ static int bev_debug_flags = 0; #define DEBUG_OLD_PROJ_TO_PERP_PLANE (bev_debug_flags & 2) #define DEBUG_OLD_FLAT_MID (bev_debug_flags & 4) + /* this flag values will get set on geom we want to return in 'out' slots for edges and verts */ #define EDGE_OUT 4 #define VERT_OUT 8 @@ -260,6 +269,9 @@ static BoundVert *add_new_bound_vert(MemArena *mem_arena, VMesh *vm, const float vm->boundstart->prev = ans; } ans->profile.super_r = PRO_LINE_R; + ans->adjchain = NULL; + ans->sinratio = 1.0f; + ans->visited = false; vm->count++; return ans; } @@ -342,52 +354,6 @@ static EdgeHalf *find_other_end_edge_half(BevelParams *bp, EdgeHalf *e, BevVert return NULL; } -static bool other_edge_half_visited(BevelParams *bp, EdgeHalf *e) -{ - BevVert *bvo; - - bvo = find_bevvert(bp, e->is_rev ? e->e->v1 : e->e->v2); - if (bvo) - return bvo->visited; - else - return false; -} - -static bool edge_half_offset_changed(EdgeHalf *e) -{ - return e->offset_l != e->offset_l_spec || - e->offset_r != e->offset_r_spec; -} - -static float adjusted_rel_change(float val, float spec) -{ - float relchg; - - relchg = 0.0f; - if (val != spec) { - if (spec == 0) - relchg = 1000.0f; /* arbitrary large value */ - else - relchg = fabsf((val - spec) / spec); - } - return relchg; -} - -static float max_edge_half_offset_rel_change(BevVert *bv) -{ - int i; - float max_rel_change; - EdgeHalf *e; - - max_rel_change = 0.0f; - for (i = 0; i < bv->edgecount; i++) { - e = &bv->edges[i]; - max_rel_change = max_ff(max_rel_change, adjusted_rel_change(e->offset_l, e->offset_l_spec)); - max_rel_change = max_ff(max_rel_change, adjusted_rel_change(e->offset_r, e->offset_r_spec)); - } - return max_rel_change; -} - /* Return the next EdgeHalf after from_e that is beveled. * If from_e is NULL, find the first beveled edge. */ static EdgeHalf *next_bev(BevVert *bv, EdgeHalf *from_e) @@ -818,10 +784,6 @@ static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, bool e copy_v3_v3(off1a, v->co); d = max_ff(e1->offset_r, e2->offset_l); madd_v3_v3fl(off1a, norm_perp1, d); - if (e1->offset_r != d) - e1->offset_r = d; - else if (e2->offset_l != d) - e2->offset_l = d; copy_v3_v3(meetco, off1a); } else if (fabsf(ang - (float)M_PI) < BEVEL_EPSILON_ANG) { @@ -830,10 +792,6 @@ static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, bool e * common line, at offset distance from v. */ d = max_ff(e1->offset_r, e2->offset_l); slide_dist(e2, v, d, meetco); - if (e1->offset_r != d) - e1->offset_r = d; - else if (e2->offset_l != d) - e2->offset_l = d; } else { /* Get normal to plane where meet point should be, @@ -871,7 +829,6 @@ static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, bool e 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_v1); cross_v3_v3v3(norm_perp2, dir2, norm_v2); @@ -891,9 +848,6 @@ static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, bool e if (isect_kind == 0) { /* lines are collinear: 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) - e2->offset_l = d; } else { /* The lines intersect, but is it at a reasonable place? @@ -903,11 +857,9 @@ static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, bool e * or if the offset amount is > the edge length*/ if (e1->offset_r == 0.0f && is_outside_edge(e1, meetco, &closer_v)) { copy_v3_v3(meetco, closer_v->co); - e2->offset_l = len_v3v3(meetco, v->co); } if (e2->offset_l == 0.0f && is_outside_edge(e2, meetco, &closer_v)) { copy_v3_v3(meetco, closer_v->co); - e1->offset_r = len_v3v3(meetco, v->co); } if (edges_between && e1->offset_r > 0.0f && e2->offset_l > 0.0f) { /* Try to drop meetco to a face between e1 and e2 */ @@ -926,8 +878,6 @@ static void offset_meet(EdgeHalf *e1, EdgeHalf *e2, BMVert *v, BMFace *f, bool e 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); } } } @@ -994,40 +944,27 @@ static bool good_offset_on_edge_between(EdgeHalf *e1, EdgeHalf *e2, EdgeHalf *em /* 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. - * The offsets probably do not meet at a common point on emid, so need to pick - * one that causes the least problems. If the other end of one of e1 or e2 has been visited - * 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]) + * Return true if we placed meetco as compromise between where two edges met. + * If we did, put ration of sines of angles in *r_sinratio too */ +static bool offset_on_edge_between( + EdgeHalf *e1, EdgeHalf *e2, EdgeHalf *emid, + BMVert *v, float meetco[3], float *r_sinratio) { - float d, ang1, ang2, sina1, sina2, lambda; + float ang1, ang2; float meet1[3], meet2[3]; - bool visited1, visited2, ok1, ok2; + bool ok1, ok2; + bool retval = false; BLI_assert(e1->is_bev && e2->is_bev && !emid->is_bev); - visited1 = other_edge_half_visited(bp, e1); - visited2 = other_edge_half_visited(bp, e2); - ok1 = offset_meet_edge(e1, emid, v, meet1, &ang1); ok2 = offset_meet_edge(emid, e2, v, meet2, &ang2); if (ok1 && ok2) { - if (visited1 && !visited2) { - copy_v3_v3(meetco, meet1); - } - else if (!visited1 && visited2) { - copy_v3_v3(meetco, meet2); - } - else { - /* find best compromise meet point */ - sina1 = sinf(ang1); - sina2 = sinf(ang2); - lambda = sina2 * sina2 / (sina1 * sina1 + sina2 * sina2); - interp_v3_v3v3(meetco, meet1, meet2, lambda); - } + mid_v3_v3v3(meetco, meet1, meet2); + if (r_sinratio) + /* ang1 should not be 0, but be paranoid */ + *r_sinratio = (ang1 == 0.0f) ? 1.0f : sinf(ang2) / sinf(ang1); + retval = true; } else if (ok1 && !ok2) { copy_v3_v3(meetco, meet1); @@ -1041,13 +978,7 @@ static void offset_on_edge_between( slide_dist(emid, v, e1->offset_r, meetco); } - /* offsets may have changed now */ - d = dist_to_line_v3(meetco, v->co, BM_edge_other_vert(e1->e, v)->co); - if (fabsf(d - e1->offset_r) > BEVEL_EPSILON) - e1->offset_r = d; - d = dist_to_line_v3(meetco, v->co, BM_edge_other_vert(e2->e, v)->co); - if (fabsf(d - e2->offset_l) > BEVEL_EPSILON) - e2->offset_l = d; + return retval; } /* Offset by e->offset in plane with normal plane_no, on left if left==true, @@ -1806,6 +1737,7 @@ static void build_boundary_terminal_edge(BevelParams *bp, BevVert *bv, EdgeHalf } } +#if 0 /* Return a value that is v if v is within BEVEL_MAX_ADJUST_PCT of the spec (assumed positive), * else clamp to make it at most that far away from spec */ static float clamp_adjust(float v, float spec) @@ -1819,6 +1751,7 @@ static float clamp_adjust(float v, float spec) else return v; } +#endif /* 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. @@ -1835,11 +1768,10 @@ static float clamp_adjust(float v, float spec) static void build_boundary(BevelParams *bp, BevVert *bv, bool construct) { MemArena *mem_arena = bp->mem_arena; - EdgeHalf *efirst, *e, *e2, *e3, *enip, *eip, *eother; + EdgeHalf *efirst, *e, *e2, *e3, *enip, *eip, *eon; BoundVert *v; - BevVert *bvother; VMesh *vm; - float co[3]; + float co[3], r; int nip, nnip; /* Current bevel does nothing if only one edge into a vertex */ @@ -1853,30 +1785,9 @@ static void build_boundary(BevelParams *bp, BevVert *bv, bool construct) vm = bv->vmesh; - /* Find a beveled edge to be efirst. Then for each edge, try matching widths to other end. */ + /* Find a beveled edge to be efirst */ 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 */ - /* sometimes, adjustment can accumulate errors so use the bp->limit_offset to - * let user limit the adjustment to within a reasonable range around spec */ - if (bp->limit_offset) { - e->offset_l = clamp_adjust(eother->offset_r, e->offset_l_spec); - e->offset_r = clamp_adjust(eother->offset_l, e->offset_r_spec); - } - else { - 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 */ @@ -1890,6 +1801,7 @@ static void build_boundary(BevelParams *bp, BevVert *bv, bool construct) e = efirst; do { BLI_assert(e->is_bev); + eon = NULL; /* 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. @@ -1913,7 +1825,8 @@ static void build_boundary(BevelParams *bp, BevVert *bv, bool construct) } else if (nnip > 0) { if (bp->loop_slide && nnip == 1 && good_offset_on_edge_between(e, e2, enip, bv->v)) { - offset_on_edge_between(bp, e, e2, enip, bv->v, co); + if (offset_on_edge_between(e, e2, enip, bv->v, co, &r)) + eon = enip; } else { offset_meet(e, e2, bv->v, NULL, true, co); @@ -1922,7 +1835,8 @@ static void build_boundary(BevelParams *bp, BevVert *bv, bool construct) else { /* nip > 0 and nnip == 0 */ if (bp->loop_slide && nip == 1 && good_offset_on_edge_between(e, e2, eip, bv->v)) { - offset_on_edge_between(bp, e, e2, eip, bv->v, co); + if (offset_on_edge_between(e, e2, eip, bv->v, co, &r)) + eon = eip; } else { offset_meet(e, e2, bv->v, e->fnext, true, co); @@ -1933,6 +1847,9 @@ static void build_boundary(BevelParams *bp, BevVert *bv, bool construct) v->efirst = e; v->elast = e2; v->ebev = e2; + v->eon = eon; + if (eon) + v->sinratio = r; e->rightv = v; e2->leftv = v; for (e3 = e->next; e3 != e2; e3 = e3->next) { @@ -1962,98 +1879,328 @@ static void build_boundary(BevelParams *bp, BevVert *bv, bool construct) } } -/* Do a global pass to try to make offsets as even as possible. - * Consider this graph: - * nodes = BevVerts - * edges = { (u,v) } where u and v are nodes such that u and v - * are connected by a mesh edge that has at least one end - * whose offset does not match the user spec. - * - * Do a breadth-first search on this graph, starting from nodes - * that have any_adjust=true, and changing all - * not-already-changed offsets on EdgeHalfs to match the - * corresponding ones that changed on the other end. - * The graph is dynamic in the sense that having an offset that - * doesn't meet the user spec can be added as the search proceeds. - * We want this search to be deterministic (not dependent - * on order of processing through hash table), so as to avoid - * flicker to to different decisions made if search is different - * while dragging the offset number in the UI. So look for the - * lower vertex number when there is a choice of where to start. +#if 0 +static void print_adjust_stats(BoundVert *vstart) +{ + BoundVert *v; + EdgeHalf *eleft, *eright; + double even_residual2, spec_residual2; + double max_even_r, max_even_r_pct; + double max_spec_r, max_spec_r_pct; + double delta, delta_pct; + + printf("\nSolution analysis\n"); + even_residual2 = 0.0; + spec_residual2 = 0.0; + max_even_r = 0.0; + max_even_r_pct = 0.0; + max_spec_r = 0.0; + max_spec_r_pct = 0.0; + printf("width matching\n"); + v = vstart; + do { + if (v->adjchain != NULL) { + eright = v->efirst; + eleft = v->adjchain->elast; + delta = fabs(eright->offset_r - eleft->offset_l); + delta_pct = 100.0 * delta / eright->offset_r_spec; + printf("e%d r(%f) vs l(%f): abs(delta)=%f, delta_pct=%f\n", + BM_elem_index_get(eright->e), eright->offset_r, eleft->offset_l, delta, delta_pct); + even_residual2 += delta * delta; + if (delta > max_even_r) + max_even_r = delta; + if (delta_pct > max_even_r_pct) + max_even_r_pct = delta_pct; + } + v = v->adjchain; + } while (v && v != vstart); + + printf("spec matching\n"); + v = vstart; + do { + if (v->adjchain != NULL) { + eright = v->efirst; + eleft = v->adjchain->elast; + delta = fabs(eright->offset_r - eright->offset_r_spec); + delta_pct = 100.0 * delta / eright->offset_r_spec; + printf("e%d r(%f) vs r spec(%f): abs(delta)=%f, delta_pct=%f\n", + BM_elem_index_get(eright->e), eright->offset_r, eright->offset_r_spec, delta, delta_pct); + spec_residual2 += delta * delta; + if (delta > max_spec_r) + max_spec_r = delta; + if (delta_pct > max_spec_r_pct) + max_spec_r_pct = delta_pct; + + delta = fabs(eleft->offset_l - eleft->offset_l_spec); + delta_pct = 100.0 * delta / eright->offset_l_spec; + printf("e%d l(%f) vs l spec(%f): abs(delta)=%f, delta_pct=%f\n", + BM_elem_index_get(eright->e), eleft->offset_l, eleft->offset_l_spec, delta, delta_pct); + spec_residual2 += delta * delta; + if (delta > max_spec_r) + max_spec_r = delta; + if (delta_pct > max_spec_r_pct) + max_spec_r_pct = delta_pct; + } + v = v->adjchain; + } while (v && v != vstart); + + printf("Analysis Result:\n"); + printf("even residual2 = %f, spec residual2 = %f\n", even_residual2, spec_residual2); + printf("max even delta = %f, max as percent of spec = %f\n", max_even_r, max_even_r_pct); + printf("max spec delta = %f, max as percent of spec = %f\n", max_spec_r, max_spec_r_pct); +} +#endif + +static bool adjust_the_cycle_or_chain_fast(BoundVert *vstart, int np, bool iscycle) +{ + BoundVert *v; + EdgeHalf *eleft, *eright; + float *g; + float *g_prod; + float gprod, gprod_sum, spec_sum, p; + int i; + + g = MEM_mallocN(np * sizeof(float), "beveladjust"); + g_prod = MEM_mallocN(np * sizeof(float), "beveladjust"); + + v = vstart; + spec_sum = 0.0f; + i = 0; + do { + g[i] = v->sinratio; + if (iscycle || v->adjchain != NULL) { + spec_sum += v->efirst->offset_r; + } + else { + spec_sum += v->elast->offset_l; + } + i++; + v = v->adjchain; + } while (v && v != vstart); + + gprod = 1.00f; + gprod_sum = 1.0f; + for (i = np - 1; i > 0; i--) { + gprod *= g[i]; + g_prod[i] = gprod; + gprod_sum += gprod; + } + if (iscycle) { + gprod *= g[0]; + if (fabs(gprod - 1.0f) > BEVEL_EPSILON) { + /* fast cycle calc only works if total product is 1 */ + MEM_freeN(g); + MEM_freeN(g_prod); + return false; + } + else + g_prod[0] = 1.0f; + } + if (gprod_sum == 0.0f) { + MEM_freeN(g); + MEM_freeN(g_prod); + return false; + } + p = spec_sum / gprod_sum; + + /* apply the new offsets */ + v = vstart; + i = 0; + do { + if (iscycle || v->adjchain != NULL) { + eright = v->efirst; + eleft = v->elast; + eright->offset_r = g_prod[(i + 1) % np] * p; + if (iscycle || v != vstart) { + eleft->offset_l = v->sinratio * eright->offset_r; + } + } + else { + /* not a cycle, and last of chain */ + eleft = v->elast; + eleft->offset_l = p; + } + i++; + v = v->adjchain; + } while (v && v != vstart); + + MEM_freeN(g); + MEM_freeN(g_prod); + return true; +} + +/* Adjust the offsets for a single cycle or chain. + * For chains and some cycles, a fast solution exists. + * Otherwise, we set up and solve a linear least squares problem + * that tries to minimize the squared differences of lengths + * at each end of an edge, and (with smaller weight) the + * squared differences of the offsets from their specs. + */ +static void adjust_the_cycle_or_chain(BoundVert *vstart, bool iscycle) +{ + BoundVert *v; + EdgeHalf *eleft, *eright; + LinearSolver *solver; + double weight, val; + int i, np, nrows, row; + + np = 0; + v = vstart; + do { + np++; + v = v->adjchain; + } while (v && v != vstart); + + if (adjust_the_cycle_or_chain_fast(vstart, np, iscycle)) + return; + + nrows = iscycle ? 2 * np : 2 * np - 1; + + solver = EIG_linear_least_squares_solver_new(nrows, np, 1); + + v = vstart; + i = 0; + weight = BEVEL_MATCH_SPEC_WEIGHT; /* sqrt of factor to weight down importance of spec match */ + do { + /* except at end of chain, v's indep variable is offset_r of v->efirst */ + if (iscycle || v->adjchain != NULL) { + eright = v->efirst; + eleft = v->elast; + + /* residue i: width difference between eright and eleft of next */ + EIG_linear_solver_matrix_add(solver, i, i, 1.0); + EIG_linear_solver_right_hand_side_add(solver, 0, i, 0.0); + if (iscycle) { + EIG_linear_solver_matrix_add(solver, i > 0 ? i - 1 : np - 1, i, -v->sinratio); + } + else { + if (i > 0) + EIG_linear_solver_matrix_add(solver, i - 1, i, -v->sinratio); + } + + /* residue np + i (if cycle) else np - 1 + i: + * right offset for parm i matches its spec; weighted */ + row = iscycle ? np + i : np - 1 + i; + EIG_linear_solver_matrix_add(solver, row, i, weight); + EIG_linear_solver_right_hand_side_add(solver, 0, row, weight * eright->offset_r); + } + else { + /* not a cycle, and last of chain */ + eleft = v->elast; + /* second part of residue i for last i */ + EIG_linear_solver_matrix_add(solver, i - 1, i, -1.0); + /* residue 2 * np -2 : last spec match residue is for left offset of final parm */ + row = 2 * np - 2; + EIG_linear_solver_matrix_add(solver, row, i, weight); + EIG_linear_solver_right_hand_side_add(solver, 0, row, weight * eleft->offset_l); + } + i++; + v = v->adjchain; + } while (v && v != vstart); + EIG_linear_solver_solve(solver); + + /* Use the solution to set new widths */ + v = vstart; + i = 0; + do { + val = EIG_linear_solver_variable_get(solver, 0, i); + if (iscycle || v->adjchain != NULL) { + eright = v->efirst; + eleft = v->elast; + eright->offset_r = (float)val; + if (iscycle || v != vstart) { + eleft->offset_l = (float)(v->sinratio * val); + } + } + else { + /* not a cycle, and last of chain */ + eleft = v->elast; + eleft->offset_l = (float)val; + } + i++; + v = v->adjchain; + } while (v && v != vstart); + + EIG_linear_solver_delete(solver); +} + +/* Adjust the offsets to try to make them, as much as possible, + * have even-width bevels with offsets that match their specs. + * The problem that we can try to amelieroate is that when loop slide + * is active, the meet point will probably not be the one that makes + * both sides have their specified width. And because both ends may be + * on loop slide edges, the widths at each end could be different. * - * Note that this might not process all BevVerts, only the ones - * that need adjustment. + * It turns out that the dependent offsets either form chains or + * cycles, and we can process each of those separatey. */ static void adjust_offsets(BevelParams *bp) { - BevVert *bv, *searchbv, *bvother; - int i, searchi; + BevVert *bv, *bvcur; + BoundVert *v, *vanchor, *vchainstart, *vnext; + EdgeHalf *enext; GHashIterator giter; - EdgeHalf *e, *efirst, *eother; - GSQueue *q; - float max_rel_adj; + bool iscycle; - BLI_assert(!bp->vertex_only); + /* find and process chains and cycles of unvisited BoundVerts that have eon set */ GHASH_ITER(giter, bp->vert_hash) { - bv = BLI_ghashIterator_getValue(&giter); - bv->visited = false; - } + bv = bvcur = BLI_ghashIterator_getValue(&giter); + vanchor = bv->vmesh->boundstart; + do { + if (vanchor->visited || !vanchor->eon) + continue; - q = BLI_gsqueue_new(sizeof(BevVert *)); - /* the following loop terminates because at least one node is visited each time */ - for (;;) { - /* look for root of a connected component in search graph */ - searchbv = NULL; - searchi = -1; - GHASH_ITER(giter, bp->vert_hash) { - bv = BLI_ghashIterator_getValue(&giter); - if (!bv->visited && max_edge_half_offset_rel_change(bv) > 0.0f) { - i = BM_elem_index_get(bv->v); - if (!searchbv || i < searchi) { - searchbv = bv; - searchi = i; + /* Find one of (1) a cycle that starts and ends at v + * where each v has v->eon set and had not been visited before; + * or (2) a chain of v's where the start and end of the chain do not have + * v->eon set but all else do. + * It is OK for the first and last elements to + * have been visited before, but not any of the inner ones. + * We chain the v's together through v->adjchain, and are following + * them in left->right direction, meaning that the left side of one edge + * pairs with the right side of the next edge in the cycle or chain. */ + + /* first follow paired edges in left->right direction */ + v = vchainstart = vanchor; + iscycle = false; + while(v->eon && !v->visited && !iscycle) { + enext = find_other_end_edge_half(bp, v->efirst, &bvcur); + BLI_assert(enext != NULL); + vnext = enext->leftv; + v->adjchain = vnext; + v->visited = true; + if (vnext->visited) { + if (vnext != vchainstart) { + printf("WHOOPS, adjusting offsets, expected cycle!\n"); + break; + } + adjust_the_cycle_or_chain(vchainstart, true); + iscycle = true; } + v = vnext; } - } - if (searchbv == NULL) - break; - - BLI_gsqueue_push(q, &searchbv); - while (!BLI_gsqueue_is_empty(q)) { - BLI_gsqueue_pop(q, &bv); - /* If do this check, don't have to check for already-on-queue before push, below */ - if (bv->visited) - continue; - bv->visited = true; - build_boundary(bp, bv, false); - - e = efirst = &bv->edges[0]; - do { - eother = find_other_end_edge_half(bp, e, &bvother); - if (eother && !bvother->visited && edge_half_offset_changed(e)) { - BLI_gsqueue_push(q, &bvother); - } - } while ((e = e->next) != efirst); - } + if (!iscycle) { + /* right->left direction, changing vchainstart at each step */ + v = vchainstart; + bvcur = bv; + do { + enext = find_other_end_edge_half(bp, v->elast, &bvcur); + BLI_assert(enext != NULL); + vnext = enext->rightv; + vnext->adjchain = v; + vchainstart = vnext; + v->visited = true; + v = vnext; + } while(!v->visited && v->eon); + adjust_the_cycle_or_chain(vchainstart, false); + } + } while ((vanchor = vanchor->next) != bv->vmesh->boundstart); } - BLI_gsqueue_free(q); - /* Should we auto-limit the error accumulation? Typically, spirals can lead to 100x relative adjustments, - * and somewhat hacky mechanism of using bp->limit_offset to indicate "clamp the adjustments" is not - * obvious to users, who almost certainly want clamping in this situation. - * The reason not to clamp always is that some models work better without it (e.g., Bent_test in regression - * suite, where relative adjust maximum is about .6). */ - if (!bp->limit_offset) { - max_rel_adj = 0.0f; - GHASH_ITER(giter, bp->vert_hash) { - bv = BLI_ghashIterator_getValue(&giter); - max_rel_adj = max_ff(max_rel_adj, max_edge_half_offset_rel_change(bv)); - } - if (max_rel_adj > BEVEL_MAX_AUTO_ADJUST_PCT / 100.0f) { - bp->limit_offset = true; - adjust_offsets(bp); - bp->limit_offset = false; - } + /* Rebuild boundaries with new width specs */ + GHASH_ITER(giter, bp->vert_hash) { + bv = BLI_ghashIterator_getValue(&giter); + build_boundary(bp, bv, false); } } @@ -4983,6 +5130,7 @@ void BM_mesh_bevel( bp.use_weights = use_weights; bp.loop_slide = loop_slide; bp.limit_offset = limit_offset; + bp.offset_adjust = true; bp.dvert = dvert; bp.vertex_group = vertex_group; bp.mat_nr = mat; @@ -5019,7 +5167,7 @@ void BM_mesh_bevel( } /* Perhaps do a pass to try to even out widths */ - if (!bp.vertex_only) { + if (!bp.vertex_only && bp.offset_adjust) { adjust_offsets(&bp); } |