Неэффективный анализ данных вершин и индексов, поиск более эффективных методов

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 - это мой первый язык, но я подозреваю, что не стоит так долго выполнять эту задачу, и я, вероятно, просто написал свой метод действительно неэффективно или, может быть, подходить к этой проблеме.

В любом случае, я был бы признателен за любую помощь, которую я мог бы получить. Спасибо за прочтение.

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

Update 2:

Вот моя обновленная структура и метод после реализации некоторых рекомендуемых решений.

Struct:

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

После попытки различных частей рекомендуемых решений метода был в состоянии обработать модель с 70K треугольников в 13 минут, ранее он принял полтора часа.

Так что это было огромное улучшение, оценили все решения до сих пор, чтобы держать это открытым, возможно, через день или два, чтобы узнать, приходят ли какие-либо другие рекомендации.

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

    } 
}