🖥️ Компʼютерна графіка · Алгоритми
📅 Квітень 2026⏱ 16 хв🔴 Просунутий рівень

BVH: ієрархія обмежувальних обʼємів для трасування променів та виявлення зіткнень

Рендеринг сцени з мільйонами трикутників через грубий перебір перетинів промінь–трикутник тривав би хвилини на кадр. BVH зводить це до мілісекунд — організовуючи геометрію в дерево вкладених обмежувальних коробок і пропускаючи цілі піддерева тієї ж миті, коли промінь не влучає в їхню коробку. Та сама структура даних забезпечує виявлення зіткнень у реальному часі як в ігрових рушіях, так і у фізично коректних трасувальниках шляху.

1. Проблема прискорення

Трасувальник шляху випускає мільйони променів на кадр. Кожен промінь має знайти найближчий перетин із геометрією сцени. Без прискорення перевірка одного променя проти N трикутників коштує O(N). За N = 10 мільйонів трикутників і 4 мільйони променів на кадр при 60 fps це 2,4 × 10¹⁵ перевірок трикутників на секунду — приблизно у 10⁶× понад можливості сучасного апаратного забезпечення.

Структури прискорення розвʼязують це, відсікаючи великі частини сцени до перевірок окремих трикутників. BVH знижує очікувану вартість променя з O(N) до O(log N) для рівномірно розподілених сцен — сцена з 10 мільйонів трикутників потребує ~23 перевірок обмежувальних коробок плюс жменьку перевірок трикутників на промінь, замість 10 мільйонів.

Альтернативні структури прискорення: kd-дерева розбивають простір гіперплощинами — вони адаптуються до нерегулярної геометрії, але їх важче будувати й обходити на GPU. Рівномірні сітки прості, але марнують памʼять на розріджених сценах. BVH стала домінантною, бо добре адаптується до складної геометрії, ефективна на GPU (когерентний доступ до памʼяті) і відображається безпосередньо на апаратні RT-блоки GPU (RTX, RDNA3 RT, Apple Pro RT).

2. Обмежувальні коробки, вирівняні за осями

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

// Означення AABB struct AABB { vec3 min; // кут із найменшими x, y, z vec3 max; // кут із найбільшими x, y, z }; // Побудова AABB зі списку трикутників AABB computeAABB(Triangle* tris, int count) { AABB box = { +INF, -INF }; for each tri in tris: for each vertex v in tri: box.min = componentMin(box.min, v); box.max = componentMax(box.max, v); return box; } // Обʼєднання двох AABB AABB merge(AABB a, AABB b) { return { componentMin(a.min, b.min), componentMax(a.max, b.max) }; }

Перетин «промінь–AABB» (метод плит)

Перевірка променя проти AABB надзвичайно дешева — 6 ділень і кілька порівнянь — що робить її етапом швидкого відсіювання перед дорогими перевірками трикутників:

// Перетин «промінь–AABB» — метод плит // Промінь: P(t) = origin + t·direction bool rayAABB(Ray ray, AABB box, float tMin, float tMax) { for axis in {x, y, z}: float invD = 1.0 / ray.direction[axis]; float t0 = (box.min[axis] - ray.origin[axis]) * invD; float t1 = (box.max[axis] - ray.origin[axis]) * invD; if (invD < 0) swap(t0, t1); tMin = max(tMin, t0); tMax = min(tMax, t1); if (tMax < tMin) return false; // плита пропущена → коробка не влучена return true; } Вартість: ~12 операцій з рухомою комою (проти ~20–50 для перетину трикутника)

3. Побудова BVH: стратегії

BVH — це бінарне дерево. Кожен внутрішній вузол містить AABB і вказівники на два дочірні вузли. Листові вузли містять один або кілька примітивів. Ключове питання: як розбити множину примітивів на дві групи, щоб сформувати два дочірні вузли?

Медіанне розбиття за центроїдами

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

