我正在尝试实现网格表示的半边数据结构。我目前的障碍是,
对于此 DS,您需要多个指针,可能的实现示例如下:
class HalfEdge {
Edge * next;
Edge * prev;
Edge * pair;
Vertex * vertex;
Face * face;
}
这没有错。但是,如果您使用指针(假设我们使用智能指针而不是原始指针以避免指针的已知问题(,您的数据现在很少存在于内存中,并且由于缓存而降低性能。更糟糕的是,如果你想把这个网格发送到gpu,现在你必须序列化顶点,想象一下你必须每一帧都这样做!
所以另一种选择是拥有数组,然后这样做:
// 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;
}
这与数组相结合,将允许您将内容临时保存在内存中,现在您可以将网格发送到 gpu,而无需制作线性化缓冲区的开销。但是,这有一个语法问题。
以前你可以做face->field
现在你必须做face_array[face_index].field
这是超级笨重的。
天真地,人们可能会认为将用于分配的顶点和用于访问的指针结合起来会起作用,就像Face* face = &face_array[index]
一样,任何在C++方面具有足够经验的人都知道指针将在调整数组大小的那一刻变得无效。
由于不知道网格的潜在大小,无法预先分配阵列,因此无法执行此操作。
基于上述所有内容,如果您希望内存是偶然的,您能比face_array[index].field
做得更好吗?
假设您将成员存储在列表中,您可以执行以下操作:
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;
// ...
};
这将允许您访问本地范围内的值,例如
HalfEdge he = /* ... */;
auto& edge = he.next(); // which is otherwise equivalent to
auto& edge = edge_list[he.next_index];
从本质上讲,它类似于您存储引用的想法,但不是存储对可能失效的数据成员的引用,而是存储对实际数组的引用,并根据需要重新计算偏移量。