Sign in to follow this  
XVincentX

Make a index buffer

Recommended Posts

XVincentX    129
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 this post


Link to post
Share on other sites
Buckeye    10747
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 this post


Link to post
Share on other sites
Sc4Freak    643
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 this post


Link to post
Share on other sites
XVincentX    129
Quote:
Original post by Sc4Freak
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.


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 this post


Link to post
Share on other sites
andur    781
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 this post


Link to post
Share on other sites
Buckeye    10747
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 this post


Link to post
Share on other sites
XVincentX    129
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?

Share this post


Link to post
Share on other sites
Buckeye    10747
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 this post


Link to post
Share on other sites
XVincentX    129
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 this post


Link to post
Share on other sites
Buckeye    10747
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 this post


Link to post
Share on other sites
XVincentX    129
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 this post


Link to post
Share on other sites
XVincentX    129
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 this post


Link to post
Share on other sites
Buckeye    10747
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 this post


Link to post
Share on other sites
XVincentX    129
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

What do you think about this results?

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 this post


Link to post
Share on other sites
XVincentX    129
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 this post


Link to post
Share on other sites
Buckeye    10747
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 this post


Link to post
Share on other sites
XVincentX    129
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 this post


Link to post
Share on other sites
Buckeye    10747
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 this post


Link to post
Share on other sites
XVincentX    129
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.

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