当结构包含内部向量中不同数量的元素时，如何应用面向数据的设计？

Question

我想将面向数据的设计（基于 this article）应用于我的简单物理引擎。我专注于优化碰撞测试，因为它是其中最昂贵的部分。

我已经将可能与玩家碰撞的边界球体组织成单个 vector:

struct Sphere{ //I don't split sphere into parts, 
    //as I usually access both position and radius in my calculations
    Point3D position;
    float radius;
};
std::vector<BoudingSphere> spheres;

并且我在 single function/method 中测试了与它们的碰撞。到那时，一切对我来说都很清楚。

问题是，我还有一些更通用的结构，例如：

struct Polygon{ //it may e.g. represents the area or be used for more precise tests      
    std::vector<Point2D> points;
};

我想以同样的方式创建 std::vector<Polygon> 并不是一个好的做法，因为嵌套的 vector (points) 会在内存中占据很多位置 (保留它）。

另一方面，我不能假设总是有 2、3、4 或 10 个点（差别很大，最多约 20 个，但通常要少得多）。

我不想从Polygon通用结构切换到例如一系列三角形（因为在许多计算中它比分开的三角形更快）。

那我该怎么办？我想遵循面向数据设计的精神，并在我的 Polygon.

中有效地使用 memory/cache

我必须摆脱内部 vector (points) 吗？如果是这样怎么办？

Answer 1

这个问题没有明确的答案，因为它需要了解您访问数据的方式，例如何时初始化、是否可以在初始化阶段后更改等等。但是，如果您的数据相对稳定并且您正在以一致的方式访问多边形，只是遍历所有多边形或属于一个特定对象的多边形，一种方法可能是将多边形的点放入一个单独的向量中，并且只需要多边形将开始和结束索引存储到该数组。

这样，在遍历过程中需要访问一些东西。首先，索引存储在多边形中。第二，要点本身。如果多边形也布置在矢量中，那么这两种访问都可能是缓存友好的。类似的方法可以应用于多边形集——只需将多边形存储在一个向量中，并在你的游戏对象中有一个（开始，结束）对。

当结构包含内部向量中不同数量的元素时，如何应用面向数据的设计？

How to apply Data-Oriented Desing when an structure contains various number of elements in inner vector?

c++

memory

vector

data-oriented-design