Пользователь
0,1
рейтинг
25 февраля 2014 в 12:26

Разработка → Box2d: анатомия коллизий перевод tutorial

Что такое коллизии?

В Box2D принято считать, что друг с другом сталкиваются тела, однако на самом деле при расчете коллизий используются фикстуры (fixtures, переводы слова существуют, но я не уверен, есть ли среди них устоявшийся). Объекты могут сталкиваться разными способами, поэтому библиотека предоставляет большое количество уточняющей информации, которая может быть использована в игровой логике. Например, вы можете захотеть узнать следующее:

  • Когда столкновение начинается и заканчивается
  • Точку соприкосновения фикстур
  • Вектор нормали к линии контакта фикстур
  • Какая энергия была приложена и результат коллизии

Обычно столкновение происходит очень быстро, однако в этой статье мы попытаемся взять одну конкретную коллизию и замедлить ее, чтобы успеть рассмотреть детали происходящего и информацию, которую можно извлечь из события.

В нашем сценарии будут сталкиваться две полигональные фикстуры в мире с нулевой гравитацией (чтобы лучше контролировать процесс). Первая фикстура — стационарный квадрат, вторая — движущийся горизонтально по направлению к квадрату треугольник.



Все настроено таким образом, чтобы нижняя часть треугольника столкнулась с верхним углом квадрата. Тонкости реализации этого процесса выходят за рамки статьи — основное внимание уделим тому, какую информацию можно извлечь на каждом этапе столкновения. Если есть желание самостоятельно запустить предлагаемый пример, исходный код прилагается.

Получении информации о столкновении

Информация о столкновении содержится в объекте типа b2Contact. Из него можно узнать, какие именно фикстуры сталкиваются, и определить их положение и направление результирующих импульсов. Существует два способа получения объектов b2Contact в Box2D. Первый — перебрать текущий список контактов каждого тела объекта, второй — использовать слушатель контактов. Рассмотрим каждый из них, чтобы дальше было понятнее, о чем идет речь.

Проверка списка контактов

В любой момент можно перебрать все контакты мира (имеется в виду b2World)

  for (b2Contact* contact = world->GetContactList(); contact; contact = contact->GetNext())
      contact->... //do something with the contact

или получить контакты тела определенного объекта

for (b2ContactEdge* edge = body->GetContactList(); edge; edge = edge->next)
      edge->contact->... //do something with the contact

Если выбран этот подход, очень важно помнить, что наличие контакта в этих списках не означает, что фикстуры соприкасаются — это значит только, что пересекаются их AABB. Если требуется убедиться, что контактируют сами фикстуры, воспользуйтесь методом IsTouching(). К этому вопросу мы еще вернемся.

Слушатели контактов

Проверка списка контактов становится неэффективной в ситуациях, когда столкновения происходят часто и в больших количествах. Устанавливая слушателей контактов, вы отдаете поручение Box2D сообщать, когда происходит что-то интересное, вместо того, чтобы вручную следить за началом и завершением столкновений. Слушатель контактов — это объект класса b2ContactListener, часть функций которого замещается при необходимости.

  void BeginContact(b2Contact* contact);
  void EndContact(b2Contact* contact);
  void PreSolve(b2Contact* contact, const b2Manifold* oldManifold);
  void PostSolve(b2Contact* contact, const b2ContactImpulse* impulse);

Должен заметить, что в зависимости от ситуации, некоторые события дают нам не только объект b2Contact. В процессе выполнения функции Step, когда Box2D определяет, что произошел контакт, он выполняет обратный вызов определенных функций слушателя, чтобы уведомить вас. Практическое использование "обратных вызовов при коллизиях" рассматривается в отдельной статье. Здесь мы все внимание сосредоточим на том, что можно узнать, обрабатывая события столкновений.

В общем случае я рекомендую метод слушателей контактов. На первый взгляд он может показаться несколько неуклюжим, однако он более эффективен и полезен в долгосрочной перспективе. До сих пор мне не встречалась ситуация, когда проверка списка контактов давала бы ощутимый выигрыш.

Вне зависимости от способа получения контактов, они содержат одинаковую информацию. Наиболее важные данные о пересекающихся фикстурах можно получить так

b2Fixture* a = contact->GetFixtureA();
  b2Fixture* b = contact->GetFixtureB();

