BVH-дерево

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Приклад ієрархії обмежувальних об'ємів із використанням прямокутників як обмежувальних об'ємів.

Ієрархія обмеженого об'єму (BVH) — це деревовидна структура на множині геометричних об'єктів. Усі геометричні об'єкти, що утворюють листкові вузли дерева, загорнуті в обмежувальні об'єми. Ці вузли потім групуються, як невеликі набори і укладаються в більші обмежувальні обсяги. Вони, у свою чергу, також групуються та укладаються в інші більші обмежувальні обсяги рекурсивним способом, що в кінцевому підсумку призводить до структури дерева з єдиним обмежуючим обсягом у верхній частині дерева. Ієрархії обмежувальних об'ємів використовуються для ефективної підтримки кількох операцій над наборами геометричних об'єктів, наприклад, при виявленні зіткнень і трасуванні променів.

Хоча обгортання об'єктів у обмежувальні об'єми та виконання тестів на зіткнення для них перед тестуванням самої геометрії об'єкта спрощує тести та може призвести до значного покращення продуктивності, така ж кількість попарних тестів між обмежуючими об'ємами все ще виконується. Якщо впорядкувати обмежувальні об'єми в ієрархію, часову складність (кількість виконаних тестів) можна зменшити до логарифмічної кількості об'єктів. З такою ієрархією під час тестування, якщо батьківські об'єми не перетинаються (наприклад, якщо обмежувальні об'єми двох бамперних автомобілів не перетинаються, обмежувальні об'єми самих бамперів не потрібно перевіряти на зіткнення), то об'єми-нащадки не потрібно перевіряти на перетин.

Проблеми вибору BVH[ред. | ред. код]

Вибір граничного обсягу визначається компромісом між двома цілями. З одного боку, ми хотіли б використовувати обмежувальні об'єми, які мають дуже просту форму. Таким чином, нам потрібно лише кілька байтів для їх зберігання, а тести перетину[en] та обчислення відстані прості, та швидкі. З іншого боку, ми хотіли б мати обмежувальні обсяги, які дуже щільно підходять до відповідних об'єктів даних. Одним з найбільш часто використовуваних обмежувальних об'ємів є мінімальна обмежувальна коробка, вирівняна по осі, тобто, її грані паралельні координатним осям. Мінімальний обмежувальний прямокутник, вирівняний по осі, для заданої множини об'єктів легко обчислити, йому потрібно лише кілька байтів пам'яті, а надійні тести перетину реалізуються легко та надзвичайно швидко.

Існує кілька бажаних властивостей BVH, які слід враховувати при проектуванні для конкретного застосування:[1]

  • Вузли, що містяться в будь-якому даному піддереві, повинні бути поруч один з одним. Чим нижче по дереву, тим ближче повинні бути вузли один до одного.
  • Кожен вузол в BVH повинен мати мінімальний об'єм.
  • Сума всіх обмежених об'ємів повинна бути мінімальною.
  • Більшу увагу слід приділяти вузлам біля кореня BVH. Зріз вузла біля кореня дерева вилучає більше об'єктів з подальшого розгляду.
  • Об'єм перекриття однотипних вузлів повинен бути мінімальним.
  • BVH має бути збалансованим, як за структурою вузла, так і за змістом. Балансування дозволяє зрізати якомога більшу частину BVH, коли гілка не проходить.

З точки зору структури BVH, необхідно вирішити, який ступінь (кількість нащадків) і висоту використовувати в дереві, що представляє BVH. Дерево низького ступеня буде більшої висоти. Це збільшує час проходження від кореня до листя. З іншого боку, на кожному відвідуваному вузлі потрібно витрачати менше роботи, щоб перевірити його дочірні елементи на перекриття. Для дерева високого ступеня справедливо протилежне: хоча дерево буде меншої висоти, на кожен вузол витрачається більше роботи. На практиці двійкові дерева (ступінь = 2) є найбільш поширеними. Однією з основних причин є те, що двійкові дерева легше будувати.[2]

