Deindexing/Unifying Vertex/Normal/Texccord Indices

I came across quite a few posts in this forum that touches upon with deindexing/unifying indices which I need to do to render in OpenGL using buffering techniques which only accept one array of indices for all the various data that need to be bufffered (vertices/normals/texcoords) using drawElements, whereas collada uses multiple indices (within <triangles>

for eg.) to reference each of the data/channels. I’m afraid none of the previous posts are completely clear (atleast to me). I was wondering if it would be possible in this thread to hammer out some of the finer details on how to do this.

To begin with I would like to reference this post that mentions this in brief, pointing to the ColladaRefinery’s deindexer. What I would like to do is do the deindexing myself (esp. since ColladaRefinery is Windows only afaics).

Specifically, my question relates to redundant vertex information. It seems that collada files can use one normal per polygon per vertex, especially to account for smoothing related to the same vertex being part of multiple polys. Thus its possible to have far more normals than vertices and in the combined index, each vertex can be associated with multiple normals. For eg. slightly modifying the discussion here, within a double offset primitives

tag, we can find (substituting index literals with v1, n1 etc.):


<triangles count="2" material="matl_name">
  <input offset="0" semantic="VERTEX" source="#Model-Geometry-Vertex"/>
  <input offset="1" semantic="NORMAL" source="#Model-Geometry-Normals"/>


 v1 n21 v2 n32 v3 n29 v3 n11 v4 n43 v6 n98 </p>
</triangles>

Won’t the process of unifying the vertex indices by creating duplicate vertices for each of the multiple normals for that vertex defeat the very purpose of reducing reduntant information being transferred, which is an advantage offered by vertex arrays in openGL? Is this an evil I’ll need to live with if I need to buffer data? Or am I misunderstanding the way to go about deindexing/unifying indices?

I’m also curious about this. I’ve looked in to FBX and Collada, a long time ago tough and got to the point where I couldn’t figure out how to create a vertex and index buffer.

let’s take a cube for example:

If triangulated there is 8 positions and 32 indices.

I’v come to the point where I could render models in wire fram just using positions and vertices and, well the indices as index buffer. But when It came to uv’s and normals, those where mapped with there own set of indices.

If one could with the refinery manage to get 8 positions/normals/uv’s sharing the 32 indices that would be awsome!
I’m installing the refinery as i’m writing this post. Is there any tutorials how to use it??

Well I made a cube i Maya.

I Run this refinery on the dae file:

Input -> polygons2Triangle->Optimizer->deindexer->output

and ended up with this:


<?xml version="1.0"?>
<COLLADA xmlns="http://www.collada.org/2005/11/COLLADASchema" version="1.4.0">
    <asset>
        <contributor>
            <authoring_tool>FBX COLLADA exporter</authoring_tool>
        </contributor>
        <created>2009-11-02T21:34:55Z</created>
        <modified>2009-11-02T21:34:55Z</modified>
        <unit meter="0.01" name="meter"/>
        <up_axis>Y_UP</up_axis>
    </asset>
    <library_materials>
        <material id="lambert1" name="lambert1">
            <instance_effect url="#lambert1-fx"/>
        </material>
    </library_materials>
    <library_effects>
        <effect id="lambert1-fx" name="lambert1">
            <profile_COMMON>
                <technique sid="standard">
                    <lambert>
                        <emission>
                            <color sid="emission">0 0 0 1</color>
                        </emission>
                        <ambient>
                            <color sid="ambient">0 0 0 1</color>
                        </ambient>
                        <diffuse>
                            <color sid="diffuse">0.4 0.4 0.4 1</color>
                        </diffuse>
                        <transparent>
                            <color sid="transparent">0 0 0 1</color>
                        </transparent>
                        <transparency>
                            <float sid="transparency">1</float>
                        </transparency>
                    </lambert>
                </technique>
            </profile_COMMON>
        </effect>
    </library_effects>
    <library_geometries>
        <geometry id="pCube1-lib" name="pCube1Mesh">
            <mesh>
                <source id="pCube1-lib-Position">
                    <float_array id="pCube1-lib-Position-array" count="24">-0.5 -0.5 0.5 0.5 -0.5 0.5 0.5 0.5 0.5 -0.5 0.5 0.5 0.5 0.5 -0.5 -0.5 0.5 -0.5 0.5 -0.5 -0.5 -0.5 -0.5 -0.5</float_array>
                    <technique_common>
                        <accessor count="8" source="#pCube1-lib-Position-array" stride="3">
                            <param name="X" type="float"/>
                            <param name="Y" type="float"/>
                            <param name="Z" type="float"/>
                        </accessor>
                    </technique_common>
                </source>
                <source id="pCube1-lib-Normal0">
                    <float_array id="pCube1-lib-Normal0-array" count="24">0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0</float_array>
                    <technique_common>
                        <accessor count="8" source="#pCube1-lib-Normal0-array" stride="3">
                            <param name="X" type="float"/>
                            <param name="Y" type="float"/>
                            <param name="Z" type="float"/>
                        </accessor>
                    </technique_common>
                </source>
                <source id="pCube1-lib-UV1">
                    <float_array id="pCube1-lib-UV1-array" count="16">0.375 0 0.625 0 0.625 0.25 0.375 0.25 0.625 0.5 0.375 0.5 0.625 0.75 0.375 0.75</float_array>
                    <technique_common>
                        <accessor count="8" source="#pCube1-lib-UV1-array" stride="2">
                            <param name="S" type="float"/>
                            <param name="T" type="float"/>
                        </accessor>
                    </technique_common>
                </source>
                <vertices id="pCube1-lib-Vertex">
                    <input semantic="POSITION" source="#pCube1-lib-Position"/>
                </vertices>
                <triangles count="12" material="lambert1">
                    <input offset="0" semantic="VERTEX" source="#pCube1-lib-Vertex"/>
                    <input offset="0" semantic="NORMAL" source="#pCube1-lib-Normal0"/>
                    <input offset="0" semantic="TEXCOORD" source="#pCube1-lib-UV1" set="1"/>
                    

