🔒 Locked

Optimize a triangle list

Started by sascoo Mar 4, 2009 at 12:04 AM 6 replies 1.5k views

Original Post

Mar 4, 2009 at 12:04 AM

I am writing a program where I take a model and break it down into chunks. Currently I have a very, very blunt algorithm O(n^2) which breaks it down leaving me with my desired vertex, index, texcoord, normal, and tangent buffers. I would like to speed things up since I may be dealing with 50k vertices and I need to break them down into reasonably sized chunks to stream in. As of right now it would be very easy and quick for me to generate a vector of points which would result in a triangle list. I know that Direct3D has an optimize function that can take in a buffer like that and spit out the index and vertex buffers by generating an adjacency buffer(I don't know how to structure one of these...). Does anyone have something I could reference or something to get me started with? Thanks, John

Geoffrey

Mar 4, 2009 at 4:25 AM

What, exactly, is the bottleneck in your existing code?

sascoo

Mar 4, 2009 at 9:54 AM

Hahaha yeah, it's not pretty but I just wanted to get things working at the time :)

sudo code:

vector<Vector3> vertices; // Where this is the chunk of all verticesvector<uint> tempIndices // Where this is the indices that fall inside of the quad-tree nodevector<Vector3> cVertices // Where this is the new vertices for the chunkvector<uint> cIndices // Where this is the final indices go which reference cVerticesSo then I just brute force to make sure that I don't have duplicates in cVertices when i parse...for(int i = 0; i < tempIndices.size(); i++){   bool found = false;   for(int j = 0; j < cVertices.size(); j++)   {       if(vertices[tempIndices] == cVertices[j])       {            cIndices.push_back(j);            found = true;       }   }   if(found == false)   {       cVertices.push_back(vertices[tempIndices]);       cIndices.push_back(vertices.size());   }}

I am just making that up from memory so the logic might be a bit skewed...but as you can see, this is not a good way of getting the indices for one vertex buffer and changing them so they reference another vertex buffer.

Geoffrey

Mar 4, 2009 at 12:10 PM

Searching through cVertices to find the vertex (if you've added it already) is slow, especially for large meshes - an this leads to the algorithm overall being O(n^2) (http://en.wikipedia.org/wiki/Big_O_notation - article is a bit hardcore to be honest). In other words it's very slow.

In any case, you should be able to speed up your algorithm greatly by doing something more efficient here. I'd recommend a hash table, mapping vertices you've added already to their new indices.

Theory here: http://en.wikipedia.org/wiki/Hash_table

Depending on the exact compiler you're using, you might have access to std::hash_map or something similar, which will do all of the work for you. I believe you want a std::hash_map. You might need to implement a hashing function for Vector3, but I suspect any old thing will do for your purposes - just return x + y + z or something.

Note that though it's quite large, you can get rid of the hash table as soon as the algorithms finished. It's only needed for working. Also, it will run even quicker if you pre-size it to the number of vertices in the mesh, or something around about there (using hash_map.resize).

sascoo

Mar 4, 2009 at 1:17 PM

I suppose using a hash table would speed things up a lot, but I don't think it would work for my needs. A problem with hashing is that there would be gaps in the data due to hashing and I need to write the data to a binary file. I was hoping someone knew how ID3DXMesh::Optimize was implemented because from what I understand, it would generate the buffers in the correct format... I guess I can just output a triangle list and use that until I get to the final build of the model. After that I can run my the algorithm I have now and use index buffers for the drawing.

swiftcoder

Mar 4, 2009 at 1:24 PM

Quote:
Original post by sascoo
I suppose using a hash table would speed things up a lot, but I don't think it would work for my needs. A problem with hashing is that there would be gaps in the data due to hashing and I need to write the data to a binary file.

The has map isn't the final data structure - it is merely used to test for duplicates along the way. The values are written out to arrays (just as your current case), but the hash map allows you to quickly check if an identical vertex has been processed previously.

sascoo

Mar 4, 2009 at 1:55 PM

Ahh... I got you. I will use the hash table for simply checking to see if I have already added the vertice to the vector. If it is there, then I search through the vector until I find it and put its index into the index vector. If I cant find it, then I add it to the vertex buffer and add its location to the index buffer. So I have another question... Which would be best to use, a hash or a set? I know that hashing would be faster but would it be easier to use?

swiftcoder

Mar 4, 2009 at 3:33 PM

Quote:
Original post by sascoo
Ahh... I got you. I will use the hash table for simply checking to see if I have already added the vertice to the vector. If it is there, then I search through the vector until I find it and put its index into the index vector. If I cant find it, then I add it to the vertex buffer and add its location to the index buffer. So I have another question... Which would be best to use, a hash or a set? I know that hashing would be faster but would it be easier to use?

You can use a set if you just want to discard a duplicates, but you will still need a linear search to find the first occurrence. With a hash_map (or even a regular map - slower but more portable), you can store the index of the first occurrence in the map, which saves that costly linear search.

Topic Locked

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