Алгоритм однозначного поиска ребер из полигональной сетки

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

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

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


geometry mesh polygon graphics edge-detection
person Peter Shinners    schedule 16.10.2008    source источник

Ответы (5)


arrow_upward
4
arrow_downward

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

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

person shoosh    schedule 16.10.2008
comment
если я правильно понимаю, вы получите уникальную хэш-карту первого уровня, но с большим количеством хэш-карт уровня 2 (по одной для каждого значения A). Интересно, действительно ли помогают хэш-карты уровня 2 °, достаточно ли значений B на этих вторых хэш-картах? - person labotsirc; 28.09.2011

arrow_upward
4
arrow_downward

Чтобы прояснить, вы хотите, чтобы список многоугольников был таким:

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

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

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

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

затем вы хотите удалить дублирующуюся кромку B - C и C - B и поделиться ею?

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

person Lasse V. Karlsen    schedule 16.10.2008

arrow_upward
2
arrow_downward

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

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

person Peter Shinners    schedule 17.10.2008

arrow_upward
1
arrow_downward

Вот реализация 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

person ideasman42    schedule 10.05.2013

arrow_upward
0
arrow_downward

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

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

Edge sampleEdge;

std::map<Edge, bool> uniqueEdges;

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

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

uniqueEdges[sampleEdge] = true;

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

person namespace sid    schedule 03.04.2012