# Help to implement correct algorithm for index array

This topic is 1764 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I have a problem with creating algorithm for my index buffer.

for (int i = 0; i < indexvector3.Vertices.Count; i++)
{

for (int j = i + 1; j < indexvector3.Vertices.Count; j++)
{
if (Equals(indexvector3.Vertices, indexvector3.Vertices[j]) &&
(!Equals(tempMesh.Textures[indexvector3.Texcoords], tempMesh.Textures[indexvector3.Texcoords[j]])
|| !Equals(tempMesh.Normals[indexvector3.Normals], tempMesh.Normals[indexvector3.Normals[j]]))
)
{

indexvector3.Vertices[j] = constructedMesh.Vertices.Count - 1;

for (int k = j + 1; k < indexvector3.Vertices.Count; k++)
{
if(Equals(indexvector3.Vertices[j], indexvector3.Vertices[k]) && Equals(tempMesh.Textures[indexvector3.Texcoords[j]], tempMesh.Textures[indexvector3.Texcoords[k]])
&& Equals(tempMesh.Normals[indexvector3.Normals[j]], tempMesh.Normals[indexvector3.Normals[k]]))

{

indexvector3.Vertices[k] = constructedMesh.Vertices.Count - 1;

}

}
}
}
}

IndexVector3 - it is a class where all indices of vertices, texcoord and normals stored

tempMesh - class where stored not builded mesh with sorted coordinates

ans constructed mesh - class the same type as tempMesh, where I write coordinates in correct order.

After all I load it in my engine, but all models are broken. You can see it on screenshot.

I cannot found bug in my algorithm. Could someone help me with this problem, please?

##### Share on other sites

More info needed, What language is that? C++? What does your draw code look like, have you tested it with a known poly? What are the meshes supposed to look like?

Explain why you are using Equals(a,b) instead of "==" if that is C++

Why do you have j start at the value of i plus one?

for (int j = i + 1; j < indexvector3.Vertices.Count; j++)

Have you tried printing out every vertice in you buffer to confirm its the same amount as the sum of your mesh

I don't see support for both Quads and Trigs, possibly your problem, as it could cause an off by one error in your drawing

When you have a large amount of code like this, try to narrow down your problem before posing it on a forum, instead of saying "my code dosn't work, how do I fix it?"

##### Share on other sites

A little hard to track what your doing.   Have you tried doing it in increments.  For eaxmple, cut your loop value in half for your FOR loop and run it.  If everything appears to be okay increase it until you find where it is going wrong.  Then examine the values to make sure your data is entered correctly.

##### Share on other sites

Sorry for my 1st post, I was in despair. I try to explain all detail.

1. I write my own converter from collada (blender and 3s max) to my binary format on C#.

2. That binary format I load in my engine.

3. Converter work fine and even can triangulate non-triangulated meshes and engine display all of them correctly. You can see it on attached screen shot 1.

I use class with 3 lists o store 3 array indices, but they are not optimized. They just written as they are in COLLADA file. I want to use correct index buffer to save memory.

I construct from those 3 arrays of indices  one mesh. And it works. Code here

for (int i = 0; i < indexvector3.Vertices.Count; i++)
{

}
for (int i = 0; i < indexvector3.Normals.Count; i++)
{

}
for (int i = 0; i < indexvector3.Texcoords.Count; i++)
{

}

But when I use algorithm from my 1st message for creating index array I have some problems with my models. They all are broken. This you can see on screen shots 2 and 3.

P.S I use for

(int j = i + 1; j < indexvector3.Vertices.Count; j++)

because I compare in second and 3rd cycles previous value with current. There is no need add unnecessary pass through the loop.

Edited by BlackJoker

##### Share on other sites

I have a very different approach after my thread here .. perhaps it's silly :D but it's working fast.

void MAX_GenerateIndices()
{
FWODuplicator dupl;
FWOObject * _fwoObject = ExportInterface::GetInterface()->GetFWOObject();
_fwoObject->_indexList = new UINT[ _fwoObject->_indexCount ];

UINT currentIndex = 0;

for( UINT vid = 0; vid < _fwoObject->_vertexList.size(); vid++)
{
UINT vIndex = 0;
FWOVertex * vertex = _fwoObject->_vertexList[vid];

if( dupl.IsMapped(vertex, &vIndex))
{
_fwoObject->_indexList[vid] = vIndex;
}else{
_fwoObject->_optimalizedVertexList.push_back(vertex);
_fwoObject->_indexList[vid] = currentIndex++;
dupl.Map(vertex, _fwoObject->_indexList[vid] );
}
}
}

I am not good in checking other's code, so i will paste my idea. This is a easy index generator, you can see, i just get my object, which contain index count variable then i make a empty index array.

You see, this function is very simple, right ? but the core of this function is FWODuplicator :) which determine, if vertex exists or not in array already.

Now, the duplicator :) most advanced members will laugh perhaps becuase i would use something better ... but this is OK, lol.

