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

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

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

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

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

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

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

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

9 голосов | спросил Maximus Minimus 12 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 12 Sep 2013 21:12:37 +0400 2013, 21:12:37

2 ответа


11

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

ответил Nathan Reed 12 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 12 Sep 2013 21:42:54 +0400 2013, 21:42:54
2

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

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

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

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

ответил Sean Middleditch 12 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 12 Sep 2013 22:30:23 +0400 2013, 22:30:23

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132