[Bf-blender-cvs] [aaa5678] master: BMesh: move BM_face_split_edgenet to its own file
Campbell Barton
noreply at git.blender.org
Wed Dec 9 06:33:04 CET 2015
Commit: aaa56782d3c7b253aac34fcc8e966703bc368fe4
Author: Campbell Barton
Date: Wed Dec 9 16:21:43 2015 +1100
Branches: master
https://developer.blender.org/rBaaa56782d3c7b253aac34fcc8e966703bc368fe4
BMesh: move BM_face_split_edgenet to its own file
Isolate edge-net splitting in preparation for other functions to be added here.
===================================================================
M source/blender/bmesh/CMakeLists.txt
M source/blender/bmesh/bmesh.h
M source/blender/bmesh/intern/bmesh_mods.c
M source/blender/bmesh/intern/bmesh_mods.h
A source/blender/bmesh/intern/bmesh_polygon_edgenet.c
A source/blender/bmesh/intern/bmesh_polygon_edgenet.h
===================================================================
diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt
index 257768b..686b850 100644
--- a/source/blender/bmesh/CMakeLists.txt
+++ b/source/blender/bmesh/CMakeLists.txt
@@ -112,6 +112,8 @@ set(SRC
intern/bmesh_operators_private.h
intern/bmesh_polygon.c
intern/bmesh_polygon.h
+ intern/bmesh_polygon_edgenet.c
+ intern/bmesh_polygon_edgenet.h
intern/bmesh_private.h
intern/bmesh_queries.c
intern/bmesh_queries.h
diff --git a/source/blender/bmesh/bmesh.h b/source/blender/bmesh/bmesh.h
index 78c814a..f29d280 100644
--- a/source/blender/bmesh/bmesh.h
+++ b/source/blender/bmesh/bmesh.h
@@ -244,6 +244,7 @@ extern "C" {
#include "intern/bmesh_mods.h"
#include "intern/bmesh_operators.h"
#include "intern/bmesh_polygon.h"
+#include "intern/bmesh_polygon_edgenet.h"
#include "intern/bmesh_queries.h"
#include "intern/bmesh_walkers.h"
diff --git a/source/blender/bmesh/intern/bmesh_mods.c b/source/blender/bmesh/intern/bmesh_mods.c
index cde231b..84588d9 100644
--- a/source/blender/bmesh/intern/bmesh_mods.c
+++ b/source/blender/bmesh/intern/bmesh_mods.c
@@ -29,22 +29,14 @@
#include "MEM_guardedalloc.h"
-
#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
*
@@ -425,549 +417,6 @@ BMFace *BM_face_split_n(
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;
-
-#ifdef USE_FASTPATH_NOFORK
-walk_nofork:
-#else
- BLI_SMALLSTACK_PUSH(vert_visit, v);
- BM_ELEM_API_FLAG_ENABLE(v, VERT_VISIT);
-#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);
-
-#ifdef USE_FASTPATH_NOFORK
- /* only tag forks */
- BLI_SMALLSTACK_PUSH(vert_visit, v);
- BM_ELEM_API_FLAG_ENABLE(v, VERT_VISIT);
-#endif
- }
-
- 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_v
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list