Analogia do Płaskolandii
Flatland Edwina Abbotta (1884): mieszkańcy dwuwymiarowej płaszczyzny. Postrzegają długość i szerokość. Głębokość: trzeci wymiar nad nimi, niewidoczny. Nie mogą go postrzegać, nie mogą go używać, nie mogą z nim budować. Geometria ich świata zawiera wymiar, który strukturalnie odrzucają.
MOAD-0007 działa tak samo. Obiekty w przestrzeni 3D niosą pozycję, rotację i objętość ograniczającą: bogatą strukturę geometryczną. Skan liniowy traktuje je jak płaską listę. Struktura przestrzenna: obecna, nieużywana, odrzucona. Każdy test przecięcia skanuje całą listę, jakby obiekty nie miały geometrii ani pozycji.
Przykład Three.js
Three.js Raycaster.intersectObjects(): mając promień (pozycję i kierunek w przestrzeni 3D), znajdź wszystkie obiekty, z którymi promień się przecina. Implementacja: przejdź przez wszystkie N obiektów sceny i przetestuj każdy z nich względem promienia. O(N) na wywołanie.
Obsługa zdarzenia hover wywołuje intersectObjects() raz na klatkę przy 60 klatkach na sekundę. Przy N=100 obiektów: 6 000 testów przecięcia na sekundę. Przy N=10 000 obiektów: 600 000 testów na sekundę. Koszt: proporcjonalny do N, a nie do liczby obiektów, z którymi promień faktycznie się przecina.
Przy N=100: niewidoczny. Budżet klatki (16,7 ms przy 60 fps) pochłania koszt bez protestu.
Przy N=10 000: dominujący. 600 000 testów przecięcia na sekundę obciąża główny wątek. Liczba klatek spada. Scena, która działała przy N=100, cicho się załamuje, gdy N przekracza próg.
Struktura, którą odrzuca skan liniowy
Obiekty zajmują pozycje w przestrzeni. Obiekt znajdujący się na pozycji (1000, 0, 0) nie może przeciąć promienia skierowanego w kierunku (-1, 0, 0) z pozycji (0, 0, 0): obiekt leży w przeciwnym kierunku. Skan liniowy i tak go sprawdza.
Obiekty mają objętości ograniczające: sferę lub prostopadłościan otaczający cały obiekt. Promień, który nie przecina objętości ograniczającej obiektu, nie może przeciąć samego obiektu. Skan liniowy i tak wykonuje pełny test przecięcia.
Geometria koduje, które obiekty można pominąć. Skan liniowy ignoruje geometrię. To jest odrzucenie.
Co oznacza „Odrzucanie Struktury”
Analogia Flatland: mieszkańcy Flatlandu nie mogli postrzegać głębi. Defekt Flatland odrzuca strukturę geometryczną, która istnieje w danych, ale nigdy nie trafia do algorytmu.
Dlaczego Zbiór Haszujący Nie Może Naprawić MOAD-0007
MOAD-0001 fix: zastąp sekwencyjne sprawdzanie przynależności zbiorem haszującym. list.contains(x): O(N). set.has(x): O(1). Pytanie o przynależność: „czy x znajduje się w tej kolekcji?” Nie dotyczy geometrii przestrzennej.
MOAD-0007 fix: zastąp liniowe przeszukiwanie przestrzenne indeksem przestrzennym (BVH, octree, k-d tree, R-tree). Pytanie przestrzenne: „które obiekty w tej kolekcji przecinają ten promień/sferę/frustum?” Wymagana jest bliskość przestrzenna.
Zbiór haszujący odpowiada na pytanie o przynależność: „czy ten dokładny obiekt jest obecny?” O(1). Nie może odpowiedzieć na pytanie o bliskość: „które obiekty znajdują się w pobliżu tego promienia?” Zbiór haszujący nie ma pojęcia odległości ani zasięgu przestrzennego. Haszowanie odrzuca geometrię równie skutecznie jak skan liniowy.
BVH odpowiada na pytanie o bliskość: „które obiekty mieszczą się w tym zapytaniu przestrzennym?” O(log N + k). Organizuje obiekty według położenia, dzięki czemu zapytania o bliskość pomijają obiekty odległe geometrycznie.
| Pytanie | Poprawna struktura | Niepoprawna struktura |
|---|---|---|
| Czy obiekt X znajduje się w tym zbiorze? | HashSet (O(1)) | Lista liniowa (O(N)) |
| Które obiekty przecinają ten promień? | BVH/octree/k-d tree (O(log N)) | Skan liniowy LUB HashSet (O(N) lub O(N)) |
MOAD-0001 & MOAD-0007: obie operacje O(N) zastąpione czymś szybszym. Różne struktury wymagane, ponieważ pytania się różnią.
Kiedy budować, kiedy pominąć
Budowanie BVH kosztuje O(N log N). Zapytanie kosztuje O(log N + k). Punkt równowagi: gdy liczba zapytań przewyższa liczbę budów na tyle, że oszczędności na zapytaniach przewyższają koszt budowy.
Przy N=100: skan liniowy trwa mikrosekundy. Budowa BVH dodaje narzut. Pomiń BVH.
Przy N=10 000 przy 60 Hz: skan liniowy dominuje budżet klatki. Zapytania BVH kosztują 1/1000 skanu liniowego. Zbuduj BVH raz; wykonuj zapytania 60 razy na sekundę. Punkt równowagi osiągnięty przed pierwszą klatką.
Zasada: buduj, gdy N * Q > N log N, gdzie Q = liczba zapytań na cykl przebudowy. Dla interaktywnych scen 3D: Q = 60 na sekundę, próg N = kilkaset obiektów.
Diagnozuj i napraw scenę 3D
Aplikacja wizualizacji 3D renderuje 5000 obiektów geometrycznych. Obsługa najechania myszką uruchamia się 60 razy na sekundę. Przy każdym zdarzeniu najechania wywołuje scene.intersectObjects(ray, objects), które iteruje po wszystkich 5000 obiektach i testuje każdy względem promienia. Częstotliwość klatek spadła z 60 fps do 8 fps.
Członek zespołu sugeruje: 'Umieść wszystkie obiekty w Set dla wyszukiwania O(1).'