# Make a index buffer

## Recommended Posts

Hello, i need help on an algorithm. I've taken from a file (Collada, .dae) a vertex buffer, that has got a lot of duplicates. I would like to delete duplicates and work with an index buffer. I tried in some modes (with a std::list), a for-cycles series, but i block every time in some part. Can you suggest me the way to follow to reach the purpose? Consider, for example, a mesh that has got Vertex Position, Normals and TexCoord. Oh, i'm using D3D10 (but this does not matters)

##### Share on other sites
You might look at D3DXWeldVertices (if it's applicable to D3X10).

Otherwise, you can try something like:

1. create a vector<D3DXVECTOR3> originalVertices and newVertices
2. create a vector<D3DXVECTOR3> for the origNormals
3. create a vector<int> for originalIndices and one for newIndices

Fill originalVertices.
Fill both set of indices (make them the same).

newVertices.push_back(originalVertices[0]);

Loop through originalVertices[1] to originalVertices[numVertices-1].

Compare each original vertex to all the newVertices entries using some criteria such as magnitude(original - new) for some small value. You may want to compare the normals also. If the normals are quite different, you want not want to call that vertex a duplicate.

After each comparison, if you want to keep the original vertex #originalVNum, add it to the newVertices list.

If it's a duplicate of newVertices[newVNum], change newIndices[originalVNum] to newVNum.

You end up with a list (well, vector) of newVertices and newIndices. Create a new mesh using the newVertices and newIndices, taking the normal from origNormals appropriately.

##### Share on other sites
Thank you. Tomorrow i will read better your advices and will try to use them.

##### Share on other sites
Unfortunately, D3DXWeldVertices doesn't appear to be a part of the DX10 D3DX library yet.

It should be noted that a naive implementation could take O(n^2) (or worse) running time.

The algorithm Buckeye described is good, but if you implement it naively you could get worst-case O(n^3). Because for each vertex, you're looping through every other vertex. And then for each of those loops, if the vertex gets welded you need to loop through the entire index buffer as well to find and correct any indices pointing to your now-welded vertex.

If you find that your algorithm is too slow, I would suggest looking into spatial partitioning and various other acceleration structures which should be able to significantly speed up this kind of operation.

##### Share on other sites
Quote:
 Original post by Sc4FreakUnfortunately, D3DXWeldVertices doesn't appear to be a part of the DX10 D3DX library yet.It should be noted that a naive implementation could take O(n^2) (or worse) running time.The algorithm Buckeye described is good, but if you implement it naively you could get worst-case O(n^3). Because for each vertex, you're looping through every other vertex. And then for each of those loops, if the vertex gets welded you need to loop through the entire index buffer as well to find and correct any indices pointing to your now-welded vertex.If you find that your algorithm is too slow, I would suggest looking into spatial partitioning and various other acceleration structures which should be able to significantly speed up this kind of operation.

This is bad: i work with meshes with a lot of vertices, and n^3 it's a huge amout of time.

Have you got any suggestion to speed up this operation?
I looked for WeldVertices in D3DX9 library and if needed and if could speed up operation, i will use it. From the prototype i can see it uses ID3DXMesh while i'm working with Vertex and Index buffers taken directly from the .dae file...

##### Share on other sites
Well, if you can, you should do this as a preprocess step to the mesh file itself and not at load time every single time you run your game.

My approach to this, is to build up a Vertex struct with all of the information I want in it, and then I toss them into a dictionary (key is the Vertex, value is the index #). If there's no collision, then its a new unique vertex. If there is a collision, then its a duplicate then I just pull out the index # of the previously encountered vertex.

This might not be the most efficient approach, but, I do it as part of the conversion of my mesh files into my own custom format, so it only has to be done once per mesh. Its fast enough to handle meshes with hundreds of thousands of vertices without any measureable slow down (as opposed to not having the duplicate vertex elimination enabled).

##### Share on other sites
Quote:
 This is bad: i work with meshes with a lot of vertices, and n^3 it's a huge amout of time.

You only need to do it once per mesh, right? Or are you continually loading new meshes with duplicate vertices?

##### Share on other sites
hello again.
I'm tring to implement your method but (mabye for my bad english, i can't understand all you write) i'm not able to continue the code.

As index buffer, i've got ad Indices Array:

	UINT *Indices = new UINT[this->ColladaBuffer.Indici];{	for (UINT i = 0; i < this->ColladaBuffer.Indici;i++)	{		Indices[i] = i;	}}

With this code it works, but now i want to create a real index buffer (the one that you see it's inutilizable...in this way it works as a normal Draw() call...)
So:

I've got a raw float values taken from .dae file buffer. I have got

float *buffer = new float[bufsize];//I take position, normals and texcoord from file...		std::vector<float> OrigVertices;		std::vector<float> NewVertices;		for (int i = 0; i < bufsize;i++)		{			OrigVertices.push_back(buffer(i));		}	NewVertices.push_back(OrigVertices[0]);	for(int i = 0; i < OrigVertices.size() - 1; i++)	{		if	}

But now i do not know how to continue...
Can you help me again?

Up

##### Share on other sites
First of all, your English is much better than my Italian! I'll try to explain things as best I can.

Second of all, each vertex should be D3DXVECTOR3, not a single float.

D3DXVECTOR3 *buffer = new D3DXVECTOR3[bufsize];//I take position, normals and texcoord from file...std::vector<D3DXVECTOR3> OrigVertices;std::vector<D3DXVECTOR3> NewVertices;for (int i = 0; i < bufsize;i++)		{			OrigVertices.push_back(buffer(i));		}NewVertices.push_back(OrigVertices[0]);

You also need two index vectors.

vector<int> origIdx; // indices with duplicates
vector<int> newIdx; // indices with duplicates removed

Fill both origIdx and newIdx with the indices from your file.

Something like:
for (UINT i = 0; i < this->ColladaBuffer.Indici;i++){	origIdx.push_back(i);	newIdx.push_back(i);}

Now, compare each old vertex after the first vertex to each of the new vertices. Something like:
D3DXVECTOR3 origV, newV;float epsilon = { a small number. How close do you want the vertices to be to call it "duplicate"? }bool duplicateV;for(int i=1; i<(int)OrigVertices.size(); i++){	origV = OrigVertices[i];	duplicateV = false;	for(int j=0; j<(int)NewVertices.size(); j++)	{		newV = NewVertices[j];		if( fabs(origV.x-newV.x) < epsilon && fabs(origV.y-newV.y) < epsilon && fabs(origV.z-newV.z) < epsilon )		{			newIdx[i] = j; // it's duplicate. use the NewVertices vertex			duplicateV = true;			break;		}	}	if( !duplicateV )	{		NewVertices.push_back( origV ); // use the original vertex		newIdx[i] = (int)NewVertices.size()-1;	}	}

I haven't tested this, but it should be close.

##### Share on other sites
Hello, i'm implementing still your code.
As i said up, i've got a raw float array (first 3 floats are position, next 3 are normal, next 3 texcoord).
Now i've modified your code in this way

		std::vector<float> OrigVertices;		std::vector<float> NewVertices;		for (int i = 0; i < bufsize;i++)		{			OrigVertices.push_back(buffer[i]);		}	NewVertices.push_back(OrigVertices[0]);	NewVertices.push_back(OrigVertices[1]);	NewVertices.push_back(OrigVertices[2]);	NewVertices.push_back(OrigVertices[3]);	NewVertices.push_back(OrigVertices[4]);	NewVertices.push_back(OrigVertices[5]);	NewVertices.push_back(OrigVertices[6]);	NewVertices.push_back(OrigVertices[7]);	NewVertices.push_back(OrigVertices[8]);	std::vector<unsigned int> OrigIndices, OptIndices;	for (UINT i = 0; i < this->ColladaBuffer.Indici;i++)	{		OrigIndices.push_back(i);		OptIndices.push_back(i);	}{	D3DVECTOR Vx,Nx,Tx;	D3DVECTOR VxN,NxN,TxN;	bool DuplicateV;	for (int i = 0; i < (OrigVertices.size());i+=9)	{		Vx.x = OrigVertices[i];		Vx.y = OrigVertices[i+1];		Vx.z = OrigVertices[i+2];		Nx.x = OrigVertices[i+3];		Nx.y = OrigVertices[i+4];		Nx.z = OrigVertices[i+5];		Tx.x = OrigVertices[i+6];		Tx.y = OrigVertices[i+7];		Tx.z = OrigVertices[i+8];		DuplicateV = false;		for (int j = 0; j < (NewVertices.size());j+=9)		{			VxN.x = NewVertices[j];			VxN.y = NewVertices[j+1];			VxN.z = NewVertices[j+2];			NxN.x = NewVertices[j+3];			NxN.y = NewVertices[j+4];			NxN.z = NewVertices[j+5];			TxN.x = NewVertices[j+6];			TxN.y = NewVertices[j+7];			TxN.z = NewVertices[j+8];			if (fabs(Vx.x-VxN.x) < Epsilon && fabs(Vx.y-VxN.y) < Epsilon && fabs(Vx.z-VxN.z) < Epsilon)			{				OptIndices[i] = j;				DuplicateV = true;				break;			}		}		if (!DuplicateV)		{			NewVertices.push_back(Vx.x);			NewVertices.push_back(Vx.y);			NewVertices.push_back(Vx.z);			NewVertices.push_back(Nx.x);			NewVertices.push_back(Nx.y);			NewVertices.push_back(Nx.z);			NewVertices.push_back(Tx.x);			NewVertices.push_back(Tx.y);			NewVertices.push_back(Tx.z);			OptIndices[i] = NewVertices.size() - 1;		}	}}

But i've got an out of range (i'm still tring to discover what vector is).
But i've not understand the utility of OriginalIndices vector!
Can you help me again?

##### Share on other sites
First:
for (int i = 9; i < (OrigVertices.size());i += 9)

Note that 'i' starts at 9, not 0, because you've already put the first OrigVertex into NewVertex. You don't want to test that one.

Second:

You're correct. As it turns out, the original indices are never used! Sorry about that.

Third:

The indices need to be for each vertex, each set of 9 values. That's why you're getting an "out of range."

Note the changes to the code below.

std::vector<float> OrigVertices;std::vector<float> NewVertices;for (int i = 0; i < bufsize;i++){	OrigVertices.push_back(buffer[i]);}NewVertices.push_back(OrigVertices[0]);NewVertices.push_back(OrigVertices[1]);NewVertices.push_back(OrigVertices[2]);NewVertices.push_back(OrigVertices[3]);NewVertices.push_back(OrigVertices[4]);NewVertices.push_back(OrigVertices[5]);NewVertices.push_back(OrigVertices[6]);NewVertices.push_back(OrigVertices[7]);NewVertices.push_back(OrigVertices[8]);std::vector<unsigned int> OrigIndices, OptIndices;for (UINT i = 0; i < this->ColladaBuffer.Indici;i++){	OrigIndices.push_back(i);	OptIndices.push_back(i);}{	D3DVECTOR Vx,Nx,Tx;	D3DVECTOR VxN,NxN,TxN;	int OrigVertIdx, NewVertIdx; // indices for full vertex <=========	bool DuplicateV;	for (int i = 0; i < (OrigVertices.size());i += 9)	{		OrigVertIdx = i/9; // integer divide to get vertex index <=======		Vx.x = OrigVertices[i];		Vx.y = OrigVertices[i+1];		Vx.z = OrigVertices[i+2];		Nx.x = OrigVertices[i+3];		Nx.y = OrigVertices[i+4];		Nx.z = OrigVertices[i+5];		Tx.x = OrigVertices[i+6];		Tx.y = OrigVertices[i+7];		Tx.z = OrigVertices[i+8];		DuplicateV = false;		for (int j = 0; j < (NewVertices.size());j +=9 )		{			VxN.x = NewVertices[j];			VxN.y = NewVertices[j+1];			VxN.z = NewVertices[j+2];			NxN.x = NewVertices[j+3];			NxN.y = NewVertices[j+4];			NxN.z = NewVertices[j+5];			TxN.x = NewVertices[j+6];			TxN.y = NewVertices[j+7];			TxN.z = NewVertices[j+8];			if (fabs(Vx.x-VxN.x) < Epsilon && fabs(Vx.y-VxN.y) < Epsilon && fabs(Vx.z-VxN.z) < Epsilon)			{				NewVertIdx = j/9; // index to new vertex <=============				OptIndices[OrigVertIdx] = NewVertIdx; // corrected indices <===========				DuplicateV = true;				break;			}		}		if (!DuplicateV)		{			NewVertIdx = (NewVertices.size()-1)/9; // corrected index <============			NewVertices.push_back(Vx.x);			NewVertices.push_back(Vx.y);			NewVertices.push_back(Vx.z);			NewVertices.push_back(Nx.x);			NewVertices.push_back(Nx.y);			NewVertices.push_back(Nx.z);			NewVertices.push_back(Tx.x);			NewVertices.push_back(Tx.y);			NewVertices.push_back(Tx.z);			OptIndices[OrigVertIdx] = NewVertIdx ; // corrected indices <==========		}	}}

I'm pretty sure that's good.

##### Share on other sites
I've tried your code with a mesh of 12589 vertices.
With Epsilon = 0 numvertices remains the same, while with epsilon = 0.5f it reduces at 10000 and something vertices.
But there's a problem in index buffer, becouse with both epsilon values mesh are drawn in the same (and wrong) way.

Now i've to go school, i will retry in this afteroon.

##### Share on other sites
Here is an image, with this code
		std::vector<float> OrigVertices;		std::vector<float> NewVertices;	std::vector<unsigned int> OptIndices;	for (UINT i = 0; i < this->ColladaBuffer.Indici;i++)	{		OptIndices.push_back(i);	}	for (int i = 0; i < bufsize;i++)	{		OrigVertices.push_back(buffer[i]);	}	NewVertices.push_back(OrigVertices[0]);	NewVertices.push_back(OrigVertices[1]);	NewVertices.push_back(OrigVertices[2]);	NewVertices.push_back(OrigVertices[3]);	NewVertices.push_back(OrigVertices[4]);	NewVertices.push_back(OrigVertices[5]);	NewVertices.push_back(OrigVertices[6]);	NewVertices.push_back(OrigVertices[7]);	NewVertices.push_back(OrigVertices[8]);	{		D3DVECTOR Vx,Nx,Tx;		D3DVECTOR VxN,NxN,TxN;		int OrigVertIdx, NewVertIdx;		bool DuplicateV;		for (int i = 9; i < (OrigVertices.size());i += 9)		{			OrigVertIdx = i/9;			Vx.x = OrigVertices[i];			Vx.y = OrigVertices[i+1];			Vx.z = OrigVertices[i+2];			Nx.x = OrigVertices[i+3];			Nx.y = OrigVertices[i+4];			Nx.z = OrigVertices[i+5];			Tx.x = OrigVertices[i+6];			Tx.y = OrigVertices[i+7];			Tx.z = OrigVertices[i+8];			DuplicateV = false;			for (int j = 0; j < (NewVertices.size());j +=9 )			{				VxN.x = NewVertices[j];				VxN.y = NewVertices[j+1];				VxN.z = NewVertices[j+2];				NxN.x = NewVertices[j+3];				NxN.y = NewVertices[j+4];				NxN.z = NewVertices[j+5];				TxN.x = NewVertices[j+6];				TxN.y = NewVertices[j+7];				TxN.z = NewVertices[j+8];				if (fabs(Vx.x-VxN.x) < Epsilon && fabs(Vx.y-VxN.y) < Epsilon && fabs(Vx.z-VxN.z) < Epsilon)				{					NewVertIdx = j/9;					OptIndices[OrigVertIdx] = NewVertIdx;					DuplicateV = true;					break;				}			}			if (!DuplicateV)			{				NewVertIdx = (NewVertices.size()-1)/9;				NewVertices.push_back(Vx.x);				NewVertices.push_back(Vx.y);				NewVertices.push_back(Vx.z);				NewVertices.push_back(Nx.x);				NewVertices.push_back(Nx.y);				NewVertices.push_back(Nx.z);				NewVertices.push_back(Tx.x);				NewVertices.push_back(Tx.y);				NewVertices.push_back(Tx.z);				OptIndices[OrigVertIdx] = NewVertIdx ;			}		}	}

And Epsilon = 0

[IMG]http://img516.imageshack.us/img516/8751/noepsilonah1.jpg[/IMG]

##### Share on other sites
I may have gotten an index incorrect.

I think:

NewVertIdx = (NewVertices.size()-1)/9;

should be:

NewVertIdx = (NewVertices.size())/9;

Good idea, by the way. Setting Epsilon to 0 should give you the original mesh.

##### Share on other sites
Now it's ok, i forget to remove the -1.
Anyway, i did some tests with this code, and here are the results (i used QueryPerformanceCounter & Frequency)

Results:
A mesh with 125928 vertices (and relatives texcoord and normals)

Without index buffer
Vertices: 125928
Memory: 503712 bytes
Time: 0.891 secs

With index buffer and 0.5 as epsilon value
Vertices: 10251
Memory: 41004 bytes
Time: 18,474 secs

With index buffer and 0.0 as epsilon value
Time: 185,586 secs

I would say thank you to Buck for the great help that he gave to me.

[Edited by - XVincentX on April 25, 2008 4:19:16 AM]

##### Share on other sites
Some hints? I would transform the copy vertex to vertex and perform it with a memcpy...

##### Share on other sites
Hints about what, XVincentX?

##### Share on other sites
Mmm i do not know.
I'm a little bit warried becouse a my friend said that, with same algorithm, mesh loading takes only 2 seconds!

I've changed single vector assignements with the insert() functions, gaining 0,400 seconds :)

##### Share on other sites
I thought you were going to remove the duplicate vertices and save the mesh to a new mesh file. Then you can use the new mesh file in your final application. You only need to change it once, correct?

##### Share on other sites
I was thinking to the same thing: rewrinte on the original file the new vertex and index buffer.

##### Share on other sites
I had a discussion with my friend and he said me his implementation, with run time index buffer generation, with same mesh and epsilon = 0.0001, uses only 2 seconds.
It's very strange.
He gave me his implementation...i'm trying to understand something. Someone can suggest something?
protected static void Triangulize(Model3D model)        {            int totalVertices = 0;            int strideSize = model.Stride;            float[] vertexTemp = new float[strideSize];            List<float> newVerticesList = new List<float>();            List<int> newIndexList = new List<int>();            for (int i = 0; i < model.VertexCount; i++)            {                //per ogni vertice                //salvo il vertice                for (int j = 0; j < strideSize; j++)                {                    vertexTemp[j] = model.Data[i * strideSize + j];                }                //controlla se già esiste                int currentVertex = -1;                for (int j = 0; j < totalVertices; j++)                {                    //confronta il vertice attuale con quelli già inseriti                    bool equal = true;                    for (int k = 0; k < strideSize; k++)                    {                        if (Math.Abs(vertexTemp[k] - newVerticesList[j * strideSize + k])<epsilon)                        {                            equal = false;                            break;                        }                    }                    if (equal)                    {                        currentVertex = j;                        break;                    }                }                if (currentVertex == -1)                {                    //nuovo vertice, aggiungere                    newIndexList.Add(totalVertices);                    totalVertices++;                    for (int j = 0; j < strideSize; j++)                        newVerticesList.Add(vertexTemp[j]);                }                else                {                    //il vertice già esiste, aggiungere solo l'indice                    newIndexList.Add(currentVertex);                }            }            model.Data.Clear();            model.Data.AddRange(newVerticesList);            model.IndexData.Clear();            model.IndexData.AddRange(newIndexList);        }

##### Share on other sites
Your friend's algorithm (method, sequence) does the same thing as the algorithm you came up with, but it is more efficient (faster, quicker).

Part of that efficiency (quickness, speed) is because the new algorithm tests the data in the model's vertex buffer without copying it to a new list.

Time is also saved by not converting (changing, copying) the vertices into D3DXVector3 structures before the epsilon comparison (test) is made.

##### Share on other sites
I modified the code in this way

		std::vector<float> OrigVertices;		std::vector<float> NewVertices;	std::vector<unsigned int> OptIndices;	for (UINT i = 0; i < this->ColladaBuffer.Indici;i++)	{		Indices[i] = i;	}	OptIndices.insert(OptIndices.begin(),Indices,Indices + this->ColladaBuffer.Indici);	OrigVertices.insert(OrigVertices.begin(),buffer,buffer + bufsize);	NewVertices.insert(NewVertices.begin(),OrigVertices.begin(),OrigVertices.begin() + 9);	{//		D3DVECTOR Vx,Nx,Tx;//		D3DVECTOR VxN,NxN,TxN;		int OrigVertIdx, NewVertIdx;		bool DuplicateV;		for (int i = 9; i < (OrigVertices.size());i += 9)		{			OrigVertIdx = i/9;/*			Vx.x = OrigVertices[i];			Vx.y = OrigVertices[i+1];			Vx.z = OrigVertices[i+2];			Nx.x = OrigVertices[i+3];			Nx.y = OrigVertices[i+4];			Nx.z = OrigVertices[i+5];			Tx.x = OrigVertices[i+6];			Tx.y = OrigVertices[i+7];			Tx.z = OrigVertices[i+8];*/			DuplicateV = false;			for (int j = 0; j < (NewVertices.size());j +=9 )			{/*				VxN.x = NewVertices[j];				VxN.y = NewVertices[j+1];				VxN.z = NewVertices[j+2];				NxN.x = NewVertices[j+3];				NxN.y = NewVertices[j+4];				NxN.z = NewVertices[j+5];				TxN.x = NewVertices[j+6];				TxN.y = NewVertices[j+7];				TxN.z = NewVertices[j+8];*/				if (fabs(OrigVertices[i]-NewVertices[j]) < Epsilon && fabs(OrigVertices[i+1] - NewVertices[j+1]) < Epsilon && fabs(OrigVertices[i+2] - NewVertices[j+2]) < Epsilon)				{					NewVertIdx = j/9;					OptIndices[OrigVertIdx] = NewVertIdx;					DuplicateV = true;					break;				}			}			if (!DuplicateV)			{				NewVertIdx = (NewVertices.size())/9;				NewVertices.insert(NewVertices.end(),OrigVertices.begin() + i,OrigVertices.begin() + i + 9);				OptIndices[OrigVertIdx] = NewVertIdx ;			}		}	}

Now the code requires 6,7 seconds.
I should try now to remove completely the vector's usage.

## 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

• ### Forum Statistics

• Total Topics
628300
• Total Posts
2981894

• 9
• 9
• 11
• 10
• 10