diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-05-16 00:34:40 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-05-16 00:34:40 +0400 |
commit | 1df12416cac4e9c0339667626a41529a6a597e26 (patch) | |
tree | 9d5177b001f9e043fcd9bc4c521ae6197bfa2353 | |
parent | 85530846b66c3e206dee82a1eb64d28a924bfc9e (diff) |
bmesh, grid fill tool.
This uses 2 edge loops and fills them with a grid, taking into account curvature of surrounding edges.
Access from face menu: Ctrl+F,G
http://www.graphicall.org/ftp/ideasman42/grid_fill.png
-rw-r--r-- | release/scripts/startup/bl_ui/space_view3d.py | 1 | ||||
-rw-r--r-- | source/blender/bmesh/CMakeLists.txt | 1 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_opdefines.c | 24 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_operators_private.h | 1 | ||||
-rw-r--r-- | source/blender/bmesh/operators/bmo_grid_fill.c | 418 | ||||
-rw-r--r-- | source/blender/editors/mesh/editmesh_tools.c | 54 | ||||
-rw-r--r-- | source/blender/editors/mesh/mesh_intern.h | 1 | ||||
-rw-r--r-- | source/blender/editors/mesh/mesh_ops.c | 1 |
8 files changed, 501 insertions, 0 deletions
diff --git a/release/scripts/startup/bl_ui/space_view3d.py b/release/scripts/startup/bl_ui/space_view3d.py index b682700e75b..7e4845a562f 100644 --- a/release/scripts/startup/bl_ui/space_view3d.py +++ b/release/scripts/startup/bl_ui/space_view3d.py @@ -1966,6 +1966,7 @@ class VIEW3D_MT_edit_mesh_faces(Menu): layout.operator("mesh.flip_normals") layout.operator("mesh.edge_face_add") layout.operator("mesh.fill") + layout.operator("mesh.fill_grid") layout.operator("mesh.beautify_fill") layout.operator("mesh.inset") layout.operator("mesh.bevel").vertex_only = False diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt index dd8bb22727c..9114a183e2d 100644 --- a/source/blender/bmesh/CMakeLists.txt +++ b/source/blender/bmesh/CMakeLists.txt @@ -50,6 +50,7 @@ set(SRC operators/bmo_edgenet.c operators/bmo_edgesplit.c operators/bmo_extrude.c + operators/bmo_grid_fill.c operators/bmo_hull.c operators/bmo_inset.c operators/bmo_join_triangles.c diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c index 53e01b94712..88fc7652885 100644 --- a/source/blender/bmesh/intern/bmesh_opdefines.c +++ b/source/blender/bmesh/intern/bmesh_opdefines.c @@ -530,6 +530,29 @@ static BMOpDefine bmo_bridge_loops_def = { }; /* + * Grid Fill. + * + * Create faces defined by 2 disconnected edge loops (which share edges). + */ +static BMOpDefine bmo_grid_fill_def = { + "grid_fill", + /* slots_in */ + {{"edges", BMO_OP_SLOT_ELEMENT_BUF, {BM_EDGE}}, /* input edges */ + /* restricts edges to groups. maps edges to integer */ + {"mat_nr", BMO_OP_SLOT_INT}, /* material to use */ + {"use_smooth", BMO_OP_SLOT_BOOL}, /* smooth state to use */ + {{'\0'}}, + }, + /* slots_out */ + /* maps new faces to the group numbers they came from */ + {{"faces.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_FACE}}, /* new faces */ + {{'\0'}}, + }, + bmo_grid_fill_exec, + BMO_OPTYPE_FLAG_NORMALS_CALC | BMO_OPTYPE_FLAG_SELECT_FLUSH, +}; + +/* * Edge Loop Fill. * * Create faces defined by one or more non overlapping edge loops. @@ -1701,6 +1724,7 @@ const BMOpDefine *bmo_opdefines[] = { &bmo_extrude_face_region_def, &bmo_extrude_vert_indiv_def, &bmo_find_doubles_def, + &bmo_grid_fill_def, &bmo_inset_individual_def, &bmo_inset_region_def, &bmo_join_triangles_def, diff --git a/source/blender/bmesh/intern/bmesh_operators_private.h b/source/blender/bmesh/intern/bmesh_operators_private.h index 2a67407b261..bce599736d4 100644 --- a/source/blender/bmesh/intern/bmesh_operators_private.h +++ b/source/blender/bmesh/intern/bmesh_operators_private.h @@ -65,6 +65,7 @@ void bmo_extrude_edge_only_exec(BMesh *bm, BMOperator *op); void bmo_extrude_face_region_exec(BMesh *bm, BMOperator *op); void bmo_extrude_vert_indiv_exec(BMesh *bm, BMOperator *op); void bmo_find_doubles_exec(BMesh *bm, BMOperator *op); +void bmo_grid_fill_exec(BMesh *bm, BMOperator *op); void bmo_inset_individual_exec(BMesh *bm, BMOperator *op); void bmo_inset_region_exec(BMesh *bm, BMOperator *op); void bmo_join_triangles_exec(BMesh *bm, BMOperator *op); diff --git a/source/blender/bmesh/operators/bmo_grid_fill.c b/source/blender/bmesh/operators/bmo_grid_fill.c new file mode 100644 index 00000000000..5c25c5a042a --- /dev/null +++ b/source/blender/bmesh/operators/bmo_grid_fill.c @@ -0,0 +1,418 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * Contributor(s): Campbell Barton. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/bmesh/operators/bmo_grid_fill.c + * \ingroup bmesh + * + * Fill 2 isolated, open edge loops with a grid of quads. + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_listbase.h" +#include "BLI_math.h" + +#include "bmesh.h" + +#include "intern/bmesh_operators_private.h" /* own include */ + +#define EDGE_MARK 4 +#define FACE_OUT 16 + +#define BARYCENTRIC_INTERP + +#ifdef BARYCENTRIC_INTERP +/** + * 2 edge vectors to normal. + */ +static void quad_edges_to_normal( + float no[3], + const float co_a1[3], const float co_a2[3], + const float co_b1[3], const float co_b2[3]) +{ + float diff_a[3]; + float diff_b[3]; + + sub_v3_v3v3(diff_a, co_a2, co_a1); + sub_v3_v3v3(diff_b, co_b2, co_b1); + normalize_v3(diff_a); + normalize_v3(diff_b); + add_v3_v3v3(no, diff_a, diff_b); + normalize_v3(no); +} + +static void quad_verts_to_barycentric_tri( + float tri[3][3], + float co_a[3], + float co_b[3], + + float co_a_next[3], + float co_b_next[3], + + float co_a_prev[3], + float co_b_prev[3], + bool is_flip + ) +{ + float no[3]; + + copy_v3_v3(tri[0], co_a); + copy_v3_v3(tri[1], co_b); + + quad_edges_to_normal(no, + co_a, co_a_next, + co_b, co_b_next); + + if (co_a_prev) { + float no_t[3]; + quad_edges_to_normal(no_t, + co_a_prev, co_a, + co_b_prev, co_b); + add_v3_v3(no, no_t); + normalize_v3(no); + } + + if (is_flip) negate_v3(no); + mul_v3_fl(no, len_v3v3(tri[0], tri[1])); + + mid_v3_v3v3(tri[2], tri[0], tri[1]); + add_v3_v3(tri[2], no); +} + +#endif + + +/** + * This may be useful outside the bmesh operator. + * + * \param v_grid 2d array of verts, all boundary verts must be set, we fill in the middle. + */ +static void bm_grid_fill_array(BMesh *bm, BMVert **v_grid, const int xtot, const int ytot, + const short mat_nr, const bool use_smooth, + const bool use_flip) +{ + int x, y; + +#define XY(_x, _y) ((_x) + ((_y) * (xtot))) + +#ifdef BARYCENTRIC_INTERP + float tri_a[3][3]; + float tri_b[3][3]; + float tri_t[3][3]; /* temp */ + + quad_verts_to_barycentric_tri( + tri_a, + v_grid[XY(0, 0)]->co, + v_grid[XY(xtot - 1, 0)]->co, + v_grid[XY(0, 1)]->co, + v_grid[XY(xtot - 1, 1)]->co, + NULL, NULL, + false); + + quad_verts_to_barycentric_tri( + tri_b, + v_grid[XY(0, (ytot - 1))]->co, + v_grid[XY(xtot - 1, (ytot - 1))]->co, + v_grid[XY(0, (ytot - 2))]->co, + v_grid[XY(xtot - 1, (ytot - 2))]->co, + NULL, NULL, + true); +#endif + + /* Build Verts */ + for (y = 1; y < ytot - 1; y++) { +#ifdef BARYCENTRIC_INTERP + quad_verts_to_barycentric_tri( + tri_t, + v_grid[XY(0, y + 0)]->co, + v_grid[XY(xtot - 1, y + 0)]->co, + v_grid[XY(0, y + 1)]->co, + v_grid[XY(xtot - 1, y + 1)]->co, + v_grid[XY(0, y - 1)]->co, + v_grid[XY(xtot - 1, y - 1)]->co, + false); +#endif + for (x = 1; x < xtot - 1; x++) { + float co[3]; + BMVert *v; + /* we may want to allow sparse filled arrays, but for now, ensure its empty */ + BLI_assert(v_grid[(y * xtot) + x] == NULL); + + /* place the vertex */ +#ifdef BARYCENTRIC_INTERP + { + float co_a[3], co_b[3]; + + barycentric_transform( + co_a, + v_grid[x]->co, + tri_t[0], tri_t[1], tri_t[2], + tri_a[0], tri_a[1], tri_a[2]); + barycentric_transform( + co_b, + v_grid[(xtot * ytot) + (x - xtot)]->co, + tri_t[0], tri_t[1], tri_t[2], + tri_b[0], tri_b[1], tri_b[2]); + + interp_v3_v3v3(co, co_a, co_b, (float)y / ((float)ytot - 1)); + } + +#else + interp_v3_v3v3( + co, + v_grid[x]->co, + v_grid[(xtot * ytot) + (x - xtot)]->co, + (float)y / ((float)ytot - 1)); +#endif + + v = BM_vert_create(bm, co, NULL, 0); + v_grid[(y * xtot) + x] = v; + } + } + + /* Build Faces */ + for (x = 0; x < xtot - 1; x++) { + for (y = 0; y < ytot - 1; y++) { + BMFace *f; + + if (use_flip) { + f = BM_face_create_quad_tri( + bm, + v_grid[XY(x, y + 0)], /* BL */ + v_grid[XY(x, y + 1)], /* TL */ + v_grid[XY(x + 1, y + 1)], /* TR */ + v_grid[XY(x + 1, y + 0)], /* BR */ + NULL, + false); + } + else { + f = BM_face_create_quad_tri( + bm, + v_grid[XY(x + 1, y + 0)], /* BR */ + v_grid[XY(x + 1, y + 1)], /* TR */ + v_grid[XY(x, y + 1)], /* TL */ + v_grid[XY(x, y + 0)], /* BL */ + NULL, + false); + } + BMO_elem_flag_enable(bm, f, FACE_OUT); + f->mat_nr = mat_nr; + if (use_smooth) { + BM_elem_flag_enable(f, BM_ELEM_SMOOTH); + } + } + } +#undef XY +} + +static void bm_grid_fill(BMesh *bm, + struct BMEdgeLoopStore *estore_a, struct BMEdgeLoopStore *estore_b, + struct BMEdgeLoopStore *estore_rail_a, struct BMEdgeLoopStore *estore_rail_b, + const short mat_nr, const bool use_smooth) +{ +#define USE_FLIP_DETECT + + const int xtot = BM_edgeloop_length_get(estore_a); + const int ytot = BM_edgeloop_length_get(estore_rail_a); + //BMVert *v; + int i; + int x, y; + LinkData *el; + bool use_flip = false; + + ListBase *lb_a = BM_edgeloop_verts_get(estore_a); + ListBase *lb_b = BM_edgeloop_verts_get(estore_b); + + ListBase *lb_rail_a = BM_edgeloop_verts_get(estore_rail_a); + ListBase *lb_rail_b = BM_edgeloop_verts_get(estore_rail_b); + + BMVert **v_grid = MEM_callocN(sizeof(BMVert *) * xtot * ytot, __func__); + /** + * <pre> + * estore_b + * +------------------+ + * ^ | | + * end | | | + * | | | + * | |estore_rail_a |estore_rail_b + * | | | + * start | | | + * |estore_a | + * +------------------+ + * ---> + * start -> end + * </pre> + */ + + BLI_assert(((LinkData *)lb_a->first)->data == ((LinkData *)lb_rail_a->first)->data); /* BL */ + BLI_assert(((LinkData *)lb_b->first)->data == ((LinkData *)lb_rail_a->last)->data); /* TL */ + BLI_assert(((LinkData *)lb_b->last)->data == ((LinkData *)lb_rail_b->last)->data); /* TR */ + BLI_assert(((LinkData *)lb_a->last)->data == ((LinkData *)lb_rail_b->first)->data); /* BR */ + + for (el = lb_a->first, i = 0; el; el = el->next, i++) { v_grid[i] = el->data; } + for (el = lb_b->first, i = 0; el; el = el->next, i++) { v_grid[(ytot * xtot) + (i - xtot)] = el->data; } + for (el = lb_rail_a->first, i = 0; el; el = el->next, i++) { v_grid[xtot * i] = el->data; } + for (el = lb_rail_b->first, i = 0; el; el = el->next, i++) { v_grid[(xtot * i) + (xtot - 1)] = el->data; } + for (x = 1; x < xtot - 1; x++) { for (y = 1; y < ytot - 1; y++) { BLI_assert(v_grid[(y * xtot) + x] == NULL); }} + +#ifdef USE_FLIP_DETECT + { + ListBase *lb_iter[4] = {lb_a, lb_b, lb_rail_a, lb_rail_b}; + const int lb_iter_dir[4] = {1, -1, 1, -1}; + int winding_votes = 0; + + for (i = 0; i < 4; i++) { + LinkData *el_next; + for (el = lb_iter[i]->first; el && (el_next = el->next); el = el->next) { + BMEdge *e = BM_edge_exists(el->data, el_next->data); + if (BM_edge_is_boundary(e)) { + winding_votes += (e->l->v == el->data) ? lb_iter_dir[i] : -lb_iter_dir[i]; + } + } + } + use_flip = (winding_votes < 0); + } +#endif + + + bm_grid_fill_array(bm, v_grid, xtot, ytot, mat_nr, use_smooth, use_flip); + MEM_freeN(v_grid); + +#undef USE_FLIP_DETECT +} + +static bool bm_edge_test_cb(BMEdge *e, void *bm_v) +{ + return BMO_elem_flag_test((BMesh *)bm_v, e, EDGE_MARK); +} + +static bool bm_edge_test_rail_cb(BMEdge *e, void *UNUSED(bm_v)) +{ + return BM_edge_is_wire(e) || BM_edge_is_boundary(e); +} + +void bmo_grid_fill_exec(BMesh *bm, BMOperator *op) +{ + ListBase eloops = {NULL, NULL}; + ListBase eloops_rail = {NULL, NULL}; + struct BMEdgeLoopStore *estore_a, *estore_b; + struct BMEdgeLoopStore *estore_rail_a, *estore_rail_b; + BMVert *v_a_first, *v_a_last; + BMVert *v_b_first, *v_b_last; + const short mat_nr = BMO_slot_int_get(op->slots_in, "mat_nr"); + const bool use_smooth = BMO_slot_bool_get(op->slots_in, "use_smooth"); + + int count; + bool change = false; + BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK); + + count = BM_mesh_edgeloops_find(bm, &eloops, bm_edge_test_cb, (void *)bm); + + if (count != 2) { + BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, + "Select two edge loops"); + goto cleanup; + } + + estore_a = eloops.first; + estore_b = eloops.last; + + v_a_first = ((LinkData *)BM_edgeloop_verts_get(estore_a)->first)->data; + v_a_last = ((LinkData *)BM_edgeloop_verts_get(estore_a)->last)->data; + v_b_first = ((LinkData *)BM_edgeloop_verts_get(estore_b)->first)->data; + v_b_last = ((LinkData *)BM_edgeloop_verts_get(estore_b)->last)->data; + + if (BM_edgeloop_length_get(estore_a) != BM_edgeloop_length_get(estore_b)) { + BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, + "Edge loop vertex count mismatch"); + goto cleanup; + } + + if (BM_edgeloop_is_closed(estore_a) || BM_edgeloop_is_closed(estore_b)) { + BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, + "Closed loops unsupported"); + goto cleanup; + } + + /* ok. all error checking done, now we can find the rail edges */ + + if (BM_mesh_edgeloops_find_path(bm, &eloops_rail, bm_edge_test_rail_cb, bm, v_a_first, v_b_first) == false) { + BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, + "Loops are not connected by wire/boundary edges"); + goto cleanup; + } + + BM_mesh_edgeloops_find_path(bm, &eloops_rail, bm_edge_test_rail_cb, (void *)bm, v_a_first, v_b_last); + + /* Check flipping by comparing path length */ + estore_rail_a = eloops_rail.first; + estore_rail_b = eloops_rail.last; + + BLI_assert(BM_edgeloop_length_get(estore_rail_a) != BM_edgeloop_length_get(estore_rail_b)); + + if (BM_edgeloop_length_get(estore_rail_a) < BM_edgeloop_length_get(estore_rail_b)) { + BLI_remlink(&eloops_rail, estore_rail_b); + BM_edgeloop_free(estore_rail_b); + estore_rail_b = NULL; + + BM_mesh_edgeloops_find_path(bm, &eloops_rail, bm_edge_test_rail_cb, (void *)bm, + v_a_last, + v_b_last); + estore_rail_b = eloops_rail.last; + } + else { /* a > b */ + BLI_remlink(&eloops_rail, estore_rail_a); + BM_edgeloop_free(estore_rail_a); + estore_rail_a = estore_rail_b; + + /* reverse so these so both are sorted the same way */ + BM_edgeloop_flip(bm, estore_b); + SWAP(BMVert *, v_b_first, v_b_last); + + BM_mesh_edgeloops_find_path(bm, &eloops_rail, bm_edge_test_rail_cb, (void *)bm, + v_a_last, + v_b_last); + estore_rail_b = eloops_rail.last; + } + + BLI_assert(estore_a != estore_b); + BLI_assert(v_a_last != v_b_last); + + if (BM_edgeloop_length_get(estore_rail_a) != BM_edgeloop_length_get(estore_rail_b)) { + BMO_error_raise(bm, op, BMERR_INVALID_SELECTION, + "Connecting edges vertex mismatch"); + goto cleanup; + } + + /* finally we have all edge loops needed */ + bm_grid_fill(bm, estore_a, estore_b, estore_rail_a, estore_rail_b, + mat_nr, use_smooth); + + change = true; +cleanup: + BM_mesh_edgeloops_free(&eloops); + BM_mesh_edgeloops_free(&eloops_rail); + + if (change) { + BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT); + } +} diff --git a/source/blender/editors/mesh/editmesh_tools.c b/source/blender/editors/mesh/editmesh_tools.c index 65e31b2093b..9d466b924a8 100644 --- a/source/blender/editors/mesh/editmesh_tools.c +++ b/source/blender/editors/mesh/editmesh_tools.c @@ -2605,6 +2605,60 @@ void MESH_OT_fill(wmOperatorType *ot) RNA_def_boolean(ot->srna, "use_beauty", true, "Beauty", "Use best triangulation division"); } +static int edbm_fill_grid_exec(bContext *C, wmOperator *op) +{ + BMOperator bmop; + Object *obedit = CTX_data_edit_object(C); + BMEditMesh *em = BKE_editmesh_from_object(obedit); + const short use_smooth = edbm_add_edge_face__smooth_get(em->bm); + const int totedge_orig = em->bm->totedge; + const int totface_orig = em->bm->totface; + + if (!EDBM_op_init(em, &bmop, op, + "grid_fill edges=%he mat_nr=%i use_smooth=%b", + BM_ELEM_SELECT, em->mat_nr, use_smooth)) + { + return OPERATOR_CANCELLED; + } + + BMO_op_exec(em->bm, &bmop); + + /* cancel if nothing was done */ + if ((totedge_orig == em->bm->totedge) && + (totface_orig == em->bm->totface)) + { + EDBM_op_finish(em, &bmop, op, true); + return OPERATOR_CANCELLED; + } + + BMO_slot_buffer_hflag_enable(em->bm, bmop.slots_out, "faces.out", BM_FACE, BM_ELEM_SELECT, true); + + if (!EDBM_op_finish(em, &bmop, op, true)) { + return OPERATOR_CANCELLED; + } + + EDBM_update_generic(em, true, true); + + return OPERATOR_FINISHED; +} + +void MESH_OT_fill_grid(wmOperatorType *ot) +{ + /* identifiers */ + ot->name = "Fill Grid"; + ot->description = "Fill grid from two loops"; + ot->idname = "MESH_OT_fill_grid"; + + /* api callbacks */ + ot->exec = edbm_fill_grid_exec; + ot->poll = ED_operator_editmesh; + + /* flags */ + ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO; +} + + + static int edbm_beautify_fill_exec(bContext *C, wmOperator *op) { Object *obedit = CTX_data_edit_object(C); diff --git a/source/blender/editors/mesh/mesh_intern.h b/source/blender/editors/mesh/mesh_intern.h index 3cec07414d0..15de5f6bf79 100644 --- a/source/blender/editors/mesh/mesh_intern.h +++ b/source/blender/editors/mesh/mesh_intern.h @@ -193,6 +193,7 @@ void MESH_OT_solidify(struct wmOperatorType *ot); void MESH_OT_knife_cut(struct wmOperatorType *ot); void MESH_OT_separate(struct wmOperatorType *ot); void MESH_OT_fill(struct wmOperatorType *ot); +void MESH_OT_fill_grid(struct wmOperatorType *ot); void MESH_OT_beautify_fill(struct wmOperatorType *ot); void MESH_OT_quads_convert_to_tris(struct wmOperatorType *ot); void MESH_OT_tris_convert_to_quads(struct wmOperatorType *ot); diff --git a/source/blender/editors/mesh/mesh_ops.c b/source/blender/editors/mesh/mesh_ops.c index f27479b57a3..6f26875c73e 100644 --- a/source/blender/editors/mesh/mesh_ops.c +++ b/source/blender/editors/mesh/mesh_ops.c @@ -98,6 +98,7 @@ void ED_operatortypes_mesh(void) WM_operatortype_append(MESH_OT_colors_reverse); WM_operatortype_append(MESH_OT_fill); + WM_operatortype_append(MESH_OT_fill_grid); WM_operatortype_append(MESH_OT_beautify_fill); WM_operatortype_append(MESH_OT_quads_convert_to_tris); WM_operatortype_append(MESH_OT_tris_convert_to_quads); |