Comparing list elements performance problem

F

FireScythe

Newcomer
Joined
Jun 18, 2006
Messages
4
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
 
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).

C#: 
//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
 
Back
Top