A faster way to look for duplicate vertices Obj,Colladae files

Question

I have read this post on correctly loading texture coordinates and it all works correctly but the problem here lies in speed.

Basically the idea is to look for an vertex processed earlier that may have the exact same attribute values as the current one being processed and if such a vertex exist, use that vertex index value for your indexBuffer and move on. Very simple concept and implementation ,here is how i have done it

class Vertex
{
 //The index values read from a file either by processing the f attribute in obj files or the <p> attribute for meshes in colladae files
 private final int
 vertexIndex,
 texCoordIndex,
 normalIndex,
 colorIndex;

 //The actual values for each attribute used in the mesh
 private final Vector3f
 vertex=new Vector3f(),
 normal=new Vector3f(),
 color=new Vector3f();
 private final Vector2f texCoord=new Vector2f();

 @Override
 public boolean equals(Object obj)//The key method used for finding duplicate vertices from the list
 {
  Vertex v=(Vertex)obj;

  //Check if every attribute of both are same
  return    this.vertexIndex==v.VertexIndex
         && this.texCoordIndex==v.texCoordIndex
         && this.normalIndex==v.normalIndex
         && this.colorIndex==v.colorIndex;
 }
}

Finaly we have an ArrayList of these

ArrayList<Vertex> vertices=new ArrayList();

And for every vertex read from the file the idea is simple

Vertex newVertex=readFromFile();

int prev=vertices.indexOf(newVertex);
if(prev!=-1)//We have found an similar vertex from before so use that 
{
 indexBuffer.add(prev); //the indexBuffer will use the vertex at that position
}
else
{
 vertices.add(newVertex); //Add  new vertex
 indexBuffer.add(vertices.size()-1);//New Vertex Index is simply the index of last element in the list
}

And while this yields correct results the problem is performance because for every nth vertex added we have to do an "LINEAR SEARCH!!!" on the previous n-1 vertices added before it to find our duplicate vertex which is terrible because it took me 7 seconds to load the Standford dragon model but if i completly discard the looking process and just live with the duplicates it took just 1.5 seconds.

An optimization i thought of was since i am using java was to harness the power of parallel streams of java 14 to look for duplicates like this.

Optional<Vertex> possibleDuplicate=vertices.stream()
                                           .parallel()
                                           .filter(prev->prev.equals(newVertex))
                                           .findFirst();

But this was an even more terrible idea as it took me now 12 seconds to load. A possible reason could be that spawning 100's of threads for every newVertex to be processed is an huge overhead.

He mentions in the post he used binary search on the sorted vertices to look for duplicates faster but some questions on that

Based on what attribute do i sort the vertices when the vertex has multiple attributes?

One way to do binary search on the ArrayList is by using the one built in the collections framework but how do i tell the comparator if one Vertex is less that or greater than the other?

It has gotten so slow for large models that i have to give the user the choice of eliminating duplicates with an flag.

Is there a better way?

Answer 1

Searching through the list of vertices is going to be incredibly slow, not sure what the big-O representation would be but I imagine it wouldn't be pretty.

Instead use some sort of hashing mechanism to lookup an existing vertex - here is a fragment of the code I implemented to construct a model from an OBJ file that contains duplicate vertices:

public static class IndexedBuilder extends Builder {
    private final List<Integer> index = new ArrayList<>();
    private final Map<Vertex, Integer> map = new HashMap<>();

    @Override
    public IndexedBuilder add(Vertex vertex) {
        // Lookup existing vertex index
        final Integer prev = map.get(vertex);

        // Add new vertices
        if(prev == null) {
            // Add new vertex
            final int next = index.size();
            index.add(next);
            map.put(vertex, next);
            super.add(vertex);
        }
        else {
            // Existing vertex
            index.add(prev);
        }

        return this;
    }
}

The map is essentially a table of vertices with their associated index.

The only work to perform per-vertex is the calculation of the hash-code which will be much, much faster than searching (and is considerably simpler).

EDIT: Obviously this requires you to have implemented a decent hash-code implementation on your vertex class, something like this:

class Point {
    public final float x, y, z;

    @Override
    public int hashCode() {
        return Objects.hash(x, y, z);
    }
}

// Similar for normals & texture coordinates

class Vertex {
    private final Point point;
    private final Vector normal;
    private final TextureCoordinate coords;

    @Override
    public int hashCode() {
        return Objects.hash(point, normal, coords);
    }
}