Multithread-optimierte Kollisionsberechnungen

Die wohl größte Herausforderung bei der Entwicklung von multithread-fähigen Anwendungen besteht darin, diese threadsicher zu konzipieren. Die in der Theorie so wohlklingende Idee des Multithreadings – die Parallelverarbeitung – sieht sich in der Realität mit ernst zu nehmenden Schwierigkeiten konfrontiert, denn echte Parallelverarbeitung funktioniert nur bei wirklich unabhängigen Aufgaben. In der Realität müssen Threads aufeinander warten, weil ein Thread die Berechnungen eines zweiten Threads benötigt oder werden geblockt, weil gerade ein zweiter Thread auf eine gemeinsam genutzte Ressource zugreift. Diese Mittel der Synchronisierung können jedoch in Echtzeit-Anwendungen schnell zu gravierenden Problemen führen. Als konkretes Beispiel betrachten wir in diesem Artikel die in OpenGL-Tutortial 28 durchgeführten Kollisionsberechnungen zwischen einzelnen Asteroiden in einem Asteroidenfeld.

Das konkrete Problem – die Kollisionsberechnungen können nicht unabhängig von den Bewegungsberechnungen durchgeführt werden, da jede Kollision die Geschwindigkeit und damit die Bewegung ändert.

Mit den Mitteln der Synchronisierung (kritischer Abschnitt oder Mutex) können wir das Problem scheinbar lösen – bei einer laufenden Kollisionsberechnung wird eine anstehende Bewegungsberechnung für die an der Kollision beteiligten Asteroiden blockiert, bzw. eine anstehende Kollisionsberechnung wird so lange blockiert, bis die laufenden Bewegungsberechnungen abgeschlossen sind. Mit zunehmender Anzahl von Asteroiden und möglichen Kollisionen wird das Ganze jedoch problematisch, da sich die an den Bewegungs- und Kollisionsberechnungen beteiligten Threads immer häufiger gegenseitig blockieren würden. Jede zusätzliche Blockierung verringert die Performance und widerspricht dem Gedanken einer echten Parallelverarbeitung.

Doch ist die Synchronisierung der Threads im konkreten Fall wirklich notwendig?

Und was geschieht schlimmstenfalls, wenn man darauf verzichtet?

Für unser konkretes Problem sind die Folgen bei Verzicht auf eine Synchronisierung zu vernachlässigen. Im schlimmsten Fall werden für die Dauer der Kollisionsberechnungen die Bewegungsberechnungen mit einer falschen Geschwindigkeit vorgenommen. Unsere Aufgabe als Entwickler besteht nun darin, die Zeitdauer, in der die Bewegung mit einer falschen Geschwindigkeit simuliert wird, auf ein Minimum zu reduzieren.

Um dies zu erreichen, erstellen wir für die anstehenden Berechnungen zunächst eine Kopie der Asteroid-Geschwindigkeitsvektoren:

// Kopie der Geschwindigkeitsvektoren anlegen:
Velocity1AfterCollision = Asteroid[i].Velocity;
Velocity2AfterCollision = Asteroid[j].Velocity;

Unter Verwendung dieser Kopien werden mithilfe der Compute_3DCollision_Response()-Funktion die neuen Geschwindigkeiten nach erfolgter Kollision berechnet. Im Anschluss daran werden die neu berechneten Geschwindigkeiten den beteiligen Asteroiden-Instanzen zugewiesen:

Asteroid[i].Velocity = Velocity1AfterCollision;
Asteroid[j].Velocity = Velocity2AfterCollision;

Fehler bei den Bewegungsberechnungen in einem zweiten Thread sind nur in dem Zeitraum möglich, in dem die Zuweisung der neuen Geschwindigkeitswerte erfolgt.

Vor den eigentlichen Kollisionsberechnungen wird mithilfe eines einfachen Bounding-Sphären-Tests überprüft, ob sich zwei Asteroiden soweit einander angenähert haben, dass eine Kollision im Bereich des Möglichen liegt. Doch selbst wenn sich die Bounding-Sphären zweier Asteroiden überlappen, können wir nicht sicher sein, ob tatsächlich eine Kollision unmittelbar bevorsteht (die Asteroiden nähern sich einander an) oder ob sich die Kollision bereits ereignet hat (die Asteroiden entfernen sich voneinander). Um zwischen beiden Fällen unterscheiden zu können, berechnen wir zusätzlich den quadratischen Abstand der Kollisionspartner für das nachfolgende Frame (bei 30 Frames pro Sekunde liegt das nachfolgende Frame 1/30 Sekunden in der Zukunft) und vergleichen diesen mit dem aktuellen quadratischen Abstand. Vergrößert sich der Abstand, kann eine Kollision ausgeschlossen werden, da sich die Asteroiden voneinander entfernen. Der nachfolgende Code-Ausschnitt verdeutlicht die einzelnen Berechnungsschritte:

