valentsys.site

# COLLADA2BIN converter using the TinyXML parser

## Introduction

This project is based on the ["COLLADA, TinyXML, and OpenGL"](https://www.codeproject.com/articles/625701/collada-tinyxml-and-opengl) program by Matt Scarpino. The code posted here, extends the one from the original article, by adding parsing for the `<library_controllers>`, `<library_visual_scenes>` and `<library_animations>` sections of a collada file. You can read the full COLLADA specification from [here](https://www.khronos.org/files/collada_spec_1_4.pdf).

The program discussed here is a converter, which takes a COLLADA "*.dae" file and a outputs a binary file, with a custom specific format. It was intented to be used as a tool alongside another project &ndash; a game engine.

This document describes the types and functions in the converter code, as well as the binary format.

## Custom types

```cpp
typedef float vec3[3];
typedef float vec4[4];
typedef float mat4[16];
```

## Structs and classes 

### The `source_data` class
A source node declares a data repository that provides values according to the semantics of an `<input>` element that refers to it. The source node contains a data array node, which can be one of the following types: `<IDREF_array>`, `<Name_array>`, `<bool_array>`, `<float_array>` or an `<int_array>`. Additionally, it contains a `<technique_common>` node, which holds information on how to read the data array.

Here is an example of a `<source>` element that contains an array of floating-point values that compose a single RGB color:
```xml
<source id="color_source" name="Colors">
  <float_array id="values" count="3">0.8 0.8 0.8</float_array>
  <technique_common>
    <accessor source="#values" count="1" stride="3">
      <param name="R" type="float"/>
      <param name="G" type="float"/>
      <param name="B" type="float"/>
    </accessor>
  </technique_common>
</source>
```
The `source_data` abstract class describes a collada `<source>` node. 

```cpp
class source_data {
  public:
    source_data();
    ~source_data();
    
    unsigned int semantic;
    unsigned int size;
    unsigned int stride;
    virtual void* data() const=0;
};
```

#### The `num1D_data` class
The `num1D_data` class is a `source_data` type, that holds a numerical array, like a float array or an int array.
```cpp
class num1D_data: public source_data {
  public:
    num1D_data(): source_data(){ ... }
    ~num1D_data();

    GLenum gltype;
    void* num_data;
    virtual void* data() const;
};

```
#### The `names_data` class
The `names_data` type holds a names string array.
```cpp
class names_data: public source_data {
  public:  
  names_data(): source_data(){ ... }
    ~names_data();

    char** name_data;    
    virtual void* data() const;
};
```

### The `raw_geom` class
An `raw_geom` object describes a parsed `<geometry>` node. In general, the `<geometry>` element categorizes the declaration of geometric information. Computer graphics hardware has been normalized, primarily, to accept vertex position information with varying degrees of attribution (color, normals, etc.). Geometric descriptions provide this vertex data with relative directness or efficiency. Some of the more common forms of geometry are: *b-spline*, *bezier*, *mesh*, *nurbs*, *patch*. Currently, COLLADA supports only polygonal meshes and splines.

Here is an example of an empty mesh `<geometry>` element with the allowed attributes:
```xml
<library_geometries>
  <geometry name="cube" id="cube123">
  <mesh>
    <source id="box-Pos"/>
    <vertices id="box-Vtx">
      <input semantic="POSITION" source="#box-Pos"/>
    </vertices>
  </mesh>
  </geometry>
  ...
</library_geometries>
```
The `raw_geom` class supports only meshes, with an arbitrary number of attributes and several different types of primitives: `GL_LINES`, `GL_LINE_STRIP`, `GL_TRIANGLES`, `GL_TRIANGLE_FAN`, `GL_TRIANGLE_STRIP`. The mesh attributes are described with the `<input>` elements, which in turn reffer to a `<source>` element, containing the attribute values.

```cpp
class raw_geom {
  public:
    raw_geom();
    ~raw_geom();

    std::string name;
    num1D_data* sources;
    unsigned int num_sources;
    GLenum primitive;
    int index_count;
    unsigned int input_count;
    unsigned short* indices;
};
```

### The `joint` class
The `joint` class describes a parsed armature joint data. It contains the joint's name, the inverse bind transform to object space, the local transform in joint space, keyframe transforms data, and joint hierarchy information.  

```cpp
class joint{
  public:
    joint();
    ~joint();

    std::string name;
    int joint_arr_index;
    int num_child_joints;
    
    mat4 transform;
    mat4 inv_bind_transform;
    
    num1D_data* keyframe_transforms;
    num1D_data* keyframe_timestamps;
    
    joint* parent_joint;
    joint** child_joints;
};
```

### The `armature_ctl` class
The `armature_ctl` class holds the data of a parsed mesh armature controller. It contains information about the armature joints hierarchy and joint-to-mesh-vertex association data, like weights and indices.

```cpp
class armature_ctl{
  public:
    armature_ctl();
    ~armature_ctl();

    int num_joints;
    vec3 pos, scale;
    vec4 rotx, roty, rotz;
    
    names_data* joint_names;
    joint* joints;
    joint* root_joint;

    num1D_data* joint_inv_transforms;
    num1D_data* vertex_joint_assoc;
    num1D_data* vertex_joint_weights;
};
```

### The `mesh` class
A `mesh` object describes a fully parsed mesh, with its associated armature controller, vertices and indices list.

```cpp
class mesh {
  public:
    mesh();
    ~mesh();
    raw_geom* raw;
    armature_ctl* armature_ctl;
    std::vector<vertex> vertices;
    std::vector<unsigned int> indices;
};
```
### The `vertex` struct
The `vertex` struct describes a fully processed mesh vertex. The indices array holds the raw geometry attribute source indices for the vertex. 

```cpp
struct vertex{
  bool seen;
  vertex* twin;
  unsigned int* indices;
};
```
A vertex may be part of two primitives, in which case it may require to have a twin vertex. Notice the `twin` property.

## Reading data from the COLLADA document

### The `<library_geometries>` section

The `<library_geometries>` section of the COLLADA document contains a collection of geometry objects, each described by a `<geometry>` element.

At this point, our program works only with mesh-based geometries, which are defined with a `<mesh>` child node. 

The mesh node contains several `<source>` elements, which describe the mesh vertex attributes, a `<vertices>` element, which declares the vertices main attribute (its position), and and another element, which describes how to form vertices and primitives. The other element, can be one of the following: `lines`, `linestrips`, `polygons`, `polylist`, `triangles` , `trifans`, or `tristrips`.

Each of the previously mentioned primitive nodes holds the information on how to form primitives from the mesh vertices, and also how to form the individual vertices using the attribute sources. The `<vcount>` child element contains a list of integers, each specifying the number of vertices for one primitive. The `<p>` node contains a list of integers that specify the vertex attributes for an individual vertex. For example, a vertex with position index `i`, in the positions source array, normal with index `j` in the normals source array, and uv coord `k` in the uvs source will be described as `i j k` in the `<p>` element array.

An example `<geometry>` element with `polylist` primitives:
```xml
<library_geometries>
  <geometry name="..." id="...">
  <mesh>
    <!-- positions float_array -->
    <source id="pos-attr-data"> ... </source>
    <!-- normals float_array -->
    <source id="normals-attr-data"> ... </source>
    <!-- uvs float_array -->
    <source id="uvs-attr-data"> ... </source>        
    <!--declares the attributes and identity of mesh-vertices-->
    <vertices id="mesh-vertices">
      <input semantic="POSITION" source="#pos-attr-data"/>
    </vertices>
    <polylist material="..." count="1420">
      <input semantic="VERTEX" source="#mesh-vertices" offset="0"/>
      <input semantic="NORMAL" source="#normals-attr-data" offset="1"/>
      <input semantic="TEXCOORD" source="#uvs-attr-data" offset="2" set="0"/>    
      <vcount> ... </vcount>
      <p> ... </p>
    </polylist>
  </mesh>
  </geometry>
  ...
</library_geometries>
...
```

#### The `read_mesh_geometries` function

```cpp
void read_mesh_geometries(TiXmlDocument* colladaDoc, mesh* meshes, const int meshesCount)`;
```
The `read_mesh_geometries` function parses the `<library_geometries>` section and creates an output `mesh` array, containing all mesh geometries. Note, that the new mesh objects will go on further processing, because at this stage, only the `raw` property (`raw_geom` type) gets initialized. 

This function essentially creates new `raw_geom` objects, and then assigns them to the newly created mesh objects. First, all the sources from the `<mesh>` element are parsed to `num1D_data` objects, which are then assigned the `raw_geom` object's sources array. Then, the primitive type is established, and the `indices` array is read, from the `<p>` element of the corresponding primitives node.

#### The `construct_mesh` function 
```cpp
void construct_mesh(mesh* mesh, const int meshesCount);
```

The `construct_mesh` takes an unprocessed `mesh` object array, and for each of the meshes in the array, populates the `vertices` and `indices` arrays, using the raw geometry information of the `raw` (`raw_geom`) object. You can reffer to the [previus function (read_mesh_geometries)](#the-read_mesh_geometries-function) function to further examine how the `raw_geom` objects are generated.


### The `<library_controllers>` section

According to the concept of the COLLADA format, a *controller* is a device or mechanism that manages and directs the operations of another object. We are interested in armature, or skin controllers. Such controller nodes hold information about the armature joints, and how the armature affects a specific mesh. It contains vertex-joint relations, which describe how many joints affect each mesh vertex, and with what weight.

If you wish to get a more complete explanation, read the full specification for the `<skin>` node. Here is a short xml block, which shows the basic structure of a skin controller.

```xml
<library_controllers>
  <controller id="" name="Armature">
    <skin source="#<Mesh_id>(link to mesh)">
      <!-- joint names Name_array -->
      <source id="joint-names-data"> ... </source>
      <!-- float_array holding inv bind transform matrices for each joint (inverse bind= from joint to object space) -->
      <source id="inv-trans-data"> ... </source>
      <!-- weights float array -->
      <source id="weights-data"> ... </source>    
      <joints>
        <input semantic="JOINT" source="#joint-data"/>
        <input semantic="INV_BIND_MATRIX" source="#inv-trans-data"/>
      </joints>
      <vertex>
          <input semantic="JOINT" source="#joint-names-data" offset="0"/>
          <input semantic="WEIGHT" source="#weights-data" offset="1"/>
          <!-- list of integers, each specifying the number of joints associated with one of the vertices. -->
          <vcount> ... </vcount>
          <!-- list of joint-weight index pairs for each vertex. -->
          <v> ... </v>
      </vertex>
    </skin>
  </controller>
  ...
</library_controllers>
```

#### The `read_mesh_armature_controller` function
```cpp 
void read_mesh_armature_controller(TiXmlDocument* colladaDoc, mesh* mesh);
```

This function takes as input a mesh object (`mesh`), with an already constructed `vertices` array, and searches the `<library_controllers>` section for a skin controller, reffering to that particular mesh. If it finds such a controller, it constructs a new `armature_ctl` object, and sets it as the mesh armature controller.

Constructing the `armature_ctl` object, involves several steps. First, using the joint related sources in the `<skin>` node, the `joint_names`, `joints` and `joint_inv_transforms` arrays are initialized and populated. Then, the `vertex_joint_assoc` and `vertex_joint_weights` arrays are generated, based on the information in the `<vertex>` element. 

It is important to note, that the function truncates the maximal number of joints affecting a single vertex to three. In other words, if a vertex is affected by more than three joints, only the first three are recorded in the `vertex_joint_assoc` and `vertex_joint_weights` arrays, and the vertex-joint weights are recomputed.

### The `<library_visual_scenes>` section

The `<library_visual_scenes>` section of the COLLADA document holds a collection of `<visual_scene>` nodes. 

A `visual_scene` element describes a kind of object hierarchy. The hierarchical structure of the `<visual_scene>` is organized into a scene graph. A scene graph is a directed acyclic graph (DAG) or tree data structure that contains nodes of visual information and related data. The structure of the scene graph contributes to optimal processing and rendering of the data and is therefore widely used in the computer graphics domain.

A `<visual_scene>` element contains `<node>` elements, which represent points of information within the scene graph. A node element can contain child nodes, and transforms, like: `<translate>`, `<rotate>`, `<scale>` and `<matrix>`. The transforms show how a child node element is situated, related to the parent node.

```xml
<library_visual_scenes>
  <!-- holds a scene node graph -->
  <visual_scene>  
    <node name="Armature">
      <translate sid="location"> ... </translate>
      <rotate sid="rotationZ"> ... </rotate>
      <rotate sid="rotationY"> ... </rotate>
      <rotate sid="rotationX"> ... </rotate>
      <scale sid="scale"> ... </scale>
      <!-- armature joint node -->
      <node name="..." type="JOINT">
        <matrix sid="transform"> ... </matrix>
        <node> ... </node>
      </node>
  </visual_scene>
</library_visual_scenes>
```
Our program uses the `visual_scenes` section to read armature joint hierarchies, declared inside of armature nodes.

#### The `read_armature_controller_node_tree` function
```cpp
void read_armature_controller_node_tree(TiXmlElement* scene, armature_ctl* ctl);
```
This function searches throught the child nodes of a `<visual_scene>` element, to find an armature type node.  When the function finds an armature node, it reads its contents recursively, and builds the armature joint hierarchy of the `armature_ctl` input object.

Currently, the function searches for node elements with a name attribute value "Armature". 

### The `<library_animations>` section

The `<library_animations>` section of the COLLADA document, contains `<animation>` nodes. Each animation node has the following structure:
```xml
<animation>
  <!-- Num1D timestamps for keyframes -->
  <source id="a">...</source>
  <!-- Num1D transforms for all keyframes -->
  <source id="b">...</source>
  <!-- Name_array describing the interpolation type for all keyframes (not parsed by our program at this time) -->
  <source id="c">...</source>
  <sampler>
    <input semantic="INPUT" source="#a"/>
    <input semantic="OUTPUT" source="#b"/>
    <input semantic="INTERPOLATION" source="#c"/>
  </sampler>
  <channel target="<Joint name>/<property (transform)>"/>  
</animation>
```

#### The `read_armature_controller_animations` function
```cpp
void read_armature_controller_animations(TiXmlDocument* colladaDoc, armature_ctl* ctl);
```
The function reads the animation keyframes information for the armature controller joints. 

For each of the `<animation>` elements in the `<libary_animations>` section, it extracts the value of the `target` attribute of the `<channel>` child element, and using that value, searches for any matching joint in the armature controller joints list. 

If it finds the matching target joint, it updates the joint's data, using the keyframe and transform sources, located in the `<animation>` node.

## Code organization
The project uses the [CMake](https://cmake.org/) build system. The essential source files are located in the `src` directory. In addition, there is the `tinyxml` directory, containing the [TinyXML](http://www.grinninglizard.com/tinyxml/) source and the `main.cpp` file, which contains the `main` method.

All the *class* and *struct* declarations are located in the `src/structs.hpp` file. The definitions of the classes are in separate source files, named after the class name. These files are:
* `src/armaturectl.cpp`;
* `src/rawgeom.cpp`;
* `src/num1ddata.cpp`;
* `src/joint.cpp`;
* `src/mesh.cpp`;
* `src/namesdata.cpp`;

The procedure declarations, mentioned [here](#procedures), are in the `src/funcs.hpp` file. The definitions are located across several source files with appropriate names:
* `src/animations.cpp`;
* `src/controllers.cpp`;
* `src/customtypes.cpp`;
* `src/geometries.cpp`;
* `src/joints.cpp`;
* `src/meshes.cpp`;
* `src/sources.cpp`;
* `src/visualscenes.cpp`;

## Binary format

### Overview
This section contains a complete format description of the output binary file. The file can be viewed as having several distinct sections:
* **Meshes metadata**: meta information about the mesh collection;
* **Meshes data** (for each mesh):
  + **Mesh metadata**: contains metadata for the individual mesh-- the mesh name, the mesh primitives type and others.
  + **Mesh vertices data**: holds *positions*, *normals*, *uv coordinates*, etc.
  + **Mesh indices data**: describes how the mesh vertices form primitives (triangles, trifans, lines, etc.);
  + **Joint armature metadata**: contains some meta information about the mesh joint armature &ndash; the armature object space position, orientation and scale, the number of joints and the joints hierarchy;
  + **Joint data** (for each joint): holds the joint name, the relative joint transformations, the joint keyframe transformations, and the joint animation keyframe timestamps;
  (At this time, no interpolation data is included, but by extending the `<library_animations>` parser method, this can be easily added as well.)
  + **Joint-vertex data**: per vertex joint-vertex *joint indices* of the joints affecting the vertex, plus the *weights* for each vertex-joint relation;
  
Each of this parts is reviewed in detail in the next couple of paragraphs.

As you can see, in the current implementation, the focus is to have a collection of meshes with a single joint armature. This is due to the specifics of the project that uses this converter. Ofcourse anyone could extend or alter this, to their own liking.

### Meshes metadata
Currently, this section contains only a single integer, which is the **number of meshes** in the file.

### Meshes data
The rest of the file contains large chuncks of data, for each individual mesh. They are reviewed next.

#### Mesh metadata
This section holds the following:
1. *name length N* (`uint32`);
2. *name* (N `char`s);
3. *primitive type* (`uint32`)
  (lines= 0, linestrips= 1, polygons= 2, polylist= 3, triangles= 4, trifans= 5, tristrips= 6);
4. *flags* (`uint32`);
  (For now, there is only one flag on the `$2^0$` position, determining whether or not the mesh has an associated armature controller.)
5. *number of vertex attributes A* (`uint32`);
	
	
![mesh metadata](./media/fig1.png)

#### Mesh vertices data
As mentioned above, the mesh metadata contains the number of vertex attributes *A*. For each of those vertex attributes, we have the following structure:

1. *attribute semantic* (`uint32`);
  An integer specifying the usage of the source. (For example, `0` is position, `1` is normal, `2` is texcoord and so on.)
2. *gl type* (`uint32`);
  A number representing the [gl type](https://www.khronos.org/opengl/wiki/OpenGL_Type) of the attribute elements. At this time, this can be either *Gl_INT* or *GL_FLOAT*. This number is usefull for determining the size (in bytes), of a single attribute element.
3. *number of attribute elements V* (`uint32`);
  This is the number of attribute elements, equal to the number of mesh vertices, multiplied by the attribute source stride. For example, the number of position elements must be the three times the number of the mesh vertices. In this example, the stride is three.
4. *attribute stride* (`uint32`);
  This number can be later used to determine, the number of attribute elements per vertex.

Following these four numbers are *V* attribute elements.

![mesh vertices](./media/fig2.png)

#### Mesh indices data
Next, we have the indices array. The mesh is drawn as a collection of primitives. These primitives must be of a certain primitive type, which is determined in the mesh metadata section. OpenGL defines several distinct primitive types: *lines*, *linestrips*, *polygons*, *polylist*, *triangles*, *trifans*, *tristrips*. You can read more about them, from [here](https://www.khronos.org/opengl/wiki/Primitive).

In essence, the indices determine the ordered sequence of vertices, by which to build primitives and the mesh as a whole. The indices are in fact vertex indices, specifying an address offset multiple in the final mesh vertex array, which is loaded into video memory. All indices are strinctly in the range from zero to the *number of vertices*.

The indices data begins with the *number of indices I*. Then follow *I* unsigned integer numbers &ndash; the indices.

![mesh indices](./media/fig3.png)

#### Joint armature metadata
This section contains the following information, about the mesh armature controller:
1. *position* (`float[3]`);
2. *X rotation* (`float[4]`);
3. *Y rotation* (`float[4]`);
4. *Z rotation* (`float[4]`);
5. *scale* (`float[3]`);
6. *total number of armature joints J* (`uint32`);

Following these values, is the joint hierarchy array. The array describes the number of child joints and the child joint indices for each joint in the armature skeleton. For each joint, we have:
1. The *number of child joints U* for that joint (uint32);
2. The *indices* of the *U* child joints (uint[U]);

![armature metadata](./media/fig4.png)

#### Joint data
The next section of the binary file contains information about the individual joints from the armature. For each joint we have the following data:
1. *name length G* (`uint32`);
2. *name* (G `char`s);
3. *joint transform* (`float[16]`);
4. *joint inverse bind transform* (`float[16]`);
5. *number of keyframes Z* (`uint32`);
6. *keyframe timestamps* (`float[Z]`);
7. *keyframe transforms* (`float[16*Z]`);

![armature metadata](./media/fig5.png)

#### Joint-vertex data
Lastly, after the data for all the joints, follows the joint-vertex association array, and the joint-vertex weights array. All vertices have the same number of joints associated with them, so the following structure applies:
1. *number of elements Q* (`uint32`);
	(This number is equal to the number of mesh vertices multiplied by the number of joints affecting a single vertex.)
2. *stride Y* (`uint32`);
	(This number gives the number of joints per single vertex.)
3. *associate array* values (`uint32[Q*Y]`);
	(This array holds joint indices. There are *Y* indices for each vertex.)
4. *weights array* values (`float[Q*Y]`);
	(This array holds float weight values. There are *Y* weight values for each vertex, corresponding to the *Y* indices, which were previously written.)

![armature metadata](./media/fig6.png)