Vertex和Index数据解析效率低下，寻找更高效的方法

Question

我写了一个方法来解析包含顶点数据的数组。该方法的目标是根据该数据生成一个新的唯一顶点数组和一个新索引。

这是我用来在数组中存储顶点的结构。

struct Vertex: Hashable {
    var x, y, z,
    nx, ny, nz,
    s, t: Float

    var hashValue: Int {
        return "\(self.x),\(self.y),\(self.z),\(self.nx),\(self.ny),\(self.nz),\(self.s),\(self.t),".hashValue
    }

    static func ==(lhs: Vertex, rhs: Vertex) -> Bool {
        return lhs.hashValue == rhs.hashValue
    }
}

这是我用来创建唯一顶点数组和新索引的方法。该方法的第一个参数采用一个数组，其中包含已按原始索引排序的顶点数据。

func makeVertexIndex(_ array: [Float]) -> ([Vertex], [Int]) {
    var counter = 0
    var indexCounter = 0
    var holder = [Float]()
    var vertices = [Vertex]()
    var index = [Int]()

    for i in array {
        counter += 1

        if counter == 8 {
            counter = 0
            holder.append(i)
            let vertex = Vertex(x: holder[0], y: holder[1], z: holder[2],
                                nx: holder[3], ny: holder[4], nz: holder[5],
                                s: holder[6], t: holder[7])

            if vertices.contains(vertex) {
                guard let match = vertices.index(of: vertex) else { continue }
                index.append(match)
            } else {
                vertices.append(vertex)
                index.append(indexCounter)
                indexCounter += 1
            }

            holder.removeAll()
        } else {
            holder.append(i)
        }
    }

    return (vertices, index)
}

我能够成功解析较低三角形数的网格，但是当我尝试运行解析较高三角形数网格时，它花了一个多小时才运行。

我对编码很陌生，Swift 是我的第一语言，但我怀疑完成这项任务不应该花这么长时间，我可能只是写了我的方法真的很低效或者可能有我可以用完全不同的方式来解决这个问题。

无论如何，如果我能得到任何帮助，我将不胜感激。感谢阅读。

更新 1： 我重写了我的方法，首先创建顶点数组，然后将其更改为一个集合以使值唯一并返回数组，然后运行通过 vertexArray 循环在唯一顶点数组中查找匹配项。这个版本的方法将我的测试网格上的处理时间从 21 秒缩短到大约 12 秒。

func makeVertexIndex(_ array: [Float]) -> ([Vertex], [Int]) {
    var counter = 0
    var holder = [Float]()
    var vertexArray = [Vertex]()
    var vertices = [Vertex]()
    var index = [Int]()

    for i in array {
        counter += 1

        if counter == 8 {
            counter = 0
            holder.append(i)
            let vertex = Vertex(x: holder[0], y: holder[1], z: holder[2],
                                nx: holder[3], ny: holder[4], nz: holder[5],
                                s: holder[6], t: holder[7])

            vertexArray.append(vertex)

            holder.removeAll()
        } else {
            holder.append(i)
        }
    }

    let vertexSet = Set(vertexArray)
    vertices = Array(vertexSet)

    for v in vertexArray {
        guard let match = vertices.index(of: v) else { continue }
        index.append(match)
    }

    return (vertices, index)
}

更新二：

这是我在实施一些推荐的解决方案后更新的结构和方法。

结构：

struct Vertex: Hashable {
    var x, y, z,
    nx, ny, nz,
    s, t: Float

    var hashValue: Int {
        return "\(self.x),\(self.y),\(self.z),\(self.nx),\(self.ny),\(self.nz),\(self.s),\(self.t)".hashValue
    }

    static func ==(lhs: Vertex, rhs: Vertex) -> Bool {
        return (lhs.x == rhs.x) && (lhs.y == rhs.y) && (lhs.z == rhs.z) && (lhs.nx == rhs.nx) &&
            (lhs.ny == rhs.ny) && (lhs.nz == rhs.nz) && (lhs.s == rhs.s) && (lhs.t == rhs.t)
    }
}

