CODEWITHSUNDEEP
c#wpfcollections3d
mandarin
mandarin

Reputation: 1386

How to search for values in Point3DCollection?

Basically I am using a MeshGeometry3D to load points, positions and normals from an STL file. The STL file format duplicates points, so I want to first search the MeshGeometry3D.Positions for duplicate before adding the newly read point.

The Mesh.Positions.IndexOf(somePoint3D) does not work, because it compares based on the object reference rather than the X, Y, Z values of the Point3D. This is why I am iterating the entire Collection to manually find duplicates:

//triangle is a custom class containing three vertices of type Point3D
//for each 3 points read from STL the triangle object is reinitialized

vertex1DuplicateIndex = -1;
vertex2DuplicateIndex = -1;
vertex3DuplicateIndex = -1;

for (int q = tempMesh.Positions.Count - 1; q >= 0; q--)
{
    if (vertex1DuplicateIndex != -1)
        if (tempMesh.Positions[q] == triangle.Vertex1)
            vertex1DuplicateIndex = q;

    if (vertex2DuplicateIndex != -1)
        if (tempMesh.Positions[q] == triangle.Vertex2)
            vertex2DuplicateIndex = q;

    if (vertex3DuplicateIndex != -1)
        if (tempMesh.Positions[q] == triangle.Vertex3)
            vertex3DuplicateIndex = q;

    if (vertex1DuplicateIndex != -1 && vertex2DuplicateIndex != -1 && vertex3DuplicateIndex != -1)
        break;
}

This code is actually very efficient when duplicates are found, but when there is no duplicate the collection is iterated entirely which is very slow for big meshes, with more than a million positions.

Is there another approach on the search?

Is there a way to force Mesh.Positions.IndexOf(newPoint3D) to compare based on value like the Mesh.Positions[index]==(somePoint3D), rather than the reference comparison it is doing now?

Upvotes: 0

Views: 307

Answers (2)

mandarin
mandarin

Reputation: 1386

Using hakononakani's idea I've managed to speed up a bit, using a combination of a HashSet and a Dictionary. The following is a simplified version of my code:

class CustomTriangle
{
    private Vector3D normal;
    private Point3D vertex1, vertex2, vertex3;
}

private void loadMesh()
{
    CustomTriangle triangle;
    MeshGeometry3D tempMesh = new MeshGeometry3D();
    HashSet<string> meshPositionsHashSet = new HashSet<string>();
    Dictionary<string, int> meshPositionsDict = new Dictionary<string, int>();
    int vertex1DuplicateIndex, vertex2DuplicateIndex, vertex3DuplicateIndex;
    int numberOfTriangles = GetNumberOfTriangles();

    for (int i = 0, j = 0; i < numberOfTriangles; i++)
    {
        triangle = ReadTriangleDataFromSTLFile();

        vertex1DuplicateIndex = -1;

        if (meshPositionsHashSet.Add(triangle.Vertex1.ToString()))
        {
            tempMesh.Positions.Add(triangle.Vertex1);
            meshPositionsDict.Add(triangle.Vertex1.ToString(), tempMesh.Positions.IndexOf(triangle.Vertex1));

            tempMesh.Normals.Add(triangle.Normal);
            tempMesh.TriangleIndices.Add(j++);
        }
        else
        {
            vertex1DuplicateIndex = meshPositionsDict[triangle.Vertex1.ToString()];
            tempMesh.TriangleIndices.Add(vertex1DuplicateIndex);
            tempMesh.Normals[vertex1DuplicateIndex] += triangle.Normal;
        }

        //Do the same for vertex2 and vertex3
    }
}

At the end tempMesh will have only unique points. All you have to do is normalize all Normals and you're ready to visualize.

The same can be achieved only with the Dictionary using:

if (!meshPositionsDict.Keys.Contains(triangle.Vertex1.ToString()))

I just like using the HashSet, because it's fun to work with :) In both cases the final result is a ~60 times faster algorithm than before!

Upvotes: 0

hakononakani
hakononakani

Reputation: 305

I don't know of a built in way to do this, but you could use a hash map to cache the indices of the 3D vectors. Depending of the quality of your hash functions for the vectors you'll have a 'sort of' constant lookup (no collisions are impossible, but it should be faster than iterating though all the vertex data for each new triangle point).

Upvotes: 1

Related Questions