class FWODuplicatorCellData
{
public:
FWODuplicatorCellData( FWOVertex * vertex, UINT index );
FWOVertex * _vertex;
UINT _index;
};

class FWODuplicatorCell
{
public:
std::vector<FWODuplicatorCellData> _dupData;
};

class FWODuplicator { public: bool CompareDoubles( double value1, double value2 ); bool CompareVertex( FWOVertex * v1, FWOVertex * v2 ); void Map( FWOVertex * vertex, UINT index ); bool IsMapped( FWOVertex * vertex, UINT * index); private: FWODuplicatorCell dc[10][10][10]; };

That's in my header. It also compare vertices with a small difference, let's say 0.001, so it will "merge" them :) nice optimalization right ? yep, fixing graphics artist bugs.

I think, you know what FWODuplicatorCell dc[10][10][10] means right ? i just splitted world space into 10x10x10 boxes, so searching for duplicates is faster. I tried HASH maps for that .. but i had some problems.

Ok, and Now, main functions for that :)

void FWODuplicator::Map( FWOVertex * vertex, UINT index )
{
FWOObject * _fwoObject = ExportInterface::GetInterface()->GetFWOObject();

double xDiff = _fwoObject->_maxx - _fwoObject->_minx;
double yDiff = _fwoObject->_maxy - _fwoObject->_miny;
double zDiff = _fwoObject->_maxz - _fwoObject->_minz;

UINT x=0,y=0,z=0;

if( vertex->x < _fwoObject->_minx+xDiff*0.1 ) x = 0; else
if( vertex->x < _fwoObject->_minx+xDiff*0.2 ) x = 1; else
if( vertex->x < _fwoObject->_minx+xDiff*0.3 ) x = 2; else
if( vertex->x < _fwoObject->_minx+xDiff*0.4 ) x = 3; else
if( vertex->x < _fwoObject->_minx+xDiff*0.5 ) x = 4; else
if( vertex->x < _fwoObject->_minx+xDiff*0.6 ) x = 5; else
if( vertex->x < _fwoObject->_minx+xDiff*0.7 ) x = 6; else
if( vertex->x < _fwoObject->_minx+xDiff*0.8 ) x = 7; else
if( vertex->x < _fwoObject->_minx+xDiff*0.9 ) x = 8; else x = 9;

if( vertex->y < _fwoObject->_miny+yDiff*0.1 ) y = 0; else
if( vertex->y < _fwoObject->_miny+yDiff*0.2 ) y = 1; else
if( vertex->y < _fwoObject->_miny+yDiff*0.3 ) y = 2; else
if( vertex->y < _fwoObject->_miny+yDiff*0.4 ) y = 3; else
if( vertex->y < _fwoObject->_miny+yDiff*0.5 ) y = 4; else
if( vertex->y < _fwoObject->_miny+yDiff*0.6 ) y = 5; else
if( vertex->y < _fwoObject->_miny+yDiff*0.7 ) y = 6; else
if( vertex->y < _fwoObject->_miny+yDiff*0.8 ) y = 7; else
if( vertex->y < _fwoObject->_miny+yDiff*0.9 ) y = 8; else y = 9;

if( vertex->z < _fwoObject->_minz+zDiff*0.1 ) z = 0; else
if( vertex->z < _fwoObject->_minz+zDiff*0.2 ) z = 1; else
if( vertex->z < _fwoObject->_minz+zDiff*0.3 ) z = 2; else
if( vertex->z < _fwoObject->_minz+zDiff*0.4 ) z = 3; else
if( vertex->z < _fwoObject->_minz+zDiff*0.5 ) z = 4; else
if( vertex->z < _fwoObject->_minz+zDiff*0.6 ) z = 5; else
if( vertex->z < _fwoObject->_minz+zDiff*0.7 ) z = 6; else
if( vertex->z < _fwoObject->_minz+zDiff*0.8 ) z = 7; else
if( vertex->z < _fwoObject->_minz+zDiff*0.9 ) z = 8; else z = 9;

dc[x][y][z]._dupData.push_back( FWODuplicatorCellData(vertex, index) );
}

