Хонич А.
Как самому создать трехмерную игру
стр. 127

раздела (мнимая линия).

3.    Если вы не забыли, сначала должно делиться пространство с левой стороны линии раздела. Поэтому слева выбираем точку 1 и идем вверх.

4.    Далее слева от линии раздела 1 выбираем точку 2 и ведем вверх.

5.    Слева и справа от линии раздела 2 получились две неделимые области (два прямоугольника), которые становятся субсекгорами а и Ь.

6.    Правая область от линии 1 также не ну ждается в делении и становится субсектором с.

7.    Далее точно так же делятся правые области от линии раздела 0.

8.    После деления всего уровня (у иас получилось 5 узлов и 6 субсекторов) номера в рекурсивном дереве реверсируются (обратная последовательность), т.е. 0 узел станет 4, а 4 узел станет 0, и точно также с субсекгорами. Для номеров субсекгоров устанавливается 15 бит, а для номеров узлов 15 бит сброшен. Например, субсекгор 1 фактически будет иметь номер в шестнадцатеричном исчислении: 0x8001.

Для автоматической генерации рекурсивного дерева необходимо создать алгоритм, способный автоматически оптимально выбирать линии раздела. Основной принцип здесь состоит в том, чтобы свести к минимуму' количество узлов и субсекгоров, ну и, желательно, дополнительных вершин (которые получаются при мнимом продолжении линий раздела). Большинство генераторов BSP дерева обычно делят карту' пополам, и выбирают первую линию раздела где-то в середине карты.

Существуют два метода оптимизации BSP дерева, на мой взгляд, взаимоисключающих:

1.    Получение сбалансированного дерева. У сбалансированного дерева количества узлов и ветвей с левой и с правой сторон приблизительно должны совпадать.

2.    Свести к минимуму количество расколов линий и дополнительных вершин. Таким образом, уменьшается общее количество сегментов (SEGS) Однако обойтись совсем без расколов в подавляющем большинстве случаев не удастся. Но нам это и не нужно. Нам нужно, чтобы их было как можно меньше. Как это можно оптимизировать? Тут самое главное - оптимальный выбор линий раздела. Рассмотрим простой пример, изображенный на рисунке.

Если линиями раздела выбрать а и Ь, то мы получим четыре дополнительные вершины, 5 суб-секторов и 16 сегментов.

Если в качестве линий раздела выбрать А и В, то дополнительных вершин не требуется.


Новости
Авторы Kingdom Come: «Мы хотели сделать Red Dead Redemption с мечами»
Не причислять себя к традиционным инди-разработчикам, а пытаться создать игру, сравнимую с Red Dead, Far Cry, «Ведьмаком», Assassin’s Creed и The Elder Scrolls V: Skyrim.
VR-игра по мотивам Psychonauts добралась до ПК
На ПК вышла VR-игра от легендарного Тима Шейфера: теперь в Psychonauts in the Rhombus of Ruin могут сыграть не только владельцы PS VR, но и обладатели HTC Vive или Oculus Rift.