Урок · Фізика · Виявлення зіткнень · JavaScript
📅 Липень 2026 ⏱ ≈ 28 хв 🎯 Просунутий рівень

Фізика твердих тіл: SAT та EPA для виявлення зіткнень

Кожен стабільний фізичний рушій — Bullet, PhysX, Rapier — зрештою відповідає на два однакові запитання для будь-якої пари опуклих форм: чи торкаються вони одна одної, і якщо так, наскільки глибоко та вздовж якої нормалі? Теорема розділяючої осі дає швидку відповідь "так/ні" для багатогранників, а GJK разом зі своїм компаньйоном для глибини проникнення EPA узагальнюють цю ідею на довільні опуклі оболонки та закруглені форми. Цей урок будує обидва алгоритми з перших принципів.

1. Опуклі багатогранники та опорні функції

Опуклий багатогранник — це перетин скінченної множини півпросторів, або, еквівалентно, опукла оболонка скінченної множини точок. Усі алгоритми зіткнення опуклих форм у цьому уроці (SAT, GJK, EPA) побудовані на одному примітиві: опорній функції (support function). Для заданого напрямку d функція support(d) повертає вершину форми, найвіддаленішу вздовж d: 

// Опорна функція для опуклої оболонки, збереженої як масив вершин
function support(vertices, d) {
  let best = vertices[0];
  let bestDot = best.x * d.x + best.y * d.y + best.z * d.z;
  for (let i = 1; i < vertices.length; i++) {
    const v = vertices[i];
    const dot = v.x * d.x + v.y * d.y + v.z * d.z;
    if (dot > bestDot) { bestDot = dot; best = v; }
  }
  return best;
}

// Опора різниці Мінковського A ⊖ B: найвіддаленіша точка A
// вздовж d, мінус найвіддаленіша точка B вздовж -d
function supportMinkowski(hullA, hullB, d) {
  const pA = support(hullA, d);
  const negD = { x: -d.x, y: -d.y, z: -d.z };
  const pB = support(hullB, negD);
  return {
    x: pA.x - pB.x,
    y: pA.y - pB.y,
    z: pA.z - pB.z,
    a: pA, b: pB // зберігаємо вихідні точки для відновлення контакту
  };
}

Ключова ідея, яку використовують і SAT, і GJK: дві опуклі форми A та B перетинаються тоді й лише тоді, коли початок координат лежить усередині різниці Мінковського A ⊖ B = { a − b : a ∈ A, b ∈ B }. SAT перевіряє це опосередковано через проєкції на осі; GJK перевіряє це безпосередньо, будуючи симплекс усередині множини різниці.

2. SAT: теорія та вибір осей

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

Проєкційний інтервал множини точок S на вісь n̂: [min, max] = [ min_{p∈S}(p·n̂), max_{p∈S}(p·n̂) ] Тест перекриття для інтервалів [minA,maxA], [minB,maxB]: overlap = min(maxA, maxB) − max(minA, minB) overlap ≤ 0 ⟹ n̂ — розділяюча вісь ⟹ зіткнення немає overlap > 0 для ВСІХ кандидатних осей ⟹ форми перетинаються Вектор мінімального зміщення (MTV): вісь із НАЙМЕНШИМ додатним перекриттям дає одразу контактну нормаль і глибину проникнення.

Бокс має 3 унікальні нормалі граней (3 пари паралельних граней), тому двом OBB потрібні 3 + 3 = 6 осей нормалей граней плюс 3×3 = 9 осей векторних добутків ребер: 15 осей загалом. Це класичний результат, що лежить в основі SAT для OBB-OBB, який використовується у незліченних фізичних рушіях і в колізійному коді ще з часів Nintendo64.

3. SAT для орієнтованих боксів (OBB проти OBB)

Ось повний тест SAT для 3D OBB-проти-OBB, включно з 9 осями векторних добутків ребер, необхідними для контактів ребро-ребро: 

