[Bf-blender-cvs] [58ae64b] soc-2013-paint: BMesh: new face splitting function BM_face_split_edgenet
Campbell Barton
noreply at git.blender.org
Sat Jul 12 12:44:50 CEST 2014
Commit: 58ae64b2bb58fe0042b73d0f3518bb9a5b957866
Author: Campbell Barton
Date: Fri Jul 11 10:29:53 2014 +1000
https://developer.blender.org/rB58ae64b2bb58fe0042b73d0f3518bb9a5b957866
BMesh: new face splitting function BM_face_split_edgenet
This takes a face and an edge-net, splitting the face into regions
defined by the edge-net.
===================================================================
M source/blender/bmesh/intern/bmesh_mods.c
M source/blender/bmesh/intern/bmesh_mods.h
M source/blender/bmesh/intern/bmesh_private.h
===================================================================
diff --git a/source/blender/bmesh/intern/bmesh_mods.c b/source/blender/bmesh/intern/bmesh_mods.c
index 2d7a2cf..4d3fac4 100644
--- a/source/blender/bmesh/intern/bmesh_mods.c
+++ b/source/blender/bmesh/intern/bmesh_mods.c
@@ -32,12 +32,19 @@
#include "BLI_math.h"
#include "BLI_array.h"
+#include "BLI_alloca.h"
+#include "BLI_stackdefines.h"
+#include "BLI_linklist_stack.h"
+#include "BLI_sort_utils.h"
#include "BKE_customdata.h"
#include "bmesh.h"
#include "intern/bmesh_private.h"
+// #define DEBUG_PRINT
+
+
/**
* \brief Dissolve Vert
*
@@ -416,6 +423,536 @@ BMFace *BM_face_split_n(BMesh *bm, BMFace *f,
return f_new;
}
+
+/* -------------------------------------------------------------------- */
+/* Face Split Edge-Net */
+
+/** \name BM_face_split_edgenet and helper functions.
+ *
+ * \note Don't use #BM_edge_is_wire or #BM_edge_is_boundary
+ * since we need to take flagged faces into account.
+ * Also take care accessing e->l directly.
+ *
+ * \{ */
+
+/* Note: All these flags _must_ be cleared on exit */
+
+/* face is apart of the edge-net (including the original face we're splitting) */
+#define FACE_NET _FLAG_WALK
+/* edge is apart of the edge-net we're filling */
+#define EDGE_NET _FLAG_WALK
+/* tag verts we've visit */
+#define VERT_VISIT _FLAG_WALK
+
+struct VertOrder {
+ float angle;
+ BMVert *v;
+};
+
+static unsigned int bm_edge_flagged_radial_count(BMEdge *e)
+{
+ unsigned int count = 0;
+ BMLoop *l;
+
+ if ((l = e->l)) {
+ do {
+ if (BM_ELEM_API_FLAG_TEST(l->f, FACE_NET)) {
+ count++;
+ }
+ } while ((l = l->radial_next) != e->l);
+ }
+ return count;
+}
+
+static BMLoop *bm_edge_flagged_radial_first(BMEdge *e)
+{
+ BMLoop *l;
+
+ if ((l = e->l)) {
+ do {
+ if (BM_ELEM_API_FLAG_TEST(l->f, FACE_NET)) {
+ return l;
+ }
+ } while ((l = l->radial_next) != e->l);
+ }
+ return NULL;
+}
+
+static bool bm_face_split_edgenet_find_loop_pair(
+ BMVert *v_init, const float face_normal[3],
+ BMEdge *e_pair[2])
+{
+ /* Always find one boundary edge (to determine winding)
+ * and one wire (if available), otherwise another boundary.
+ */
+ BMIter iter;
+ BMEdge *e;
+
+ /* detect winding */
+ BMLoop *l_walk;
+ bool swap;
+
+ BLI_SMALLSTACK_DECLARE(edges_boundary, BMEdge *);
+ BLI_SMALLSTACK_DECLARE(edges_wire, BMEdge *);
+ int edges_boundary_len = 0;
+ int edges_wire_len = 0;
+
+ BM_ITER_ELEM (e, &iter, v_init, BM_EDGES_OF_VERT) {
+ if (BM_ELEM_API_FLAG_TEST(e, EDGE_NET)) {
+ const unsigned int count = bm_edge_flagged_radial_count(e);
+ if (count == 1) {
+ BLI_SMALLSTACK_PUSH(edges_boundary, e);
+ edges_boundary_len++;
+ }
+ else if (count == 0) {
+ BLI_SMALLSTACK_PUSH(edges_wire, e);
+ edges_wire_len++;
+ }
+ }
+ }
+
+ /* first edge should always be boundary */
+ if (edges_boundary_len == 0) {
+ return false;
+ }
+ e_pair[0] = BLI_SMALLSTACK_POP(edges_boundary);
+
+ /* attempt one boundary and one wire, or 2 boundary */
+ if (edges_wire_len == 0) {
+ if (edges_boundary_len >= 2) {
+ e_pair[1] = BLI_SMALLSTACK_POP(edges_boundary);
+ }
+ else {
+ /* one boundary and no wire */
+ return false;
+ }
+ }
+ else {
+ e_pair[1] = BLI_SMALLSTACK_POP(edges_wire);
+
+ if (edges_wire_len > 1) {
+ BMVert *v_prev = BM_edge_other_vert(e_pair[0], v_init);
+ BMVert *v_next;
+ float angle_best;
+
+ v_next = BM_edge_other_vert(e_pair[1], v_init);
+ angle_best = angle_on_axis_v3v3v3_v3(v_prev->co, v_init->co, v_next->co, face_normal);
+
+ while ((e = BLI_SMALLSTACK_POP(edges_wire))) {
+ float angle_test;
+ v_next = BM_edge_other_vert(e, v_init);
+ angle_test = angle_on_axis_v3v3v3_v3(v_prev->co, v_init->co, v_next->co, face_normal);
+ if (angle_test < angle_best) {
+ angle_best = angle_test;
+ e_pair[1] = e;
+ }
+ }
+ }
+ }
+
+
+ /* flip based on winding */
+ l_walk = bm_edge_flagged_radial_first(e_pair[0]);
+ swap = false;
+ if (face_normal == l_walk->f->no) {
+ swap = !swap;
+ }
+ if (l_walk->v != v_init) {
+ swap = !swap;
+ }
+ if (swap) {
+ SWAP(BMEdge *, e_pair[0], e_pair[1]);
+ }
+
+ return true;
+}
+
+static bool bm_face_split_edgenet_find_loop_walk(
+ BMVert *v_init, const float face_normal[3],
+ /* cache to avoid realloc every time */
+ struct VertOrder *edge_order, const unsigned int edge_order_len,
+ BMEdge *e_pair[2])
+{
+ /* fast-path for the common case (avoid push-pop).
+ * Also avoids tagging as visited since we know we
+ * can't reach these verts some other way */
+#define USE_FASTPATH_NOFORK
+
+ BMVert *v;
+ BMVert *v_dst;
+ bool found = false;
+
+ struct VertOrder *eo;
+ STACK_DECLARE(edge_order);
+
+ /* store visited verts so we can clear the visit flag after execution */
+ BLI_SMALLSTACK_DECLARE(vert_visit, BMVert *);
+
+ /* likely this will stay very small
+ * all verts pushed into this stack _must_ have their previous edges set! */
+ BLI_SMALLSTACK_DECLARE(vert_stack, BMVert *);
+ BLI_SMALLSTACK_DECLARE(vert_stack_next, BMVert *);
+
+ STACK_INIT(edge_order, edge_order_len);
+
+ /* start stepping */
+ v = BM_edge_other_vert(e_pair[0], v_init);
+ v->e = e_pair[0];
+ BLI_SMALLSTACK_PUSH(vert_stack, v);
+
+ v_dst = BM_edge_other_vert(e_pair[1], v_init);
+
+#ifdef DEBUG_PRINT
+ printf("%s: vert (search) %d\n", __func__, BM_elem_index_get(v_init));
+#endif
+
+ /* This loop will keep stepping over the best possible edge,
+ * in most cases it finds the direct route to close the face.
+ *
+ * In cases where paths can't be closed,
+ * alternatives are stored in the 'vert_stack'.
+ */
+ while ((v = BLI_SMALLSTACK_POP_EX(vert_stack, vert_stack_next))) {
+ BMIter eiter;
+ BMEdge *e_next;
+
+ BLI_SMALLSTACK_PUSH(vert_visit, v);
+ BM_ELEM_API_FLAG_ENABLE(v, VERT_VISIT);
+
+
+#ifdef USE_FASTPATH_NOFORK
+walk_nofork:
+#endif
+
+ BLI_assert(STACK_SIZE(edge_order) == 0);
+
+ /* check if we're done! */
+ if (v == v_dst) {
+ found = true;
+ goto finally;
+ }
+
+ BM_ITER_ELEM (e_next, &eiter, v, BM_EDGES_OF_VERT) {
+ if ((v->e != e_next) &&
+ (BM_ELEM_API_FLAG_TEST(e_next, EDGE_NET)) &&
+ (bm_edge_flagged_radial_count(e_next) < 2))
+ {
+ BMVert *v_next;
+
+ v_next = BM_edge_other_vert(e_next, v);
+
+#ifdef DEBUG_PRINT
+ /* indent and print */
+ {
+ BMVert *_v = v;
+ do {
+ printf(" ");
+ } while ((_v = BM_edge_other_vert(_v->e, _v)) != v_init);
+ printf("vert %d -> %d (add=%d)\n",
+ BM_elem_index_get(v), BM_elem_index_get(v_next),
+ BM_ELEM_API_FLAG_TEST(v_next, VERT_VISIT) == 0);
+ }
+#endif
+
+ if (!BM_ELEM_API_FLAG_TEST(v_next, VERT_VISIT)) {
+ eo = STACK_PUSH_RET_PTR(edge_order);
+ eo->v = v_next;
+
+ v_next->e = e_next;
+ }
+ }
+ }
+
+#ifdef USE_FASTPATH_NOFORK
+ if (STACK_SIZE(edge_order) == 1) {
+ eo = STACK_POP_PTR(edge_order);
+ v = eo->v;
+
+ goto walk_nofork;
+ }
+#endif
+
+ /* sort by angle if needed */
+ if (STACK_SIZE(edge_order) > 1) {
+ unsigned int j;
+ BMVert *v_prev = BM_edge_other_vert(v->e, v);
+
+ for (j = 0; j < STACK_SIZE(edge_order); j++) {
+ edge_order[j].angle = angle_signed_on_axis_v3v3v3_v3(v_prev->co, v->co, edge_order[j].v->co, face_normal);
+ }
+ qsort(edge_order, STACK_SIZE(edge_order), sizeof(struct VertOrder), BLI_sortutil_cmp_float_reverse);
+ }
+
+ while ((eo = STACK_POP_PTR(edge_order))) {
+ BLI_SMALLSTACK_PUSH(vert_stack_next, eo->v);
+ }
+
+ if (!BLI_SMALLSTACK_IS_EMPTY(vert_stack_next)) {
+ BLI_SMALLSTACK_SWAP(vert_stack, vert_stack_next);
+ }
+ }
+
+
+finally:
+ /* clear flag for next execution */
+ while ((v = BLI_SMALLSTACK_POP(vert_visit))) {
+ BM_ELEM_API_FLAG_DISABLE(v, VERT_VISIT);
+ }
+
+ return found;
+
+#undef USE_FASTPATH_NOFORK
+}
+
+static bool bm_face_split_edgenet_find_loop(
+ BMVert *v_init, const float face_normal[3],
+ /* cache to avoid realloc every time */
+ struct VertOrder *edge_order, const unsigned int edge_order_len,
+ BMVert **r_face_verts, int *r_face_verts_len)
+{
+ BMEdge *e_pair[2];
+ BMVert *v;
+
+ if (!bm_face_split_edgenet_find_loop_pair(v_init, face_normal, e_pair)) {
+ return false;
+ }
+
+ BLI_assert((bm_edge_flagged_radial_count(e_pair[0]) == 1) ||
+ (bm_edge_flagged_radial_count(e_pair[1]) == 1));
+
+ if (bm_face_split_edgenet_find_loop_walk(v_init, face_normal, edge_order, edge_order_len, e_pair)) {
+ unsigned int i = 0;
+
+ r_face_verts[i++] = v_init;
+ v = BM_edge_other_vert(e_pair[1], v_init);
+ do {
+ r_face_verts[i++] = v;
+ } while ((v = BM_edge_other_vert(v->e, v)) != v_init);
+ *r_face_verts_len = i;
+ return (i > 2) ? true : false;
+ }
+ else {
+ return false;
+ }
+}
+
+/**
+ * Splits a face into many smaller faces defined by an edge-net.
+ * handle customdata and degenerate cases.
+ *
+ * - isolated holes or unsupported face configurations, will be ignored.
+ * - customdata calculations aren't efficient
+ * (need to calculate weights for each vert).
+ */
+bool BM_face_split_edgenet(
+ BMesh *bm,
+ BMFace *f, BMEdge **edge_net, const int edge_net_len,
+ BMFace ***r_face_arr, int *r_face_arr_len)
+{
+ /* re-use for new face verts */
+ BMVert **face_verts;
+ int face_verts_len;
+
+ BMFace **face_arr = NULL;
+ BLI_array_declare(face_arr);
+
+ BMVert **vert_queue;
+ STACK_DECLARE(vert_queue);
+ int i;
+
+ struct VertOrder *edge_order;
+ const unsigned int edge_order_len = edge_net_len + 2;
+
+ BMVert *v;
+
+ BMLoop *l_iter, *l_first;
+
+
+ if (!edge_net_len) {
+ if (r_face_arr) {
+ *r_face_arr = NULL;
+ *r_face_arr_len = 0;
+ }
+ return false;
+ }
+
+ /* over-alloc (probably 2-4 is only used in most cases), for the biggest-fan */
+ edge_order = BLI_array_alloca(edge_order, edge_order_len);
+
+ /* use later */
+ face_verts = BLI_array_alloca(face_verts, edge_net_len + f->len);
+
+ vert_queue = BLI_array_alloca(vert_queue, edge_net_len + f->len);
+ STACK_INIT(vert_queue, f->len + edge_net_len);
+
+ BLI_assert(BM_ELEM_API_FLAG_TEST(f, FACE_NET) == 0);
+ BM_ELEM_API_FLAG_ENABLE(f, FACE_NET);
+
+#ifdef DEBUG
+ for (i = 0; i < edge_net_len; i++) {
+ BLI_assert(BM_ELEM_API_FLAG_TEST(edge_net[i], EDGE_NET) == 0);
+ }
+ l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+ do {
+ BLI_assert(BM_ELEM_API_F
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list