Быстрые способы отфильтровать список треугольников перед выполнением теста SAT против AABB

Я пытаюсь выполнить пересечение треугольников AABB с треугольниками, исходящими из сетки триадов, а AABB - отдельными ячейками из структурированной трехмерной сетки / вокселя. Существуют ли какие-либо умные способы/алгоритмы, которые я мог бы использовать для фильтрации и уменьшения количества треугольников и комбинаций AABB, с которыми мне пришлось бы выполнять тест SAT? В настоящее время я проверяю каждый треугольник по каждой ячейке сетки, что неэффективно. Я также рассматривал возможность фильтрации треугольников на основе расстояния до центра тяжести и максимального размера треугольника в сетке треугольников в качестве допуска. Но это снова потребует перебора всех треугольников. Я также рассматривал K-ближайших соседей.


c++ mesh intersection voxel separating-axis-theorem
person Shriram Krishna    schedule 28.07.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Есть несколько хорошо известных методов, таких как:

  1. дать AABB каждому треугольнику. Итак, сначала вы делаете пересечение AABB против AABB. Цель состоит в том, чтобы быстро отбросить непересекающиеся треугольники.

  2. Когда у вас есть все треугольники внутри AABB, вы можете выполнять массовое обнаружение столкновений между AABB, используя такие алгоритмы, как I-COLLIDE. Вы также можете создать AABB-дерево (также известное как Bounding-Volume-Hierarchy или BVH) для сетки, чтобы сразу отбросить огромное количество непересекающихся треугольников.

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

person Mauricio Cele Lopez Belon    schedule 04.08.2020