Loading AI tools
З Вікіпедії, вільної енциклопедії
Бінарне розбиття простору (англ. binary space partitioning), в інформатиці, це метод рекурсивного розбиття евклідового простору на опуклі множини за допомогою гіперплощин. Це розбиття призводить до подання об'єктів у просторі за допомогою деревоподібної структури даних, відомої як BSP-дерево.
BSP-дерево розроблялось для використання у тривимірній комп'ютерній графіці[1][2], тому що, структура BSP-дерева дозволяє виокремити інформацію, щодо об'єктів сцени, яка дозволяє при рендерингу ефективно виконувати такі операції, як сортування візуальних об'єктів в порядку віддалення від спостерігача та виявлення зіткнень. Також BSP-дерево використовується в застосунках для виконання операцій над формами (конструктивна блокова геометрія) в САПР[3], виявлення зіткнень у робототехніці, трасуванні променів та в інших застосунках, які виконують обробку складних просторових сцен.
Бінарне розбиття простору часто використовується для 3D-відеоігор, зокрема у шутерах від першої особи. BSP-дерева були вперше застосовані фахівцями компанії LucasArts на початку 80-х років. Популярність у розробників вони здобули завдяки компанії id Software, яка розробила рушії Doom (1993) і Quake (1996).
У відеоіграх, BSP-дерева, що містять статичну геометрію сцени, часто використовуються разом з Z-буфером, щоб правильно об'єднати рухомі об'єкти (наприклад, двері та персонажі) на тлі сцени.
Бінарне розбиття простору — це універсальний процес рекурсивного поділу сцени на два до тих пір, поки розбиття не задовольняє одному або декільком вимогам. Його можна розглядати як узагальнення інших просторових структур дерева таких як к-D дерева і дерева квадрантів.
Виникнення бінарного розбиття простору в комп'ютерній графіці пояснюється тим, що потрібно швидко малювати тривимірні сцени, що складаються з многокутників. Недолік такого розбиття полягає в тому, що створення BSP-дерева може зайняти багато часу. Як правило, тому його виконують один раз на статичній геометрії, як підготовчий крок розрахунку, до візуалізації або інших операцій у реальному часі на сцені.
Конкретний вибір розбиття площини і критерій для завершення процесу поділу варіюється в залежності від призначення BSP-дерева.
У BSP-дереві кожен вузол пов'язаний з прямою, яка розбиває або площиною в 2-вимірному або 3-вимірному просторі відповідно. При цьому всі об'єкти, що лежать з фронтальної сторони площини відносяться до фронтального піддерева, а всі об'єкти, що лежать зі зворотного боку площини відносяться до оборотного піддерева. Для визначення належності об'єкта до фронтальної або зворотної сторони прямій або площині, що розбиває необхідно досліджувати стан кожної його точки. Положення точки відносно площини визначається скалярним добутком нормалі площини і координат точки в однорідних координатах. Можливі три випадки:
Якщо для всіх точок об'єкта скалярний добуток більше або дорівнює 0, то він відноситься до фронтального піддерева. Якщо для всіх точок об'єкта скалярний добуток менше або дорівнює 0, то він відноситься до оборотного піддерева. Якщо скалярні добутки для точок об'єкта мають різний знак, то його розтинають площиною, яка розбиває так, щоб отримані об'єкти лежали тільки з фронтальної або тільки зі зворотної сторони. Для кожного підвузла BSP-дерева справедливо вищенаведене твердження, з тим винятком, що для розгляду підлягають тільки ті об'єкти, які належать до фронтальної або зворотної сторони батьківського вузла площини, яка розбиває.
Вищенаведене визначення описує тільки властивості BSP-дерева, але не каже як його побудувати. Як правило, BSP-дерево будується для набору відрізків на площині або полігонів в просторі, що представляють деяку фігуру або сцену. Розглянемо алгоритм побудови BSP-дерева для набору полігонів в просторі:[2]
На наступній діаграмі показано використання цього алгоритму в перетворенні списку ліній або полігонів в BSP-дерево. На кожній з восьми стадій (I.-VIII.) додається один новий вузол до дерева.
Остаточна кількість полігонів або ліній в дереві часто більше (іноді значно більше[2]), ніж початковий список, так як лінії або полігони, які перетинають площину перегородки повинна бути розділена на дві частини. Бажано звести до мінімуму це збільшення, але і підтримувати розумний баланс в кінцевому дереві. Вибір розділової площини дуже важливий в створенні ефективного BSP-дерева.
Площина, яка розбиває вибирається таким чином, щоб збалансувати дерево, тобто щоб число полігонів у фронтальному і зворотному піддереві було приблизно однаково: min(|N(Fi) — N(Bi)|)
де N(Fi) — число полігонів з фронтального боку деякої площині i, яка розбиває, N(Bi) — число полігонів зі зворотного боку площини i, яка розбиває.
При сортуванні об'єктів в порядку віддалення від спостерігача за допомогою BSP-дерева досліджуються взаємне розташування вектора і точки спостереження (POV) і нормалей площин, які розбивають. Якщо нормаль площини, яка розбиває і вектор спостереження співнаправлені, то фронтальне піддерево знаходиться від спостерігача далі, ніж зворотне, в іншому випадку оборотне піддерево знаходиться від спостерігача далі, ніж фронтальне. При цьому, якщо площина, яка розбиває знаходиться позаду спостерігача, то саму площину, а також фронтальне або оборотне піддерево може бути не видно повністю. Рекурсивний алгоритм сортування полігонів за допомогою BSP-дерева наступний:
Процедура ОбійтиВузол(Вузол) Якщо Вузол <> ПорожнійВказівник Якщо ВекториСпівнаправлені(ВекторСпостереження, Вузол.НормальПлощиниЯкаРозбиває) Якщо СкалярнийДобуток(ТочкаСпостереження, Вузол.НормальПлощиниЯкаРозбиває) >= 0 // Площина знаходиться позаду спостерігача, спостерігач бачить тільки фронтальне піддерево ОбійтиВузол(Вузол.ФронтальнеПіддерево); Інакше // Площина знаходиться спереду спостерігача, // фронтальне піддерево знаходиться далі оборотного ОбійтиВузол(Вузол.ФронтальнеПіддерево); ДодатиПолігонДоСпискуВідображення(Вузол.Полігон); ОбійтиВузол(Вузол.ОборотнеПіддерево); КінецьЯкщо; Інакше Якщо СкалярнийДобуток(ТочкаСпостереження, Вузол.НормальПлощиниЯкаРозбиває) >= 0 // Площина знаходиться спереду спостерігача, // оборотне піддерево знаходиться далі фронтального ОбійтиВузол(Вузол.ОборотнеПіддерево); ДодатиПолігонДоСпискуВідображення(Вузол.Полігон); ОбійтиВузол(Вузол.ФронтальнеПіддерево); Інакше // Площина знаходиться позаду спостерігача, спостерігач бачить тільки оборотне піддерево ОбійтиВузол(Вузол.ОборотнеПіддерево); КінецьЯкщо; КінецьЯкщо; КінецьЯкщо; Кінець;
Цей алгоритм можна оптимізувати, якщо врахувати, що для деякого набору полігонів дерево має вироджену структуру, в тому випадку, коли для кожного полігону з цього набору вся решта лежить тільки з фронтальної або тільки зі зворотної сторони. Саме так зробив Джон Кармак в рушії DOOM.
Алгоритм для прискорення з рекурсивного може бути перетворений в ітеративний.
Відсікання невидимих поверхонь реалізується шляхом введення додаткової інформації в BSP-дерево, такої як рамки (bounding boxes, bounding spheres). Рамки — це прямокутники або паралелепіпеди, окружності або сфери, які обмежують область розташування полігонів деякого піддерева. Таким чином, кожен вузол має дві рамки. Піддерево гарантовано невидимо, якщо зорова піраміда не перетинається з обмежувальним об'єктом. Зворотне невірно. Однак прямого твердження досить, щоб відсікти обробку суттєвої кількості об'єктів.
Вибір геометричних об'єктів, якими представлені рамки, виходить з простоти алгоритму перевірки перетину зорової піраміди з рамкою.
При пошуку зіткнень BSP-дерево використовується для пошуку площини, розташованої найближче до об'єкта. Найчастіше межі об'єкта задаються обмежувальною сферою (або колом) для спрощення обчислень. Виконується обхід BSP-дерева від кореня до площини, розташованої найближче до об'єкта. При цьому, якщо не виявлено перетинів обмежувальної сфери ні з однією площиною, то зіткнення немає, в іншому випадку — є.
Приклад:
Процедура ПощукЗіткнень(Вузол, Об’єкт) Якщо Вузол <> ПорожнійВказівник Якщо Відстань(Вузол.Площина, Об’єкт.ЦентрОбмежувальноїСфери) > Об’єкт.РадіусОбмежувальноїСфери Якщо СкалярнийДобуток(Об’єкт.ЦентрОбмежувальноїСфери, Вузол.НормальПлощиниЯкаРозбиває) >= 0 // Об’єкт знаходиться з фронтального боку площини, яка розбиває, // обходимо тільки фронтальне піддерево ПошукЗіткнень(Вузол.ФронтальнеПіддерево, Об’єкт); Інакше // Об’єкт знаходиться на зворотному боці площини, яка розбиває, // обходимо тільки оборотне піддерево ПошукЗіткнень(Вузол.ОборотнеПіддерево, Об’єкт); КінецьЯкщо; Інакше Повернути ЄЗіткнення; КінецьЯкщо; Інакше Повернути НемаєЗіткнення; КінецьЯкщо; Кінець;
Алгоритм для прискорення з рекурсивного може бути перетворений в ітеративний.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.