4 ms·

Geometry/topology is very often presented as soup of pointers, (think of doubly connected edge list, Quad-edge, etc.) I have personnally always implemented thes

Geometry/topology is very often presented as soup of pointers, (think of doubly connected edge list, Quad-edge, etc.) I have personnally always implemented these with pointers, because it's at the tip of my skills and that's how they are presented on the internet ; but I'm curious to know if people more confortable with topologies and meshes use a different memory representation.

Const-me 4y ago
I usually keeping these things as indexed meshes: std::vector<Vector3> for positions, and std::vector<std::array<uint32_t,3>> for the triangles. As a nice side effect, the representation is compatible with GPUs, matches VRAM layout of the vertex/index buffers. For some simple algorithms which need adjacency information, that’s everything needed. For instance, to compute per-vertex normals, nothing else is required, create an std::vector for the per-vertex accumulators, and iterate over the triangles. For complicated algorithms which need adjacency information, I build special indices over the same data. To find triangles connected to specific triangle, a hash map with uint64_t keys (two sorted uint32_t vertex IDs in the lower/upper half of the integer) and a structure of two uint32_t values (triangle IDs, good meshes are guaranteed to have exactly 2 triangles for each edge, with opposite winding directions). To find triangles by vertex, a multimap from uint32_t vertex to uint32_t triangle. For algorithms which need to modify these meshes, sometimes I generate new meshes instead of modifying old ones. Other times I replace erased elements with special values (like UINT_MAX for integer indices), append new elements to the end of the vectors, and when the algorithm is complete I re-index the mesh while removing unused vertices/triangles.
ordu 4y ago
I think, that they presented on Internet as a soup of pointers, because it is the obvious and general way to do it. Other ways like connectivity matrix are less general: if you have a lot of nodes, and by several orders of magnitude less then N^2 edges, then the most of matrix elements will be empty. Moreover it is not obvious way, you need to explain it also on top of your goal to explain what you are explaining about geometry/topology. So if you tried to do it you'd spend all the allotted time talking about pros and cons of different representations of topology. I believe that if someone tried to talk about topology while using Rust as a language for sample code, he/she would use some other representation, because a soup of pointers is a PITA in Rust. It is easier to claim that we will be using a connectivity matrix, or a Vec of edges, and to explain how it works, than to juggle with pointers.
LorenPechtel 4y ago
If the *only* thing you need is to move along the list then pointers are probably the best answer. However, in my limited experience with such things I have always found myself needing both walking around and a big-picture list of items. Thus I have always implemented such things as a list of elements and storing indexes rather than pointers.

Const-me 4y ago

I usually keeping these things as indexed meshes: std::vector<Vector3> for positions, and std::vector<std::array<uint32_t,3>> for the triangles. As a nice side effect, the representation is compatible with GPUs, matches VRAM layout of the vertex/index buffers. For some simple algorithms which need adjacency information, that’s everything needed. For instance, to compute per-vertex normals, nothing else is required, create an std::vector for the per-vertex accumulators, and iterate over the triangles. For complicated algorithms which need adjacency information, I build special indices over the same data. To find triangles connected to specific triangle, a hash map with uint64_t keys (two sorted uint32_t vertex IDs in the lower/upper half of the integer) and a structure of two uint32_t values (triangle IDs, good meshes are guaranteed to have exactly 2 triangles for each edge, with opposite winding directions). To find triangles by vertex, a multimap from uint32_t vertex to uint32_t triangle. For algorithms which need to modify these meshes, sometimes I generate new meshes instead of modifying old ones. Other times I replace erased elements with special values (like UINT_MAX for integer indices), append new elements to the end of the vectors, and when the algorithm is complete I re-index the mesh while removing unused vertices/triangles.

ordu 4y ago

I think, that they presented on Internet as a soup of pointers, because it is the obvious and general way to do it. Other ways like connectivity matrix are less general: if you have a lot of nodes, and by several orders of magnitude less then N^2 edges, then the most of matrix elements will be empty. Moreover it is not obvious way, you need to explain it also on top of your goal to explain what you are explaining about geometry/topology. So if you tried to do it you'd spend all the allotted time talking about pros and cons of different representations of topology. I believe that if someone tried to talk about topology while using Rust as a language for sample code, he/she would use some other representation, because a soup of pointers is a PITA in Rust. It is easier to claim that we will be using a connectivity matrix, or a Vec of edges, and to explain how it works, than to juggle with pointers.

LorenPechtel 4y ago

If the *only* thing you need is to move along the list then pointers are probably the best answer. However, in my limited experience with such things I have always found myself needing both walking around and a big-picture list of items. Thus I have always implemented such things as a list of elements and storing indexes rather than pointers.