Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Ієрархія обмеженого об'єму (BVH) — це деревовидна структура на множині геометричних об'єктів. Усі геометричні об'єкти, що утворюють листкові вузли дерева, загорнуті в обмежувальні об'єми. Ці вузли потім групуються, як невеликі набори і укладаються в більші обмежувальні обсяги. Вони, у свою чергу, також групуються та укладаються в інші більші обмежувальні обсяги рекурсивним способом, що в кінцевому підсумку призводить до структури дерева з єдиним обмежуючим обсягом у верхній частині дерева. Ієрархії обмежувальних об'ємів використовуються для ефективної підтримки кількох операцій над наборами геометричних об'єктів, наприклад, при виявленні зіткнень і трасуванні променів.
Хоча обгортання об'єктів у обмежувальні об'єми та виконання тестів на зіткнення для них перед тестуванням самої геометрії об'єкта спрощує тести та може призвести до значного покращення продуктивності, така ж кількість попарних тестів між обмежуючими об'ємами все ще виконується. Якщо впорядкувати обмежувальні об'єми в ієрархію, часову складність (кількість виконаних тестів) можна зменшити до логарифмічної кількості об'єктів. З такою ієрархією під час тестування, якщо батьківські об'єми не перетинаються (наприклад, якщо обмежувальні об'єми двох бамперних автомобілів не перетинаються, обмежувальні об'єми самих бамперів не потрібно перевіряти на зіткнення), то об'єми-нащадки не потрібно перевіряти на перетин.
Проблеми вибору BVH
Вибір граничного обсягу визначається компромісом між двома цілями. З одного боку, ми хотіли б використовувати обмежувальні об'єми, які мають дуже просту форму. Таким чином, нам потрібно лише кілька байтів для їх зберігання, а [en] та обчислення відстані прості, та швидкі. З іншого боку, ми хотіли б мати обмежувальні обсяги, які дуже щільно підходять до відповідних об'єктів даних. Одним з найбільш часто використовуваних обмежувальних об'ємів є мінімальна обмежувальна коробка, вирівняна по осі, тобто, її грані паралельні координатним осям. Мінімальний обмежувальний прямокутник, вирівняний по осі, для заданої множини об'єктів легко обчислити, йому потрібно лише кілька байтів пам'яті, а надійні тести перетину реалізуються легко та надзвичайно швидко.
Існує кілька бажаних властивостей BVH, які слід враховувати при проектуванні для конкретного застосування:
- Вузли, що містяться в будь-якому даному піддереві, повинні бути поруч один з одним. Чим нижче по дереву, тим ближче повинні бути вузли один до одного.
- Кожен вузол в BVH повинен мати мінімальний об'єм.
- Сума всіх обмежених об'ємів повинна бути мінімальною.
- Більшу увагу слід приділяти вузлам біля кореня BVH. Зріз вузла біля кореня дерева вилучає більше об'єктів з подальшого розгляду.
- Об'єм перекриття однотипних вузлів повинен бути мінімальним.
- BVH має бути збалансованим, як за структурою вузла, так і за змістом. Балансування дозволяє зрізати якомога більшу частину BVH, коли гілка не проходить.
З точки зору структури BVH, необхідно вирішити, який ступінь (кількість нащадків) і висоту використовувати в дереві, що представляє BVH. Дерево низького ступеня буде більшої висоти. Це збільшує час проходження від кореня до листя. З іншого боку, на кожному відвідуваному вузлі потрібно витрачати менше роботи, щоб перевірити його дочірні елементи на перекриття. Для дерева високого ступеня справедливо протилежне: хоча дерево буде меншої висоти, на кожен вузол витрачається більше роботи. На практиці двійкові дерева (ступінь = 2) є найбільш поширеними. Однією з основних причин є те, що двійкові дерева легше будувати.
Побудова
Існує три основні категорії методів побудови дерева: зверху вниз, знизу вгору та методи вставки.
Методи зверху вниз розбивають вхідний набір на дві (або більше) підмножини, обмежуючи їх у вибраному обмежувальному обсязі, а потім продовжують розбивати (і обмежувати) рекурсивно, поки кожна підмножина не буде складатися лише з одного примітиву (досягаються листові вузли). Методи «зверху вниз» прості в реалізації, швидкі в побудові та, безумовно, найпопулярніші, але загалом не призводять до найкращих можливих дерев.
Методи знизу вгору починаються з вхідного набору у вигляді листків дерева, а потім групують два (або більше) з них, щоб утворити новий (внутрішній) вузол, продовжують таким же чином, поки все не буде згруповано під одним вузлом (корінь дерева). Методи «знизу вгору» складніше реалізувати, але загалом, ймовірно, виростуть кращі дерева. Деякі нещодавні дослідження (наприклад) вказують на те, що в низьковимірному просторі швидкість побудови можна значно підвищити (що відповідає або перевершує підходи зверху вниз) шляхом сортування об'єктів за допомогою [en] та застосування приблизного кластеризації на основі цього послідовний порядок.
Методи зверху вниз і знизу вгору вважаються офлайновими методами, оскільки вони вимагають, щоб усі примітиви були доступні до початку конструювання. Методи вставки створюють дерево, вставляючи по одному об'єкту, починаючи з порожнього дерева. Місце вставки має бути обрано таким чином, щоб дерево зростало якомога менше відповідно до показника витрат. Методи вставки вважаються онлайновими, оскільки вони не вимагають, щоб усі примітиви були доступні до початку побудови і, таким чином, дозволяють виконувати оновлення під час виконання.
Використання
BVH часто використовуються в трасуванні променів для усунення потенційних кандидатів на перетин у сцені, пропускаючи геометричні об'єкти, розташовані в обмежуючих обсягах, які не перетинаються поточним променем. Крім того, як поширена оптимізація продуктивності, коли цікавить лише найближче перетин променя, оскільки алгоритм обходу променів є низхідними вузлами, а кілька дочірніх вузлів перетинають промінь, алгоритм обходу спочатку розглядатиме ближчий об'єм, і якщо він знайде перехрестя там, яке остаточно ближче, ніж будь-яке можливе перетин у другому (або іншому) томі (тобто томи не перекриваються), він може безпечно ігнорувати другий том. Подібні оптимізації під час обходу BVH можна використовувати при спуску до дочірніх томів другого тому, щоб обмежити подальший простір пошуку і таким чином зменшити час обходу.
Крім того, для BVH було розроблено багато спеціалізованих методів, особливо на основі AABB (обмежувальні рамки, вирівняні по осі), такі як паралельне побудова, прискорений обхід SIMD, хороша евристика розділення (SAH — евристика площі поверхні часто використовується в трасуванні променів), широкі дерева (4-х і 16-ти рядкові дерева забезпечують певні переваги в продуктивності, як при складанні, так і при виконанні запитів для практичних сцен), і швидке оновлення структури (у додатках реального часу об'єкти можуть рухатися або деформуватися в просторі відносно повільно або бути нерухомими, і той самий BVH можна оновити, щоб він залишався дійсним без повної перебудови з нуля).
BVH також, природно, підтримують вставлення та видалення об'єктів без повної перебудови, але в результаті цього BVH має, як правило, гіршу продуктивність запитів у порівнянні з повною перебудовою. Щоб вирішити ці проблеми (а також швидке оновлення структури є неоптимальним), новий BVH може бути створений асинхронно паралельно або синхронно, після виявлення достатніх змін (перекриття листків велике, кількість вставок і видалення перевищила поріг, і інші більш досконалі евристики).
BVH також можна поєднувати з методами графіка сцени та [en], щоб зменшити використання пам'яті, покращити оновлення структури та повну продуктивність перебудови, а також покращити розбивку об'єктів або примітивів.
Див. також
- Розбиття бінарного простору, дерево октантів, k-d дерево
- R-дерево, [en], R*-дерево та [en]
- [en]
- Граф сцени
- [en]
- Ієрархічна кластеризація
- [en]
Посилання
- 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 .
- Ericson, 2005, с. 238
- 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 . S2CID 2585433.
- 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 . S2CID 2840180.
Посилання
- BVH в Javascript
- Динамічний BVH на C#
- Бібліотека BVH з відкритим кодом Intel Embree
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Iyerarhiya obmezhenogo ob yemu BVH ce derevovidna struktura na mnozhini geometrichnih ob yektiv Usi geometrichni ob yekti sho utvoryuyut listkovi vuzli dereva zagornuti v obmezhuvalni ob yemi Ci vuzli potim grupuyutsya yak neveliki nabori i ukladayutsya v bilshi obmezhuvalni obsyagi Voni u svoyu chergu takozh grupuyutsya ta ukladayutsya v inshi bilshi obmezhuvalni obsyagi rekursivnim sposobom sho v kincevomu pidsumku prizvodit do strukturi dereva z yedinim obmezhuyuchim obsyagom u verhnij chastini dereva Iyerarhiyi obmezhuvalnih ob yemiv vikoristovuyutsya dlya efektivnoyi pidtrimki kilkoh operacij nad naborami geometrichnih ob yektiv napriklad pri viyavlenni zitknen i trasuvanni promeniv Priklad iyerarhiyi obmezhuvalnih ob yemiv iz vikoristannyam pryamokutnikiv yak obmezhuvalnih ob yemiv Hocha obgortannya ob yektiv u obmezhuvalni ob yemi ta vikonannya testiv na zitknennya dlya nih pered testuvannyam samoyi geometriyi ob yekta sproshuye testi ta mozhe prizvesti do znachnogo pokrashennya produktivnosti taka zh kilkist poparnih testiv mizh obmezhuyuchimi ob yemami vse she vikonuyetsya Yaksho vporyadkuvati obmezhuvalni ob yemi v iyerarhiyu chasovu skladnist kilkist vikonanih testiv mozhna zmenshiti do logarifmichnoyi kilkosti ob yektiv Z takoyu iyerarhiyeyu pid chas testuvannya yaksho batkivski ob yemi ne peretinayutsya napriklad yaksho obmezhuvalni ob yemi dvoh bampernih avtomobiliv ne peretinayutsya obmezhuvalni ob yemi samih bamperiv ne potribno pereviryati na zitknennya to ob yemi nashadki ne potribno pereviryati na peretin Problemi viboru BVHVibir granichnogo obsyagu viznachayetsya kompromisom mizh dvoma cilyami Z odnogo boku mi hotili b vikoristovuvati obmezhuvalni ob yemi yaki mayut duzhe prostu formu Takim chinom nam potribno lishe kilka bajtiv dlya yih zberigannya a en ta obchislennya vidstani prosti ta shvidki Z inshogo boku mi hotili b mati obmezhuvalni obsyagi yaki duzhe shilno pidhodyat do vidpovidnih ob yektiv danih Odnim z najbilsh chasto vikoristovuvanih obmezhuvalnih ob yemiv ye minimalna obmezhuvalna korobka virivnyana po osi tobto yiyi grani paralelni koordinatnim osyam Minimalnij obmezhuvalnij pryamokutnik virivnyanij po osi dlya zadanoyi mnozhini ob yektiv legko obchisliti jomu potribno lishe kilka bajtiv pam yati a nadijni testi peretinu realizuyutsya legko ta nadzvichajno shvidko Isnuye kilka bazhanih vlastivostej BVH yaki slid vrahovuvati pri proektuvanni dlya konkretnogo zastosuvannya Vuzli sho mistyatsya v bud yakomu danomu pidderevi povinni buti poruch odin z odnim Chim nizhche po derevu tim blizhche povinni buti vuzli odin do odnogo Kozhen vuzol v BVH povinen mati minimalnij ob yem Suma vsih obmezhenih ob yemiv povinna buti minimalnoyu Bilshu uvagu slid pridilyati vuzlam bilya korenya BVH Zriz vuzla bilya korenya dereva viluchaye bilshe ob yektiv z podalshogo rozglyadu Ob yem perekrittya odnotipnih vuzliv povinen buti minimalnim BVH maye buti zbalansovanim yak za strukturoyu vuzla tak i za zmistom Balansuvannya dozvolyaye zrizati yakomoga bilshu chastinu BVH koli gilka ne prohodit Z tochki zoru strukturi BVH neobhidno virishiti yakij stupin kilkist nashadkiv i visotu vikoristovuvati v derevi sho predstavlyaye BVH Derevo nizkogo stupenya bude bilshoyi visoti Ce zbilshuye chas prohodzhennya vid korenya do listya Z inshogo boku na kozhnomu vidviduvanomu vuzli potribno vitrachati menshe roboti shob pereviriti jogo dochirni elementi na perekrittya Dlya dereva visokogo stupenya spravedlivo protilezhne hocha derevo bude menshoyi visoti na kozhen vuzol vitrachayetsya bilshe roboti Na praktici dvijkovi dereva stupin 2 ye najbilsh poshirenimi Odniyeyu z osnovnih prichin ye te sho dvijkovi dereva legshe buduvati PobudovaIsnuye tri osnovni kategoriyi metodiv pobudovi dereva zverhu vniz znizu vgoru ta metodi vstavki Metodi zverhu vniz rozbivayut vhidnij nabir na dvi abo bilshe pidmnozhini obmezhuyuchi yih u vibranomu obmezhuvalnomu obsyazi a potim prodovzhuyut rozbivati i obmezhuvati rekursivno poki kozhna pidmnozhina ne bude skladatisya lishe z odnogo primitivu dosyagayutsya listovi vuzli Metodi zverhu vniz prosti v realizaciyi shvidki v pobudovi ta bezumovno najpopulyarnishi ale zagalom ne prizvodyat do najkrashih mozhlivih derev Metodi znizu vgoru pochinayutsya z vhidnogo naboru u viglyadi listkiv dereva a potim grupuyut dva abo bilshe z nih shob utvoriti novij vnutrishnij vuzol prodovzhuyut takim zhe chinom poki vse ne bude zgrupovano pid odnim vuzlom korin dereva Metodi znizu vgoru skladnishe realizuvati ale zagalom jmovirno virostut krashi dereva Deyaki neshodavni doslidzhennya napriklad vkazuyut na te sho v nizkovimirnomu prostori shvidkist pobudovi mozhna znachno pidvishiti sho vidpovidaye abo perevershuye pidhodi zverhu vniz shlyahom sortuvannya ob yektiv za dopomogoyu en ta zastosuvannya pribliznogo klasterizaciyi na osnovi cogo poslidovnij poryadok Metodi zverhu vniz i znizu vgoru vvazhayutsya oflajnovimi metodami oskilki voni vimagayut shob usi primitivi buli dostupni do pochatku konstruyuvannya Metodi vstavki stvoryuyut derevo vstavlyayuchi po odnomu ob yektu pochinayuchi z porozhnogo dereva Misce vstavki maye buti obrano takim chinom shob derevo zrostalo yakomoga menshe vidpovidno do pokaznika vitrat Metodi vstavki vvazhayutsya onlajnovimi oskilki voni ne vimagayut shob usi primitivi buli dostupni do pochatku pobudovi i takim chinom dozvolyayut vikonuvati onovlennya pid chas vikonannya VikoristannyaBVH chasto vikoristovuyutsya v trasuvanni promeniv dlya usunennya potencijnih kandidativ na peretin u sceni propuskayuchi geometrichni ob yekti roztashovani v obmezhuyuchih obsyagah yaki ne peretinayutsya potochnim promenem Krim togo yak poshirena optimizaciya produktivnosti koli cikavit lishe najblizhche peretin promenya oskilki algoritm obhodu promeniv ye nizhidnimi vuzlami a kilka dochirnih vuzliv peretinayut promin algoritm obhodu spochatku rozglyadatime blizhchij ob yem i yaksho vin znajde perehrestya tam yake ostatochno blizhche nizh bud yake mozhlive peretin u drugomu abo inshomu tomi tobto tomi ne perekrivayutsya vin mozhe bezpechno ignoruvati drugij tom Podibni optimizaciyi pid chas obhodu BVH mozhna vikoristovuvati pri spusku do dochirnih tomiv drugogo tomu shob obmezhiti podalshij prostir poshuku i takim chinom zmenshiti chas obhodu Krim togo dlya BVH bulo rozrobleno bagato specializovanih metodiv osoblivo na osnovi AABB obmezhuvalni ramki virivnyani po osi taki yak paralelne pobudova priskorenij obhid SIMD horosha evristika rozdilennya SAH evristika ploshi poverhni chasto vikoristovuyetsya v trasuvanni promeniv shiroki dereva 4 h i 16 ti ryadkovi dereva zabezpechuyut pevni perevagi v produktivnosti yak pri skladanni tak i pri vikonanni zapitiv dlya praktichnih scen i shvidke onovlennya strukturi u dodatkah realnogo chasu ob yekti mozhut ruhatisya abo deformuvatisya v prostori vidnosno povilno abo buti neruhomimi i toj samij BVH mozhna onoviti shob vin zalishavsya dijsnim bez povnoyi perebudovi z nulya BVH takozh prirodno pidtrimuyut vstavlennya ta vidalennya ob yektiv bez povnoyi perebudovi ale v rezultati cogo BVH maye yak pravilo girshu produktivnist zapitiv u porivnyanni z povnoyu perebudovoyu Shob virishiti ci problemi a takozh shvidke onovlennya strukturi ye neoptimalnim novij BVH mozhe buti stvorenij asinhronno paralelno abo sinhronno pislya viyavlennya dostatnih zmin perekrittya listkiv velike kilkist vstavok i vidalennya perevishila porig i inshi bilsh doskonali evristiki BVH takozh mozhna poyednuvati z metodami grafika sceni ta en shob zmenshiti vikoristannya pam yati pokrashiti onovlennya strukturi ta povnu produktivnist perebudovi a takozh pokrashiti rozbivku ob yektiv abo primitiviv Div takozhRozbittya binarnogo prostoru derevo oktantiv k d derevo R derevo en R derevo ta en en Graf sceni en Iyerarhichna klasterizaciya en PosilannyaEricson Christer 2005 6 1 Hierarchy Design Issues Real Time collision detection Morgan Kaufmann Series in Interactive 3 D Technology Morgan Kaufmann s 236 7 ISBN 1 55860 732 3 Ericson 2005 s 238 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 s 81 88 CiteSeerX 10 1 1 991 3441 doi 10 1145 2492045 2492054 ISBN 9781450321358 S2CID 2585433 Gunther 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 s 113 8 CiteSeerX 10 1 1 137 6692 doi 10 1109 RT 2007 4342598 ISBN 978 1 4244 1629 5 S2CID 2840180 PosilannyaBVH v Javascript Dinamichnij BVH na C Biblioteka BVH z vidkritim kodom Intel Embree