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

Question

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

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

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

Answer 1

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

Существует много способов эффективного решения этой проблемы. Посмотрите информацию об ray tracing acceleration structures.