Найти уникальные вершины из «супа-треугольника»

Question

Я создаю конвертер CAD-файлов поверх двух библиотек (Opencascade и DWF Toolkit).

Однако, мой вопрос не зависит от платформы:

Дано:

Я сгенерировал сетку, поскольку список треугольных граней образует модель, построенную через мое приложение. Каждый треугольник определяется тремя вершинами, которые состоят из трех чисел с плавающей точкой (координаты x, y и z). Поскольку треугольники образуют сетку, большинство вершин разделены более чем одним треугольником.

Цель:

Мне нужно найти список уникальных вершин и сгенерировать массив граней, состоящий из кортежей из трех индексов в этом списке.

Что я хочу сделать, это:

//step 1: build a list of unique vertices
for each triangle
   for each vertex in triangle
      if not vertex in listOfVertices
         Add vertex to listOfVertices

//step 2: build a list of faces 
for each triangle
   for each vertex in triangle
      Get Vertex Index From listOfvertices
      AddToMap(vertex Index, triangle)

Хотя у меня есть реализация, которая делает это, шаг 1 (генерация списка уникальных вершин) действительно медленный в порядке O (n!), Поскольку каждая вершина сравнивается со всеми вершинами, уже имеющимися в списке. Я подумал: «Эй, давайте создадим хэш-карту компонентов моих вершин, используя std :: map, что должно ускорить процесс!», Только чтобы обнаружить, что генерирование уникального ключа из трех значений с плавающей запятой не является тривиальной задачей.

Здесь в игру вступают эксперты stackoverflow: мне нужна какая-то хеш-функция, которая работает с 3 числами с плавающей запятой, или любая другая функция, генерирующая уникальное значение из позиции 3d-вершины.

Answer 1

Три решения. Есть, конечно, другие

1. Используйте хэш-карту. Это будет работать только в том случае, если «тот же» означает точно такой же
2. Используйте двоичное пространство, чтобы разделить точки
3. Используйте регулярную сетку, чтобы разделить ваши очки.

В случаях 2 и 3, если вы хотите указать какой-либо допуск, вам нужно будет искать более одной части дерева или сетки. В случае BSP это означает, что вы проверяете, находитесь ли вы в пределах допуска плоскости деления, и, если это так, повторяются в обе половины. В случае сетки это означает проверку всех соседних ячеек, которые находятся в пределах допуска. Ничего из этого не является слишком сложным, но означает, что будет труднее использовать решение «с полки».

Answer 2

Дамп всех вершин в массиве, затем выполните unique(sort(array)). Это должно быть O (k n log (n)), где k - это среднее число треугольников, имеющих общую вершину, обычно k <7. </p>

Единственное предостережение, о котором я могу подумать, это то, что ваша функция unique должна иметь возможность взять указатель на функцию сравнения, поскольку вы, вероятно, захотите считать свои вершины равными, если

distance(vertex1, vertex2) < threshold

но похоже, что ОК .

Answer 3

Общая идея получения хеша - умножить каждый битовый шаблон с плавающей точкой на простое и сложить их вместе. Примерно так:

unsigned int hash_point(float x, float y, float z)
{
   unsigned int* px = (unsigned int*)&x;
   unsigned int* py = (unsigned int*)&y;
   unsigned int* pz = (unsigned int*)&z;

   return (*px)*PRIME1 + (*py)*PRIME2 + (*pz)*PRIME3;
}

Вы должны заметить, что sizeof (unsigned int) здесь считается равным sizeof (float). Пример приведен только для иллюстрации основной идеи, вам следует настроить ее под свои нужды.