Как применить Data-Oriented Desing, когда структура содержит различное количество элементов во внутреннем векторе?

Question

Я хотел бы применить Data-Oriented Design (на основе, например, этой статьи) к моему простому физическому движку. И я сосредоточен на оптимизации тестирования столкновений, так как это самая дорогая его часть.

Я организовал ограничивающие сферы, которые могут столкнуться с игроком в один 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;

и я проверяю столкновения с ними внутри одной функции / метода. На данный момент мне все ясно.

Проблема в том, что у меня также есть некоторые более общие структуры, такие как:

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 общая структура, например, серии треугольников (поскольку во многих вычислениях она быстрее разделенных треугольников).

Что мне тогда делать? Я хочу следовать духу Data-Oriented Design и эффективно использовать память / кеш с моим Polygon,

Нужно ли избавляться от внутреннего vector (points)? Как если так?

Answer 1

На этот вопрос не может быть однозначного ответа, так как для этого потребуются знания о том, как вы обращаетесь к данным с точки зрения того, когда они инициализируются, могут ли они быть изменены после этапа инициализации, и многих других. Однако, если ваши данные относительно стабильны и вы обращаетесь к своим полигонам согласованным образом, просто перебирая все полигоны или полигоны, принадлежащие одному конкретному объекту, один из подходов может состоять в том, чтобы поместить точки ваших полигонов в отдельный вектор и просто иметь полигоны хранят начальный и конечный индексы для этого массива.

Таким образом, есть несколько вещей, которые должны быть доступны во время обхода. Сначала индексы хранятся в многоугольниках. Во-вторых, сами точки. Оба этих доступа, вероятно, будут дружественными к кешу, если полигоны также расположены в векторе. Аналогичный подход может быть применен к наборам полигонов - просто храните полигоны в векторе и имейте пару (начало, конец) в ваших игровых объектах.