• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
BlackJoker

Help to implement correct algorithm for index array

5 posts in this topic

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

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?

 

0

Share this post


Link to post
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?"

0

Share this post


Link to post
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.

0

Share this post


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

Share this post


Link to post
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[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 :)

0

Share this post


Link to post
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[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
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0