BMesh: support connecting single-edge island links
authorCampbell Barton <ideasman42@gmail.com>
Wed, 16 Dec 2015 18:02:39 +0000 (05:02 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Wed, 16 Dec 2015 18:13:57 +0000 (05:13 +1100)
Handle these cases by temporarily disconnecting the single links to ensure isolated islands,
then link back up after.

source/blender/bmesh/intern/bmesh_polygon_edgenet.c
source/blender/bmesh/intern/bmesh_polygon_edgenet.h
source/blender/bmesh/tools/bmesh_intersect.c
source/blender/editors/mesh/editmesh_intersect.c
source/blender/editors/mesh/editmesh_knife.c

index 420fb26ca08a18e8251598c786513279a9343b9a..85efffb82d302213c9197230fdde38a96717239d 100644 (file)
@@ -606,6 +606,10 @@ bool BM_face_split_edgenet(
  *
  * \{ */
 
+
+#define USE_PARTIAL_CONNECT
+
+
 #define VERT_IS_VALID BM_ELEM_INTERNAL_TAG
 
 /* can be X or Y */
@@ -685,8 +689,10 @@ static void bvhtree_test_edges_isect_2d_vert_cb(
        if (edge_isect_verts_point_2d(e, data->v_origin, data->v_other, co_isect)) {
                const float t = line_point_factor_v2(co_isect, data->v_origin->co, data->v_other->co);
                const float dist_new = data->dist_orig * t;
-               /* avoid float precision issues, possible this is greater */
-               if (LIKELY(dist_new < hit->dist)) {
+               /* avoid float precision issues, possible this is greater,
+                * check anove zero to allow some overlap
+                * (and needed for partial-connect which will overlap vertices) */
+               if (LIKELY((dist_new < hit->dist) && (dist_new > 0.0f))) {
                        /* v1/v2 will both be in the same group */
                        if (v1_index <  (int)data->vert_range[0] ||
                            v1_index >= (int)data->vert_range[1])
@@ -707,8 +713,10 @@ static void bvhtree_test_edges_isect_2d_ray_cb(
        /* direction is normalized, so this will be the distance */
        float dist_new;
        if (isect_ray_seg_v2(data->v_origin->co, ray->direction, e->v1->co, e->v2->co, &dist_new, NULL)) {
-               /* avoid float precision issues, possible this is greater */
-               if (LIKELY(dist_new < hit->dist)) {
+               /* avoid float precision issues, possible this is greater,
+                * check anove zero to allow some overlap
+                * (and needed for partial-connect which will overlap vertices) */
+               if (LIKELY(dist_new < hit->dist && (dist_new > 0.0f))) {
                        if (e->v1 != data->v_origin && e->v2 != data->v_origin) {
                                const int v1_index = BM_elem_index_get(e->v1);
                                /* v1/v2 will both be in the same group */
@@ -909,15 +917,188 @@ static int bm_face_split_edgenet_find_connection(
        return v_other ? BM_elem_index_get(v_other) : -1;
 }
 
+
+/**
+ * Support for connecting islands that have single-edge connections.
+ * This options is not very optimal (however its not needed for booleans either).
+ */
+#ifdef USE_PARTIAL_CONNECT
+
+/**
+ * Split vertices which are part of a partial connection
+ * (only a single vertex connecting an island).
+ *
+ * \note All edges and vertices must have their #BM_ELEM_INTERNAL_TAG flag enabled.
+ * This function leaves all the flags set as well.
+ *
+ */
+static BMVert *bm_face_split_edgenet_partial_connect(BMesh *bm, BMVert *v_delimit)
+{
+       /* -------------------------------------------------------------------- */
+       /* Initial check that we may be a delimiting vert (keep this fast) */
+
+       /* initial check - see if we have 3+ flagged edges attached to 'v_delimit'
+        * if not, we can early exit */
+       LinkNode *e_delimit_list = NULL;
+       unsigned int e_delimit_list_len = 0;
+
+#define EDGE_NOT_IN_STACK  BM_ELEM_INTERNAL_TAG
+#define VERT_NOT_IN_STACK  BM_ELEM_INTERNAL_TAG
+
+#define FOREACH_VERT_EDGE(v_, e_, body_) { \
+       BMEdge *e_ = v_->e; \
+       do { body_ } while ((e_ = BM_DISK_EDGE_NEXT(e_, v_)) != v_->e); \
+} ((void)0)
+
+       /* start with face edges, since we need to split away wire-only edges */
+       BMEdge *e_face_init = NULL;
+
+       FOREACH_VERT_EDGE(v_delimit, e_iter, {
+               if (BM_elem_flag_test(e_iter, EDGE_NOT_IN_STACK)) {
+                       BLI_assert(BM_elem_flag_test(BM_edge_other_vert(e_iter, v_delimit), VERT_NOT_IN_STACK));
+                       BLI_linklist_prepend_alloca(&e_delimit_list, e_iter);
+                       e_delimit_list_len++;
+                       if (e_iter->l != NULL) {
+                               e_face_init = e_iter;
+                       }
+               }
+       });
+
+       /* skip typical edge-chain verts */
+       if (LIKELY(e_delimit_list_len <= 2)) {
+               return NULL;
+       }
+
+
+       /* -------------------------------------------------------------------- */
+       /* Complicated stuff starts now! */
+
+
+       /* Store connected vertices for restoring the flag */
+       LinkNode *vert_stack = NULL;
+       BLI_linklist_prepend_alloca(&vert_stack, v_delimit);
+       BM_elem_flag_disable(v_delimit, VERT_NOT_IN_STACK);
+
+       /* Walk the net... */
+       {
+               BLI_SMALLSTACK_DECLARE(search, BMVert *);
+               BMVert *v_other = BM_edge_other_vert(e_face_init ? e_face_init : v_delimit->e, v_delimit);
+
+               BLI_SMALLSTACK_PUSH(search, v_other);
+               BM_elem_flag_disable(v_other, VERT_NOT_IN_STACK);
+
+               while ((v_other = BLI_SMALLSTACK_POP(search))) {
+                       BLI_assert(BM_elem_flag_test(v_other, VERT_NOT_IN_STACK) == false);
+                       BLI_linklist_prepend_alloca(&vert_stack, v_other);
+                       BMEdge *e_iter = v_other->e;
+                       do {
+                               BMVert *v_step = BM_edge_other_vert(e_iter, v_other);
+                               if (BM_elem_flag_test(e_iter, EDGE_NOT_IN_STACK)) {
+                                       if (BM_elem_flag_test(v_step, VERT_NOT_IN_STACK)) {
+                                               BM_elem_flag_disable(v_step, VERT_NOT_IN_STACK);
+                                               BLI_SMALLSTACK_PUSH(search, v_step);
+                                       }
+                               }
+                       } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v_other)) != v_other->e);
+               }
+       }
+
+       /* Detect if this is a delimiter by checking if we didn't walk any of edges connected to 'v_delimit' */
+       bool is_delimit = false;
+       FOREACH_VERT_EDGE(v_delimit, e_iter, {
+               BMVert *v_step = BM_edge_other_vert(e_iter, v_delimit);
+               if (BM_elem_flag_test(v_step, VERT_NOT_IN_STACK)) {
+                       is_delimit = true;  /* if one vertex is valid - we have a mix */
+               }
+               else {
+                       /* match the vertex flag (only for edges around 'v_delimit') */
+                       BM_elem_flag_disable(e_iter, EDGE_NOT_IN_STACK);
+               }
+       });
+
+#undef FOREACH_VERT_EDGE
+
+       /* Execute the split */
+       BMVert *v_split = NULL;
+       if (is_delimit) {
+               v_split = BM_vert_create(bm, v_delimit->co, NULL, 0);
+               BM_vert_separate_wire_hflag(bm, v_split, v_delimit, EDGE_NOT_IN_STACK);
+               BM_elem_flag_enable(v_split, VERT_NOT_IN_STACK);
+
+               BLI_assert(v_delimit->e != NULL);
+               BLI_assert(v_split->e != NULL);
+       }
+
+       /* Restore flags */
+       do {
+               BM_elem_flag_enable((BMVert *)vert_stack->link, VERT_NOT_IN_STACK);
+       } while ((vert_stack = vert_stack->next));
+
+       do {
+               BM_elem_flag_enable((BMEdge *)e_delimit_list->link, EDGE_NOT_IN_STACK);
+       } while ((e_delimit_list = e_delimit_list->next));
+
+#undef EDGE_NOT_IN_STACK
+#undef VERT_NOT_IN_STACK
+
+       return v_split;
+}
+
+
+/**
+ * Check if creating a connection between 2 edges will later overlap when splicing vertices back together.
+ */
+static bool bm_vert_partial_connect_check_overlap(
+        BMVert **vert_arr, const int *remap,
+        const int v_a_index, const int v_b_index)
+{
+       int v_a_remap = remap[v_a_index];
+       int v_b_remap = remap[v_b_index];
+
+       if (v_a_remap == -1 && v_b_remap == -1) {
+               return false;
+       }
+       else if (UNLIKELY((v_a_remap == v_b_index) || (v_b_remap == v_a_index))) {
+               /* connected to eachother */
+               return true;
+       }
+       else {
+               /* check that creating an edge here will overlap an existing edge
+                * once adjacent vertices are spliced together. */
+               const int v_pair[2] = {v_a_index, v_b_index};
+               for (int i = 0; i < 2; i++) {
+                       BMVert *v = vert_arr[v_pair[i]];
+                       BMEdge *e_iter = v->e;
+                       do {
+                               BMVert *v_step = BM_edge_other_vert(e_iter, v);
+                               const int v_step_index = BM_elem_index_get(v_step);
+                               if (remap[v_step_index] == v_pair[!i]) {
+                                       return true;
+                               }
+                       } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != v->e);
+               }
+       }
+
+       return false;
+}
+
+
+#endif  /* USE_PARTIAL_CONNECT */
+
+
+
 /**
  * For when the edge-net has holes in it-this connects them.
  *
+ * \param use_partial_connect: Support for handling islands connected by only a single edge,
+ * \note that this is quite slow so avoid using where possible.
  * \param mem_arena: Avoids many small allocs & should be cleared after each use.
  * take care since \a r_edge_net_new is stored in \a r_edge_net_new.
  */
 bool BM_face_split_edgenet_connect_islands(
         BMesh *bm,
         BMFace *f, BMEdge **edge_net_init, const unsigned int edge_net_init_len,
+        bool use_partial_connect,
         MemArena *mem_arena,
         BMEdge ***r_edge_net_new, unsigned int *r_edge_net_new_len)
 {
@@ -959,6 +1140,48 @@ bool BM_face_split_edgenet_connect_islands(
                BM_elem_flag_enable(edge_arr[i]->v2, VERT_NOT_IN_STACK);
        }
 
+
+
+#ifdef USE_PARTIAL_CONNECT
+       /* Split-out delimiting vertices */
+       struct TempVertPair {
+               struct TempVertPair *next;
+               BMVert *v_temp;
+               BMVert *v_orig;
+       };
+
+       struct {
+               struct TempVertPair *list;
+               unsigned int len;
+               int *remap;  /* temp -> orig mapping */
+       } temp_vert_pairs = {NULL};
+
+       if (use_partial_connect) {
+               for (unsigned int i = 0; i < edge_net_init_len; i++) {
+                       for (unsigned j = 0; j < 2; j++) {
+                               BMVert *v_delimit = (&edge_arr[i]->v1)[j];
+                               BMVert *v_other;
+
+                               /* note, remapping will _never_ map a vertex to an already mapped vertex */
+                               while (UNLIKELY((v_other = bm_face_split_edgenet_partial_connect(bm, v_delimit)))) {
+                                       struct TempVertPair *tvp = BLI_memarena_alloc(mem_arena, sizeof(*tvp));
+                                       tvp->next = temp_vert_pairs.list;
+                                       tvp->v_orig = v_delimit;
+                                       tvp->v_temp = v_other;
+                                       temp_vert_pairs.list = tvp;
+                                       temp_vert_pairs.len++;
+                               }
+                       }
+               }
+
+               if (temp_vert_pairs.len == 0) {
+                       use_partial_connect = false;
+               }
+       }
+#endif  /* USE_PARTIAL_CONNECT */
+
+
+
        unsigned int group_arr_len = 0;
        LinkNode *group_head = NULL;
        {
@@ -1150,6 +1373,23 @@ bool BM_face_split_edgenet_connect_islands(
        }
        BLI_bvhtree_balance(bvhtree);
 
+
+
+#ifdef USE_PARTIAL_CONNECT
+       if (use_partial_connect) {
+               /* needs to be done once the vertex indices have been written into */
+               temp_vert_pairs.remap = BLI_memarena_alloc(mem_arena, sizeof(*temp_vert_pairs.remap) * vert_arr_len);
+               copy_vn_i(temp_vert_pairs.remap, vert_arr_len, -1);
+
+               struct TempVertPair *tvp = temp_vert_pairs.list;
+               do {
+                       temp_vert_pairs.remap[BM_elem_index_get(tvp->v_temp)] = BM_elem_index_get(tvp->v_orig);
+               } while ((tvp = tvp->next));
+       }
+#endif  /* USE_PARTIAL_CONNECT */
+
+
+
        /* Create connections between groups */
 
        /* may be an over-alloc, but not by much */
@@ -1195,11 +1435,19 @@ bool BM_face_split_edgenet_connect_islands(
 
                                /* only for degenerate geometry */
                                if (index_other != -1) {
-                                       BMVert *v_end = vert_arr[index_other];
+#ifdef USE_PARTIAL_CONNECT
+                                       if ((use_partial_connect == false) ||
+                                           (bm_vert_partial_connect_check_overlap(
+                                                vert_arr, temp_vert_pairs.remap,
+                                                BM_elem_index_get(v_origin), index_other) == false))
+#endif
+                                       {
+                                               BMVert *v_end = vert_arr[index_other];
 
-                                       edge_net_new[edge_net_new_index] = BM_edge_create(bm, v_origin, v_end, NULL, 0);
-                                       edge_net_new_index++;
-                                       args.edge_arr_new_len++;
+                                               edge_net_new[edge_net_new_index] = BM_edge_create(bm, v_origin, v_end, NULL, 0);
+                                               edge_net_new_index++;
+                                               args.edge_arr_new_len++;
+                                       }
                                }
                        }
 
@@ -1211,11 +1459,18 @@ bool BM_face_split_edgenet_connect_islands(
 
                                /* only for degenerate geometry */
                                if (index_other != -1) {
-                                       BMVert *v_end = vert_arr[index_other];
-
-                                       edge_net_new[edge_net_new_index] = BM_edge_create(bm, v_origin, v_end, NULL, 0);
-                                       edge_net_new_index++;
-                                       args.edge_arr_new_len++;
+#ifdef USE_PARTIAL_CONNECT
+                                       if ((use_partial_connect == false) ||
+                                           (bm_vert_partial_connect_check_overlap(
+                                                vert_arr, temp_vert_pairs.remap,
+                                                BM_elem_index_get(v_origin), index_other) == false))
+#endif
+                                       {
+                                               BMVert *v_end = vert_arr[index_other];
+                                               edge_net_new[edge_net_new_index] = BM_edge_create(bm, v_origin, v_end, NULL, 0);
+                                               edge_net_new_index++;
+                                               args.edge_arr_new_len++;
+                                       }
 
                                        /* tell the 'next' group it doesn't need to create its own back-link */
                                        unsigned int g_index_other = verts_group_table[index_other];
@@ -1239,6 +1494,21 @@ bool BM_face_split_edgenet_connect_islands(
        }
 
 finally:
+
+#ifdef USE_PARTIAL_CONNECT
+       /* don't free 'vert_temp_pair_list', its part of the arena */
+       if (use_partial_connect) {
+               struct TempVertPair *tvp = temp_vert_pairs.list;
+               do {
+                       /* we must _never_ create connections here
+                        * (inface the islands can't have a connection at all) */
+                       BLI_assert(BM_edge_exists(tvp->v_orig, tvp->v_temp) == NULL);
+                       BM_vert_splice(bm, tvp->v_orig, tvp->v_temp);
+               } while ((tvp = tvp->next));
+       }
+#endif
+
+
        for (unsigned int i = 0; i < edge_arr_len; i++) {
                BM_elem_flag_disable(edge_arr[i], EDGE_NOT_IN_STACK);
                BM_elem_flag_disable(edge_arr[i]->v1, VERT_NOT_IN_STACK);
index b6642319fe6fd1bf820026098bad5d058108b2e3..72ae7695f0f8da61fa8eb21ee3399bf0afe558c6 100644 (file)
@@ -33,8 +33,9 @@ bool BM_face_split_edgenet(
 bool BM_face_split_edgenet_connect_islands(
         BMesh *bm,
         BMFace *f, BMEdge **edge_net_init, const unsigned int edge_net_init_len,
+        bool use_partial_connect,
         struct MemArena *arena,
         BMEdge ***r_edge_net_new, unsigned int *r_edge_net_new_len)
-ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3, 5, 6, 7);
+ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1, 2, 3, 6, 7, 8);
 
 #endif  /* __BMESH_POLYGON_EDGENET_H__ */
index 0d5e0a8c58427176649f0d17cab4366fa049d6f5..abcc4b132eaaea03a5efcbbc3b7a2f46d35bd00c 100644 (file)
@@ -264,6 +264,7 @@ static void face_edges_split(
                if (BM_face_split_edgenet_connect_islands(
                        bm, f,
                        edge_arr, edge_arr_len,
+                       false,
                        mem_arena_edgenet,
                        &edge_arr_holes, &edge_arr_holes_len))
                {
index b60df2e7e44e3d570f64a9277f7a311b19f622c6..86d1b9b8644a85d4a1accd6915acfcd0ace787f8 100644 (file)
@@ -423,6 +423,7 @@ static void bm_face_split_by_edges_island_connect(
                if (BM_face_split_edgenet_connect_islands(
                        bm, f,
                        edge_arr, e_link_len,
+                       true,
                        mem_arena_edgenet,
                        &edge_arr_holes, &edge_arr_holes_len))
                {
index d9ee340a43bf6192b0853f8c262321a3bbf295cc..4192b9f69d23d84f2404841d96309b9b10e0222c 100644 (file)
@@ -2332,6 +2332,7 @@ static void knife_make_face_cuts(KnifeTool_OpData *kcd, BMFace *f, ListBase *kfe
                if (BM_face_split_edgenet_connect_islands(
                        bm, f,
                        edge_array, edge_array_len,
+                       true,
                        kcd->edgenet.arena,
                        &edge_array_holes, &edge_array_holes_len))
                {