方法：

    func makeVertexIndex(_ array: [Float]) -> ([Vertex], [Int]) {
        var vertexArray = [Vertex]()
        vertexArray.reserveCapacity(array.count / 8)

        var vertices = [Vertex]()
        var index = [Int]()

        // Creating an array of Vertex from an array containing 
        // position/normal/texcoord in correct order.
        for i in stride(from: 0, to: array.count, by: 8) {
            let vertex = Vertex(x: array[i], y: array[i + 1], z: array[i + 2],
                                nx: array[i + 3], ny: array[i + 4], nz: array[i + 5],
                                s: array[i + 6], t: array[i + 7])

            vertexArray.append(vertex)
        }

        // Making the Vertex array unique by converting to set and back to array.
        let vertexSet = Set(vertexArray)
        vertices = Array(vertexSet)

        // Making new index by finding the matching vertex in the 
        // unique vertex array and adding that array index to the new index
        for v in vertexArray {
            guard let match = vertices.index(of: v) else { continue }
            index.append(match)
        }

        return (vertices, index)
    }

在尝试了推荐解决方案的各个部分后，该方法能够在 13 分钟内处理一个包含 70K 个三角形的模型，而之前需要一个半小时以上。

所以这是一个巨大的改进，感谢迄今为止的所有解决方案，将其开放一两天，看看是否有其他建议。

Answer 1

您的 == 代码比较哈希而不是每个属性是否有特殊原因？即

static func ==(lhs: Vertex, rhs: Vertex) -> Bool {
    return (lhs.x == rhs.x) && (lhs.y == rhs.y) && (lhs.z == rhs.z) &&
        (lhs.nx == rhs.nx) && ...etc
}

然后如果lhs.x不等于rhs.x，代码会很快失败并继续下一个。目前，您不得不一次又一次地创建哈希值。或者，您可以通过在构造函数中计算一次哈希来加速当前代码（并且，例如，使所有属性 private(set) 像下面的简化示例一样）。

struct Vertex {
    private(set) var x, y: Float
    let hash: Int

    init(x: Float, y: Float) {
        self.x = x
        self.y = y
        hash = "\(x),\(y)".hashValue
    }

    static func ==(lhs: Vertex, rhs: Vertex) -> Bool {
        return lhs.x == rhs.x
    }
}

let vertex = Vertex(x: 1.0, y: 2.0)
print(vertex.hash)

Answer 2

您似乎正试图以一组新的顶点和一组索引结束。如果新的一组顶点包含重复项，则将其从顶点列表中删除，并将重复项的索引加倍。从你的第一个功能来看。你的第二个只在匹配时添加了一个索引。你指的是什么？

从一开始.. 如果您有 V1 V2 V3 V4，并且 V4 = V1，您需要索引 [0,0,1,2]。

这是正确的吗？我会通过一次迭代浮点数组 8 来清理它，然后确定是否有重复项，如果有，找出哪些是重复项，然后创建最后两个数组。这是我的看法..

func makeVertexIndex(_ array: [Float]) -> ([Vertex], [Int]) {

    var newVertices = [Vertex]()
    for i in stride(from: 0, to: array.count, by: 8) {
        newVertices.append(Vertex(x: array[i], y: array[i + 1], z: array[i + 2],
                               nx: array[i + 3], ny: array[i + 4], nz: array[i + 5],
                               s: array[i + 6], t: array[i + 7]))

    }


    if newVertices.count > Set(newVertices).count {
        var uniqueVertices = [Vertex]()
        var indices = [Int]()

        var vertexIndex = [Vertex: Int]()
        var count = 0

        for vertex in newVertices {
            if let existingVertex = vertexIndex[vertex] {
                indices.append(existingVertex)
            } else {
                vertexIndex[vertex] = count
                uniqueVertices.append(vertex)
                count += 1
            }
        }

        return (uniqueVertices, indices.sorted())

    } else {
        return (newVertices, [Int](0..<newVertices.count))

    }
}

Vertex和Index数据解析效率低下，寻找更高效的方法

Inefficient parsing of Vertex and Index data, looking for more efficient methods

arrays

scenekit

swift

metal