Die Flatland-Analogie
Edwin Abbotts Flatland (1884): Bewohner einer zweidimensionalen Ebene. Sie nehmen Länge und Breite wahr. Tiefe: die dritte Dimension über ihnen, unsichtbar. Sie können sie nicht wahrnehmen, nicht nutzen, nicht damit bauen. Die Geometrie ihrer Welt enthält eine Dimension, die sie strukturell verwerfen.
MOAD-0007 funktioniert genauso. Objekte im 3D-Raum tragen Position, Rotation und Bounding Volume: eine reichhaltige geometrische Struktur. Ein Linearsuchlauf behandelt sie als flache Liste. Die räumliche Struktur: vorhanden, ungenutzt, verworfen. Jeder Schnitttest durchsucht die gesamte Liste, als hätten die Objekte keine Geometrie und keine Position.
Das Three.js-Beispiel
Three.js Raycaster.intersectObjects(): gegeben eines Strahls (einer Position & Richtung im 3D-Raum), alle Objekte finden, die der Strahl schneidet. Die Implementierung: durch alle N Szenen-Objekte iterieren, jedes einzeln gegen den Strahl testen. O(N) pro Aufruf.
Ein Hover-Event-Handler ruft intersectObjects() einmal pro Frame bei 60 Frames pro Sekunde auf. Bei N=100 Objekten: 6.000 Schnitttests pro Sekunde. Bei N=10.000 Objekten: 600.000 Tests pro Sekunde. Die Kosten: proportional zu N, nicht zur Anzahl der Objekte, die der Strahl tatsächlich schneidet.
Bei N=100: unsichtbar. Das Frame-Budget (16,7 ms bei 60 fps) absorbiert die Kosten ohne Beschwerde.
Bei N=10.000: dominant. 600.000 Schnitttests pro Sekunde sättigen den Main-Thread. Die Framerate bricht ein. Die Szene, die bei N=100 funktionierte, kollabiert still, sobald N die Schwelle überschreitet.
Die Struktur, die der lineare Scan verwirft
Objekte belegen Positionen im Raum. Ein Objekt an Position (1000, 0, 0) kann einen Strahl, der in Richtung (-1, 0, 0) von Position (0, 0, 0) zeigt, nicht schneiden: das Objekt liegt in der entgegengesetzten Richtung. Ein linearer Scan prüft es trotzdem.
Objekte haben Bounding Volumes: eine Kugel oder Box, die das gesamte Objekt umschließt. Ein Strahl, der das Bounding Volume eines Objekts nicht schneidet, kann das Objekt nicht schneiden. Ein linearer Scan führt trotzdem den vollständigen Schnitttest durch.
Die Geometrie kodiert, welche Objekte übersprungen werden können. Der lineare Scan ignoriert die Geometrie. Das ist das Verwerfen.
Was „Struktur verwerfen“ bedeutet
Die Flatland-Analogie: Abbotts Bewohner konnten keine Tiefe wahrnehmen. Ein Flatland-Defekt verwirft geometrische Struktur, die in den Daten existiert, aber nie in den Algorithmus gelangt.
Warum ein Hash-Set MOAD-0007 nicht beheben kann
MOAD-0001-Fix: Ersetze einen sequentiellen Mitgliedschaftstest 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 involviert.
MOAD-0007-Fix: Ersetze einen linearen räumlichen Scan durch einen räumlichen Index (BVH, Octree, k-d-Baum, R-Baum). Die räumliche Frage: „Welche Objekte in dieser Sammlung schneiden diesen Strahl/diese Kugel/dieses Frustum?“ Räumliche Nähe erforderlich.
Ein Hash-Set beantwortet Mitgliedschaft: „Ist dieses exakte Objekt vorhanden?“ O(1). Es kann keine Nähe beantworten: „Welche Objekte liegen nahe diesem Strahl?“ Ein Hash-Set hat keine Vorstellung von Distanz oder räumlicher Ausdehnung. Hashing verwirft Geometrie genauso gründlich wie ein linearer Scan.
Ein BVH beantwortet Nähe: „Welche Objekte fallen in diese räumliche Abfrage?“ O(log N + k). Es organisiert Objekte nach Position, sodass Nähe-Abfragen geometrisch entfernte Objekte überspringen.
| Frage | Korrekte Struktur | Falsche Struktur |
|---|---|---|
| Ist Objekt X in diesem Set? | HashSet (O(1)) | Lineare Liste (O(N)) |
| Welche Objekte schneiden diesen Strahl? | BVH/Octree/k-d-Baum (O(log N)) | Linearer Scan ODER HashSet (O(N) oder O(N)) |
MOAD-0001 & MOAD-0007: beide O(N)-Operationen werden durch etwas Schnelleres ersetzt. Unterschiedliche Strukturen sind erforderlich, weil sich die Fragestellungen unterscheiden.
Wann bauen, wann überspringen
Der Aufbau einer BVH kostet O(N log N). Abfragen kosten O(log N + k). Break-even: wenn Abfragen den Aufbau so oft übertreffen, dass die Einsparungen die Aufbaukosten übersteigen.
Bei N=100: Linearer Scan dauert Mikrosekunden. BVH-Aufbau verursacht Overhead. BVH überspringen.
Bei N=10.000 bei 60 Hz: Linearer Scan dominiert das Frame-Budget. BVH-Abfragen kosten nur 1/1.000 des linearen Scans. BVH einmal aufbauen, 60-mal pro Sekunde abfragen. Break-even wird vor dem ersten Frame erreicht.
Die Regel: bauen, wenn N * Q > N log N, wobei Q = Abfragen pro Aufbauzyklus. Für interaktive 3D-Szenen: Q = 60 pro Sekunde, N-Schwelle = wenige hundert Objekte.
Diagnose & Fix einer 3D-Szene
Eine 3D-Visualisierungsanwendung rendert 5.000 geometrische Objekte. Ein Hover-Handler wird 60-mal pro Sekunde ausgelöst. Bei jedem Hover-Ereignis ruft der Handler scene.intersectObjects(ray, objects) auf, der alle 5.000 Objekte durchläuft und jedes gegen den Strahl testet. Die Framerate sank von 60 fps auf 8 fps.
Ein Teammitglied schlägt vor: „Alle Objekte in ein Set legen für O(1)-Lookup.“