По ту сторону треугольников

Замечательная книга "GPU Gems" повествует о возможности использовать графический процессор для чего-то большего, нежели рендеринг составленных из треугольников моделей.

"По ту сторону  треугольников" - приблизительно так можно перевести с английского "Beyond Triangles" - название последней главы замечательной книги "GPU Gems". Она одной из первых рассказала массовому читателю о возможности использовать графический процессор для чего-то большего, нежели рендеринг составленных из треугольников моделей. Тогда это были главным образом научные расчеты: динамика жидкостей, визуализация результатов объемного сканирования, расчет стереограмм и т. д. Однако за прошедшие несколько лет ситуация радикально изменилась: на GPU были перенесены все классические алгоритмы и разработан целый ряд новых, максимально использующих преимущества, даваемые архитектурой современных видеокарт. Техника GPGPU[General-Purpose Computation on GPUs, вычисления общего назначения на графических процессорах] становится по-настоящему general-purpose, универсальной, подходящей для решения практически любых задач. Мне, как большому энтузиасту этой области компьютерных наук, хотелось бы рассказать об одном из самых многообещающих ее направлений: использовании GPU для расчета внутренней логики игр.

Отчего да почему

Дело в том, что обычно ядро игры устроено так: сначала на центральном процессоре рассчитываются все перемещения и взаимодействия объектов, изменение их формы (анимация), параметры среды и пр. Затем, с учетом всех этих данных, сцена (то есть набор моделей и спецэффектов) переводится все тем же центральным процессором в стандартное представление: набор координат вершин треугольников и их атрибутов (нормалей, цветов, текстурных координат и прочего). Полученный массив данных, зачастую довольно большой, пересылается на видеокарту, которая и занимается их выводом на экран: расчетом освещения, наложением текстур и применением различных спецэффектов. И хотя пропускная способность шины процессор-видеокарта за последние годы подросла довольно сильно, она до сих пор зачастую является "узким местом" при программировании игр. Поэтому весьма соблазнительно избежать этой пересылки и реализовать выполнение как можно большей части алгоритмов прямо на графическом процессоре.

Уроки физики

Чего не хватает современным играм, чтобы их наконец-то можно было назвать по-настоящему реалистичными? Поиграв во второй HalfLife на максимальных настройках графики, я уже совсем не уверен, что главным препятствием на пути окончательного переселения человечества в компьютерные миры является несовершенство визуальной составляющей. Несколько лет назад мне довелось повозиться с хорошим шлемом виртуальной реальности, и я не сомневаюсь: подай на него картинку уровня детища Valve, и достоверности изображения для девяноста девяти процентов случаев хватит с лихвой.

Другое дело, взаимодействие объектов игрового мира друг с другом и отклик их на действия человека. Лично меня при игре даже в самые динамичные игры вроде Warcraft III, Need For Speed, Grand Theft Auto или ту же HalfLife не покидает ощущение, что я попал в галактику, вдруг остывшую до нуля градусов по Кельвину. Планеты здесь подобно Луне лишены атмосферы, и ветер на них отсутствует. Дым и осколки разорвавшихся снарядов во всем подражают рентгеновским лучам и проходят сквозь тела, не причинив им ни малейшего вреда. Сами тела при этом сделаны из сплошного куска металла, но, разрушаясь, тут же растворяются в воздухе. Жидкостей здесь не бывает. Как, впрочем, и резины, дерева, глины или ваты.

Одним словом, играм чертовски не хватает качественной физики. И, положа руку на сердце, я не могу их винить. Обсчет физических моделей - это, пожалуй, самая трудоемкая и ресурсозатратная программистская задача из встающих перед разработчиками игр (сравниться с ней может разве что реализация приличного ИИ). Даже в самых новых и продвинутых шутерах количество одновременно обрабатываемых физической подсистемой тел измеряется десятками, максимум сотнями. Опыт же фотореалистичного рендеринга эффектов вроде разламывающихся стен, взрывов или текущей лавы показывает, что о каком бы то ни было реализме можно будет говорить не раньше, чем игровой движок сможет в реальном времени оперировать тысячами, а лучше десятками тысяч взаимодействующих друг с другом объектов. Причем речь идет не только о таких сравнительно несложных вещах, как столкновения или жесткие закрепления, но и о по-настоящему мощных математических приемах, например решении дифференциальных уравнений, описывающих связи объектов и поведение гибких или рвущихся материалов.

