Введение в дискретно-ориентированные многогранники для задачи определения столкновений
Обнаружение столкновений (collision detection) виртуальных объектов является довольно значимой частью для задач визуализации.
Задача
А задача состоит в том, чтобы определить столкнулись (collide) ли два объекта или нет.
Сложность же состоит в том, что при тестировании примитивов визуализации непосредственно с другими примитивами вычисление коллизий занимает неоправданно большие ресурсы, особенно при огромном количестве объектов участвующих в симуляции.
Чтобы облегчить подобные вычисления и не производить проверку непосредственно между примитивами визуализации (что занимает наибольшее время), были выдуманы технологии ограничивающих объемов (bounding volume), которые позволяют описывать объекты визуализации таким образом, чтобы проверка на столкновения занимала не такие значительные ресурсы хотя и при небольшой потери точности.
Другими словами, ограничивающие объемы — это простые геометрические фигуры, куда вписываются более сложные объекты.
Bounding volumes
Наиболее востребованные ограничивающие объемы:
— Сфера (Sphere).
— Ограничивающий параллелепипед, выровненный по координатным осям (Axis-aligned bounding boxes — AABB, уж простите за перевод).
— Объектно-ориентированный ограничивающий параллелепипед (Object-oriented bounding boxes — OBB)
— Дискретно-ориентированные многогранники. (Discrete oriented polytopes — k-DOPs)
— и другие.
Рис 1. Обзор BV.
Каждый из них имеют ряд достоинств и недостатков, но остановимся на k-DOP.
Рис 2. Доходчиво о BV.
Дискретно-ориентированные многогранники — это заранее известное количество ограничивающих плоскостей и их ориентации. K в названии описывает количество таких плоскостей.
Например, двухмерный 4-DOP является обычным квадратом, описывающим некий также двухмерный объект. По сути AABB — это частный случай k-DOP.
Двухмерный AABB является таким же квадратом, как и 4-DOP.
А трехмерный AABB является таким же кубом, как и 6-DOP.
Но k-DOP так же может использовать большее количество плоскостей. И, как было сказано, ориентация таких плоскостей выбирается заранее и не меняется.
Ориентации плоскостей определяют через вектора направления, компоненты нормалей которых ограничены множеством <-1, 0, 1>.
Например, для обычного квадрата необходимо 4 плоскости с направлениями: (0, 1), (1, 0).
Здесь описаны направления двух плоскостей, но которые ограничивают квадрат снизу, сверху, слева и справа. Хотя всего плоскостей 4, поэтому, бывает, пишут еще так: (0, ±1), (±1, 0)
Данные нормали позволяют серьезно облегчить вычисления.
Структура
k-DOP описывается всего лишь минимальными и максимальными интервалами (slabs) или дистанциями. Два значения на одну плоскость, что в итоге получается довольно просто обрабатывать и хранить.
Рис 3. Интервалы в k-DOP.
Например, для квадрата, как мы запомнили, надо 4 плоскости (k=4). Значит, потребуется 2 (k/2) минимальных и 2 максимальных значений.
Рис 4. 8-DOP описывающий треугольник.
Давайте посчитаем интервалы, описывающие этот многогранник.
Берем первую плоскость с направлением (1, 0) и умножаем на координаты:
3*1 + 1*0 = 3
5*1 + 4*0 = 5
1*1 + 5*0 = 1
Проверка на пересечение
Если по крайней мере одна плоскость не пересекается, то вся структура также не пересекается.
Только если все интервалы/плоскости пересекаются, тогда пересекается сама структура k-DOP. Но следует заметить, что описываемый объект может и не пересекаться.
Поэтому говорится, если k-DOP структуры двух объектов сталкиваются (collide), то их описываемые объекты могут сталкиваться.
Иерархии ограничивающих объемов (Bounding Volume Hierarchy)
Как выяснилось, использование ограничивающих объемов позволяет упростить проверку на столкновения, но теряет немного в точности.
Поэтому для простых объектов, чтобы исключить не нужные проверки, тестируют сначала их ограничивающие объемы, как AABB или k-DOP, а после уже переходят на примитивы.
Но при сложно структурированных объектах применяют иерархии ограничивающих объемов. Часто это просто бинарные деревья, где ноды определяют какой-то объект или часть объекта, ограниченный каким-то объемом.
Рис 5. Дерево объектов.
Использование таких деревьев нужно для снижения количества вычислений.
Очевидно, что если проверку на коллизии производить непосредственно на объектах, это может потребовать слишком много времени. Применение ограничивающих объемов позволяет немного облегчить это задачу. А объединение ограничивающих объемов в иерархическую систему дает возможность исключить заведомо непересекающиеся части объекта.
Обычно создание дерева происходит одним способом из трех.
Сложный объект (рутовая нода) делится на менее сложные (дочерние ноды). Например, пока объекты не закончатся или пока не выполнится какое-то условие. (top down method)
Простые объекты (ноды) объединяются в более сложные пока не останется один сложный рутовый объект (bottom up method).
Или добавление объекта в уже сформированное дерево (insertion method).
При сбалансированном таком дереве сложность поиска равна сложности других сбалансированных бинарных деревьях поиска — O(logN).
Наиболее интересный вопрос каким же способом делить объект на дочерние.
Критерий сравнения частей объекта, чтобы помещать в левое или правое поддерево могут различаться.
Наиболее простым является простое деление пространства пополам: все объекты с координатами выше определенной идут в правое поддерево, все остальные в левое.
Также может быть подсчет среднего значения, например, по выбранной оси.
Или построение медианы. Или любым другим способом.
Рис 6. Другое абстрактное дерево объектов.
Поиск коллизий
Поиск столкновений на двух иерархических структур, в свою очередь, тоже может быть реализован разными способами.
Чтобы проверить на пересечения двух объектов, необходимо просто создать дерево (BVH-tree) на каждый объект, где нода определяет свою часть объекта через какой-то ограничивающий объем.
Далее нужно пройтись по деревьям и сопоставить ноду с одного дерева с нодами другого, таким образом, чтобы двигаться только в том направлении, где есть пересечение их ограничивающих объемов.
Рис 7. Дерево рекурсии сопоставления объектов.
Box2d: анатомия коллизий
Что такое коллизии?
В Box2D принято считать, что друг с другом сталкиваются тела, однако на самом деле при расчете коллизий используются фикстуры (fixtures, переводы слова существуют, но я не уверен, есть ли среди них устоявшийся). Объекты могут сталкиваться разными способами, поэтому библиотека предоставляет большое количество уточняющей информации, которая может быть использована в игровой логике. Например, вы можете захотеть узнать следующее:
Все настроено таким образом, чтобы нижняя часть треугольника столкнулась с верхним углом квадрата. Тонкости реализации этого процесса выходят за рамки статьи — основное внимание уделим тому, какую информацию можно извлечь на каждом этапе столкновения. Если есть желание самостоятельно запустить предлагаемый пример, исходный код прилагается.
Получении информации о столкновении
Информация о столкновении содержится в объекте типа b2Contact. Из него можно узнать, какие именно фикстуры сталкиваются, и определить их положение и направление результирующих импульсов. Существует два способа получения объектов b2Contact в Box2D. Первый — перебрать текущий список контактов каждого тела объекта, второй — использовать слушатель контактов. Рассмотрим каждый из них, чтобы дальше было понятнее, о чем идет речь.
Проверка списка контактов
В любой момент можно перебрать все контакты мира (имеется в виду b2World)
или получить контакты тела определенного объекта
Если выбран этот подход, очень важно помнить, что наличие контакта в этих списках не означает, что фикстуры соприкасаются — это значит только, что пересекаются их AABB. Если требуется убедиться, что контактируют сами фикстуры, воспользуйтесь методом IsTouching(). К этому вопросу мы еще вернемся.
Слушатели контактов
Проверка списка контактов становится неэффективной в ситуациях, когда столкновения происходят часто и в больших количествах. Устанавливая слушателей контактов, вы отдаете поручение Box2D сообщать, когда происходит что-то интересное, вместо того, чтобы вручную следить за началом и завершением столкновений. Слушатель контактов — это объект класса b2ContactListener, часть функций которого замещается при необходимости.
Должен заметить, что в зависимости от ситуации, некоторые события дают нам не только объект b2Contact. В процессе выполнения функции Step, когда Box2D определяет, что произошел контакт, он выполняет обратный вызов определенных функций слушателя, чтобы уведомить вас. Практическое использование «обратных вызовов при коллизиях» рассматривается в отдельной статье. Здесь мы все внимание сосредоточим на том, что можно узнать, обрабатывая события столкновений.
В общем случае я рекомендую метод слушателей контактов. На первый взгляд он может показаться несколько неуклюжим, однако он более эффективен и полезен в долгосрочной перспективе. До сих пор мне не встречалась ситуация, когда проверка списка контактов давала бы ощутимый выигрыш.
Вне зависимости от способа получения контактов, они содержат одинаковую информацию. Наиболее важные данные о пересекающихся фикстурах можно получить так
Когда происходит обход списка контактов определенного объекта, возможно, одна из фикстур коллизии известна, но если используется слушатель контактов, придется полностью положиться на эти функции, чтобы понять, что с чем сталкивается. Четко заданного порядка фикстур не существует, так что часто приходится устанавливать пользовательские данные (user data), чтобы понять, какому именно объекту принадлежит фикстура или тело. Располагая объектом фикстуры, можно воспользоваться методом GetBody(), чтобы получить ссылку на тело.
Столкновение шаг за шагом.
Теперь давайте подробнее рассмотрим последовательность событий, происходящих при столкновении. Надеюсь, картинок с описанием каждого шага будет достаточно для понимания материала. Возможно, вы захотите загрузить исходники к уроку, чтобы запускать их во время чтения. Тестовая программа позволяет ставить симуляцию на паузу, перезапускать и выполнять ее по шагам.
Начнем с ситуации, когда AABB фикстур не пересекаются, так мы сможет проследить историю полностью. Кликните флажок «AABBs», чтобы увидеть фиолетовые прямоугольные области вокруг каждой фикстуры.
AABB фикстур начинают перекрываться
Несмотря на то, что сами фикстуры еще не пересеклись, на этом этапе уже создается экземпляр b2Contact и добавляется в список контактов мира и списки каждого тела. Если вы просматриваете эти списки, то по наличию объектов b2Contact можно судить о том, что в принципе контакт возможен, хотя фикстуры не обязательно пересеклись.
Результат: контакт существует, но IsTouching() возвращает ложь
Продолжаем симуляцию, пока не пересекутся непосредственно фикстуры…
Фикстуры начинают пересекаться.
Приблизив верхний угол квадрата, можно увидеть переход, как на следующих изображениях
Шаг n
Шаг n+1 (не bullet-объекты)
Все это происходит за один шаг симуляции, значит, реальную точку пересечения (к которой ведет пунктирная линия на рисунке выше), мы проскочили. Это происходит потому, что Box2D сначала смещает все тела и только потом проверяет пересечения, по крайней мере, это его поведение по умолчанию. Если вам нужна реальная точка соприкосновения, то нужно сделать следующее
Шаг n+1 (треугольник — bullet-объект)
Bullet-тела, расходуют больше процессорного времени на расчеты и для большинства приложений не требуются. Просто помните о том, что при обычных настройках, иногда коллизии могут пропускаться — в нашем примере, если бы треугольник двигался достаточно быстро, он мог бы пролететь сквозь угол квадрата, не инициировав столкновения. Если у вас есть очень быстро перемещающиеся тела, контакты которых не должны пропускаться, например, мммм… пули 🙂 тогда их нужно объявлять как bullet-объекты. Дальнейшее изложение будет вестись для не-bullet-тел.
Точки столкновения и нормаль
К этому моменту в нашем контакте присутствует реальное соприкосновение, что дает возможность ответить не некоторые вопросы в начале статьи. Для начала давайте получим нормаль и точку касания. Предполагается, что приведенный далее код вызывается или из метода BeginContact слушателя контактов или из вашего метода после предварительного получения контакта из списка.
Объект контакта содержит информацию о коллизии в локальных координатах тел сталкивающихся объектов, а это не совсем то, что нам нужно. Однако можно запросить у контакта более полезную структуру b2WorldManifold, которая содержит позицию коллизии в мировых координатах.
Полученные точки будут использованы Box2D для расчета реакции на столкновение для вычисления импульса, который направит фикстуры в противоположные стороны. Это будут неточные места соприкосновения фикстур (если только вы не использовали bullet-объекты), хотя на практике их обычно достаточно для расчетов столкновений в игровой логике.
Далее рассмотрим нормаль коллизии, которая направлена от фикстуры A к B:
Похоже на то, что для этого столкновения самый быстрый способ избавиться от перекрывающихся объектов, это оттолкнуть угол треугольника вверх и влево, а квадрата — вниз и вправо. Хотелось бы обратить ваше внимание на то, что нормаль — это просто направление, она не привязана ни к какой точке контакта — я изобразил ее проходящей через points[0] для удобства.
Важно также помнить, что нормаль столкновения не определяет угол между фикстурами (ведь треугольник двигается вообще горизонтально) — она лишь задает направление, следуя которому быстрее всего компенсируется перекрытие объектов. Например, представьте, что треугольник двигается немного быстрее, и перекрытие выглядит так:
Тогда самый быстрый способ разделить фикстуры — оттолкнуть треугольник вверх и вправо. Так что использовать нормаль для расчета угла между объектами нецелесообразно. Если требуется узнать направления, по которым будут разделяться фигуры, можно воспользоваться следующим кодом:
Он позволит получить относительную скорость реакции всех точек столкнувшихся тел. В нашем простом случае можно было бы ограничиться линейной скоростью треугольника, так как известно, что квадрат неподвижен, а треугольник не вращается. Но вышеуказанный код будет учитывать и случаи, когда оба дела движутся или вращаются.
Также нужно заметить, что не при каждом столкновении будет именно две точки коллизии. Я намерено остановился на достаточно сложном примере, когда перекрываются два угла многоугольников, но чаще бывает только одна такая точка. Вот несколько примеров столкновений, для которых достаточно одной точки
Итак, только что мы рассмотрели, как определить точки и нормаль коллизии, на основе которых Box2D будет рассчитывать реакцию, направленную на компенсацию перекрытий. Теперь вернемся к последовательности событий.
Реакция на столкновение
( (b2Contact::Update, b2Island::Report))
Шаг_столкновения
Шаг_столкновения + 1
Шаг_столкновения + 1
Когда фикстуры перекрываются, реакция Box2d по умолчанию — приложить импульс к каждой из них, чтобы направить в разные стороны. Однако это не всегда удается сделать за один шаг моделирования. Как показано на рисунках для нашего примера, две фикстуры будут перекрываться на протяжении трех шагов, пока отскок не состоится, и они окончательно не разделятся.
В это время мы можем вмешаться и настроить поведение модели, как нам захочется. Если используется подход со слушателем контактов, методы PreSolve и PostSolve будут вызываться на каждом шаге, пока фикстуры перекрываются, давая возможность модифицировать контакт перед тем, как он будет обработан стандартными средствами реакции на коллизию (PreSolve), и узнать, какие импульсы были приложены Box2D (PostSolve)
Для большей наглядности приведу вывод printf, которая помещена в в функцию Step и каждый метод слушателя контактов:
Результат: PreSolve and PostSolve вызываются несколько раз
PreSolve and PostSolve
Оба эти метода получают в качестве параметра указатель на b2Contact, так что мы имеем доступ к той же информации о точках и нормалях, что и в BeginContact. PreSolve дает на возможность изменить характеристики контакта перед расчетом реакции на столкновение и даже отменить реакцию полностью. PostSolve позволяет получить информацию о вычисленной реакции.
В PreSolve можно сделать следующие настройки объекта контакта:
Вызов SetEnabled(false) деактивирует контакт, значит, реакция на столкновение просчитываться не будет. Это может понадобиться, когда необходимо временно позволить объектам пролетать друг сквозь друга. Классический пример — односторонняя стена или платформа, когда игрок может пройти сквозь обычно непроходимый объект при определенных условиях, которые можно проверить только во время выполнения — например, позиция игрока или направление его движения.
Важно помнить, что на следующей итерации контакт снова активируется, так что если нужно отключить его на продолжительное время, придется делать это на каждом шаге.
Кроме ссылки на контакт, PreSolve содержит второй параметр, из которого можно получить характеристики коллизии (точки и нормаль) с предыдущего шага моделирования. Если кто-то знает, зачем это может пригодиться — расскажите мне 😀
PostSolve вызывается после того, как реакция на столкновение была рассчитана и применена. У метода есть второй параметр, содержащий информацию о приложенном в результате импульсе. Обычно он используется для проверки, не превысила ли реакция некоторое пороговое значения, в результате чего объект можно разрушить и т.п. В статье » sticky projectiles» содержится пример использования функции PostSolve для определения, должна ли стрела застревать в мишени.
Возвращаемся к сценарию столкновения
Фикстуры больше не перекрываются
(b2Contact::Update)
AABB все еще перекрываются, так что контакт пока остается в соответствующих списках мира и тела.
(увеличенный масштаб)
AABB фикстур не перекрываются
(b2ContactManager::Collide)
Результат: контакт удаляется из списка контактов мира и тела.
Метод EndContact получает указатель на b2Contact, когда фикстуры уже не соприкасаются, так что в нем уже не содержится актуальной информации. Тем не менее EndContact является неотъемлемым элементом слушателя контактов, так как позволяет контролировать, когда игровые объекты покидают зону соприкосновения.
Unity3d. Уроки от Unity 3D Student (B00-B03)
Добрый день. Предлагаю свой вариант перевода уроков по Unity3d от www.unity3dstudent.com
Введение.
Данная статья представляет из себя первый набор базовых (из раздела Beginner) уроков. Уроки в основном нацелены на изучение скриптинга и использование компонентов.
Поэтому предполагается, что с основами работы в GUI Unity вы слегка знакомы. Если нет, изучите вводный раздел на этом же сайте.
Уроки достаточно ясные и короткие, так что трудностей в процессе их изучения должно возникать минимум.
PS: А хорошо это или плохо — вопрос достаточно сложный.
В некоторых местах уроков есть минимальные косметические изменения, не затрагивающие основную суть.
Базовый Урок 00 — Добавления массы / гравитации к твердому телу.
В уроке рассказывается, как добавлять гравитацию / массу к объекту с помощью компонента Rigidbody (твердое тело).
Если вы хотите добавить массу или гравитацию к объекту, нужно воспользоваться компонентом Rigidbody, который расположен в меню компонентов.
Создайте проект или новую сцену в готовом проекте (предварительно подключив Standard Assets packages). Добавьте куб (GameObject->Create Other->Cube), плоскость (GameObject->Create Other->Plane) и точечный источник света (GameObject->Create Other->Point Light). Расположите их как указанно на картинке ниже.
Так же расположите камеру, чтоб она отображала все наши объекты. Если нажать на кнопку Play, то вы увидите статичную сцену, где ничего не происходит.
Теперь добавим компонент Rigidbody (твердое тело). Он расположен в меню Component->Physics. Выберете наш куб и добавьте этот компонент к нему.
Если нажать на Play, вы увидите как куб падает на плоскость под действием силы тяжести. Давайте немного изменим физические свойства нашего куба. Снова выберите куб. В Inspector View вы можете увидеть компонент Box Collider, одним из параметров которого является Material (по умолчанию значение None(Physics Material)). Кликните правой кнопкой мыши на это значение и выскочит окно выбора физического материала. Если вы создавали проект, подключив стандартный набор ресурсов (Standard Assets) вы увидите несколько стандартных физических материалов. Выберете Bouncy (Упругий).
Теперь нажав Play вы увидите, как после падения куб начнет отскакивать от поверхности.
Дополнительные материалы:
Базовый Урок 01 — Основы обнаружения столкновений.
В уроке рассказывается как обнаружить столкновения (collisions) между объектами используя скрипты.
Создайте сцену как в предыдущем уроке или загрузите уже имеющуюся. Добавьте к ней еще один куб, растяните его по горизонтали в 5-6ть раз и по вертикали в 2а раза. Расположите его как показано на рисунке ниже.
В этом уроке важны названия объектов. Назовите плоскость Floor, а куб представляющий стену Wall (Ваш К.О.)
В Project View нажмите на Create и выберете С# Script. Назовите его boxdrop. Дважды кликнув на скрипт вы откроете его в вашем редакторе скриптов (как правило, по умолчанию это MonoDevelop. У автора статьи это Visual Studio 2010 под Windows или Textmate под MacOs).
Обратите внимание, что название класса всегда должно совпадать с названием скрипта(регистр букв тоже имеет значение):
По умолчанию Unity создает каркас для C# скрипта. Удалите из тела класса boxdrop все содержимое и замените следующим:
Функция OnCollisionEnter определяет столкновение объекта с другими объектами. А статический метод Log класса Debug пишет сообщение в консоль Unity. После сохранения скрипта, добавьте его как компонент для падающего куба.
Теперь если вы нажмете Play, в момент когда куб коснется пола консоль выдаст соответствующее сообщение. Открыть окно консоли можно комбинацией ctrl + shift + c в Windows или cmd + shift + c в MacOs. Последнее консольное сообщение отображается в статус баре проекта (внизу окна).
Причем сообщение будет выдаваться при каждом столкновении.
Для того, чтобы понять с каким именно объектом столкнулся наш куб, мы будем брать значение параметра класса Collision, которое будет принимать метод OnCollisionEnter:
Нажмите Play и после того как ваш куб коснется несколько раз стены и пола остановите игру и откройте консоль. Теперь при столкновении только со стеной или полом будет выдаваться соответствующие названию объекта сообщение.
Дополнительные материалы:
Базовый Урок 02 — Основы ввода
В Уроке рассказываются основы ввода с использованием скриптов.
В Unity существует множество способов для ввода текстовых данных. Мы рассмотрим простейший случай, в котором нажатие на клавишу «пробел» вызовет сообщение в консоли Unity. В отличии от предыдущих уроков, в этой сцене присутствует только камера и пустой игровой объект (GameObject->Create Empty).
Добавим C# скрипт и назовем его keyPress. Откройте скрипт. В теле класса keyPress вы увидете пустую функцию Update(). Она вызывается каждый кадр:
Чтоб понять был ли ввод с клавиатуры или нет, требуется проверять это каждый кадр. Добавим в нашу функцию Update следующий код:
Сохраним файл и добавим этот скрипт к пустому объекту (перетащив скрипт на объект или же выделив объект и перетащив скрипт в Inspector View). Давайте выясним, что такое «Jump». Идем в Edit->Project Settings->Input.
В Inspector’e открылся Input Manager. Разверните пункт Axes. Если выбрать Jump, видно что его имя как раз и представляет строка «Jump», а значение переменной Positive Button есть space. Про остальные параметры вы можете прочитать в справочнике Unity (ссылка в конце урока).
Запустите сцену, перейдите в закладку Game View и нажмите пробел, после чего в консоли (и внизу окна проекта) увидите соответствующее сообщение.
Аналогичный результат можно получить если заменить строку
Дополнительные материалы:
В Уроке рассказывается, как создавать префабы, и для чего они нужны.
Префаб (сборная конструкция) — это объект, содержащийся в вашем проекте, его можно клонировать и создавать множество его экземпляров, причем все экземпляры при копировании будут иметь те же компоненты те же компоненты. Создайте или загрузите сцену из Базового Урока 1. У нас на сцене присутствует куб, который падает и выдает сообщение в консоль при столкновении с объектами. Что если мы хотим создать множество таких же кубов (с уже добавленными компонентами)?
Создадим префаб, с помощью Create->Prefab в Project View.
В итоге получим серую иконку с названием New Prefab.
Переименуем ее в «BouncyBox». Теперь нам осталось лишь перетащить все что требуется в наш префаб. То есть Cube.
Цвет иконки поменялся на синий и теперь, если вы выделите наш префаб, в Inspector View вы увидите что он имеет те же параметры, что были и у объекта Cube.
Если вы хотите создавать экземпляры префаба, то вам требуется перетащить его в сцену.
Нажмите Play и увидите, что добавленный куб ведет себя точно так же, как и оригинальный.
Префабы нужны в случае, если вам требуется создать много одинаковых объектов, которые содержат множество компонентов. К примеру, если вы разрабатываете игру и вам нужно добавить много врагов у которых одинаковое поведение, внешний вид и пр.