// Медіанне розбиття (просте, швидке, але субоптимальне за якістю) 1. Знайти AABB усіх центроїдів примітивів. 2. Обрати вісь розбиття = вісь із найбільшою протяжністю. 3. Відсортувати примітиви за центроїдом уздовж осі розбиття. 4. Розбити за медіаною → дві приблизно рівні дочірні множини. Час побудови: O(N log N) для одного рівня (домінує сортування) Повне дерево: O(N log² N) Якість: достатня, але не SAH-оптимальна Типове застосування: швидка перебудова під час анімації, прототипи

Обʼєктне розбиття проти просторового

Обʼєктне розбиття (те, що робить BVH) призначає кожен примітив рівно одному вузлу. Просторове розбиття (kd-дерева) обрізає примітиви на площині розбиття — трикутник, що перетинає межу, потрапляє до обох дочірніх вузлів. Обʼєктне розбиття простіше й уникає дублювання примітивів; просторове може бути щільнішим для великих трикутників.

4. Евристика площі поверхні (SAH)

Евристика площі поверхні обирає розбиття, що мінімізує очікувану вартість влучання випадкового променя у вузол. Вона використовує геометричний факт, що ймовірність влучання випадкового променя у опуклий обʼєкт пропорційна його площі поверхні (для рівномірно розподілених променів в обмежувальній сфері).

// Модель вартості SAH для розбиття вузла N на дочірні L і R SAH cost = C_traverse // вартість обходу + (SA(L)/SA(N)) × N_L × C_intersect // очікувана вартість лівого дочірнього + (SA(R)/SA(N)) × N_R × C_intersect // очікувана вартість правого дочірнього SA(X) = площа поверхні AABB множини X N_L = кількість примітивів у лівому дочірньому N_R = кількість примітивів у правому дочірньому C_traverse ≈ 1–2 (відносно C_intersect = 1) Оптимальне розбиття мінімізує цю вартість серед усіх кандидатних позицій розбиття. Пошук SAH (наближення з кошиками): поділити діапазон центроїдів на K=32 кошики вздовж кожної осі. Для кожної межі кошика (3 осі × 31 розбиття = 93 кандидатні розбиття): обчислити N_L, SA(L), N_R, SA(R) за прохід O(N). Обрати розбиття з мінімальною вартістю SAH. Загальна вартість побудови: O(N log N) — порівнянна з медіанним розбиттям Якість: у 2–3× менше відвідувань вузлів на промінь, ніж у медіанного розбиття

SAH із кошиками (Вальд, 2007) — стандарт у промислових рендерерах. Вона наближає точний оптимум SAH (який потребує O(N log N) на рівень) майже з тією самою якістю, використовуючи лише K=32 кошики. Embree, Optix і практично всі промислові трасувальники шляху використовують SAH із кошиками або її варіанти.

Завершення на листку

Рекурсія зупиняється, коли вузол має ≤ N_leaf примітивів (зазвичай 1–4 трикутники). Менші листки покращують якість обходу (менше хибних спрацювань), але збільшують кількість вузлів і памʼять. Установлення N_leaf = 4 і використання 4-широкого SIMD для одночасної перевірки всіх 4 трикутників — поширена оптимізація у CPU-рендерерах (пакетне трасування).

5. Обхід «промінь–BVH»

Маючи промінь і корінь BVH, знайти найближчий перетин. Стандартний алгоритм використовує стек, щоб уникнути рекурсії (зручно для GPU):