for(i = 0; i < NumAsteroids; i++)
{
// Asteroid ist sichtbar:
if(Asteroid[i].PlayerViewDirectionDistance > 0.0f)
{
for(j = i+1; j < NumAsteroids; j++)
{
// Asteroid ist sichtbar:
if(Asteroid[j].PlayerViewDirectionDistance > 0.0f)
{
// Mehrfachkollisionen zwischen einem Asteroiden-Kollisionspaar vermeiden:
if(Asteroid[i].ID_CollisionPartner != j ||
   Asteroid[j].ID_CollisionPartner != i)
{
// Berechnung der Kollisionsachse (normierte Verbindungslinie zwischen den
// kollidierenden Asteroiden):
CollisionAxis = Asteroid[j].WorldSpacePosition -
                Asteroid[i].WorldSpacePosition;

DistanceSqBeforeCollision = D3DXVec3LengthSq(&CollisionAxis);

// Ist der (quadratische) Abstand zu groß, dann ist eine Kollision
// ausgeschlossen:
if(DistanceSqBeforeCollision > 2.0f*Asteroid[i].ScaleFactor*
                                    Asteroid[j].ScaleFactor+
                                    Asteroid[i].ScaleFactorSq+
                                    Asteroid[j].ScaleFactorSq)
    continue;

// Position der Asteroiden im nächsten Frame berechnen:
Position1Later = Asteroid[i].WorldSpacePosition +
                 Asteroid[i].Velocity*g_FrameTime;

Position2Later = Asteroid[j].WorldSpacePosition +
                 Asteroid[j].Velocity*g_FrameTime;

// neuer Abstandsdifferenzvektor:
DistanceVectorLater = Position1Later - Position2Later;

// Asteroiden bewegen sich voneinander weg (Abstand wird größer),
// daher ist keine Kollision zu befürchten:
if(DistanceSqBeforeCollision < D3DXVec3LengthSq(&DistanceVectorLater))
    continue;

// Kopie der Geschwindigkeitsvektoren anlegen:
Velocity1AfterCollision = Asteroid[i].Velocity;
Velocity2AfterCollision = Asteroid[j].Velocity;

CollisionAxis /= sqrt(DistanceSqBeforeCollision);

Compute_3DCollision_Response(&Velocity1AfterCollision,
                             &Velocity2AfterCollision,
                             Asteroid[i].Mass, Asteroid[j].Mass,
                             &CollisionAxis);

Asteroid[i].Velocity = Velocity1AfterCollision;
Asteroid[j].Velocity = Velocity2AfterCollision;

Asteroid[i].ID_CollisionPartner = j;
Asteroid[j].ID_CollisionPartner = i;
}}}}}

Im Artikel (Spielephysik (game physics): Kollisionen von Massenpunkten im 3D-Raum) sind wir bereits auf die physikalischen Grundlagen (Stoßprozesse) eingegangen, die bei der Berechnung der Geschwindigkeitsänderungen während einer Kollision berücksichtigt werden müssen. Die einzelnen Rechenschritte sollten sich mithilfe des Source Codes der Compute_3DCollision_Response()-Funktion ohne Schwierigkeiten nachvollziehen lassen:

INLINE void Compute_3DCollision_Response(D3DXVECTOR3* pVelocity1,
                                         D3DXVECTOR3* pVelocity2,
                                         float &mass1, float &mass2,
                                         D3DXVECTOR3* pCollisionAxis)
{
    // Berechnung der Anfangsgeschwindigkeitsbeträge entlang der
    // Kollisionsachse:
    float tempFactor1 = D3DXVec3Dot(pVelocity1, pCollisionAxis);
    float tempFactor2 = D3DXVec3Dot(pVelocity2, pCollisionAxis);

    D3DXVECTOR3 CollisionAxisVelocity1;
    D3DXVECTOR3 CollisionAxisVelocity2;

    CollisionAxisVelocity1 = tempFactor1* (*pCollisionAxis);
    CollisionAxisVelocity2 = tempFactor2* (*pCollisionAxis);

    // Subtrahiert man nun diese Geschwindigkeitsbeträge
    // von den Anfangsgeschwindigkeiten, so erhält man die
    // Geschwindigkeitsanteile, die während der Kollision
    // unverändert bleiben:
    *pVelocity1 -= CollisionAxisVelocity1;
    *pVelocity2 -= CollisionAxisVelocity2;

    // Berechnung der Geschwindigkeitsanteile entlang
    // der Kollisionsachse nach dem Stoß:
    float tempFactor3 = mass1 + mass2;
    float tempFactor4 = mass1 - mass2;

    float tempFactor5 = (2.0f*mass2*tempFactor2 + tempFactor1*tempFactor4)/
                         tempFactor3;

    float tempFactor6 = (2.0f*mass1*tempFactor1 - tempFactor2*tempFactor4)/
                         tempFactor3;

    CollisionAxisVelocity1 = tempFactor5* (*pCollisionAxis);
    CollisionAxisVelocity2 = tempFactor6* (*pCollisionAxis);

    // Addiert man die Geschwindigkeitsanteile entlang
    // der Kollisionsachse nach dem Stoß zu den
    // Geschwindkeitsanteilen, die während des Stoßes
    // unverändert bleiben, erhält man die
    // Endgeschwindigkeiten:
    *pVelocity1 += CollisionAxisVelocity1;
    *pVelocity2 += CollisionAxisVelocity2;
}