Обнаружение столкновений OBB и OBB

20

Допустим, у вас есть два объекта Bounding Box, каждый из которых хранит текущие вершины блока в векторе, причем все вершины объекта повернуты и сдвинуты относительно общей оси.

Вот изображение, чтобы проиллюстрировать мою проблему:

Как я могу работать, если два OBB перекрывают какие-либо ссылки, чтобы помочь объяснить решение проблемы, будет приветствоваться. Ничего слишком запутанного, пожалуйста ...

Джошуа Барнетт
источник

Ответы:

16

OBB является выпуклой оболочкой. Выпуклый корпус - это трехмерная фигура, на поверхности которой нет «щелей». Каждый «удар» (вершина) на выпуклой оболочке выступает наружу , а не внутрь. Если вы разрежете плоскость через выпуклый корпус, вы получите (только один) выпуклый многоугольник. Если вы находитесь внутри выпуклого корпуса и стреляете лазером, направленным наружу, вы будете пробивать поверхность корпуса только один раз (никогда дважды).

Тест теоремы о разделяющей оси может быть использован для обнаружения столкновения выпуклых оболочек. Тест SAT прост. Работает в 2D и 3D. Хотя изображения ниже будут в 2D, они также могут быть легко применены к 3D.

концепция

Это ключевая концепция, которую вы используете с SAT:

  • Две фигуры пересекаются, только если они перекрываются, когда «проецируются» на каждую нормальную ось обеих фигур .

«Проекция» фигуры на одномерный вектор выглядит так (то, что я называю «дробление»)

Форма с красными вершинами и осью

введите описание изображения здесь

«Проецирование фигуры на ось» означает опускание перпендикуляра из каждой точки фигуры, чтобы приземлиться на ось. Вы можете думать об этом как о «раздавливании» точек рукой, которая собирает все и перпендикулярно раздавливает ее до оси.

введите описание изображения здесь

То, что у вас осталось: точки на оси

введите описание изображения здесь

СБ говорит:

Чтобы пересечь 2 выпуклых корпуса, они должны перекрываться на каждой оси (где каждая нормаль любой формы считается осью, которую мы должны проверить).

Возьмите эти 2 формы:

введите описание изображения здесь

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

Пробуем верхнюю нормаль пятиугольника:

введите описание изображения здесь

Это экстенты. Они перекрываются.

введите описание изображения здесь

Попробуйте левую сторону прямоугольника. Теперь они не пересекаются в этой оси, поэтому нет пересечения.

введите описание изображения здесь

Алгоритм:

Для каждого лица нормальны обе фигуры:

  • Найти минимальное и максимальное экстенты (наибольшее и наименьшее значение) проекции всех угловых точек вершин обеих фигур на эту ось
  • Если они не перекрываются, пересечения нет .

И это действительно так. Код для обеспечения работы SAT очень короткий и простой.

Вот некоторый код, который демонстрирует, как сделать проекцию оси SAT:

void SATtest( const Vector3f& axis, const vector<Vector3f>& ptSet, float& minAlong, float& maxAlong )
{
  minAlong=HUGE, maxAlong=-HUGE;
  for( int i = 0 ; i < ptSet.size() ; i++ )
  {
    // just dot it to get the min/max along this axis.
    float dotVal = ptSet[i].dot( axis ) ;
    if( dotVal < minAlong )  minAlong=dotVal;
    if( dotVal > maxAlong )  maxAlong=dotVal;
  }
}

Телефонный код:

// Shape1 and Shape2 must be CONVEX HULLS
bool intersects( Shape shape1, Shape shape2 )
{
  // Get the normals for one of the shapes,
  for( int i = 0 ; i < shape1.normals.size() ; i++ )
  {
    float shape1Min, shape1Max, shape2Min, shape2Max ;
    SATtest( normals[i], shape1.corners, shape1Min, shape1Max ) ;
    SATtest( normals[i], shape2.corners, shape2Min, shape2Max ) ;
    if( !overlaps( shape1Min, shape1Max, shape2Min, shape2Max ) )
    {
      return 0 ; // NO INTERSECTION
    }

    // otherwise, go on with the next test
  }

  // TEST SHAPE2.normals as well

  // if overlap occurred in ALL AXES, then they do intersect
  return 1 ;
}

bool overlaps( float min1, float max1, float min2, float max2 )
{
  return isBetweenOrdered( min2, min1, max1 ) || isBetweenOrdered( min1, min2, max2 ) ;
}

inline bool isBetweenOrdered( float val, float lowerBound, float upperBound ) {
  return lowerBound <= val && val <= upperBound ;
}
bobobobo
источник
Hullinator реализует тест SAT для выпуклых оболочек
бобобо
классное объяснение! Благодарю. Я думаю , что вы , возможно, опечатка в строке: «так что позволяет попробовать несколько осей на шоу были перекрытие не происходит.», Потому что тогда вы продолжаете давать примеры , когда они делают перекрытие. Спасибо еще раз!
Вам не нужно делать тесты также для всех перекрестных произведений нормалей? В этой статье geometrytools.com/Documentation/DynamicCollisionDetection.pdf говорится об этом.
ИНФИНИТЕЙ
Стоит отметить, что этот специфический метод SAT работает только в 2D. В 3D вам нужно получить больше, чем просто нормали каждого лица. Как только вы получите правильные нормали, остальная часть процесса (проект, сравнение) будет точно такой же.
Фонд Моника иск
По вашим двухмерным изображениям действительно сложно определить направление движения стрелок.
WDUK
7

Вы обязательно должны посмотреть теорему о разделяющей оси . Это для выпуклых объектов. Существует правило: «Если два выпуклых объекта не пересекаются, то существует плоскость, в которой проекция этих двух объектов не пересекается».

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

Что - то более подходящее для вашей проблемы можно найти здесь (две машины встречных).

zacharmarz
источник
1

Больше статей SAT .

Последняя статья на этом сайте содержит полный код, я думаю, что он написан на FLASH, я понятия не имею, но у меня было ровно 0 проблем с преобразованием его в C ++, когда мне пришлось использовать SAT в первый раз, не должно быть трудно сделать то же самое для других языков. Единственное, что вам нужно будет добавить - это сохранять вектор смещения при каждом расчете (если он самый маленький, конечно, вы поймете это, когда узнаете о SAT), код в этом уроке этого не делает, поэтому Вы получите последний вычисленный вектор.

http://rocketmandevelopment.com/tag/separation-axis-theorem/

Хорошие, старые учебники по N-Game. Лучшая теория SAT в сети.

http://www.metanetsoftware.com/technique/tutorialA.html

Dreta
источник
Это так раздражает, что никто не публикует полный рабочий источник со всеми необходимыми классами. Я перенес его код в собственную демонстрацию, но он просто не работает. :( Это мой проект до сих пор, если кто-то может помочь мне отладить его, это было бы здорово. Ссылка
Джошуа Барнетт
что значит не работает? обратите внимание на то, как вы храните свои вершины, на изображении они находятся в декартовой системе координат, в учебнике он хранит вершины как векторы относительно центроида (все, что вам нужно сделать, это вычесть центроид из ваших собственных вершин или удалите строки, где он изменяет свои собственные вершины), такие функции, как точечный продукт, вы можете создать сами, вам не нужно руководство для них, остальные должны быть прямыми, это не материал для копирования и вставки, изучите SAT, прежде чем пытаться реализовать его
dreta
Вот как я это реализовал: SAT.as , Shape2D.as , что вы подразумеваете под centroid? Центр многоугольника, такой как (x, y)?
Джошуа Барнетт
На данный момент у меня есть функция getOBB (), которая возвращает вершины, как показано на моем исходном изображении. Это вычисляется из вектора <b2Vec2>, содержащего вершины фигуры, переменную угла и переменную положения.
Джошуа Барнетт
да, центр, способ, которым этот парень создает свои многоугольники, дает смещения от центра, idk AS3, но из того, что я вижу, вы проецируете свои вершины такими, какие они есть, при вычислении точечного произведения старайтесь вычесть центроид из вершин (векторное вычитание ), кроме этого вы не проверяете, какой вектор разделения является самым маленьким, вы сохраняете только последний вычисленный
dreta