Feedback on API design of a HalfEdge Data structure

Question

Background

Sometimes also referred to as doubly connected edge list, the HalfEdge data structure allows programmers to efficiently and easily modify topological and geometric properties of a mesh. Examples of things you can do with them in very efficient terms:

• Find all neighbours of a vertex.
• Split an edge.
• Split a face.

And many others.

Implementation

I have an implementation where I took great care of many invariant that make the DS better. For example, pair edges are stored consecutively in memory. That is, the index into the allocation array of the pair of an edge is always either +1 or -1. I have been also very careful that allocations and modifications always preserve the order of the edges, faces...

For any operation that adds elements (faces, vertices, edges) it is trivial to maintain these invariants so operations like edge flipping and splitting are simple to design.

However removing elements such as vertex deletion or edge collapsing will create holes in my data, which breaks an enormous amount of my algorithms, which assume for ergonomics and efficiency that the data is always contiguous.

Deletion work around.

What I ended up doing to support the more iffy operations is have 2 structs HalfEdge and HalfEdgeDeleter. HalfEdgeDeleter takes a lifetimed reference into a half edge and won't let it go until the user explicitly calls finish(). When that method is called, the destructor of the deleter will reorganize the data to restore all invariants that deleting elements may have broken.

An example of this API in use:

        let (verts, _normals, _uvs, verts_idx, _normals_idx, _uvs_idx) =
            load_obj_from_disk("../../Assets/convex_poly.obj");
        let mut mesh = HalfMesh::new((verts, verts_idx));

        let mesh_deleter = HalfMeshDeleter::new(&mut mesh); // Blocks access to the mesh
        mesh_deleter.hedge_handle(GeomId(0)).collapse::<f32>();
        mesh_deleter.finish(); // Releases the mesh.

Question

This seems to be perfectly functional but has certain problems. First, I am not a fan of having an entire additional structure to handle deletion operations. Second it reduces the possibilities of breaking the mesh irreparably, but it does not eliminate them all together because to do so I would restrict the API too much, making it unusable, so some level of unsoundness is required to make it functional.

Can I do this better?

The invariants that need to be preserved:

• Data structure stores only the data, no metadata, i.e. no list of deleted ids or anything of the sort.

• O(1) operations are truly O(1) (i.e. no randomly triggering a defragmentation algorithm abusing the fact that the amortized cost is O(1))

• Pair edges are always stored contiguously in memory.

• There are no gaps in the data for long periods of time.