Вместо предисловия. Только хорошая мотивация может побороть природную лень, собственно ничего не добавить и не прибавить – написать статью описывающую рендеринг ландшафта я собирался давно, собирался, собирался, собирался… И увидев приз – подписку на MSDN наконец собрался. Еще один disclaimer: статья мной субъективно оценивается как средняя по уровню, я не разжевываю здесь все базовые вещи (например что такое матрица проекции, как организован основной игровой цикл XNA, что такое шейдер и т.п.), так что статья рекомендуется к прочтению людям у которых есть некий опыт программирования в XNA и они наконец задумались о такой насущной в игре вещи как…
Ландшафт
Открытые пространства в современных играх встречаются повсеместно и в самых разных жанрах: RTS, FPS, RPG, MMORPG – в большинстве игр этих жанров действие так или иначе происходит на поверхности. Само слово еще вначале XIX века трактовали как “окружающую наблюдателя территорию, которую можно осмотреть единым взглядом”. Что-то близкое к геймдеву, не так ли?!
Все, что мы хотим изобразить на мониторе компьютера, должно иметь какую-то математическую модель, возникает закономерный вопрос – как описать местность? Есть несколько вариантов известных мне.
Воксели
Увы мне, я не художник, но постарался изобразить некий объем разделенный на равные части и у этих частей образно есть атрибут (назовем это цветом), в нашем случае говорящий заполнена ли часть объема (в нашем случае землей, снегом, водой, да мало ли вариантов) или нет. Как это выглядит в реализации – в простейшем случае у нас есть бооооольшой трехмерный массив, в котором записаны данные. В чем плюсы: можно задать самый замысловатый ландшафт – нависающие арки, скалы с обратным уклоном, гроты и т.д. и т.п… Из минусов нетривиальность исполнения, большой расход памяти.
Воксели + немного мамбо-джамбо
Вообще говоря массив из предыдущего пункта можно рассматривать как результат некой функции v=f(x,y,z) , где область допустимых значений этой функции {-1,0,1} , говоря человеческим языком функция каждой точке трехмерного пространства сопоставляет -1, если эта точка под землей, 0 если точка поверхность земли и 1 если точка над землей. Этот замечательный подход иногда используют при процедурной генерации ландшафта. С другой стороны если вы поклонник математического анализа и разбираетесь в рядах так, что Тейлор и Фурье вам позавидуют, то для вас, наверное, не составит труда сделать обратную операцию, а именно из массива сделать функцию. Функция эта, учитывая конечность элементов ряда в реальной жизни, будет не совсем тем, что хочется, а с ошибкой, но тут уж как говорится “селяви”, больше членов – больше точность. В общем и целом на этом фронте может быть множество интересных идей и воксели будоражили, и будут будоражить умы энтузиастов с самой эры зарождения компьютерной графики, но в основном мы поговорим о гораздо более часто используемом, простом (здесь, как и везде простота - относительное понятие) в реализации и понимании способе.
Карта высот
Почти все модели в науке и технике упрощены, они позволяют нам представлять некий объект с определенной точностью, но естественно не являются самим объектом, не описывают всех его свойств и поведения. Например, представление о том, от какого полюса к какому движутся электроны, менялось вроде бы не один раз, что не мешало довольно успешно пользоваться телеграфом, электрической дугой и прочим и прочим. В нашем случае упрощение тоже имеется, мы будем строить ландшафт по высоте. Т.е. любые две координаты x и z дают координату y, которая показывает высоту поверхности над абсолютным уровнем, если присмотреться, то видно, что из уравнения общего вида в предыдущем пункте, по сути, исключили одну переменную, теперь оно такое y=f(x,z), что с одной стороны дело существенно упрощает. С другой стороны лишает таких вкусностей как многоуровневость ландшафта, никаких арочек, обратного наклона и прочих радостей без плясок с бубном. Что это означает для реализации, а то, что нужен не трехмерный массив, а двумерный и выполнить его можно с определенной дискретизацией. Если еще проще, пусть у нас есть GPS, берем участок 100x100 метров и дальше обходим его и записываем результаты замеров высоты, если замеры мы будем делать через каждые 10 метров, то у нас получится табличка примерно такого вида:
H(0,0)= 5 метров
H(10,0)= 6.53 метра
…
H(100,0)=12 метров
H(0,10)= 5.2 метра
H(10,10)=5.4 метра
…
H(100,100)=10.5 метров
Неглупые люди решили, что такие данные для обработки удобно хранить в картинках, т.е. теперь представьте, что есть картинка с размерностью 101 пиксель на 101 пиксель. И в, например красном, канале каждого пикселя мы будем хранить значение высоты для соответствующей точки или распределять эти значения по всем трем или четырем байтам – тут все зависит от потребностей, формата хранения, фантазии наконец. В результате получаются картинки такого плана:
Австралия
Земля целиком
Как нетрудно заметить более высокие места – более светлые. Вот и все общее описание принципа. Для того, чтобы создавать карты высот совершенно не обязательно бросаться к Paint’у и судорожно настраивать цвета в палитре. На текущий момент создано немало инструментов, которые помогут создать собственные карты, достаточно лишь погуглить на предмет “heightmap editor” и вам откроются бездны и бездны, в том числе и 3D редакторы, но мне для начала хватило простенького hme.
Дьявол в деталях
На словах все довольно просто, но когда дело доходит до реализации могут возникнуть определенные сложности и, наверное, одна из самых интересных в этом плане задач, это получение больших ландшафтов, миллион квадратных километров с детализацией скажем в 10 метров, да только хранение такого объема уже гигабайты или небольшие площади, но с огромной детализацией, что в принципе одно и тоже. Но мы спустимся с небес и при вполне земной задаче 1025x1025 точек у нас уже два миллиона треугольников на экране. Пусть даже многие из них будут отсечены при куллинге, поверьте оставшихся хватит для того чтобы притормозить ваш даже очень навороченный комп. А ведь большинство этих треугольников настолько далеки, что куча таких умещается в одном пикселе – шейдеры вхолостую “прокачивают” совершенно ненужные данные. Здесь-то на помощь и приходят множество алгоритмов под общей аббревиатурой LOD (Level Of Detail – уровень детализации). Эти алгоритмы позволяют эффективно отсечь лишнее и аппроксимировать удаленное для адекватного рендеринга. При изучении материала мне гораздо больше помогли ссылки присланные ребятами на форуме, за что им огромное спасибо.
Я же тем времен скромно продолжу рассказ о том, как сделать ландшафт с ROAM (Realtime Optimally-Adapting Meshes) .
Предполагаю, что вы знакомы с построением каркаса приложения на XNA и поэтому думаю следующее действие не вызовет затруднений – в проект в качестве контента мы добавим текстуру, которая является не чем иным как картой высот. У меня она в bitmap формате:
Следующим шагом будет создание класса, ответственного за визуализацию ландшафта. Назовем его емко и глубокомысленно – Terrain. В моей архитектуре это просто класс, но в принципе его вполне можно реализовывать как наследника DrawableGameComponent.
Все самое важное мы сделали ? Остались остальные 80 % работы. У нас есть текстура, в которой хранятся данные о высотах, нам нужно при инициализации получить из нее данные.
Пресловутая текстура – это heightTexture, я надеюсь сказать _heightTexture = Game.Content.Load("heightmap"); вы вполне перед этим сумеете. Итак в вышеописанном методе мы получаем массив цветов с помощью метода Texture2D.GetData, затем пробегая построчно по массиву (хоть он и одномерный, но мы же ведь знаем размер строчки (i + j*_heightTexture.Width – формула простая, но она будет еще долго фигурировать в работе этого компонента, так что лучше сразу уясните, если вдруг что то не ясно, как из одномерного массива сделать двумерный). После такого мы обязаны жениться заполнить вершинный буфер.
Для примера я использую стандартный VertexPositionColor, при текстурировании можно и нужно будет использовать другие форматы вершин, но сейчас этого достаточно. Дальше начинается самое интересное – для прорисовки нам не хватает индексного буфера, он будет заполняться динамически и индексы нам будет помогать определять класс TerrainTriangle. Для того, чтобы подробно объяснить его логику работы постараюсь для начала описать алгоритм в целом.
Изначально весь регион представляется двумя треугольниками:
Если какой либо из треугольников в видимом пространстве занимает больше определенной части размерности экрана (в моем примере eps = 0.1f):
Здесь lPos, rPos, tPos, vCenter – соответственно левая, правая, верхняя и центральная координаты треугольника. Вообще говоря на них можно и экономить память, т.е. вычислять эти Vector3 в процессе держа только индексы вершин, потому как сетка эта займет в памяти
треугольников, однако помним, что экономя на памяти теряем на производительности, так что я так не ухищрялся.
Далее треугольник, который признан слишком толстым делится пополам, а так же делится его сосед снизу и если не был разделен треугольник являющийся “родоначальным” (треугольник из которого делением пополам образовался этот), то делится и он. т.е.:
И этот тоже разделим. Получим :
Здесь показан принцип деления, который отражает метод:
bNeigh – здесь треугольник который является примыкает к стороне разделяемой пополам. А т.к. метод применяется для всех треугольников из изначального набора (напомню их вначале 2), то он охватывает все сегменты.
Из всего этого можно понять, что ROAM обладает таким свойством как инертность, т.е. в самом начале рендеринга нас ждет адаптация (что ясно из названия метода и которая всегда требует некоторого времени) к текущим условиям, впрочем на глаз чаще всего незаметная. Так что если вы планируете пролеты со скоростью пули на тысячу километров над уровнем местности – может стоит подумать о другом методе (или поумерить амбиции), в любом случае об этом свойстве метода стоит помнить.
Следующим шагом мы соберем все треугольники на которых остановилось деление в список:
Пока не стоит обращать внимания на ConcurrentStack, про оптимизацию и многопоточность мы поговорим дальше. Здесь стоит внимательно присмотреться к самой логике проверки на “склеиваемость”, при потенциальной возможности склеить (см. предыдущее свойство) проверяется достаточно ли мал треугольник и не нужно ли дробить его соседа снизу. Если эти условия соблюдены, то в список для склейки добавляются треугольник и его нижний сосед. Только следует иметь в виду, что вся эта проверка и добавление проводятся на родителях конечных треугольников:
Если у вас ум заходит за разум, ничего – на все требуется время и обстоятельные размышления никому еще не навредили. Пройдитесь по тексту глазами, разберитесь по шагам что к чему. Напоминаю, что у нас остался сухой остаток leftOverList, что делать с ним – все просто, если такой треугольник не является разделенным, то его добавляем к отрисовываемым:
Еще поясняю маленький момент с условием, который может ускользнуть от внимания – помните в самом начале у нас было два треугольника, покрывавших весь регион местности, а теперь подумайте, что будет если повернуть камеру “в небо”. Мы можем потерять все треугольники, и в следующей итерации просто не из чего будет строить сетку.
Таким образом, из раза в раз мы адаптируем наш набор треугольников к изменившимся условиям. Эту операцию естественно не обязательно делать каждый Update, можете обратить внимание - в проекте, прилагающемуся к статье есть интерфейс IDirected, который предоставляет события PositionChanged и IDirectionChanged, а ICamera является его наследником. Таким образом апдейт ландшафта можно привязать к изменению состояния наблюдателя (его перемещения или поворота), что существенно скажется на производительности, обязательно поэкспериментируйте на эту тему. Все необходимое для этого есть в примере. Только не забудьте, как это честно сделал я, что нужно убедиться, что сетка адаптировалась до конца, иначе вас ждет довольно забавное поведение вашей местности. Ну и осталась техника… Нам нужно заполнить индексный буфер, здесь нам поможет helper-класс, который мне понадобился больше из-за того, что моя фиговенькая видюшка на работе не позволяла адресовать в индексном буфере больше Int16 точек, а добрая NVidia 8800 GTS уже с 92-ым (могу ошибаться) процессором дома позволяла еще и не такие чудеса:
Сей дженерик-класс позволяет инициализировать индексный буфер изначальным списком вершин, справляется с потерей устройства и позволяет обновлять себя без лишнего геморроя, ну и личный упоминавшийся бонус вряд ли кому еще полезный – возможность выбирать размерность адресации:
Из кода видно, что всего лишь использую BasicEffect, однако если держать в уме, что сам класс Terrain это не DrawableGameComponent и заглянуть чуть выше по стеку вы увидите метод Draw откуда все это хозяйство вызывается, там происходит любопытная вещь, такая как ResetRenderStates(). Название у нее вполне самоописательное, а нужна вся эта котовасия, потому как вы наверняка будете рисовать что-то поверх свое - курсор, FPSы ( соответсвующий компонент кстати прилагается - только имейте в виду, он сделал “честным”, больше чем было вызовов Draw в секунду не покажет).
Теперь несколько слов об еще одном улучшении классики, этот алгоритм я выполнил с помощью библиотеки ParallelFX , что позволило выполнять операции разбиения треугольников и их слияния, задействовав все возможности ваших многоядерных процессоров. Обратите внимание на класс ConcurrentStack , именно он позволяет нам добавлять треугольники из разных потоков без риска, само же использование библиотеки интуитивно просто. Да, имейте в виду это - CTP, хоть и вполне рабочая превью, но все же превью.
Ну и давайте полюбуемся на результат, мы этого заслужили:
Не слишком впечатляющий результат с точки зрения графики? Вы абсолютно правы и именно поэтому в следующей статье (будет, будет, неужто за месяц не напишу, я же хочу прыз) мы будем ландшафт текстурировать, затенять, научимся получать точку на местности по точке экрана, в планах так же эффекты типа указателя на поверхности (кто помнит геймплей WOW или Neverwinter Nights и заклинания по области тот поймет о чем речь), возможно дойдут руки до билбордов и простенькой зелени, ну и мы обязательно украсим сцену каким-нить красивым небом (веротяно пока статичным ). Как видите планов громадье… Если понравилось – пишите, если не понравилось – пишите тоже, с интересом буду ждать комментариев.
треугольников, однако помним, что экономя на памяти теряем на производительности, так что я так не ухищрялся.
Vova
