Ich hab mal S+P implementiert. Der Knackpunkt ist dass du die Änderungen der Konfiguration bewertest, nicht eine Situation an sich.
Nehmen wir mal an, du hast zwei Körper, von denen einer kleiner ist als der andere. Sie überschneiden sich zu Anfang weder in x noch in y-Richtung. (Ich beschränke mich mal auf 2 Dimensionen).
Die Körper seien A und B, mit Bounding-Boxes A1-A2 und B1-B2.
Am Anfang ist die
x-Achse: A1, A2, B1, B2
y-Achse: B1, B2, A1, A2
nun bewegt sich das kleinere A in x-Richtung, bis es hinter B verschwindet. Es passiert hinter B und erscheint wieder. Dabei passieren in den Listen folgende Ereignisse:
A1, A2, B1, B2 -> A1, B1, A2, B2 : A2-B1 tauschen Plätze, Kollision!
A1, B1, A2, B2 -> B1, A1, A2, B2
B1, A1, A2, B2 -> B1, A1, B2, A2
B1, A1, B2, A2 -> B1, B2, A1, A2 : A1-B2 tauschen Plätze, Ende der Kollision
Anders gesagt: Sobald sich ein Ende einer Box zwischen den Enden einer anderen Box befindet hast du eine Kollision. Du führst immer sortierte Listen der Enden und Listen der in jeder Dimension gerade überlappenden Boxen.