0 1 2 
					   0 2 3 
					   3 2 4 
					   1 4 2 
					   3 4 5 
					   5 4 6 
					   1 6 4 
					   5 6 7 
					   7 6 1 
					   7 1 0 
					   7 0 3 
					   7 3 5</p>
                </triangles>
            </mesh>
        </geometry>
    </library_geometries>
    <library_animations>
        <animation id="pCube1-anim" name="pCube1"/>
    </library_animations>
    <library_lights>
        <light id="SceneAmbient-lib" name="SceneAmbientMesh">
            <technique_common>
                <ambient>
                    <color>0.4 0.4 0.4</color>
                </ambient>
            </technique_common>
        </light>
    </library_lights>
    <library_visual_scenes>
        <visual_scene id="RootNode" name="RootNode">
            <node id="pCube1" name="pCube1">
                <translate sid="translate">0 0 0</translate>
                <rotate sid="rotateZ">0 0 1 0</rotate>
                <rotate sid="rotateY">0 1 0 0</rotate>
                <rotate sid="rotateX">1 0 0 0</rotate>
                <scale sid="scale">2.01273 2.01273 2.01273</scale>
                <instance_geometry url="#pCube1-lib">
                    <bind_material>
                        <technique_common>
                            <instance_material symbol="lambert1" target="#lambert1"/>
                        </technique_common>
                    </bind_material>
                </instance_geometry>
            </node>
        </visual_scene>
    </library_visual_scenes>
    <scene>
        <instance_visual_scene url="#RootNode"/>
    </scene>
</COLLADA>


I got 8 positons/normals/uv’s and 36 indices :slight_smile:

Good for you, HermanssoN. I, however, do not have the luxury of being able to run refinery as I am working on GNU/Linux. In any case, it’d be nice if it were possible to work out an outline of the unifying/deindexing algorithm here. I am at the moment rummaging through the code of deindexer_core.cpp in refinery.

Also, considering your example of the cube, the dae before the refinery’s deindexer must have contained 1 normal per vertex per face, correct? Can you please post the dae that you input to the deindexer (i.e. the output post optimizer)? Since you have posted the only post-deindexed dae I have seen till now, if I could get the original dae, I can try working my way back.

Also, I wonder what the optimizer does. According to refinery, it is to:

optimize the primitives to improve the vertex cache hit rate


<?xml version="1.0" encoding="utf-8"?>
<COLLADA xmlns="http://www.collada.org/2005/11/COLLADASchema" version="1.4.0">
  <asset>
    <contributor>
      <authoring_tool>FBX COLLADA exporter</authoring_tool>
    </contributor>
    <created>2009-11-02T21:34:55Z</created>
    <modified>2009-11-02T21:34:55Z</modified>
    <unit meter="0.010000"/>
    <up_axis>Y_UP</up_axis>
  </asset>
  <library_materials>
    <material id="lambert1" name="lambert1">
      <instance_effect url="#lambert1-fx"/>
    </material>
  </library_materials>
  <library_effects>
    <effect id="lambert1-fx" name="lambert1">
      <profile_COMMON>
        <technique sid="standard">
          <lambert>
            <emission>
              <color sid="emission">0.000000  0.000000 0.000000 1.000000</color>
            </emission>
            <ambient>
              <color sid="ambient">0.000000  0.000000 0.000000 1.000000</color>
            </ambient>
            <diffuse>
              <color sid="diffuse">0.400000  0.400000 0.400000 1.000000</color>
            </diffuse>
            <transparent>
              <color sid="transparent">0.000000  0.000000 0.000000 1.000000</color>
            </transparent>
            <transparency>
              <float sid="transparency">1.000000</float>
            </transparency>
          </lambert>
        </technique>
      </profile_COMMON>
    </effect>
  </library_effects>
  <library_geometries>
    <geometry id="pCube1-lib" name="pCube1Mesh">
      <mesh>
        <source id="pCube1-lib-Position">
          <float_array id="pCube1-lib-Position-array" count="24">
