Бінарне розбиття простору англ binary space partitioning в інформатиці це метод рекурсивного розбиття евклідового просто

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

Бінарне розбиття простору (вгорі) і відповідне BSP-дерево (внизу). Простір містить відрізки {A, B1, B2, C1, C2, D1, D2, D3}. Кореневий вузол містить сегмент А; два піддерева, що відповідають областям по обидві сторони від А.

BSP-дерево розроблялось для використання у тривимірній комп'ютерній графіці, тому що, структура BSP-дерева дозволяє виокремити інформацію, щодо об'єктів сцени, яка дозволяє при рендерингу ефективно виконувати такі операції, як сортування візуальних об'єктів в порядку віддалення від спостерігача та виявлення зіткнень. Також BSP-дерево використовується в застосунках для виконання операцій над формами (конструктивна блокова геометрія) в САПР, виявлення зіткнень у робототехніці, трасуванні променів та в інших застосунках, які виконують обробку складних просторових сцен.

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

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

Загальна характеристика

Бінарне розбиття простору — це універсальний процес рекурсивного поділу сцени на два до тих пір, поки розбиття не задовольняє одному або декільком вимогам. Його можна розглядати як узагальнення інших просторових структур дерева таких як к-D дерева і дерева квадрантів.

Виникнення бінарного розбиття простору в комп'ютерній графіці пояснюється тим, що потрібно швидко малювати тривимірні сцени, що складаються з многокутників. Недолік такого розбиття полягає в тому, що створення BSP-дерева може зайняти багато часу. Як правило, тому його виконують один раз на статичній геометрії, як підготовчий крок розрахунку, до візуалізації або інших операцій у реальному часі на сцені.

Конкретний вибір розбиття площини і критерій для завершення процесу поділу варіюється в залежності від призначення BSP-дерева.

У BSP-дереві кожен вузол пов'язаний з прямою, яка розбиває або площиною в 2-вимірному або 3-вимірному просторі відповідно. При цьому всі об'єкти, що лежать з фронтальної сторони площини відносяться до фронтального піддерева, а всі об'єкти, що лежать зі зворотного боку площини відносяться до оборотного піддерева. Для визначення належності об'єкта до фронтальної або зворотної сторони прямій або площині, що розбиває необхідно досліджувати стан кожної його точки. Положення точки відносно площини визначається скалярним добутком нормалі площини і координат точки в однорідних координатах. Можливі три випадки:

Скалярний добуток більше 0 — точка лежить з фронтальної сторони площині;
Скалярний добуток дорівнює 0 — точка лежить на площині
Скалярний добуток менше 0 — точка лежить на звороті площині.

Якщо для всіх точок об'єкта скалярний добуток більше або дорівнює 0, то він відноситься до фронтального піддерева. Якщо для всіх точок об'єкта скалярний добуток менше або дорівнює 0, то він відноситься до оборотного піддерева. Якщо скалярні добутки для точок об'єкта мають різний знак, то його розтинають площиною, яка розбиває так, щоб отримані об'єкти лежали тільки з фронтальної або тільки зі зворотної сторони. Для кожного підвузла BSP-дерева справедливо вищенаведене твердження, з тим винятком, що для розгляду підлягають тільки ті об'єкти, які належать до фронтальної або зворотної сторони батьківського вузла площини, яка розбиває.

Побудова дерева

Приклад побудови 1. A — корінь і набір відрізків на всій площині. 2. A ділиться на B і C. 3. B ділиться на D і E. 4. D ділиться на повністю опуклі F і G, які і стають листям дерева.

Вищенаведене визначення описує тільки властивості BSP-дерева, але не каже як його побудувати. Як правило, BSP-дерево будується для набору відрізків на площині або полігонів в просторі, що представляють деяку фігуру або сцену. Розглянемо алгоритм побудови BSP-дерева для набору полігонів в просторі:

Якщо задана множина полігонів пуста, то закінчити алгоритм;
Для заданої множини полігонів вибрати площину S, яка розбиває;
Розсікти всі полігони, які перетинаються з S;
Віднести всі полігони, що знаходяться з фронтального боку S, до фронтального піддерева F, а всі полігони, що знаходяться із зворотного боку S, до оборотного піддерева B;
Виконати алгоритм рекурсивно для множини полігонів фронтального піддерева F;
Виконати алгоритм рекурсивно для множини полігонів оборотного піддерева B.

На наступній діаграмі показано використання цього алгоритму в перетворенні списку ліній або полігонів в BSP-дерево. На кожній з восьми стадій (I.-VIII.) додається один новий вузол до дерева.

	Почнемо зі списку ліній (або в 3D-полігонів), що утворюють сцену. У схемах дерев, списки позначаються прямокутниками з округленими кутами, а вузли — кругами. В просторовій схемі ліній напрямок позначається стрілкою.
