java—查找重复顶点的一种快速方法obj、colladae文件

我已经阅读了这篇关于正确加载纹理坐标的文章，它都正常工作，但这里的问题在于速度。
基本上，我们的想法是寻找一个先前处理的顶点，该顶点可能与当前正在处理的顶点具有完全相同的属性值，如果存在这样的顶点，请将该顶点索引值用作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<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个顶点上找到我们的重复顶点，这很糟糕，因为加载standford dragon模型花了我7秒钟，但是如果我完全放弃寻找过程，只使用重复的顶点，只需要1.5秒钟。
我想到的一个优化是，自从我使用java以来，就是利用java14的并行流的能力来寻找这样的副本。

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

但这是一个更可怕的想法，因为我现在花了12秒加载。一个可能的原因是，为每个要处理的newvertex生成100个线程是一个巨大的开销。
他在帖子中提到，他在排序的顶点上使用二进制搜索来更快地寻找重复的顶点，但在这方面有一些问题
当顶点有多个属性时，根据什么属性对顶点排序？
在arraylist上进行二进制搜索的一种方法是使用collections框架中构建的一种方法，但是如何告诉比较器一个顶点是小于还是大于另一个顶点呢？
它已经变得如此缓慢的大型模型，我不得不给用户选择消除重复的标志。
有更好的办法吗？

在顶点列表中搜索会非常慢，不确定big-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 本质上是一个顶点表及其关联索引。
按顶点执行的唯一工作是哈希代码的计算，它将比搜索快得多（而且相当简单）。
编辑：显然，这需要您在vertex类上实现一个像样的哈希代码实现，如下所示：

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

java—查找重复顶点的一种快速方法obj、colladae文件

1条答案

相关问题

热门标签

最新问答