Thread-basierte (Kollisions)berechnungen – Worker-Threads, Events und Interlocked-Funktionen

Im heutigen Artikel werden wir uns mit dem Ablauf der im OpenGL-Programmbeispiel 12 durchgeführten thread-basierten Kollisionsberechnungen befassen. Sicher werden sich einige von Ihnen die Frage stellen, welche Vorteile wir von der Auslagerung der Kollisionsberechnungen zu erwarten haben oder ob wir die Berechnungen dadurch nicht unnötig verkomplizieren.
Um zu zeigen, wie viel Rechenleistung selbst einfachste Bounding-Sphären-Ausschlusstests bei einer zunehmenden Anzahl von potenziellen Kollisionspartnern beanspruchen, betrachten wir einige Zahlenbeispiele:

• 2 Objekte: 1 mögliches Kollisionspaar
• 3 Objekte: 3 mögliche Kollisionspaare
• 4 Objekte: 6 mögliche Kollisionspaare
• 100 Objekte: 4950 mögliche Kollisionspaare
• n Objekte: n*(n-1)/2 mögliche Kollisionspaare

Ohne zusätzliche Optimierungen – wie beispielsweise durch die Sektorisierung der Spielewelt – können die Kollisionsberechnungen einen Prozessor schneller als man denkt in die Knie zwingen. Die Framerate bricht ein, das Spiel beginnt zu ruckeln und wird unspielbar. Entkoppelt man jedoch diese Berechnungen vom eigentlichen Hauptprogramm und führt sie in einem separaten Thread aus, dann bleibt die Framerate stabil.



Darüber hinaus ist es bei sich langsam bewegenden Objekten sogar unproblematisch, wenn sich die Berechnungen über mehrere Frames hinziehen, etwa weil sie mit geringerer Priorität (weniger Prozessorzeit) durchgeführt werden. Ein Blick auf die zugehörigen Einstellungen in der Datei ThreadSettings.txt im Ordner Bin macht dies deutlich:

AsteroidCollisionsThreadInvPrecision(>=0): 5 
AsteroidCollisionsThreadPriority(>=-2): -2 AsteroidCollisionsThreadProcessorID(<0:StandardSettings): -1

Um Rechenleistung zu sparen, lassen wir den Kollisions-Thread mit minimaler Priorität laufen (AsteroidCollisionsThreadPriority: -2 , THREAD_PRIORITY_LOWEST). Nach Abschluss aller Berechnungen (alle Asteroiden wurden paarweise auf eine mögliche Kollision hin getestet) wartet der Thread auf ein Ereignis (Event), um einen erneuten Durchlauf zu starten. Wann genau die Berechnungen wieder aufgenommen werden, ist vom Parameter AsteroidCollisionsThreadInvPrecision abhängig. Im konkreten Fall wird der neue Kollisionstest-Durchlauf erst 5 Frames nach Beendigung vorherigen aus dem Hauptprogramm heraus gestartet.

Hinweis:

Je langsamer sich die potenziellen Kollisionspartner bewegen, umso mehr Frames können wir warten, bevor ein neuer Durchlauf gestartet werden muss.

Im OpenGL-Programmbeispiel 12 ist es die CAsteroidPhysicsManager-Klasse, die für das Thread-Handling, die Bewegungsberechnungen, für die Durchführung der Sichtbarkeitstests sowie für die Aktualisierung der Asteroid-Instanzdaten verantwortlich ist. Die zugehörigen Thread-Funktionen tragen die passenden Bezeichnungen AsteroidCollisionsThread() sowie AsteroidMovementThread():

unsigned int WINAPI AsteroidCollisionsThread(void* data);
unsigned int WINAPI AsteroidMovementThread(void* data);

class CAsteroidPhysicsManager
{
public:

    long NumAsteroids;
    long NumVisibleAsteroids;

    CCameraAlignedCollisionGrid  CameraAlignedCollisionGrid;
    CAsteroid*                   Asteroid;