Когда происходит обход списка контактов определенного объекта, возможно, одна из фикстур коллизии известна, но если используется слушатель контактов, придется полностью положиться на эти функции, чтобы понять, что с чем сталкивается. Четко заданного порядка фикстур не существует, так что часто приходится устанавливать пользовательские данные (user data), чтобы понять, какому именно объекту принадлежит фикстура или тело. Располагая объектом фикстуры, можно воспользоваться методом GetBody(), чтобы получить ссылку на тело.

Столкновение шаг за шагом.

Теперь давайте подробнее рассмотрим последовательность событий, происходящих при столкновении. Надеюсь, картинок с описанием каждого шага будет достаточно для понимания материала. Возможно, вы захотите загрузить исходники к уроку, чтобы запускать их во время чтения. Тестовая программа позволяет ставить симуляцию на паузу, перезапускать и выполнять ее по шагам.

Начнем с ситуации, когда AABB фикстур не пересекаются, так мы сможет проследить историю полностью. Кликните флажок «AABBs», чтобы увидеть фиолетовые прямоугольные области вокруг каждой фикстуры.



AABB фикстур начинают перекрываться

Несмотря на то, что сами фикстуры еще не пересеклись, на этом этапе уже создается экземпляр b2Contact и добавляется в список контактов мира и списки каждого тела. Если вы просматриваете эти списки, то по наличию объектов b2Contact можно судить о том, что в принципе контакт возможен, хотя фикстуры не обязательно пересеклись.

Результат: контакт существует, но IsTouching() возвращает ложь

Продолжаем симуляцию, пока не пересекутся непосредственно фикстуры…

Фикстуры начинают пересекаться.



Приблизив верхний угол квадрата, можно увидеть переход, как на следующих изображениях

Шаг n


Шаг n+1 (не bullet-объекты)


Все это происходит за один шаг симуляции, значит, реальную точку пересечения (к которой ведет пунктирная линия на рисунке выше), мы проскочили. Это происходит потому, что Box2D сначала смещает все тела и только потом проверяет пересечения, по крайней мере, это его поведение по умолчанию. Если вам нужна реальная точка соприкосновения, то нужно сделать следующее

bodyDef.bullet = true; //before creating body, or      
  body->SetBullet(true); //after creating body

Шаг n+1 (треугольник — bullet-объект)


Bullet-тела, расходуют больше процессорного времени на расчеты и для большинства приложений не требуются. Просто помните о том, что при обычных настройках, иногда коллизии могут пропускаться — в нашем примере, если бы треугольник двигался достаточно быстро, он мог бы пролететь сквозь угол квадрата, не инициировав столкновения. Если у вас есть очень быстро перемещающиеся тела, контакты которых не должны пропускаться, например, мммм… пули :) тогда их нужно объявлять как bullet-объекты. Дальнейшее изложение будет вестись для не-bullet-тел.

Результат:
  • IsTouching() возвращает истину
  • Срабатывает функция обратного вызова BeginContact

Точки столкновения и нормаль

К этому моменту в нашем контакте присутствует реальное соприкосновение, что дает возможность ответить не некоторые вопросы в начале статьи. Для начала давайте получим нормаль и точку касания. Предполагается, что приведенный далее код вызывается или из метода BeginContact слушателя контактов или из вашего метода после предварительного получения контакта из списка.

Объект контакта содержит информацию о коллизии в локальных координатах тел сталкивающихся объектов, а это не совсем то, что нам нужно. Однако можно запросить у контакта более полезную структуру b2WorldManifold, которая содержит позицию коллизии в мировых координатах.

  int numPoints = contact->GetManifold()->pointCount;
  
  //...world manifold is helpful for getting locations
  b2WorldManifold worldManifold;
  contact->GetWorldManifold( &worldManifold );
  
  //draw collision points
  glBegin(GL_POINTS);
  for (int i = 0; i < numPoints; i++)
      glVertex2f(worldManifold.points[i].x, worldManifold.points[i].y);
  glEnd();



Полученные точки будут использованы Box2D для расчета реакции на столкновение для вычисления импульса, который направит фикстуры в противоположные стороны. Это будут неточные места соприкосновения фикстур (если только вы не использовали bullet-объекты), хотя на практике их обычно достаточно для расчетов столкновений в игровой логике.

