| 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
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 9926 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| 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
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
