Comparing list elements performance problem

[FireScythe]

Hello, i'm having a problem with the speed of a piece of my code. I'm working with 3D models which have been broken up into chunks, which I am converting into a single object in an .obj file. The problem with this is that because some vertices have been duplicated to split the model the smoothing is incorrect, so this code goes through every vertex and compares it with all other vertices to see if the position and normal data is the same, and if it is it re-references the duplicates to a single vertex.

 

The problem with my code is that 13,000 vertices takes approximately 33 seconds and these models can have over 100,000 vertices, which takes many minutes to complete. So i was wondering it there was a quicker way to perform the comparision (prefereably in safe code).

 

[csharp]//"Vertices" is a List of vertices which contain position, normal and texture coordinate information

//"removeVerts" is a List of int's defining which indices need to be changed

//"replaceVerts" is a List of int's defining what the indices in removeVerts need to be changed to

foreach (ProjectTag.vertex vert in Vertices)

{

//If this vertex has already been re-referenced move on to the next one

if (removeVerts.Contains(Vertices.IndexOf(vert)))

continue;

//Get a list of all vertices which have the same position and normal values

List<ProjectTag.vertex> Defs = Vertices.FindAll(

delegate(ProjectTag.vertex v)

{

return

vert.position.X == v.position.X &&

vert.position.Y == v.position.Y &&

vert.position.Z == v.position.Z &&

vert.normal.I == v.normal.I &&

vert.normal.J == v.normal.J &&

vert.normal.K == v.normal.K;

}

);

//If the count is 1 then we would be re-referencing a vertex to itself, so we move on

if (Defs.Count > 1)

{

foreach (ProjectTag.vertex D in Defs)

{

//Get the index to change

int index = Vertices.IndexOf(D);

//Get the index to change to

int vertindex = Vertices.IndexOf(vert);

//Check we are not changing it to itself

if (index != vertindex)

{

//Add the current and changed indices which are used later

removeVerts.Add(index);

replaceVerts.Add(vertindex);

}

}

}

}[/csharp]

Thanks, FireScythe

[FireScythe]

Well, i've made progress with this so I thought i'd post it here. I managed to redo my code to be much faster (the 13,000 verticies mentioned above now only takes 3-4 seconds rather than 33).

 

//Stores the new Indicies
List<int> IndexList = new List<int>();
//Stores already compared position and normal values
List<float[]> testVerts = new List<float[]>();
//Holds the indicies of the tested values above
List<int> replaceVerts = new List<int>();

//Loop through all verticies
for (int i = 0; i < Vertices.Count; i++)
{
   //Get the values to test
   float[] test = new float[6]
   {
       Vertices[i].position.X,
       Vertices[i].position.Y,
       Vertices[i].position.Z,
       Vertices[i].normal.I,
       Vertices[i].normal.J,
       Vertices[i].normal.K
   };
   //Find out if these values are already stored
   float[] found = testVerts.Find(
       delegate (float[] f)
       {                        
           return 
                test[0] == f[0] &&
                test[1] == f[1] &&
                test[2] == f[2] &&
                test[3] == f[3] &&
                test[4] == f[4] &&
                test[5] == f[5];
        });

   if (found == null)
   {   
       //If not found add them
       testVerts.Add(test);
       replaceVerts.Add(i);
       //As the values were not found, set the index to i (no change)
       IndexList.Add(i);
   }
   else
   {
       //The values were found so set the index to the index of the found values 
       IndexList.Add(replaceVerts[testVerts.IndexOf(found)]);
   }
}
// Later code uses the IndexList to reference the correct vertex, thus ignoring any duplicates