Эффективная структура для представления иерархии преобразования

Кто-нибудь может предложить эффективный для памяти способ представления дерева матриц, например, в иерархической модели?

Я особенно стремлюсь сохранить локальность данных, и я подозреваю, что подход типа структура массивов (матрицы и индексы для матриц) может быть подходящим.

Как и многие цепные матричные вычисления, эта структура, вероятно, будет скопирована в памяти довольно много, поэтому наличие непрерывного хранилища будет большим бонусом.

Дерево как массив звучит как победа для меня. Просто выполните глубинный обход вашей иерархии и заполните массив; при перемотке через рекурсию вы можете либо обновить родительский элемент с абсолютным индексом на child, либо просто delta-from-me, а потомки также могут хранить родительские индексы в любом случае. Действительно, если вы используете относительные смещения, вам не нужно переносить корневой адрес. Я полагаю, что структура будет выглядеть примерно так

struct Transform
{
   Matrix m; // whatever you like
   int parent;   // index or offset, you choose!
   int sibling;
   int firstchild;
};

... так что вам нужно, чтобы узлы тоже знали, как добраться до братьев и сестер, поскольку вы не можете (легко) иметь структуру переменного размера. Хотя я предполагаю, что если вы используете смещения байтов вместо смещений Transform, у вас может быть переменное число дочерних элементов на преобразование:

struct Transform
{
   Matrix m; // whatever you like
   int parent;  // negative byte offest
   int numchildren;
   int child[0]; // can't remember if you put a 0 there or leave it empty;
                 // but it's an array of positive byte offsets
};

... тогда вам просто нужно убедиться, что вы разместили последовательные преобразования в нужном месте.

Вот как вы строите полностью автономное дерево со встроенными дочерними «указателями».

int BuildTransforms(Entity* e, OutputStream& os, int parentLocation)
{
    int currentLocation = os.Tell();

    os.Write(e->localMatrix);
    os.Write(parentLocation);
    int numChildren = e->GetNumChildren();
    os.Write(numChildren);

    int childArray = os.Tell();
    os.Skip(numChildren * sizeof(int));
    os.AlignAsNecessary();  // if you need to align transforms

    childLocation = os.Tell();
    for (int i = 0; i < numChildren; ++i) {
        os.Seek(childArray + (i * sizeof(int)));
        os.Write(childLocation);
        os.Seek(childLocation);
        childLocation = BuildTransforms(e->GetChild(i), os, currentLocation);
    }

    return os.Tell();
}

void BuildTransforms(Entity* root)
{
    OutputStream os;
    BuildTransforms(root, os, -1, 0);
}

(Если вы хотите сохранить относительные местоположения, просто добавьте - currentLocationдве записи "location".)

Индексирование по массиву матриц, вероятно, было бы самым прямым и эффективным способом использования памяти.

Цепочка преобразований может храниться в LIFO в виде последовательности указателей или целых чисел или другой небольшой структуры, которая указывается в матричном массиве. Это поможет предотвратить сохранение избыточных матриц и отделит код хранения данных от кода доступа к данным.

В конечном итоге вы просто нажмете и извлечете значения индекса из LIFO, чтобы сохранить или воспроизвести свою цепочку преобразования.

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