Просторове хешування для пошуку сусідів за O(1)

Наївний пошук сусідів перевіряє кожну пару частинок: O(N²). Сітка просторового хешування зіставляє 3D-позиції з пласкою хеш-таблицею, використовуючи лише цілочисельну арифметику, що дає в середньому O(1) на запит і уможливлює плавні симуляції зі 100 тис. частинок у реальному часі.

1Основна ідея: комірки та хеш-функція

Світ концептуально поділено на рівномірні комірки розміру h (радіус взаємодії). Кожна 3D-координата зіставляється з цілочисельним індексом комірки, який потім хешується у слот таблиці:

          const h = 0.5; // розмір комірки = радіус взаємодії // 3D-позиція →
          цілочисельні координати комірки function cellOf(x, y, z) { return
          [Math.floor(x / h), Math.floor(y / h), Math.floor(z / h)]; } //
          Цілочисельна комірка → плаский індекс таблиці (великі прості числа
          зменшують кластеризацію колізій) const TABLE = 1 << 20; // 1 млн слотів — має бути степенем 2
          для дешевого модуля const P1 = 73856093, P2 = 19349663, P3 = 83492791;
          function hashCell(cx, cy, cz) { // XOR масштабованих координат — швидко
          і доволі рівномірно return ((cx * P1) ^ (cy * P2) ^ (cz * P3)) &
          (TABLE - 1); }
        

Розмір комірки має дорівнювати радіусу взаємодії h. Запит сусідства 3×3×3 (27 комірок у 3D) тоді гарантує, що кожен потенційний сусід буде знайдений. У 2D це 3×3 = 9 комірок.

2Структура хеш-таблиці — пласкі масиви

Замість JavaScript-об'єктів (повільне виділення пам'яті) використовуйте два цілочисельні масиви — масив лічильників (скільки частинок у кожному слоті) та масив списку частинок (плаский список індексів частинок на слот).

          const N = 100_000; // макс. частинок // Підхід із пласким відсортованим
          списком (найшвидша перебудова щокадру): const cellStart = new Int32Array(TABLE +
          1); // стартовий індекс за префіксною сумою const cellCount = new Int32Array(TABLE);
          // частинок на комірку const sortedIds = new Int32Array(N); // індекси частинок,
          відсортовані за комірками // Альтернативно: ланцюгові кошики (простіше
          оновлювати, трохи повільніша ітерація) const buckets = new
          Array(TABLE).fill(null).map(() => []);
        

3Фаза побудови: розподіл частинок по комірках

          // particles: Float32Array з [x,y,z, ...] із кроком 3 function
          build(particles, n) { // 1. Рахуємо частинки в кожній комірці
          cellCount.fill(0); for (let i = 0; i < n; i++) { const [cx, cy, cz]
          = cellOf(particles[i*3], particles[i*3+1], particles[i*3+2]);
          cellCount[hashCell(cx, cy, cz)]++; } // 2. Префіксна сума → стартовий
          індекс на комірку cellStart[0] = 0; for (let b = 0; b < TABLE; b++) {
          cellStart[b + 1] = cellStart[b] + cellCount[b]; } // 3. Заповнюємо sortedIds
          (стабільний розподіл) const tempCount = new Int32Array(TABLE); //
          робочий лічильник for (let i = 0; i < n; i++) { const [cx, cy, cz] =
          cellOf(particles[i*3], particles[i*3+1], particles[i*3+2]); const slot
          = hashCell(cx, cy, cz); sortedIds[cellStart[slot] + tempCount[slot]] =
          i; tempCount[slot]++; } } // Перебудова щокадру для рухомих частинок
          — час O(N)
        

4Фаза запиту: ітерація по сусідніх комірках

          // Ітеруємо всі частинки в межах радіуса h від точки (qx, qy, qz)
          function query(particles, qx, qy, qz, callback) { const [bcx, bcy,
          bcz] = cellOf(qx, qy, qz); const h2 = h * h; // Перевіряємо сусідство
          3×3×3 (27 комірок) for (let dz = -1; dz <= 1; dz++) { for
          (let dy = -1; dy <= 1; dy++) { for (let dx = -1; dx <= 1; dx++)
          { const slot = hashCell(bcx + dx, bcy + dy, bcz + dz); const start =
          cellStart[slot]; const end = start + cellCount[slot]; for (let k =
          start; k < end; k++) { const j = sortedIds[k]; const rx =
          particles[j*3] - qx; const ry = particles[j*3+1] - qy; const rz =
          particles[j*3+2] - qz; const r2 = rx*rx + ry*ry + rz*rz; if (r2 <
          h2) callback(j, Math.sqrt(r2), rx, ry, rz); } } } } } // Використання: для
          кожної частинки знаходимо її сусідів for (let i = 0; i < N; i++) {
          query(particles, particles[i*3], particles[i*3+1], particles[i*3+2],
          (j, dist) => { // j — індекс сусіда, dist — відстань }); }
        

Колізії хешів (дві комірки зіставляються з одним слотом) спричиняють хибнопозитивних кандидатів — частинки, що хешуються в той самий слот, але перебувають у різних комірках. Точна перевірка відстані r2 < h2 відсіює їх, тож коректність зберігається ціною кількох зайвих кандидатів.

5Щільність рідини SPH із просторовим хешуванням

          // Ядро SPH: poly6 function poly6(r, h) { if (r >= h) return 0;
          const diff = h*h - r*r; return (315 / (64 * Math.PI * h**9)) *
          diff**3; } const mass = 0.02; const densities = new Float32Array(N);
          function computeDensities(particles) { build(particles, N); for (let i
          = 0; i < N; i++) { densities[i] = 0; query(particles,
          particles[i*3], particles[i*3+1], particles[i*3+2], (j, dist) => {
          densities[i] += mass * poly6(dist, h); } ); } } // Без просторового
          хешування: O(N²) = 10^10 операцій для 100 тис. частинок // З просторовим
          хешуванням: O(N·k), де k ≈ 27 × сер_на_комірку ≈ 50..100
        

6Розширення та обмеження

Нерівномірна щільність — для дуже мінливої щільності частинок розгляньте натомість BVH або k-d дерево (просторове хешування найкраще для приблизно рівномірних розподілів).
Кілька радіусів — будуйте окремі хеш-сітки для малих/великих радіусів або завжди використовуйте найбільший із фільтрацією за відстанню.
Просторове хешування на GPU — на GPU використовуйте сортування підрахунком (префіксна сума) у обчислювальних шейдерах / transform feedback. Для WebGPU існують бібліотеки GPUSorting.
Компактне хешування — для розріджених розподілів використовуйте JavaScript Map<number, number[]> — менше пам'яті для розріджених сіток, але повільніша ітерація, ніж у типізованих масивів.

          // Поради з налаштування: // TABLE має бути в 2-4× більшою за N для
          доброго коефіцієнта завантаження (низька частота колізій) // Розмір комірки h має точно
          відповідати радіусу взаємодії // Для 2D (частинки обмежені площиною): запитуємо лише 3×3 = 9
          комірок const TABLE_2D = 1 << 18; // 256 тис. слотів для 2D-симуляції з
          50 тис. частинок function hashCell2D(cx, cy) { return ((cx * P1) ^ (cy *
          P2)) & (TABLE_2D - 1); } // Запитуємо 9 комірок у 2D for (let dy = -1;
          dy <= 1; dy++) { for (let dx = -1; dx <= 1; dx++) { const slot =
          hashCell2D(bcx + dx, bcy + dy); // ... ітеруємо слот } }
        