查找重复顶点 Obj、Colladae 文件的更快方法

Question

我已经阅读了 post 关于正确加载纹理坐标的内容，并且一切正常，但这里的问题在于速度。

基本上，我们的想法是寻找一个较早处理的顶点，该顶点可能具有与当前正在处理的顶点完全相同的属性值，如果存在这样的顶点，请将该顶点索引值用于您的 indexBuffer 并继续。非常简单的概念和实现，这就是我是如何做到的

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;
 }
}

最后我们有一个 ArrayList

ArrayList<Vertex> vertices=new ArrayList();

对于从文件中读取的每个顶点，这个想法很简单

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
}

虽然这会产生正确的结果，但问题是性能，因为对于添加的每第 n 个顶点，我们都必须进行“线性搜索！！！”在之前添加的 n-1 个顶点上找到我们的重复顶点，这很糟糕，因为我花了 7 秒来加载 Standford dragon 模型，但如果我完全放弃查找过程并只使用重复项，它只需要 1.5 秒。

我想到的一个优化是因为我正在使用 java 是利用 java 14 的并行流的力量来寻找这样的重复项。

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

但这是一个更糟糕的想法，因为我现在需要 12 秒才能加载。一个可能的原因可能是为每个要处理的新顶点生成 100 个线程是一个巨大的开销。

他在 post 中提到他在排序的顶点上使用二进制搜索来更快地查找重复项，但对此有一些疑问

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?

对于大型模型，它变得如此缓慢，以至于我必须让用户选择使用标志消除重复项。

有没有更好的方法？

Answer 1

搜索顶点列表会非常慢，不确定大 O 表示是什么，但我想它不会很漂亮。

而是使用某种散列机制来查找现有顶点 - 这是我实现的代码片段，用于从包含重复顶点的 OBJ 文件构建模型：

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;
    }
}

map 本质上是一个 table 顶点及其相关索引。

对每个顶点执行的唯一工作是哈希码的计算，这将比搜索快得多（而且要简单得多）。

编辑：显然，这要求您在顶点 class 上实现了一个像样的哈希码实现，如下所示：

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);
    }
}

查找重复顶点 Obj、Colladae 文件的更快方法

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

java

duplicates

vertex