Splitting arcs in a graph causes corruption.

[olson-sean-k]

Triangulating a graph constructed by subdividing a simple face appears to cause corruption. I discovered this while experimenting with the subdivide example, which demonstrates this function:

pub fn circumscribe<G>(face: FaceView<&mut MeshGraph<G>, G>) -> FaceView<&mut MeshGraph<G>, G>
where
    G: EdgeMidpoint<Midpoint = VertexPosition<G>> + GraphGeometry,
    G::Vertex: AsPosition,
{
    // Split each edge, stashing the vertex key and moving to the next arc.
    let arity = face.arity();
    let mut arc = face.into_arc();
    let mut splits = SmallVec::<[_; 4]>::with_capacity(arity);
    for _ in 0..arity {
        let vertex = arc.split_at_midpoint();
        splits.push(vertex.key());
        arc = vertex.into_outgoing_arc().into_next_arc();
    }
    // Split faces along the vertices from each arc split.
    let mut face = arc.into_face().unwrap();
    for (a, b) in splits.into_iter().perimeter() {
        face = face.split(ByKey(a), ByKey(b)).unwrap().into_face().unwrap();
    }
    // Return the central face of the subdivision.
    face
}

Using this function, the following code causes a panic when calling triangulate:

let mut graph = MeshGraph::<Point2<f64>>::from_raw_buffers(
    vec![NGon([0usize, 1, 2, 3])],
    vec![(-1.0 -1.0), (1.0, -1.0), (1.0, 1.0), (-1.0, 1.0)],
)
.unwrap();
let key = graph.faces().nth(0).unwrap().key();
// Subdivide the face twice.
circumscribe(circumscribe(graph.face_mut(key).unwrap()));
graph.triangulate(); // PANIC!

So far, it seems that the subdivisions work as intended. The number of vertices and faces is correct and so is the arity of the faces. However, triangulation suddenly fails when it encounters a face with arity 11. That's very strange:

1. Triangulation is implemented using splits, which should be independent of other faces; the arity of faces elsewhere in the graph should not be affected.
2. After the subdivisions, there are only 12 vertices in the graph, so a face with arity 11 would include all but one of them.

I suspect that something is wrong in the mutation API (specifically FaceSplitSnapshot and split_with_snapshot), but I'm not sure. For example, maybe the snapshot is failing to identify the perimeters for the two newly inserted faces for the split.

[olson-sean-k]

There are duplicate keys in the perimeters constructed by FaceSplitSnapshot::snapshot. This causes this error to be returned.

[olson-sean-k]

It looks like a face insertion may be the problem. During a split, two face insertions that each use a perimeter with three vertices are performed. After this operation, an unrelated face is corrupted, and reports having 11 interior arcs. The arcs form a consistent ring, but are clearly nonsense. This could be a deeper problem with arc connectivity...

[olson-sean-k]

It seems that some vertices never have a leading arc despite being a part of a ring. Looking at the connectivity set of vertices during face insertions, there are vertices with no connectivity that are part of the connectivity of other vertices! Sure enough, trying to access the leading arc of all vertices in the graph also leads to a panic:

for vertex in graph.vertices() {
    let arc = vertex.into_outgoing_arc(); // PANIC!
    let _ = arc.key();
}

[olson-sean-k]

Implementing #17 likely would have caught this. Test coverage and exercising of the mutation API is not very good, but changing the commit implementation for VertexMutation already causes test failures for composite edge splits:

fn commit(self) -> Result<Self::Mutant, Self::Error> {
    let VertexMutation {
        storage: vertices, ..
    } = self;
    // Fail if any vertex payloads have no leading arc. FAILS.
    for (_, vertex) in vertices.iter() {
        let _ = vertex.arc.ok_or_else(|| GraphError::TopologyMalformed)?;
    }
    Ok(Core::empty().bind(vertices))
}

[olson-sean-k]

I believe this is the problematic line of code. It is likely more correct to disconnect vertices from their leading arcs, but the code in split_with_cache will leave the vertex B without a leading arc when splitting from the arc AB.

[olson-sean-k]

This is fixed by 6bfe175 on the mutate branch. I plan to do more work on that branch to improve the mutation module.

[olson-sean-k]

I've cherry-picked 043abfe from the mutate branch into master. That change provides the basic fix. It was lingering on the mutate branch for a while, but since this is an easy bug to encounter, I wanted to pull it out of mutate so that it doesn't get held up by other changes.