Таким образом, перед нами стоит задача: повысить скорость физических расчетов хотя бы на порядок. И, как уже давно догадался внимательный читатель, помогут нам в этом всемогущие шейдеры и запредельные мощности современных GPU.

Тут я тоже начну издалека. Идея снять нагрузку по расчету физики с явно не справляющегося с ней центрального процессора витает в воздухе не первый год. В числе прочих долгое время муссировалась и концепция специально сконструированного для этих целей сопроцессора. И вот в марте 2005 года никому не известная тогда фирма AGEIA, с кучей шума и надоевшего до зубовного скрежета пиара в околокомпьютерных изданиях, публично огласила свои планы по созданию физического акселератора PhysX. Употребленное здесь слово "акселератор" говорит сердцу бывалого игромана больше тысяч эпитетов и стопок хвалебных пресс-релизов. Оно, сердце, истосковавшись по былым потрясениям, вновь наполняется кровью и бешено колотится в предчувствии революции. Всего каких-то десять лет назад появление легендарного 3D-акселератора Voodoo Graphics взорвало рынок трехмерных игр, впервые дав ощущение реальности происходящего - и мы не забыли, как это было. Мы хотим еще.

Но давайте глядеть на вещи трезво. В отличие от видеокарты, работающей с потоками треугольников и пикселов, гипотетический PhysX должен будет эффективно справляться с обсчетом самых разных взаимодействий и математических моделей, разнообразие которых порой кажется мне даже большим, чем разнообразие реального мира. В возможность такого верится, прямо скажем, с трудом. Более того, по заявлению разработчиков, прямого API предоставляться не будет, и все программирование будет вестись через фирменную библиотеку. Негибкость такого подхода многим сразу же показалась фатальной, особенно если учесть, что главным конкурентом в борьбе за роль физического ускорителя выступает практически универсальный вычислитель - GPU.

Еще в 2002 году, выпуская на рынок Radeon 9700, корпорация ATI бросалась громкими заявлениями о переносе физических вычислений на карту и незамедлительном наступлении эры кинематографического качества рендеринга. Хотя за рекламной мишурой не стояло ничего, кроме нескольких лабораторных исследований и пары кривых прототипов, чаяния отрасли и научного сообщества эти слова отражали очень точно: в том, что считать физику на GPU можно и нужно, были уверены все. Так что никто из сторонних наблюдателей иллюзий по поводу будущего AGEIA не питал: все сходились во мнении, что nVidia и ATI постараются задавить начинание в зародыше. И вот буквально на днях битва за потребителя началась: 23 марта было объявлено о выпуске PhysX на рынок, а двумя днями ранее на GDC[Game Developers Conference] миру было представлено детище nVidia и знаменитых Havok - работающий целиком на карте физический движок Havok FX.

Анонсированная на второй квартал новинка продолжает сверхудачную серию физических движков Havok, использовавшихся в Max Payne 2, Age of Empires III, HalfLife 2, F.E.A.R. и еще доброй сотне самых крутых тайтлов последних лет, так что внимание разработчиков к Havok FX обеспечено.

Заявлено, что система будет работать на любых картах, поддерживающих Shader Model 3.0, то есть это линейки GeForce 6xxx и 7xxx плюс Radeon X1xxx. Более того, наконец-то в полную мощь заработает технология SLI: одна карточка будет заниматься просчетом физики, а другая - отрисовкой сцены.