// box = { center, halfExtents: {x,y,z}, axes: [ex, ey, ez] } (одиничні вектори)
function obbSAT(A, B) {
  const axes = [];
  for (const a of A.axes) axes.push(a);
  for (const b of B.axes) axes.push(b);
  for (const a of A.axes)
    for (const b of B.axes) {
      const c = cross(a, b);
      if (length(c) > 1e-6) axes.push(normalize(c)); // пропускаємо паралельні ребра
    }

  let minOverlap = Infinity, mtvAxis = null;
  const d = sub(B.center, A.center);

  for (const axis of axes) {
    const rA = projectedRadius(A, axis);
    const rB = projectedRadius(B, axis);
    const dist = Math.abs(dot(d, axis));
    const overlap = rA + rB - dist;
    if (overlap <= 0) return null; // розділяюча вісь → зіткнення немає
    if (overlap < minOverlap) { minOverlap = overlap; mtvAxis = axis; }
  }
  // нормаль повинна вказувати від A до B
  if (dot(d, mtvAxis) < 0) mtvAxis = negate(mtvAxis);
  return { normal: mtvAxis, depth: minOverlap };
}

// Проєкційний "радіус" OBB на довільну вісь
function projectedRadius(box, axis) {
  return box.halfExtents.x * Math.abs(dot(box.axes[0], axis))
       + box.halfExtents.y * Math.abs(dot(box.axes[1], axis))
       + box.halfExtents.z * Math.abs(dot(box.axes[2], axis));
}
Чому перекриття радіусів, а не проєктовані вершини: для бокса проєкція всіх 8 вершин на вісь завжди центрована відносно проєктованого центру бокса з радіусом Σ hᵢ·|axisᵢ·n̂|. Обчислення таким способом дозволяє уникнути явного проєктування всіх 8 вершин — формула O(1) замість O(вершини).

4. SAT для довільних опуклих оболонок

Для загальних опуклих багатогранників (не лише боксів) нормалі граней беруться з кожної грані, а осі векторних добутків — з кожної пари непаралельних ребер — це O(F₁ + F₂ + E₁·E₂), що цілком прийнятно для типових колізійних сіток (десятки граней), але стає затратним для оболонок з великою кількістю вершин. Тому більшість рушіїв спрощує колізійну геометрію до спрощених опуклих оболонок (≤ 32 вершини), згенерованих офлайн за допомогою quickhull, а GJK/EPA — які взагалі не перелічують осі — залишають для всього, що має багато вершин. 

function hullSAT(hullA, hullB) {
  const axes = [
    ...hullA.faceNormals,
    ...hullB.faceNormals,
    ...edgeCrossAxes(hullA.edges, hullB.edges)
  ];
  let best = { depth: Infinity, normal: null };
  for (const n of axes) {
    const [minA, maxA] = projectHull(hullA.vertices, n);
    const [minB, maxB] = projectHull(hullB.vertices, n);
    const overlap = Math.min(maxA, maxB) - Math.max(minA, minB);
    if (overlap <= 0) return null;
    if (overlap < best.depth) best = { depth: overlap, normal: n };
  }
  return best;
}

5. GJK: відстань між опуклими формами

Алгоритм Gilbert-Johnson-Keerthi (GJK) відповідає на питання "чи перетинаються ці дві опуклі форми?" без перелічування жодних осей — він працює для сфер, капсул і довільних оболонок однаково, тому й замінив SAT як універсальну вузьку фазу у Bullet, PhysX і Box2D. GJK ітеративно будує симплекс (точка, лінія, трикутник, тетраедр) з опорних точок різниці Мінковського, який щоразу наближається до початку координат: 

function gjkIntersect(hullA, hullB) {
  let d = { x: 1, y: 0, z: 0 }; // довільний початковий напрямок
  let simplex = [supportMinkowski(hullA, hullB, d)];
  d = negate(simplex[0]);

  for (let iter = 0; iter < 64; iter++) {
    const p = supportMinkowski(hullA, hullB, d);
    if (dot(p, d) < 0) return { hit: false }; // неможливо досягти початку координат → перетину немає
    simplex.push(p);

    const result = doSimplex(simplex, d); // змінює simplex і напрямок
    if (result.containsOrigin) return { hit: true, simplex };
    d = result.newDirection;
  }
  return { hit: false }; // перевищено бюджет ітерацій (майже вироджений випадок)
}

// doSimplex зводить симплекс до найменшого підсимплекса, що
// залишається найближчим до початку координат, і повертає новий
// напрямок пошуку, перпендикулярний до цього підсимплекса, який
// вказує в бік початку координат.
// Випадок "лінія": напрямок = потрійний добуток у бік початку координат
// Випадок "трикутник": напрямок = нормаль грані або ребро
// Випадок "тетраедр": якщо початок координат усередині всіх 4 граней → containsOrigin
Чому це завершується: кожна нова опорна точка в напрямку d гарантовано просувається до початку координат вздовж d (це саме те, що максимізує "опора"). Якщо вона не перетинає півпростір початку координат, то жодна точка різниці Мінковського не може цього зробити — саме тому працює ранній вихід dot(p, d) < 0.

