Построение данных о смежности треугольников

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

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

Я знаю, что для любого данного треугольника в списке, индексы {0, 1}, {1, 2} и {2, 0} (или {n, n + 1}, {n + 1, n + 2}, { n + 2, n}, если вы предпочитаете) его формы; Индексный список правильно сформирован и правильно соблюдает порядок намотки.

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

Я знаю, что в списке смежности каждый исходный треугольник представлен 6 индексами, исходные индексы идут в слоты 0, 2, 4; новые индексы для завершения смежности идут в слоты 1, 3, 5. Индекс для завершения для ребра {0, 1} входит в слот 1, индекс для завершения для ребра {1, 2} идет в слот 3, индекс для завершения для ребра {2, 1} переходит в слот 5.

Что я пробовал?

Я пробовал перебор, и да, это сработает, но я придерживаюсь более элегантного подхода.

Я пробовал Эрика Ленгеля для построения краевого списка, но (1) он, кажется, не соответствует первоначальному порядку треугольника, (2) он не соответствует порядку намотки, (3) он так же ясен, как грязь, куда идти затем, после того как вы построили список краев, и (4) у меня есть подозрение на пример кода, в котором есть такие очевидные явные ошибки, как «triangleIndex» и «faceIndex» - автор даже скомпилировал код, не говоря уже о том, чтобы запустить его проверить это?

Итак, какие-либо предложения или указатели здесь?

Я бы попытался использовать хеш-таблицу для этого (например, std::unordered_mapесли вы находитесь в C ++). Создайте хеш-таблицу, которая отображается от полуграда (выраженного в виде пары индексов по порядку) к третьему индексу треугольника, которому принадлежит полугол.

Это можно построить, просто выполнив итерацию по списку треугольников и добавив три полуголия каждого треугольника в хеш-таблицу. Если ваш начальный индексный список содержит пару смежных треугольников (0, 1, 2, 2, 1, 3), вы получите хеш-таблицу, содержащую:

(0, 1) -> 2
(1, 2) -> 0
(2, 0) -> 1
(2, 1) -> 3
(1, 3) -> 2
(3, 2) -> 1

Обратите внимание, что ребра (1, 2) и (2, 1) оба появляются в таблице, представляя две стороны ребра и указывая на третью вершину каждого из двух треугольников.

Затем, чтобы построить данные смежности, все, что вам нужно сделать, это повторить список треугольников и запросить ребра каждого треугольника с противоположной обмоткой. Таким образом, при обработке треугольника (0, 1, 2) вы будете запрашивать ребра (1, 0), (2, 1) и (0, 2). Это найдет противоположную вершину каждого ребра, если оно существует.

Посмотрите на половинную структуру данных .

Идея примерно такова, что вы храните список половин ребер , например, половину определенного ребра, прикрепленного к конкретной грани. Эта структура затем также хранит информацию о соответствующем половинном ребре для примыкающей грани.

Структура данных делает запросы о связности, смежности и т. Д. Очень эффективными. Существуют алгоритмы для эффективной генерации данных, хотя и не обязательно для эффективного «выполнения игры» (вы, вероятно, захотите сделать это в автономном режиме в своем конвейере ресурсов).

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