Implement different data structures for unstructured meshes

[juliohm]

Currently, we have UnstructuredMesh as the only data structure for unstructured meshes. It actually implements a Face-based structure that is useful for visualization. It is not useful at all for neighbor search or other kinds of queries.

We need to rename UnstructuredMesh to FaceMesh (Face-based mesh) or a similar name, and introduce other data structures such as Edge, HalfEdge, etc.

[serenity4]

I am not sure I understand the issue, and I am admittedly a bit confused about the current implementation of UnstructuredMesh. I'll try to communicate what I understood. From polytope theory, meshes can be described as a collection of faces. Since a face is a polytope, it describes what it's made of, i.e. edges, which are polytopes that describe their relation to vertices. So, a UnstructuredMesh can be described by just faces in theory. If we loosen the requirements on what a mesh is (allowing "faces" which are sets of edges that are not closed, and/or allowing meshes that have loose edges or vertices -loose as in not attached to any face), well it becomes complicated. In that case we may need a fully generic data structure (like discussed in #12). If I understand correctly, you are talking about introducing data structures with clear assumptions for a given purpose (e.g., FaceMesh with only valid, maybe even nondegenerate faces specifically for rendering), is that right? And the UnstructuredMesh currently implemented would be a FaceMesh? That's where I get confused. Looking at the code I mostly see that it has a specific field for elements, and keeps track of connectivity ranks. It's not useful for rendering surfaces in 3D since its elements would be volumes (and not actual faces, contrarily to what the name would imply) Was it specific to 2D rendering then?

introduce other data structures such as Edge, HalfEdge, etc.

What should Edge and HalfEdge represent? I would consider Segments or Chains to play the role of an Edge already, as they are both a 1-polytope. I searched for what a half-edge is, and found that it is just a directed edge. Is it correct?

[juliohm]

In summary, we have multiple ways of storing the topological information of the mesh. In UnstructuredMesh we have a global vector of vertices and a list of connectivity objects that point to this global vector. In this case, we allow this list of connectivity objects to contain faces of any rank (e.g. triangle, edge, tetrahedron).

Other data structures encode the connectivities differently. They only store the faces of highest order (e.g. triangles in 2D) and then provide a smart scheme to navigate the neighbors of a face, the incident faces of lower rank, etc. These data structures are famous in polygon mesh processing. For example, the DCEL structure used in CGAL: https://en.wikipedia.org/wiki/Doubly_connected_edge_list

What we need to do is think about these structures carefully. Maybe preserve this greedy representation we currently have as UnstructuredMesh that stores every single face in any rank possible, and then add other structures that are smart in memory usage and more useful for spatial queries and navigation. Makes sense?

[juliohm]

I've renamed the verbose UnstructuredMesh to SimpleMesh. This simple mesh is the greedy representation where we are free to insert faces of any rank in the connectivity list. I will start working on different representations.

[juliohm]

We now have HalfEdgeStructure and ExplicitStructure in the master branch. Next step consists of refactoring SimpleMesh to use ExplicitStructure before moving forward with other implementations.

[juliohm]

This issue is fixed. We have all the machinery in place to keep adding more topological data structures.