Алгоритм определения коллизии цилиндра и сложного тела

#алгоритм #3d

Дано:

1) Сложное тело (меш ландшафта), состоящее из треугольных полигонов

2) Простое тело (к примеру цилиндр). Для него известна точка центра и все его измерения.

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

Основная задача - как можно быстрее ответить, есть ли пересечение между этими телами.
Допускается предобработка сложного тела.

Какие вообще есть подходы для решения подобной задачи?



Так же скажу сразу, что нужен именно алгоритм, а не какой-то физический движок, который
все это сам определит.
    

Ответы

Ответ 1

Разбить поиск на этапы. Первый это грубое отсечение, по крайним координатам тел.
Если коллизия не найдена, значит тела не пересекаются. Если найдена, тогда преступаем
к детальному отсечению по полигонам попавшим в эту область. 

Можете почитать более детально про алгоритмы Sweep And Prune и V-Clip


Ответ 2

Если хотите быстро - надо математически: 

По сути, необходимо проверить на пересечение каждого примитива из которого состоит
сложное тело с цилиндром.

Допустим известно уравнение поверхности какой-то части сложного тела, тогда наличие
решения системы из двух уравнений, в котором первое - уравнение этой поверхности, а
второе - параметрическое(либо ещё какое-то) уравнение цилиндра, даст ответ пересекаются
ли они (тоесть имеют ли общие точки).

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