Подробностей внутреннего устройства движка сообщается пока очень мало. В общих чертах устроено все будет так: к набору стандартных базовых типов объектов добавляется ряд новых, описывающих те структуры, которые удалось эффективно реализовать на GPU. Например, примитив Debris[Переводится это слово вовсе не так, как вы подумали, а "осколки", "обломки", "частицы"], абстракция твердого тела. Примитивы можно будет как задавать готовыми 3D-моделями, так и конструировать на лету силами центрального процессора. Последнее может оказаться особенно полезным при визуализации взрывов и прочих разрушений: например, размер и форма выбиваемых снарядами из кирпичной стены кусков будут зависеть от силы выстрела и места попадания. После того как описание объекта передано на карту, CPU им больше не занимается: все, начиная от расчета столкновений и заканчивая выводом треугольников на экран, делает графический процессор.

Обещан также некий высокоскоростной односторонний интерфейс, при помощи которого можно снабжать GPU информацией, необходимой для учета воздействия на игровой мир объектов, параметры которых хранятся не на карте, а в оперативной памяти. Очевидно, к таковым в первую очередь относятся управляемые системой ИИ вражеские монстры и все объекты, подконтрольные пользователю. В эту же группу с большой вероятностью попадают тела, форма которых задается параметрически или постоянно меняется.

Поддерживается и моделирование так называемых нечетких объектов (жидкостей, дыма), которые, как обычно, задаются системой частиц или сеткой узлов плюс набором дифференциальных уравнений, описывающих действие частиц (узлов) друг на друга и их реакцию на внешние силы. Судя по всему, в пакете реализован быстрый интегратор вроде входящего в небезызвестный пакет NovodeX. Ясно, что как раз тут прирост по скорости должен быть самым большим: уж что-что, а методы решения систем дифференциальных уравнений на массивно-параллельных системах изучены очень хорошо.

К лету nVidia и Havok обещают довести технологию до ума, так что к концу года можно ожидать первых игр с официальной поддержкой нового движка. До революции остались считанные месяцы, друзья.

С небес на землю

Как известно, две трети населенных пунктов России находится в сельской местности, где зачастую нет даже телефона. Что уж там говорить о паре видеокарт nVidia семейства GeForce 7xxx с поддержкой технологии SLI. Так что давайте обратим взор к разработкам, не требующим таких больших мощностей, но оттого не менее интересным. В конце концов, говоря, что на GPU можно делать что угодно, я ведь не врал.

Если вы смотрели чудесный мультфильм "Последняя фантазия" ("Final Fantasy: The Spirits Within"), то наверняка обратили внимание, как реалистично там выглядят волосы героев. Я был сражен наповал: и на плечи ложатся, и на ветру колышутся, и друг с другом переплетаются. И волосков там не два и не десять, а тысячи, десятки тысяч. Даже страшно представить вычислительную мощь, стоявшую за этим шедевром. Я это все к чему говорю: в сделанном пару лет назад к выходу GeForce 6800 демо-ролике "Nalu" одноименная русалка обладала шевелюрой сравнимой реалистичности. А просчитывалось все (не без участия GPU, конечно) в реальном времени. В играх я пока такого нигде не встречал, но, думаю, это лишь вопрос времени.

Другим довольно редким на экранах наших мониторов гостем является имитация одежды. Обратите внимание: плащи к персонажам игр насмерть прибиты гвоздями, в шляпы вделан титановый каркас, а все складки накрахмалены и для надежности пропитаны клеем-"момент". Но надежда есть: в последнее время стали появляться алгоритмы, позволяющие сравнительно недорогими средствами моделировать поведение ткани в интерактивном режиме. В простейшем случае поступают так: участок ткани представляют как решетку узлов, каждый из которых образует упругие связи с четырьмя соседями. Затем на каждом кадре последовательно: а) применяют действие гравитации, то есть сдвигают все узлы вниз в соответствии со временем, прошедшим с предыдущего кадра; б) проверяют, что расстояние между соседними узлами не стало слишком большим, в противном случае корректируют координаты узлов; в) следят за тем, чтобы узлы не проходили сквозь препятствия и, опять-таки, подправляют их положение в случае необходимости. Все три стадии элементарно переписываются в терминах операций над текстурами, и скорость выполнения получающегося кода весьма высока. Впрочем, в этом каждый может убедиться самостоятельно, скачав соответствующую программу, например, с сайта nVidia.

