Треугольники и память

В эру гига- и терабайтов как-то стало не принято заботиться о том, сколько памяти потребляют данные в памяти. Работы по оптимизации зачастую намного дороже дополнительной ОЗУ и программисты чувствуют себя вольготно, пока не происходит что-то экстраординарное, вроде достижения лимита памяти на процесс на x86 ОС. В такие моменты мы хватаемся за голову (или профайлер) и смотрим, что же поглотило заветные мегабайты.
Эта история о подобном случае, когда хранение 3D моделей в памяти стало неоправданно дорогим из-за избыточности самого распространенного примитива - треугольника.

Для удобства чтения я буду писать код на C#, хотя все описанное можно повторить и в C++, и в Delphi и пр., за исключением последнего абзаца.

Все началось с того, что модели надо не только хранить, но и обрабатывать, потому к каждому треугольнику добавились данные вроде вектора нормали, граничных точек, коэффициенты и пр.:

struct Triangle
{
        public Vector A;
        public Vector B;
        public Vector C;
        public bool TwoSided;

        float ND;
        float Reci;
        Vector Normal;
        byte K;
        byte U;
        byte V;
        Vector LowerBound;
        Vector UpperBound;
}

Значения K, U, V - номера сторон треугольника, Normal - вектор нормали, LowerBound и UpperBound - границы описанного параллелепипеда, а остальные коэффициенты нужны для просчета коллизий. Vector содержит три переменные типа float, т.е. занимает 12 байт, а вся указанная структура занимает 88 байт*. При наличии 10 миллионов треугольников (а это вполне возможно, если мы храним не одну сцену, а весь игровой мир) они все занимают 880+ мегабайт ОЗУ. Если это слишком много, то самым правильным и простым решением будет переход на 64-битную архитектуру, в которой это значение - лишь капля в море. Но если же нам дорог каждый мегабайт, то можно заняться неблагодарным делом оптимизации :)

Первое, что сразу приходит в голову - использовать внешний массив с вершинами - треугольники в модели почти всегда имеют 2-3 общие вершины с соседями. Мы испольузуем три индекса и одну ссылку на массив вершин. Получится всего 16 байт вместо 36 на вершины, но надо не забывать, что сами вершины от этого не исчезнут и должны хранится в неких внешних массивах. При соотношении вершин и треугольников 1 к 3 выходит, что у нас есть отдельно 40 мегабайт вершин, а треугольники занимают теперь 680 мегабайт.
Затем мы можем убрать вектор нормали и вычислять его при необходимости. Также известно, что значения U и V могут быть вычислены из значения K. Таким образом, структура будет занимать уже 56 байт, значит мы уменьшили потребление с 880 до 600 мегабайт, т.е. примерно на 32%, что уже очень неплохо. В общих случаях на такой структуре можно было бы и остановиться:

struct Triangle
{
        public int A;
        public int B;
        public int C;
        public Vector [] VertexBuffer;
        public bool TwoSided;

        float ND;
        float Reci;
        byte K;
        Vector LowerBound;
        Vector UpperBound;
}

Следующие шаги уже довольно нетривиальны. У нас есть Bounding Box треугольника, заданный двумя точками - LowerBound и UpperBound. Координаты этих точек составляются из шести координат вершин (наибольшее и наименьше значение X, Y и Z), потому мы можем сказать, что для описания этого бокса достаточно хранить 6 индексов:

int lbx = MinIndex(A.X, B.X, C.X);
int lby = MinIndex(A.Y, B.Y, C.Y);
int lbz = MinIndex(A.Z, B.Z, C.Z);
int ubx = MaxIndex(A.X, B.X, C.X);
int uby = MaxIndex(A.Y, B.Y, C.Y);
int ubz = MaxIndex(A.Z, B.Z, C.Z);

int MaxIndex(float a, float b, float c)
{
     return a > b ? a > c ? 0 : 2 : b > c ? : 1 : 2;
}

int MinIndex(float a, float b, float c)
{
     return a < b ? a < c ? 0 : 2 : b < c ? : 1 : 2;
}

Эти индексы принимают значения от 0 до 2, т.е. занимают по 2 бита каждый и могут быть упакованы в два байта данных:

LowerBoundPack = (byte) ((lbx) | (lby << 2) | (lbz << 4));
UpperBoundPack = (byte) ((ubx) | (uby << 2) | (ubz << 4));

Назад в векторы эта данные превращаются довольно просто:

Vector[] abc = {A, B, C};

byte lbx = (byte) (m_lowerBoundPack & 0x3);
byte lby = (byte) ((m_lowerBoundPack >> 2) & 0x3);
byte lbz = (byte) ((m_lowerBoundPack >> 4) & 0x3);

byte ubx = (byte) (m_upperBoundPack & 0x3);
byte uby = (byte) ((m_upperBoundPack >> 2) & 0x3);
byte ubz = (byte) ((m_upperBoundPack >> 4) & 0x3);

Vector lb = new Vector(abc[lbx].X, abc[lby].Y, abc[lbz].Z);
Vector ub = new Vector(abc[ubx].X, abc[uby].Y, abc[ubz].Z);

Но при этом индексы занимают по 6 бит из 8ми, потому мы можем спокойно записать флаг TwoSided и значение K в неиспользованные биты:

LowerBoundPack |= (byte)(K << 6);
if (TwoSided)
    UpperBoundPack |= 0x40;

Таким образом структуру мы сократили до 28 байт:

struct Triangle
{
        public int A;
        public int B;
        public int C;
        public Vector [] VertexBuffer;

        float ND;
        float Reci;
        byte LowerBoundPack;
        byte UpperBoundPack;
}

В памяти наши треугольники будут занимать 280 мегабайт + 40 мегабайт вершин, т.е. 320 мегабайт, что на 63% меньше, чем изначальный вариант.
На этом можно было бы и остановиться, но есть еще один интересный нюанс. По статистике, модели с количеством вершин более 65536 составляют примерно 2% от общего числа, а около 95% моделей содержит от 256 до 65535 с вершин. Выходит, что использовать 32-битные индексы откровенно расточительно. Также нет особой необходимости хранить ссылку на буфер с вершинами для каждого треугольника - это свойство самой модели и должно храниться в ней.

На помощь придут темплейты в C++ или дженерики в C# **:

struct Triangle<T> where T : struct, IConvertible
{
    public T A;
    public T B;
    public T C;

    byte LowerBoundPack;
    byte UpperBoundPack;
    float ND;
    float Reci;
}

Такая структура потребует некоторых нюансов в обработке, а также придется использовать ссылку на VertexBuffer из объекта модели. В случае T = short размер структуры будет 16 байт, а для T = int - 24 байта. Таким образом, в памяти наши треугольники с вершинами займут ~200 мегабайт, что в 4.4 раза меньше, чем в изначальной задаче, т.е. оптимизация составила 77% использования памяти.

Стоило ли это того? На первый взгляд стоило, но код обработки таких треугольников стал выполнятся немного медленее и заметно потерял в читаемости. Вывод прост - надо знать меру во всем, даже в оптимизациях. :)

---

* Все размеры структур в памяти даны с учетом выравнивания и указанного порядка переменных. К примеру, "ручной" подсчет в первой структуре дает 83 байта, т.е. простая перестановка позволила бы получить размер структуры 84 байта
** Для параметра T нужно требование IConvertible, чтобы можно было привести переменные типа T к int с помощью подобной конструкции:

int a = Convert.ToInt32(A);