Алгоритм поиска уникальных ребер из полигональной сетки

Question

Я ищу хороший алгоритм, который сможет дать мне уникальные края из набора полигональных данных.В этом случае полигоны определяются двумя массивами.Один массив — это количество точек на полигон, а другой массив — это список индексов вершин.

У меня есть версия, которая работает, но производительность снижается при достижении более 500 000 полигонов.Моя версия проходит по каждой грани и добавляет отсортированные вершины каждого ребра в stl::set.Мой набор данных будет в основном состоять из треугольников и четырехугольников, и большинство ребер будут общими.

Есть ли более разумный алгоритм для этого?

Answer 1

Да
Используйте двойную хэш-карту.
Каждое ребро имеет два индекса A,B.допустим, что А > Б.
Первая хеш-карта верхнего уровня сопоставляет A с другой хеш-картой, которая, в свою очередь, сопоставляет B с некоторым значением, представляющим нужную вам информацию о каждом ребре.(или просто логическое значение, если вам не нужно хранить информацию о ребрах).
По сути, это создает двухуровневое дерево, состоящее из хэш-карт.

Чтобы найти ребро в этой структуре, вы берете больший индекс, ищете его на верхнем уровне и получаете хеш-карту.затем возьмите меньший индекс и найдите его во второй хэш-карте.

Answer 2

Просто чтобы уточнить, вам нужен такой список полигонов:

A +-----+ B
   \    |\
    \ 1 | \
     \  |  \
      \ | 2 \
       \|    \
      C +-----+ D

Тогда вместо ребер вот так:

A - B -+
B - C  +- first polygon
C - A -+

B - D -+
D - C  +- second polygon
C - B -+

тогда вы хотите удалить дубликат B-C vs.Край C-B и поделитесь им?

Какую проблему с производительностью вы наблюдаете в своем алгоритме?Я бы сказал, что набор с разумной реализацией хеширования должен работать вполне нормально.С другой стороны, если ваш хеш не оптимален для данных, у вас возникнет множество коллизий, которые могут плохо повлиять на производительность.

Answer 3

Вы оба правы.Использование хорошего хешсета позволило повысить производительность намного выше требуемого уровня.В итоге я создал свой собственный небольшой хэш-набор.

Общее количество ребер будет между N/2 и N.N — количество уникальных вершин в сетке.Все общие ребра будут N/2, а все уникальные ребра будут N.Оттуда я выделяю буфер uint64 и упаковываю свои индексы в эти значения.Используя небольшой набор уникальных таблиц, я могу быстро найти уникальные ребра!

Answer 4

Вот реализация хеширования ребер на языке C, используемая в Blender именно с целью быстрого создания ребер из граней, может дать некоторые подсказки другим, чтобы они могли создать свои собственные.

http://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/edgehash.c

http://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/BLI_edgehash.h

Здесь используется BLI_mempool,https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/intern/BLI_mempool.c

https://gitorious.org/blenderprojects/blender/blobs/master/blender/source/blender/blenlib/BLI_mempool.h

Answer 5

Сначала вам нужно убедиться, что ваши вершины уникальны.Это если вам нужно только одно ребро в определенной позиции.Затем я использую эту структуру данных

typedef std::pair<int, int> Edge;

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

Edge содержит индексы вершин, составляющих ребро, в отсортированном порядке.Следовательно, если sampleEdge представляет собой ребро, состоящее из вершин с номерами индексов 12 и 5, sampleEdge.first = 5 и sampleEdge.12

Тогда вы можете просто сделать

uniqueEdges[sampleEdge] = true;

для всех ребер.uniqueEdges будет содержать все уникальные ребра.