Далее рассмотрим нормаль коллизии, которая направлена от фикстуры A к B:

 float normalLength = 0.1f;
  b2Vec2 normalStart = worldManifold.points[0] - normalLength * worldManifold.normal;
  b2Vec2 normalEnd = worldManifold.points[0] + normalLength * worldManifold.normal;
  
  glBegin(GL_LINES);
  glColor3f(1,0,0);//red
  glVertex2f( normalStart.x, normalStart.y );
  glColor3f(0,1,0);//green
  glVertex2f( normalEnd.x, normalEnd.y );
  glEnd();

Похоже на то, что для этого столкновения самый быстрый способ избавиться от перекрывающихся объектов, это оттолкнуть угол треугольника вверх и влево, а квадрата — вниз и вправо. Хотелось бы обратить ваше внимание на то, что нормаль — это просто направление, она не привязана ни к какой точке контакта — я изобразил ее проходящей через points[0] для удобства.



Важно также помнить, что нормаль столкновения не определяет угол между фикстурами (ведь треугольник двигается вообще горизонтально) — она лишь задает направление, следуя которому быстрее всего компенсируется перекрытие объектов. Например, представьте, что треугольник двигается немного быстрее, и перекрытие выглядит так:



Тогда самый быстрый способ разделить фикстуры — оттолкнуть треугольник вверх и вправо. Так что использовать нормаль для расчета угла между объектами нецелесообразно. Если требуется узнать направления, по которым будут разделяться фигуры, можно воспользоваться следующим кодом:

b2Vec2 vel1 = triangleBody->GetLinearVelocityFromWorldPoint( worldManifold.points[0] );
b2Vec2 vel2 = squareBody->GetLinearVelocityFromWorldPoint( worldManifold.points[0] );
b2Vec2 impactVelocity = vel1 - vel2;

Он позволит получить относительную скорость реакции всех точек столкнувшихся тел. В нашем простом случае можно было бы ограничиться линейной скоростью треугольника, так как известно, что квадрат неподвижен, а треугольник не вращается. Но вышеуказанный код будет учитывать и случаи, когда оба дела движутся или вращаются.

Также нужно заметить, что не при каждом столкновении будет именно две точки коллизии. Я намерено остановился на достаточно сложном примере, когда перекрываются два угла многоугольников, но чаще бывает только одна такая точка. Вот несколько примеров столкновений, для которых достаточно одной точки







Итак, только что мы рассмотрели, как определить точки и нормаль коллизии, на основе которых Box2D будет рассчитывать реакцию, направленную на компенсацию перекрытий. Теперь вернемся к последовательности событий.

Реакция на столкновение
( (b2Contact::Update, b2Island::Report))
Шаг_столкновения


Шаг_столкновения + 1


Шаг_столкновения + 1


Когда фикстуры перекрываются, реакция Box2d по умолчанию — приложить импульс к каждой из них, чтобы направить в разные стороны. Однако это не всегда удается сделать за один шаг моделирования. Как показано на рисунках для нашего примера, две фикстуры будут перекрываться на протяжении трех шагов, пока отскок не состоится, и они окончательно не разделятся.

В это время мы можем вмешаться и настроить поведение модели, как нам захочется. Если используется подход со слушателем контактов, методы PreSolve и PostSolve будут вызываться на каждом шаге, пока фикстуры перекрываются, давая возможность модифицировать контакт перед тем, как он будет обработан стандартными средствами реакции на коллизию (PreSolve), и узнать, какие импульсы были приложены Box2D (PostSolve)

Для большей наглядности приведу вывод printf, которая помещена в в функцию Step и каждый метод слушателя контактов:
        ...
        Step
        Step
        BeginContact
        PreSolve
        PostSolve
        Step
        PreSolve
        PostSolve
        Step
        PreSolve
        PostSolve
        Step
        EndContact
        Step
        Step
        ...

Результат: PreSolve and PostSolve вызываются несколько раз

PreSolve and PostSolve

Оба эти метода получают в качестве параметра указатель на b2Contact, так что мы имеем доступ к той же информации о точках и нормалях, что и в BeginContact. PreSolve дает на возможность изменить характеристики контакта перед расчетом реакции на столкновение и даже отменить реакцию полностью. PostSolve позволяет получить информацию о вычисленной реакции.

В PreSolve можно сделать следующие настройки объекта контакта:
  void SetEnabled(bool flag);//non-persistent - need to set every time step
  
  //these available from v2.2.1
  void SetFriction(float32 friction);//persists for duration of contact
  void SetRestitution(float32 restitution);//persists for duration of contact

