Triangles and Memory

For readability I’ll write the code in C#, although everything described here can just as easily be done in C++, Delphi, and so on, with the exception of the last paragraph.

It all started with the fact that models don’t just need to be stored, they need to be processed, so each triangle picked up extra data like a normal vector, boundary points, coefficients, and so on:

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

The values K, U, V are the triangle’s side indices, Normal is the normal vector, LowerBound and UpperBound are the bounds of the containing box, and the remaining coefficients are needed for collision calculations. Vector holds three float variables, i.e. it takes up 12 bytes, and the whole structure above takes up 88 bytes*. With 10 million triangles (which is entirely possible if we’re storing not just one scene but an entire game world), that’s 880+ megabytes of RAM. If that’s too much, the simplest and most correct fix is to move to a 64-bit architecture, where this figure is just a drop in the ocean. But if every megabyte matters to us, we can get into the thankless business of optimization 🙂

The first thing that comes to mind is to use an external vertex array – triangles in a model almost always share 2-3 vertices with their neighbors. We use three indices and one reference to the vertex array. That gets us down to just 16 bytes instead of 36 for the vertices, but keep in mind the vertices themselves don’t disappear – they still have to live in some external array. With a vertex-to-triangle ratio of 1 to 3, we end up with 40 megabytes of vertices on the side, while the triangles now take up 680 megabytes.
Next we can drop the normal vector and compute it on demand. It’s also known that the U and V values can be derived from K. That way the structure will take up just 56 bytes, meaning we’ve cut consumption from 880 down to 600 megabytes, i.e. roughly 32%, which is already quite good. In most cases you could stop right there with a structure like this:

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

The next steps are considerably less trivial. We have the triangle’s bounding box, defined by two points – LowerBound and UpperBound. The coordinates of these points are assembled from six vertex coordinates (the smallest and largest X, Y, and Z values), so we can say that storing 6 indices is enough to describe this box:

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

These indices only take values from 0 to 2, i.e. 2 bits each, so they can be packed into two bytes of data:

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

Turning this data back into vectors is fairly simple:

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

But since the indices only use 6 of the 8 bits, we can happily store the TwoSided flag and the K value in the unused bits:

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

This way we’ve cut the structure down to 28 bytes:

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

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

In memory our triangles will now take up 280 megabytes + 40 megabytes for vertices, i.e. 320 megabytes, which is 63% less than the original version.
We could stop here, but there’s one more interesting wrinkle. Statistically, models with more than 65536 vertices make up only about 2% of the total, and around 95% of models have somewhere between 256 and 65535 vertices. So it turns out that using 32-bit indices everywhere is frankly wasteful. There’s also no real need to store a reference to the vertex buffer in every single triangle – that’s a property of the model itself and should be stored there instead.

Templates in C++ or generics in C# come to the rescue here **:

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

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

A structure like this requires some care in how it’s handled, and you’ll also have to use a reference to the VertexBuffer from the model object. For T = short the structure size becomes 16 bytes, and for T = int, 24 bytes. So in memory our triangles plus vertices will now take up ~200 megabytes, which is 4.4 times less than in the original problem, i.e. the optimization amounts to a 77% reduction in memory usage.

Was it worth it? At first glance, yes, but the code that processes these triangles ended up running a bit slower and noticeably lost some readability. The conclusion is simple – moderation matters, even in optimization. 🙂

---

* All structure sizes in memory are given with alignment and the stated variable order taken into account. For instance, a “manual” count for the first structure gives 83 bytes, i.e. simply reordering the fields would have gotten the structure down to 84 bytes
** The T parameter requires the IConvertible constraint so that variables of type T can be cast to int using a construct like this:

int a = Convert.ToInt32(A);