[Bf-blender-cvs] [b2f7eb5] bmesh-boolean-experiment: Add BM_face_split_edgenet_connect_islands to bmesh_polygon_edgenet.c
Campbell Barton
noreply at git.blender.org
Wed Dec 9 06:45:29 CET 2015
Commit: b2f7eb52be09ec9480c4e35769bdb32fd3f257ba
Author: Campbell Barton
Date: Wed Dec 9 16:38:19 2015 +1100
Branches: bmesh-boolean-experiment
https://developer.blender.org/rBb2f7eb52be09ec9480c4e35769bdb32fd3f257ba
Add BM_face_split_edgenet_connect_islands to bmesh_polygon_edgenet.c
===================================================================
M source/blender/bmesh/intern/bmesh_polygon_edgenet.c
M source/blender/bmesh/intern/bmesh_polygon_edgenet.h
M source/blender/bmesh/tools/bmesh_intersect.c
===================================================================
diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
index 1241614..787a8a4 100644
--- a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
+++ b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
@@ -33,7 +33,9 @@
#include "BLI_alloca.h"
#include "BLI_stackdefines.h"
#include "BLI_linklist_stack.h"
+#include "BLI_sort.h"
#include "BLI_sort_utils.h"
+#include "BLI_kdtree.h"
#include "BKE_customdata.h"
@@ -580,3 +582,359 @@ bool BM_face_split_edgenet(
#undef EDGE_NET
/** \} */
+
+
+/* -------------------------------------------------------------------- */
+/* Face Split Edge-Net Connect Islands */
+
+/** \name BM_face_split_edgenet_connect_islands and helper functions.
+ *
+ * Connect isolated mesh 'islands' so they form legal regions from which we can create faces.
+ *
+ * Intended to be used as a pre-processing step for #BM_face_split_edgenet.
+ *
+ * \{ */
+
+/* Represents isolated edge-links,
+ * each island owns contiguous slices of a vert & edge array. */
+struct GeomIsland {
+ LinkNode node; /* keep first */
+ unsigned int vert_len, edge_len;
+
+ /* Set the following vars once we have >1 groups */
+
+ /* when when an edge in a previous group connects to this one,
+ * so theres no need to create one pointing back. */
+ unsigned int has_prev_edge : 1;
+
+ /* verts in the group which has the lowest & highest values,
+ * the lower vertex is connected to the first edge */
+ struct {
+ BMVert *min, *max;
+ } vert_span;
+};
+
+static int group_min_cmp_fn(const void *p1, const void *p2, void *user_data)
+{
+ struct { unsigned int axis; } *data = user_data;
+ const struct GeomIsland *g1 = *(struct GeomIsland **)p1;
+ const struct GeomIsland *g2 = *(struct GeomIsland **)p2;
+ const float f1 = g1->vert_span.min->co[data->axis];
+ const float f2 = g2->vert_span.min->co[data->axis];
+
+ if (f1 < f2) return -1;
+ if (f1 > f2) return 1;
+ else return 0;
+}
+
+struct GeomIsland_KDTreeTest {
+ unsigned int vert_range[2];
+ BMVert **vert_arr;
+ unsigned int axis;
+
+ /* for each search */
+ float axis_value;
+};
+
+static int kdtree_find_exclude_range_prev_cb(void *user_data, int index, const float co[3], float dist_sq)
+{
+ UNUSED_VARS(co, dist_sq);
+ struct GeomIsland_KDTreeTest *group_test = user_data;
+ return ((index < (int)group_test->vert_range[0] || index >= (int)group_test->vert_range[1]) &&
+ /* allow equality to support degenerate cases (when they're equal) */
+ (group_test->vert_arr[index]->co[group_test->axis] <= group_test->axis_value));
+}
+
+static int kdtree_find_exclude_range_next_cb(void *user_data, int index, const float co[3], float dist_sq)
+{
+ UNUSED_VARS(co, dist_sq);
+ struct GeomIsland_KDTreeTest *group_test = user_data;
+ return ((index < (int)group_test->vert_range[0] || index >= (int)group_test->vert_range[1]) &&
+ /* allow equality to support degenerate cases (when they're equal) */
+ (group_test->vert_arr[index]->co[group_test->axis] >= group_test->axis_value));
+}
+
+/**
+ * For when the edge-net has holes in it-this connects them.
+ */
+bool BM_face_split_edgenet_connect_islands(
+ BMesh *bm,
+ BMFace *f, BMEdge **edge_net_init, const unsigned int edge_net_init_len,
+ BMEdge ***r_edge_net_new, unsigned int *r_edge_net_new_len)
+{
+ /* -------------------------------------------------------------------- */
+ /* This function has 2 main parts.
+ *
+ * - Check if there are any holes.
+ * - Connect the holes with edges (if any are found).
+ *
+ * Keep the first part fast since it will run very often for edge-nets that have no holes.
+ */
+
+ const unsigned int edge_arr_len = (unsigned int)edge_net_init_len + (unsigned int)f->len;
+ BMEdge **edge_arr = BLI_array_alloca(edge_arr, edge_arr_len);
+ bool ok = false;
+
+ memcpy(edge_arr, edge_net_init, sizeof(*edge_arr) * (size_t)edge_net_init_len);
+
+ /* _must_ clear on exit */
+#define EDGE_NOT_IN_STACK BM_ELEM_INTERNAL_TAG
+#define VERT_NOT_IN_STACK BM_ELEM_INTERNAL_TAG
+
+ {
+ unsigned int i = edge_net_init_len;
+ BMLoop *l_iter, *l_first;
+ l_iter = l_first = BM_FACE_FIRST_LOOP(f);
+ do {
+ edge_arr[i++] = l_iter->e;
+ } while ((l_iter = l_iter->next) != l_first);
+ BLI_assert(i == edge_arr_len);
+ }
+
+ for (unsigned int i = 0; i < edge_arr_len; i++) {
+ BM_elem_flag_enable(edge_arr[i], EDGE_NOT_IN_STACK);
+ BM_elem_flag_enable(edge_arr[i]->v1, VERT_NOT_IN_STACK);
+ BM_elem_flag_enable(edge_arr[i]->v2, VERT_NOT_IN_STACK);
+ }
+
+ unsigned int group_arr_len = 0;
+ LinkNode *group_head = NULL;
+ {
+ /* scan 'edge_arr' backwards so the outer face boundary is handled first
+ * (since its likely to be the largest) */
+ unsigned int edge_index = (edge_arr_len - 1);
+ unsigned int edge_in_group_tot = 0;
+
+ BLI_SMALLSTACK_DECLARE(vstack, BMVert *);
+
+ while (true) {
+ LinkNode *edge_links = NULL;
+ unsigned int unique_verts_in_group = 0, unique_edges_in_group = 0;
+
+ /* list of groups */
+ BLI_assert(BM_elem_flag_test(edge_arr[edge_index]->v1, VERT_NOT_IN_STACK));
+ BLI_SMALLSTACK_PUSH(vstack, edge_arr[edge_index]->v1);
+ BM_elem_flag_disable(edge_arr[edge_index]->v1, VERT_NOT_IN_STACK);
+
+ BMVert *v_iter;
+ while ((v_iter = BLI_SMALLSTACK_POP(vstack))) {
+ unique_verts_in_group++;
+
+ BMEdge *e_iter = v_iter->e;
+ do {
+ if (BM_elem_flag_test(e_iter, EDGE_NOT_IN_STACK)) {
+ BM_elem_flag_disable(e_iter, EDGE_NOT_IN_STACK);
+ unique_edges_in_group++;
+
+ BLI_linklist_prepend_alloca(&edge_links, e_iter);
+
+ BMVert *v_other = BM_edge_other_vert(e_iter, v_iter);
+ if (BM_elem_flag_test(v_other, VERT_NOT_IN_STACK)) {
+ BLI_SMALLSTACK_PUSH(vstack, v_other);
+ BM_elem_flag_disable(v_other, VERT_NOT_IN_STACK);
+ }
+ }
+ } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_iter)) != v_iter->e);
+ }
+
+ struct GeomIsland *g = alloca(sizeof(*g));
+ g->vert_len = unique_verts_in_group;
+ g->edge_len = unique_edges_in_group;
+ edge_in_group_tot += unique_edges_in_group;
+
+ BLI_linklist_prepend_nlink(&group_head, edge_links, (LinkNode *)g);
+
+ group_arr_len++;
+
+ if (edge_in_group_tot == edge_arr_len) {
+ break;
+ }
+
+ /* skip edges in the stack */
+ while (BM_elem_flag_test(edge_arr[edge_index], EDGE_NOT_IN_STACK) == false) {
+ BLI_assert(edge_index != 0);
+ edge_index--;
+ }
+ }
+ }
+
+ /* single group - no holes */
+ if (group_arr_len == 1) {
+ goto finally;
+ }
+
+
+ /* -------------------------------------------------------------------- */
+ /* Previous checks need to be kept fast, since they will run very often,
+ * now we know there are holes, so calculate a spatial lookup info and
+ * other per-group data.
+ */
+
+#define VERT_IN_KDTREE BM_ELEM_INTERNAL_TAG
+
+ struct GeomIsland **group_arr = BLI_array_alloca(group_arr, group_arr_len);
+ const unsigned int axis = (unsigned int)axis_dominant_v3_ortho_single(f->no);
+ unsigned int vert_arr_len = 0;
+ /* sort groups by lowest value vertex */
+ {
+ /* fill 'groups_arr' in reverse order so the boundary face is first */
+ struct GeomIsland **group_arr_p = &group_arr[group_arr_len];
+
+ for (struct GeomIsland *g = (void *)group_head; g; g = (struct GeomIsland *)g->node.next) {
+ LinkNode *edge_links = g->node.link;
+
+ /* init with *any* different verts */
+ g->vert_span.min = ((BMEdge *)edge_links->link)->v1;
+ g->vert_span.max = ((BMEdge *)edge_links->link)->v2;
+
+ do {
+ BMEdge *e = edge_links->link;
+ BLI_assert(e->head.htype == BM_EDGE);
+
+ for (int j = 0; j < 2; j++) {
+ BMVert *v_iter = (&e->v1)[j];
+ BLI_assert(v_iter->head.htype == BM_VERT);
+ const float axis_value = v_iter->co[axis];
+
+ if (axis_value < g->vert_span.min->co[axis]) {
+ g->vert_span.min = v_iter;
+ }
+ if (axis_value > g->vert_span.max->co[axis]) {
+ g->vert_span.max = v_iter;
+ }
+ }
+ } while ((edge_links = edge_links->next));
+
+ g->has_prev_edge = false;
+
+ vert_arr_len += g->vert_len;
+
+ *(--group_arr_p) = g;
+ }
+ }
+
+ {
+ struct { unsigned int axis; } data = {axis};
+ BLI_qsort_r(group_arr, group_arr_len, sizeof(*group_arr), group_min_cmp_fn, &data);
+ }
+
+ /* we don't know how many unique verts there are connecting the edges, so over-alloc */
+ BMVert **vert_arr = BLI_array_alloca(vert_arr, vert_arr_len);
+ /* map vertex -> group index */
+ unsigned int *verts_group_table = BLI_array_alloca(verts_group_table, vert_arr_len);
+
+ KDTree *tree = BLI_kdtree_new(vert_arr_len);
+
+ {
+ int v_index = 0; /* global vert index */
+ for (unsigned int g_index = 0; g_index < group_arr_len; g_index++) {
+ /* fill the kdtree */
+ LinkNode *edge_links = group_arr[g_index]->node.link;
+ do {
+ BMEdge *e = edge_links->link;
+ for (int j = 0; j < 2; j++) {
+ BMVert *v_iter = (&e->v1)[j];
+ if (!BM_elem_flag_test(v_iter, VERT_IN_KDTREE)) {
+ BM_elem_flag_enable(v_iter, VERT_IN_KDTREE);
+ BLI_kdtree_insert(tree, v_index, v_iter->co);
+ vert_arr[v_index] = v_iter;
+ verts_group_table[v_index] = g_index;
+ v_index++;
+ }
+ }
+ } while ((edge_links = edge_links->next));
+ }
+ }
+
+ BLI_kdtree_balance(tree);
+
+
+ /* Create connections between groups */
+
+ /* may be an over-alloc, but not by much */
+ unsigned int edge_net_new_len = (unsigned int)edge_net_init_len + ((group_arr_len - 1) * 2);
+ BMEdge **edge_net_new = MEM_mallocN(sizeof(*edge_net_new) * edge_net_new_len, __func__);
+ memcpy(edge_net_new, edge_net_init, sizeof(*edge_net_new) * (size_t)edge_net_init_len);
+
+ {
+ unsigned int edge_net_new_index = edge_net_init_len;
+ /* start-end of the verts in the current group */
+ struct GeomIsland_KDTreeTest group_test;
+
+ group_test.vert_range[0] = 0;
+ group_test.vert_range[1] = group_arr[0]->vert_len;
+ group_test.vert_arr = vert_arr;
+ group_test.axis = axis;
+
+ for (unsigned int g_index = 1; g_index < group_arr_len; g_index++) {
+ struct GeomIsland *g = group_arr[g_index];
+
+ /* the range of verts this group uses in 'verts_arr' (not uncluding the last index) */
+ group_test.vert_range[0] = group_test.vert_range[1];
+ group_test.vert_ra
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list