Бесконечная поверхность конуса * Проверка пересечения AABB

Question

Я пытаюсь найти более быстрый алгоритм для проверки того, пересекает ли выровненная по оси коническая поверхность объем ограничивающего прямоугольника, выровненного по оси.

Текущий разработанный мной алгоритмследующим образом:

• x = 0
• Для каждого из 4 параллельных ребер AABB:
  • Пересечь его линиюс конусом.
  • Если точка пересечения находится внутри AABB:
    • Вернуть true.
  • Если точка пересечения находится на определенной сторонеAABB:
    • x + = 1
• Если x == 0 или x == 4 (все пересечения были на одной сторонеAABB):
  • Вернуть false.
• Вернуть true.

Кто-нибудь может придумать более эффективный?Похоже, что это делает большую дополнительную работу, вычисляя каждое пересечение линии.

РЕДАКТИРОВАТЬ:

Выше алгоритм плох, например:

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

РЕДАКТИРОВАТЬ РЕДАКТИРОВАТЬ: см. мой собственный ответ ниже для решения, которое я позже обнаружил, что мне кажется почти оптимальным.

Answer 1

Я нашел возможно оптимальное решение:

Уравнение для единичного правого конуса, открывающегося вдоль оси + -z, равно x^2 + y^2 - z^2 = 0.

Найдите максимальное и минимальное значение x^2 + y^2 - z^2по AABB, используя арифметический интервал .Подсказка: для x^2 минимум составляет clamp(0, [xmin, xmax])^2, а максимум - max(xmin^2, xmax^2).

• Если полученный интервал является полностью отрицательным, прямоугольник полностью находится внутри конуса.
• Если результирующий интервал содержит 0, прямоугольник пересекает поверхность конуса.
• Если результирующий интервал является полностью положительным, прямоугольник полностью выходит за пределы конуса.

Answer 2

Глядя на эту таблицу тестов пересечения объекта / объекта кажется, что нет известного теста на пересечение конуса / AABB.Так что, боюсь, вы сами по себе!

Вы можете начать со статьи Дэвида Эберли " Пересечение треугольника и конуса " и посмотреть, сколько из этого вы можете приспособитьв вашей ситуации.(В худшем случае AABB состоит из 12 треугольников, но я ожидаю, что вы можете добиться большего успеха.)

Answer 3

Я придумал алгоритм для решения общего случая произвольного конуса и aabb, но он все еще эффективно обрабатывает ваш конкретный случай.

Я описал это в другой теме: Определить, пересекаются ли куб и конус?

Answer 4

Ссылка на статью Дэвида Эберли от @Gareth Rees хороша, но если вы разбьете все на треугольники, вы в конечном итоге будете проверять лишние вершины и ребра.Я думаю, что это будет хорошо работать:

1. (Необязательно) Проверьте, находится ли AABB полностью на противоположной стороне плоскости, перпендикулярной оси конуса.Если это так, пересечения нет.

2. Проверьте каждую из 8 вершин, чтобы увидеть, находится ли она внутри конуса.Если любая вершина есть, конус и AABB пересекаются.Это довольно просто, но это объяснено на странице 4 ссылки.

3. Проверьте каждый из 12 ребер, чтобы увидеть, пересекаются ли они с конусом.Если есть какое-либо ребро, конус и AABB пересекаются.Это на страницах 4-5 ссылки.

4. Проверьте каждую из 6 граней, чтобы увидеть, не пересекаются ли они с конусом.Если есть какое-либо ребро, конус и AABB пересекаются.Этого достаточно для проверки луча, образованного осью конуса, против AABB;это довольно стандартный тест пересечения.

На самом деле может быть лучше поменять местами порядок проверки граней и граней;Я ожидаю, что проверки лица будут быстрее, чем проверки ребер, так что вы можете выйти раньше.

Вероятно, есть несколько хороших возможностей для оптимизации SIMD, так как количество вершин и ребер кратно4, и конус выровнен по оси, но это выходит за рамки этого ответа:)