Optimizing Geometry for the 64-bit Platform

At first the system was prototyped without any optimizations. Then we decided to stop storing coordinates directly in the triangle – we created a shared vertex pool for each model, and triangles held only references into it. As a second step we did the same thing for the tree leaves – replacing triangles with references into a shared pool. That’s exactly when we noticed the excessive memory consumption, especially in x64 mode.
In simplified terms, the tree was an array of arrays of pointers to triangles, each of which was an array of three pointers to vertices. In C++ that can be written, roughly, as:

typedef Vertex** Triangle;
typedef Triangle** Leaf;
typedef Leaf* Tree;

The declaration

Tree m_tree;

is equivalent to

Vertex ***** m_tree;

That looks pretty scary :). For clarity, we can use STL and a made-up stdext::triplet template and write it like this:

typedef stdext::triplet<Vertex*, Vertex*, Vertex*> Triangle;
typedef std::vector<Triangle*> Leaf;
typedef std::vector<Leaf> Tree;

The declaration

Tree m_tree;

is equivalent to

std::vector<
    std::vector<
        stdext::triplet<Vertex*, Vertex*, Vertex*>* > >
           m_tree;

Of course, in the real system the triangle, leaf, and tree are separate classes with their own properties and methods, but right now what matters to us is the nesting structure, the hierarchy. It’s not hard to guess that each pointer takes 4 bytes on the x86 architecture and 8 bytes on x64. And we ended up with a lot of pointers, which is what drove the substantial memory usage.
Server-side geometry often uses simplified models – it doesn’t much matter whether a window frame is included when computing an NPC’s path, and the number of polygons in a tree trunk barely affects the line-of-sight calculation near it. That’s why models tend to be small – it’s rare for a model to have several thousand vertices. It follows that 16-bit indices would be enough to address vertices and triangles, whereas on an x64 system we were using 64-bit pointers.

The next step in the optimization was fairly predictable – we replaced the most frequently used references with unsigned short indices, which cut the hierarchy’s memory usage by 2x on x86 systems and 4x on the x64 architecture. As a next step we built template classes that let us use any type as an index: depending on a model’s complexity, we create either a Tree<unsigned char> or a Tree<unsigned short>. It’s more convenient to split more complex models into parts than to store them with 32-bit indices. Over 50% of the models in our test project fell into the 8-bit index category. Compared to the original pointer-based version, the difference turned out to be enormous.

Now for some numbers:

8-bit: models 5140, leafs 157489, leaf references 899038, triangles 409962
16-bit: models 4376, leafs 2950551, leaf references 13938081, triangles 6774482

That means we previously had 21553332 vertex pointers and 14837119 triangle pointers, which at 64 bits comes to 291123608 bytes, or roughly 277 megabytes of data.
After the optimization, that became 1229886 8-bit vertex indices, 20323446 16-bit ones, 899038 8-bit triangle pointers, and 13938081 16-bit ones. In total that’s 70651978 bytes, or roughly 67 megabytes of data. A win of more than 4x on the 64-bit architecture.

There were other optimizations too – for instance, in the tree, the array of leaves was turned into a single array of triangle indices with a delimiter – but the biggest gain by far came from dropping pointers in favor of indices.