Bestimmung des Kollisionsvolumens mit Hilfe des Sutherland-Hodgman-Algorithmus

Im SAT-Beitrag ging es darum, herauszufinden, ob sich zwei konvexe Körper berühren oder schneiden. In diesem Beitrag soll die Kollisionsprüfung nun dahingehend erweitert werden, dass zusätzlich Größe und Mittelpunkt der Kollision näherungsweise berechnet werden.
Dabei wird die für den SAT-Beitrag verwendete Hitbox-Klasse dahingehend erweitert, dass jede Hitbox nun darüber Buch führt, welche Eckpunkte zu welchen Flächen gehören. Es besteht also jetzt eine Verbindung zwischen den vier Eckpunkten, die die Frontseite beschreiben und dem Ebenenvektor dieser Frontseite.

Was kann der hier vorgestellte Algorithmus:

  • Er schneidet zwei konvexe Körper und berechnet die Eckpunkte des dabei entstehenden Schnittvolumens.
public static List<Vector3> CalculateVolume(Hitbox caller, Hitbox collider)
{
    List<Vector3> volumeVertices = new List<Vector3>();

    volumeVertices.AddRange(Hitbox.ClipFaces(caller, collider));
    volumeVertices.AddRange(Hitbox.ClipFaces(collider, caller));

    return volumeVertices;
}

Im obigen Codebeispiel ist der grobe Ablauf zu sehen. Es wird eine leere Liste für die Eckpunkte des Schnittvolumens angelegt. Dann wird die Hitbox des aufrufenden Objekts mit der Hitbox des Kollisionsobjekts geschnitten, und es bleiben nur die Eckpunkte der aufrufenden Hitbox übrig, die sich innerhalb der anderen Hitbox befinden.
Danach verläuft es genau umgekehrt. Somit hat man danach alle Eckpunkte beider Objekte, die sich im jeweils anderen Objekt befinden.

Die benötigten Methoden der erweiterten Hitbox-Klasse

Die Methode ClipFaces() ist als Pseudocode zu verstehen. Es muss selbst dafür Sorge getragen werden, dass die einzelnen Informationen zur Verfügung stehen und abgefragt werden können.
Die hier ebenfalls verwendete Face-Klasse beinhaltet lediglich die zu einer Seite gehörenden Eckpunkte und den Ebenenvektor der Seite. Die Eckpunkte müssen benachbart aufgelistet sein.

public static List<Vector3> ClipFaces(Hitbox caller, Hitbox collider)
{
    // Erstelle eine Kopie aller Eckpunkte der aufrufenden Hitbox:
    List<Vector3> callerVertices = new List<Vector3>(caller.Vertices());

    // Erstelle eine (leere) Liste der Eckpunkte, 
    // die zum Kollisionsvolumen zählen:
    List<Vector3> collisionVolumeVertices = new List<Vector3>();

    // Durchlaufe alle Flächen (faces) der Hitbox des Kollisionsobjekts:
    for (int colliderFaceIndex = 0; colliderFaceIndex < collider.Faces().Length; colliderFaceIndex++)
    {
        Face colliderClippingFace = collider.GetFaceWithIndex(colliderFaceIndex);

        // Hole den ersten Eckpunkt der aktuellen Fläche (face):
        Vector3 colliderClippingFaceVertex = colliderClippingFace.GetFirstVertex();
        // Hole den Ebenenvektor dieser Fläche (surface normal):
        Vector3 colliderClippingFaceNormal = colliderClippingFace.GetFaceNormal();

        // Durchlaufe alle Eckpunkte der aufrufenden Hitbox...
        for (int callerVertexIndex = 0; callerVertexIndex < callerVertices.Count; callerVertexIndex++)
        {
            // ...und hole den aktuellen Eckpunkt und den benachbarten:
            Vector3 callerVertex1 = callerVertices[callerVertexIndex];
            Vector3 callerVertex2 = callerVertices[(callerVertexIndex + 1) % callerVertices.Count];
            // Berechne die Richtung der Linie, die diese 
            // beiden Eckpunkte verbindet:
            Vector3 lineDirection = Vector3.NormalizeFast(callerVertex2 - callerVertex1);

            // Jetzt wird geprüft, ob der eine Eckpunkt vor oder hinter
            // der aktuellen Ebene (face) des Kollisionsobjekts liegt:
            bool callerVertex1InsideRegion = IsInFrontOfPlane(ref callerVertex1, ref colliderClippingFaceNormal, ref colliderClippingFaceVertex);
            // So wird auch mit dem zweiten Eckpunkt verfahren:
            bool callerVertex2InsideRegion = IsInFrontOfPlane(ref callerVertex2, ref colliderClippingFaceNormal, ref colliderClippingFaceVertex);

            if (callerVertex1InsideRegion)
            {
                if (callerVertex2InsideRegion)
                {
                    // Liegen beide Punkte auf der richtigen Seite,
                    // gehören Sie zum Kollisionsvolumen:
                    if (!collisionVolumeVertices.Contains(callerVertex2))
                        collisionVolumeVertices.Add(callerVertex2);
                }
                else
                {
                    // Wenn nicht, dann müssen sie an die Hülle 
                    // des Kollisionskörpers angeglichen werden:
                    Vector3? clippedVertex = ClipLineToPlane(ref callerVertex2, ref lineDirection, ref colliderClippingFaceVertex, ref colliderClippingFaceNormal);
                    // Dieser angepasste Eckpunkt wird dann in die Liste
                    // aufgenommen:
                    if (clippedVertex != null && !collisionVolumeVertices.Contains(clippedVertex.Value))
                        collisionVolumeVertices.Add(clippedVertex.Value);
                }
            }
            else
            {
                // Wenn der erste Punkt nicht auf der richtigen Seite 
                // liegt, aber der zweite Punkt schon, dann wird wieder
                // angeglichen:
                if (callerVertex2InsideRegion)
                {
                    Vector3? clippedVertex = ClipLineToPlane(ref callerVertex1, ref lineDirection, ref colliderClippingFaceVertex, ref colliderClippingFaceNormal);
                    if (clippedVertex != null && !collisionVolumeVertices.Contains(clippedVertex.Value))
                        collisionVolumeVertices.Add(clippedVertex.Value);
                    if (!collisionVolumeVertices.Contains(callerVertex2))
                        collisionVolumeVertices.Add(callerVertex2);
                }
            }
        }
        callerVertices.Clear();
        for(int i = 0; i < collisionVolumeVertices.Count; i++)
        {
            callerVertices.Add(collisionVolumeVertices[i]);
        }
        collisionVolumeVertices.Clear();
    }
    return callerVertices;
}
private static bool IsInFrontOfPlane(ref Vector3 vertex, ref Vector3 planeNormal, ref Vector3 vertexOnPlane)
{
    float distancePointToPlane = Vector3.Dot(planeNormal, vertex - vertexOnPlane);
    return distancePointToPlane >= 0;
}
private static Vector3? ClipLineToPlane(ref Vector3 vertexToBeClipped, ref Vector3 lineDirectionNormalized, ref Vector3 vertexOnPlane, ref Vector3 planeNormal)
{
    if (Vector3.Dot(planeNormal, lineDirectionNormalized) == 0)
        return null;

    float t = (Vector3.Dot(planeNormal, vertexOnPlane) - Vector3.Dot(planeNormal, vertexToBeClipped)) / Vector3.Dot(planeNormal, lineDirectionNormalized);
    Vector3 clippedVertex = vertexToBeClipped + lineDirectionNormalized * t;
    return clippedVertex;
}

Quellen

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.