View more

View more

View more

Image of the Day Submit

IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

Help to implement correct algorithm for index array

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

5 replies to this topic

#1BlackJoker  Members

Posted 22 March 2013 - 07:19 AM

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[i], indexvector3.Vertices[j]) &&
(!Equals(tempMesh.Textures[indexvector3.Texcoords[i]], tempMesh.Textures[indexvector3.Texcoords[j]])
|| !Equals(tempMesh.Normals[indexvector3.Normals[i]], 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?

#2Weeve  Members

Posted 22 March 2013 - 01:08 PM

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?"

#3Poigahn  Members

Posted 22 March 2013 - 06:02 PM

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.

Your Brain contains the Best Program Ever Written : Manage Your Data Wisely !!

#4BlackJoker  Members

Posted 23 March 2013 - 08:01 AM

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.

Attached Thumbnails

Edited by BlackJoker, 23 March 2013 - 08:47 AM.

#5wh1sp3rik  Members

Posted 25 March 2013 - 01:47 AM

I have a very different approach after my thread here .. perhaps it's silly 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[i]._vertex ) ) {*index=dc[x][y][z]._dupData[i]._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

DirectX 11, C++

#6BlackJoker  Members

Posted 26 March 2013 - 12:50 PM

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[i], constructedMesh.Vertices[j]) &&
(Equals(constructedMesh.Textures[i], constructedMesh.Textures[j]) &&
(Equals(constructedMesh.Normals[i], 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, 28 March 2013 - 06:15 AM.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.