Нахождение точки контакта с SAT

Теорема о разделяющей оси (SAT) упрощает определение минимального вектора перемещения, т. Е. Самого короткого вектора, который может разделить два сталкивающихся объекта. Однако мне нужен вектор, который разделяет объекты вдоль вектора, в котором движется проникающий объект (то есть точка контакта).

Я нарисовал картинку, чтобы помочь уточнить. Есть одна коробка, перемещающаяся из позиции «до» в позицию «после». В своей позиции после, он пересекает серый многоугольник. SAT может легко вернуть MTV, который является красным вектором. Я рассчитываю рассчитать синий вектор.

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

Есть ли более простой и / или более эффективный способ найти вектор точки контакта?

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

К счастью, тесты с разделительной осью могут вам помочь! Вот описание алгоритма, любезно предоставленное Роном Левайном :

Алгоритм идет так. Вы работаете с вектором относительной скорости двух выпуклых тел. Проецирование каждого из двух тел и вектора относительной скорости на конкретную разделяющую ось при t ₀ дает два одномерных интервала и одномерную скорость, так что легко определить, пересекаются ли два интервала, и если нет, то они раздвигаются или движутся вместе. Если они разделены и раздвигаются по какой-либо из разделяющих осей (или, по сути, по любой оси независимо от), то вы знаете, что в будущем столкновения не будет. Если на любой разделяющей оси два проецируемых интервала пересекаются при t₀ или разделены и движутся вместе, то легко вычислить (двумя простыми одномерными линейными выражениями) самое раннее будущее время, в которое два интервала будут сначала пересекаться, и (при условии продолжения прямолинейного движения) самое позднее будущее время, когда два интервалы будут в последний раз пересекаться и начать раздвигаться. (Если они пересекаются при t ₀, то самое раннее будущее время пересечения будет t t). Сделайте это для максимально всех разделительных осей. Если максимум по всем осям самого раннего будущего времени пересечения меньше, чем минимум по всем осям самого последнего будущего времени пересечения, то это максимальное самое раннее будущее время пересечения является точным временем первого столкновения двух трехмерных многогранников, в противном случае нет столкновения в будущем.

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

Вот несколько грубых и совершенно непроверенных псевдокодов для алгоритма:

t_min := +∞
t_max := -∞
foreach axis in potential_separating_axes
    a_min := +∞
    a_max := -∞
    foreach vertex in a.vertices
        a_min = min(a_min, vertex · axis)
        a_max = max(a_max, vertex · axis)
    b_min := +∞
    b_max := -∞
    foreach vertex in b.vertices
        b_min = min(b_min, vertex · axis)
        b_max = max(b_max, vertex · axis)
    v := b.velocity · axis
    if v > 0 then
        if a_max < b_min then
            return no_intersection
        else if (a_min < b_min < a_max) or (b_min < a_min < b_max) then
            t_min = min(t_min, (a_max - b_min) / v)
            t_max = max(t_max, 0)
        else
            t_min = min(t_min, (a_max - b_min) / v)
            t_max = max(t_max, (a_min - b_max) / v)
    else if v < 0 then
        // repeat the above case with a and b swapped
    else if v = 0 then
        if a_min < b_max and b_min < a_max then
            t_min = min(t_min, 0)
            t_max = max(t_max, 0)
        else
            return no_intersection
if t_max < t_min then
    // advance b by b.velocity * t_max
    return intersection
else
    return no_intersection

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

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

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

http://www.codezealot.org/archives/394

Контактный коллектор возвратит точку на одном из объектов, который «наиболее ответственен» за столкновение, а не на прямую точку столкновения. Однако вам не нужна эта прямая точка столкновения. Вы можете просто раздвинуть объекты, используя уже имеющуюся глубину проникновения и нормаль, и использовать контактный коллектор, чтобы применить другие физические эффекты (например, заставить коробку опрокинуться / скатиться по склону).

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

Глубина проникновения будет относительно небольшой, и простое выталкивание коробки из уклона по нормали проникновения приведет к тому, что коробка окажется достаточно близко к «правильному» положению, чтобы быть практически незаметной на практике, особенно если коробка будет подпрыгивать, падать или скользить потом в любом случае.

Просто спроецируйте вектор MAT на направление Vector. Полученный вектор может быть добавлен к вектору направления для компенсации проникновения. Спроецируйте это так же, как вы делаете на Оси, когда делаете SAT. Это устанавливает объект точно в положение, в котором он касается другого объекта. Добавьте небольшой эпсилон для борьбы с проблемами с плавающей запятой.

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

После того, как вы определили MTV, вы знаете норму кромки / поверхности, с которой вам нужно проверить. Вам также известен линейный вектор скорости взаимопроникающего объекта.

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

vec3 vertex;
float mindot = FLT_MAX;
for ( vert : vertices )
{
    if (dot(vert, MTV) < mindot)
    {
         mindot = dot(vert, MTV);
         vertex = vert;
    }
}

Как только вы определили вершину, бинарный полушаг становится намного менее дорогим:

//mindistance is the where the reference edge/plane intersects it's own normal. 
//The max dot product of all vertices in B along the MTV will get you this value.
halfstep = 1.0f;
vec3 cp = vertex;
vec3 v = A.velocity*framedurationSeconds;
float errorThreshold = 0.01f; //choose meaningful value here
//alternatively, set the while condition to be while halfstep > some minimum value
while (abs(dot(cp,normal)) > errorThreshold)
{            
    halfstep*=0.5f;
    if (dot(cp,normal) < mindistance) //cp is inside the object, move backward
    {
        cp += v*(-1*halfstep);
    }
    else if ( dot(cp,normal) > mindistance) //cp is outside, move it forward
    {
        cp += v*(halfstep);
    }
}

return cp;

Это достаточно точно, но обеспечит только одну точку столкновения в одном случае.

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

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

Интересно, что этот метод полушагов также может дать вам (почти) точное время, когда объект произошел во время кадра:

float collisionTime = frametimeSeconds * halfstep;

Если вы выполняете какое-то физическое разрешение столкновений, вы можете исправить положение A следующим образом:

v - (v*halfstep)

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