Boids з нуля на Three.js InstancedMesh

1. Навіщо InstancedMesh

Звичайний Mesh видає один draw call на об'єкт. Для 5000 боїдів це 5000 викликів рендерингу — GPU витрачає більше часу на накладні витрати виклику й зміну стану, ніж на власне трикутники, і частота кадрів обвалюється значно нижче 60 fps. THREE.InstancedMesh рендерить N копій однієї геометрії й матеріалу за один draw call, а дані на копію (позиція, обертання, масштаб, навіть колір) подаються як буфер, що GPU читає для кожного екземпляра. Це той самий механізм geometry instancing, що лежить в основі gl.drawArraysInstanced / gl.drawElementsInstanced у WebGL.

2. Налаштування InstancedMesh

Створіть спільну геометрію та матеріал, потім інстанціюйте InstancedMesh фіксованої ємності. Боїди зазвичай — маленький конус або проста низькополігональна форма «риби», що вказує вздовж +Z.

import * as THREE from "three";

const COUNT = 5000;

const geometry = new THREE.ConeGeometry(0.15, 0.6, 6);
geometry.rotateX(Math.PI / 2); // вказувати вздовж +Z замість +Y

const material = new THREE.MeshStandardMaterial({
  color: 0x60a5fa,
  roughness: 0.4,
  metalness: 0.1,
});

const boidMesh = new THREE.InstancedMesh(geometry, material, COUNT);
boidMesh.instanceMatrix.setUsage(THREE.DynamicDrawUsage); // підказка: оновлюється щокадру
scene.add(boidMesh);

// Багаторазові тимчасові об'єкти — уникайте виділення пам'яті в циклі рендеру
const dummy = new THREE.Object3D();
const targetQuat = new THREE.Quaternion();
const upAxis = new THREE.Vector3(0, 1, 0);

3. Стан боїда та правила Рейнольдса

Кожному боїду потрібні лише позиція та швидкість — орієнтація виводиться зі швидкості щокадру, ніколи не зберігається окремо. Позиції та швидкості живуть у плоских Float32Array для ефективної для кешу ітерації замість масиву об'єктів.

const positions = new Float32Array(COUNT * 3);
const velocities = new Float32Array(COUNT * 3);

for (let i = 0; i < COUNT; i++) {
  positions[i * 3 + 0] = (Math.random() - 0.5) * 40;
  positions[i * 3 + 1] = (Math.random() - 0.5) * 40;
  positions[i * 3 + 2] = (Math.random() - 0.5) * 40;
  const a = Math.random() * Math.PI * 2;
  velocities[i * 3 + 0] = Math.cos(a);
  velocities[i * 3 + 2] = Math.sin(a);
}

const MAX_SPEED = 6, MAX_FORCE = 10;
const SEP_R = 1.2, VIEW_R = 3.5;
const W_SEP = 1.6, W_ALIGN = 1.0, W_COH = 1.0;

4. Просторовий хеш uniform grid

Прямий пошук сусідів — O(N²): 25 мільйонів перевірок відстані за кадр при 5000 боїдах. Uniform grid за координатами клітинки знижує це приблизно до O(N): перебудовуємо хеш щокадру, і кожен боїд перевіряє лише ~27 клітинок навколо себе.

const CELL = VIEW_R; // розмір клітинки = радіус сприйняття
const grid = new Map(); // "x,y,z" -> number[] індексів боїдів

function cellKey(x, y, z) {
  return `${Math.floor(x / CELL)},${Math.floor(y / CELL)},${Math.floor(z / CELL)}`;
}

function rebuildGrid() {
  grid.clear();
  for (let i = 0; i < COUNT; i++) {
    const key = cellKey(positions[i*3], positions[i*3+1], positions[i*3+2]);
    if (!grid.has(key)) grid.set(key, []);
    grid.get(key).push(i);
  }
}

function forEachNeighbor(i, callback) {
  const cx = Math.floor(positions[i*3] / CELL);
  const cy = Math.floor(positions[i*3+1] / CELL);
  const cz = Math.floor(positions[i*3+2] / CELL);
  for (let dx = -1; dx <= 1; dx++)
  for (let dy = -1; dy <= 1; dy++)
  for (let dz = -1; dz <= 1; dz++) {
    const bucket = grid.get(`${cx+dx},${cy+dy},${cz+dz}`);
    if (bucket) for (const j of bucket) if (j !== i) callback(j);
  }
}

5. Побудова матриці екземпляра

Щокадру, після обчислення нових позицій і швидкостей для кожного боїда, треба записати матрицю трансформації 4×4 у буфер екземплярів InstancedMesh. Object3D з Three.js — зручний тимчасовий контейнер: встановіть його position/quaternion/scale, викличте updateMatrix(), потім скопіюйте результат у слот екземпляра.

function writeInstance(i) {
  dummy.position.set(
    positions[i * 3],
    positions[i * 3 + 1],
    positions[i * 3 + 2]
  );
  dummy.quaternion.copy(orientations[i]); // див. розділ 6
  dummy.scale.setScalar(1);
  dummy.updateMatrix();
  boidMesh.setMatrixAt(i, dummy.matrix);
}

// після циклу по всіх боїдах:
boidMesh.instanceMatrix.needsUpdate = true;

6. Плавна орієнтація через Quaternion.slerp

Миттєве встановлення напряму швидкості щокадру спричиняє помітне тремтіння, коли боїд різко повертає — боїд, що миттєво розвертається, обертається на 180° за один кадр. Сферична лінійна інтерполяція (slerp) між попередньою орієнтацією та цільовою орієнтацією, виведеною зі швидкості, згладжує це у природний нахилений поворот.