Еще одна весьма многообещающая техника - так называемые Coupled Map Lattices (CML). Многие из вас, наверное, слышали про математическую игру "Жизнь". Напомню правила. Место действия - двухмерный массив клеток, противоположные края которого во избежание граничных эффектов отождествлены: получается этакий дискретный тор. Каждая клетка может находиться в двух состояниях: она либо жива, либо мертва. У клетки, очевидно, восемь соседей. Задается распределение живых клеток в начале игры. Это "первое поколение". Каждое следующее поколение рассчитывается по таким правилам: 1) если у мертвой клетки ровно три живых соседа, она оживает; 2) если у живой клетки два или три живых соседа, она продолжает жить; 3) если же живых соседей меньше двух или больше трех, то клетка умирает (от одиночества и от перенаселенности соответственно). Задавая различные первые поколения, можно получать разнообразнейшие картины развития популяции. Так вот, если в игре "Жизнь" разрешить клеткам принимать не два состояния, а больше, и соответственно усложнить свод правил, по которым клетки переходят из одного состояния в другое, то как раз и получится CML. Оказывается, при помощи этих систем очень удобно моделировать целый ряд природных явлений, в частности кипение жидкостей, рост барханов и формирование облаков. Более того, эта техника как будто специально придумана, чтобы ее реализовали на графическом процессоре: N+1-е поколение (текстура) получается из N-го поколения (текстуры) применением одного и того же свода правил (пиксельного шейдера) к каждой клетке поля (пиксела текстуры). Замечу, что я писал такую программу для центрального процессора, и нормального быстродействия удавалось добиться лишь для сеток весьма скромных размеров. Здесь же все просто летает.

Идеологически чем-то похожи на CML и "боиды", при помощи которых уже двадцать лет моделируется поведение стай птиц, косяков рыб, облаков насекомых и т. д.["КТ" уже писала об этой технике] Если вкратце, каждый член стаи подчиняется трем простым правилам: избегай столкновений; двигайся туда же, куда и все; придерживайся центра стаи. А поскольку область зрения считается весьма небольшой, то движение каждой птицы определяется движением лишь нескольких ближайших ее соседей. Группа итальянских ученых еще в 2004 году написала целиком работающую на GPU мощную систему для моделирования передвижений больших стай птиц (с облетом препятствий, включая динамические) и отрапортовала об отличных скоростных показателях детища. Если же вспомнить, что прямой потомок "боидов", система Massive, использовалась для расчета поведения многотысячных армад в кинотрилогии "Властелин Колец"… Ох, славные битвы грядут, камрады-ролевики!

О программировании систем частиц на современных графических процессорах я могу говорить часами. Хотя бы потому, что именно так называлась одна из моих курсовых работ. Более очевидного кандидата на вынос с CPU, наверное, не найти. Тысячи точек движутся по простым законам, минимально взаимодействуя друг с другом и окружающим миром - или не взаимодействуя вовсе. Выигрыш от того, что эти гигантские массивы данных не гоняются на каждом кадре из оперативной памяти на видеокарту, огромен. Если же приложение таково, что частицам требуется сортировка (такое бывает, например, при моделировании воды), то преимущество шейдерного подхода становится просто разгромным. Мой почти не оптимизированный код давал выигрыш в два-три раза, в Сети же встречаются отчеты о реализациях, дающих восьми- и даже десятикратный выигрыш.

Ну и конечно, на карточку уходит практически вся рутина: анимация (от колыхания травы до обратной кинематики моделей); выделение границ и силуэтных ребер; определение видимости (в том числе закрывание объектов друг другом); LOD-техника (выбор в реальном времени подходящей детализации модели для сокращения числа выводимых полигонов); вычисление пересечений геометрических примитивов (например, луча и объектов сцены, для определения точки попадания пули). GPU стали по-настоящему универсальны и, повторюсь, подходят практически для любых задач. Судя по всему, уже в ближайшие несколько лет можно ожидать серьезного повышения как качества картинки, так и реалистичности взаимодействия с игровым миром. И этому решительно невозможно не радоваться!