Page MenuHome
Differential D10205

Fix unsubdivide entering an infinite loop with two faces vert
Needs ReviewPublic
Actions

Authored by Pablo Dobarro (pablodp606) on Jan 26 2021, 1:11 AM.

Details

Reviewers
Sergey Sharybin (sergey)
Summary

In the initial step of unsubdivide, the algorithms tags the center
vertex of each subdivided face of the lower level subdivision level.
After that, it checks if the state of the tags is a valid configuration
for building a lower level base mesh. If it is, it starts dissolving the
tagged vertices to start building the new base mesh.

With the following topology, unsubdivide tags the vertices marked with a
blue X. It was considering this set of tags valid, so it was dissolving
them and starting the grid extraction.

When dissolving vertex A, that creates a loose edge over the face, so
the untagged vertex B and the edge C were also dissolved. Because of
this, grid extraction was starting with an unexpected topology layout,
making it enter an infinite loop as it was not able to find the corners of
the grids for the new base mesh loops.

This adds and extra rule to the tag state checking that considers these
cases as there is actually no valid lower level mesh to rebuild.

Diff Detail

Repository
rB Blender
Branch
fix-unsubdivide-loop (branched from master)
Build Status
Buildable 12378
Build 12378: arc lint + arc unit

Event Timeline

Pablo Dobarro (pablodp606) requested review of this revision.Jan 26 2021, 1:11 AM
Pablo Dobarro (pablodp606) created this revision.
Harbormaster completed remote builds in B12378: Diff 33126.Jan 26 2021, 1:11 AM
Pablo Dobarro (pablodp606) retitled this revision from Fix unsubdivide entering an infinte loop with two faces vert to Fix unsubdivide entering an infinite loop with two faces vert.Jan 26 2021, 1:12 AM
Pablo Dobarro (pablodp606) edited the summary of this revision. (Show Details)
Pablo Dobarro (pablodp606) added a reviewer: Sergey Sharybin (sergey).
Sergey Sharybin (sergey) added a comment.Jan 26 2021, 9:55 AM

What is not clear to me, is why the ckeck only needed for 2-faced faces. What if vertex is adjacent to 3, 5 or more faces?

source/blender/blenkernel/intern/multires_unsubdivide.c
263

Keep iterators closer to usage.
Possibly, even move the loops into a helper functions, which will:

  • Help readability around iter, iter_a, iter_b
  • Make it More clear what the check is doing semantically (from function name and comment).
Pablo Dobarro (pablodp606) added a comment.Jan 26 2021, 5:35 PM

What is not clear to me, is why the ckeck only needed for 2-faced faces. What if vertex is adjacent to 3, 5 or more faces?

I think this is the only case were the vertex B is dissolved when dissolving vertex A and a valid tag pattern is detected. The rest of the cases are already considered by the existing rules.
If vertex B has 3 or 5 adjacent faces and all edges are adjacent to 1 or 2 faces, it should always be possible to dissolve one of its neighbors. After this patch, base meshes like this work as expected.

source/blender/blenkernel/intern/multires_unsubdivide.c
263

Should I include this refactor as part of this patch?

Sergey Sharybin (sergey) added inline comments.Jan 27 2021, 9:38 AM
source/blender/blenkernel/intern/multires_unsubdivide.c
263

No, don't mix refactor and functional changes.

In this patch what you can easily do is to declare BMEdge *e; just before the loop you need it for.

You should also consider making it so:

/* Returns truth if any adjacent vertex to the given one is tagged with `BM_ELEM_TAG`.   */
static bool check_any_adjacent_vert_tagged(BMVert *vert) {
  BMEdge *edge;
  BM_ITER_ELEM (edge, &iter, v, BM_EDGES_OF_VERT) {
    BMVert *other_vert = BM_edge_other_vert(edge, vert);
    if (BM_elem_flag_test(other_vert, BM_ELEM_TAG)) {
      return true;
    }
  }
  return false;
}

static bool unsubdivide_is_center_vertex_tag_valid(BMesh *bm, int *elem_id, int elem) {
    ...
    else if (BM_vert_face_count(v) == 2) {
      if (check_any_adjacent_vert_tagged(v)) {
        /* Inner vertex with two faces with connected tagged vertex.
         * NOTE: The other cases of adjacency (for example, vertex is adjacent to 3 faces) is handled with checks above. */
        return false;
      }
    }
   ...
}

Gives you vertical space in unsubdivide_is_center_vertex_tag_valid to place the note about adjacency case which you explained in the comment here in the review.

Revision Contents
Changeset List

PathSize
source/
blender/
blenkernel/
intern/
11 lines

Diff 33126

View Options

source/blender/blenkernel/intern/multires_unsubdivide.c

Loading...