bool FWODuplicator::IsMapped( FWOVertex * vertex, UINT * index )
{
FWOObject * _fwoObject = ExportInterface::GetInterface()->GetFWOObject();

double xDiff = _fwoObject->_maxx - _fwoObject->_minx;
double yDiff = _fwoObject->_maxy - _fwoObject->_miny;
double zDiff = _fwoObject->_maxz - _fwoObject->_minz;

UINT x=0,y=0,z=0;

if( vertex->x < _fwoObject->_minx+xDiff*0.1 ) x = 0; else
if( vertex->x < _fwoObject->_minx+xDiff*0.2 ) x = 1; else
if( vertex->x < _fwoObject->_minx+xDiff*0.3 ) x = 2; else
if( vertex->x < _fwoObject->_minx+xDiff*0.4 ) x = 3; else
if( vertex->x < _fwoObject->_minx+xDiff*0.5 ) x = 4; else
if( vertex->x < _fwoObject->_minx+xDiff*0.6 ) x = 5; else
if( vertex->x < _fwoObject->_minx+xDiff*0.7 ) x = 6; else
if( vertex->x < _fwoObject->_minx+xDiff*0.8 ) x = 7; else
if( vertex->x < _fwoObject->_minx+xDiff*0.9 ) x = 8; else x = 9;

if( vertex->y < _fwoObject->_miny+yDiff*0.1 ) y = 0; else
if( vertex->y < _fwoObject->_miny+yDiff*0.2 ) y = 1; else
if( vertex->y < _fwoObject->_miny+yDiff*0.3 ) y = 2; else
if( vertex->y < _fwoObject->_miny+yDiff*0.4 ) y = 3; else
if( vertex->y < _fwoObject->_miny+yDiff*0.5 ) y = 4; else
if( vertex->y < _fwoObject->_miny+yDiff*0.6 ) y = 5; else
if( vertex->y < _fwoObject->_miny+yDiff*0.7 ) y = 6; else
if( vertex->y < _fwoObject->_miny+yDiff*0.8 ) y = 7; else
if( vertex->y < _fwoObject->_miny+yDiff*0.9 ) y = 8; else y = 9;

if( vertex->z < _fwoObject->_minz+zDiff*0.1 ) z = 0; else
if( vertex->z < _fwoObject->_minz+zDiff*0.2 ) z = 1; else
if( vertex->z < _fwoObject->_minz+zDiff*0.3 ) z = 2; else
if( vertex->z < _fwoObject->_minz+zDiff*0.4 ) z = 3; else
if( vertex->z < _fwoObject->_minz+zDiff*0.5 ) z = 4; else
if( vertex->z < _fwoObject->_minz+zDiff*0.6 ) z = 5; else
if( vertex->z < _fwoObject->_minz+zDiff*0.7 ) z = 6; else
if( vertex->z < _fwoObject->_minz+zDiff*0.8 ) z = 7; else
if( vertex->z < _fwoObject->_minz+zDiff*0.9 ) z = 8; else z = 9;

for( UINT i = 0; i < dc[x][y][z]._dupData.size(); i++)
{
if( CompareVertex( vertex, dc[x][y][z]._dupData._vertex ) ) {*index=dc[x][y][z]._dupData._index; return true;}
}
return false;
}

bool FWODuplicator::CompareVertex( FWOVertex * v1, FWOVertex * v2 )
{
if( !CompareDoubles(v1->x,v2->x) ) return false;
if( !CompareDoubles(v1->y,v2->y) ) return false;
if( !CompareDoubles(v1->z,v2->z) ) return false;

if( !CompareDoubles(v1->nx,v2->nx) ) return false;
if( !CompareDoubles(v1->ny,v2->ny) ) return false;
if( !CompareDoubles(v1->nz,v2->nz) ) return false;

if( !CompareDoubles(v1->uvx,v2->uvx) ) return false;
if( !CompareDoubles(v1->uvy,v2->uvy) ) return false;

if( !CompareDoubles(v1->uv2x,v2->uv2x) ) return false;
if( !CompareDoubles(v1->uv2y,v2->uv2y) ) return false;
return true;
}

bool FWODuplicator::CompareDoubles( double value1, double value2 )
{
if( value1 <= (value2 + 0.0005) && (value1 +  + 0.0005) >= value2 ) return true; else return false;
}

So that's all, i hope, it will help someone. As as said, perhaps it's not fastest and clever solution, but it's working fast, faster than stupid O(n3) complexity with three for loops for checking, if there is a duplicate :)

##### Share on other sites

Problem was solved. The algoritm for that is:

public Mesh OptimizeMesh(Mesh constructedMesh)
{
Mesh optimizedMesh;
optimizedMesh = constructedMesh;

for (int i = 0; i < constructedMesh.Vertices.Count; i++)
{
for (int j = i + 1; j < constructedMesh.Vertices.Count; j++)
{
if (Equals(constructedMesh.Vertices, constructedMesh.Vertices[j]) &&
(Equals(constructedMesh.Textures, constructedMesh.Textures[j]) &&
(Equals(constructedMesh.Normals, constructedMesh.Normals[j]))
))
{
optimizedMesh.Vertices.RemoveAt(j);
optimizedMesh.Normals.RemoveAt(j);
optimizedMesh.Textures.RemoveAt(j);

Decrement(ref optimizedMesh, i, j);
j--;
}
}
}
return optimizedMesh;
}

public void Decrement(ref Mesh mesh, int i, int j)
{
for (int k = 0; k < mesh.IndexBuffer.Count; k++)
{
if (mesh.IndexBuffer[k] == j)
{
mesh.IndexBuffer[k] = i;
}
if (mesh.IndexBuffer[k] > j)
{
mesh.IndexBuffer[k]--;
}
}
}

Thats work for C#. If you will need some comments, please, feel free to ask me by private message.

Edited by BlackJoker