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.
Summary
HalfEdgeMesh::num_connected_components()andHalfEdgeMesh::connected_components()marked a facevisitedwhen 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: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
Fix
Set
visited[idx] = trueat push time in both traversals, so each face is enqueued and expanded exactly once. Regression testHalfEdgeMesh.ConnectedComponentsVisitEachFaceOnceasserts the component face list has no duplicates and matchesnum_faces(), and that the extractedface_mapis 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.