    HANDLE AsteroidCollisionsThreadHandle;
    unsigned int AsteroidCollisionsThreadID;

    bool AsteroidCollisionsThreadRunning;
    long AsteroidCollisionsThreadCounter;
    long AsteroidCollisionsThreadInvPrecision;

    HANDLE AsteroidMovementThreadHandle;
    unsigned int AsteroidMovementThreadID;

    bool AsteroidMovementThreadRunning;
    long AsteroidMovementThreadCounter;
    long AsteroidMovementThreadInvPrecision;

    HANDLE UpdateAsteroidCollisionsEvent;
    HANDLE UpdateAsteroidMovementEvent;

    long StopAsteroidCollisionsThreadFromRunning;
    long StopAsteroidMovementThreadFromRunning;

    CAsteroidPhysicsManager();
    ~CAsteroidPhysicsManager();

    void Init_Asteroids(
         CInstancedObjectTextureAndMeshDesc* pTextureAndMeshDesc,
         CSimpleObjectInstanceMemoryManager* pMemoryManager,
         long numAsteroids);

    void Update_Movement(void);
    void Update_Visibility(D3DXVECTOR3* pCameraPosition,
                           D3DXVECTOR3* pCameraViewDirection);

    void Update_Collisions(void);

    void Init_AsteroidCollisionsThread(long threadPriority,
         bool autoThreadAffinity, long processorID);

    void Init_AsteroidMovementThread(long threadPriority,
         bool autoThreadAffinity, long processorID);

    void Update_AsteroidCollisionsThread(void);
    void Update_AsteroidMovementThread(void);

    void Set_AsteroidCollisionsThreadInvPrecision(long InvPrecision);
    void Set_AsteroidMovementThreadInvPrecision(long InvPrecision);
};

Während der Initialisierungsphase müssen die einzelnen Worker-Threads für die Durchführung der Kollisions- und Bewegungsberechnungen zunächst gestartet werden (_beginthreadex()). Im Anschluss daran erfolgt die Festlegung der Threadpriorität (SetThreadPriority()) sowie der Prozessoraffinität (SetCore()):

void CAsteroidPhysicsManager::Init_AsteroidCollisionsThread(
     long threadPriority, bool autoThreadAffinity, long processorID)
{
    if(AsteroidCollisionsThreadRunning == true)
        return;

    StopAsteroidCollisionsThreadFromRunning = 0;

    AsteroidCollisionsThreadHandle = (HANDLE)_beginthreadex(NULL, 0,
    &AsteroidCollisionsThread, this, 0, &AsteroidCollisionsThreadID);

    if(threadPriority == 0)
        SetThreadPriority(AsteroidCollisionsThreadHandle,
                          THREAD_PRIORITY_NORMAL);
    else if(threadPriority == -1)
        SetThreadPriority(AsteroidCollisionsThreadHandle,
                          THREAD_PRIORITY_BELOW_NORMAL);
    else if(threadPriority == -2)
        SetThreadPriority(AsteroidCollisionsThreadHandle,
                          THREAD_PRIORITY_LOWEST);
    else if(threadPriority == 1)
        SetThreadPriority(AsteroidCollisionsThreadHandle,
                          THREAD_PRIORITY_ABOVE_NORMAL);
    else //if(threadPriority == 2)
        SetThreadPriority(AsteroidCollisionsThreadHandle,
                          THREAD_PRIORITY_HIGHEST);

    if(autoThreadAffinity == false)
        SetCore(AsteroidCollisionsThreadHandle, processorID);

    AsteroidCollisionsThreadRunning = true;
}

Mithilfe der Methoden Set_AsteroidCollisionsThreadInvPrecision() sowie Set_AsteroidMovementThreadInvPrecision() lässt sich festlegen, wie viele Frames die Kollisions- bzw. die Bewegungsberechnungen nach Beendigung des letzten Durchlaufs pausieren sollen:

void CAsteroidPhysicsManager::Set_AsteroidCollisionsThreadInvPrecision(
                              long InvPrecision)
{
    AsteroidCollisionsThreadInvPrecision = InvPrecision;
}

