Ну во первых, я пока что не пришёл к однозначному выводу. Просто такая коллизия должна переиспользовать уже существующие вертексы, что положительно скажется на финальном размере карты. А коллизия по плоскостям генерит слишком много этих самых плоскостей, несколько миллионов. Оно и в параное так было, посмотри размеры клипмапы для ЧАЭС.
Добавлено 06-11-2020 в 09:41:
Цитата:
ncuxonaT писал: Ты хочешь строить какую-то единую структуру для всей карты со всеми елками?
Зависит от сложности симуляции. Для простой халфовской физики, можно хранить все объекты в локальном пространстве. Но для симуляции твёрдых тел, подобный подход уже не слишком удобен, хотя и тоже возможен.
Я вообще не хочу с физикой особенно заморачиваться, как выяснилось, она мало кому нужна. Единственное что народ котирует - это разрушение. Тотальная деструкция.
Еще одну забавную вещь обнаружил. Фрустум использует коллижен три для определения пересечений видимости и отсечения невидимых, нет не полигонов, скорее всего целых моделей, аппроксимированных до ббокса.
Вместо запроса OQ. Впрочем такой подход, предполагает геометрию, оптимизированную особым образом и не слишком вяжется с брашевыми уровнями. Тут скорее надо чтобы уровень был разбит на достаточно большие куски.
Дома Noesis окончательно сломался, вылетает при запуске, ничо не помогает.
Но на работе воркает, я его запустил и проанализировал кусочки террайна от сталкеровской карты. И вот что выяснилось - сплиттер вообще не анализирует геометрию на предмет пространственной принадлежности.
Он скорее смотрит, чтобы у вертексов не было соседей. Т.е. эти куски, на которые разбит ландшафт могут проходить через всю карту.
Решил опробывать BVH-деревья для трассировки. Я хронически путаюсь с терминологии, поэтому до сих пор забываю, AAAB это подмножество BVH или наоборот. Ну да ладно. Вообщем деревья строго аксиальные.
Сталкер не имеет собственной подсистемы коллизии и юзает стороннюю, точнее связку ODE + OPCODE. Вот здесь конечно нейминг вводит в лютое заблуждение. Потому что OPCODE воспринимается как целое слово - операционный код для процессора\виртуальной машины. Хотя на деле это аббревиатурко от OPtimized COllision DEtection. Была такая библиотека, в начале нулевых. А еще до нее была библиотека RAPID, которую OPCODE, со слов автора превосходила в большинстве случаев минимум в 2 раза.
Ну и вот значит сталкер её использует для коллизии. Точнее первоначально её использует сам ODE для симуляции твёрдых тел. А сталкер использует именно как коллизию, в двух кейсах, понятно - точечная трасса и трасса ббоксом для всяких игровых ситуаций. Точечная трасса, луч, так же используется для лайтмаппера. А я, напомню, заюзал вальвовское KD-tree, переписав его на FPU. И в целом был доволен до поры, так сказать. до времени. Но выяснилась неприятная вещь. Оно адски долго строится, если полигонов много. На сталкеровских картах это может занимать несколько минут. Второй момент, как вы уже наверное, догадались, был связан с тем, что я хотел уйти от коллизии по плоскостям и мне для этого понадобилась новая структура организации данных.
Ну в данном случае OPCODE был просто первый, кто под руку подвернулся. Там в принципе хорошая кастомизация по выбору секущей, можно поэкспериментировать. Сам OPCODE предлагает кроме построения дерева еще и саму коллизию, но сталкер использует собственные методы, ну впрочем как и я. Итак, я заимплементировал это дерево самостоятельно, чёб не тащить целую либу ради такой ерунды и провёл предварительные тесты. Для тестов использовал карту shaderlab_terrain, там гигантская моделька гор, хоть и довольно низкополигональная. Результаты:
269960 total traces casted, 16641 luxels illuminated
9
total lightmap pages 1
10
CreateLightmapPages: 0.014780 secs
11
writing maps\shaderlab_terrain.bsp
12
active memory 0 bytes, peak memory 10.08 Mb
13
active strings 52
14
2 seconds elapsed
Как минимум один плюс тут есть - AABB-tree строится в сотни раз быстрее, чем KD-tree. Это обстоятельство, кстати позволяет самому сталкеру не хранить дерево на диске, а строить его каждый раз при загрузке уровня, т.к. это очень быстро. Как видно из статистики - профит во всём.
AABB-tree меньше весит, чем KD-tree, в десятки раз быстрее строится и чуть-чуть быстрее работает. Ну это пока навскидку. Буду проводить серию тестов.
6077427 total traces casted, 108036 luxels illuminated
9
total lightmap pages 4
10
CreateLightmapPages: 0.135933 secs
11
writing maps\gwdm2_.bsp
12
active memory 0 bytes, peak memory 10.08 Mb
13
active strings 199
14
1 minute, 25 seconds elapsed
Здесь вальвовское дерево в десятки раз быстрее. Хотя строится по прежнему дольше.
Добавлено 13-11-2020 в 23:03:
проверил еще кучу карт. KD-tree быстрее всегда. Кроме исключений когда построка дерева сопоставима по времени с рассчётом освещения.
учитывая что разрыв реально до 30 раз + 2д хэширование крайне неудачное в сталкере (там наоборот aabb-tree идеально подходит), я поверю что свет в сталкере считался неделями.
ncuxonaT ты не знаешь как строится AABB-tree?
Перебором всех треугольников, входящих в заданный объем, выбирается один из аксиальных углов. Нода разбивается на два узла. Каждая нода хранит ровно один примитив в конце разбиения. Поэтому можно заранее высчитать кол-во нод в дереве. Плохо то, что алгоритм просмотра рекурсивный и не поддается какой-либо оптимизации.
А у KD-tree вальвовского есть два важных момента. Во первых разбиение дерева оценивает даже не кол-во полигонов в узле, а кол-во операций, которые потребуются для трассировки этого узла. Т.е. стоимость сплита в опкодах. А во вторых сама трасса нерекурсивная, она просто перебирает в цикле ноды. Из-за этого производительность такая хорошая.
В любой трассе рекурсия это самое слабое место, самый главный удар по производительности.
Пока особо хвастаться нечем. По крайней мере по моим меркам.
Добавлено 14-11-2020 в 16:47:
Ну вообщем полная жопа. Сталкеровский рейтрейсер критически не годится для рассчёта лайтмап по своему быстродействию. Неудивительно, что они неделями ждали результата.
Добавлено 14-11-2020 в 16:48:
Посчитал свет на testers_mp_pool. Вальвовский рейтрейсер управился за 19 секунд, а сталкеровский считал 5 минут 9 секунд.
Добавлено 14-11-2020 в 16:50:
Справедливости ради отмечу, что оба рейтрейсера используют идентичный алгоритм пересечения луча с треугольником, который дополнительно оптимизирован путём предрасчётов некоторых значений и которого, разумеется не было в самом сталкере. Так что там вероятно, это время рассчётов было бы еще больше.
Добавлено 14-11-2020 в 17:04:
Вот вы говорите, релиз к привычной дате.
Чем тут хвастаться? фпс ниже плинтуса, коллизию вообще страшно включать. Единственное достижение - лайтмапа всего 7 минут считается.
Дядя Миша знаю, но хотел узнать детали, например, по какому принципу выбирается, где разбивать ноду.
Цитата:
Дядя Миша писал: кол-во операций, которые потребуются для трассировки этого узла. Т.е. стоимость сплита в опкодах.
Ничто не мешает делать так же в ААВВ дереве. Обычно это учитывают при расчете SAH.
Непонятно, почему а ААВВ траверс с рекурсией, а у кД нет. В чем разница?
Я знаю только бесстековый траверс, когда каждый узел хранит hit/miss линки, тут же нет рекурсии.
Я потом вероятно опробую еще какие-нибудь деревья.
Но в данном случае мною двигало любопытство - узнать насколько в сталкере эффективная трассировка лучей.
Цитата:
ncuxonaT писал: Непонятно, почему а ААВВ траверс с рекурсией
старый алгоритм на самом деле. Вероятно тогда над подобными вещами не заморачивались.