STL to sort vertices
Author
Greetings!
I am writing some convertes for Alias|Wavefront Maya .OBJ file format. The point is, that i get the information in some kind of vertex list. For every face i get 3 vertices. Not vertex indexes. Small example of two faces:
3.2 5.2 6.1
2.1 2.3 4.5
6.7 8.2 1.2
3.2 5.2 6.2
3.4 5.6 8.7
6.7 8.2 1.2
That would be 2 triangles, vertices are passed as float x,y,z;
I load those vertices in my:
struct vertex_t{ float x, y, z; };
I pushback every vertex in a vector like this:
std::vector<vertex_t*> vertices;
vertices.pushback(new vertex_t(x,y,z));
In souch a "vector" some vertices do repeat themself. Is there any automated way that would generate me a unique list of only unique vertices like face information? I see myself writing souch kind of parses every month. Is there a more elegant way? I don't want to sort that vertex container over and over again by my self.
You could copy the vertices into a mesh and use the meshes optimisation functions to eliminate them.
Here's some completely 100% untested source code that I just wipped up:
const float tollerance = 0.0001f;struct Vector3fLess{ bool operator ()(const Vector3f &a, const Vector3f &b) const { float diff; bool isLess = false; diff = b.x - a.x; if (diff > tollerance) { isLess = true; } else if (diff >= -tollerance) { diff = b.y - a.y; if (diff > tollerance) { isLess = true; } else if (diff >= -tollerance) { isLess = (b.z - a.z > tollerance); } } return isLess; }};void createUniqueVertices(const std::vector<Vector3f> &inputVerts, std::vector<Vector3f> &outputVerts, std::vector<int> outputIndices){ std::map<Vector3f, int, Vector3fLess> uniqueVertices; outputIndices.reserve(inputVerts.size()); for (std::vector<Vector3f>::const_iterator i = inputVerts.begin(); i != inputVerts.end(); ++i) { std::map<Vector3f, int, Vector3fLess>::iterator found = uniqueVertices.find(*i); int index; if (found == uniqueVertices.end()) { // New vertex index = uniqueVertices.size(); uniqueVertices[*i] = index; } else { // Use existing vertex index = found->second; } outputIndices.push_back(index); } outputVerts.resize(uniqueVertices.size()); for (std::map<Vector3f, int, Vector3fLess>::iterator i = uniqueVertices.begin(); i != uniqueVertices.end(); ++i) { outputVerts[i->second] = i->first; }}
Insert it all into a std::map<Vertex, unsigned short> object, with the unsigned short being the index of the vertex.
So, load a vertex from file, then check if it exists in the map object. If it doesn't, insert it into the map index with an index of map.size()-1, or something like that. If it does exist, don't insert it into the map and assign the index of the next vertex in the triangle to be map[vertex].
So, load a vertex from file, then check if it exists in the map object. If it doesn't, insert it into the map index with an index of map.size()-1, or something like that. If it does exist, don't insert it into the map and assign the index of the next vertex in the triangle to be map[vertex].
Quote:Original post by Samurai Jack
struct vertex_t{ float x, y, z; };
std::vector<vertex_t*> vertices;
vertices.pushback(new vertex_t(x,y,z));
Ow, ow, ow. Please don't store them by pointer in your vector, there's absolutely no reason to. It's already a small type with value semantics and you don't need polymorphic behavior. Storing on the heap will increase your memory use by at least a quarter ( possibly more, depending on padding your heap's block size ), make your program slower ( since heap allocation isn't cheap and you'll have an extra indirection penalty ), and make your program harder to code ( because you'll have to remember to delete all those structs at some point ).
C++ is not Java.
struct vertex_t{ float x, y, z; };
std::vector<vertex_t> vertices;
vertices.pushback( vertex_t(x,y,z) );
Implement an operator < and an operator== for the vertex type
then take your vector and do
then take your vector and do
std::sort(vector.begin(),vector.end())std::unique(vector.begin(),vector.end())Quote:Original post by Nitage
Implement an operator < and an operator== for the vertex type
then take your vector and dostd::sort(vector.begin(),vector.end())std::unique(vector.begin(),vector.end())
Except that std::unique ( like std::remove ) doesn't actually remove anything.
You'll probably be happier with:
std::sort(v.begin(),v.end())v.erase( std::unique(v.begin(),v.end()), v.end() );
You might want to check out std::set in the STL documentation. I think that is exactly what you need.
HappyMiel
HappyMiel
I second Nitage's code, as modified by me22 to actually remove the duplicates. I bet it'd be much faster than using std::set or std::map. People always seem to use maps even if a sorted vector fits the problem better. Sets and maps are more useful when you're inserting/removing elments frequently. In this case though all your inserts are up-front and then you never insert again. Go with a sorted vector here.
I also recomment you follow me22's advice of working with a container of vertex objects rather than a container of pointers to vertices.
I also recomment you follow me22's advice of working with a container of vertex objects rather than a container of pointers to vertices.
Quote:Original post by sthomas
I also recommen[d] you follow me22's advice
=)
And yes, for anything performance-critical sets are basically only useful for HUGE amounts of data ( where their algorithmic complexity finally wins over vector's tiny constants ) or where you really need set's iterator invalidation properties ( in which case a vector of shared_ptrs might be better anyways, especially since that gives you weak_ptrs )
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