i.	Наступні етапи Ми обираємо лінію, A, зі списку та,… …додаємо її до вузла. Ми розділили лінії, що залишилися в списку на тих, хто перед A (тобто B2, C2, D2), та тих, хто за (B1, C1, D1). Ми спочатку опрацьовуємо лінії, які знаходяться перед A (на етапах ii–v),… …після цього ті, що за (на етапах vi–vii)
ii.	Тепер ми застосовуємо алгоритм до списку ліній, які знаходяться в передній частині (містять В2, С2, Д2). Ми вибираємо лінію В2, додаємо її у вузол і ділимо список на лінії, які перед В2 (Н2), і ті, що знаходяться за (С2, С3).
iii.	Виберіть лінію D2 зі списку ліній в передній частині B2. Це єдиний рядок в списку, так що після додавання його в вузол, більше нічого не повинно бути зроблено.
iv.	Ми закінчили з лініями перед В2, тому розглянемо лінії позаду B2 (C2 і D3). Виберіть одну з них (C2), додайте її в вузол, іншу лінію в списку (D3) треба поставити в список ліній в передній частині С2.
v.	Тепер подивимося на список ліній в передній частині С2. Існує тільки одна лінія (D3), так що додаємо її до цього вузла і продовжуємо.
vi.	Тепер ми додали всі лінії, які знаходилися в передній частині, до BSP-дерева, так що ми тепер починаємо працювати з списком ліній позаду А. Вибираємо лінію (B1) з цього списку, ми додаємо B1 до вузла та ділимо список ліній в лінії, що знаходяться в передній частині B1 (тобто D1) та позаду В1 (тобто C1).
vii.	Оброблюємо перший список ліній в передній частині B1, D1 є єдиною лінією в цьому списку, так що додаємо її до цього вузла і продовжуємо.
viii.	Дивимося на наступну лінію у списку ліній за B1, залишилася єдина лінія у цьому списку — C1, так що додаємо її до цього вузла, і BSP-дерево завершено.

Остаточна кількість полігонів або ліній в дереві часто більше (іноді значно більше), ніж початковий список, так як лінії або полігони, які перетинають площину перегородки повинна бути розділена на дві частини. Бажано звести до мінімуму це збільшення, але і підтримувати розумний баланс в кінцевому дереві. Вибір розділової площини дуже важливий в створенні ефективного 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 // Об’єкт знаходиться з фронтального боку площини, яка розбиває, // обходимо тільки фронтальне піддерево ПошукЗіткнень(Вузол.ФронтальнеПіддерево, Об’єкт); Інакше // Об’єкт знаходиться на зворотному боці площини, яка розбиває, // обходимо тільки оборотне піддерево ПошукЗіткнень(Вузол.ОборотнеПіддерево, Об’єкт); КінецьЯкщо; Інакше Повернути ЄЗіткнення; КінецьЯкщо; Інакше Повернути НемаєЗіткнення; КінецьЯкщо; Кінець;

Алгоритм для прискорення з рекурсивного може бути перетворений в ітеративний.

Хронологія

