CODEWITHSUNDEEP
c++arraysmemorydata-structuressyntax
Makogan
Makogan

Reputation: 9622

C++ can you design a data structure that keeps pointers in contiguous memory and doesn't invalidate them?

I am trying to implement the half edge data structure for mesh representation. My current hurdle is,

For this DS you need multiple pointers, an example of a possible implementation is this:

class HalfEdge {
        Edge * next;
        Edge * prev;
        Edge * pair;
        Vertex * vertex;
        Face * face;
}

There's nothing wrong with that. However if you use pointers (let's say we use smart pointers instead of raw to avoid known issues with pointers), your data now lives sparsely in memory and you loose performance due to caching. Worse, if you want to send that mesh to the gpu, now you must serialize the vertices, and imagine you have to do that every frame!

So an alternative is to have arrays and then do this:

// Somewhere else we have vectors of edges, faces and vertices
// we store their indices in the array rather than pointers.
class HalfEdge {
        uint next_index;
        uint prev_index;
        uint pair_index;
        uint vertex_index;
        uint face_index;
}

This, combined with the arrays, will allow you to keep stuff contingently in memory and now you can send the mesh to the gpu without the overhead of making the linearized buffer. However this has a syntax problem.

Before you could do face->field now you have to do face_array[face_index].field Which is super clunky.

Naively one could think that combining vertices for allocation and pointers for access would work, something like Face* face = &face_array[index], however, anyone with enough experience in C++ knows that pointer is going to become invalid the second the array is resized.

Not knowing the potential size of the mesh, the array can't be pre allocated, so it's not possible to do that.

Based on all of the above, can you do better than face_array[index].field if you want the memory to be contingent?

Upvotes: 2

Views: 405

Answers (1)

N. Shead
N. Shead

Reputation: 3938

Assuming you store your members in a list, you could do something like:

class HalfEdge {
public:
  Edge& next() { return (*edge_list)[next_index]; }
  Edge& prev() { return (*edge_list)[prev_index]; }
  // ...
  // probably also const-qualified versions is a good idea

private:
  // or global if needed, or whatever
  std::vector<Edge>* edge_list;
  // ...

  std::size_t next_index;
  std::size_t prev_index;
  // ...
};

This will allow you to access values in your local scope like

HalfEdge he = /* ... */;
auto& edge = he.next();  // which is otherwise equivalent to
auto& edge = edge_list[he.next_index];

In essence it's similar to your idea of storing a reference, but rather than storing a reference to a data member that can get invalidated we instead store a reference to the actual array, and recalulate the offset as needed.

Upvotes: 1

Related Questions