Die Funktionen zum Update der Worker-Threads (Update_AsteroidCollisionsThread() sowie Update_AsteroidMovementThread()) werden zwar aus dem Hauptprogramm heraus in jedem Frame aufs Neue aufgerufen, jedoch wird ihre Ausführung so lange vorzeitig abgebrochen, wie die Bedingungen AsteroidCollisionsThreadCounter < AsteroidCollisionsThreadInvPrecision bzw. AsteroidMovementThreadCounter < AsteroidMovementThreadInvPrecision erfüllt sind. Erst nach der vom Benutzer festgelegten Anzahl von Frames werden die Berechnungen neu gestartet:

void CAsteroidPhysicsManager::Update_AsteroidCollisionsThread(void)
{
    if(AsteroidCollisionsThreadCounter <
       AsteroidCollisionsThreadInvPrecision)
    {
        AsteroidCollisionsThreadCounter++;
        return;
    }

    AsteroidCollisionsThreadCounter = 0;

    // Berechnung neu starten:
    SetEvent(UpdateAsteroidCollisionsEvent);

}

Einschub – Events (Ereignisse):

Mithilfe von Events lassen sich die Berechnungen in unterschiedlichen Threads synchronisieren und zugleich unnötige Prozessorlasten (Threads, die mit 100% Prozessorlast laufen, obwohl gerade keine Aufgaben anstehen) vermeiden.

Initialisiert wird ein Event unter Verwendung der CreateEvent()-Funktion:

UpdateAsteroidCollisionsEvent = CreateEvent(NULL,
          TRUE  /*Event kann manuell zurückgesetzt werden*/,
          FALSE /*Event zu Beginn nonsignaled*/, NULL);

Mittels der WaitForSingleObject()-Funktion kann ein Thread so lange „schlafen” gelegt werden, bis ein Event in den signalisierten Zustand versetzt wird:

WaitForSingleObject(UpdateAsteroidCollisionsEvent, INFINITE);

Ein Event wird mithilfe der SetEvent()-Funktion in den signalisierten bzw. mittels der ResetEvent()-Funktion in den nicht-signalisierten Zustand versetzt:

SetEvent(UpdateAsteroidMovementEvent);
ResetEvent(UpdateAsteroidMovementEvent);

Betrachten wir nun am Beispiel der AsteroidCollisionsThread()-Funktion die Implementierung eines einfachen Worker-Threads. Der prinzipielle Aufbau eines solchen Threads ist schnell erklärt:

• Eintritt in eine Endlosschleife
• Warten, bis vom Hauptprogramm das Signal kommt, die Berechnungen neu zu starten
• Berechnungen ausführen
• Überprüfen, ob die Endlosschleife verlassen werden soll (Thread beenden)

unsigned int WINAPI AsteroidCollisionsThread(void* data)
{
    CAsteroidPhysicsManager* pAsteroidPhysicsManager =
    (CAsteroidPhysicsManager*)data;

    for(;;) // Endlosschleife
    {
        // Warten, bis vom Hauptprogramm das Signal kommt, die
        // Berechnungen neu zu starten:
        WaitForSingleObject(
        pAsteroidPhysicsManager->UpdateAsteroidCollisionsEvent, INFINITE);

        // Hinweis:
        // siehe Artikel Multithread-optimierte Kollisionsberechnungen
        pAsteroidPhysicsManager->Update_Collisions();

        ResetEvent(pAsteroidPhysicsManager->UpdateAsteroidCollisionsEvent);

        // Überprüfen, ob die Schleife verlassen werden soll:
        if(InterlockedCompareExchange(
        &pAsteroidPhysicsManager->StopAsteroidCollisionsThreadFromRunning,
        1, /*neuer Wert, sofern der alte Wert mit dem Vergleichswert
            übereinstimmt*/
        1 /*Vergleichswert*/) == 1 /*alter Wert*/)
            break;
    }

    return 0; // Thread beendet sich selbst

}