Вызов SetEnabled(false) деактивирует контакт, значит, реакция на столкновение просчитываться не будет. Это может понадобиться, когда необходимо временно позволить объектам пролетать друг сквозь друга. Классический пример — односторонняя стена или платформа, когда игрок может пройти сквозь обычно непроходимый объект при определенных условиях, которые можно проверить только во время выполнения — например, позиция игрока или направление его движения.

Важно помнить, что на следующей итерации контакт снова активируется, так что если нужно отключить его на продолжительное время, придется делать это на каждом шаге.

Кроме ссылки на контакт, PreSolve содержит второй параметр, из которого можно получить характеристики коллизии (точки и нормаль) с предыдущего шага моделирования. Если кто-то знает, зачем это может пригодиться — расскажите мне :D

PostSolve вызывается после того, как реакция на столкновение была рассчитана и применена. У метода есть второй параметр, содержащий информацию о приложенном в результате импульсе. Обычно он используется для проверки, не превысила ли реакция некоторое пороговое значения, в результате чего объект можно разрушить и т.п. В статье " sticky projectiles" содержится пример использования функции PostSolve для определения, должна ли стрела застревать в мишени.

Возвращаемся к сценарию столкновения

Фикстуры больше не перекрываются
(b2Contact::Update)
AABB все еще перекрываются, так что контакт пока остается в соответствующих списках мира и тела.



(увеличенный масштаб)


Результат:
  • Вызывается EndContact
  • IsTouching() возвращает ложь

Так продолжается до тех пор, пока AABB не перестанут перекрываться

AABB фикстур не перекрываются
(b2ContactManager::Collide)


Результат: контакт удаляется из списка контактов мира и тела.

Метод EndContact получает указатель на b2Contact, когда фикстуры уже не соприкасаются, так что в нем уже не содержится актуальной информации. Тем не менее EndContact является неотъемлемым элементом слушателя контактов, так как позволяет контролировать, когда игровые объекты покидают зону соприкосновения.

Итог

