Хонич А.
Как самому создать трехмерную игру
стр. 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 сегментов.

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


Новости
Выход Fear the Wolves в раннем доступе в Steam отложили
Чернобыльская королевская битва Fear the Wolves от бывших авторов "Сталкера" должна была уже сегодня выйти в раннем доступе в Steam, но игра задержится - участники закрытого бета-теста выявили множество проблем, так что релиз решили отложить.
Похоже, авторы God of War уже приступили к работе над продолжением
В начале июня старший художник Sony Santa Monica Нейт Стивенс рассказал, что следующая часть God of War станет «масштабнее, лучше и продолжительнее», а команде предстоит поломать голову над тем, как бы превзойти самих себя в сиквеле.