Duplicate Vertices?

[gaar321]

Hello

can you please help direct me to some documentation on how to delete duplicate vertices and generate an index using a hashtable

[Paul McKenzie]

Hello

can you please help direct me to some documentation on how to delete duplicate vertices and generate an index using a hashtable

The question is so vague, how can we answer you?

What does vertices have to do with Visual C++? Where is the code for these "dupilcate vertices"? How are they implemented? What do you mean by "index"? etc.. etc...

Regards,

Paul McKenzie

[gaar321]

ermm well I am parsing an obj file format and I want to know how to implement a hash table to to remove double vertices (x,y,z points) in memory

[Paul McKenzie]

ermm well I am parsing an obj file format and I want to know how to implement a hash table to to remove double vertices (x,y,z points) in memory

Read your response. Do you think that it conveys any information useful to others? What does "parsing an obj file format" have to do with vertices?

You want to know how to remove duplicates, whether it's vertices, integers, doubles, or Widgets? If that's the real question, then you need to tell us how you're storing these duplicates. In an array? In a vector? In a CArray? In a CMap? etc.. etc..

Then you need to tell us how you're representing these x,y,z coordinates. A struct with three elements? A tuple of three elements? Etc... etc...

Regards,

Paul McKenzie

[gaar321]

The x,y,z coordinates are stored in a vector that uses XMFLOAT3 and i want suggestions on how to detected duplicate data so the double coordinate can be discarded and added to an index array as a reference.

[Paul McKenzie]

The x,y,z coordinates are stored in a vector that uses XMFLOAT3 and i want suggestions on how to detected duplicate data so the double coordinate can be discarded and added to an index array as a reference.

So you want to

1) Detect the duplicates
2) Create another container that stores which items were duplicated.

First, there are containers that automatically do not store duplicates, namely std::set. Is it that important to know what the duplicates are? If not, then you can just use a std::set instead of std::vector to store your XMFLOAT3 variables.

If you must use vector, there are several things you can do.

1) You can sort the vector, and then call unique() to remove the duplicates.

or

2) Use a combination of vector and set. The vector is used to hold your XMFLOAT3 data, and the set is used as a temporary "duplicate finder". See this example below:

#include <DirectXMath.h>
#include <vector>
#include <set>
#include <iterator>
#include <algorithm>

// Needed for set to order items.
struct ComparisonSpec
{
    bool operator()(const XMFLOAT3& xf1, const XMFLOAT3& xf2) const
    {
        if ( xf1.x < xf2.x )
          return true;
        if ( xf1.y < xf2.y )
          return true;
       return xf1.z < xf2.z;
    }
};

typedef std::set<XMFLOAT3, ComparisonSpec> XMFLOAT3Set;
typedef std::vector<XMFLOAT3> XMFLOAT3Vector;

XMFLOAT3Set RemoveDuplicates(XMFLOAT3Vector& xIn)
{
   // This will hold the duplicates
    XMFLOAT3Set theDups;

   // This will help us figure out the duplicates easily
    XMFLOAT3Set     tempSet;
    size_t nValues = xIn.size();
    for (size_t i = 0; i < nValues; ++i )
    {
       // attempt to insert.  If this is false, no insertion was done due to duplicate
       if ( !tempSet.insert( xIn[i] ).second )
          theDups.insert( xIn[i] );  // add dup to our dup set
    }
    xIn.clear();  // clear out original vector

   // now copy our set back to the original vector
    std::copy( tempSet.begin(), tempSet.end(), std::back_inserter(xIn));

  // return the duplicates
    return theDups;
}

int main()
{
  XMFLOAT3Vector v1;
  XMFLOAT3 x1, x2, x3;
  x1.x = 0;
  x1.y = 5;
  x1.z = 10;
//...
  x2.x = 2;
  x2.y = 5;
  x2.z = -1;
//...
  // create a duplicate
  x3 = x1;

  // now add these to our vector
  v1.push_back( x1 );
  v1.push_back( x2 );
  v1.push_back( x3 );

  // call function
  XMFLOAT3Set allMyDupsAreHere = RemoveDuplicates( v1 );

  // v1 will have the unique items.  The allMyDupsAreHere contains the entries that were duplicates  
}

I didn't comment all of the code or test it, but the essence is that you have a vector of XMFLOAT3, unsorted, and maybe contains duplicates. What the RemoveDuplicates() does is take the vector, add the item to a set (the set automatically filters out duplicates), and then copies the set back to the original vector. While this is going on, another set is recording the duplicates, and this is what is returned. Please note that the order of XMLFOLAT3 items in the original vector is not preserved -- whatever order was in the set is what is copied back to the vector.

So you have the set of duplicates, the vector has been filtered of all the duplicates. So the next thing you want to do is to take that duplicate set that was returned and do whatever you need to do with it now that you know what the duplicates are.

Regards,

Paul McKenzie

[gaar321]

Thanks a lot !