Моделирование столкновений зданий: введение в компьютерную графику

Системы обнаружения столкновений используются во всевозможных видеоиграх и симуляторах. Но как на самом деле создаются эти системы? Оказывается, ключевые идеи, лежащие в основе этих систем, встречаются во всей области компьютерной науки, называемой компьютерной графикой. Мы начинаем с основ анимации, а затем переходим к идеям дискретного и непрерывного обнаружения столкновений. Мы разбираем их на примере простых симуляций небольшого числа частиц, но масштабирование этих симуляций — отдельная сложная задача. Мы представляем важные идеи в рамках схем оптимизации фазы для ускорения обнаружения столкновений, включая алгоритм прогонки и обрезки, равномерные сетки, деревья Короля-Диана и иерархии ограничивающих объёмов. 0:00 Введение 1:25 Введение в анимацию 2:46 Дискретное обнаружение столкновений и реакция на них 5:50 Реализация 6:50 Ограничения дискретного обнаружения столкновений 8:10 Непрерывное обнаружение столкновений 11:42 Моделирование двух частиц 13:13 Масштабирование моделирования 15:42 Алгоритм «развертка и обрезка» 19:05 Разбиение пространства на равномерную сетку 20:43 Деревья KD 23:51 Иерархии ограничивающих объёмов 27:12 Повторение Исправление: На отметке 9:02 уравнения линейной интерполяции должны быть следующими: x(t) = t * x(1) + (1 - t) * x(0) и y(t) = t * y(1) + (1 - t) * y(0). Во всех последующих выводах x(0) заменяется на x(1). Все y(0) также следует заменить на y(1) по той же причине. После исправления 2: Я провёл эксперимент, используя наивное решение проверки каждой пары частиц с дополнительной неэффективностью рендеринга анимации, поэтому сравнение было некорректным, и поэтому число было таким большим. Фактическое ускорение всё ещё довольно значительно, но не НАСТОЛЬКО. Небольшое исправление: p.vel обновляется и используется в следующей строке на 6:28, p.vel и p.pos должны обновляться одновременно. Это видео поддерживается сообществом Patreon. Особая благодарность следующим участникам Patreon: Бёрту Хамбургу Джастину Хайстеру Майклу Навенштейну Ричарду Уэллсу Заку Лэндису Поддержка:   / reducible   Твиттер:   / reducible20   Это видео было бы невозможно без библиотеки с открытым исходным кодом manim, созданной 3blue1brown: https://github.com/3b1b/manim Вот ссылка на репозиторий с кодом, использованным для создания анимаций в этом видео: https://github.com/nipunramk/Reducible Обзор вывода уравнения вектора реакции на столкновение в 2D: https://www.vobarian.com/collisions/2... Алгоритм обхода иерархии ограничивающего объёма для широкой фазы: https://thegeneralsolution.wordpress.... Идеи и презентация в этом видео были вдохновлены множеством ресурсов — вот некоторые из них, которые я счёл особенно полезными для дальнейшего изучения: https://www.toptal.com/game/video-gam... Разработка игрового физического движка Яном Миллингтоном, глава 12 https://github.com/mattleibow/jitterp... http://www.mcihanozer.com/tips/comput...