plexus
plexus copied to clipboard
Reevaluate the constraints on non-manifold topology in graphs.
MeshGraph
, despite being based on a half-edge graph design, supports some non-manifold and non-compact topologies. Below are some observations about these features that may need to be revisited to avoid degenerate behavior.
One of the most obvious examples of this is the concept of rings, which may not be associated with a face and allow for explicit gaps in a graph. Additionally, graphs allow for unbounded edges, which are edges that participate in no faces at all. This interacts strangely with rings, because a lone edge forms a single ring in which a face may be inserted.
A ring requires only two arcs at a minimum. This is different from a face, which must be composed of at least three vertices and three arcs. Some code assumes that rings and faces are identical in this respect. For example, rings and faces share circulator implementations which use a lower bound size hint of three. More critically, mutations do not detect rings with an arity of two when attempting to insert faces. I'm not sure yet, but this probably leads to latent errors or, in the worst case, get_or_insert_face
being capable of corrupting a graph.
MeshGraph
also supports singularities. A singularity is a vertex that is shared by more than one face where none of the faces share any other topology. This forms a non-manifold "pinwheel" structure. This was previously disallowed, but I relaxed this constraint. However, it requires detection and special behavior for certain operations.
At the very least, it would probably be best for graphs to reject unbounded edges. It's also worth keeping in mind that gaps in a surface can also be represented geometrically: using ()
or Option<_>
for face geometry is one way to model a wireframe or a surface with gaps, respectively.
I think this issue (or others; I'm not yet sure how to organize the work) should track the following changes to graphs:
- Disallow singularities. See 7de93ea, which removed their detection in the mutation API.
- Disallow unbounded edges.
- Require an arity of three or higher for rings. (This is implied by the previous item.)
In essence, this restores the requirement (and limitation) that graphs represent a manifold, with the possible exception of empty rings.
Another important observation that's worth noting here: disallowing these non-manifold features has implications for the way that topological mutations work, especially removals. For example, when removing a face, it may be necessary for other topology to also be removed so as to avoid inconsistency.
One obvious example is a graph composed of nothing more than a single face. Removing the face (and nothing more) results in unbounded edges. In this situation, removing the face would need to be maximally destructive, resulting in the removal of all edges, arcs, and vertices too.