Advertisement Jump to content
Sign in to follow this  

Removing duplicate verts in C++ using std::map and D3DXVECTOR3

This topic is 3106 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

I'm running into a problem that's driving me absolutely batty. I'm currently generating some geometry, and the algorithms I'm using to create it generate a very large number of duplicate vertices. It's important that the duplicate vertices be removed and indexed, not for performance reasons, but because I need to perform some additional work on those vertices and duplicates throw a serious wrench into things.

The code I'm using to do this right now is S-L-O-W. I'm essentially iterating through a vector of original vertices (could be well over 12k) and for each one iterating through a list of unique vertices (about 2k unique verts for 12k original verts, so you can see that duplicates are a huge issue) and adding the original vertex to the unique list if it's not already there. This code is part of an editor so it's not a huge deal, but at the same it's miserable having to wait 2-3 minutes just for the vertex indexing code to run.

What I would like to do is this (VecList, IdxList, and VectorIndexMap are all just typedefs for std::vector<D3DXVECTOR3>, std::vector<int>, and std::map<D3DXVECTOR3, int> respectively):

VectorIndexMap vecIdxMap;
IdxList indices;

// Create a map of unique vertices to index numbers
for (VecList::size_type i = 0; i < originalVerts.size(); i++)
D3DXVECTOR3 curVert = originalVerts;

VectorIndexMap::iterator vIdxIt;
if ( (vIdxIt = vecIdxMap.find(curVert)) == vecIdxMap.end() )
// Add this vertex to unique list, add a reference to it to the index list
vecIdxMap[curVert] = curIndex++;
// This vertex already indexed, so just add it to the index list

I have the above implemented and it's significantly faster. In fact, what takes 3-4 minutes using vectors takes about 10 seconds using that code. The problem is that it doesn't actually work. The map seems to be returning false positives, so I end up with the proper number of indices, but too few unique vertices by about 1/3. If I iterate through the map one-by-one using an iterator and check for equality (just as if I was using a vector) it works, so I suspect the issue is with my D3DXVECTOR3 operator<. This is the code I'm using for that:

inline bool operator<(const D3DXVECTOR3 &lhs, const D3DXVECTOR3 &rhs)
if (lhs.y < rhs.y) return true; if (lhs.y > rhs.y) return false;
if (lhs.z < rhs.z) return true; if (lhs.z > rhs.z) return false;
return lhs.x < lhs.x;

The problem is, I don't know why this doesn't work, and until I figure it out I'm stuck using the vector method that's so painfully slow. Any insight at all would be really appreciated so I could stop slamming my head into the wall over and over. :)

Share this post

Link to post
Share on other sites

You have no idea how long I've been staring at that line of code. As embarrassing as that is, I guess it pays to have a second set of eyes look things over. That solved it, and you're my new hero for the day.

Edit- Seriously, I was pulling my hair out over this and thinking for some reason strict weak ordering just wasn't going to work with D3DXVECTOR3. I was actually considering writing a hash function to solve this.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!