diff options
-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 | 23 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_operators_private.h | 1 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.h | 2 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_queries.h | 1 | ||||
-rw-r--r-- | source/blender/bmesh/operators/bmo_connect_concave.c | 211 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_triangulate.c | 8 | ||||
-rw-r--r-- | source/blender/editors/mesh/editmesh_tools.c | 34 | ||||
-rw-r--r-- | source/blender/editors/mesh/mesh_intern.h | 1 | ||||
-rw-r--r-- | source/blender/editors/mesh/mesh_ops.c | 1 |
11 files changed, 282 insertions, 2 deletions
diff --git a/release/scripts/startup/bl_ui/space_view3d.py b/release/scripts/startup/bl_ui/space_view3d.py index 661c38a6a38..c45d639737d 100644 --- a/release/scripts/startup/bl_ui/space_view3d.py +++ b/release/scripts/startup/bl_ui/space_view3d.py @@ -2381,6 +2381,7 @@ class VIEW3D_MT_edit_mesh_clean(Menu): layout.operator("mesh.dissolve_degenerate") layout.operator("mesh.dissolve_limited") layout.operator("mesh.vert_connect_nonplanar") + layout.operator("mesh.vert_connect_concave") layout.operator("mesh.fill_holes") diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt index 23737866bf2..80adb595ac9 100644 --- a/source/blender/bmesh/CMakeLists.txt +++ b/source/blender/bmesh/CMakeLists.txt @@ -43,6 +43,7 @@ set(SRC operators/bmo_bisect_plane.c operators/bmo_bridge.c operators/bmo_connect.c + operators/bmo_connect_concave.c operators/bmo_connect_nonplanar.c operators/bmo_connect_pair.c operators/bmo_create.c diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c index 114358884b7..d0679b9919a 100644 --- a/source/blender/bmesh/intern/bmesh_opdefines.c +++ b/source/blender/bmesh/intern/bmesh_opdefines.c @@ -933,6 +933,28 @@ static BMOpDefine bmo_connect_verts_def = { }; /* + * Connect Verts to form Convex Faces. + * + * Ensures all faces are convex **faces**. + */ +static BMOpDefine bmo_connect_verts_concave_def = { + "connect_verts_concave", + /* slots_in */ + {{"faces", BMO_OP_SLOT_ELEMENT_BUF, {BM_FACE}}, + {{'\0'}}, + }, + /* slots_out */ + {{"edges.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_EDGE}}, + {"faces.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_FACE}}, + {{'\0'}}, + }, + bmo_connect_verts_concave_exec, + (BMO_OPTYPE_FLAG_UNTAN_MULTIRES | + BMO_OPTYPE_FLAG_NORMALS_CALC | + BMO_OPTYPE_FLAG_SELECT_FLUSH), +}; + +/* * Connect Verts Across non Planer Faces. * * Split faces by connecting edges along non planer **faces**. @@ -1950,6 +1972,7 @@ const BMOpDefine *bmo_opdefines[] = { &bmo_collapse_def, &bmo_collapse_uvs_def, &bmo_connect_verts_def, + &bmo_connect_verts_concave_def, &bmo_connect_verts_nonplanar_def, &bmo_connect_vert_pair_def, &bmo_contextual_create_def, diff --git a/source/blender/bmesh/intern/bmesh_operators_private.h b/source/blender/bmesh/intern/bmesh_operators_private.h index 9c1b7085835..979f7d2640a 100644 --- a/source/blender/bmesh/intern/bmesh_operators_private.h +++ b/source/blender/bmesh/intern/bmesh_operators_private.h @@ -41,6 +41,7 @@ void bmo_bridge_loops_exec(BMesh *bm, BMOperator *op); void bmo_collapse_exec(BMesh *bm, BMOperator *op); void bmo_collapse_uvs_exec(BMesh *bm, BMOperator *op); void bmo_connect_verts_exec(BMesh *bm, BMOperator *op); +void bmo_connect_verts_concave_exec(BMesh *bm, BMOperator *op); void bmo_connect_verts_nonplanar_exec(BMesh *bm, BMOperator *op); void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op); void bmo_contextual_create_exec(BMesh *bm, BMOperator *op); diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h index b25a7dbaa55..9980b59a298 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.h +++ b/source/blender/bmesh/intern/bmesh_polygon.h @@ -63,6 +63,8 @@ void BM_face_triangulate( BMesh *bm, BMFace *f, BMFace **r_faces_new, int *r_faces_new_tot, + BMEdge **r_edges_new, + int *r_edges_new_tot, const int quad_method, const int ngon_method, const bool use_tag, struct MemArena *pf_arena, diff --git a/source/blender/bmesh/intern/bmesh_queries.h b/source/blender/bmesh/intern/bmesh_queries.h index abff55719f5..535b752d4f2 100644 --- a/source/blender/bmesh/intern/bmesh_queries.h +++ b/source/blender/bmesh/intern/bmesh_queries.h @@ -143,6 +143,7 @@ bool BM_face_is_any_vert_flag_test(const BMFace *f, const char hflag) ATTR_WARN_ bool BM_face_is_any_edge_flag_test(const BMFace *f, const char hflag) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); bool BM_face_is_normal_valid(const BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); +bool BM_face_is_convex(const BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); float BM_mesh_calc_volume(BMesh *bm, bool is_signed) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); diff --git a/source/blender/bmesh/operators/bmo_connect_concave.c b/source/blender/bmesh/operators/bmo_connect_concave.c new file mode 100644 index 00000000000..aec8119d421 --- /dev/null +++ b/source/blender/bmesh/operators/bmo_connect_concave.c @@ -0,0 +1,211 @@ +/* + * ***** 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. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/bmesh/operators/bmo_connect_concave.c + * \ingroup bmesh + * + * Connect vertices so all resulting faces are convex. + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_math.h" +#include "BLI_utildefines.h" +#include "BLI_alloca.h" +#include "BLI_memarena.h" +#include "BLI_heap.h" +#include "BLI_polyfill2d.h" +#include "BLI_polyfill2d_beautify.h" +#include "BLI_edgehash.h" + +#include "bmesh.h" + +#include "intern/bmesh_operators_private.h" /* own include */ + +#define EDGE_OUT (1 << 0) +#define FACE_OUT (1 << 1) + +static int bm_edge_length_cmp(const void *a_, const void *b_) +{ + const BMEdge *e_a = *(const void **)a_; + const BMEdge *e_b = *(const void **)b_; + + int e_a_concave = ((BM_elem_flag_test(e_a->v1, BM_ELEM_TAG)) && (BM_elem_flag_test(e_a->v2, BM_ELEM_TAG))); + int e_b_concave = ((BM_elem_flag_test(e_b->v1, BM_ELEM_TAG)) && (BM_elem_flag_test(e_b->v2, BM_ELEM_TAG))); + + /* merge edges between concave edges last since these + * are most likely to remain and be the main dividers */ + if (e_a_concave < e_b_concave) return -1; + else if (e_a_concave > e_b_concave) return 1; + else + { + const float e_a_len = BM_edge_calc_length_squared(e_a); + const float e_b_len = BM_edge_calc_length_squared(e_b); + if (e_a_len < e_b_len) return 1; + else if (e_a_len > e_b_len) return -1; + else return 0; + } +} + +static bool bm_face_split_by_concave( + BMesh *bm, BMFace *f_base, const float eps, + + MemArena *pf_arena, + struct Heap *pf_heap, struct EdgeHash *pf_ehash) +{ + const int f_base_len = f_base->len; + int faces_array_tot = f_base->len - 3; + int edges_array_tot = f_base->len - 3; + BMFace **faces_array = BLI_array_alloca(faces_array, faces_array_tot); + BMEdge **edges_array = BLI_array_alloca(edges_array, edges_array_tot); + const int quad_method = 0, ngon_method = 0; /* beauty */ + + float normal[3]; + BLI_assert(f_base->len > 3); + + copy_v3_v3(normal, f_base->no); + + BM_face_triangulate( + bm, f_base, + faces_array, &faces_array_tot, + edges_array, &edges_array_tot, + quad_method, ngon_method, false, + pf_arena, + pf_heap, pf_ehash); + + BLI_assert(edges_array_tot <= f_base_len - 3); + + if (faces_array_tot) { + int i; + for (i = 0; i < faces_array_tot; i++) { + BMFace *f = faces_array[i]; + BMO_elem_flag_enable(bm, f, FACE_OUT); + } + } + BMO_elem_flag_enable(bm, f_base, FACE_OUT); + + if (edges_array_tot) { + int i; + + qsort(edges_array, edges_array_tot, sizeof(*edges_array), bm_edge_length_cmp); + + for (i = 0; i < edges_array_tot; i++) { + BMLoop *l_pair[2]; + BMEdge *e = edges_array[i]; + BMO_elem_flag_enable(bm, e, EDGE_OUT); + + if (BM_edge_is_contiguous(e) && + BM_edge_loop_pair(e, &l_pair[0], &l_pair[1])) + { + bool ok = true; + int j; + for (j = 0; j < 2; j++) { + BMLoop *l = l_pair[j]; + + /* check that merging the edge (on this side) + * wouldn't result in a convex face-loop. + * + * This is the (l->next, l->prev) we would have once joined. + */ + float cross[3]; + cross_tri_v3( + cross, + l->v->co, + l->radial_next->next->next->v->co, + l->prev->v->co + ); + + if (dot_v3v3(cross, normal) <= eps) { + ok = false; + break; + } + } + + if (ok) { + BMFace *f_new, *f_pair[2] = {l_pair[0]->f, l_pair[1]->f}; + f_new = BM_faces_join(bm, f_pair, 2, true); + if (f_new) { + BMO_elem_flag_enable(bm, f_new, FACE_OUT); + } + } + } + } + } + + BLI_heap_clear(pf_heap, NULL); + BLI_edgehash_clear_ex(pf_ehash, NULL, BLI_POLYFILL_ALLOC_NGON_RESERVE); + + return true; +} + +static bool bm_face_convex_tag_verts(BMFace *f) +{ + bool is_concave = false; + if (f->len > 3) { + const BMLoop *l_iter, *l_first; + + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + if (BM_loop_is_convex(l_iter) == false) { + is_concave = true; + BM_elem_flag_enable(l_iter->v, BM_ELEM_TAG); + } + else { + BM_elem_flag_disable(l_iter->v, BM_ELEM_TAG); + } + } while ((l_iter = l_iter->next) != l_first); + } + return is_concave; +} + +void bmo_connect_verts_concave_exec(BMesh *bm, BMOperator *op) +{ + BMOIter siter; + BMFace *f; + bool changed = false; + + MemArena *pf_arena; + Heap *pf_heap; + EdgeHash *pf_ehash; + + pf_arena = BLI_memarena_new(BLI_POLYFILL_ARENA_SIZE, __func__); + pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE); + pf_ehash = BLI_edgehash_new_ex(__func__, BLI_POLYFILL_ALLOC_NGON_RESERVE); + + BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) { + if (f->len > 3 && bm_face_convex_tag_verts(f)) { + if (bm_face_split_by_concave( + bm, f, FLT_EPSILON, + pf_arena, pf_heap, pf_ehash)) + { + changed = true; + } + } + } + + if (changed) { + BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_OUT); + BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_OUT); + } + + BLI_memarena_free(pf_arena); + BLI_heap_free(pf_heap, NULL); + BLI_edgehash_free(pf_ehash, NULL); +} diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c index b76054f270f..404776a0769 100644 --- a/source/blender/bmesh/tools/bmesh_triangulate.c +++ b/source/blender/bmesh/tools/bmesh_triangulate.c @@ -64,7 +64,9 @@ static void bm_face_triangulate_mapping( BLI_assert(face->len > 3); BM_face_triangulate( - bm, face, faces_array, &faces_array_tot, + bm, face, + faces_array, &faces_array_tot, + NULL, NULL, quad_method, ngon_method, use_tag, pf_arena, pf_heap, pf_ehash); @@ -121,7 +123,9 @@ void BM_mesh_triangulate( if (face->len > 3) { if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) { BM_face_triangulate( - bm, face, NULL, NULL, + bm, face, + NULL, NULL, + NULL, NULL, quad_method, ngon_method, tag_only, pf_arena, pf_heap, pf_ehash); diff --git a/source/blender/editors/mesh/editmesh_tools.c b/source/blender/editors/mesh/editmesh_tools.c index 1e301e09837..3a9e366fe37 100644 --- a/source/blender/editors/mesh/editmesh_tools.c +++ b/source/blender/editors/mesh/editmesh_tools.c @@ -964,6 +964,40 @@ void MESH_OT_vert_connect(wmOperatorType *ot) ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO; } +static int edbm_vert_connect_concave_exec(bContext *C, wmOperator *op) +{ + Object *obedit = CTX_data_edit_object(C); + BMEditMesh *em = BKE_editmesh_from_object(obedit); + + if (!EDBM_op_call_and_selectf( + em, op, + "faces.out", true, + "connect_verts_concave faces=%hf", + BM_ELEM_SELECT)) + { + return OPERATOR_CANCELLED; + } + + + EDBM_update_generic(em, true, true); + return OPERATOR_FINISHED; +} + +void MESH_OT_vert_connect_concave(wmOperatorType *ot) +{ + /* identifiers */ + ot->name = "Split Concave Faces"; + ot->idname = "MESH_OT_vert_connect_concave"; + ot->description = "Makes all faces convex"; + + /* api callbacks */ + ot->exec = edbm_vert_connect_concave_exec; + ot->poll = ED_operator_editmesh; + + /* flags */ + ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO; +} + static int edbm_vert_connect_nonplaner_exec(bContext *C, wmOperator *op) { diff --git a/source/blender/editors/mesh/mesh_intern.h b/source/blender/editors/mesh/mesh_intern.h index 6ba91097ec4..a794db62e3e 100644 --- a/source/blender/editors/mesh/mesh_intern.h +++ b/source/blender/editors/mesh/mesh_intern.h @@ -175,6 +175,7 @@ void MESH_OT_normals_make_consistent(struct wmOperatorType *ot); void MESH_OT_vertices_smooth(struct wmOperatorType *ot); void MESH_OT_vertices_smooth_laplacian(struct wmOperatorType *ot); void MESH_OT_vert_connect(struct wmOperatorType *ot); +void MESH_OT_vert_connect_concave(struct wmOperatorType *ot); void MESH_OT_vert_connect_nonplanar(struct wmOperatorType *ot); void MESH_OT_edge_split(struct wmOperatorType *ot); void MESH_OT_bridge_edge_loops(struct wmOperatorType *ot); diff --git a/source/blender/editors/mesh/mesh_ops.c b/source/blender/editors/mesh/mesh_ops.c index e7dc5a69d53..8146be7ee47 100644 --- a/source/blender/editors/mesh/mesh_ops.c +++ b/source/blender/editors/mesh/mesh_ops.c @@ -161,6 +161,7 @@ void ED_operatortypes_mesh(void) WM_operatortype_append(MESH_OT_solidify); WM_operatortype_append(MESH_OT_select_nth); WM_operatortype_append(MESH_OT_vert_connect); + WM_operatortype_append(MESH_OT_vert_connect_concave); WM_operatortype_append(MESH_OT_vert_connect_nonplanar); WM_operatortype_append(MESH_OT_knife_tool); WM_operatortype_append(MESH_OT_knife_project); |