Моделирование столкновений зданий: Введение в компьютерную графику
Системы обнаружения столкновений встречаются во всевозможных видеоиграх и симуляциях. Но как же на самом деле создавать такие системы? Оказывается, ключевые идеи, лежащие в их основе, встречаются во многих областях компьютерной науки, называемых компьютерной графикой. Мы начинаем с основ анимации, а затем переходим к идеям дискретного и непрерывного обнаружения столкновений. Мы разбираем их в контексте простых симуляций небольшого числа частиц, но масштабирование этих симуляций — это совершенно другая задача. Мы представляем масштабные идеи в широких схемах оптимизации фаз для ускорения обнаружения столкновений, включая алгоритм обхода и обрезки, равномерные сетки, K-D деревья и иерархии ограничивающих объемов. Исправление: 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 следует обновлять одновременно. Это видео было бы невозможно без библиотеки с открытым исходным кодом manim, созданной 3blue1brown:https://github.com/3b1b/manim Вот ссылка на репозиторий, содержащий код, использованный для создания анимации в этом видео:https://github.com/nipunramk/Reducible Алгоритм обхода иерархии ограничивающих объемов для широкой фазы:https://thegeneralsolution.wordpress.com/2011/12/13/broad-phase-collision-detection-bounding-volume-hierarchies-1/ Идеи и оформление этого видео были вдохновлены множеством различных источников — вот некоторые из них, которые показались мне особенно интересными для дальнейшего изучения:https://www.toptal.com/developers/game/video-game-physics-part-ii-collision-detection-for-solid-objects Разработка игрового физического движка Иэном Миллингтоном:https://github.com/mattleibow/jitterphysics Оригинал видео:https://www.youtube.com/watch?v=eED4bSkYCB8&t=2s Автор:Reducible
Системы обнаружения столкновений встречаются во всевозможных видеоиграх и симуляциях. Но как же на самом деле создавать такие системы? Оказывается, ключевые идеи, лежащие в их основе, встречаются во многих областях компьютерной науки, называемых компьютерной графикой. Мы начинаем с основ анимации, а затем переходим к идеям дискретного и непрерывного обнаружения столкновений. Мы разбираем их в контексте простых симуляций небольшого числа частиц, но масштабирование этих симуляций — это совершенно другая задача. Мы представляем масштабные идеи в широких схемах оптимизации фаз для ускорения обнаружения столкновений, включая алгоритм обхода и обрезки, равномерные сетки, K-D деревья и иерархии ограничивающих объемов. Исправление: 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 следует обновлять одновременно. Это видео было бы невозможно без библиотеки с открытым исходным кодом manim, созданной 3blue1brown:https://github.com/3b1b/manim Вот ссылка на репозиторий, содержащий код, использованный для создания анимации в этом видео:https://github.com/nipunramk/Reducible Алгоритм обхода иерархии ограничивающих объемов для широкой фазы:https://thegeneralsolution.wordpress.com/2011/12/13/broad-phase-collision-detection-bounding-volume-hierarchies-1/ Идеи и оформление этого видео были вдохновлены множеством различных источников — вот некоторые из них, которые показались мне особенно интересными для дальнейшего изучения:https://www.toptal.com/developers/game/video-game-physics-part-ii-collision-detection-for-solid-objects Разработка игрового физического движка Иэном Миллингтоном:https://github.com/mattleibow/jitterphysics Оригинал видео:https://www.youtube.com/watch?v=eED4bSkYCB8&t=2s Автор:Reducible