const orientations = Array.from({ length: COUNT }, () => new THREE.Quaternion());
const TURN_SPEED = 6; // вище = різкіший поворот

function updateOrientation(i, dt) {
  const vx = velocities[i*3], vy = velocities[i*3+1], vz = velocities[i*3+2];
  const speed = Math.hypot(vx, vy, vz);
  if (speed < 1e-4) return; // зберегти попередню орієнтацію, якщо майже нерухомий

  dummy.position.set(0, 0, 0);
  dummy.lookAt(vx / speed, vy / speed, vz / speed);
  targetQuat.copy(dummy.quaternion);

  // сферична інтерполяція до цілі, незалежна від частоти кадрів
  const t = 1 - Math.exp(-TURN_SPEED * dt);
  orientations[i].slerp(targetQuat, t);
}

Використання 1 - exp(-TURN_SPEED * dt) замість фіксованого t зберігає швидкість повороту сталою незалежно від частоти кадрів — поширений трюк експоненційного згладжування, який уникає бага «швидша машина повертає швидше» наївного коду типу lerp(pos, target, 0.1).

7. Повний цикл оновлення

Зібравши все разом: перебудовуємо просторовий хеш, обчислюємо сили розлучення/вирівнювання/зближення для кожного боїда лише по сусідах із сітки, інтегруємо швидкість і позицію, оновлюємо орієнтацію, потім записуємо кожну матрицю екземпляра.

function step(dt) {
  rebuildGrid();

  for (let i = 0; i < COUNT; i++) {
    let sepX=0,sepY=0,sepZ=0;
    let avgVX=0,avgVY=0,avgVZ=0;
    let comX=0,comY=0,comZ=0, n=0;

    forEachNeighbor(i, (j) => {
      const dx = positions[i*3]-positions[j*3];
      const dy = positions[i*3+1]-positions[j*3+1];
      const dz = positions[i*3+2]-positions[j*3+2];
      const d2 = dx*dx + dy*dy + dz*dz;
      if (d2 > VIEW_R*VIEW_R || d2 < 1e-6) return;

      if (d2 < SEP_R*SEP_R) { sepX+=dx/d2; sepY+=dy/d2; sepZ+=dz/d2; }
      avgVX+=velocities[j*3]; avgVY+=velocities[j*3+1]; avgVZ+=velocities[j*3+2];
      comX+=positions[j*3]; comY+=positions[j*3+1]; comZ+=positions[j*3+2];
      n++;
    });

    let ax = sepX*W_SEP, ay = sepY*W_SEP, az = sepZ*W_SEP;
    if (n > 0) {
      ax += (avgVX/n - velocities[i*3]) * W_ALIGN + (comX/n - positions[i*3]) * W_COH;
      ay += (avgVY/n - velocities[i*3+1]) * W_ALIGN + (comY/n - positions[i*3+1]) * W_COH;
      az += (avgVZ/n - velocities[i*3+2]) * W_ALIGN + (comZ/n - positions[i*3+2]) * W_COH;
    }

    // обмежити силу, проінтегрувати швидкість, обмежити швидкість, проінтегрувати позицію
    const fLen = Math.hypot(ax, ay, az) || 1;
    const fScale = Math.min(1, MAX_FORCE / fLen);
    velocities[i*3]   += ax * fScale * dt;
    velocities[i*3+1] += ay * fScale * dt;
    velocities[i*3+2] += az * fScale * dt;

    const vLen = Math.hypot(velocities[i*3], velocities[i*3+1], velocities[i*3+2]) || 1;
    const vScale = Math.min(1, MAX_SPEED / vLen);
    velocities[i*3]   *= vScale;
    velocities[i*3+1] *= vScale;
    velocities[i*3+2] *= vScale;

    positions[i*3]   += velocities[i*3]   * dt;
    positions[i*3+1] += velocities[i*3+1] * dt;
    positions[i*3+2] += velocities[i*3+2] * dt;

    updateOrientation(i, dt);
    writeInstance(i);
  }

  boidMesh.instanceMatrix.needsUpdate = true;
}

8. Примітки щодо продуктивності

• Групуйте прапорець буфера: instanceMatrix.needsUpdate = true треба встановити рівно один раз за кадр після запису всіх екземплярів — ніколи всередині циклу по боїдах, інакше ви завантажите весь буфер N разів.
• Уникайте виділень пам'яті в гарячому циклі: об'єкт dummy Object3D, цільовий кватерніон і рядки ключів сітки треба перевикористовувати, а не створювати заново щокадру — тиск на збирач сміття є найпоширенішою причиною ривків у JS-системах частинок.
• Обмежувальна сфера: викличте boidMesh.computeBoundingSphere() один раз після налаштування (або встановіть frustumCulled = false) — Three.js не може автоматично вивести межі для кожного екземпляра, і некоректний обмежувальний об'єм за замовчуванням може призвести до того, що вся зграя буде зникати й з'являтися у полі зору.
• Колір на екземпляр (опційно): використовуйте InstancedMesh.instanceColor та setColorAt(i, color), щоб фарбувати боїдів за швидкістю чи групою без додаткових draw call.
• Подальше масштабування: понад ~20 000 боїдів перенесіть пошук сусідів та інтегрування у GPU compute pass (compute-шейдер WebGPU або ping-pong текстура у WebGL2) — див. примітку про GPU-паралелізм у статті Алгоритм Боїдів.