Broad phase et narrow phase des collisions : candidats et contacts

Pourquoi séparer le travail de collision ?

Un pipeline de collision remplit deux tâches distinctes : repérer quelles formes sont susceptibles d'interagir, puis déterminer ce que leur géométrie produit réellement. Confondre ces deux tâches conduit à des vues de débogage trompeuses et à des optimisations mal placées. Le chevauchement de deux boîtes englobantes est une raison d'investiguer, pas une preuve suffisante que deux objets de gameplay se sont touchés.

Le contrat des candidats

Une broad phase s'appuie sur des volumes englobants conservateurs pour éviter de tester chaque paire de formes. L'arbre dynamique de Box2D organise des boîtes alignées sur les axes dans une hiérarchie binaire. [1] Les routines de la narrow phase opèrent sur les formes elles-mêmes et peuvent produire des variétés de contact (contact manifolds) contenant des points de contact et une normale. Le filtrage des collisions et le solveur de contraintes qui intervient ensuite ont des responsabilités distinctes. [2]

Exemple détaillé

Prenons 100 caisses en mouvement. Tester chaque paire non ordonnée exigerait 100 × 99 / 2 = 4950 tests de paires. Supposons qu'une requête spatiale, donnée à titre d'illustration, produise 180 candidats après le filtrage par couches, et que les tests géométriques trouvent 24 paires en contact. Ces chiffres inventés servent à expliquer les étapes du pipeline ; ils ne constituent pas un résultat de performance.

Une longue caisse tournée en diagonale peut avoir une boîte alignée sur les axes très grande, avec des coins vides. Une autre caisse qui pénètre dans l'un de ces coins doit passer la broad phase, mais échouer au test sur la forme. Étiqueter comme collision chacun des 180 candidats provoquerait de faux événements de dégâts. À l'inverse, un volume englobant qui ne contient pas entièrement sa forme peut éliminer un contact réel avant que la narrow phase ne le voie.

Méthode de travail pratique

Définissez qui met à jour les proxies spatiaux après un déplacement, un redimensionnement, une activation ou une destruction. Utilisez des identités de paires stables afin qu'une détection répétée ne crée pas d'événements de gameplay en double. Décidez si les filtres s'appliquent avant l'émission des candidats, avant le test des formes, ou aux deux endroits ; documentez toute règle susceptible de changer en cours de partie.

Mesurez séparément le nombre de candidats, le nombre de contacts réels, le coût de mise à jour de l'arbre et le coût des tests géométriques. Dans une scène de diagnostic, affichez à la fois la forme réelle et ses volumes englobants. Incluez des objets fins et tournés, des empilements denses, et un grand objet en mouvement parmi de petits objets. Examinez les contacts manqués avant de chercher à réduire le nombre de candidats.

Compromis et limites

Des volumes englobants généreux peuvent réduire la maintenance de l'index spatial, mais laissent passer davantage de candidats. Des volumes serrés peuvent inverser cet équilibre. Une grille, un arbre ou un sweep-and-prune doit être évalué en fonction de la taille des objets, de leurs mouvements et de leur densité dans la charge de travail visée.

Les scènes denses peuvent malgré tout produire de nombreuses paires valides ; une structure spatiale ne peut pas faire disparaître des interactions inévitables. Gardez observables séparément le chevauchement en broad phase, le contact en narrow phase, la réponse du solveur et la politique de détection des impacts côté gameplay. La détection continue des collisions (CCD) exige elle aussi une politique de requête qui tienne compte du temps ; un simple chevauchement statique à la position finale ne couvre pas un intervalle de mouvement.

Sources

[1] Dynamic tree — Erin Catto and Box2D contributors.

[2] Collision — Erin Catto and Box2D contributors.