-
Notifications
You must be signed in to change notification settings - Fork 1
Home
Статья
Таблица
Презентация
Текст выступления
Английский:
Презентация
Текст выступления
В настоящее время моделирование движения различных тел в соответствии с физическими законами приобретает всю большую значимость. Оно применяется не только в разработке разнообразных тренажёров, аппаратуры, механизмов, но и при создании компьютерных игр, построенных в большинстве своём на взаимодействии тел.
Таким образом, в физических симуляциях различных систем объектов зачастую требуется решать задачу обнаружения столкновения двух (или более) тел. Это необходимо для того, чтобы исключить возможность "проваливания" одного объекта в другой, а также для получения информации для дальнейшей симуляции их поведения при ударе. В подобных задачах также нередко делается упор на то, чтобы обеспечить визуализацию динамической сцены в реальном времени. В таком случае, для обеспечения комфортной для восприятия частоты кадров возникает необходимость обновления сцены за малое время.
Как правило, сцены содержат в себе достаточно большое количество объектов, поэтому актуальной проблемой для такого рода симуляций является выбор наиболее быстродейственного алгоритма поиска коллизий. В таких случаях алгоритм полного перебора является неприменимым из-за сложности О(n^2). Существенное снижение вычислительных затрат может быть достигнуто за счёт исключения из проверки столкновения некоторых объектов, которые очевидно не имеют коллизии с рассматриваемым. Такой эффект достигается в силу использования алгоритмов разбиения пространства, которые, в основном, используют структуры дерева для создания иерархии разбиения областей на подобласти.
Однако, на данный момент существует большое количество алгоритмов построенных на пространственных деревьях. Они используют различные принципы разбиения пространства, а также имеют ряд настраиваемых параметров, которые влияют на их быстродействие.
Возникает очевидная потребность в изучении подобных алгоритмов, сравнении их при различных параметрах и количествах объектов на сцене для создания наиболее быстродейственного (может, универсального?) метода для всех возможных условий. Это требование и стало целью данного проекта.
Получается, что наша цель - создать алгоритм, который бы сочетал в себе несколько. Внимание, вопрос, а сможем ли мы это сделать на основании того, что мы уже получили?