Struktur yang efisien untuk mewakili hierarki transformasi

Adakah yang bisa menyarankan cara efisien memori untuk mewakili pohon matriks, misalnya dalam model hierarki?

Saya sangat tertarik untuk melestarikan lokalitas data, dan saya menduga pendekatan tipe struktur-array (matriks & indeks ke matriks) mungkin cocok.

Seperti halnya banyak perhitungan matriks berantai, struktur ini mungkin akan disalin dalam memori sedikit, sehingga memiliki penyimpanan yang berdekatan akan menjadi bonus besar.

Tree-as-array kedengarannya seperti kemenangan bagi saya. Lakukan saja traversal mendalam-pertama pada hierarki Anda dan isi sebuah array; ketika memutar ulang melalui rekursi Anda dapat memperbarui induk dengan indeks absolut untuk anak atau hanya delta-dari-saya, dan anak-anak dapat menyimpan indeks induk juga. Memang, jika Anda menggunakan offset relatif maka Anda tidak perlu membawa alamat root. Saya kira strukturnya mungkin akan terlihat seperti

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

... jadi Anda akan memerlukan simpul untuk mengetahui cara mendapatkan saudara juga karena Anda tidak dapat (dengan mudah) memiliki struktur ukuran variabel. Meskipun saya kira jika Anda menggunakan byte offset alih-alih Transform offset, Anda bisa memiliki jumlah variabel anak per transformasi:

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
};

... maka Anda hanya perlu memastikan bahwa Anda meletakkan Transformasi berturut-turut di tempat yang tepat.

Inilah cara Anda membangun pohon yang serba lengkap dengan "pointer" anak tertanam.

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);
}

(Jika Anda ingin menyimpan lokasi relatif, cukup tambahkan - currentLocationke dua "lokasi" tulis.)

Pengindeksan ke dalam array matriks mungkin akan menjadi pendekatan yang paling lurus ke depan, efisiensi memori.

Rantai transformasi dapat disimpan dalam LIFO sebagai serangkaian pointer atau bilangan bulat atau struct kecil lainnya yang diindeks ke dalam array matriks. Ini akan membantu mencegah penyimpanan matriks yang berlebihan dan akan memisahkan kode penyimpanan data dari kode aksesor data.

Pada akhirnya Anda hanya akan mendorong dan mengeluarkan nilai indeks dari LIFO untuk menyimpan atau memutar rantai transformasi Anda.

Anda mungkin juga dapat menghemat sedikit memori jika struktur matriks Anda juga dapat berisi tipe transformasi ... rotasi, terjemahan, dll. Jika tidak, tipe tersebut harus disimpan dengan indeks yang menghasilkan duplikasi yang lebih mungkin.