   Algorithm question: finding shared vertices fast.
  Hi,I´m looking for the fastest algoritm for the following problem.I have one index buffer and one vertex buffer. The vertex buffer contains some vertices that are duplicates, some vertices are exactly the same as other vertices. I want to find all duplicates and create a new, smaller vertex buffer, and a new, equal size index buffer and render exactly the same mesh with that but which takes less memory. Only the vertex position is relevant in determing if it´s a duplicate.The simplest (but idiotic) way is to loop the entire vertex buffer for each vertex in the list. So if the list has 30000 vertices, I would need 30000*30000 = 900000000 checks to get the job done.What would be the fastest way to do this? I was thinking about looping the list and place every vertex in a STL hash map, at the same time testing if that vertex was already in the hash map by converting the vertex position to one value which is used as the STL key. Can anyone give some suggestions on what could be the fastest way?Peter   
Quote:Original post by PeterVWhat would be the fastest way to do this? I was thinking about looping the list and place every vertex in a STL hash map, at the same time testing if that vertex was already in the hash map by converting the vertex position to one value which is used as the STL key.That is about as fast as you are going to be able to get, unless your positions hash particularly poorly. I used a similar technique to weld vertices from OBJ files, using std::set, and it worked plenty fast enough - although I was performing the welding offline, if you need this at runtime it may not be that fast.   ;  The STL map approach works well.  I have an implementation of what you are asking for (however, it does allow for "duplicates" based on more than position).  Visit Geometric Tools, select the Foundation tab in the "Browse Libraries..." section, and then select the Meshes tab.  The relevant files are Wm4UniqueVerticesTriangles.{h,inl}.As mentioned, this is reasonable for offline computations and probably not fast enough during a real-time application.;  The process you have mentioned is in general the correct way to do it. The trick is to make your comparison with the unique set as quick as possible. Simply iterating all the unique list is in this case very slow, not idiotic but maybe niave :-) Hash map is simply the best way to proceed.;  Thanks guys,I´ll go for the hash map method.And yes, it is for offline computation in the tools, not during the game itself.Peter   