[Bf-blender-cvs] [961ec8c] bmesh-boolean-experiment: Improve hole-detection
Campbell Barton
noreply at git.blender.org
Wed Dec 9 04:34:05 CET 2015
Commit: 961ec8c6aebe30e37d5596c33f29305ad0a9d2a9
Author: Campbell Barton
Date: Wed Dec 9 14:13:18 2015 +1100
Branches: bmesh-boolean-experiment
https://developer.blender.org/rB961ec8c6aebe30e37d5596c33f29305ad0a9d2a9
Improve hole-detection
- use vert-stack instead of edges for walking edge-links (avoid a nested loop).
- count verts as well as edges when walking over edge-links.
- don't over-alloc vert arrays (was using total edges * 2)
- use the simpler linklist prepend since order if edges is no longer relied on.
- order edges/group walking for minimal sorting.
- use the dominant axis to order verts instead of abusing the vertex normal.
===================================================================
M source/blender/bmesh/tools/bmesh_intersect.c
===================================================================
diff --git a/source/blender/bmesh/tools/bmesh_intersect.c b/source/blender/bmesh/tools/bmesh_intersect.c
index 8e7abce..e3a1ac7 100644
--- a/source/blender/bmesh/tools/bmesh_intersect.c
+++ b/source/blender/bmesh/tools/bmesh_intersect.c
@@ -97,12 +97,11 @@ extern void bl_debug_color_set(const unsigned int col);
#ifdef USE_HOLE_FILL
-/* abuse vertex normals, these will be recalculated anyway */
-#define VERT_VALUE(v) ((v)->no[0])
-
-struct GroupNode {
+/* Represents isolated edge-links,
+ * each island owns contiguous slices of a vert & edge array. */
+struct GeomIsland {
LinkNode node; /* keep first */
- unsigned int edge_len, vert_len;
+ unsigned int vert_len, edge_len;
/* Set the following vars once we have >1 groups */
@@ -117,40 +116,44 @@ struct GroupNode {
} vert_span;
};
-static int group_min_cmp_fn(const void *p1, const void *p2)
+static int group_min_cmp_fn(const void *p1, const void *p2, void *user_data)
{
- const struct GroupNode *g1 = *(struct GroupNode **)p1;
- const struct GroupNode *g2 = *(struct GroupNode **)p2;
- const float f1 = VERT_VALUE(g1->vert_span.min);
- const float f2 = VERT_VALUE(g2->vert_span.min);
+ 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 EdgeGroup_KDTreeTest {
+struct GeomIsland_KDTreeTest {
unsigned int vert_range[2];
- BMVert **verts_arr;
- float value;
+ 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 EdgeGroup_KDTreeTest *group_test = user_data;
+ 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) */
- (VERT_VALUE(group_test->verts_arr[index]) <= group_test->value));
+ (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 EdgeGroup_KDTreeTest *group_test = user_data;
+ 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) */
- (VERT_VALUE(group_test->verts_arr[index]) >= group_test->value));
+ (group_test->vert_arr[index]->co[group_test->axis] >= group_test->axis_value));
}
/**
@@ -180,10 +183,8 @@ static bool bm_face_split_edgenet_prepare_holes(
memcpy(edge_arr, edge_net_init, sizeof(*edge_arr) * (size_t)edge_net_init_len);
/* _must_ clear on exit */
-#define VERT_NOT_IN_KDTREE BM_ELEM_INTERNAL_TAG
#define EDGE_NOT_IN_STACK BM_ELEM_INTERNAL_TAG
- /* XXX this is wrong, we need some better way to know if an edge is in the net */
-#define EDGE_IS_NET BM_ELEM_SEAM
+#define VERT_NOT_IN_STACK BM_ELEM_INTERNAL_TAG
{
unsigned int i = edge_net_init_len;
@@ -196,58 +197,59 @@ static bool bm_face_split_edgenet_prepare_holes(
}
for (unsigned int i = 0; i < edge_arr_len; i++) {
- BM_elem_flag_enable(edge_arr[i], EDGE_IS_NET);
BM_elem_flag_enable(edge_arr[i], EDGE_NOT_IN_STACK);
- BM_elem_flag_enable(edge_arr[i]->v1, VERT_NOT_IN_KDTREE);
- BM_elem_flag_enable(edge_arr[i]->v2, VERT_NOT_IN_KDTREE);
+ BM_elem_flag_enable(edge_arr[i]->v1, VERT_NOT_IN_STACK);
+ BM_elem_flag_enable(edge_arr[i]->v2, VERT_NOT_IN_STACK);
}
- LinkNode *groups;
- unsigned int groups_len = 0;
+ unsigned int group_arr_len = 0;
+ LinkNode *group_head = NULL;
{
- LinkNodePair groups_np = {NULL, NULL};
- unsigned int edge_index = 0;
+ /* 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(estack, BMEdge *);
+ BLI_SMALLSTACK_DECLARE(vstack, BMVert *);
while (true) {
- LinkNodePair g_np = {NULL, NULL};
- unsigned int g_len = 0;
+ LinkNode *edge_links = NULL;
+ unsigned int unique_verts_in_group = 0, unique_edges_in_group = 0;
/* list of groups */
- BLI_SMALLSTACK_PUSH(estack, edge_arr[edge_index]);
- BM_elem_flag_disable(edge_arr[edge_index], EDGE_NOT_IN_STACK);
-
- BMEdge *e;
- while ((e = BLI_SMALLSTACK_POP(estack))) {
- BLI_linklist_append_alloca(&g_np, e);
- g_len++;
-
- edge_in_group_tot++;
-
- for (int i = 0; i < 2; i++) {
- BMVert *v_iter = (&e->v1)[i];
- BMEdge *e_iter = v_iter->e;
- do {
- if ((e_iter != e) &&
- (BM_elem_flag_test(e_iter, EDGE_NOT_IN_STACK)))
- {
- BLI_SMALLSTACK_PUSH(estack, e_iter);
- BM_elem_flag_disable(e_iter, EDGE_NOT_IN_STACK);
+ 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);
- }
+ }
+ } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_iter)) != v_iter->e);
}
- struct GroupNode *group_base = alloca(sizeof(*group_base));
- group_base->edge_len = g_len;
+ 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;
- group_base->has_prev_edge = false;
+ BLI_linklist_prepend_nlink(&group_head, edge_links, (LinkNode *)g);
- BLI_linklist_append_nlink(&groups_np, g_np.list, (LinkNode *)group_base);
-
- groups_len++;
+ group_arr_len++;
if (edge_in_group_tot == edge_arr_len) {
break;
@@ -255,97 +257,98 @@ static bool bm_face_split_edgenet_prepare_holes(
/* skip edges in the stack */
while (BM_elem_flag_test(edge_arr[edge_index], EDGE_NOT_IN_STACK) == false) {
- edge_index++;
+ BLI_assert(edge_index != 0);
+ edge_index--;
}
}
-
- groups = groups_np.list;
}
/* single group - no holes */
- if (groups_len == 1) {
+ if (group_arr_len == 1) {
goto finally;
}
- /* its not important which axis we sort along (though it does define the path direction along the face),
- * just that its from one side to another (across the face)
- * so the first group is always the outer-most */
- float f_ortho_dir[3];
- ortho_v3_v3(f_ortho_dir, f->no);
- struct GroupNode **groups_arr = BLI_array_alloca(groups_arr, groups_len);
+ /* -------------------------------------------------------------------- */
+ /* 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 */
{
- struct GroupNode *group_base = (void *)groups;
- for (unsigned int group_index = 0; group_index < groups_len; group_index++, group_base = (void *)group_base->node.next) {
- LinkNode *g = group_base->node.link;
+ /* fill 'groups_arr' in reverse order so the boundary face is first */
+ struct GeomIsland **group_arr_p = &group_arr[group_arr_len];
- {
- BMEdge *e = g->link;
- group_base->vert_span.min = e->v1;
- group_base->vert_span.max = e->v2;
- }
+ 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 = g->link;
+ 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 value = dot_v3v3(f_ortho_dir, v_iter->co);
- VERT_VALUE(v_iter) = value;
+ const float axis_value = v_iter->co[axis];
- if (value < VERT_VALUE(group_base->vert_span.min)) {
- group_base->vert_span.min = v_iter;
+ if (axis_value < g->vert_span.min->co[axis]) {
+ g->vert_span.min = v_iter;
}
- if (value > VERT_VALUE(group_base->vert_span.max)) {
- group_base->vert_span.max = v_iter;
+ if (axis_value > g->vert_span.max->co[axis]) {
+ g->vert_span.max = v_iter;
}
}
- } while ((g = g->next));
+ } while ((edge_links = edge_links->next));
+
+ g->has_prev_edge = false;
- group_base->has_prev_edge = false;
+ vert_arr_len += g->vert_len;
- groups_arr[group_index] = group_base;
+ *(--group_arr_p) = g;
}
}
- qsort(groups_arr, groups_len, sizeof(*groups_arr), group_min_cmp_fn);
-
-
- /* -------------------------------------------------------------------- */
- /* 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.
- */
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list