Надеюсь, что в статье дан понятный обзор того, что происходит милисекунда за милисекундой в недрах механизма расчета столкновений Box2D. Возможно, это было не самое интересное чтение, однако после изучения разных вопросов на форумах меня не покидало чувство, что некоторые детали часто упускаются, в результате большое количество времени тратится на то, чтобы разобраться, что вообще происходит… Также я заметил тенденцию, когда реализовывать слушатель контактов не решаются, в то время как это требует гораздо меньших усилий по сравнению с последующими задачами. Знание описанных деталей должно дать лучшее понимание вещей, который можно реализовать, улучшить дизайн и сэкономить время.
Перевод: iforce2d
Андросов Вадим @vadim_ig
карма
53,0
рейтинг 0,1
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (18)

  • +1
    А не расскажите почему в качестве AABB выбирается куб или квадрат, но не окружность описывающую фигуру?
    • +2
      Возможно потому, что квадрат можно быстрее и проще просчитать.
    • +2
      Наверное, потому, что с прямоугольником быстрее производить вычисления — с окружностью же нужно учитывать радиусы, которые, в свою очередь, ведут к использованию квадратической функции. Не исключаю, что иногда окружность удобнее — например, если объект вращается.
      // предыдущий коммент меня опередил.
      • +2
        Я может не прав, но что бы посчитать пересекаются ли две окружности, нам нужно сложить два радиуса и сравнить с расстоянием между центрами.
        • +1
          Конечно. Но если, например, размер объекта динамичный — операция вычисления радиуса становится затратной.
        • +3
          Да, но чтобы вычислить расстояние между центрами нужны операции возведения в квадрат и извлечение корня, а они затратные.
          Поэтому пересекать кубы быстрее.
        • +1
          Расстояние между центрами — число с плавающей точкой. Его вычисление вероятно дороже, чем сравнение нескольких пар целых чисел.
          К тому же, если в box2d всё считается в целых числах, то и работать проще с целыми.
        • +1
          для вычисления расстояния придется числа в квадраты возводить или по модулю брать, а с прямоугольными областями (стороны которых параллельны осям координат) достаточно операций сравнения
        • +2
          Вам дали кучу ответов, но пропустили самый важный — соотношение площади описанного прямоугольника к площади фигуры почти всегда заметно меньше, чем соотношение площади описанной окружнасти к площади фигуры. Т.е. имея длинную «палку», т.е. прямоугольник с длиной намного большей его ширины, описывать его окружностью очень неудобно, в реальных случаях проверки коллизии будут выполняться слишком часто. Для сравнения представьте, что вокруг фигур тетриса описаны окружности — сколько можно таких фигур поместить в игровой «колодец», чтобы описанные окружности не пересекались? Теперь представьте, что вокруг фигур описаны AABB прямоугольники и снова ответьте на этот вопрос.

          Что интересно, в «больших» 3D физических движках иногда есть смысл использовать и баундинг сферы, и баундинг боксы, но это уже отдельный разговор.
          • 0
            Вот именно, что площади разные и иногда, действительно, оптимальнее использовать сферу. И вы абсолютно правы, что это самый важный фактор! Правда все это всплывает чаще всего, когда сам пытаешься реализовать проверку коллизий без всяких библиотек.
    • 0
      Наверно потому что параллелепипеды удобнее и быстрее считаются. У окружности на границе погрешность, поэтому супер точно определить соприкосновения не получится.
    • +3
      AABB (axis-aligned bounding box) — по определению прямоугольник или параллелепипед, а то, о чём вы хотели спросить, — виды ограничивающих объёмов.
      Помимо вышеупомянутой простоты арифметики при расчётах, ориентированные по осям коробки проще строить, чем описанные вокруг многоугольников и многогранников окружности и сферы.
    • +2
      На самом деле, что проще посчитать — пересечение ААВВ, или сфер-окружностей, вопрос спорный. Считается, что окружность — самая простая геометрия для расчёта пересечений. ААВВ чуть по-сложнее. При этом у окружности есть еще одно преимущество — её не надо пересчитывать при вращении — перемещении объекта, а ААВВ — надо. Зато ААВВ проще пересчитывать в случае деформации объектов.

      И есть еще одно преимущество — обычно ААВВ имеет меньший объём по сравнению с габаритной сферой, а значит точнее аппроксимирует целевой объект и реже происходят ситуации, когда коллизия между контейнерами произошла, а между реальной геометрией — нет, что гораздо важнее, чем сомнительное преимущество в скорости расчета коллизии между самими габаритными контейнерами.
      • +1
        Сферы гораздо проще и дешевле в использовании, чем баундингбоксы. Открою страшный секрет, что квадрат не обязательно извлекать для определения пересечения двух сфер.
        • 0
          Не совсем так. Баундингбоксы бывают разные. Есть ориентированные баундингбоксы (OBB), которые поворачиваются вместе с объектом, они действительно на порядок дороже, чем окружности. Но в статье говорится о AABB — это баундингбоксы, которые ориентированы по главным осям мировых координат. Посчитать их пересечение значительно проще, достаточно вычесть центры прямоугольников и сравнить компоненты полученного вектора с суммой полуразмеров прямоугольников. То есть, 4 операции сложения-вычитания и две операции сравнения. Для двух окружностей требуется 4 операции сложения-вычитания, две операции умножения и одно сравнение. То есть, сложности сопоставимы, но на современных процессорах с глубокими конвейерами операции сравнения могут оказаться дороже, чем операции умножения. К тому же, AABB нужно пересчитывать при каждом вращении объекта.

          P.S.: в своём физическом движке мы использовали именно сферы для объектов и бинарные деревья OBB для полигональных сеток. А вот для облака точек лучше подходит окто-дерево AABB. Так что, всему своё место.
          • 0
            Операции сравнения несравненно дороже, кроме того Вы пропустили +2 операции сравнения для прямоугольников. После вычитания центров надо определить их знак. Впрочем, это все копейки.
            Я (в некоторых приложениях) пересечения объектов определяю условно бесплатно — рисуя любой Image, заношу цветные пикселы в цветной растр, а индексные пикселы — в индексный растр. Каждый объект имеет свой индекс. Попали в одну точку индексного растра разные индексы? Да — значит объекты с этими индексами визуально прикоснулись.
  • +3
    В процессе выполнения функции Step, когда Box2D определяет, что произошел контакт, он выполняет обратный вызов определенных функций слушателя, чтобы уведомить вас.

    Мне кажется, лучше не переводить это и оставить «колбек» как кальку, или же просто писать callback. Минусы к этому комменту покажут, насколько это удачная идея.
  • +5
    На мой вкус только gif'ок не хватает для наглядности. А так отличная статья, спасибо!

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.