6. EPA: глибина проникнення із симплекса GJK

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

function epa(hullA, hullB, simplex) {
  let polytope = tetrahedronToFaces(simplex); // 4 трикутні грані, обхід CCW

  for (let iter = 0; iter < 32; iter++) {
    // 1. Знайти грань, найближчу до початку координат
    const closest = findClosestFace(polytope); // { normal, distance, verts }

    // 2. Отримати нову опорну точку в напрямку нормалі цієї грані
    const p = supportMinkowski(hullA, hullB, closest.normal);
    const d = dot(p, closest.normal);

    // 3. Якщо нова точка ледь розширює багатогранник, ми досягли збіжності
    if (d - closest.distance < 1e-5) {
      return { normal: closest.normal, depth: closest.distance,
               points: closest.verts };
    }

    // 4. Інакше розширюємо: видаляємо всі грані, які "бачить" нова
    //    точка, збираємо межу отвору у вигляді ребер, перетріангулюємо
    const { remainingFaces, boundaryEdges } = removeVisibleFaces(polytope, p);
    const newFaces = boundaryEdges.map(edge => makeFace(edge[0], edge[1], p));
    polytope = [...remainingFaces, ...newFaces];
  }
  return null; // перевищено бюджет ітерацій
}
Відстань трикутної грані {v0,v1,v2} до початку координат: n̂ = normalize((v1 − v0) × (v2 − v0)) [спрямована назовні] dist = n̂ · v0 [знакова відстань] Критерій збіжності: support(closest.normal) · n̂ − dist < ε → поверхня багатогранника перебуває в межах ε від істинної межі Мінковського вздовж цієї нормалі, тож відстань ≈ глибина проникнення

Вартість EPA визначається переважно функцією findClosestFace (лінійний прохід по гранях багатогранника, або купа для великих багатогранників) та ростом кількості граней з кожною ітерацією. На практиці 5–15 ітерацій сходяться до точності менше міліметра для типових ігрових сіток.

7. Генерація контактного маніфолду

Однієї нормалі й глибини з SAT або EPA достатньо, щоб розділити дві форми, але стабільний штабель боксів потребує кількох контактних точок на пару — інакше бокс, що лежить на грані, поступово провертатиметься навколо своєї опорної нормалі щокадру. Стандартна техніка — обрізання (clipping): визначити опорну грань (у тіла з найплоскішою гранню, узгодженою з нормаллю) і падаючу грань (у іншого тіла), а потім обрізати ребра падаючої грані боковими площинами опорної грані (поліфонне обрізання Сазерленда-Ходжмена): 

function clipManifold(referenceFace, incidentFace, normal) {
  let points = incidentFace.vertices;
  // Обрізаємо падаючий полігон кожною боковою площиною опорної грані
  for (const sidePlane of sidePlanesOf(referenceFace)) {
    points = clipPolygonAgainstPlane(points, sidePlane);
    if (points.length === 0) return []; // повністю обрізано
  }
  // Залишаємо лише точки, що досі нижче опорної грані (проникають)
  return points
    .filter(p => dot(sub(p, referenceFace.point), normal) <= 0)
    .map(p => ({
      point: p,
      depth: -dot(sub(p, referenceFace.point), normal)
    }));
}
Кешування маніфолду: промислові рушії (наприклад, btPersistentManifold у Bullet) зберігають контактні точки між кадрами, поки пара тіл залишається близько одна до одної, зіставляючи нові результати обрізання зі старими точками за близькістю, щоб імпульси з "теплим стартом" (див. урок про фізичний рушій) залишалися дійсними, а штабелі не "стрибали" щокадру.

8. Числові пастки та стійкість

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

Практичне правило: використовуйте SAT безпосередньо, коли обидві форми — бокси або опуклі оболонки з невеликою кількістю граней: він точний, передбачуваний для розгалужень і дає MTV за один прохід. Звертайтеся до GJK+EPA, коли потрібні сфери, капсули або загальні опуклі оболонки в тому самому шляху коду, оскільки абстракція опорної функції GJK приховує специфічну для форми геометрію за єдиним інтерфейсом.