Побудова[ред. | ред. код]

Існує три основні категорії методів побудови дерева: зверху вниз, знизу вгору та методи вставки.

Методи зверху вниз розбивають вхідний набір на дві (або більше) підмножини, обмежуючи їх у вибраному обмежувальному обсязі, а потім продовжують розбивати (і обмежувати) рекурсивно, поки кожна підмножина не буде складатися лише з одного примітиву (досягаються листові вузли). Методи «зверху вниз» прості в реалізації, швидкі в побудові та, безумовно, найпопулярніші, але загалом не призводять до найкращих можливих дерев.

Методи знизу вгору починаються з вхідного набору у вигляді листків дерева, а потім групують два (або більше) з них, щоб утворити новий (внутрішній) вузол, продовжують таким же чином, поки все не буде згруповано під одним вузлом (корінь дерева). Методи «знизу вгору» складніше реалізувати, але загалом, ймовірно, виростуть кращі дерева. Деякі нещодавні дослідження (наприклад[3]) вказують на те, що в низьковимірному просторі швидкість побудови можна значно підвищити (що відповідає або перевершує підходи зверху вниз) шляхом сортування об'єктів за допомогою кривої заповнення простору[en] та застосування приблизного кластеризації на основі цього послідовний порядок.

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

Використання[ред. | ред. код]

BVH часто використовуються в трасуванні променів для усунення потенційних кандидатів на перетин у сцені, пропускаючи геометричні об'єкти, розташовані в обмежуючих обсягах, які не перетинаються поточним променем.[4] Крім того, як поширена оптимізація продуктивності, коли цікавить лише найближче перетин променя, оскільки алгоритм обходу променів є низхідними вузлами, а кілька дочірніх вузлів перетинають промінь, алгоритм обходу спочатку розглядатиме ближчий об'єм, і якщо він знайде перехрестя там, яке остаточно ближче, ніж будь-яке можливе перетин у другому (або іншому) томі (тобто томи не перекриваються), він може безпечно ігнорувати другий том. Подібні оптимізації під час обходу BVH можна використовувати при спуску до дочірніх томів другого тому, щоб обмежити подальший простір пошуку і таким чином зменшити час обходу.

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

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

BVH також можна поєднувати з методами графіка сцени та екземпляром геометрії[en], щоб зменшити використання пам'яті, покращити оновлення структури та повну продуктивність перебудови, а також покращити розбивку об'єктів або примітивів.

Див. також[ред. | ред. код]

Посилання[ред. | ред. код]

  1. ↑ Ericson, Christer (2005). §6.1 Hierarchy Design Issues. Real-Time collision detection. Morgan Kaufmann Series in Interactive 3-D Technology. Morgan Kaufmann. с. 236—7. ISBN 1-55860-732-3.
  2. ↑ (Ericson, 2005, с. 238)
  3. ↑ Gu, Yan; He, Yong; Fatahalian, Kayvon; Blelloch, Guy (2013). Efficient BVH Construction via Approximate Agglomerative Clustering (PDF). HPG '13: Proceedings of the 5th High-Performance Graphics Conference. ACM. с. 81—88. CiteSeerX 10.1.1.991.3441. doi:10.1145/2492045.2492054. ISBN 9781450321358. S2CID 2585433.
  4. ↑ Günther, J.; Popov, S.; Seidel, H.-P.; Slusa⅘dllek, P. (2007). Realtime Ray Tracing on GPU with BVH-based Packet Traversal. 2007 IEEE Symposium on Interactive Ray Tracing. IEEE. с. 113—8. CiteSeerX 10.1.1.137.6692. doi:10.1109/RT.2007.4342598. ISBN 978-1-4244-1629-5. S2CID 2840180.

Посилання[ред. | ред. код]

Отримано з https://uk.wikipedia.org/w/index.php?title=BVH-дерево&oldid=38458301