В телеграм я пока не пишу, естественно выложу ссылку.
Итак, дальнейшая работа над декомпилятором уровней сталкера продолжена быть не может. Почему? Очень просто. Вопрос и раньше вставал, но теперь уже без вариантов - надо заняться коллизией.
Нет нормального механизма. Собственно вариантов коллижен-детектора в природе существует два штуки: полигональный и конвексный. Я не рассматриваю случаи столкновения сфера vs бокс, сфера vs цилиндр, так как речь, естественно, о коллижен детекторе произвольной геометрии.
Полигональный - это конкавный детектор, т.е. геометрия может быть произвольной формы. Конвексный работает только с выпуклыми телами, а невыпуклые тела разбиваются на выпуклые (декомпозиция). Частным случаем конвексного детектора являются и нашы брашы. Просто в большом геймдеве их брашами давно никто не называет, ну конвексный объект и всё.
С брашами преимущество было в том, что дизайнер заранее строил уровень из конвексных объектов. Но в подходе к генерации брашей заложена мина - их качество очень сильно привязано к точности вещественных чисел. А точность вещественного падает (экспоненциально?) при удалении от центра (нуля). Вальва в сорсе даже замутила такой хак, что все брашы перед созданием сурфейсов принудительно перемещались в центр, а потом возвращались обратно - для большей точности результатов. Но это конечно так себе выход - ошибки всё равно накапливаются. Именно поэтому кстати BSP\CSG и работают с двойной точностью вещественного, уж слишком видна разница. Но зато с такими объектами очень просто реализуется коллизия - минимум операций, всегда предсказуемые результаты. Собственно, когда встал этот вопрос - как коллидить с объектами произвольной формы, Кармак из каждого полигончика сделал такой тонкий браш.
Но с оговорками. Во первых это было сделано только для параметрических поверхностей - т.е. патчей. Которым можно регулировать уровень разбиения и таким образом создавать более грубое приближение. Но уже для вставляемых на карту моделей делать что-то подобное он отказался (в ку3 кстати где-то было коммент на эту тему в исходниках, слишком много полигонов). Впрочем тогда и компутеры были слабже. Так-то подход неплох в целом. Например я использовал его в XashXT генерируя брашы налиту и каждый кадр для физических объектов. Разумеется, тех объектов, которые мне сделал PhysX из полигональных.
А там действовало жесткое ограничение - максимум 256 полигонов на твёрдое тело. К тому же брашы генерились только непосредственно перед коллизией (когда монстр\игрок оказывался слишком близко от тела и не перестраивались, если его положение не менялось, поэтому оно практически не тормозило). Именно поэтому мне многие говорили, что в XashXT очень приятное взаимодействие игрока с физтелами - его как буто реально чувствуешь, а не проваливаешься в него или оно улетает куда-то от малейшего прикосновения. Но в целом такая схема оправдана быть не может. Всё же слишком много операций. В Параное-2 я пошёл еще дальше, физикса там уже не было (Элбер сказал, что на физику ему плевать, но рагдолл бы не помешал). Там я этот подход переписал на качественно новый уровень, ввёл хэширование плоскостей и другие ускоряющие операции. Да и сами брашы коллизий сохранил в кэш, чтобы не строить его каждый раз при загрузке уровня. Но и всё равно, генерация таких вот брашей для той же ЧАЭС занимала порядка получаса, а плоскостей получалось около 10 миллионов
Происходило это потому, что каждый такой браш, полученный из полигончика создаёт дополнительно вовсе не четыре стороны, как может показаться (для треугольника). Дело в том, что сам механизм трассировки плотно завязан на аксиальность плоскостей. Иными словами брашы, повёрнутые на любой угол, отличный от 90 градусов нормально коллидить не будут. По крайней мере с оригинальным кодом от Кармака. Потому что вокруг каждого браша должен быть во первых описывающий его объем AABB который всегда аксиальный (из него кстати для любого браша можно узнать его AABB - первые шесть сторон всегда аксиальны и отсортированы в едином порядке, это справедливо и для ку2 и для ку3). Второй момент заключается в том, что на проблемные места - острые углы, добавляются бевелы - скосы. Чтобы трасса не застряла в этом проблемном угле. Игрок это никак не ощущает на самом деле. Для него наоборот физика очень мягкая и предсказуемая. Но как вы понимаете, таким образом, у нас во первых каждый браш должен состоять минимум из шести сторон. А бывает и до 32-х, причём реальный полигон там только один, четыре закрывающих, еще парочка аксиальных, остальное бевелы.
Т.е. нетрудно догадаться, сколько места займет такая вот коллизия, даже несмотря на отсутствие в данных вертексов и тот факт, что там нет дублирующихся данных. На этот вопрос очень легко ответить - для той же ЧАЭС коллизия, построенная таким вот образом весила порядка 80 мегабайт. Сталкеровский оригинальный cform - 20 мегабайт. Да и строился он наверняка быстрее, хотя я и не проверял.
Так что в принципе превращать полигоны в брашы - не очень хорошая идея, когда у вас этих полигонов слишком много. Есть более экономный вариант, как вы понимаете. Для этого нам надо превратить нашы полигоны в конвексные брашы. Т.е. не каждый полигончик превратить в отдельный браш. А выполнить конвексную декомпозицию. Из-за чего кол-во брашей в такой коллизии падает в десятки раз, а качество коллизии - наоборот только возрастает. Т.е. на первый взгляд сплошные плюсы.
Но не всё так просто. Во первых нам надо еще построить конвексный хулл для нашего объекта. Хулл можно построить двумя способами - собственно декомпозицией, voxel-based аппроксимацией и вписанием объекта.
Последний вариант - самый простой. Мы просто берём минимальный нулевой объем и добавляем в него новую точку, а умный алгоритм из этого облака точек уже сам создаёт конвексный хулл (это кстати к вопросу, почему физ.движки не требуют полигоны, а именно точки для создания конвексных хуллов). Алгоритм простейший, скорость работы высокая. На выходе что-то очень конвексное. Если этот объект динамический и размерами меньше игрока, то пофиг. Если это статическая геометрия, ну скажем домик деревянный с интерьером, метод очевидно не конает - внутрь зайти будет невозможно. Остаётся декомпозиция. Можно декомпозировать через BSP-дерево, т.к. любой объект, пропущенный сквозь него становится конвексным. А потом мы просто берём полученные конвексные брашы и мержим их друг с другом, пока это возможно. Я использую этот подход для патчей и он себя неплохо зарекомендовал. Для произвольного набора треугольников ситуация сильно хуже. Нет никакой возможность различить где реальная геометрия, а где остатки от исходного браша, иссечённого деревом. Дерево можно строить и наоборот - добавлением, но там получается строго обратная проблема - часть брашей исчезает. В реальном игровом уровне такой проблемы не стоит, т.к. дерево сечёт изначально конвексные объемы. Так что метод рабочий, но да, не слишком надёжный для большого полигонажа. Опять таки он из плоскостей делает объемные штуки, что не всегда удобно. Про VHACD распространяться не хочу - очень долго и очень затратно по памяти. Воксели вообще много жрут, это понятно. Но какую-нибудь сраную модельку, которую BSP декомпозирует за полсекунды, воксельное дерево может считать до полуминуты. Так что этот вариант я не рассматриваю.
Ну и наконец вариант третий - полигональный детектор. Плюс в том, что нам не надо переводить наши полигоны в какие-то принципиально иные сущности - т.е. мы реально трейсим геометрию. Так же геометрию очень легко симплифицировать через тот же Progressive Mesh, например (собственно в Сталкере так и сделано). Но есть у такого подхода два минуса. Во первых, поскольку мы трейсим реально полигон, за ним нет никакого объема (ну в крайнем случае там будет солидный лиф, если мы поместили всё это в BSP-дерево). Поэтому из-за каких погрешностей вещественных очень легко получить результат когда объект пролетает насквозь или застревает в текстурах, ну понятно. Второй минус вытекает из первого - невозможно таким образом сделать нахождение в среде, типа воды или кислоты. В Doom3 где коллизия полигональная задачу решили при помощи брашей. Т.е. браши там остались только для тестирования на нахождение внутри геометрии, в том числе - внутри воды.
Так что вот такие варианты.
Добавлено 10-09-2020 в 15:43:
Итак, исходя из вышесказанного, кокова кота выбы выбрали? что тут можно сделать? У полигональной трассы, не говоря уже тяжёлый алгоритм, собственно трассировки, присутствует некоторая избыточность. Т.е. эти данные в любом случае займут довольно много места, именно поэтому коллоизационные поверхности симплифицируют. Пытаться построить из произвольной модели конвексную декомпозицию - занятие, скорее всего довольно-таки долгое. Особенно если моделей много и они сложные.
И да, чаще всего это всё равно будет приближение. Превращать каждый полигончик в отдельный браш - это очень быстро, но влечёт за собой большие расходы памяти. Но есть один метод. На самом деле - все вот эти скосы и аксиальные планесы, точнее код, который их добавляет к брашу, обладает одной примечательной особенностью, над который вообще мало кто задумывается, а именно - ему плевать на замкнутость браша! Ему плевать на то, сколько у браша сторон. Для нас как бы самое важное - это построить виндинг, а для нормального браша это реализуется только путём взаимного обрезания сторон, как вы понимаете. Но мы рассмотрим вырожденный случай - браш из одного полигона. Прикол в том, что этому брашу бевелы и ограничивающее пространство добавляются точно так же как и настоящему брашу. Это не голословное утверждение - в параное именно такой подход и используется. Т.е. если бы я там делал из полигонов настоящие тонкие брашы, можете не сомневаться, там на ЧАЭС было бы не 10 миллионов плоскостей, а все 40. Второй момент - таким полигонам вовсе необязательно состоять непременно из трёх точек. Проще говоря, там может быть сколько угодно сторон. Главное чтобы он продолжал оставаться конвексным. Это в свою очередь открывает широкие возможности по оптимизации исходной геометрии, поскольку брашы фактически строятся из полигонов, без добавления лишнего. Плюсы такого подхода:
1. не надо ничего глобально переписывать, изменения минимальны
2. надёжность такой коллизии полностью идентична обычным брашам, причём, алгоритм даже не знает что перед ним какие-то полигоны
3. поскольку полигон двухмерен, его легче оптимизировать, наконец можно строить брашы из группы аксиальных полигонов, которые примерно направлены в одну сторону, независимо от того, сколько их там, бевелов будет добавлено кратно меньше, чем если бы мы попытались сделать браш из каждого полигончика. Строго говоря, такая конструкция уже вообще не является брашем с точки зрения редактора или дизайнера. А вот с точки зрения коллижен детектора - очень даже является.
4. униформное хранение данных. Плоскости индексированы, а у сами плоскостей дополнительно индексированы нормали. Т.е. при разумном подходе можно очень сильно сократить данные.
5. скорость работы. Даже при тех десяти миллионов полигонах, помещенных в простейшее AABB-дерево, коллизия на ЧАЭС была довольно таки надёжной и быстрой. А ведь можно было сделать на порядок умнее.
6. Наконец никто не мешает пропустить набор треугольников через дециматор и получить на выходе упрощенную копию. К слову сказать - дециматоры тоже очень быстро работают, это весьма простая операция.
Но конечно надо будет затестировать различные варианты и посмотреть, какие лучше годяцца.
Учитывая вышесказанное, как вы уже догадались, я в первую очередь попытаюсь дожать именно коллизию по полигоно-брашам. И если результат меня устроит (ну скажем общий объем данных коллизии будет меньше чем в сталкере), то тогда уже можно будет рассмотреть вопрос об используемом дереве.
В заключение хочу сказать пару слов о том, почему я иногда выбираю те или иные решения. На самом деле, я не ставлю себе догмы, что BSP устарел и его надо срочно дропнуть и не особо оглядываюсь на другие проекты, ну типа в сталкере октри, значит и мне тоже надо. В первую очередь, я всегда пытаюсь выжать максимум из уже имеющейся технологии, сделать что-то такое, чего возможно еще никто не делал.
Это интересно. А пихать в движок всего подряд по принципу - на дворе 2020й год, нам срочно нужны воксели - не очень.
Добавлено 10-09-2020 в 15:46:
И да, я очень люблю униформный подход, он потенциально обеспечивает будущие возможности, о которыхна момент разработки никто не задумывается.
ncuxonaT сам формат cform я еще не разбирал, но визуально он выглядит как сплошная полигональная геометрия. А уж из скольких кусков он состоит и как эти куски помещены в дерево, я не смотрел.
У превращения полигонов в браши есть главный минус - такая дата много весит. Во всём остальном сплошные плюсы. То есть задача - симплифицировать эту геометрию. Но ведь для полигональной коллизии это тоже нужно. Значит в любом случае этим займусь.
Добавлено 10-09-2020 в 17:22:
Цитата:
ncuxonaT писал: В сталкере геометрия для коллизий считалась автоматически для целой карты?
если вопрос о том, что считал геометрию (я отвечал немного на другое), то да, компилятор из видимой автоматически делал. Утилита qSlim. Она же и прогрессивные мешы создаёт для видимых.
Дядя Миша писал: Хулл можно построить двумя способами - собственно декомпозицией, voxel-based аппроксимацией и вписанием объекта.
Последний вариант - самый простой. <...> Остаётся декомпозиция.
>два способа, по факту перечислены три формулировки
используй скобки пожалуйста, а то бывает так:
>вижу три формулировки
"последний вариант-самый простой"
ок, остаётся ещё два.
"Остаётся декомпозиция"
я: ????
Дядя Миша писал: Для нас как бы самое важное - это построить виндинг, а для нормального браша это реализуется только путём взаимного обрезания сторон, как вы понимаете.
Так получается что природа брашевой геометрии состоит не в BSP-дереве, а именно в виндинге?
Crystallize писал: >два способа, по факту перечислены три формулировки
Ох. Voxel-based это тоже разновидность декомпозиции.
Цитата:
Crystallize писал: Так получается что природа брашевой геометрии состоит не в BSP-дереве, а именно в виндинге?
Природа в том, чтобы была возможность манипулировать сторонами браша всегда при этом получая конвексный объект. С плоскостями это проще всего получается. Если бы объект был вертексным, проверка на конвексность заняла бы гораздо больше времени. А так всё просто - любые нековексные включения тут же уничтожаются при построении браша. Т.е. генерация из плоскостей реальной геометрии - гарантия конвексности. Ну и конечно тот факт, что у браша не может быть слишком много сторон - обычно 128 максимум.
Добавлено 10-09-2020 в 20:17:
Цитата:
Crystallize писал: не в BSP-дереве
да дерево тут вообще непричём
Дерево это способ разделения пространства. Просто так уж получилось, что BSP чуть ли не единственное, которое реально режет геометрию, из-за чего с ним не любят связываться. Впрочем есть разновидность BSP дерева, которое ничего не режет, но оно менее эффективное, т.к. опирается на уже существующие разрезы.
Вот что мне удалось выяснить. Основных алгоритмов существует две штуки.
Quadric Error Metrics (QEM) от Мишеля Гарланда. Имплементация называется qSlim, была впервые выпущена в 1998-м году, а в 2006-м её автор устроился в NVidia, где вероятно пребывает и по сей день. Но это это не точно.
Вот страничка https://mgarland.org/software/qslim20.html
Собствено именно эту реализацию использует XRay. Алгоритм хороший, но при пороговых значениях полигонов начинает быстро терять детали. Зато в оригинальной имплементации масса всяческих настроек и обратная связь, отслеживания пороговой деградации меша. Ну то есть, когда кол-во полигонов снижается до критического уровня и он перестаёт сохранять свою форму в рамках заданной погрешности.
Второй вариант Progressive Mesh от Stan Melax. Это тоже известный чувак в геймдеве. Вот его страничка http://www.melax.com, алгоритма там уже нет, но насколько я понял, он так и называется по имени автора - Melax.
У него есть git где всё это и выложено: https://github.com/melax/sandbox
Имплементация PM называется bunnylod, именно её я когда-то использовал для симплификации мешей в VHLT CB для ускорения трассировки. Впрочем я не проверил тогда результат визуально, так что возможно где-то ошибся - в тенях частенько бывали дыры.
Его алгоритм на порядок проще и даёт гораздо более устойчивые варианты при слишком низком поликаунте, там где QEM уже обсирается.
Но нет никаких настроек. На git обновлённая версия алгоритма, оригинальную можно найти например здесь: https://github.com/dougbinks/BunnyLOD И кстати, автор убрал ссылку, но сам файл лежит на прежнем месте: http://www.melax.com/bunnylod.zip
У самого Стэна так же есть множество любопытных вещей, которые занимали нашы умы в начале нулевых, в частности - геомод на BSP-дереве (sandbox\testbsp, sandbox\testbool), на сайте есть уже откомпиленное. Вы же всё спрашивали за геомод, ну вот.
Теперь надо выбрать между этими двумя алгоритмами или использовать оба. Тут вот какой еще важный момент - вертекс можно перемещать без особых проблем, нормально можно рассчитать заново, но это не касается координат текстуры и лайтмапы.
Добавлено 11-09-2020 в 12:36:
То что касается меша коллизии, здесь как бы ответ однозначен - надо симплифицировать по максимуму. Качество коллизии от этого только вырастает. А вот насчёт видимой геометрии - тут всё не так однозначно.
Помните я говорил, что лоды в наше время не имеют определяющего значения, потому что главная нагрузка идёт на пиксельный конвейер, а он в свою очередь эффективно лодируется мипами? На gamedev.ru народ в начале десятых тоже жаловался, что от использования лодов фпс в лучшем случае вообще не меняется или даже немного падает. Когда у нас был фиксированный конвейер и вертексы-индексы прокачивались по шине, смысл конечно был. Сейчас - не знаю. Но в любом случае надо провести эксперименты конечно.