Bounding volume hierarchy (original) (raw)
A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects, that form the leaf nodes of the tree, are wrapped in bounding volumes. These nodes are then grouped as small sets and enclosed within larger bounding volumes. These, in turn, are also grouped and enclosed within other larger bounding volumes in a recursive fashion, eventually resulting in a tree structure with a single bounding volume at the top of the tree. Bounding volume hierarchies are used to support several operations on sets of geometric objects efficiently, such as in collision detection and ray tracing.
| Property | Value |
|---|---|
| dbo:abstract | A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects, that form the leaf nodes of the tree, are wrapped in bounding volumes. These nodes are then grouped as small sets and enclosed within larger bounding volumes. These, in turn, are also grouped and enclosed within other larger bounding volumes in a recursive fashion, eventually resulting in a tree structure with a single bounding volume at the top of the tree. Bounding volume hierarchies are used to support several operations on sets of geometric objects efficiently, such as in collision detection and ray tracing. Although wrapping objects in bounding volumes and performing collision tests on them before testing the object geometry itself simplifies the tests and can result in significant performance improvements, the same number of pairwise tests between bounding volumes are still being performed. By arranging the bounding volumes into a bounding volume hierarchy, the time complexity (the number of tests performed) can be reduced to logarithmic in the number of objects. With such a hierarchy in place, during collision testing, children volumes do not have to be examined if their parent volumes are not intersected (for example, if the bounding volumes of two bumper cars do not intersect, the bounding volumes of the bumpers themselves would not have to be checked for collision). (en) Drzewo brył ograniczających (ang. Bound Volume Hierarchy, BVH) – struktura danych do przechowywania i szybkiego wykonywania zapytań dotyczących obiektów w przestrzeni trójwymiarowej. Najczęściej stosowana jest w grafice komputerowej do akceleracji algorytmu śledzenia promieni (ang. ray tracing) oraz w symulacjach fizyki ciał do akceleracji detekcji kolizji (np. w grach komputerowych). Drzewo BVH ma najczęściej postać przestrzennie zrównoważonego drzewa binarnego (chociaż stosuje się też drzewa o rozwidleniu 4, 8 czy 16). Obiekty znajdujące się w przestrzeni trójwymiarowej ograniczone są poprzez prostsze bryły – najczęściej prostopadłościany ze ścianami równoległymi do osi układu współrzędnych (ang. box, pudełko) lub kule – a ograniczenie drzewa łatwo wyznaczyć poprzez ograniczenie dwóch poddrzew. Drzewa BVH mają różną konstrukcję w zależności od zastosowań. Można je budować zarówno z góry w dół (poprzez podział większych brył na mniejsze), jak i z dołu w górę (poprzez łączenie brył mniejszych w większe). W przeciwieństwie do drzewa kd (również stosowanych w metodach śledzenia promieni i symulacjach), w przypadku scen dynamicznych, (w których obiekty poruszają się lub pojawiają i znikają) drzewo BVH łatwo uaktualnić poprzez utrzymanie struktury i zmianę rozmiarów pudełek, tak aby było nadal prawidłowe i bliskie optymalności – która i tak zwykle jest oparta na heurystykach. W przypadku drzew kd jest to niemożliwe. W praktyce korzystanie z nich jest bardziej wydajne, jednak z uwagi na koszt tworzenia jakichkolwiek drzew w przypadku scen dynamicznych używa się drzew BVH, ponieważ można je zbudować raz i wykorzystać w wielu następnych klatkach sceny – podobieństwo sceny w czasie powoduje, że drzewo BVH jest wystarczająco dobre. (pl) Ієрархія обмеженого об'єму (BVH) — це деревовидна структура на множині геометричних об'єктів. Усі геометричні об'єкти, що утворюють листкові вузли дерева, загорнуті в обмежувальні об'єми. Ці вузли потім групуються, як невеликі набори і укладаються в більші обмежувальні обсяги. Вони, у свою чергу, також групуються та укладаються в інші більші обмежувальні обсяги рекурсивним способом, що в кінцевому підсумку призводить до структури дерева з єдиним обмежуючим обсягом у верхній частині дерева. Ієрархії обмежувальних об'ємів використовуються для ефективної підтримки кількох операцій над наборами геометричних об'єктів, наприклад, при виявленні зіткнень і трасуванні променів. Хоча обгортання об'єктів у обмежувальні об'єми та виконання тестів на зіткнення для них перед тестуванням самої геометрії об'єкта спрощує тести та може призвести до значного покращення продуктивності, така ж кількість попарних тестів між обмежуючими об'ємами все ще виконується. Якщо впорядкувати обмежувальні об'єми в ієрархію, часову складність (кількість виконаних тестів) можна зменшити до логарифмічної кількості об'єктів. З такою ієрархією під час тестування, якщо батьківські об'єми не перетинаються (наприклад, якщо обмежувальні об'єми двох бамперних автомобілів не перетинаються, обмежувальні об'єми самих бамперів не потрібно перевіряти на зіткнення), то об'єми-нащадки не потрібно перевіряти на перетин. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Example_of_bounding_volume_hierarchy.svg?width=300 |
| dbo:wikiPageExternalLink | https://www.embree.org/ https://github.com/imbcmdth/jsBVH http://www.codeproject.com/Articles/832957/Dynamic-Bounding-Volume-Hiearchy-in-Csharp |
| dbo:wikiPageID | 3950612 (xsd:integer) |
| dbo:wikiPageLength | 9926 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1094757939 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:M-tree dbr:Bounding_volume dbr:Crofton_formula dbr:SIMD dbr:Geometry_instancing dbr:R-tree dbr:Collision_detection dbc:Geometric_data_structures dbr:Time_complexity dbr:K-d_tree dbc:3D_computer_graphics dbr:Tree_structure dbr:Binary_space_partitioning dbr:Hierarchical_clustering dbr:Ray_tracing_(graphics) dbr:OptiX dbr:R*-tree dbr:Geometric dbr:Minimum_bounding_box dbr:Space-filling_curve dbr:Octree dbr:Sweep_and_prune dbr:Scene_graph dbr:X-tree dbr:Intersection_test dbr:R+-tree dbr:File:Example_of_bounding_volume_hierarchy.svg |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Geometric_data_structures dbc:3D_computer_graphics |
| gold:hypernym | dbr:Structure |
| rdf:type | yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:DataStructure105728493 yago:PsychologicalFeature100023100 yago:WikicatGeometricDataStructures dbo:Building yago:Structure105726345 |
| rdfs:comment | A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects, that form the leaf nodes of the tree, are wrapped in bounding volumes. These nodes are then grouped as small sets and enclosed within larger bounding volumes. These, in turn, are also grouped and enclosed within other larger bounding volumes in a recursive fashion, eventually resulting in a tree structure with a single bounding volume at the top of the tree. Bounding volume hierarchies are used to support several operations on sets of geometric objects efficiently, such as in collision detection and ray tracing. (en) Drzewo brył ograniczających (ang. Bound Volume Hierarchy, BVH) – struktura danych do przechowywania i szybkiego wykonywania zapytań dotyczących obiektów w przestrzeni trójwymiarowej. Najczęściej stosowana jest w grafice komputerowej do akceleracji algorytmu śledzenia promieni (ang. ray tracing) oraz w symulacjach fizyki ciał do akceleracji detekcji kolizji (np. w grach komputerowych). Drzewo BVH ma najczęściej postać przestrzennie zrównoważonego drzewa binarnego (chociaż stosuje się też drzewa o rozwidleniu 4, 8 czy 16). (pl) Ієрархія обмеженого об'єму (BVH) — це деревовидна структура на множині геометричних об'єктів. Усі геометричні об'єкти, що утворюють листкові вузли дерева, загорнуті в обмежувальні об'єми. Ці вузли потім групуються, як невеликі набори і укладаються в більші обмежувальні обсяги. Вони, у свою чергу, також групуються та укладаються в інші більші обмежувальні обсяги рекурсивним способом, що в кінцевому підсумку призводить до структури дерева з єдиним обмежуючим обсягом у верхній частині дерева. Ієрархії обмежувальних об'ємів використовуються для ефективної підтримки кількох операцій над наборами геометричних об'єктів, наприклад, при виявленні зіткнень і трасуванні променів. (uk) |
| rdfs:label | Bounding volume hierarchy (en) Drzewo BVH (pl) BVH-дерево (uk) |
| owl:sameAs | freebase:Bounding volume hierarchy yago-res:Bounding volume hierarchy wikidata:Bounding volume hierarchy dbpedia-pl:Bounding volume hierarchy dbpedia-uk:Bounding volume hierarchy https://global.dbpedia.org/id/4azLm |
| prov:wasDerivedFrom | wikipedia-en:Bounding_volume_hierarchy?oldid=1094757939&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Example_of_bounding_volume_hierarchy.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Bounding_volume_hierarchy |
| is dbo:wikiPageDisambiguates of | dbr:BVH |
| is dbo:wikiPageRedirects of | dbr:Bvtree dbr:BV-tree dbr:Bounding_volume_hierarchies |
| is dbo:wikiPageWikiLink of | dbr:BVH dbr:BVT dbr:Enscape dbr:List_of_data_structures dbr:M-tree dbr:Bvtree dbr:Bounding_volume dbr:Crofton_formula dbr:R-tree dbr:GeForce_20_series dbr:Glossary_of_computer_graphics dbr:Bounding_interval_hierarchy dbr:Collision_detection dbr:Turing_(microarchitecture) dbr:Local_coordinates dbr:Ming_C._Lin dbr:Caustic_Graphics dbr:Nvidia_RTX dbr:Hidden-surface_determination dbr:Soft-body_dynamics dbr:Hierarchical_clustering dbr:Ray_tracing_(graphics) dbr:IClone dbr:Open_Cascade_Technology dbr:OptiX dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Scene_graph dbr:Priority_R-tree dbr:Spatial_database dbr:BV-tree dbr:Bounding_volume_hierarchies |
| is foaf:primaryTopic of | wikipedia-en:Bounding_volume_hierarchy |
