Ну чтожы, давайте немного расскажу о том, что это вообще такое, откуда взялось, почему не было раньшы. Бинарные деревья (хотя навряд ли только они), имеют следующую особенность - их построение привязывается к конкретной задаче. То есть нельзя построить идеальное дерево для всего сразу, но можно для одних и тех же данных построить несколько деревьев и каждое будет оптимально для своих задач. Собственно, поэтому и клипноды - оптимизированное дерево для коллизии. С видимостью всё не так однозначно. После первой кваки, Кармак решил не хранить более одного дерева на модель. В ку2 это привело к проблемам - на ноды пришлось класть брашы, дерево получилось неоптимальным, переусложнённым. Настолько неоптимальным, что для рассчёта видимости, компилятор создаёт новое дерево, игнорируя детальные и мелкие лифы. Но в ку2 нет явной привязки виздаты к лифам - там промежуточные индексы, которые называются кластерами. В ку3 дерево еще более общее. Если быть точным, оно ни для чего. Для коллизии оно слишком поверхностное, кмк регулярная сетка была бы куда более оптимальна. Для точечной трассы - аналогично, оно не включает в себя например плоскости патчей, трисурф-моделей, это надо трейсить отдельно. Еще и проверяя, что в этом лифе мы уже трейсили (это особенно интересно выполнять при мультипоточных рассчётах). Единственное для чего кутришное дерево оптимально - это для видимости. В моду уже входили графические ускорители, риваТНТ опять же. И вот с их учётом дерево и было построено. А для первой кваки остался самый неоптимальный вариант на текущий момент. Рассмотрим это подробнее.
В первой кваке\первой халфе, как известно нет функ_детайла, нет ареапорталов и прочего. Дерево там в первую очередь устроено для максимальной оптимизации коллизии. А небольшой размер дерева получался автоматически - квака не блистала детализаций в 95-м году, сами понимаете. Но время шло, карты становились всё навороченней и вот то самое дерево, которое идеально подходило для колоизации, выступило ключевым тормозом перестройки для проверки видимости.
По очень простой причине - чем больше детализация, тем больше лифов и нодов, чем больше лифов и нодов, там дольше обходить дерево. Возникала ситуация, когда проверка на видимость в десятки раз дольше, чем, собственно отрисовка. Вот кстати, что касается, сипульчера, спонзы и прочих подобных карт. Китаец и автор TyrUtils, понимали проблему, поэтому попытались ввести детайл-брашы для первого квейка\халфы. Но проблему это решило только наполовину и вот почему: оптимальное дерево существовало только для виза и здорово сокращало время его рассчётов, вплоть до того, что карта, которая могбы считаться часов 30, теперь считалась пару минут. Но для сохранения совместимости с форматом халфы\кваки, им в любом случае пришлось нагенерить дополнительных нодов-лифов для того чтобы описать все эти детальные брашы, чтобы движок смог их отрисовать. Причём нельзя даже сказать, что они вообще не нужны - ведь они же еще и для коллизии используются. Тот же рад, например тени по ним считает. Но считать видимость по такому дереву нельзя категорически. Вот у того же Edge Of Forever, скомпиленного в формат условной первохалфы, получается 136 тысяч лифов. Даже если просто пробежать их в цикле - ну можете подсчитать сколько времени это займет. Далее, видимые лифы копятся для энтить для быстрой проверки видимости. Ну кто движок ковырял тот знает. А если лифов через чур много, то вместо них делается проверка видимости по хеадноде. Вы никогда не задумывались сколько времени занимает такая вот проверка? Я не считал точно сколько там энтить каждый кадр её запрашивают, но всего на карте 386 энтить. Ну пусть половина. Этот запрос на проверку видимости, отнимает по времени 0.07 секунд!!!!! Рендер, к примеру управляется на два порядка быстрее. То есть получается идиотизм. Вроде бы и детайлы есть и виз оптимизированный. А фпс всё хуже и хуже. К слову говоря старый Кармаковский код с поиском лифов через родителя ноды в данной ситуации чувствует себя чуть получше. Но и только. Конечно это всё неюзабельно, как вы понимаете. Как же поступить в данной ситуации? Какие варианты у меня были?
Добавлено 02-11-2019 в 20:56:
самый "простой" метод, который у меня был, как вы понимаете - это взять формат карт из Quake3. После всего что я сделал для халфовского формата, научил его считать лайтмапы на моделях, повертексное и еще массу других интересных вещей, взять дропуть и прикрутить кутришный формат, как в Волатиле. Ну не скрою, текущая архитектура XashNT позволяет его прикрутитьЮ не затрагивая другие подсистемы. Но сами особенности формата могут доставить немало весёлых минут мапперам, если я им потенциально предложу на него перейти. Напомню, что я даже патчи и трисурфы имплементировал в халфовский формат. Как говорится - последний довод за кутришный, который мне всегда приводили в пример.
Ну вообщем с учётом вышесказанного я решил, что мне нужно не маяться дурью прикручивая к движку разные там форматы карт, этим хорошо заниматься, когда ты учишься, и попытаться решить проблему более элегантным способом. Например построить такое специальное дерево для видимости. Как это сделать? Компиляторы, учитывющие детайлы в картах делают одну оптимизацию - для детальных лифов пишется тот же самый оффсет виздаты, что и для главного лифа, из которого они наследуются. Второй момент - они обычно не раскиданы по карте вперемежку, а идут группой подряд. Собсно это второе больше влияет на возможности оптимизации по скорости построения нового дерева, а не на какую-то принципиальную невозможность. Главное же условие, я назвал - совпадающие оффсеты у виздаты. Итак, по этим оффсетам мы находим настоящие визлифы, их кол-во и создаём новый массив с визлифами, аккумулируя в один лиф всё из детальных. Аналогично из обычных нодов создаётся массив визнодов. Здесь над подстерегает одна нехорошая проблема - во первых эти ноды раньше ссылались на детальные лифы, а теперь на одни и те же номера обычных лифов, которыми мы их подменили. Это не фатально, но провоцирует дубликат в BoxLeafnums, что в свою очередь быстро приводит к их переполнению в массивах энтить и снова здравствуй поиск по хеадноде, а поскольку визнодов столько же, сколько было в исходном массиве, никакой оптимизации считайте и не было - только память зря израсходовали. То есть моя основная задача, которую я решал последние два дня - как эффективно выкинуть эти лишние ноды и при этом не поломать дерево и чтобы это было быстро (поскольку делается во время загрузки уровня). Ну собно, немного статистики я привёл выше. Edge Of Forever с виздеревом теперь выдаёт вместо 15 фпс, около 500. У спонзы тоже фпс очень вырос.
ну и разумеется в моде рейда произойдут аналогичные позитивные улучшения.
Дядя Миша писал: После всего что я сделал для халфовского формата, научил его считать лайтмапы на моделях, повертексное и еще массу других интересных вещей, взять дропуть и прикрутить кутришный формат, как в Волатиле.
А что тебя смущает, это самое логичное решение. Я эту иррунду с лифами и нодами, в которых непременно должны лежать все сурфасы, быстро просёк и даже не стал пытаться использовать. Оно полезно разве что для софтварного рендера.
Что касается "после всего что сделал" - ну я тоже когда-то сделал в волатиле кучу всяких интересных оптимизаций для шадов-волюмов, а ты говорил - не жалей, выбрасывай, ну неактуальны уже эти волюмы. И вот однажды я выбросил и не жалею.
XaeroX писал: Оно полезно разве что для софтварного рендера.
Оно полезно для точечной трассы в первую очередь.
Цитата:
XaeroX писал: ну я тоже когда-то сделал в волатиле кучу всяких интересных оптимизаций для шадов-волюмов
Вот ежели бы ты научил волюмы кастовать тени от альфа-текстур - их реально было бы жалко выбрасывать.
Добавлено 02-11-2019 в 22:09:
Вообще я планирую кутришный формат прикрутить, в рамках теста. Ну интересно жеж. Ну то потом когда-нибудь.
Добавлено 02-11-2019 в 23:13:
Хым. Оказывается я случайно нашёл возможность оптимизировать любое дерево, не только содержащее детайл-ноды. Можно выкинуть из дерева ссылку на общий нулевой лиф и за счёт этого сократить его размер. Ссылка на этот лиф всё равно нахрен не нужна для визтри. А для наружки достаточно сделать PointInLeaf увидеть что кластер == -1 и включить полную видимость.
От оно. У меня же виз по возможности идентичные векторы выбрасывает для экономии места. Хотя это и не совсем корректно по идее - использовать это как условие для идентичных лифов, придётся пересмотреть немного этот механизм.
Дядя Миша писал: Очевидно в джеке можно порезать брашы для любой карты
Угу, но халфовские компиляторы всё склеят обратно и порежут так, как им нравится. А ку3шные - уважают право маппера решать, как и что должно быть порезано.
Цитата:
Дядя Миша писал: У меня же виз по возможности идентичные векторы выбрасывает для экономии места.
Это ещё одна умная оптимизация, от которой мало толку на ку3шном дереве с малым числом кластеров?
XaeroX писал: Угу, но халфовские компиляторы всё склеят обратно и порежут так, как им нравится
Халфовские порежут, а мои не порежут.
С этим виздеревом всё не так однозначно вообщем. Можно использовать один накопительный проход, это очень быстро, практически незаметно.
А можно использовать поиск по лифам NxN, но с прямым продвижением, я чёрт его знает как это правильно называется, не силён в терминологии.
Ну вообщем цикл вида
C++ Source Code:
1
for( int i = 0; i < numleafs; i++ )
2
{
3
for( int j = i + 1; j < numleafs; j++ )
4
{
5
}
6
}
Это дешевле чем настоящий NxN. Но и дерево для первого случая получается менее оптимальным, результаты для быстрого построения
Цитата:
LoadLeafs: time: 0.100575 secs
node tree optimized by 3 iterations
source 162224 nodes, optimized tree 3757 nodes
source 138415 leafs, optimized tree 2235 leafs
LoadNodes: time: 0.291052 secs
Результаты для глубокой аналитики от Ozzy
Цитата:
LoadLeafs: time: 2.419452 secs
node tree optimized by 3 iterations
source 162224 nodes, optimized tree 3757 nodes
source 138415 leafs, optimized tree 2235 leafs
LoadNodes: time: 0.291097 secs
На первый взгляд кажется, что один хрен. Но в игре, быстрое построение даёт 400 фпс, а медленное - 470 фпс. Так же на некоторых картах кол-во лифов для визтри может увеличиться при быстром построении, что тоже может сказаться на итоговом фпс. Здесь есть еще одна проблема - дублирующиеся лифы. Для поиска по дереву это не играет никакой роли, т.к. найденные сурфейсы всё равно помечаются единожды. Но это имеет значение для BoxLeafnums, куда попадают одинаковые лифы. Само по себе это не проблема тоже. Проблема в том, что этих лифов, как вы помните на энтитю не может быть более 48. А потом начинается тежолый поиск по головной ноде, хотя он теперь и происходит по визтри, это всё равно нежелательный кейс. Ну собсно, я пока что сделал проверку при сохранении лифов в энтить, чёб добавляло лишь уникальные. А потом надо подумать, возможно заменить фиксированный массив на деномический. Но гораздо важнее разобраться насколько вообще допустимы эти дублирующиеся лифы. На первый взгляд всё отлично, фпс сильно вырос, видимость корректно считается. Но тут необходимо провести серию юнит-тестов.
Цитата:
XaeroX писал: Это ещё одна умная оптимизация, от которой мало толку на ку3шном дереве с малым числом кластеров?
Дерево само-по себе не самоцель. Оптимальнее иметь несколько деревьев для своих задач. Так вот кутришное толком не годится ни для чего. Оно только для видимости. Физика по нему настолько неоптимально считается, что я вот просто уверен, что если его заменить на AABB, станет быстрее. Кстати попробуй.
Дядя Миша писал: Физика по нему настолько неоптимально считается, что я вот просто уверен, что если его заменить на AABB, станет быстрее.
Быстрее на 0.00001 сек? Колоизация это последнее, что может тормозить на ку3шном дереве. Куда важнее дерево, которое использует физдвиг для динамической симуляции. Но там своё.
| IP: 
02-11-2019 13:05
