BMesh: tool to ensure all faces are convex

Access from Mesh -> Cleanup
This commit is contained in:
Campbell Barton 2015-02-02 09:04:31 +11:00
parent d655a8f168
commit 64124ba904
Notes: blender-bot 2023-02-14 09:32:02 +01:00
Referenced by issue #43524, Warp modifier with custom curve is clamped to 0-1
11 changed files with 282 additions and 2 deletions

View File

@ -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")

View File

@ -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

View File

@ -932,6 +932,28 @@ static BMOpDefine bmo_connect_verts_def = {
BMO_OPTYPE_FLAG_SELECT_FLUSH),
};
/*
* 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.
*
@ -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,

View File

@ -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);

View File

@ -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,

View File

@ -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();

View File

@ -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);
}

View File

@ -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);

View File

@ -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)
{

View File

@ -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);

View File

@ -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);