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 :)