D05.11. Areas of application space partitioning trees?

[DmytroTarasov]

D05.11. Areas of application space partitioning trees? D05.11. Сфери застосування space partitioning trees?

[DmytroTarasov]

Discussion from previous years:

• Machine learning
• Computer Graphics
• Statistics
• Data with a large number of parameters

[DmytroTarasov]

Обговорення з попередніх років:

• Машинне навчання
• Комп’ютерна графіка
• Статистика
• Дані з великою кількістю параметрів

[Yuliiaa]

BSP trees are very useful for real time interaction with displays of static images. Before the static scene is rendered, the BSP tree is calculated. BSP trees can be traversed very quickly (linear time) for hidden surface removal and shadow casting. With some work, BSP trees can be modified to handle dynamic events in a scene. https://web.cs.wpi.edu/~matt/courses/cs563/talks/bsp/document.html Binary space partitioning was invented in the context of 3D computer graphics in 1969, where the structure of a BSP tree permits for spatial information about the objects in a scene that is useful in rendering, such as objects being ordered from front-to-back with respect to a viewer at a given location, to be accessed quickly. Other applications of BSPinclude:accomplishing geometrical operations with shapes (constructive solid geometry) in CAD, collision detection in 3D video games and robotics, ray tracing, and other applications that involve the handling of complex spatial scenes. https://www.tutorialspoint.com/bsp-trees-in-data-structure

[khilchuk-ol]

Прикладом такого дерева є kd-tree. Воно має наступні сфери використання:

1. Пошук найближчого сусіда. Наприклад, розглянемо наступну ситуацію: є карта (2-вимірний простір), є положення людини на цей карті і потрібно знайти найближчу будівлю певного типу (кафе, лікарня, тощо). Це буде задача пошуку найближчого сусіда.

2. Формування складних запитів до бази даних. Наприклад, в базі даних міститься інформацію про студентів, потрібно отримати інформацію про всіх студентів із віком та рейтингом у певних діапазонах. Це можна розглядати настпуним чином: проміжок віку - відрізок на осі Ох, проміжок рейтингу - відрізок на осі Оу. У 2-д просторі можна утворити прямокутну область, елементи якої відповідатимуть поставленим вимогам. Тоді з kd-tree можна буде отримати потрібні дані.

3. Проблема n тіл. Питання полягає ось в чому: як можна ефективно симулювати рух n тіла у просторі під дією певних законів. За допомогою kd-tree можна поділити простір на частини та для кожної із них розглядати, як те, що відбувається в цій частині, вплине на решту частин в деякий момент часу.

4. Редукція кольорів. Задача: обрати деяку кількість кольорів, щоб із нею представити повний спектр (градієнтно). Кольори можна представити як точки з координатами, що відповідають rgb коду і побудувати 3-д дерево,

Ресурс на дискусію, де можна знайти детальнішу інформацію: https://www.quora.com/What-is-a-kd-tree-and-what-is-it-used-for

[Edward3635]

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

space partitioning trees часто використовується для 3D-відеоігор, зокрема у шутерах від першої особи, space partitioning trees були вперше застосовані фахівцями компанії LucasArts на початку 80-х років. Популярність у розробників вони здобули завдяки компанії id Software, яка розробила рушії Doom (1993) і Quake (1996).

У відеоіграх, space partitioning trees, що містять статичну геометрію сцени, часто використовуються разом з Z-буфером, щоб правильно об'єднати рухомі об'єкти (наприклад, двері та персонажі) на тлі сцени.