6

我正在编写一个物理引擎，并且很难找到一种设计数据存储的好方法。

我想要的功能：

  • 有一个代表 PhysicsBody 的类
  • 有一个代表碰撞体积的类（比如说一个盒子）
  • 每个物理体可以附加一个以上的碰撞体积
  • 可能有没有碰撞体积的物理体
  • 可选：没有物理实体的 CollisionVolume。（想想触发量）

现在我基本上有两个循环。一种更新模拟中的物理体。它更新它们的位置/速度/旋转。第二个循环对所有碰撞体积执行碰撞检测。它只是一个嵌套的 for 循环，用于检查每对碰撞体积之间的碰撞。（我知道它可以做得更好，但这是一个单独的话题）

我知道理想的方法是将对象存储在连续的数组中。

std::vector<PhysicsBody> m_bodies;
std::vector<CollisionVolume> m_colliders;

我发现这种方法的问题：

  • 很难维护 PhysicsBody -> CollisionVolume 关系。例如，如果我想从我的向量中删除一个 CollisionVolume，我会将它与最后一个交换并弹回。数据被移动，如果我在 PhysicsBody 中存储了 CollisionVolume 的索引，它就不再有效。
  • 每当我销毁一个 PhysicsBody 时，析构函数都会检查是否有任何碰撞体积附在它上面，并适当地将其从物理系统中删除。问题是向量会制作内部副本并销毁它们，当这种情况发生时，它会通过删除不应该删除的碰撞体积来造成严重破坏。
  • CollisionVolume 实际上是一个基类（不一定是），其他类从它派生出来，比如盒子/球体等等。我可能不使用继承并提出其他一些复杂的设计，但这是需要牢记的。

我努力寻找解决方法，但最终改为存储指针：

std::vector<PhysicsBody*> m_bodies;
std::vector<CollisionVolume*> m_colliders;

我想出的最小化缓存未命中的最佳解决方案是重载 new/delete 并将这些对象存储在内存池中，仅用于物理系统。

还有其他更好的解决方案吗？显然，性能是关键。

4

3 回答 3

2

一个基本问题：在没有线程运行和修改来自不同内核 (CPU) 的数据的情况下，您认为需要关注缓存一致性成本吗？

仅当线路在与读取器核心不同的核心上变脏时才会触发缓存一致性协议，反之亦然。

看来您实际上是指缓存局部性？那正确吗？

具有一致性 Vs。不碍事的地方，这是我的看法：

当您进入向量时，您就失去了对管理位置的直接控制。你可以通过一个内存池来取回其中的一部分。尽管如此，您仍将不得不应对与调整大小操作相关的重定位。

你知道前期元素的数量吗？如果是，您可以这样做。

vector<T> myVec;
myVec.reserve(NUM_ELEMS);

其次是从内存的连续区域为每个对象就地新建。

myvec[i] = ...

向量和元素的内存也可以完全来自单个池。这可以通过在实例化 std::vector 时传入自定义分配器来实现。请参阅以下内容：

于 2015-04-30T07:24:02.803 回答
0

无论您是否计划使用矢量引擎 (GPU) 进行计算，我想指出数据模型的显着差异。典型的数据布局遵循 OOP，称为结构数组。为了使用某种矢量引擎，将数据重组为数组结构。更多来自英特尔的主题

https://software.intel.com/en-us/articles/creating-a-particle-system-with-streaming-simd-extensions

于 2015-05-01T15:02:29.260 回答
0

避免丢失 mem 局部性并将内存块融合在一起以更好地命中缓存的一种简单方法是简单地将您删除的物理元素保留在向量中以避免使索引无效，但将它们标记为removed以便您可以在后续插入时回收这些空白空间.

在这里，如果您想走完整的路线来制作自己的容器，如果您仍然想在这些已删除的对象上调用析构函数以了解如何使用“放置新”和手动调用析构函数来实现 STL 容器，这真的很有帮助避免需要类型 T 的赋值运算符之类的东西。

您还可以在插入新索引时将它们推送到空索引列表中以回收，或者更快地将这些元素视为列表指针的联合，如下所示：

union PhysicsNode
{
    PhysicsBody body;
    PhysicsNode* next_free;
};
PhysicsNode* free_physics_nodes;

碰撞节点也是如此。在这种情况下，当它被“占用”时，您将把这个 PhysicsNode 当作​​一个 PhysicsBody 来对待，而当它是“空置”或“空闲”时，你将它当作一个单链表节点来回收。

不幸的是，试图在这个级别解决问题通常会让你弄乱面向对象的设计、构造函数和析构函数机制等。

因此，当您想要这种效率以及所有面向对象编程的好东西时，您可能会想在内存分配器级别以基本相同的方式解决这个问题。

于 2015-05-01T14:42:45.613 回答