Как я могу эффективно обнаружить пересечение обнаружения луча и сетки?

Question

У меня есть несколько 3d моделей в приложении OpenGL ES для iPhone, и в какой-то момент я хочу, чтобы пользователь коснулся экрана и начал действовать на них. Проблема состоит в том, чтобы распознать, какие из них были отображены на экране. Чтобы добиться этого, я рассчитал луч выбора, как предложено в FAQ по OpenGL, и теперь я хочу определить, пересекается ли он с какой-либо моделью.

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

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

Answer 1

Вы совершенно правы, есть лучшие способы пройти через дерево. Один из методов - построить октаву вокруг объекта. Затем, если луч пересекает один из 8 сегментов, вы можете проверить, с каким из его 8 дочерних элементов он пересекается, и так далее, пока у вас не останется несколько треугольников для проведения теста на пересечение. Другой способ - построить K-d дерево .

Существует много способов эффективно решить эту проблему. Посмотрите информацию о структурах ускорения трассировки лучей .