diff options
| -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)) { |