-
Notifications
You must be signed in to change notification settings - Fork 6
Mesh Implementations Data Structures
There are many different ways to implement/store a mesh. These different implementations have different characteristics in terms of:
- What neighborhood information can I obtain in constant time
- Memory usage
- Speed/cache friendliness
- What elements (face, edge, vertex) are "explicitly" stored = can be referred to
A table showing all this data can be found here. The different data structures will be briefly explained here.
| Name | Mem | Poly | Explicit Edge | Multi-blade Vertex |
|---|---|---|---|---|
| Shared Vertex | 7 | ✗ | ✗ | - |
| Linked Face | 13 | ✗ | ✗ | ✔ |
| Directed Edge | 13 | ✗ | ✗ | ✗ |
| Half Edge | 21/27 | ✔ | ✔ | ✔ |
| Winged Edge | 27 | ✔ | ✔ | ? |
I call these weak because they have a very limited feature set and are only useful in very special and rare situations. Furthermore, there are more capable data structures that do not really have any disadvantages compared to the weak ones.
However, I might want to consider still providing these to do some stuff. For example, shape creation functions can certainly create instances of these two types.
Vec<{
vertices: [VertexProp; 3],
}>
Just stores a list of faces, where each face just stores the properties of all its vertices. This DS has no adjacency information at all. Bad, because properties are duplicated and vertices are stored implicitly. This is sometimes used to render stuff, but it's usually better to use an index buffer instead to avoid duplicating data.
So this might be worth as some serialization/storage format, but not something to perform operations on. (Note: this is exactly the format STL files are stored in.)
Vec<{
prop: VertexProp,
neighbors: Vec<VertexHandle>,
}>
A list of vertices is stored, where each vertex stores it's properties and its neighbors. Bad, because it contains lists and faces are stored implicitly.
vertices: Vec<()>,
faces: Vec<{
vertices: [VertexHandle; 3],
}>Probably the most commonly used data structure in general. Graphic APIs like OpenGL are usually fed with data like this (a vertex- and an index-buffer).
- Vertex: 1
- Face: 3
- Edge: 0
Total per vertex: 1 + 2·3 + 3·0 = 7
vertices: Vec<{
one_face: Option<FaceHandle>,
>,
faces: Vec<{
vertices: [{
handle: VertexHandle,
next_face: FaceHandle,
}; 3],
}>- Vertex: 1
- Face: 3 · 2 = 6
- Edge: 0
Total per vertex: 1 + 2·6 + 3·0 = 13
- Vertex: 1
- Face: 0
- Edge: 2 · 2 = 4
Total per vertex: 1 + 2·0 + 3·4 = 13
vertices: Vec<{
half_edge: Option<HeHandle>,
>,
faces: Vec<{
half_edge: HeHandle,
}>,
half_edges: Vec<{
next: HeHandle,
twin: HeHandle, // stored implicitly
prev: HeHandle, // optional
vertex: VertexHandle,
face: FaceHandle,
}>- Vertex: 1
- Face: 1
- Edge: 2 · 3 = 6 (or 8 with
prev)
Total per vertex: 1 + 2·1 + 3·6 = 21 (or 27 with prev)
- Vertex: 1
- Face: 1
- Edge: 8
Total per vertex: 1 + 2·1 + 3·8 = 27
TODO