-0.500000 -0.500000 0.500000
0.500000 -0.500000 0.500000
-0.500000 0.500000 0.500000
0.500000 0.500000 0.500000
-0.500000 0.500000 -0.500000
0.500000 0.500000 -0.500000
-0.500000 -0.500000 -0.500000
0.500000 -0.500000 -0.500000
</float_array>
          <technique_common>
            <accessor source="#pCube1-lib-Position-array" count="8" stride="3">
              <param name="X" type="float"/>
              <param name="Y" type="float"/>
              <param name="Z" type="float"/>
            </accessor>
          </technique_common>
        </source>
        <source id="pCube1-lib-Normal0">
          <float_array id="pCube1-lib-Normal0-array" count="72">
0.000000 0.000000 1.000000
0.000000 0.000000 1.000000
0.000000 0.000000 1.000000
0.000000 0.000000 1.000000
0.000000 1.000000 0.000000
0.000000 1.000000 0.000000
0.000000 1.000000 0.000000
0.000000 1.000000 0.000000
0.000000 0.000000 -1.000000
0.000000 0.000000 -1.000000
0.000000 0.000000 -1.000000
0.000000 0.000000 -1.000000
0.000000 -1.000000 0.000000
0.000000 -1.000000 0.000000
0.000000 -1.000000 0.000000
0.000000 -1.000000 0.000000
1.000000 0.000000 0.000000
1.000000 0.000000 0.000000
1.000000 0.000000 0.000000
1.000000 0.000000 0.000000
-1.000000 0.000000 0.000000
-1.000000 0.000000 0.000000
-1.000000 0.000000 0.000000
-1.000000 0.000000 0.000000
</float_array>
          <technique_common>
            <accessor source="#pCube1-lib-Normal0-array" count="24" stride="3">
              <param name="X" type="float"/>
              <param name="Y" type="float"/>
              <param name="Z" type="float"/>
            </accessor>
          </technique_common>
        </source>
        <source id="pCube1-lib-UV1">
          <float_array id="pCube1-lib-UV1-array" count="28">
0.375000 0.000000
0.625000 0.000000
0.375000 0.250000
0.625000 0.250000
0.375000 0.500000
0.625000 0.500000
0.375000 0.750000
0.625000 0.750000
0.375000 1.000000
0.625000 1.000000
0.875000 0.000000
0.875000 0.250000
0.125000 0.000000
0.125000 0.250000
</float_array>
          <technique_common>
            <accessor source="#pCube1-lib-UV1-array" count="14" stride="2">
              <param name="S" type="float"/>
              <param name="T" type="float"/>
            </accessor>
          </technique_common>
        </source>
        <vertices id="pCube1-lib-Vertex">
          <input semantic="POSITION" source="#pCube1-lib-Position"/>
        </vertices>
        <polygons material="lambert1" count="6">
          <input semantic="VERTEX" offset="0" source="#pCube1-lib-Vertex"/>
          <input semantic="NORMAL" offset="1" source="#pCube1-lib-Normal0"/>
          <input semantic="TEXCOORD" offset="2" set="1" source="#pCube1-lib-UV1"/>
          

0 0 0 1 1 1 3 2 3 2 3 2</p>
          

2 4 2 3 5 3 5 6 5 4 7 4</p>
          

4 8 4 5 9 5 7 10 7 6 11 6</p>
          

6 12 6 7 13 7 1 14 1 0 15 0</p>
          

1 16 1 7 17 7 5 18 5 3 19 3</p>
          

6 20 6 0 21 0 2 22 2 4 23 4</p>
        </polygons>
      </mesh>
    </geometry>
  </library_geometries>
  <library_animations>
    <animation id="pCube1-anim" name="pCube1"></animation>
  </library_animations>
  <library_lights>
    <light id="SceneAmbient-lib" name="SceneAmbientMesh">
      <technique_common>
        <ambient>
          <color>0.400000 0.400000 0.400000</color>
        </ambient>
      </technique_common>
    </light>
  </library_lights>
  <library_visual_scenes>
    <visual_scene id="RootNode" name="RootNode">
      <node id="pCube1" name="pCube1">
        <translate sid="translate">0.000000 0.000000 0.000000</translate>
        <rotate sid="rotateZ">0 0 1 0.000000</rotate>
        <rotate sid="rotateY">0 1 0 0.000000</rotate>
        <rotate sid="rotateX">1 0 0 0.000000</rotate>
        <scale sid="scale">2.012734 2.012734 2.012734</scale>
        <instance_geometry url="#pCube1-lib">
          <bind_material>
            <technique_common>
              <instance_material symbol="lambert1" target="#lambert1"/>
            </technique_common>
          </bind_material>
        </instance_geometry>
      </node>
    </visual_scene>
  </library_visual_scenes>
  <scene>
    <instance_visual_scene url="#RootNode"/>
  </scene>
