Аналогія з Плоскоземеллям
«Плоскоземелля» Едвіна Еббота (1884): мешканці двовимірної площини. Вони сприймають довжину та ширину. Глибина — третій вимір над ними — для них невидима. Вони не можуть її сприймати, не можуть використовувати, не можуть будувати з нею. Геометрія їхнього світу містить вимір, який вони структурно відкидають.
MOAD-0007 працює так само. Об’єкти в 3D-просторі мають позицію, обертання та обмежувальний об’єм — багату геометричну структуру. Лінійне сканування розглядає їх як плоский список. Просторова структура присутня, але не використовується, відкидається. Кожна перевірка перетину сканує весь список, ніби об’єкти не мали геометрії та позиції.
Приклад Three.js
Three.js Raycaster.intersectObjects(): заданий промінь (позиція та напрямок у 3D-просторі), знайти всі об’єкти, з якими промінь перетинається. Реалізація: перебрати всі N об’єктів сцени, перевірити кожен на перетин з променем. O(N) за виклик.
Обробник події наведення викликає intersectObjects() один раз за кадр при 60 кадрах на секунду. При N=100 об’єктів: 6000 тестів перетину за секунду. При N=10 000 об’єктів: 600 000 тестів за секунду. Вартість: пропорційна N, а не кількості об’єктів, з якими промінь реально перетинається.
При N=100: непомітно. Бюджет кадру (16,7 мс при 60 fps) поглинає витрати без проблем.
При N=10 000: домінує. 600 000 тестів перетину за секунду навантажують головний потік. Частота кадрів падає. Сцена, яка працювала при N=100, непомітно ламається, коли N перевищує поріг.
Структура, яку відкидає лінійне сканування
Об’єкти займають позиції в просторі. Об’єкт у позиції (1000, 0, 0) не може перетинатися з променем, спрямованим у бік (-1, 0, 0) з позиції (0, 0, 0): об’єкт лежить у протилежному напрямку. Лінійне сканування все одно перевіряє його.
Об’єкти мають обмежувальні об’єми: сферу або коробку, що охоплює весь об’єкт. Промінь, який не перетинає обмежувальний об’єм об’єкта, не може перетинатися з самим об’єктом. Лінійне сканування все одно виконує повну перевірку перетину.
Геометрія визначає, які об’єкти можна пропустити. Лінійне сканування ігнорує геометрію. Це і є відкидання.
Що означає «Відкидання структури»
Аналогія Flatland: мешканці Еббота не могли сприймати глибину. Дефект Flatland відкидає геометричну структуру, яка існує в даних, але ніколи не потрапляє в алгоритм.
Чому хеш-набір не може виправити MOAD-0007
MOAD-0001 fix: замінити послідовну перевірку членства на хеш-набір. list.contains(x): O(N). set.has(x): O(1). Питання членства: «чи є x у цій колекції?» Просторова геометрія не задіяна.
MOAD-0007 fix: замінити лінійне просторове сканування на просторовий індекс (BVH, octree, k-d tree, R-tree). Просторове питання: «які об’єкти цієї колекції перетинають цей промінь/сферу/фрустум?» Потрібна просторова близькість.
Хеш-набір відповідає на питання членства: «чи присутній цей точний об’єкт?» O(1). Він не може відповісти на питання близькості: «які об’єкти поблизу цього променя?» Хеш-набір не має поняття відстані чи просторового обсягу. Хешування відкидає геометрію так само повністю, як і лінійне сканування.
BVH відповідає на питання близькості: «які об’єкти потрапляють у цей просторовий запит?» O(log N + k). Він організовує об’єкти за позицією, тому запити близькості пропускають геометрично віддалені об’єкти.
| Питання | Правильна структура | Неправильна структура |
|---|---|---|
| Чи є об’єкт X у цьому наборі? | HashSet (O(1)) | Лінійний список (O(N)) |
| Які об’єкти перетинають цей промінь? | BVH/octree/k-d tree (O(log N)) | Лінійне сканування АБО HashSet (O(N) або O(N)) |
MOAD-0001 та MOAD-0007: обидві операції O(N) замінено на щось швидше. Потрібні різні структури, бо питання відрізняються.
Коли будувати, коли пропустити
Побудова BVH коштує O(N log N). Запити коштують O(log N + k). Точка беззбитковості: коли кількість запитів значно перевищує кількість побудов, а економія на запитах перевищує вартість побудови.
При N=100: лінійний скан займає мікросекунди. Побудова BVH додає накладні витрати. Пропустіть BVH.
При N=10 000 та 60 Гц: лінійний скан поглинає весь бюджет кадру. Запити BVH коштують у 1/1000 від часу лінійного скану. Побудуйте BVH один раз і виконуйте 60 запитів на секунду. Точка беззбитковості досягається ще до першого кадру.
Правило: будуйте, коли N * Q > N log N, де Q = кількість запитів за цикл перебудови. Для інтерактивних 3D-сцен: Q = 60 на секунду, поріг N — кілька сотень об’єктів.
Діагностика та виправлення 3D-сцени
3D-візуалізаційна програма рендерить 5000 геометричних об’єктів. Обробник наведення спрацьовує 60 разів на секунду. При кожній події наведення викликається scene.intersectObjects(ray, objects), який перебирає всі 5000 об’єктів і перевіряє кожен на перетин з променем. Частота кадрів впала з 60 fps до 8 fps.
Колега пропонує: «Помістіть усі об’єкти у Set для O(1) пошуку».