BMesh: tool to ensure all faces are convex
Access from Mesh -> Cleanup
This commit is contained in:
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
|
@ -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")
|
||||
|
||||
|
||||
|
|
|
@ -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
|
||||
|
|
|
@ -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,
|
||||
|
|
|
@ -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);
|
||||
|
|
|
@ -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,
|
||||
|
|
|
@ -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();
|
||||
|
||||
|
|
|
@ -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);
|
||||
}
|
|
@ -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);
|
||||
|
|
|
@ -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)
|
||||
{
|
||||
|
|
|
@ -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);
|
||||
|
|
|
@ -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);
|
||||
|
|
Loading…
Reference in New Issue