</COLLADA>



The original dae.

Have you seen remi’s xna viewer for collada?
https://collada.org/public_forum/viewtopic.php?f=13&t=676&hilit=+material+XNA
I do belive that he is using some conditioning ported to C#.
COLLADAConditioner.cs

I’m a windows user but I know there is a emulator for windows apps, Whine, that could be used in Linux. Has anyone tried to run the refinery on whine?
It’s not a clean solution but it’s am idea that popped up in my head.

Well, after a little huffing and puffing I managed to write a deindexer that works for triangles meshes alone. I have managed to load triangle meshes fine with it. Here is the significant snippet of code I am using:


float* unifyIndices(int totalVertexCount, int totalTrianglesCount, int lesserIndices[], int greaterIndices[], float greaterData[])
{
    //This function unifies the three indices into a unified index by removing the duplicated indices and data from the greater buffer so as to match the smaller one

    //We create a map for referencing lesserIndices with greaterIndices
    std::map<int,int> indexMap;

    float *rearrGreaterData = new float[totalVertexCount*3];

    for(int i=0;i<totalTrianglesCount*3;i++)
    {
        if( indexMap.count(lesserIndices[i]) == 0 )
        {
            //This is the first time this lesserIndex has been encountered
            //so add this to the map right away with the corresponding greater index
            indexMap[ lesserIndices[i] ] = greaterIndices[i];

            //Lookup the data from greaterData and add it to the hashMap
            //(Following 3 lines expanded instead of putting in a subloop for clarity)
            rearrGreaterData[ 3*lesserIndices[i]     ] = greaterData [ greaterIndices[i]*3     ];
            rearrGreaterData[ 3*lesserIndices[i] + 1 ] = greaterData [ greaterIndices[i]*3 + 1 ];
            rearrGreaterData[ 3*lesserIndices[i] + 2 ] = greaterData [ greaterIndices[i]*3 + 2 ];
        }

    }

    return rearrGreaterData;
}

What it does is basically takes lesserIndices (which is the index list you will be using for your final unified index, in my case for its the indices of the vertex positions) and rearranges the data in the greaterData (the attribute with multiple duplications per vertex), in my example, this would correspond to the normals.

Since the same normal may be used under duplicate normal indices for the same vertex, it is referenced only once. Thus the new array of normals (data) that the function returns is reduced in size.

I suppose this is a rather specialised case but I can’t think of why it shouldnt work for meshes with triangles alone for their geometry. If you have multiple attributes like texcoord other than normals, then you only need to use the function twice. Here is a code snippet showing its use for a double offset triangles indiced mesh, one for the normals and the other for the vertex positions:


    for(int i=0;i<polyCount*3*2;i=i+2)
    {
        modelVertexIndices[i/2] = loader->ROOT->geometry_list[0]->mesh_single->triangles_list[0]->p_data[i];
        modelNormalIndices[i/2] = loader->ROOT->geometry_list[0]->mesh_single->triangles_list[0]->p_data[i+1];
       
    }


    for(int i=0;i<polyCount*9;i++)
    {
        //Since collada uses per vertex normals per triangle
        modelNormals[i]   = loader->ROOT->geometry_list[0]->mesh_single->source_list[1]->float_array_single->data[i];
    }

    for(int i=0;i<vertCount*3;i++)
    {
        modelVertices[i] = loader->ROOT->geometry_list[0]->mesh_single->source_list[0]->float_array_single->data[i];
    }


    modelNormals = unifyIndices(vertCount,polyCount,modelVertexIndices,modelNormalIndices,modelNormals);


Please let me know if there are serious gaffes in my code/understanding or suggestions for improvements. While I want to leave this here for someone else to use I believe that no code is better than wrong and misleading code.

Hello,

I am not sure if I understood your first post correctly. But, I got indexed vbos to work in opengl with collada files.

(Talking only about positions and normal here…)

I have two arrays; one for positions and another for normals. I also have an array which stores the index values. Each index points to a unique vertex in the model. So,

Index Vertex.Posn Vertex.Normal
0 (0, 0, 0) (1, 0, 0)
1 (0, 1, 1) (0, 1, 0)

and my index array might churn out something like this:
index_array = { 0, 0, 1, 1, 1, 0 }

I can use this index_array in my drawelements. I felt that you were trying to do the same thing. If not, I am curios to know what you were trying to do then.

PS: I just came up with those values )