How do you find and remove redundent vertices fast?
Author
Since this topic doesn't really fit anywhere else, I thought I'd post it here, because I'm sure the answer has something to do with math.
I've been trying to think of different ways to remove duplicated xyz values from an array of vertices. I've been testing each vertex with all the other vertices, but processing 300,000 vertices (100,000 triangles) is waaaaay to slow using that method. LightWave does it quickly somehow, but how??? Are they hashing the vertices or something?
I did this recently by using a std::set<vertex>. Basically you try to insert each progressive vertex, and if it fails you've got a duplicate. (Note that you'll need an appropriate operator< to do this.) It might be possible to do this faster with a hash code, where you basically have a hashtable<hashcode, vertexlist>. Basically you attempt to insert into the hashtable based on a hashcode, and if there's a collision, you go through and check in the vertex list under that hash code for duplicates.
Interesting technique. I have to try this method. I'll either create < > operators for my vertex class, or hash them, and then insert them into my AVL tree class, which does not allow duplicates.
This has to be faster than comparing a vertex to all of ther other vertices...
This has to be faster than comparing a vertex to all of ther other vertices...
You can do better than Promit's solution by using a hash_set<vertex>. Insertions into set<> take O(log N) time, where N is the size of the set. Insertions into hash_set<> take ammortized constant time. For large collections of elements the speed difference should be noticeable. To use hash_set<> you don't need to provide a comparison, but you do need a hash function. Also notice that hash_set is not part of the C++ standard, although many STL implementations provide it.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
