Fast Unique Vertex Determination

You can provide a custom compare function/functor to an std::map or use the default and implement the "less than" operator (operator <) for your vertex structur. Alternatively you can use a map with an unsigned integer as your key type and compute a hash out of your vertex components.

EDIT: small excample for the hash based method:

Ah nice idea! I'll give the hashing method a twirl and see how it goes :)

Thanks

Hmm I tried your hashing methods and another hash method but it seems they don't work 100%. Would it have something to do with the components being floating point and therefore would have inaccuracies? Are there hash methods that would work for this type of usage?

I would not recommend sebbit's algorithm. What I would do is the following,

1) Insert all of your vertices into a table
2) Sort the table
3) Iterate over the table and build a new table that doesn't have duplicates.

That will be much faster. In fact, you can fold step 3 and 2 into one step for an even faster algorithm if you want to implement your own sort routine. As you sort throw out duplicates.


To answer your last question, when you compare floats you should compare that the floats are almost equivalent (within some tolerance). Just google float comparison C++

I wouldn't recommend sorting and pruning. The most elegant solution (which also happens to be the most efficient solution) is to insert the vertices one by one into a spatial hash table and remove duplicates as they are encountered. Basically what sebbit suggested, except properly detecting duplicates with respect to a floating-point comparison threshold.

For detail, see:
http://groups.google.com/group/comp.games.development.programming.algorithms/msg/d6d2a2b98209e013

If that's not enough detail, you can also see Chapter 12.1 of my book for a lengthy elaboration.

I have used a dictionary (a map I guess) before using the .toString() method (a customised string representation of a vertex i.e. "123.232,12.5235235,-2.5")
so only one main loop is required and no sorting is required.

for each vertex
check vertex.toString() against dictionary
if null then add it to unique list and set dictionary value to 1 or anything really
else do nothing as its already in the list


;)

Quote:

Original post by bwhiting I have used a dictionary (a map I guess) before using the .toString() method (a customised string representation of a vertex i.e. "123.232,12.5235235,-2.5") so only one main loop is required and no sorting is required. for each vertex check vertex.toString() against dictionary if null then add it to unique list and set dictionary value to 1 or anything really else do nothing as its already in the list

Just curious - why use strings for this? It seems like it would (or at least could) be considerably less efficient than the approaches suggested earlier in the thread.

There's also floating-point accuracy to consider, as mentioned previously. If you know that duplicate vertices will have exactly the same values, then you can just use a lexicographical comparison of the vertex elements, which I would think would be faster than a string comparison (and conversion) in the general case. (Of course if duplicate vertices *aren't* guaranteed to have exactly the same values, the string approach isn't going to be of much use anyway.)

Just for reference I ended up using the less than operator in my vertex struct with an std::map. When comparing the floats I use an epsilon. It works well and is very fast - what used to take 10 minutes now only takes 10 seconds :)

I guess it was posted as a simple alternative for those reading this who might be using other languages (java or something) whom cannot use the various inbuilt functionality discussed in here. Although toStringing is probably slower (than 3 numerical comparisons) I have used it and found it to be plenty fast enough for what I was doing but the vertex count in my case was probably less then 20,000 so I can't really compare.



Seems like Shael got a working solution that he's happy with so I guess all is well.

This sounds interesting but I don't understand what it's for. Can someone give a rough explanation what's going on here it might help me with something. Thanks.

As I mentioned in my original post the main focus was to find a quick way of determining if a vertex had already been added to an array. I needed this because when exporting a mesh from 3D Studio Max the same vertex can be specified more than once because of shared vertices. So I needed a fast way to only get a list of the unique vertices that make up the mesh. This would only work if you have an accompanying index buffer - which I do.

Obviously my first approach was too slow - for each new vertex it had to loop through the current list of stored vertices to see if it was already there. As the current vertex array got bigger the longer it took to find. As the more vertices the mesh had the longer it took also.

The faster approach is to have the vertex structure overload the less than operator to compare the Position, Normal, and UV components taking into account an epsilon when comparing the floats. This is then coupled with an std::map which has the vertex as the key and its index as the value.

Using this approach the time taken to export a 20K mesh went from 5+ mins to only a few seconds.

Awesome! I used a similar thing for Blender export but it is/was less sophisticated. I found it impossible to have per vertex normals if the vertex was referenced in more than once face which obviously they always are. I did my stuff offline and dumped it into a binary file but I might (if I can ever understand it) switch to your method. Definitely something worth studying thanks for the post ;o)

**Edit**
I might post some of the code if you want?Not sure it would be much use though. It's all based on crazy iteration loops. Works well tho. Weaker than your method however for sure.

might be of interest to someone so post it, you never know!

quickly tested the method I suggested.

6k mesh took under 300 ms which is about 1 sec for 20k.


better than I thought it would be, might even be faster than hashing, will have to compare the two.


"unsigned result = 13;
result = result * 31 + GetHash(vertex);
result = result * 31 + GetHash(normal);
result = result * 31 + GetHash(textureCoord);
return result;"

seems slower than

"return x + ',' + y + ',' + z;" (code in toString() function)

to me.





This was coded in as3 for flash by the way, so performance should be much better in a faster language.