// Ітеративний обхід BVH зі стеком Hit traverse(Ray ray, BVH bvh) { int stack[64]; int top = 0; stack[top++] = 0; // почати з кореневого вузла Hit bestHit = MISS; float tBest = +INF; while (top > 0) { BVHNode node = bvh.nodes[stack[--top]]; if (node.isLeaf) { for each primitive in node.leaf: Hit h = intersect(ray, primitive); if (h.t < tBest) { bestHit = h; tBest = h.t; } } else { // Перевірити обидва дочірні; покласти ближчий ОСТАННІМ (його знімуть першим) float tL, tR; bool hitL = rayAABB(ray, bvh.nodes[node.left].aabb, 0, tBest, &tL); bool hitR = rayAABB(ray, bvh.nodes[node.right].aabb, 0, tBest, &tR); if (hitL && hitR) { // Покласти дальший дочірній першим (щоб ближчий був зверху) if (tL < tR) { stack[top++] = node.right; stack[top++] = node.left; } else { stack[top++] = node.left; stack[top++] = node.right; } } else if (hitL) stack[top++] = node.left; else if (hitR) stack[top++] = node.right; } } return bestHit; }

Порядок «спершу ближчий дочірній» критичний для продуктивності: відвідуючи ближчий дочірній першим, tBest оновлюється до меншого значення раніше, що дозволяє агресивніше відсікати AABB дальших дочірніх («ранній вихід із тіснішим t»).

Пакетний та SIMD-обхід

CPU-рендерери перевіряють 4 або 8 променів паралельно («пакет променів») за допомогою SSE/AVX SIMD. Усі промені в пакеті спільно використовують той самий стек обходу, поки вони йдуть тим самим шляхом крізь BVH — «відсікання за пірамідою видимості» в кожному вузлі за спільною обмежувальною пірамідою пакета. Розбіжні пакети повертаються до індивідуального обходу. Це дає прискорення у 2–4× на когерентних променях (первинних променях із камери), але менший виграш на розсіяних вторинних променях.

6. BVH на GPU: LBVH з кодами Мортона

Побудова за SAH на CPU (згори донизу, послідовна) надто повільна для динамічних сцен, які потребують перебудови щокадру. Лінійна BVH (LBVH) будує дерево знизу вгору із сортування за кодами Мортона за ~5–20 мс на GPU — достатньо швидко для скелетної анімації чи систем частинок у реальному часі.

// Огляд побудови LBVH Крок 1: обчислити код Мортона для кожного центроїда примітива Нормувати центроїд до [0,1]³ Переплести біти координат x, y, z → 30-бітовий або 63-бітовий цілочисловий код Мортона впорядковує примітиви за Z-кривою у 3D-просторі z_order(0.5, 0.5, 0.5) = 0b 101010101010... (переплетені біти) Крок 2: відсортувати примітиви за кодом Мортона [порозрядне сортування O(N) на GPU] Крок 3: побудувати бінарне порозрядне дерево знизу вгору Кожен внутрішній вузол розбивається на найстаршому відмінному біті у своєму діапазоні. Паралельна побудова: кожен потік обробляє один внутрішній вузол. O(N) вузлів будується за O(log N) паралельних проходів. Крок 4: переобчислити AABB знизу вгору [один атомарний min/max на батьківський вузол листка] Загальний час на GPU: ~5–20 мс для 1М трикутників (проти 200–500 мс для SAH на CPU)

Якість LBVH нижча за SAH — дерева, впорядковані за Мортоном, можуть мати погані розбиття, коли примітиви скупчуються, — але будуються у 20–50× швидше. HLBVH (ієрархічна LBVH) використовує розбиття за SAH для верхніх рівнів дерева та LBVH для піддерев, поєднуючи швидкість побудови з доброю якістю обходу.

Алгоритм Карраса 2012: повністю паралельний алгоритм побудови LBVH (Каррас, NVidia, «Maximising Parallelism in the Construction of BVHs, Octrees, and k-d Trees») є основою побудовника BVH на GPU в Optix. Кожен із N−1 внутрішніх вузлів призначається одному GPU- потоку, що визначає свою точку розбиття за відмінностями бітів коду Мортона — без послідовних залежностей між вузлами.

7. TLAS / BLAS у сучасних RT-API

DirectX Raytracing (DXR), Vulkan Ray Tracing та Metal RT використовують дворівневу структуру BVH, що відокремлює геометричні деталі від перетворень екземплярів:

