Дано:
1) Сложное тело (меш ландшафта), состоящее из треугольных полигонов
2) Простое тело (к примеру цилиндр). Для него известна точка центра и все его измерения.
Нужен алгоритм определения наличия пересечения этих двух тел. При этом, сложное тело много больше простого (по размерам и количеству вершин).
Основная задача - как можно быстрее ответить, есть ли пересечение между этими телами. Допускается предобработка сложного тела.
Какие вообще есть подходы для решения подобной задачи?
Так же скажу сразу, что нужен именно алгоритм, а не какой-то физический движок, который все это сам определит.
Ответ
Разбить поиск на этапы. Первый это грубое отсечение, по крайним координатам тел. Если коллизия не найдена, значит тела не пересекаются. Если найдена, тогда преступаем к детальному отсечению по полигонам попавшим в эту область.
Можете почитать более детально про алгоритмы Sweep And Prune и V-Clip
Комментариев нет:
Отправить комментарий