Die Flatland-Analogie
Edwin Abbotts Flatland (1884): Einwohner eines zweidimensionalen Planes. Sie wahrnehmen Länge und Breite. Tiefe: die dritte Dimension über ihnen, unsichtbar. Sie können sie nicht wahrnehmen, nicht nutzen, nicht darauf aufbauen. Die Geometrie ihrer Welt enthält eine Dimension, die sie strukturiert verwerfen.
MOAD-0007 funktioniert genauso. Objekte im 3D-Raum haben Position, Rotation und Begrenzungsgeometrie: eine reiche geometrische Struktur. Eine lineare Abfrage behandelt sie wie eine flache Liste. Die räumliche Struktur: vorhanden, nicht genutzt, verworfen. Jeder Intersections-Test scannt die gesamte Liste, als hätten die Objekte keine Geometrie und keine Position.
Der Three.js-Beispiel
Three.js Raycaster.intersectObjects(): Gegeben ein Strahl (eine Position und eine Richtung im 3D-Raum), finden Sie alle Objekte, die der Strahl trifft. Die Implementierung: Iterieren Sie durch alle N Szenenobjekte und testen Sie jedes einzelne gegen den Strahl. O(N) pro Anruf.
Ein Hover-Ereignishandler ruft intersectObjects() einmal pro Frame bei 60 Frames pro Sekunde auf. Mit N=100 Objekten: 6.000 Intersections-Tests pro Sekunde. Mit N=10.000 Objekten: 600.000 Tests pro Sekunde. Der Kosten: proportional zu N, nicht zu der Anzahl der Objekte, die der Strahl tatsächlich trifft.
Bei N=100: unsichtbar. Der Frame-Budget (16,7ms bei 60fps) verträgt den Kosten ohne Beschwerde.
Bei N=10.000: dominierend. 600.000 Intersections-Tests pro Sekunde blockiert den Hauptthread. Die Framesrate fällt. Die Szene, die bei N=100 funktioniert hat, bricht stillschweigend zusammen, wenn die Schwellenwert überquert wird.
Die von der linearen Abfrage verworfene Struktur
Objekte nehmen Positionen im Raum ein. Ein Objekt in der Position (1000, 0, 0) kann nicht mit einem vom Punkt (0, 0, 0) im Bereich (-1, 0, 0) zeigenden Strahl interagieren: Das Objekt liegt in entgegengesetzter Richtung. Eine lineare Abfrage prüft es dennoch.
Objekte haben Begrenzungsgeometrien: eine Kugel oder Box, die das gesamte Objekt umschließt. Ein Strahl, der nicht mit der Begrenzungsgeometrie eines Objekts zusammenstößt, kann das Objekt nicht treffen. Eine lineare Abfrage berechnet den vollständigen Intersections-Test dennoch.
Die Geometrie enthält Informationen darüber, welche Objekte übersprungen werden sollten. Die lineare Abfrage ignoriert die Geometrie. Dies ist der Verlust.
Was 'Die Struktur verwerfen' bedeutet
Die Flatland-Analogie: Abbotts Bewohner konnten keine Tiefe wahrnehmen. Ein Flatland Defect entsorgt geometrische Struktur, die in den Daten vorhanden ist, aber nie in das Algorithmus eintritt.
Warum kann ein Hash Set MOAD-0007 nicht beheben
MOAD-0001 Lösung: Ersetzen einer sequenziellen Mitgliedschaftsprüfung durch ein Hash Set. list.contains(x): O(N). set.has(x): O(1). Die Mitgliedschaftsfrage: 'Ist x in dieser Sammlung?' Keine räumliche Geometrie erforderlich.
MOAD-0007 Lösung: Ersetzen einer linearen räumlichen Durchsuchung durch einen räumlichen Index (BVH, Oktaeder, k-d Baum, R-Baum). Die räumliche Frage: 'Welche Objekte in dieser Sammlung schneiden mit diesem Strahl/Sphäre/Frustum?' Räumliche Nähe erforderlich.
Ein Hash Set beantwortet die Mitgliedschaft: 'Ist dieses exakte Objekt vorhanden?' O(1). Es kann keine Nähe beantworten: 'Welche Objekte in der Nähe dieses Strahls?' Ein Hash Set hat keine Vorstellung von Entfernung oder räumlicher Ausdehnung. Hashing entsorgt die Geometrie genauso gründlich wie eine lineare Durchsuchung.
Ein BVH beantwortet die Nähe: 'Welche Objekte fallen innerhalb dieses räumlichen Abfragens?' O(log N + k). Es organisiert Objekte nach Position, so dass Näheabfragen geometrisch entfernte Objekte überspringen.
| Frage | Korrekte Struktur | Falsche Struktur |
|----------|------------------|-----------------|
| Ist Objekt X in dieser Menge? | HashSet (O(1)) | Lineare Liste (O(N)) |
| Welche Objekte schneiden mit diesem Strahl? | BVH/Oktaeder/k-d Baum (O(log N)) | Lineare Durchsuchung ODER HashSet (O(N) oder O(N)) |
MOAD-0001 & MOAD-0007: beide O(N)-Operationen durch etwas Schnelleres ersetzt. Unterschiedliche Strukturen erforderlich, weil die Fragen sich unterscheiden.
Wann bauen, wann überspringen
Ein BVH (Hierarchisches Baumverzeichnis) kostet O(N log N) zum Erstellen. Abfragen kosten O(log N + k). Gleichgewicht: Wenn die Anzahl der Abfragen die Anzahl der Erstellungen um genug, dass die Abfragesparnis den Erstellungsaufwand übersteigt.
Bei N=100: Lineares Scannen dauert Mikrosekunden. BVH-Erstellung fügt Overhead hinzu. Das BVH überspringen.
Bei N=10,000 bei 60Hz: Lineares Scannen dominiert Frame-Budget. BVH-Abfragen kosten 1/1.000 des linearen Scannens. Das BVH einmal erstellen; 60 Abfragen pro Sekunde. Gleichgewicht erreicht, bevor der erste Frame gezeigt wird.
Die Regel: erstellen, wenn N * Q > N log N, wo Q = Anzahl der Abfragen pro Wiederherstellungszyklus. Für interaktive 3D-Szenen: Q = 60 pro Sekunde, Schwellenwert für N = ein paar hundert Objekte.
Diagnose & Fix a 3D Scene
Eine 3D-Visualisierungsanwendung rendernt 5.000 geometrische Objekte. Ein Hover-Handler feuert 60 Mal pro Sekunde. Bei jedem Hover-Ereignis ruft der Handler scene.intersectObjects(ray, objects) auf, wobei es alle 5.000 Objekte abläuft und jedes gegen den Strahl getestet wird. Die Frames pro Sekunde sank von 60fps auf 8fps.
Ein Teamkollege schlägt vor: 'Alle Objekte in einem Set für O(1)-Abfrage einfügen.'