HLFX.Ru Forum (https://hlfx.ru/forum/index.php)
- Наши проекты (https://hlfx.ru/forum/forumdisplay.php?forumid=1)
-- XashNT: блог разработчика (https://hlfx.ru/forum/showthread.php?threadid=5297)

Ну собсно, первые валидные результаты, для Edge Of Forever

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Vis Tree, что это и для чего нужно

Ну чтожы, давайте немного расскажу о том, что это вообще такое, откуда взялось, почему не было раньшы. Бинарные деревья (хотя навряд ли только они), имеют следующую особенность - их построение привязывается к конкретной задаче. То есть нельзя построить идеальное дерево для всего сразу, но можно для одних и тех же данных построить несколько деревьев и каждое будет оптимально для своих задач. Собственно, поэтому и клипноды - оптимизированное дерево для коллизии. С видимостью всё не так однозначно. После первой кваки, Кармак решил не хранить более одного дерева на модель. В ку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. У спонзы тоже фпс очень вырос.
ну и разумеется в моде рейда произойдут аналогичные позитивные улучшения.

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

__________________

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Дядя Миша
Ничего не понял, но как всё таки с т.з. левел-дизайнера результирующие полигоны будут выглядеть на неаксиальной геометрии?

__________________
http://www.moddb.com/mods/monorail-quest

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Компилятор уровней в формат XashNT всё так же будет резать браши через определённые промежутки, пусть и не такие большие?

Crystallize лайтмапы-то большие, можно практически не резать.
Во всяком случае это лучше, чем пытаться уменьшить лайтмапу, как ку3 делает.

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

Дядя Миша
В ку3 ты можешь сам порезать большие браши в Джеке, где надо.

__________________

Очевидно в джеке можно порезать брашы для любой карты

Я кстати понял, откуда взялась внезапная оптимизация дерева даже для тех карт, где нет никаких детайлов.

1

for( i = 0, data = g_uncompressed; i < leafnum; i++, data += g_bitbytes )

2

{

3

  if( !memcmp( data, outbuffer2, g_bitbytes ))

4

  {

5

    g_dleafs[g_leafstarts[leafnum]+1].visofs = g_dleafs[i+1].visofs;

6

    c_reused++;

7

    return;

8

  }

9

}

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

__________________

1

for( int i = 0; i < numleafs; i++ )

2

{

3

  for( int j = i + 1; j < numleafs; j++ )

4

  {

5

  }

6

}

__________________
My Projects: download page

F.A.Q по XashNT
Блог разработчика в телеграме

__________________