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

Question

Существуют индексные и вершинные буферы, подобные описанным здесь для рисования треугольников .

Часто в моем коде мне нужно искать, какие треугольники имеют определенные c вершина. Наиболее базовый c подход:

• К l oop над индексным буфером и находим треугольники, которые содержат индекс этой указанной c вершины.

Теперь мне интересно, не хватает ли мне более эффективных или стандартных алгоритмов. Спасибо.

Answer 1

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

Она может быть создана путем циклического перемещения по буферу индекса и добавления треугольника ко всем трем его вершинам.

Например, если буфер индекса:

0, 1, 4
0, 2, 3

Таблица поиска будет

0 -> [t0, t1]
1 -> [t0]
2 -> [t1]
3 -> [t1]
4 -> [t0]

Если данные обновляются, эта таблица поиска должна будет обновляется соответственно. В зависимости от того, сколько может быть количество треугольников, разделяющих одну вершину, и от того, как часто вы добавляете / удаляете их, вам может понадобиться таблица ha sh вместо обычного списка для хранения этих треугольников.