Дворівнева структура прискорення: BLAS (структура прискорення нижнього рівня): - одна на кожну унікальну сітку/геометрію - містить усі трикутники сітки в локальному просторі обʼєкта - будується одноразово (статична) або періодично (анімована) - драйвер зберігає у GPU-оптимальному форматі (непрозорому для рендерера) TLAS (структура прискорення верхнього рівня): - єдине дерево для всієї сцени - кожен листок посилається на один BLAS + матрицю світового перетворення 4×3 - перебудовується щокадру, коли екземпляри рухаються (швидко, лише N_instances вузлів) - промінь спершу трасується проти TLAS; при влучанні перетворює промінь в обʼєктний простір і продовжує обхід у вказаний BLAS Перевага: 1000 ідентичних дерев → 1 BLAS, 1000 листків TLAS Без інстансування: 1000 × N_triangles в одному плоскому BVH Інстансування економить у 1000× памʼять BLAS і вартість перебудови

У DXR BuildRaytracingAccelerationStructure() приймає дескриптор D3D12_BUILD_RAYTRACING_ACCELERATION_STRUCTURE_INPUTS, що задає списки геометрії (для BLAS) або дескриптори екземплярів (для TLAS). Драйвер опрацьовує всі внутрішні деталі формату BVH, сортування за Мортоном і SAH — застосунок лише надає геометрію та екземпляри.

Оновлення проти перебудови

BLAS можна оновити (переобчислити без структурних змін) значно швидше, ніж перебудувати з нуля. Оновлення коректне, коли вершини зміщуються незначно (анімація), але якість погіршується зі зростанням руху. Евристика: використовувати оновлення, якщо зміщення вершин < 10% від розміру примітива; інакше перебудовувати. Переобчислення на RTX 4090: ~0,5 мс для 1М трикутників; перебудова: ~5 мс.

8. BVH для виявлення зіткнень

Ігрові рушії використовують дерева AABB (варіант BVH) для широкофазного виявлення зіткнень — швидкого пошуку пар обʼєктів, які можуть зіштовхуватися, перед запуском дорогих вузькофазних геометричних перевірок (GJK, EPA).

// Широкофазне виявлення зіткнень за BVH // Запит: знайти всі обʼєкти, чиї AABB перетинаються з AABB запиту void queryOverlap(BVHNode node, AABB query, List<int>& results) { if (!aabbOverlap(node.aabb, query)) return; // обрізати піддерево if (node.isLeaf) { results.push(node.objectID); return; } queryOverlap(node.left, query, results); queryOverlap(node.right, query, results); } // Складність: O(log N + K), де K = кількість обʼєктів, що перетинаються // Для N=10000 обʼєктів за типової щільності сцени: K≈4 у середньому // проти грубого перебору: O(N²/2) = 50М перевірок

Динамічна BVH (DBVH)

В ігровій фізиці обʼєкти рухаються щокадру. Перебудовувати повну BVH щокадру марнотратно — натомість динамічна BVH використовує «товсті» AABB (розширені «полем» у кожному напрямку) і ліниве переобчислення:

Bullet Physics і Box2D використовують динамічне дерево AABB (підтримуване інкрементно) для широкої фази. Вартість оновлення на один переміщений обʼєкт — O(log N) амортизовано, що значно краще за повні перебудови.

Вибір обмежувальних обʼємів, окрім AABB

BVH у промисловості: Embree (Intel, відкритий код) — це еталон BVH для CPU — використовується в Blender Cycles, Arnold і Corona. Optix (NVIDIA) надає BVH на GPU, побудовану поверх апаратного RTX. PBRT-v4 містить чисту навчальну реалізацію BVH. Для трасування шляху у WebGL уся BVH має бути серіалізована в текстури й обходитися у GLSL — плоске представлення масивом з індексною навігацією замість вказівників.