Sign in to follow this  
Samurai Jack

STL to sort vertices

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

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