Существует ли известный «наиболее эффективный» алгоритм для обнаружения столкновений AABB и Ray?
Недавно я наткнулся на алгоритм коллизии AABB и Sphere от Arvo, и мне интересно, есть ли такой же заслуживающий внимания алгоритм для этого.
Необходимо иметь условие для этого алгоритма, что мне нужно иметь возможность запрашивать результат для расстояния от источника луча до точки столкновения. Сказав это, если есть другой, более быстрый алгоритм, который не возвращает расстояние, то в дополнение к публикации того, который делает, также публикация этого алгоритма была бы очень полезной.
Пожалуйста, также укажите, что является аргументом возврата функции и как вы используете его для возврата расстояния или случая отсутствия столкновения. Например, есть ли у него параметр out для расстояния, а также значение возврата bool? или он просто возвращает float с расстоянием, против значения -1, без столкновений?
(Для тех, кто не знает: AABB = Ограничивающая рамка с выравниванием по оси)
источник
Ответы:
Эндрю Ву, который вместе с Джоном Аманатидесом разработал алгоритм лучевой метки (DDA), повсеместно используемый в raytracers, написал «Fast Ray-Box Intersection» (альтернативный источник здесь ), который был опубликован в Graphics Gems, 1990, pp. 395-396. Вместо того, чтобы быть построенным специально для интеграции через сетку (например, объем вокселя), как DDA (см. Ответ zacharmarz), этот алгоритм специально подходит для миров, которые не подразделяются равномерно, таких как ваш типичный мир многогранников, встречающийся в большинстве 3D игры.
Подход обеспечивает поддержку 3D и, при желании, делает выборку задней поверхности. Алгоритм основан на тех же принципах интеграции, которые используются в DDA, поэтому он очень быстрый. Более подробную информацию можно найти в оригинальном томе Graphics Gems (1990).
Многие другие подходы специально для Ray-AABB можно найти на realtimerendering.com .
РЕДАКТИРОВАТЬ: альтернативный подход без ответвлений - что было бы желательно для GPU и CPU - можно найти здесь .
источник
То, что я использовал ранее в моем raytracer:
Если это возвращает true, это пересекается, если это возвращает false, это не пересекается.
Если вы используете один и тот же луч много раз, вы можете выполнить предварительные вычисления
dirfrac
(только деление во всем тесте пересечения). И тогда это действительно быстро. И у вас есть также длина луча до пересечения (хранится вt
).источник
Никто не описал алгоритм здесь, но алгоритм Graphics Gems просто:
Используя вектор направления вашего луча, определите, какие 3 из 6 возможных самолетов будут поражены первыми . Если ваш (ненормализованный) вектор направления луча равен (-1, 1, -1), то можно нанести удар по 3 плоскостям: + x, -y и + z.
Из 3 возможных плоскостей найдите t-значение для пересечения для каждого. Примите плоскость, которая получает наибольшее значение t, как самолет, который получил удар, и проверьте, что попадание находится внутри коробки . Диаграмма в тексте проясняет это:
Моя реализация:
источник
Это мое пересечение 3D ray / AABox, которое я использовал:
источник
tnear
иtfar
?Вот оптимизированная версия выше, которую я использую для GPU:
источник
Одна вещь, которую вы, возможно, захотите исследовать, это растеризация передней и задней сторон вашей ограничительной рамки в двух отдельных буферах. Отобразите значения x, y, z как rgb (это лучше всего подходит для ограничительной рамки с одним углом в (0,0,0) и противоположным в (1,1,1).
Очевидно, что это ограниченное использование, но я нашел его отличным для рендеринга простых томов.
Для более подробной информации и кода:
http://www.daimi.au.dk/~trier/?page_id=98
источник
Вот код Line против AABB, который я использовал:
источник
Это похоже на код, размещенный zacharmarz.
Я получил этот код из книги Кристера Эриксона «Обнаружение столкновений в реальном времени» в разделе «5.3.3. Пересекающийся луч или сегмент против прямоугольника».
источник
Я удивлен, увидев, что никто не упомянул метод Тавиана без ветвей
Полное объяснение: https://tavianator.com/fast-branchless-raybounding-box-intersections/
источник
Я добавил к @zacharmarz ответ для обработки, когда источник луча находится внутри AABB. В этом случае tmin будет отрицательным и позади луча, поэтому tmax является первым пересечением между лучом и AABB.
источник