Sign in to follow this  

STL to sort vertices

This topic is 4401 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
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;
}
}

Share this post


Link to post
Share on other sites
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].

Share this post


Link to post
Share on other sites
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) );

Share this post


Link to post
Share on other sites
Implement an operator < and an operator== for the vertex type

then take your vector and do


std::sort(vector.begin(),vector.end())
std::unique(vector.begin(),vector.end())

Share this post


Link to post
Share on other sites
Quote:
Original post by Nitage
Implement an operator < and an operator== for the vertex type

then take your vector and do


std::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() );

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You might want to check out std::set in the STL documentation. I think that is exactly what you need.

HappyMiel

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 )

Share this post


Link to post
Share on other sites

This topic is 4401 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this