diff options
author | Howard Trickey <howard.trickey@gmail.com> | 2020-06-26 13:42:20 +0300 |
---|---|---|
committer | Howard Trickey <howard.trickey@gmail.com> | 2020-06-26 13:43:01 +0300 |
commit | e3a420c4773a1d1a79c21f15137066d4411d3574 (patch) | |
tree | 05253ace680efd72f7328ffc171d735cd7fc07dd | |
parent | c7694185c92aa44c90fa43e58e88742e085183d9 (diff) |
Fix T76199 Bevel materials "bleed" over faces.
When there is an odd number of segments, bevel has an ambiguous
choice as to which side face to use to copy face attributes from
and to use for UV (and other loops that have math function) interpolation.
We used to make choice arbitrarily, which led to visually inconsistent
results. Now there is tie-breaking code, face with lexicographic lowest
value in vector with these elements:
(1) connected component (in math-layer space) id
(2) selected (0) vs unselected (1)
(3) material index
(4,5,6): z,x,y components of face center, in that order.
-rw-r--r-- | source/blender/bmesh/tools/bmesh_bevel.c | 417 |
1 files changed, 341 insertions, 76 deletions
diff --git a/source/blender/bmesh/tools/bmesh_bevel.c b/source/blender/bmesh/tools/bmesh_bevel.c index 10f93a8f095..e971e465eca 100644 --- a/source/blender/bmesh/tools/bmesh_bevel.c +++ b/source/blender/bmesh/tools/bmesh_bevel.c @@ -175,6 +175,26 @@ typedef struct ProfileSpacing { } ProfileSpacing; /** + * If the mesh has custom data Loop layers that 'have math' we use this + * data to help decide which face to use as representative when there + * is an ambiguous choice as to which face to use, which happens + * when there is an odd number of segments. + * + * The face_compent field of the following will only be set if there are an odd + * number of segments. The it uses BMFace indices to index into it, so will + * only be valid as long BMFaces are not added or deleted in the BMesh. + * "Connected Component" here means connected in UV space: + * i.e., one face is directly connected to another if they share an edge and + * all of Loop UV custom layers are contiguous across that edge. + */ +typedef struct MathLayerInfo { + /** A connected-component id for each BMFace in the mesh. */ + int *face_component; + /** Does the mesh have any custom loop uv layers? */ + bool has_math_layers; +} MathLayerInfo; + +/** * An element in a cyclic boundary of a Vertex Mesh (VMesh), placed on each side of beveled edges * where each profile starts, or on each side of a miter. */ @@ -297,6 +317,8 @@ typedef struct BevelParams { ProfileSpacing pro_spacing; /** Parameter values for evenly spaced profile points for the miter profiles. */ ProfileSpacing pro_spacing_miter; + /** Information about 'math' loop layers, like UV layers. */ + MathLayerInfo math_layer_info; /** Blender units to offset each side of a beveled edge. */ float offset; /** How offset is measured; enum defined in bmesh_operators.h. */ @@ -733,12 +755,13 @@ static BMFace *bev_create_quad_ex(BMesh *bm, BMEdge *e2, BMEdge *e3, BMEdge *e4, + BMFace *frep, int mat_nr) { BMVert *varr[4] = {v1, v2, v3, v4}; BMFace *farr[4] = {f1, f2, f3, f4}; BMEdge *earr[4] = {e1, e2, e3, e4}; - return bev_create_ngon(bm, varr, 4, farr, f1, earr, mat_nr, true); + return bev_create_ngon(bm, varr, 4, farr, frep, earr, mat_nr, true); } /* Is Loop layer layer_index contiguous across shared vertex of l1 and l2? */ @@ -752,7 +775,8 @@ static bool contig_ldata_across_loops(BMesh *bm, BMLoop *l1, BMLoop *l2, int lay } /* Are all loop layers with have math (e.g., UVs) - * contiguous from face f1 to face f2 across edge e? */ + * contiguous from face f1 to face f2 across edge e? + */ static bool contig_ldata_across_edge(BMesh *bm, BMEdge *e, BMFace *f1, BMFace *f2) { BMLoop *lef1, *lef2; @@ -764,41 +788,202 @@ static bool contig_ldata_across_edge(BMesh *bm, BMEdge *e, BMFace *f1, BMFace *f return true; } - v1 = e->v1; - v2 = e->v2; if (!BM_edge_loop_pair(e, &lef1, &lef2)) { return false; } + /* If faces are oriented consistently around e, + * should now have lef1 and lef2 being f1 and f2 in either order. + */ if (lef1->f == f2) { SWAP(BMLoop *, lef1, lef2); } - - if (lef1->v == v1) { - lv1f1 = lef1; - lv2f1 = BM_face_other_edge_loop(f1, e, v2); + if (lef1->f != f1 || lef2 != lef2) { + return false; } - else { - lv2f1 = lef1; - lv1f1 = BM_face_other_edge_loop(f1, e, v1); + v1 = lef1->v; + v2 = lef2->v; + BLI_assert((v1 == e->v1 && v2 == e->v2) || (v1 == e->v2 && v2 == e->v1)); + lv1f1 = lef1; + lv2f1 = lef1->next; + lv1f2 = lef2->next; + lv2f2 = lef2; + BLI_assert(lv1f1->v == v1 && lv1f1->f == f1 && lv2f1->v == v2 && lv2f1->f == f1 && + lv1f2->v == v1 && lv1f2->f == f2 && lv2f2->v == v2 && lv2f2->f == f2); + for (i = 0; i < bm->ldata.totlayer; i++) { + if (CustomData_layer_has_math(&bm->ldata, i)) { + if (!contig_ldata_across_loops(bm, lv1f1, lv1f2, i) || + !contig_ldata_across_loops(bm, lv2f1, lv2f2, i)) { + return false; + } + } } + return true; +} + +/* + * Set up the fields of bp->math_layer_info. + * We always set has_math_layers to the correct value. + * Only if there are UV layers and the number of segments is odd, + * we need to calculate connected face components in UV space. + */ +static void math_layer_info_init(BevelParams *bp, BMesh *bm) +{ + int i, f, stack_top, totface, current_component; + int bmf_index, bmf_other_index; + int *face_component; + BMFace *bmf, *bmf_other; + BMEdge *bme; + BMFace **stack; + BMIter eiter, fiter; - if (lef2->v == v1) { - lv1f2 = lef2; - lv2f2 = BM_face_other_edge_loop(f2, e, v2); + bp->math_layer_info.has_math_layers = false; + bp->math_layer_info.face_component = NULL; + for (i = 0; i < bm->ldata.totlayer; i++) { + if (CustomData_has_layer(&bm->ldata, CD_MLOOPUV)) { + bp->math_layer_info.has_math_layers = true; + break; + } } - else { - lv2f2 = lef2; - lv1f2 = BM_face_other_edge_loop(f2, e, v1); + if (!bp->math_layer_info.has_math_layers || (bp->seg % 2) == 0) { + return; } - for (i = 0; i < bm->ldata.totlayer; i++) { - if (CustomData_layer_has_math(&bm->ldata, i) && - (!contig_ldata_across_loops(bm, lv1f1, lv1f2, i) || - !contig_ldata_across_loops(bm, lv2f1, lv2f2, i))) { - return false; + BM_mesh_elem_index_ensure(bm, BM_FACE); + BM_mesh_elem_table_ensure(bm, BM_FACE); + totface = bm->totface; + face_component = BLI_memarena_alloc(bp->mem_arena, totface * sizeof(int)); + bp->math_layer_info.face_component = face_component; + + /* Set all component ids by DFS from faces with unassigned components. */ + for (f = 0; f < totface; f++) { + face_component[f] = -1; + } + current_component = -1; + + /* Use an array as a stack. Stack size can't exceed double total faces. */ + stack = MEM_malloc_arrayN(2 * totface, sizeof(BMFace *), __func__); + for (f = 0; f < totface; f++) { + if (face_component[f] == -1) { + stack_top = 0; + current_component++; + BLI_assert(stack_top < 2 * totface); + stack[stack_top] = BM_face_at_index(bm, f); + while (stack_top >= 0) { + bmf = stack[stack_top]; + stack_top--; + bmf_index = BM_elem_index_get(bmf); + if (face_component[bmf_index] != -1) { + continue; + } + face_component[bmf_index] = current_component; + /* Neighbors are faces that share an edge with bmf and + * are where contig_ldata_across_edge(...) is true for the + * shared edge and two faces. + */ + BM_ITER_ELEM (bme, &eiter, bmf, BM_EDGES_OF_FACE) { + BM_ITER_ELEM (bmf_other, &fiter, bme, BM_FACES_OF_EDGE) { + if (bmf_other != bmf) { + bmf_other_index = BM_elem_index_get(bmf_other); + if (face_component[bmf_other_index] != -1) { + continue; + } + if (contig_ldata_across_edge(bm, bme, bmf, bmf_other)) { + stack_top++; + BLI_assert(stack_top < 2 * totface); + stack[stack_top] = bmf_other; + } + } + } + } + } } } - return true; + MEM_freeN(stack); +} + +/* Use a tie-breaking rule to choose a representative face when + * there are number of choices, face[0], face[1], ..., face[nfaces]. + * This is needed when there are an odd number of segments, and the center + * segmment (and its continuation into vmesh) can usually arbitrarily be + * the previous face or the next face. + * Or, for the center polygon of a corner, all of the faces around + * the vertex are possible choices. + * If we just choose randomly, the resulting UV maps or material + * assignment can look ugly/inconsistent. + * Allow for the case when args are null. + */ +static BMFace *choose_rep_face(BevelParams *bp, BMFace **face, int nfaces) +{ + int f, bmf_index, value_index, best_f, i; + BMFace *bmf; + float cent[3]; +#define VEC_VALUE_LEN 6 + float(*value_vecs)[VEC_VALUE_LEN] = NULL; + bool *still_viable = NULL; + int num_viable = 0; + + value_vecs = BLI_array_alloca(value_vecs, nfaces); + still_viable = BLI_array_alloca(still_viable, nfaces); + for (int f = 0; f < nfaces; f++) { + bmf = face[f]; + if (bmf == NULL) { + still_viable[f] = false; + continue; + } + still_viable[f] = true; + num_viable++; + bmf_index = BM_elem_index_get(bmf); + value_index = 0; + /* First tie-breaker: lower math-layer connected component id. */ + value_vecs[f][value_index++] = bp->math_layer_info.face_component ? + (float)bp->math_layer_info.face_component[bmf_index] : + 0.0f; + /* Next tie-breaker: selected face beats unselected one. */ + value_vecs[f][value_index++] = BM_elem_flag_test(bmf, BM_ELEM_SELECT) ? 0.0f : 1.0f; + /* Next tie-breaker: lower material index. */ + value_vecs[f][value_index++] = bmf->mat_nr >= 0 ? (float)bmf->mat_nr : 0.0f; + /* Next three tie-breakers: z, x, y components of face center. */ + BM_face_calc_center_bounds(bmf, cent); + value_vecs[f][value_index++] = cent[2]; + value_vecs[f][value_index++] = cent[0]; + value_vecs[f][value_index++] = cent[1]; + BLI_assert(value_index == VEC_VALUE_LEN); + } + + /* Look for a face that has a unique minimum value for in a value_index, + * trying each value_index in turn until find a unique minimum. + */ + best_f = -1; + for (value_index = 0; num_viable > 1 && value_index < VEC_VALUE_LEN; value_index++) { + for (f = 0; f < nfaces; f++) { + if (!still_viable[f] || f == best_f) { + continue; + } + if (best_f == -1) { + best_f = f; + continue; + } + if (value_vecs[f][value_index] < value_vecs[best_f][value_index]) { + best_f = f; + /* Previous f's are now not viable any more. */ + for (i = f - 1; i >= 0; i--) { + if (still_viable[i]) { + still_viable[i] = false; + num_viable--; + } + } + } + else if (value_vecs[f][value_index] > value_vecs[best_f][value_index]) { + still_viable[f] = false; + num_viable--; + } + } + } + if (best_f == -1) { + best_f = 0; + } + return face[best_f]; +#undef VEC_VALUE_LEN } /* Merge (using average) all the UV values for loops of v's faces. @@ -4472,6 +4657,105 @@ static float snap_face_dist_squared(float *co, BMFace *f, BMEdge **r_snap_e, flo return beste_d2; } +/* What would be the area of the polygon around bv if interpolated in face frep? + */ +static float interp_poly_area(BevVert *bv, BMFace *frep) +{ + BoundVert *v; + VMesh *vm = bv->vmesh; + BMEdge *snape; + int n; + float(*uv_co)[3] = NULL; + float area; + + BLI_assert(vm != NULL); + uv_co = BLI_array_alloca(uv_co, vm->count); + v = vm->boundstart; + n = 0; + do { + BLI_assert(n < vm->count); + snap_face_dist_squared(v->nv.v->co, frep, &snape, uv_co[n]); + n++; + } while ((v = v->next) != vm->boundstart); + area = fabsf(area_poly_v3(uv_co, n)); + return area; +} + +/** + * If we make a poly out of verts around bv, snapping to rep frep, will uv poly have zero area? + * The uv poly is made by snapping all outside-of-frep vertices to the closest edge in frep. + * Sometimes this results in a zero or very small area polygon, which translates to a zero + * or very small area polygong in UV space -- not good for interpolating textures. + */ +static bool is_bad_uv_poly(BevVert *bv, BMFace *frep) +{ + float area = interp_poly_area(bv, frep); + return area < BEVEL_EPSILON_BIG; +} + +/* + * Pick a good face from all the faces around bv to use for + * a representative face, using choose_rep_face. + * We want to choose from among the faces that would be + * chosen for a single-segment edge polygon between two successive + * Boundverts. + * But the single beveled edge is a special case, + * where we also want to consider the third face (else can get + * zero-area UV interpolated face). + * + * If there are math-having custom loop layers, like UV, then + * don't include faces that would result in zero-area UV polygons + * if chosen as the rep. + */ +static BMFace *frep_for_center_poly(BevelParams *bp, BevVert *bv) +{ + int i, j, fcount; + BMFace **fchoices, *bmf, *bmf1, *bmf2, *any_bmf; + BMFace *ftwo[2]; + bool already_there; + bool consider_all_faces; + + fcount = 0; + any_bmf = NULL; + consider_all_faces = bv->selcount == 1; + /* Make an array that can hold maximum possible number of choices. */ + fchoices = BLI_array_alloca(fchoices, bv->edgecount); + for (i = 0; i < bv->edgecount; i++) { + if (!bv->edges[i].is_bev && !consider_all_faces) { + continue; + } + bmf1 = bv->edges[i].fprev; + bmf2 = bv->edges[i].fnext; + ftwo[0] = bmf1; + ftwo[1] = bmf2; + bmf = choose_rep_face(bp, ftwo, 2); + if (bmf != NULL) { + if (any_bmf == NULL) { + any_bmf = bmf; + } + already_there = false; + for (j = fcount - 1; j >= 0; j--) { + if (fchoices[j] == bmf) { + already_there = true; + break; + } + } + if (!already_there) { + if (bp->math_layer_info.has_math_layers) { + if (is_bad_uv_poly(bv, bmf)) { + continue; + } + } + fchoices[fcount++] = bmf; + } + } + } + if (fcount == 0) { + return any_bmf; + } + return choose_rep_face(bp, fchoices, fcount); +} + static void build_center_ngon(BevelParams *bp, BMesh *bm, BevVert *bv, int mat_nr) { VMesh *vm = bv->vmesh; @@ -4488,7 +4772,7 @@ static void build_center_ngon(BevelParams *bp, BMesh *bm, BevVert *bv, int mat_n ns2 = vm->seg / 2; if (bv->any_seam) { - frep = boundvert_rep_face(vm->boundstart, NULL); + frep = frep_for_center_poly(bp, bv); get_incident_edges(frep, bv->v, &frep_e1, &frep_e2); } else { @@ -4813,7 +5097,8 @@ static void bevel_build_rings(BevelParams *bp, BMesh *bm, BevVert *bv, BoundVert VMesh *vm1, *vm; BoundVert *bndv; BMVert *bmv1, *bmv2, *bmv3, *bmv4; - BMFace *f, *f2, *r_f; + BMFace *f, *f2, *r_f, *fc; + BMFace *fchoices[2]; BMEdge *bme, *bme1, *bme2, *bme3; EdgeHalf *e; int mat_nr = bp->mat_nr; @@ -4867,6 +5152,14 @@ static void bevel_build_rings(BevelParams *bp, BMesh *bm, BevVert *bv, BoundVert i = bndv->index; f = boundvert_rep_face(bndv, NULL); f2 = boundvert_rep_face(bndv->next, NULL); + fchoices[0] = f; + fchoices[1] = f2; + if (odd) { + fc = choose_rep_face(bp, fchoices, 2); + } + else { + fc = NULL; + } if (bp->vertex_only) { e = bndv->efirst; } @@ -4877,7 +5170,10 @@ static void bevel_build_rings(BevelParams *bp, BMesh *bm, BevVert *bv, BoundVert /* For odd ns, make polys with lower left corner at (i,j,k) for * j in [0, ns2-1], k in [0, ns2]. And then the center ngon. * For even ns, - * j in [0, ns2-1], k in [0, ns2-1]. */ + * j in [0, ns2-1], k in [0, ns2-1]. + * + * Recall: j is ring index, k is segment index. + */ for (j = 0; j < ns2; j++) { for (k = 0; k < ns2 + odd; k++) { bmv1 = mesh_vert(vm, i, j, k)->v; @@ -4901,6 +5197,7 @@ static void bevel_build_rings(BevelParams *bp, BMesh *bm, BevVert *bv, BoundVert NULL, bndv->next->efirst->e, bme, + f2, mat_nr); } else { @@ -4914,11 +5211,11 @@ static void bevel_build_rings(BevelParams *bp, BMesh *bm, BevVert *bv, BoundVert /* Only one edge attached to v, since vertex_only. */ if (e->is_seam) { r_f = bev_create_quad_ex( - bm, bmv1, bmv2, bmv3, bmv4, f2, f2, f2, f2, bme, NULL, bme, NULL, mat_nr); + bm, bmv1, bmv2, bmv3, bmv4, f2, f2, f2, f2, bme, NULL, bme, NULL, f2, mat_nr); } else { r_f = bev_create_quad_ex( - bm, bmv1, bmv2, bmv3, bmv4, f2, f2, f2, f, bme, NULL, bme, NULL, mat_nr); + bm, bmv1, bmv2, bmv3, bmv4, f2, f2, f2, f, bme, NULL, bme, NULL, f2, mat_nr); } } } @@ -4927,10 +5224,11 @@ static void bevel_build_rings(BevelParams *bp, BMesh *bm, BevVert *bv, BoundVert if (k == ns2) { if (e && e->is_seam) { r_f = bev_create_quad_ex( - bm, bmv1, bmv2, bmv3, bmv4, f, f, f, f, NULL, bme, bme, NULL, mat_nr); + bm, bmv1, bmv2, bmv3, bmv4, fc, fc, fc, fc, NULL, bme, bme, NULL, fc, mat_nr); } else { - r_f = bev_create_quad(bm, bmv1, bmv2, bmv3, bmv4, f, f2, f2, f, mat_nr); + r_f = bev_create_quad_ex( + bm, bmv1, bmv2, bmv3, bmv4, f, f2, f2, f, NULL, bme, bme, NULL, fc, mat_nr); } } else { @@ -4945,7 +5243,7 @@ static void bevel_build_rings(BevelParams *bp, BMesh *bm, BevVert *bv, BoundVert } bme2 = bme1 != NULL ? bme1 : bme3; r_f = bev_create_quad_ex( - bm, bmv1, bmv2, bmv3, bmv4, f, f, f, f, NULL, bme1, bme2, bme3, mat_nr); + bm, bmv1, bmv2, bmv3, bmv4, f, f, f, f, NULL, bme1, bme2, bme3, f, mat_nr); } } record_face_kind(bp, r_f, F_VERT); @@ -5143,43 +5441,9 @@ static void bevel_build_cutoff(BevelParams *bp, BMesh *bm, BevVert *bv) } } -/** - * If we make a poly out of verts around bv, snapping to rep frep, will uv poly have zero area? - * The uv poly is made by snapping all outside-of-frep vertices to the closest edge in frep. - * Assume that this function is called when the only inside-of-frep vertex is vm->boundstart. - * The poly will have zero area if the distance of that first vertex to some edge e is zero, - * and all the other vertices snap to e or snap to an edge - * at a point that is essentially on e too. - */ -static bool is_bad_uv_poly(BevVert *bv, BMFace *frep) -{ - BoundVert *v; - BMEdge *snape, *firste; - float co[3]; - VMesh *vm = bv->vmesh; - float d2; - - v = vm->boundstart; - d2 = snap_face_dist_squared(v->nv.v->co, frep, &firste, co); - if (d2 > BEVEL_EPSILON_BIG_SQ || firste == NULL) { - return false; - } - - for (v = v->next; v != vm->boundstart; v = v->next) { - snap_face_dist_squared(v->nv.v->co, frep, &snape, co); - if (snape != firste) { - d2 = dist_to_line_v3(co, firste->v1->co, firste->v2->co); - if (d2 > BEVEL_EPSILON_BIG_SQ) { - return false; - } - } - } - return true; -} - static BMFace *bevel_build_poly(BevelParams *bp, BMesh *bm, BevVert *bv) { - BMFace *f, *repface, *frep2; + BMFace *f, *repface; int n, k; VMesh *vm = bv->vmesh; BoundVert *bndv; @@ -5192,10 +5456,7 @@ static BMFace *bevel_build_poly(BevelParams *bp, BMesh *bm, BevVert *bv) BLI_array_staticdeclare(bmfaces, BM_DEFAULT_NGON_STACK_SIZE); if (bv->any_seam) { - repface = boundvert_rep_face(vm->boundstart, &frep2); - if (frep2 && repface && is_bad_uv_poly(bv, repface)) { - repface = frep2; - } + repface = frep_for_center_poly(bp, bv); get_incident_edges(repface, bv->v, &repface_e1, &repface_e2); } else { @@ -6413,7 +6674,7 @@ static void bevel_build_edge_polygons(BMesh *bm, BevelParams *bp, BMEdge *bme) VMesh *vm1, *vm2; EdgeHalf *e1, *e2; BMEdge *bme1, *bme2, *center_bme; - BMFace *f1, *f2, *f, *r_f; + BMFace *f1, *f2, *f, *r_f, *f_choice; BMVert *verts[4]; BMFace *faces[4]; BMEdge *edges[4]; @@ -6474,15 +6735,17 @@ static void bevel_build_edge_polygons(BMesh *bm, BevelParams *bp, BMEdge *bme) verts[3] = mesh_vert(vm1, i1, 0, k)->v; verts[2] = mesh_vert(vm2, i2, 0, nseg - k)->v; if (odd && k == mid + 1) { + BMFace *fchoices[2] = {f1, f2}; + edges[0] = edges[1] = NULL; + edges[2] = edges[3] = bme; + f_choice = choose_rep_face(bp, fchoices, 2); if (e1->is_seam) { - /* Straddles a seam: choose to interpolate in f1 and snap right edge to bme. */ - edges[0] = edges[1] = NULL; - edges[2] = edges[3] = bme; - r_f = bev_create_ngon(bm, verts, 4, NULL, f1, edges, mat_nr, true); + /* Straddles a seam: choose to interpolate in f_choice and snap right edge to bme. */ + r_f = bev_create_ngon(bm, verts, 4, NULL, f_choice, edges, mat_nr, true); } else { /* Straddles but not a seam: interpolate left half in f1, right half in f2. */ - r_f = bev_create_ngon(bm, verts, 4, faces, NULL, NULL, mat_nr, true); + r_f = bev_create_ngon(bm, verts, 4, faces, f_choice, NULL, mat_nr, true); } } else if (!odd && k == mid) { @@ -7264,6 +7527,8 @@ void BM_mesh_bevel(BMesh *bm, bp.face_hash = BLI_ghash_ptr_new(__func__); BLI_ghash_flag_set(bp.face_hash, GHASH_FLAG_ALLOW_DUPES); + math_layer_info_init(&bp, bm); + /* Analyze input vertices, sorting edges and assigning initial new vertex positions. */ BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { if (BM_elem_flag_test(v, BM_ELEM_TAG)) { |