#️⃣ Просторове хешування: пошук найближчих сусідів за O(1) для симуляцій частинок

Наївна проблема O(n²)

Для n частинок наївний пошук усіх пар у межах відстані h вимагає n(n-1)/2 перевірок відстані. Для n = 1000 це 499 500 перевірок. Для n = 10 000 — 50 мільйонів. При 60 fps на кожен кадр припадає близько 16 мс — 50 мільйонів обчислень відстані (кожне з яких — це квадратний корінь або щонайменше три множення та одне додавання) займуть сотні мілісекунд. Симуляція застрягає на рівні менше 10 fps.

Ключове спостереження полягає в тому, що частинки взаємодіють лише в межах радіуса h. Якщо ми можемо швидко знайти, які частинки перебувають у межах відстані h від заданої частинки, не перевіряючи всі інші, ми можемо зменшити обсяг роботи з O(n²) до O(n·k), де k — середня кількість сусідів, зазвичай невелика константа (5–50 для типових симуляцій SPH).

Підхід із сіткою: просторовий поділ

Розділіть область симуляції на сітку з розміром комірки, що дорівнює радіусу взаємодії h. Частинка в позиції (x, y) належить комірці (⌊x/h⌋, ⌊y/h⌋). Оскільки частинки взаємодіють лише в межах відстані h, будь-яка частинка, що взаємодіє з частинкою в комірці (cx, cy), обов'язково перебуває в одній із 9 сусідніх комірок (у 2D) — самій комірці плюс 8 навколишніх. У 3D це 27 комірок.

Якщо сітка має G = (W/h) × (H/h) комірок (для симуляційного поля W × H), а n частинок розподілені приблизно рівномірно, кожна комірка в середньому містить близько n/G частинок. Перегляд 9 комірок із n/G частинок у кожній коштує O(9 · n/G) = O(n · h²/(WH)) роботи — пропорційно частці площі, покритій радіусом взаємодії.

Просторове хешування: без виділення сітки

Фіксована сітка вимагає виділення W/h × H/h комірок — це прийнятно для відомих розмірів області, але марнотратно, якщо частинки скупчуються в невеликій зоні або область велика. Просторове хешування уникає явної сітки, хешуючи координати комірок у плаский масив фіксованого розміру:

class SpatialHash {
  constructor(cellSize, tableSize) {
    this.cellSize = cellSize;
    this.tableSize = tableSize;
    this.table = new Array(tableSize).fill(null).map(() => []);
  }

  hash(cx, cy) {
    // Великі прості числа для рівномірного розсіювання координат сітки
    return ((cx * 92837111) ^ (cy * 689287499)) % this.tableSize;
  }

  cellCoords(x, y) {
    return [Math.floor(x / this.cellSize), Math.floor(y / this.cellSize)];
  }

  insert(particle) {
    const [cx, cy] = this.cellCoords(particle.x, particle.y);
    const key = this.hash(cx, cy);
    this.table[key].push(particle);
  }

  query(x, y) {
    const [cx, cy] = this.cellCoords(x, y);
    const neighbors = [];
    for (let dx = -1; dx <= 1; dx++) {
      for (let dy = -1; dy <= 1; dy++) {
        const key = this.hash(cx + dx, cy + dy);
        neighbors.push(...this.table[key]);
      }
    }
    return neighbors;
  }
}

Хеш-функція відображає довільні цілочисельні пари (cx, cy) у [0, tableSize). Використання великих взаємно простих чисел запобігає систематичним колізіям між сусідніми комірками. Таблицю необхідно очищати й перебудовувати на кожному кадрі, коли частинки рухаються — очищення всього масиву таблиці займає O(tableSize) часу, тому tableSize варто вибирати як невелике кратне n, а не в експоненційно більшому масштабі.

Проєктування хеш-функції

Колізії хешування (коли різні комірки відображаються в один і той самий слот таблиці) не спричиняють помилок коректності — ми перевіряємо фактичні відстані, щоб відфільтрувати хибні спрацювання — але вони збільшують обсяг роботи. Погана хеш-функція (наприклад, (cx + cy) % tableSize) спричиняє багато колізій між комірками вздовж діагоналей. Добуток великих простих чисел розподіляє координати комірок квазі-випадково по всій таблиці.

Для обчислювальних шейдерів WebGL, де цілочисельна арифметика обмежена, поширена альтернатива — використання єдиного великого цілочисельного ключа key = cx * MAX_Y + cy та зберігання частинок у відсортованому за ключем масиві, що дозволяє двійковий пошук. Це уникає динамічного виділення пам'яті (без масивів JavaScript), що є критично важливим для пам'яті GPU.

Вибір tableSize: за n частинок і середньої кількості сусідів k кожна комірка містить приблизно k/9 частинок. Встановлення tableSize = 2n дає коефіцієнт заповнення 0,5 і прийнятний рівень колізій. Менші таблиці ризикують численними колізіями (у найгіршому випадку деградуючи до O(n²)); більші таблиці марнують пропускну здатність пам'яті під час очищення.

Підхід із префіксною сумою для паралелізму на GPU

Хеш-таблиці JavaScript використовують динамічні масиви й не можуть виконуватися паралельно на GPU. Реалізації на WebGL використовують підхід префіксної суми (сканування):

1. Прохід підрахунку: кожна частинка атомарно збільшує лічильник своєї комірки (обчислювальний шейдер).
2. Префіксна сума: обчислення кумулятивних сум для визначення початкового індексу кожної комірки у відсортованому масиві.
3. Прохід заповнення: запис кожної частинки в слот її комірки у відсортованому масиві з використанням префіксної суми як вказівника запису.
4. Запит: для будь-якої комірки читання частинок з індексу prefixSum[cell] до prefixSum[cell+1].

Це створює ідеально впакований, відсортований за комірками масив частинок — без зв'язних списків, без динамічного виділення, з повністю злитим доступом до пам'яті на GPU. Сам прохід префіксної суми виконується за O(log n) паралельних кроків за допомогою алгоритму паралельного сканування. Загалом повна перебудова просторового хешу коштує O(n) роботи, але лише O(log n) паралельних кроків — практично безкоштовно порівняно з самим обчисленням сусідів.

Просторове хешування проти BVH: коли що використовувати

• Просторове хешування: найкраще для частинок однакового розміру (рівномірний розмір комірки оптимальний), динамічних сцен (перебудова щокадру коштує O(n)), великої кількості частинок (10 тис.–1 млн), рівномірних розподілів. Використовується в SPH-рідинах, піску, зграях боїдів.
• BVH: найкраще для об'єктів різного розміру (BVH адаптується до розмірів об'єктів), статичних або повільно змінюваних сцен (перебудова дорога), запитів на перетин променів, сцен із великими порожніми областями. Використовується в трасуванні променів, фізиці твердого тіла зі складними формами.