Friday, July 18, 2014

COLLADA Deindexer

Some weeks ago, when I tried to use COLLADA Refinery I was surprised that it’s no more working (I think it’s because of my update from windows 8 to windows 8.1), since I was mainly focusing of adding new features to my 3D engine, I didn’t want to spend lot of time with this problem, so I tried to look for a quick solution in the internet but without success, I then tried to recompile the source code of COLLADA Refinery, reinstall jre and clean everything related to COLLADA Refinery... but also without succeeding to launch it.

I was mainly interested on the deindexer conditioner of COLLADA Refinery, and because all my attempts to fix quickly the problem failed, I decided to write my own deindexer instead of losing more time looking for a solution.

Before sharing with you my deindexer I will try to explain what is a deindexer, and why do we need it.
Let’s consider the following polygon:

Our polygon is composed of two triangles [v0, v2, v3] and [v0, v1, v2]. We will consider that each vertex has two attributes, position (p) and texture coordinates (t).

V0: p0[0, 0, 0], t0[0, 0];
V1: p1[0, 1, 0], t1[0, 0.5];
V2: p2[1, 1, 0], t2[0.5, 0.5];
V3: p3[1, 0, 0], t3[0.5, 0];

This polygon can be stored in three ways:

-       Without indexation:

Our data without indexation is as follow:
[v0, v2, v3, v0, v1, v2] = [p0, t0, p2, t2, p3, t3, p0, t0, p1, t1, p2, t2] = [0, 0, 0, 0, 0, 1, 1, 0, 0.5, 0.5, 1, 0, 0, 0.5, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0.5, 1, 1, 0, 0.5, 0.5] ;
As you see v0 and v2 are shared between the two triangles, that’s why p0, t0 and p2, t2 are repeated two times which is a waste of memory (imagine the case of a polygon with thousands of vertices).
If every element is 4 bytes the size of the data buffer is going to be 120 bytes.

-        Multiple indices per vertex:

In this mode we will store the position and texcoord in two separated buffers:
Position: [p0, p1, p2, p3] = [[0, 0, 0], [0, 1, 0], [1, 1, 0], [1, 0, 0]];
Texture coordinates: [t0, t1, t2, t3] = [[0, 0], [0, 0.5], [0.5, 0.5], [0.5, 0]];

We now need to represent the polygon by using these two buffers. To do this we should use a new buffer called the index buffer that will represent every vertex with two indices (one for the position and the other for texture coordinates).

Index buffer: [0, 0, 2, 2, 3, 3, 0, 0, 1, 1, 2, 2] -- the index of p0 is 0, p1 is 1… the same of t.

In this example the indices of position and texture coordinates are equal for every vertex - please not that this is not always the case.

if every element in position and texture coordinate is 4 bytes and every element in the index buffer is 2 bytes the size of our data is going to be 104 bytes.

-        One index per vertex:

Instead of using one index for every attribute (position, texcoord, normal…) we will use one index for every vertex.

Index buffer: [0, 2, 3, 0, 1, 2] -- 0 is the index of v0, 1 for v1…

if the size of one vertex is 20 bytes and the size of every element in the index buffer is 2 bytes, the data size is going to be 92 bytes.

As you see the size of data that use the index buffer is always smaller than data without index buffer.

COLLADA file format use multiple indices per vertex however my engine (as the majority of game engines) use one index per vertex, so the need to create a tool that can do the conversion.

The pseudo code of my deindexer is as below:

Struct Vertex{
      Vec3 position;
      Vec3 normal;
      Vec2 texCoord;

unsigned short positionIdx[N]; // input index buffer of position
unsigned short normalIdx[N]; // input index buffer of normal
unsigned short texCoordIdx[N]; // input index buffer of texture coordinates

Vec3 positionIn[N1]; // input position buffer
Vec3 normalIn[N2]; // input normal buffer
Vec2 texCoordIn[N3]; // input texture coordinates

Dictionary dico = Dictionary<Vertex, unsigned short>(); // We will store in this Dictionary distinct vertices and their indices in the data

List<unsigned short> indicesOutput; // ouput index buffer

for(int i = 0; i < N; ++i)
    Vec3 position = positionIn[positionIdx[i]];
    Vec3 normal =  normalIn[normalIdx[i]];
    Vec2 texCoord =  texCoordIn[texCoordIdx[i]];
    Vertex v(position, normal, texCoord);
    if(v exists in the dico)
       - We will simply add the index of v retrieved from dico to indicesOutput.
      - add a new index to indicesOutput (the new index is simply the number of elements in dico).  
      - Add v to dico.

Finally here is the link to the code source of my deindexer created using C#:

I'm not a C# guru but I like to use this language to create tools quickly. It's also an opportunity for me to gain more experience in this language.

Please note:
- I use COLLADA files exported with OpenCOLLADA plugin as input to the deindexer.
- Tangent/Bitangent export is not yet supported.