How to implement a half-edge data structure in Rust

help
1

I'm trying to implement what's called a half-edge data structure in Rust, to represent a mesh. The naive approach obviously doesn't work in Rust:

struct HalfEdge {
    face: Face,
    prev: HalfEdge,
    next: HalfEdge,
    opposite: HalfEdge
}

So I'm trying this:

struct Mesh {
    edges: Vec<HalfEdge>
}

struct HalfEdge {
    mesh: Mesh,    //  <--- Feels weird for every HalfEdge to have to know about the mesh it's in.
    prev_id: Option<usize>, // <-- This has to be optional, as the previous half edge may not have be there, while building the mesh, and forms a cycle representing a face.
   ... etc
}

impl HalfEdge {
    fn prev(&self) -> &HalfEdge {
        &self.mesh.edges[self.prev_id.expect("Explode")] // From the point of view of the mesh user, this is absolutely not optional.
    }
}

It feels a bit weird - but from Rust perspective my reasoning is that the Mesh struct is the ultimate owner. When it goes - all HalfEdges, Faces, Vertices go.

is that idiomatic Rust? Various blog posts I've seen have all manner of nested Rc, RefCell, Box etc.

The downside is it still comes down to me to ensure all half-edges in a completed mesh correctly point to something (which they should - part of the reason I'm using this structure is this guarantee - and edge can't be dangling, otherwise it would represent an open or 'non-manifold' boundary). Just like unsafe code, I still leave the potential for 'edge.prev()' to blow up. So might I as well use raw pointers in my Mesh half-edge data structure? I get no help from the compiler either way. It seems, essentially, that in Rust one can't guarantee a valid cycle of structs any more than any other language?

Another thing that feels strange is the public nature of struct fields within a module - I'd like the details of HalfEdge to be entirely private, so noone ever sees 'prev_id. I know outside the module that will be true, but I want my tests, which are in the module, to have the same API.

2 
struct HalfEdge {
    mesh: Mesh,    //  <--- Feels weird for every HalfEdge to have to know about the mesh it's in.
    prev_id: Option<usize>, // <-- This has to be optional, as the previous half edge may not have be there, while building the mesh, and forms a cycle representing a face.
   ... etc
}

Unfortunately, you aren't going to get very far with this, either. In the above snippet, the HalfEdge owns the Mesh. Since the Mesh also owns the HalfEdge, you're gonna have a bad time.

If that mesh member were instead a &Mesh, then you would run into the issue that you can't mutate Mesh to add more half-edges to the vector. If it were instead a &mut Mesh, then across all half-edges you would end up with multiple mutable references to the same object (which is forbidden).

I would give up all hope on being able to write something like edge.prev(). Instead, extract the concept of navigation into its own type:

(take this as just a sort of hastily written, vague suggestion of what direction to go in; not all ideas in it will necessarily work)

// serves as the owner of all items
struct Mesh {
    edges: Vec<HalfEdge>,
}

// serves to collect data associated for one item
struct HalfEdge {
    prev: Option<usize>,
    ...
}

// kind of represents the state of an algorithm that works on meshes
struct Cursor<'a> {
    mesh: &'a mut Mesh,
    current_id: usize,
}

impl Mesh {
    ...
    fn navigate_from(&mut self, id: usize) -> Cursor {
        Cursor {
            mesh: self,
            current_id: id,
        }
    }
}

impl<'a> Cursor<'a> {
    // navigation...
    fn prev(self) -> Self { /* change current_id */ }
    fn opposite(self) -> Self { /* change current_id */ }
    ...

    // modification...
    fn frobnicate_knobs(self) -> Self { /* mutate mesh */ }
    ...
}

fn meanwhile_in_canada() {
    // ...
    mesh.navigate_from(3)
        .prev()
        .last()
        .frobnicate_knobs();
    // etc...
}

Actually, this will probably require two types of cursors; a Cursor with a &'a Mesh (with only traversal methods, for e.g. search algorithms), and a CursorMut with a &'a mut Mesh (with both traversal and mutation methods, for mutating algorithms).

4 Likes
3

Thanks @ExpHP - that's an interesting way to get around the problem. As you can tell, I'm just learning Rust, and it seems doubly linked lists, or circular references in general, are a bit of an issue in Rust. It seems to be commonly solved with raw pointers.

4

yeah, low level data structures are challenging in rust. give this a read for far too much detail
http://cglab.ca/~abeinges/blah/too-many-lists/book/

2 Likes