[Bf-blender-cvs] [8574b01] compositor-2016: Fix T47257: bevel crash when there are internal faces.
Howard Trickey
noreply at git.blender.org
Wed Jun 8 21:50:09 CEST 2016
Commit: 8574b01929bc6238af34c9a7edafa1616333a394
Author: Howard Trickey
Date: Wed May 25 08:48:46 2016 -0400
Branches: compositor-2016
https://developer.blender.org/rB8574b01929bc6238af34c9a7edafa1616333a394
Fix T47257: bevel crash when there are internal faces.
Bevel had assumed that when rebuilding a face that touches
a vertex with beveled edges, the edges of the face at that vertex
would be adjacent in internal order. That is not necessarily true
if there are edges with more than two faces attached.
We could just prohibit beveling any edges that touch a vertex
where this happens (we already don't bevel non-manifold edges)
but the use case in the model of T47257 seems reasonable.
Also had to fix the edge-ordering code, and the face reconstruction
code to take care of cases where the face normal may not be as expected.
===================================================================
M source/blender/bmesh/tools/bmesh_bevel.c
===================================================================
diff --git a/source/blender/bmesh/tools/bmesh_bevel.c b/source/blender/bmesh/tools/bmesh_bevel.c
index 5a7788c..f7e3622 100644
--- a/source/blender/bmesh/tools/bmesh_bevel.c
+++ b/source/blender/bmesh/tools/bmesh_bevel.c
@@ -345,6 +345,36 @@ static EdgeHalf *next_bev(BevVert *bv, EdgeHalf *from_e)
return NULL;
}
+/* return count of edges between e1 and e2 when going around bv CCW */
+static int count_ccw_edges_between(EdgeHalf *e1, EdgeHalf *e2)
+{
+ int cnt = 0;
+ EdgeHalf *e = e1;
+
+ do {
+ if (e == e2)
+ break;
+ e = e->next;
+ cnt++;
+ } while (e != e1);
+ return cnt;
+}
+
+/* Assume bme1 and bme2 both share some vert. Do they share a face?
+ * If they share a face then there is some loop around bme1 that is in a face
+ * where the next or previous edge in the face must be bme2. */
+static bool edges_face_connected_at_vert(BMEdge *bme1, BMEdge *bme2)
+{
+ BMLoop *l;
+ BMIter iter;
+
+ BM_ITER_ELEM(l, &iter, bme1, BM_LOOPS_OF_EDGE) {
+ if (l->prev->e == bme2 || l->next->e == bme2)
+ return true;
+ }
+ return false;
+}
+
/* Return a good representative face (for materials, etc.) for faces
* created around/near BoundVert v.
* Sometimes care about a second choice, if there is one.
@@ -1557,7 +1587,7 @@ static void build_boundary_vertex_only(BevelParams *bp, BevVert *bv, bool constr
if (construct) {
v = add_new_bound_vert(bp->mem_arena, vm, co);
v->efirst = v->elast = e;
- e->leftv = v;
+ e->leftv = e->rightv = v;
}
else {
adjust_bound_vert(e->leftv, co);
@@ -1637,7 +1667,7 @@ static void build_boundary_terminal_edge(BevelParams *bp, BevVert *bv, EdgeHalf
v->efirst = e->prev;
v->elast = v->ebev = e;
e->leftv = v;
- e->prev->leftv = v;
+ e->prev->leftv = e->prev->rightv = v;
}
else {
adjust_bound_vert(e->leftv, co);
@@ -1648,7 +1678,7 @@ static void build_boundary_terminal_edge(BevelParams *bp, BevVert *bv, EdgeHalf
v = add_new_bound_vert(mem_arena, vm, co);
v->efirst = e->prev;
v->elast = e;
- e->leftv = v;
+ e->leftv = e->rightv = v;
e->prev->rightv = v;
}
else {
@@ -1661,7 +1691,7 @@ static void build_boundary_terminal_edge(BevelParams *bp, BevVert *bv, EdgeHalf
if (construct) {
v = add_new_bound_vert(mem_arena, vm, co);
v->efirst = v->elast = e;
- e->leftv = v;
+ e->leftv = e->rightv = v;
}
else {
adjust_bound_vert(e->leftv, co);
@@ -3237,6 +3267,11 @@ static void build_vmesh(BevelParams *bp, BMesh *bm, BevVert *bv)
if (!weld)
create_mesh_bmvert(bm, vm, i, 0, k, bv->v);
}
+ else if (n == 2 && !v->ebev && vm->mesh_kind != M_ADJ) {
+ /* case of one edge beveled and this is the v without ebev */
+ /* want to copy the verts from other v, in reverse order */
+ copy_mesh_vert(vm, i, 0, k, 1 - i, 0, ns - k);
+ }
}
} while ((v = v->next) != vm->boundstart);
@@ -3305,6 +3340,219 @@ static float edge_face_angle(EdgeHalf *e)
#define BM_BEVEL_EDGE_TAG_DISABLE(bme) BM_ELEM_API_FLAG_DISABLE( (bme), _FLAG_OVERLAP)
#define BM_BEVEL_EDGE_TAG_TEST(bme) BM_ELEM_API_FLAG_TEST( (bme), _FLAG_OVERLAP)
+/* Try to extend the bv->edges[] array beyond i by finding more successor edges.
+ * This is a possibly exponential-time search, but it is only exponential in the number
+ * of "internal faces" at a vertex -- i.e., faces that bridge between the edges that naturally
+ * form a manifold cap around bv. It is rare to have more than one of these, so unlikely
+ * that the exponential time case will be hit in practice.
+ * Returns the new index i' where bv->edges[i'] ends the best path found.
+ * The path will have the tags of all of its edges set. */
+static int bevel_edge_order_extend(BMesh *bm, BevVert *bv, int i)
+{
+ BMEdge *bme, *bme2, *nextbme;
+ BMLoop *l;
+ BMIter iter;
+ int j, tryj, bestj, nsucs, sucindex, k;
+ BMEdge **sucs = NULL;
+ BMEdge **save_path = NULL;
+ BLI_array_staticdeclare(sucs, 4); /* likely very few faces attached to same edge */
+ BLI_array_staticdeclare(save_path, BM_DEFAULT_NGON_STACK_SIZE);
+
+ bme = bv->edges[i].e;
+ /* fill sucs with all unmarked edges of bmes */
+ BM_ITER_ELEM(l, &iter, bme, BM_LOOPS_OF_EDGE) {
+ bme2 = (l->v == bv->v) ? l->prev->e : l->next->e;
+ if (!BM_BEVEL_EDGE_TAG_TEST(bme2)) {
+ BLI_array_append(sucs, bme2);
+ }
+ }
+ nsucs = BLI_array_count(sucs);
+
+ bestj = j = i;
+ for (sucindex = 0; sucindex < nsucs; sucindex++) {
+ nextbme = sucs[sucindex];
+ BLI_assert(nextbme != NULL);
+ BLI_assert(!BM_BEVEL_EDGE_TAG_TEST(nextbme));
+ BLI_assert(j + 1 < bv->edgecount);
+ bv->edges[j + 1].e = nextbme;
+ BM_BEVEL_EDGE_TAG_ENABLE(nextbme);
+ tryj = bevel_edge_order_extend(bm, bv, j + 1);
+ if (tryj > bestj || (tryj == bestj && edges_face_connected_at_vert(bv->edges[tryj].e, bv->edges[0].e))) {
+ bestj = tryj;
+ BLI_array_empty(save_path);
+ for (k = j + 1; k <= bestj; k++) {
+ BLI_array_append(save_path, bv->edges[k].e);
+ }
+ }
+ /* now reset to path only-going-to-j state */
+ for (k = j + 1; k <= tryj; k++) {
+ BM_BEVEL_EDGE_TAG_DISABLE(bv->edges[k].e);
+ bv->edges[k].e = NULL;
+ }
+ }
+ /* at this point we should be back at invariant on entrance: path up to j */
+ if (bestj > j) {
+ /* save_path should have from j + 1 to bestj inclusive edges to add to edges[] before returning */
+ for (k = j + 1; k <= bestj; k++) {
+ BLI_assert(save_path[k - (j + 1)] != NULL);
+ bv->edges[k].e = save_path[k - (j + 1)];
+ BM_BEVEL_EDGE_TAG_ENABLE(bv->edges[k].e);
+ }
+ }
+ BLI_array_free(sucs);
+ BLI_array_free(save_path);
+ return bestj;
+}
+
+/* See if we have usual case for bevel edge order:
+ * there is an ordering such that all the faces are between
+ * successive edges and form a manifold "cap" at bv.
+ * If this is the case, set bv->edges to such an order
+ * and return true; else return unmark any partial path and return false.
+ * Assume the first edge is already in bv->edges[0].e and it is tagged. */
+#ifdef FASTER_FASTORDER
+/* The alternative older code is O(n^2) where n = # of edges incident to bv->v.
+ * This implementation is O(n * m) where m = average number of faces attached to an edge incident to bv->v,
+ * which is almost certainly a small constant except in very strange cases. But this code produces different
+ * choices of ordering than the legacy system, leading to differences in vertex orders etc. in user models,
+ * so for now will continue to use the legacy code. */
+static bool fast_bevel_edge_order(BevVert *bv)
+{
+ int j, k, nsucs;
+ BMEdge *bme, *bme2, *bmenext;
+ BMIter iter;
+ BMLoop *l;
+
+ for (j = 1; j < bv->edgecount; j++) {
+ bme = bv->edges[j - 1].e;
+ bmenext = NULL;
+ nsucs = 0;
+ BM_ITER_ELEM(l, &iter, bme, BM_LOOPS_OF_EDGE) {
+ bme2 = (l->v == bv->v) ? l->prev->e : l->next->e;
+ if (!BM_BEVEL_EDGE_TAG_TEST(bme2)) {
+ nsucs++;
+ if (bmenext == NULL)
+ bmenext = bme2;
+ }
+ }
+ if (nsucs == 0 || (nsucs == 2 && j != 1) || nsucs > 2 ||
+ (j == bv->edgecount - 1 && !edges_face_connected_at_vert(bmenext, bv->edges[0].e)))
+ {
+ for (k = 1; k < j; k++) {
+ BM_BEVEL_EDGE_TAG_DISABLE(bv->edges[k].e);
+ bv->edges[k].e = NULL;
+ }
+ return false;
+ }
+ bv->edges[j].e = bmenext;
+ BM_BEVEL_EDGE_TAG_ENABLE(bmenext);
+ }
+ return true;
+}
+#else
+static bool fast_bevel_edge_order(BevVert *bv)
+{
+ BMEdge *bme, *bme2, *first_suc;
+ BMIter iter, iter2;
+ BMFace *f;
+ EdgeHalf *e;
+ int i, k, ntot, num_shared_face;
+
+ ntot = bv->edgecount;
+
+ /* add edges to bv->edges in order that keeps adjacent edges sharing
+ * a unique face, if possible */
+ e = &bv->edges[0];
+ bme = e->e;
+ if (!bme->l)
+ return false;
+ for (i = 1; i < ntot; i++) {
+ /* find an unflagged edge bme2 that shares a face f with previous bme */
+ num_shared_face = 0;
+ first_suc = NULL; /* keep track of first successor to match legacy behavior */
+ BM_ITER_ELEM (bme2, &iter, bv->v, BM_EDGES_OF_VERT) {
+ if (BM_BEVEL_EDGE_TAG_TEST(bme2))
+ continue;
+ BM_ITER_ELEM (f, &iter2, bme2, BM_FACES_OF_EDGE) {
+ if (BM_face_edge_share_loop(f, bme)) {
+ num_shared_face++;
+ if (first_suc == NULL)
+ first_suc = bme2;
+ }
+ }
+ if (num_shared_face >= 3)
+ break;
+ }
+ if (num_shared_face == 1 || (i == 1 && num_shared_face == 2)) {
+ e = &bv->edges[i];
+ e->e = bme = first_suc;
+ BM_BEVEL_EDGE_TAG_ENABLE(bme);
+ }
+ else {
+ for (k = 1; k < i; k++) {
+ BM_BEVEL_EDGE_TAG_DISABLE(bv->edges[k].e);
+ bv->edges[k].e = NULL;
+ }
+ return false;
+ }
+ }
+ return true;
+}
+#endif
+
+/* Fill in bv->edges with a good ordering of non-wire edges around bv->v.
+ * Use only edges where BM_BEVEL_EDGE_TAG is disabled so far
+ * (if edge beveling, others are wire).
+ * first_bme is a good edge to start with.*/
+static void find_bevel_edge_order(BMesh *bm, BevVert *bv, BMEdge *first_bme)
+{
+ BMEdge *bme, *bme2;
+ BMIter iter;
+ BMFace *f;
+ EdgeHalf *e;
+ EdgeHalf *e2;
+ BMLoop *l;
+ int i, ntot;
+
+ ntot = bv->edgecount;
+ i = 0;
+ for (;;) {
+ BLI_assert(first_bme != NULL);
+ bv->edges[i].e = first_bme;
+ BM_BEVEL_EDGE_TAG_ENABLE(first_bme);
+ if (fast_bevel_edge_order(bv))
+ break;
+ i = bevel_edge_order_extend(bm, bv, i);
+ i++;
+ if (i >= bv->edgecount)
+ break;
+ /* Not done yet: find a new first_bme */
+ first_bme = NULL;
+ BM_ITER_ELEM(bme, &iter, bv->v, BM_EDGES_OF_VERT) {
+ if (BM_BEVEL_EDGE_TAG_TEST(bme))
+ continue;
+ if (!first_bme)
+ first_bme = bme;
+ if (BM_edge_face_count(bme) == 1) {
+ first_bme = bme;
+ break;
+ }
+ }
+ }
+ /* now fill in the faces ... */
+ for (i = 0; i < ntot; i++) {
+ e = &bv->edges[i];
+ e2 = (i == bv->edgecount - 1) ? &bv->edges[0] : &bv->edges[i + 1];
+ bme = e->e;
+ bme2 = e2->e;
+ BM_ITER_ELEM(l, &iter, bme, BM_LOOPS_OF_EDGE) {
+ f = l->f;
+ if ((l->prev->e == bme2 || l->next->e == bme2) && !e->fnext && !e2->fprev)
+ e->fnext = e2->fprev = f;
+ }
+ }
+}
+
/*
* Construction around the vertex
*/
@@ -3312,13 +3560,12 @@ static BevVert *bevel_vert_construct(BMesh *bm, BevelParams *bp, BMVert *v)
{
BMEdge *bme;
BevVert *bv;
- BMEdge *bme2, *unflagged_bme, *first_bme;
- BMFace *f;
+ BMEdge *first_bme;
BMVert *v1, *v2;
- BMIter iter, iter2;
+ BMIter iter;
EdgeHalf *e;
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list