I wish to create said algorithm in rust if a library for it doesn't already exist.
this is really more of a 3d modeling/CGI question than a rust-specific one, and as such you'll probably have more luck asking in a group centered around that.
I don't see anything on lib.rs already, but the standard editor representation using half-edges makes this somewhat simple: each half-edge without an opposite is a surface edge, then you just need to chase the target vertices and connect them up with the next base vertex. Fiddly to get everything set up right and handle all the weird edge cases (for example handling multiple holes connecting at a vertex), but then everything is in 3d.
Literally, lol!
1 Like
If edge cases are hard, are vertex cases harder?
2 Likes
Sorry, let me be specific, I mean how do you detect an edge loop via indices?
Yeah, this is why editors use half-edge representations (among other optimizations), doing these sorts of operations from raw index lists is a huge pain and expensive.
Triangle list or strips are fairly straightforward to interpret as half-edges at least: index 3N is a half edge to index 3N + 1, which is a half edge to 3N + 2, which is a half edge to back to 3N for triangle list, for example.
But this isn't enough to do these operations efficiently: you're going to need the opposing half edge and to iterate the half edges around a vertex.
The opposite of a half edge is the one going the opposite direction. For a closed surface there's always exactly one of these, for a surface boundary edge there isn't one, but you can get degenerate surfaces like 0,1,2;0,1,3 where half edges share an an edge, so you have to figure out what you want to support. You can get this with an linear search for reversed half edges for every edge, but it's something you're going to be doing so often the O(n) construction cost of building a lookup will be well worth it in comparison to a O(nĀ²) brute force approach, especially if you can keep it around for multiple operations.
Then you need the half edges around a vertex. For example in 0,1,2;0,2,3;0,3,1 there's three edges around 0: three half edges going in, and three going out. For the other vertices there's also three edges, but two of them are a surface boundary and therefore only have one half edge, eg for 1, there's a inbound half-edge from 3 and an outbound half edge to 2. This is a bit tougher because the number of half-edges around a vertex are unbounded even for well-behaved closed surfaces, and for good behavior you generally want them to be ordered. Most of the time you just need the outbound (or just the inbound, it's equivalent), at least.
There's a few crates that will provide this form to you on lib.rs already, at least.
1 Like
How do I represent half-edges?
They're logically a start index and an end index, and represent the side of a triangle on it's left (iirc), so each triangle creates three. That means you can use a triangle list or strip index directly as a representation to be a bit more compact, but you're going to want a way to iterate and to index into that representation, so you can use those support structures.
This is the
bit I was talking about, and also the boring part you should probably fob off to a crate like (to pick a random search result) TriMesh ā data structures in Rust // Lib.rs
1 Like
One issue, I don't know the average index order of each triangle of an object in a file.
I have no idea what an "average index order" means? Generally an index buffer defines the triangles, so if it's a triangle list every three indices are a single triangle (and therefore three half edges).
I see. Thanks for the info.