Einschub – Interlocked-Funktionen:

Mithilfe von Interlocked-Funktionen lassen sich die Werte von Integer-Variablen threadsicher verändern und miteinander vergleichen:

Beispiel 1: Threadsichere Änderung des Wertes einer Integer-Variablen:

// Beispiel – IntegerVariable einen Wert von 10 zuweisen:
InterlockedExchange(&IntegerVariable, 10);

Beispiel 2: Soll der Wert einer Integer-Variable um eins erhöht (inkrementiert) bzw. um eins verringert (dekementiert) werden, so können hierfür die folgenden beiden Funktionen verwendet werden:

InterlockedIncrement(&IntegerVariable);
InterlockedDecrement(&IntegerVariable);
 

Beispiel 3: Threadsichere Änderung des Wertes einer Integer-Variablen, sofern der alte Wert mit dem Vergleichswert übereinstimmt:

// Beispiel – IntegerVariable einen Wert von 10 zuweisen, sofern ihr
// aktueller Wert 5 beträgt:
InterlockedCompareExchange(&IntegerVariable, 10, 5);

Beim Herunterfahren einer Multithread-Anwendung muss man die noch laufenden Threads überwachen, sie manuell abbrechen oder einfach warten, bis die Threads sich von selbst beenden. Beim Aufruf des CAsteroidPhysicsManager-Destruktors wird anhand der Flags AsteroidMovementThreadRunning sowie AsteroidCollisionsThreadRunning zunächst überprüft, ob die Threads für die Bewegungs- und Kollisionsberechnungen überhaupt gestartet wurden. Sollte dies der Fall sein, werden mithilfe der InterlockedExchange()-Funktion die Variablen StopAsteroidMovementThreadFromRunning sowie StopAsteroidCollisionsThreadFromRunning auf eins gesetzt, was beim nächsten Schleifendurchlauf in den jeweiligen Worker-Threads zum Verlassen der Endlosschleifen und damit zur Beendigung der Threads führt. Um sicherzustellen, dass der Abbruchtest überhaupt ausgeführt wird (eventuell warten die Threads auf ein Signal vom Hauptprogramm, ihre Berechnungen neu zu beginnen), müssen die Berechnungsdurchläufe vorsorglich ein letztes Mal neu gestartet werden (SetEvent(UpdateAsteroidMovementEvent) sowie SetEvent(UpdateAsteroidCollisionsEvent)). Im Anschluss daran wird die Ausführung des Hauptprogramms so lange unterbrochen, bis die Threads das Ende ihrer Lebensdauer signalisieren (WaitForSingleObject(AsteroidMovementThreadHandle, INFINITE) sowie WaitForSingleObject(AsteroidCollisionsThreadHandle, INFINITE)). Im letzten Schritt werden die Thread- und Event-Handles unter Verwendung der CloseHandle()-Funktion geschlossen und die weiteren Aufräumarbeiten durchgeführt:

CAsteroidPhysicsManager::~CAsteroidPhysicsManager()
{
    if(AsteroidMovementThreadRunning == true)
    {
    InterlockedExchange(&StopAsteroidMovementThreadFromRunning, 1);
    SetEvent(UpdateAsteroidMovementEvent);
    WaitForSingleObject(AsteroidMovementThreadHandle, INFINITE);
    CloseHandle(AsteroidMovementThreadHandle);
    }

    if(AsteroidCollisionsThreadRunning == true)
    {
    InterlockedExchange(&StopAsteroidCollisionsThreadFromRunning, 1);
    SetEvent(UpdateAsteroidCollisionsEvent);
    WaitForSingleObject(AsteroidCollisionsThreadHandle, INFINITE);
    CloseHandle(AsteroidCollisionsThreadHandle);
    }

    CloseHandle(UpdateAsteroidMovementEvent);
    CloseHandle(UpdateAsteroidCollisionsEvent);

    SAFE_DELETE_ARRAY(Asteroid)
}