L’analogie de Flatland
Flatland (1884) d’Edwin Abbott : habitants d’un plan bidimensionnel. Ils perçoivent la longueur et la largeur. La profondeur, troisième dimension au-dessus d’eux, leur est invisible. Ils ne peuvent ni la percevoir, ni l’utiliser, ni construire avec elle. La géométrie de leur monde contient une dimension qu’ils ignorent structurellement.
MOAD-0007 fonctionne de la même manière. Les objets dans l’espace 3D possèdent position, rotation et volume englobant : une riche structure géométrique. Un balayage linéaire les traite comme une liste plate. La structure spatiale est présente, inutilisée, ignorée. Chaque test d’intersection parcourt toute la liste, comme si les objets n’avaient ni géométrie ni position.
L’exemple Three.js
Three.js Raycaster.intersectObjects() : étant donné un rayon (une position et une direction dans l'espace 3D), trouve tous les objets que le rayon intersecte. L'implémentation : itère sur les N objets de la scène et teste chacun d'eux contre le rayon. O(N) par appel.
Un gestionnaire d'événement hover appelle intersectObjects() une fois par frame à 60 images par seconde. Avec N=100 objets : 6 000 tests d'intersection par seconde. Avec N=10 000 objets : 600 000 tests par seconde. Le coût : proportionnel à N, pas au nombre d'objets réellement intersectés par le rayon.
À N=100 : invisible. Le budget de frame (16,7 ms à 60 fps) absorbe le coût sans problème.
À N=10 000 : dominant. 600 000 tests d'intersection par seconde saturent le thread principal. Le taux de rafraîchissement chute. La scène qui fonctionnait à N=100 s'effondre silencieusement lorsque N franchit le seuil.
La structure que le balayage linéaire ignore
Les objets occupent des positions dans l'espace. Un objet situé à (1000, 0, 0) ne peut pas intersecter un rayon pointant dans la direction (-1, 0, 0) depuis (0, 0, 0) : l'objet se trouve dans la direction opposée. Un balayage linéaire le teste quand même.
Les objets possèdent des volumes englobants : une sphère ou une boîte qui contient l'objet entier. Un rayon qui n'intersecte pas le volume englobant d'un objet ne peut pas intersecter l'objet lui-même. Un balayage linéaire effectue quand même le test complet d'intersection.
La géométrie indique quels objets ignorer. Le balayage linéaire ignore la géométrie. C'est ce qu'il rejette.
Que signifie « Éliminer la structure »
L’analogie de Flatland : les habitants d’Abbott ne pouvaient pas percevoir la profondeur. Un défaut Flatland élimine la structure géométrique présente dans les données mais qui n’entre jamais dans l’algorithme.
Pourquoi une table de hachage ne peut pas résoudre MOAD-0007
MOAD-0001 fix: remplacer un test d’appartenance séquentiel par un ensemble de hachage. list.contains(x): O(N). set.has(x): O(1). La question d’appartenance : « x est-il dans cette collection ? » Aucune géométrie spatiale impliquée.
MOAD-0007 fix: remplacer un balayage spatial linéaire par un index spatial (BVH, octree, k-d tree, R-tree). La question spatiale : « quels objets de cette collection intersectent ce rayon/sphère/frustum ? » Proximité spatiale requise.
Un ensemble de hachage répond à l’appartenance : « cet objet exact est-il présent ? » O(1). Il ne peut pas répondre à la proximité : « quels objets sont près de ce rayon ? » Un ensemble de hachage n’a aucune notion de distance ou d’étendue spatiale. Le hachage élimine la géométrie aussi complètement qu’un balayage linéaire.
Un BVH répond à la proximité : « quels objets se trouvent dans cette requête spatiale ? » O(log N + k). Il organise les objets par position, ce qui permet aux requêtes de proximité d’ignorer les objets géométriquement éloignés.
| Question | Structure correcte | Structure incorrecte |
|---|---|---|
| L’objet X est-il dans cet ensemble ? | HashSet (O(1)) | Liste linéaire (O(N)) |
| Quels objets intersectent ce rayon ? | BVH/octree/k-d tree (O(log N)) | Balayage linéaire OU HashSet (O(N) ou O(N)) |
MOAD-0001 & MOAD-0007 : deux opérations O(N) remplacées par quelque chose de plus rapide. Des structures différentes sont nécessaires car les questions diffèrent.
Quand construire, quand ignorer
Construire un BVH coûte O(N log N). Les requêtes coûtent O(log N + k). Seuil de rentabilité : lorsque le nombre de requêtes dépasse suffisamment celui des constructions pour que les économies réalisées dépassent le coût de construction.
À N=100 : le balayage linéaire prend quelques microsecondes. La construction du BVH ajoute un surcoût. Ignorez le BVH.
À N=10 000 à 60 Hz : le balayage linéaire consomme le budget de la frame. Les requêtes BVH coûtent 1/1 000 du balayage linéaire. Construisez le BVH une fois ; interrogez 60 fois par seconde. Le seuil de rentabilité est atteint avant la première frame.
La règle : construisez lorsque N * Q > N log N, où Q = nombre de requêtes par cycle de reconstruction. Pour les scènes 3D interactives : Q = 60 par seconde, seuil N = quelques centaines d’objets.
Diagnostiquer & corriger une scène 3D
Une application de visualisation 3D affiche 5 000 objets géométriques. Un gestionnaire de survol se déclenche 60 fois par seconde. À chaque événement de survol, le gestionnaire appelle scene.intersectObjects(ray, objects) qui itère sur les 5 000 objets et teste chacun contre le rayon. Le taux de rafraîchissement est passé de 60 fps à 8 fps.
Un coéquipier suggère : « Place tous les objets dans un Set pour une recherche en O(1). »