Make a index buffer
Author
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)
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.
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.
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.
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.
Author
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...
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).
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).
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?
Author
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:
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
But now i do not know how to continue...
Can you help me 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; }}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?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement