🔒 Locked

Help to implement correct algorithm for index array

Started by BlackJoker Mar 22, 2013 at 1:19 PM 4 replies 1.4k views

Original Post

BlackJoker

139

BlackJoker

Mar 22, 2013 at 1:19 PM

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]]))
                                )
                            {       

constructedMesh.Vertices.Add(tempMesh.Vertices[indexvector3.Vertices[j]]);
                                constructedMesh.Normals.Add(tempMesh.Normals[indexvector3.Normals[j]]);
                                constructedMesh.Textures.Add(tempMesh.Textures[indexvector3.Texcoords[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?

Weeve

Mar 22, 2013 at 7: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?"

Poigahn

115

Poigahn

Mar 23, 2013 at 12:02 AM

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.

BlackJoker

Author

139

BlackJoker

Mar 23, 2013 at 2:01 PM

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++)
                    {
                       
                        constructedMesh.Vertices.Add(tempMesh.Vertices[indexvector3.Vertices]);
                    }
                    for (int i = 0; i < indexvector3.Normals.Count; i++)
                    {
         
                        constructedMesh.Normals.Add(tempMesh.Normals[indexvector3.Normals]);
                    }
                    for (int i = 0; i < indexvector3.Texcoords.Count; i++)
                    {
   
                        constructedMesh.Textures.Add(tempMesh.Textures[indexvector3.Texcoords]);
                    }

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.

wh1sp3rik

Mar 25, 2013 at 7:47 AM

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

BlackJoker

Author

139

BlackJoker

Mar 26, 2013 at 6: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, 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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.