Skip to content

extract_connected_components throws on any mesh with mutually-adjacent interior faces (BFS marks visited on dequeue) #103

Description

@csparker247

Summary

HalfEdgeMesh::num_connected_components() and HalfEdgeMesh::connected_components() marked a face visited when it was dequeued rather than when it was enqueued. A face adjacent to two or more faces that are themselves still in the queue is therefore pushed once per incident interior edge, so it appears multiple times in the component's face list.

This is a correctness bug, not merely redundant work:

  • connected_components() returns face lists containing duplicate faces. On a 4x4 grid (ConstructGrid(4, 4), 18 faces), the single component came back with 38 faces.
  • extract_connected_components() clones every face in that list, so it inserts the same face twice and throws:
    Attempted to add non-manifold face along edge with vids=[3, 6, 7]
    
    Any mesh with mutually-adjacent interior faces hits this, which makes multi-chart extraction unusable on real meshes.
  • num_connected_components() still returns the correct count (the outer seed loop skips already-visited faces), but does work proportional to the number of duplicate enqueues.

The existing component tests used meshes of one to two isolated triangles, which have no mutually-adjacent neighbors, so nothing caught it.

Reproduction

auto mesh = OpenABF::tests::ConstructGrid<HalfEdgeMesh<float>>(4, 4);   // 18 faces
auto ccs = mesh->connected_components();
// ccs[0].size() == 38, not 18
auto components = mesh->extract_connected_components();  // throws: non-manifold face

Fix

Set visited[idx] = true at push time in both traversals, so each face is enqueued and expanded exactly once. Regression test HalfEdgeMesh.ConnectedComponentsVisitEachFaceOnce asserts the component face list has no duplicates and matches num_faces(), and that the extracted face_map is a permutation of [0, num_faces). The test was confirmed Red against the pre-fix traversal.

Status

Found while running the F2 multi-chart packing pipeline on a real partitioned mesh. Fix and regression test are carried by PR #99 (F2) rather than a standalone PR, because F2's pipeline cannot run without it.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions