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 ;
}
Вы обязательно должны посмотреть теорему о разделяющей оси . Это для выпуклых объектов. Существует правило: «Если два выпуклых объекта не пересекаются, то существует плоскость, в которой проекция этих двух объектов не пересекается».
Вы можете найти несколько примеров в вики . Но это немного сложнее, чем для вашего случая.
Что - то более подходящее для вашей проблемы можно найти здесь (две машины встречных).
источник
Больше статей SAT .
Последняя статья на этом сайте содержит полный код, я думаю, что он написан на FLASH, я понятия не имею, но у меня было ровно 0 проблем с преобразованием его в C ++, когда мне пришлось использовать SAT в первый раз, не должно быть трудно сделать то же самое для других языков. Единственное, что вам нужно будет добавить - это сохранять вектор смещения при каждом расчете (если он самый маленький, конечно, вы поймете это, когда узнаете о SAT), код в этом уроке этого не делает, поэтому Вы получите последний вычисленный вектор.
http://rocketmandevelopment.com/tag/separation-axis-theorem/
Хорошие, старые учебники по N-Game. Лучшая теория SAT в сети.
http://www.metanetsoftware.com/technique/tutorialA.html
источник