Triangular mesh data structure and problem with point storage

Question

I'm pretty sure this will get closed as being opinion based but here goes... I am doing some mesh work in C# converting a point cloud to a triangular mesh. This is available in C++ but not really for C# (that I have been able to find).

I have a class for Point3d, Edge and Face. Point3d is the basis, Edge refers to Point3d indices for the end points of the edge and Face refers to the indices of the Edge to make a face:

public class MeshStructure
{
    public List<Point3d> Points = new List<Point3d>();
    public List<Edge> Edges = new List<Edge>();
    public List<Face> Faces = new List<Face>();
....
}

///////////////////////////////////////////////
    public class Edge
{
    int point1Index;
    int point2Index;

    public Edge(int point1Index, int point2Index)
    {
        this.point1Index = point1Index;
        this.point2Index = point2Index;
    }

    public int Point1 => point1Index;
    public int Point2 => point2Index;
}
//////////////////////////////////////////////
public class Face
{
    public Face(int edge1Index, int edge2Index, int edge3Index)
    {
        if(edge1Index == edge2Index || edge1Index == edge3Index || edge2Index == edge3Index)
        {
            throw new ArgumentException("No two edges may be identical. A face must be made up of three different edges.");
        }
        Edges.Add(edge1Index);
        Edges.Add(edge2Index);
        Edges.Add(edge3Index);
    }

    public List<int> Edges { get; } = new List<int>();
}

My problem here is how to "get" the values of points when working in the context of Face or Edge. I have come up with two strategies:

1. Pass the Points list by ref to every new instance of Edge and Face that I create. This somehow feels wrong to me though.

   public Edge(int point1Index, int point2Index, ref List<Point3d> points)
   {
       this.point1Index = point1Index;
       this.point2Index = point2Index;
       this.points = points;
   }
   

2. Pass the Points used in each Edge by value to every instance of Edge and the same concept with Face. This also feels wrong because of the memory bloat and ending up having multiple copies of the same Point3d.

Is there a design pattern for this kind of issue?

Answer 1

The representation you have is a bit uncommon. The regular Face-vertex representation can trivially reproduce your edges, so a explicit edge list does not seem to add any value as far as I can see. Another popular representation is a (half) winged mesh, but this requires more data to be stored.

I'm assuming the goal here is to have some methods that return some structural data about the mesh, like a list of connected edges for an edge. Otherwise a edge can simply be two indices.

Since you might have a great number of faces/edges there is a point in keeping the data size as small as possible. For this reason I prefer to use structs, since they do not have the overhead of a object. Consider using arrays and ref returns / in parameters to avoid copying.

One possible design is to keep faces/edges as data-only structures, and let the MeshStructure have all methods. So to iterate all connected edges there might be a IEnumerable<Edge> GetConnectedEdges(Edge edge) method.

A more complex design could be to have a two level design. An internal edge struct that stores the minimal possible data, and a public edge struct that also contains a reference to the parent object to allow complex methods. This gives a nicer API, at the cost of some complexity. Ex:

    public class MeshStructure
{
    private Point3d[] Points ;
    private EdgeInternal[] Edges ;

    public Edge GetEdge(int index) => new Edge(index, this);

    private readonly struct EdgeInternal
    {
        public int P1 { get; }
        public int P2 { get; }
        public EdgeInternal(int p1, int p2) => (P1, P2) = (p1, p2);
    }
    
    public readonly struct Edge
    {
        private readonly int edgeIndex;
        private readonly MeshStructure mesh;
        public int P1 => mesh.Edges[edgeIndex].P1;
        public int P2 => mesh.Edges[edgeIndex].P2;
        public Edge(int edgeIndex, MeshStructure mesh) => (this.edgeIndex, this.mesh) = (edgeIndex, mesh);
        public IEnumerable<Edge> GetConnectedEdges()
        {
            var edges = mesh.Edges;
            // Add logic
            return null;
        }
    }
}