good data structure for triangular mesh [closed]

Question

I am looking for a memory-efficient yet convenient data structure for a 3D mesh or face-set consisting of triangles.

Currently I am using this 'classical' structure:

• a list of points, and a list of triangles.
• Each point has a X, Y, and Z value.
• Each triangle has three indices i0, i1, i2, which refer to a point in the point list.

This is the most compact layout I can think of. It is perfect if all I want to do is draw the mesh, and never modify or filter it. However it does make most operations that modify the mesh or generate a new partial mesh very cumbersome, for example:

• Removing triangles is very inefficient.
• generating a new mesh with only triangles that have less than 3 neighbors
• Finding and removing all triangles that have one or all point within a given bounding box
• finding all edges with a certain angle
• removing all edges shorter than a certain length

Basically anything that requires modifying the mesh, or iterating over the edges or finding neighboring faces/edges, requires generating and discarding several temporary dictionaries and hash sets. There is no easy way to iterate over the points or edges of an individual face, or the edges/faces around an individual point. removing a point means removing it from each triangle, then changing the index values for all other points in all triangles, etc.

Is there a canonical data structure that does not have these drawbacks, yet is memory-efficient?

I am not looking for an entire library, just a structure I can implement myself (although it may be interesting to know how particular libraries have solved this problem)

Answer 1

There's a couple of open source data structure that may fit your needs:

1. CGAL https://www.cgal.org/
2. OpenMesh http://openmesh.org/
3. Surface Mesh http://opensource.cit-ec.de/projects/surface_mesh

I've oredered them from the harder to the easier to use. They are all half edge data structures

Take a look at this paper from Bielefeld university (developers of the Surface mesh), I think that it's a good starting point for you!