Как найти минимальный вектор перевода повернутых квадратов? - PullRequest
Новая
       29

Как найти минимальный вектор перевода повернутых квадратов?

0 голосов
/ 03 июля 2018

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

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

Проблема в том, что мой код не работает путем сравнения проекций, а вместо этого использует этот код для обнаружения коллизий: 

double DotProduct(Vector vector0, Vector vector1)
{
    return (vector0.X * vector1.X) + (vector0.Y * vector1.Y);
}

bool TestIfPointIsInFrontOfEdge(int edgeNormalIndex, int vertexToTestIndex, Box observerBox, Box observedBox)
{
    // if (v - a) · n > 0 then vertex is in front of edge
    // v is the vertex to test
    // a is a vertex on the edge that relates to the edge normal
    // n is the edge normal

    Vector v = new Vector(observedBox.vertices[vertexToTestIndex].X, observedBox.vertices[vertexToTestIndex].Y);
    Vector a = new Vector(observerBox.vertices[edgeNormalIndex].X, observerBox.vertices[edgeNormalIndex].Y);
    Vector n = observerBox.edgeNormals[edgeNormalIndex];

    Vector vMinusA = Vector.Subtract(v, a);
    double dotProduct = DotProduct(vMinusA, n);

    //Console.WriteLine(dotProduct);

    return dotProduct > 0;
}

bool TestIfAllPointsAreInFrontOfEdge(int edgeIndex, Box observerBox, Box observedBox)
{
    for (int i = 0; i < observedBox.vertices.Length; i++)
    {
        if (!TestIfPointIsInFrontOfEdge(edgeIndex, i, observerBox, observedBox))
        {
            return false;
        }
    }

    return true;
}

bool TestIfAllPointsAreInFrontOfAnyEdge(Box observerBox, Box observedBox)
{
    for (int i = 0; i < observerBox.edgeNormals.Length; i++)
    {
        if (TestIfAllPointsAreInFrontOfEdge(i, observerBox, observedBox))
            return true;
    }

    return false;
}

bool TestBoxOverlap(Box observerBox, Box observedBox)
{
    if (TestIfAllPointsAreInFrontOfAnyEdge(observerBox, observedBox) || TestIfAllPointsAreInFrontOfAnyEdge(observedBox, observerBox))
        return false;

    return true;
}

Каждый блок содержит массив из четырех объектов PointF, которые представляют вершины (Box.vertices). Они также содержат массив из четырех объектов Vector, которые являются нормализованными (единичными) векторами, представляющими нормали к каждому из ребер (Box.edgeNormals).

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

if (TestBoxOverlap(observerBox, observedBox))
{
    narrowPhaseCollisionList.Add(collision);
}

Столкновение - это массив из двух элементов, содержащий ObserverBox и seenBox.

Так как мне рассчитать MTV?

Также, как мне применить это к коробкам?

  • Перевести только одну коробку с MTV?
  • Перевести каждую коробку подальше с половиной MTV?
  • Каким-то образом вес какой части MTV применяется к каждой коробке в зависимости от некоторого свойства (массы / скорости) коробок?
...