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

Question

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

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

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

Может кто-нибудь подумать об более эффективном? Это, кажется, делает много дополнительной работы, вычисляя каждое пересечение линии.

EDIT:

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

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

EDIT EDIT: см. Мой собственный ответ ниже для решения, которое я позже обнаружил, что кажется почти оптимальным для меня.

Answer 1

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

фона: Уравнение для единичного правого отверстия конуса вдоль оси -z + является й^2 + у^2 - г^2 = 0

Найти максимум и минимум x^2 + y^2 - z^2 над AABB. Подсказка: при x^2 минимум - это зажим (0, xmin, xmax)^2, а максимум max (xmin^2, xmax^2).

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

Answer 2

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

Вы можете начать с статьи Дэвида Эберли «Intersection of a Triangle and a Cone» и посмотреть, сколько вы можете приспособиться к своей ситуации. (В худшем случае AABB состоит из 12 треугольников, но я ожидаю, что вы сможете сделать лучше.)

Answer 3

link to the David Eberly article от @Gareth Рис хороший, но если вы разделите все на треугольники, вы В конце концов проверяем избыточные вершины и ребра.Я думаю, что это будет хорошо работать:

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

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

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

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

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

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

Answer 4

я нашел лучшее решение с помощью piman на #gamedev:

Проведите проверку прямоугольного круга между верхней и нижней гранями AABB вдоль оси конуса с кругом, который конус делает на своей плоскости.

Если оба прямоугольника находятся снаружи, AABB находится вне конуса.

Answer 5

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

я описал его в другом потоке: Detect if a cube and a cone intersect each other?