Box3D beschleunigt den Separating Axis Test mit einbeschriebenen Kugeln
Speeding up the separating axis test using inscribed spheres
Der Separating Axis Test (SAT) ist robust, aber teuer – bei Polytopen kann er O(N³) erreichen. Box3D nutzt einbeschriebene Kugeln, um eine obere Schranke für die Separation zu berechnen und so Faces und Edge-Paare frühzeitig zu verwerfen. Der Autor beschreibt, wie die Gauss-Map-Kantenbögen genutzt werden, um Kanten schon vor dem Edge-Pair-Test auszusortieren, und liefert den konkreten Code für die Kandidatenprüfung.
Ich mag SAT, weil ich alle Kontaktpunkte auf einmal bekomme und keinen Fallback-Algorithmus für Überlappungen wie bei GJK brauche.