[Bf-blender-cvs] [64124ba] master: BMesh: tool to ensure all faces are convex
Campbell Barton
noreply at git.blender.org
Sun Feb 1 23:24:10 CET 2015
Commit: 64124ba904dcaac2bf029a55943282843b8a2603
Author: Campbell Barton
Date: Mon Feb 2 09:04:31 2015 +1100
Branches: master
https://developer.blender.org/rB64124ba904dcaac2bf029a55943282843b8a2603
BMesh: tool to ensure all faces are convex
Access from Mesh -> Cleanup
===================================================================
M release/scripts/startup/bl_ui/space_view3d.py
M source/blender/bmesh/CMakeLists.txt
M source/blender/bmesh/intern/bmesh_opdefines.c
M source/blender/bmesh/intern/bmesh_operators_private.h
M source/blender/bmesh/intern/bmesh_polygon.h
M source/blender/bmesh/intern/bmesh_queries.h
A source/blender/bmesh/operators/bmo_connect_concave.c
M source/blender/bmesh/tools/bmesh_triangulate.c
M source/blender/editors/mesh/editmesh_tools.c
M source/blender/editors/mesh/mesh_intern.h
M source/blender/editors/mesh/mesh_ops.c
===================================================================
diff --git a/release/scripts/startup/bl_ui/space_view3d.py b/release/scripts/startup/bl_ui/space_view3d.py
index 661c38a..c45d639 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 2373786..80adb59 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 1143588..d0679b9 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 9c1b708..979f7d2 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 b25a7db..9980b59 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 abff557..535b752 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 0000000..aec8119
--- /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 (chan
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list