1969 Шумакер опублікував доповідь, в якій описано, як ретельно розташовані літаки в віртуальному середовищі можуть бути використані для прискорення впорядкування полігонів. Методика використовувала глибини когерентності, в якій йдеться про те, що полігон на дальній стороні літака не може якимось чином перешкоджати ближчий полігон. Це було використано в тренажерах, зроблених GE, а також Еванс і Сазерленд. Проте, створення багатокутної організації даних була виконана вручну дизайнером сцени.
1980 ^[en] продовжив ідею Шумакера у справі подання 3D-об'єктів у віртуальному середовищі за допомогою літаків. Це забезпечило повністю автоматизовану і алгоритмічну генерацію ієрархічної багатокутної структури даних, відомої як Binary Space Partitioning Tree (BSP-дерево). Цей процес проходив як попередня обробка стадії офф-лайн, яка була виконана один раз у навколишньому середовищі / об'єкті.
1981 Кандидатська дисертація Нейлора представила повноцінний розвиток BSP-дерева і теоретико-графового підходу, що передбачає використання сильно зв'язкових компонентів для попереднього обчислення видимості, а також зв'язок між цими двома методами. У дисертації також включені перші емпіричні дані, що свідчать про те, що розмір дерева і кількість нових полігонів була розумною (з використанням моделі Space Shuttle).
1983 ^[en] описав реалізацію мікрокоду алгоритму BSP-дерева на буферній системі кадру Ikonas. Це була перша демонстрація визначення видимої поверхні в реальному часі з використанням BSP-дерев.
1987 Тібо і Нейлор описали як довільні багатогранники можуть бути представлені за допомогою BSP-дерева, на відміну від традиційних b-Rep (граничного уявлення). Це дало тверде уявлення поверхні на основі репрезентації. Набір операцій над многогранниками був описан з використанням інструменту, що дозволяє конструктивна блокова геометрія (CSG) в режимі реального часу.
1990 Нейлор, Amanatides і Тібо запропонували алгоритм для об'єднання двох BSP-дерев, щоб сформувати нове BSP-дерево з двох вихідних дерев. Це дає безліч переваг, серед яких: об'єднання рухомих об'єктів, які представлені як BSP-дерева зі статичним середовищем (також представлене BSP-деревом), точне виявлення зіткнень в $O(\log n*\log n)$ , належне упорядкування прозорих поверхонь, що містяться в двох взаємопроникаючих об'єктів (використовується для ефекту рентгенівського зору).
1990 ^[en] запропонував автономну генерацію потенційно видимих наборів для прискорення видимого визначення поверхні в ортогональних 2D середовищах.
1991 Гордон і Чен описали ефективний спосіб проведення передньо-заднього перекладу з BSP-дерева, а не традиційний ззаду-вперед підхід. Цей алгоритм разом з описом BSP-дерева в стандартній комп'ютерній графіці по підручнику дня (^[en]) була використана Джоном Кармаком в створенні Doom (відеоігри).
1992 кандидатська дисертація Теллера описувала ефективну генерацію потенційно видимих наборів як крок попередньої обробки для прискорення в режимі реального часу визначення видимої поверхні в довільних 3D полігональних середовищах. Це було використано в Quake (відеоігри) і робить значний внесок у результативність цієї гри.
Нейлор відповів на питання про те, що характеризує хороше BSP-дерево. Він використовував очікувані моделі випадку (а не аналізував найбільш несприятливі випадки) для математичного виміру очікуваної вартості пошуку дерева і використовував цей захід, щоб побудувати хороші BSP-дерева. Інтуїтивно зрозуміло, що дерево представляє об'єкт в декількох резолюціях моди (більш точно, як дерево наближень).

Примітки

Schumacker, Robert A.; Brand, Brigitta; Gilliland, Maurice G.; Sharp, Werner H (1969). Study for Applying Computer-Generated Images to Visual Simulation (Report). U.S. Air Force Human Resources Laboratory. p. 142. AFHRL-TR-69-14.
Fuchs, Henry; Kedem, Zvi. M; Naylor, Bruce F. (1980). «On Visible Surface Generation by A Priori Tree Structures». SIGGRAPH '80 Proceedings of the 7th annual conference on Computer graphics and interactive techniques. ACM, New York. pp. 124—133. doi:10.1145/965105.807481.
Thibault, William C.; Naylor, Bruce F. (1987). Set operations on polyhedra using binary space partitioning trees. SIGGRAPH '87 Proceedings of the 14th annual conference on Computer graphics and interactive techniques. ACM, New York. с. 153—162. doi:10.1145/37402.37421.

Література

Mark de Berg. Computational Geometry: Algorithms and Applications. — Springer Science & Business Media, 2008. — P. 259. — .

Посилання

BSP trees presentation [ 18 серпня 2005 у Wayback Machine.](англ.)
(англ.)
A Java applet that demonstrates the process of tree generation [ 8 січня 2007 у Wayback Machine.](англ.)
A Master Thesis about BSP generating [ 3 квітня 2015 у Wayback Machine.](англ.)
(англ.)
BSP in 3D space [ 31 липня 2016 у Wayback Machine.](англ.)
(рос.)

[:0-1] Schumacker, Robert A.; Brand, Brigitta; Gilliland, Maurice G.; Sharp, Werner H (1969). Study for Applying Computer-Generated Images to Visual Simulation (Report). U.S. Air Force Human Resources Laboratory. p. 142. AFHRL-TR-69-14.

[:1-2] Fuchs, Henry; Kedem, Zvi. M; Naylor, Bruce F. (1980). «On Visible Surface Generation by A Priori Tree Structures». SIGGRAPH '80 Proceedings of the 7th annual conference on Computer graphics and interactive techniques. ACM, New York. pp. 124—133. doi:10.1145/965105.807481.

[thibault87-3] Thibault, William C.; Naylor, Bruce F. (1987). Set operations on polyhedra using binary space partitioning trees. SIGGRAPH '87 Proceedings of the 14th annual conference on Computer graphics and interactive techniques. ACM, New York. с. 153—162. doi:10.1145/37402.37421.