Анализ исходного кода Doom 3

23 ноября 2011 года id Software поддержала собственную традицию и опубликовала исходный код своего предыдущего движка.

На сей раз настало время idTech4, который использовался в Prey, в Quake 4 и, разумеется, в Doom 3. Всего за несколько часов было создано больше 400 форков репозитория на GitHub, люди начали исследовать внутренние механизмы игры или портировать её на другие платформы. Я тоже решил поучаствовать и создал Intel-версию для Mac OS X, которую Джон Кармак любезно прорекламировал.

С точки зрения чистоты и комментариев это самый лучший релиз кода id Software со времени кодовой базы Doom iPhone (которая была выпущена позже, а потому откомментирована лучше). Крайне рекомендую каждому изучить этот движок, собрать его и поэкспериментировать.

Вот мои заметки о том, что я понял. Как обычно, я подчистил их, надеюсь, они сэкономят кому-нибудь пару часов и сподвигнут кого-нибудь на изучение кода для усовершенствования своих навыков программиста.

Часть 1: Обзор

Я заметил, что для объяснения кодовой базы использую всё больше и больше иллюстраций и меньше текста. Раньше я пользовался для этого gliffy, но у него есть раздражающие ограничения (например, отсутствие альфа-канала). Я подумываю над созданием собственного инструмента на основе SVG и Javascript специально для иллюстраций по 3D-движкам. Интересно, есть ли уже что-то подобное? Ну да ладно, вернёмся к коду…

Введение

Очень приятно получить доступ к исходному коду такого потрясающего движка. В момент выхода в 2004 году Doom III задал новые графические и звуковые стандарты для движков реального времени, самым примечательным из которых стал «Unified Lighting and Shadows». Впервые технология позволила художникам выразить себя с голливудским размахом. Даже восемь лет спустя первая встреча с HellKnight в Delta-Labs-4 по-прежнему выглядит невероятно зрелищно:

Первый контакт

Исходный код теперь распространяется через Github и это хорошо, потому что FTP-сервер id Software почти всегда лежал или был перегружен.

Оригинальный релиз TTimo нормально компилируется с помощью Visual Studio 2010 Professional. К сожалению, в Visual Studio 2010 «Express» отсутствует MFC и поэтому её нельзя использовать. После релиза это несколько разочаровало, но с тех пор зависимости были удалены.

Windows 7 :
===========

git clone https://github.com/TTimo/doom3.gpl.git

Для чтения и исследования кода я предпочитаю использовать XCode 4.0 в Mac OS X: скорость поиска из SpotLight, подсвечивание переменных и «Command-Click» для перехода к нужному месту делают работу удобнее, чем в Visual Studio. Проект XCode при релизе был сломан, но его очень просто исправить, и теперь есть репозиторий Github пользователя «bad sector», который хорошо работает на Mac OS X Lion.

MacOS X :
=========

git clone https://github.com/badsector/Doom3-for-MacOSX-

Примечания: оказалось, что подсветка переменных и переход по «Control-Click» также доступны и в Visual Studio 2010 после установки Visual Studio 2010 Productivity Power Tools. Не понимаю, почему этого нет в «ванильном» пакете установки.

Обе кодовые базы теперь находятся в наилучшем состоянии: для сборки исполняемого файла достаточно одного щелчка!

• Скачайте код.
• Нажмите F8 / Command-B.
• Можно запускать!

Интересный факт: для запуска игры вам понадобится папка base с ресурсами Doom 3. Я не хотел тратить время на их извлечение с компакт-дисков Doom 3 и обновление, поэтому скачал версию со Steam. Кажется, ребята из id Software сделали так же, потому что в настройках отладки опубликованного проекта Visual Studio до сих пор есть "+set fs_basepath C:Program Files (x86)Steamsteamappscommondoom 3"!

Интересный факт: Движок был разработан в Visual Studio .NET (исходники). Но в коде нет ни одной строки на C#, а опубликованная версия для компиляции требует Visual Studio 2010 Professional.

Интересный факт: Похоже, что команда Id Software — фанаты франшизы «Матрица»: рабочее название Quake III было «Trinity», а у Doom III рабочим названием было «Neo». Это объясняет, почему весь исходный код находится в подпапке neo.

Архитектура

Игра разделена на проекты, отражающие общую архитектуру движка:

Проекты	Сборки		Примечания
	Windows	Mac OS X
Game	gamex86.dll	gamex86.so	Геймплей Doom3
Game-d3xp	gamex86.dll	gamex86.so	Геймплей Doom3 eXPension (Ressurection)
MayaImport	MayaImport.dll	-	Часть тулчейна создания ресурсов: загружается во время выполнения для открытия файлов Maya и импорта монстров, маршрутов камер и карт.
Doom3	Doom3.exe	Doom3.app	Движок Doom 3
TypeInfo	TypeInfo.exe	-	Внутренний вспомогательный файл RTTI: генерирует GameTypeInfo.h, карту всех типов классов Doom3 с размером каждого элемента. Это позволяет выполнять отладку памяти с помощью класса TypeInfo.
CurlLib	CurlLib.lib	-	HTTP-клиент, используемый для скачивания файлов (статически связана с gamex86.dll и doom3.exe).
idLib	idLib.lib	idLib.a	Библиотека id Software. Включает в себя парсер, лексический анализатор, словарь… (статически связана с gamex86.dll и doom3.exe).

Как и во всех других движках, начиная с idTech2, мы видим один двоичный файл с закрытыми исходниками (doom.exe) и одну динамическую библиотеку с открытым исходным кодом (gamex86.dll):

Большая часть кодовой базы была доступна с октября 2004 года в Doom3 SDK, отсутствовал только исходный код исполняемого файла Doom3. Моддеры могли собрать idlib.a и gamex86.dll, но ядро движка было пока закрыто.

Примечание: Движок не использует стандартную библиотеку C++: все контейнеры (map, список с указателями...) реализованы заново, но активно используется libc.

Примечание: В модуле Game каждый класс наследует idClass. Это позволяет движку выполнять внутренний RTTI и создавать экземпляры классов по имени класса.

Интересный факт: Если посмотреть на иллюстрацию, то можно заметить, что некоторые необходимые фреймворки (такие как Filesystem) находятся в проекте Doom3.exe. Это представляет проблему, потому что gamex86.dll должна загружать и ресурсы. Эти подсистемы динамически загружаются библиотекой gamex86.dll из doom3.exe (вот что обозначает стрелка на иллюстрации). Если открыть DLL в PE explorer, то можно увидеть, что gamex86.dll экспортирует один метод: GetGameAPI:

Всё работает точно так же, как Quake2 загружал рендерер и игровые ddl, передачей указателей на объекты:

Когда загружается Doom3.exe, он:

• Загружает DLL в пространство памяти процесса с помощью LoadLibrary.
• Получает адрес GetGameAPI в dll с помощью GetProcAddress win32.
• Вызывает GetGameAPI.

    gameExport_t * GetGameAPI_t( gameImport_t *import );

В конце этой «установки связи» Doom3.exe есть указатель на объект idGame, а в Game.dll есть указатель на объект gameImport_t, содержащий дополнительные ссылки на все отсутстующие подсистемы, например idFileSystem.

Как Gamex86 видит объекты исполняемого файла Doom 3:

        typedef struct {
            
            int                         version;               // версия API
            idSys *                     sys;                   // непортируемые системные службы
            idCommon *                  common;                // общий
            idCmdSystem *               cmdSystem              // система консольных команд
            idCVarSystem *              cvarSystem;            // система консольных переменных
            idFileSystem *              fileSystem;            // файловая система
            idNetworkSystem *           networkSystem;         // сетевая система
            idRenderSystem *            renderSystem;          // система рендеринга
            idSoundSystem *             soundSystem;           // звуковая система
            idRenderModelManager *      renderModelManager;    // диспетчер моделей рендеринга
            idUserInterfaceManager *    uiManager;             // диспетчер интерфейса пользователя
            idDeclManager *             declManager;           // диспетчер объявлений
            idAASFileManager *          AASFileManager;        // диспетчер файлов AAS
            idCollisionModelManager *   collisionModelManager; // диспетчер модели коллизий
            
        } gameImport_t;

Как Doom 3 видит объекты Game/Modd:

    typedef struct 
    {

        int            version;     // версия API
        idGame *       game;        // интерфейс для выполнения игры
        idGameEdit *   gameEdit;    // интерфейс для внутриигрового редактирования

    } gameExport_t;

Примечания: отличный ресурс для лучшего понимания каждой подсистемы — страница документации Doom3 SDK: похоже, она написана в 2004 году человеком с глубоким пониманием кода (то есть, скорее всего, одним из команды разработки).

Код

Перед разбором приведём немного статистики из cloc:

./cloc-1.56.pl neo

2180 text files.
2002 unique files.
626 files ignored.

http://cloc.sourceforge.net v 1.56 T=19.0 s (77.9 files/s, 47576.6 lines/s)

-------------------------------------------------------------------------------
Language files blank comment code
-------------------------------------------------------------------------------
C++ 517 87078 113107 366433
C/C++ Header 617 29833 27176 111105
C 171 11408 15566 53540
Bourne Shell 29 5399 6516 39966
make 43 1196 874 9121
m4 10 1079 232 9025
HTML 55 391 76 4142
Objective C++ 6 709 656 2606
Perl 10 523 411 2380
yacc 1 95 97 912
Python 10 108 182 895
Objective C 1 145 20 768
DOS Batch 5 0 0 61
Teamcenter def 4 3 0 51
Lisp 1 5 20 25
awk 1 2 1 17
-------------------------------------------------------------------------------
SUM: 1481 137974 164934 601047
-------------------------------------------------------------------------------
По количеству строк кода обычно ничего определённого сказать нельзя, но здесь оно будет очень полезно для оценки труда, необходимого для понимания движка. В коде 601 047 строк, то есть движок в два раза «сложнее» для понимания, чем Quake III. Немного статистики об истории движков id Software в количестве строк кода:

Строки кода	Doom	idTech1	idTech2	idTech3	idTech4
Движок	39079	143855	135788	239398	601032
Инструменты	341	11155	28140	128417	-
Всего	39420	155010	163928	367815	601032

Примечание: Значительное увеличение объёма в idTech3 возникло из-за инструментов из кодовой базы lcc (компилятор C использовался для генерирования байт-кода QVM).

Примечание: Для Doom3 инструменты не учитываются, потому что они вошли в кодовую базу движка.

На высоком уровне можно заметить пару забавных фактов:

• Впервые в истории id Software код написан на C++, а не на C. Джон Кармак объяснил это в интервью.
• В коде активно используются абстрагирование и полиморфизм. Но интересный трюк позволяет избежать снижения производительности vtable на некоторых объектах.
• Все ресурсы хранятся в человекочитаемом текстовом формате. Больше никаких двоичных файлов. В коде активно используется лексический анализатор/парсер. Джон Кармак рассказал об этом в интервью.
• Шаблоны используются в низкоуровневых вспомогательных классах (в основном в idLib), но никогда не применяются на верхних уровнях, поэтому код, в отличие от Google V8, не заставляет глаза кровоточить.
• С точки зрения комментирования это вторая по качеству кодовая база id software, лучше только Doom iPhone, возможно потому, что она вышла позже Doom3. 30% комментариев — по-прежнему выдающийся результат, очень редко можно найти так хорошо задокументированный проект! В некоторых частях кода (см. раздел о dmap) комментариев больше, чем кода.
• ООП-инкапсуляция сделала код чище и упростила его чтение.
• Дни низкоуровневой ассемблерной оптимизации прошли. Некотоорые трюки, например, idMath::InvSqrt и оптимизации пространственной локализации сохранились, но в основном код просто использует доступные инструменты (GPU-шейдеры, OpenGL VBO, SIMD, Altivec, SMP, оптимизации L2 (R_AddModelSurfaces для обработки моделей)...).

Интересно также взглянуть на Стандарт написания кода idTech4 (зеркало), написанный Джоном Кармаком (в особенности я благодарен для комментарии о расположении const).

Разворачиваем цикл

Вот анализ основного цикла с самыми важными частями движка:

    idCommonLocal    commonLocal;                   // специализированный объект ОС 
    idCommon *       common = &commonLocal;         // Указатель интерфейса (поскольку Init зависим от ОС, это абстрактный метод)
        
    int WINAPI WinMain( HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow ) 
    {
            
        
        Sys_SetPhysicalWorkMemory( 192 << 20, 1024 << 20 );   //Min = 201,326,592  Max = 1,073,741,824
        Sys_CreateConsole();
            
        // Поскольку движок многопоточный, здесь инициализируются мьютексы: по одному мьютексу на "критичную" (параллельно исполняемую) часть кода.
        for (int i = 0; i < MAX_CRITICAL_SECTIONS; i++ ) { 
            InitializeCriticalSection( &win32.criticalSections[i] );
        }
            
        common->Init( 0, NULL, lpCmdLine );              // Оценка объёма доступной VRAM (выполняется не через OpenGL, а вызовом ОС)
            
        Sys_StartAsyncThread(){                          // Следующий выполняется в отдельном потоке.
            while ( 1 ){
                usleep( 16666 );                         // Выполняется на 60 Гц
                common->Async();                         // Выполнение работы
                Sys_TriggerEvent( TRIGGER_EVENT_ONE );   // Разблокировка других потоков, ожидающих ввода
                pthread_testcancel();                    // Проверка, была ли задача отменена основным потоком (при закрытии игры).
            }
        }
        
        Sys_ShowConsole
            
        while( 1 ){
            Win_Frame();                                 // Отображает/скрывает консоль
            common->Frame(){
                session->Frame()                         // Игровая логика
                {
                    for (int i = 0 ; i < gameTicsToRun ; i++ ) 
                        RunGameTic(){
                            game->RunFrame( &cmd );      // С этой точки выполнение переходит в адресное пространство GameX86.dll.
                              for( ent = activeEntities.Next(); ent != NULL; ent = ent->activeNode.Next() ) 
                                ent->GetPhysics()->UpdateTime( time );  // даём элементам подумать
                        }
                }
                
                session->UpdateScreen( false ); // обычное последовательное обновление экрана
                {
                    renderSystem->BeginFrame
                        idGame::Draw            // Фронтэнд рендерера. Не обменивается данными с видеопроцессором!
                    renderSystem->EndFrame
                        R_IssueRenderCommands   // Бекэнд рендерера. Передаёт оптимизированные видепроцессорные команды видеопроцессору.
                }
            }
        }
    }

Подробнее о полностью разобранном цикле можно здесь. При чтении кода я использовал его как карту.

Это стандартный для движков id Software цикл main. За исключением Sys_StartAsyncThread, который означает, что Doom3 многопоточный. Задача этого потока — управление критичными по времени функциями, которые движок не должен ограничивать частотой кадров:

• Микширование звука.
• Генерирование вводимых пользователем данных.

Интересный факт: все высокоуровневые объекты idTech4 являются абстрактными классами с виртуальными методами. Обычно такое снижает производительность, потому что адрес каждого виртуального метода перед его вызовом во время выполнения необходимо найти во vtable. Но есть «трюк», позволяющий этого избежать. Экземпляры всех объектов создаются статически следующим образом:

    idCommonLocal    commonLocal;                   // Реализация
    idCommon *       common = &commonLocal;         // Указатель на gamex86.dll

Поскольку объект, статично размещаемый в сегменте данных, имеет известный тип, то компилятор может оптимизировать поиск во vtable при вызове методов commonLocal. При установке связи (handshake) используется указатель интерфейса, поэтому doom3.exe может обмениваться ссылками на объекты с gamex86.dll, но в таком случае затраты на поиск во vtable не оптимизируются.

Интересный факт: изучив большинство движков id Software, я считаю примечательным то, что одно название метода НИКОГДА не менялось со времени движка doom1: метод, занимающийся считыванием вводимых с мыши и джойстика данных по прежнему называется IN_frame().

Рендерер

Две важные части:

• Поскольку в Doom3 используется система порталов, инструмент предварительной обработки dmap совершенно отличается от традиционного компоновщика bsp. Я рассмотрел его ниже, в соответствующем разделе.

  

• Рендерер времени выполнения имеет очень интересную архитектуру. Он разбит на две части с фронтэндом и бекэндом (подробнее об этом в разделе «Рендерер» ниже).

  

Профилирование

Я использовал Instruments из Xcode, чтобы проверить, чем занимаются циклы ЦП. Результаты и анализ см. в разделе «Профилирование» ниже.

Скриптинг и виртуальная машина

В каждом продукте idTech ВМ и скриптовый язык полностью менялись… и id сделала это снова (подробнее в разделе «Скриптовая ВМ»)

Интервью

Во время чтения кода меня озадачили некоторые нововведения, поэтому я написал Джону Кармаку и он был так любезен, что ответил и подробно объяснил следующие особенности:

• C++.
• Разбиение рендерера на две части.
• Текстовые ресурсы.
• Интерпретируемый байт-код.

Кроме того, я собрал на одной странице все видео и интервью с прессой об idTech4. Все они собраны на странице интервью.

Часть 2: Dmap

Как и во всех движках id Software, создаваемые командой дизайнеров карты проходят мощную предварительную обработку утилитой для увеличения производительности во время выполнения.

В idTech4 эта утилита называется dmap и её цель заключается в считывании супа из многогранников из файла .map, определении областей, соединённых порталами и сохранении их в файле .proc.

Цель этого инструмента — применение системы порталов времени выполнения в doom3.exe. Существует потрясающая статья Сета Теллера 1992 года: «Visibility Computations in Densely Occluded Polyhedral environment». В ней подробно и со множеством иллюстраций описывается то, как работает движок idTech4.

Редактор

Дизайнеры создают карты уровней с помощью CSG (Constructive Solid Geometry): они используют многогранники, обычно имеющие шесть граней, и размещают их на карте.

Эти блоки называются «кистями» (brush). На рисунке ниже использовано восемь кистей (Для объяснения каждого шага dmap я буду использовать одну и ту же карту).

Дизайнер может хорошо понимать, что находится «внутри» (первый рисунок), но dmap получает всего лишь суп из кистей, в котором нет ничего внутреннего и наружного (второй рисунок).

Что видит дизайнер	Что видит Dmap при считывании кистей из файла .map.

Кисть определяется не через грани, а через плоскости. Задание плоскостей вместо граней может казаться неэффективным, но это будет очень полезно позже, при проверке того, находятся ли две поверхности на одной плоскости. Нет внутренних и внешних частей, потому что плоскости не ориентированы «одинаково». Ориентация плоскостей может быть разной внутри или снаружи объёма.

Обзор кода

Исходный код Dmap очень хорошо откомментирован, просто посмотрите на это количество: комментариев больше, чем кода!

     bool ProcessModel( uEntity_t *e, bool floodFill ) {
     
     bspface_t        *faces;
     
     // построение bsp-дерева с использованием всех сторон
     // всех структурных кистей
     faces = MakeStructuralBspFaceList ( e->primitives );
     e->tree = FaceBSP( faces );
     
     // создаём порталы на каждом пересечении листьев,
     // чтобы обеспечить возможность заливки
     MakeTreePortals( e->tree );
     
     // классифицируем листья как непрозрачные или порталы областей
     FilterBrushesIntoTree( e );
     
     // проверяем, замкнуто ли bsp полностью
     if ( floodFill && !dmapGlobals.noFlood ) {
       if ( FloodEntities( e->tree ) ) {
         // делаем листья снаружи непрозрачными
         FillOutside( e );
       } else {
         common->Printf ( "**********************n" );
         common->Warning( "******* leaked *******" );
         common->Printf ( "**********************n" );
         LeakFile( e->tree );
         // Если нужно действительно обработать
         // "протекающую" карту, то используется параметр
         // -noFlood
         return false;
       }
     }
     
     // получение минимальной выпуклой оболочки для каждой видимой стороны
     // это необходимо делать до создания порталов между областями,
     // потому что видимая оболочка используется в качестве портала
     ClipSidesByTree( e );
     
     // определяем области, прежде чем обрезать треугольники
     // в дерево, чтобы треугольники никогда не пересекали границы областей
     FloodAreas( e );
     
     // теперь у нас есть BSP-дерево с непрозрачными и прозрачными листьями, помеченными областями
     // все примитивы теперь обрезаются до них, отбрасываются
     // фрагменты в непрозрачных областях
     PutPrimitivesInAreas( e );
     
     // теперь строим объёмы теней для освещения и разрезаем
     // списки оптимизации по деревьям лучей света,
     // чтобы не было ненужной перерисовки в случае
     // неподвижности
     Prelight( e );
     
     // оптимизация - это надмножество исправляющих T-образных соединений
     if ( !dmapGlobals.noOptimize ) {
        OptimizeEntity( e );
     } else  if ( !dmapGlobals.noTJunc ) {
        FixEntityTjunctions( e );
     }
     
     // теперь исправляем Т-образные соединения в областях
     FixGlobalTjunctions( e );
     
     return true;
     }

0. Загрузка геометрии уровня

Файл .map — это список сущностей. Уровень — это первая сущность в файле, имеющая класс «worldspawn». Сущность содержит список примитивов, которые почти всегда являются кистями. Остальные сущности — это источники света, монстры, точки спауна игрока, оружие и т.д.

   Version 2
                            
    // сущность 0
    {
        "classname" "worldspawn"
        // примитив 0
        {
            brushDef3
            {
                ( 0 0 -1 -272 ) ( ( 0.0078125 0 -8.5 ) ( 0 0.03125 -16 ) ) "textures/base_wall/stelabwafer1" 0 0 0
                ( 0 0 1 -56   ) ( ( 0.0078125 0 -8.5 ) ( 0 0.03125 16  ) ) "textures/base_wall/stelabwafer1" 0 0 0
                ( 0 -1 0 -3776) ( ( 0.0078125 0 4    ) ( 0 0.03125 0   ) ) "textures/base_wall/stelabwafer1" 0 0 0
                ( -1 0 0 192  ) ( ( 0.0078125 0 8.5  ) ( 0 0.03125 0   ) ) "textures/base_wall/stelabwafer1" 0 0 0
                ( 0 1 0 3712  ) ( ( 0.006944  0 4.7  ) ( 0 0.034   1.90) ) "textures/base_wall/stelabwafer1" 0 0 0
                ( 1 0 0 -560  ) ( ( 0.0078125 0 -4   ) ( 0 0.03125 0   ) ) "textures/base_wall/stelabwafer1" 0 0 0
            }
        }
        // примитив 1
        {
           brushDef3
        }
        // примитив 2
        {
            brushDef3
        }        
    }    
    .
    .
    .
   // сущность 37
   {
        "classname" "light"
        "name" "light_51585"
        "origin" "48 1972 -52"
        "texture" "lights/round_sin"
        "_color" "0.55 0.06 0.01"
        "light_radius" "32 32 32"
        "light_center" "1 3 -1"
   }

Каждая кисть описывается как множество плоскостей. Стороны кисти называются гранями (или изгибами), каждая из которых получается обрезкой плоскости всеми другими плоскостями кисти.

Примечание: на этапе загрузки используется очень интересная и быстрая система хэширования плоскостей (Plane Hashing System): поверх idHashIndex создана idPlaneSet, на которую стоит посмотреть.

1. MakeStructuralBspFaceList и FaceBSP

Первый этап — это разрезание карты способом двоичного разбиения пространства (Binary Space Partition). Каждая непрозрачная грань карты используется как разделительная плоскость.

Используется следующая эвристика выбора разделителя:

1: если в карте больше 5000 единиц: разрезаем с помощью ориентированной по осям плоскости (Axis Aligned Plane) посередине пространства. На рисунке ниже пространство 6000x6000 разрезано три раза.

2: Когда больше не осталось частей больше 5000 единиц: используем грани, помеченные как «порталы» (они имеют материал textures/editor/visportal). На рисунке ниже кисти порталов отмечены голубым.

3: Используем оставшиеся грани. Выбираем грань, наиболее коллинеарную с большинством других И разрезаем наименьшие грани. Также предпочтение отдаётся осевым разделителям. Разделительные плоскости отмечены красным.

Процесс завершается, когда не остаётся доступных граней: весь лист BSP-дерева представляет собой выпуклое подпространство:

2. MakeTreePortals

Теперь карта разделена на выпуклые подпространства, но эти подпространства ничего не знают друг о друге. Цель этого этапа — соединить каждый из листьев с его соседями с помощью автоматического создания порталов. Идея заключается в том, чтобы начать с шести порталов, ограничивающих карту: соединить «внешнее» с «внутренним» (с корнем BSP). Затем для каждого узла в BSP разделяем каждый портал в узле, добавляем разделительную плоскость в качестве портала и рекурсивно повторяем.

Шесть исходных порталов будут разделены и распространятся вниз, к листьям. Это не так тривиально, как кажется, потому что каждый раз узел разделяется: каждый присоединённый к нему портал тоже должен быть разделён.

На рисунке слева один портал соединяет два узла-«брата» в BSP-дереве. При следовании по левому дочернему листу его разделительная плоскость делит портал на два. Мы видим, что порталы других узлов тоже нужно обновлять, чтобы они больше не соединялись с «братьями» и их «племянниками».

В конце процесса шесть исходных порталов разделены на сотни порталов, а на разделительных плоскостях созданы новые порталы:

Каждый лист в BSP теперь знает о своих соседях благодаря связанному списку порталов, присоединяющих их к листьям, имеющим общее ребро:

3. FilterBrushesIntoTree

Этот этап похож на детскую игру с подбором форм фигур, где BSP — это доска, а кисти — это фигуры. Каждая кисть отправляется вниз по BSP для обнаружения непрозрачных листьев.

Способ работает благодаря хорошо описанной эвристике: если кисть немного пересекает разделительную плоскость, но не больше, чем на EPSILON, то онВместо этого она полностью отправляется на сторону плоскости, на которой находятся все другие элементы кисти.

Теперь «внутренние» и «внешние» части начинают быть видимыми.

Лист, которого коснулась кисть, считается непрозрачным (сплошным) и соответственным образом помечается.

4. FloodEntities и FillOutside

С помощью сущности спауна игрока для каждого листа выполняется алгоритм заливки. Он помечает листья как достижимые сущностями.

Последний этап FillOutside проходит по каждому листу и если он недостижим, то помечает его как непрозрачный.

Мы получили уровень, в котором каждое подпространство или достижимо, или непрозрачно: теперь навигация через порталы листьев единообразна и выполняется проверкой целевого листа на непрозрачность.

5. ClipSidesByTree

Настало время отбросить ненужные части кистей: каждая исходная сторона кисти отправляется вниз по BSP. Если сторона находится внутри непрозрачного пространства, то она отбрасывается. В противном случае она добавляется в список visibleHull стороны.

В результате мы получаем «кожу» уровня, сохраняются только видимые части.

С этого момента для оставшихся операций рассматривается только список visibleHull стороны.

6. FloodAreas

Теперь dmap группирует листья с идентификаторами областей: для каждого листа выполняется алгоритм заливки. Он пытается залить всё через порталы, связанные с листом.

Здесь работа дизайнера имеет огромную важность: области можно идентифицировать, только если на карте были вручную расположены visportals (кисти порталов, упомянутые на этапе 1). Без них dmap идентифицирует только одну область и каждый кадр в видеопроцессор будет отправляться вся карта.

Рекурсивный алгоритм заливки останавливается только порталами областей и непрозрачными узлами. На рисунке ниже автоматически сгенерированный портал (красный) позволит продолжить заливку, но размещённый дизайнером visportal (синий, также называется areaportal), остановит его, создав две области:

В конце процесса каждый несплошной лист принадлежит к области и определены межобластные порталы (голубой).

7. PutPrimitivesInAreas

На этом этапе в ещё одной игре «Найди фигуру» сочетаются области, определённые на этапе 6 и visibleHull, вычисленный на этапе 5: на этот раз доска — это области, а фигуры — это visibleHull.

Выделяется массив областей и каждый visibleHull каждой кисти отправляется вниз по BSP: к массиву областей добавляются поверхности по индексным areaID.

Примечание: довольно умный ход — на этом этапе также оптимизируется спаунинг сущностей. Если некоторые сущности помечены как «func_static», их экземпляры создаются сейчас и привязываются к области. Таким образом можно «приклеить» ящики, бочки и стулья к области (также выполнив предварительную генерацию их теней).

8. Prelight

Для каждого статичного источника света dmap предварительно вычисляет геометрию объёмов теней. Эти объёмы позже как есть сохраняются в .proc. Единственная хитрость заключается в том, что объёмы теней сохраняются с именем "_prelight_light", соединённым с идентификатором источника света, чтобы движок мог сопоставить источник света из файла .map и объём теней из файла .proc:

      shadowModel { /* name = */ "_prelight_light_2900"

      /* numVerts = */ 24 /* noCaps = */ 72 /* noFrontCaps = */ 84 /* numIndexes = */ 96 /* planeBits = */ 5
   
     ( -1008 976 183.125 ) ( -1008 976 183.125 ) ( -1013.34375 976 184 ) ( -1013.34375 976 184 ) ( -1010 978 184 ) 
     ( -1008 976 184 ) ( -1013.34375 976 168 ) ( -1013.34375 976 168 ) ( -1008 976 168.875 ) ( -1008 976 168.875 ) 
     ( -1010 978 168 ) ( -1008 976 167.3043518066 ) ( -1008 976 183.125 ) ( -1008 976 183.125 ) ( -1010 978 184 ) 
     ( -1008 976 184 ) ( -1008 981.34375 184 ) ( -1008 981.34375 184 ) ( -1008 981.34375 168 ) ( -1008 981.34375 168 ) 
     ( -1010 978 168 ) ( -1008 976 167.3043518066 ) ( -1008 976 168.875 ) ( -1008 976 168.875 ) 
  
     4 0 1 4 1 5 2 4 3 4 5 3 0 2 1 2 3 1 
     8 10 11 8 11 9 6 8 7 8 9 7 10 6 7 10 7 11 
     14 13 12 14 15 13 16 12 13 16 13 17 14 16 15 16 17 15 
     22 21 20 22 23 21 22 18 19 22 19 23 18 20 21 18 21 19 
     1 3 5 7 9 11 13 15 17 19 21 23 4 2 0 10 8 6 
     16 14 12 22 20 18 
     }

9. FixGlobalTjunctions

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

10. Вывод данных

В конце все предварительно обработанные данные сохраняются в файл .proc:

• Для каждой области множество граней поверхностей группируется по материалу.
• BSP-дерево с areaID для листьев.
• Изгибы межобластных порталов.
• Объёмы теней.

История

Многие сегменты кода из dmap схожи с кодом, использованным в инструментах предварительной обработки Quake (qbsp.exe), Quake 2 (q2bsp.exe) и Quake 3 (q3bsp.exe). Причина этого в том, что потенциально видимое множество (PVS) сгенерировано с помощью временной системы порталов:

• qbsp.exe считывал .map и генерировал файл .prt, содержащий информацию о связях между листьями в порталах BSP (в точности как на этапе 2 «MakeTreePortals»).
• vis.exe использовался в .prt в качестве входа. Для каждого листа:
  • выполнялась заливка с помощью порталов в связанные листья.
  • перед заливкой в лист: выполнялась проверка видимости отсечением следующего портала с двумя предыдущими порталами относительно пирамиды видимости (многие считали, что видимость определяется испусканием тысяч лучей, но это миф, в который много кто верит и сейчас).

Иллюстрация всегда лучше: допустим qbsp.exe обнаружил шесть листьев, соединённых порталами и теперь выполняется vis.exe для генерирования PVS. Этот процесс будет выполнен для каждого листа, но в этом примере мы рассмотрим только лист 1.

Так как лист всегда видим из самого себя, то первоначальное PVS для листа 1 будет следующим:

Идентификатор листа	1	2	3	4	5	6
Битовый вектор (PVS для листа 1)	1	?	?	?	?	?

Начинается выполнение алгоритма заливки: правило заключается в том, что пока у нас в пути нет двух порталов, лист считается видимым из начальной точки. Это значит, что мы достигнем листа 3 со следующим PVS:

Идентификатор листа	1	2	3	4	5	6
Битовый вектор (PVS для листа 1)	1	1	1	?	?	?

В листе 3 мы уже можем на самом деле проверять видимость: взяв две точки из портала n-2 и портала n-1, мы можем сгенерировать плоскости отсечения и протестировать следующие порталы на потенциальную видимость.

Из рисунка мы видим, что порталы, ведущие к листьям 4 и 6 не пройдут проверку, а портал к листу 5 пройдёт. Затем рекурсивно выполнится алгоритм заливки для листа 6. В конце PVS для листа 1 будет следующим:

Идентификатор листа	1	2	3	4	5	6
Битовый вектор (PVS для листа 1)	1	1	1	0	1	0

В idTech4 PVS не генерируется, вместо этого сохраняются данные порталов. Видимость каждой области вычисляется во время выполнения проецированием изгибов порталов в пространство экрана и обрезкой их друг относительно друга.

Интересный факт: Майкл Абраш объяснил весь этот процесс за 10 секунд с помощью маркера в этом отличном видео из GDC Vault (картинка кликабельна):

.

Часть 3: Рендерер

В рендерере idTech4 сделаны три важных инновации:

• «Unified Lighting and Shadows»: грани уровня и грани сущностей проходят через одинаковый конвейер и шейдеры.
• «Visible Surface Determination»: система порталов позволяет выполнять VSD во время выполнения — больше никаких PVS.
• «Multi-pass Rendering».

Наиболее важным в idTech4 стал многопроходной рендерер. Влияние каждого источника света в области видимости накапливается в буфере кадра видеопроцессора с помощью аддитивного смешивания. Doom 3 полностью использует то, что цветовые регистры буфера кадра выполняют насыщение, а не перенос.

Регистр ЦП (перенос) :
============================

1111 1111
+ 0000 0100
---------
= 0000 0011

Регистр видеопроцессора (насыщение) :
==========================

1111 1111
+ 0000 0100
---------
= 1111 1111

Я создал собственный уровень, чтобы проиллюстрировать аддитивное смешивание. На скриншоте ниже в комнате показаны три источника света, для которых выполняется три прохода. Результат каждого прохода накапливается в буфере кадра. Заметьте белое освещение в центре экрана, где все источники света смешиваются.

Я изменил движок, чтобы изолировать каждый проход:

Проход 1: источник синего света

Проход 2: источник зелёного света

Проход 3: источник красного света

Я внёс другие изменения в движок, чтобы увидеть состояние буфера кадра ПОСЛЕ каждого прохода источника света:

Буфер видеопроцессора после первого прохода

Буфер кадра видеопроцессора после второго прохода

Буфер кадра видеопроцессора после третьего прохода

Интересный факт: Можно взять результат каждого прохода источника света, смешать их вручную в Photoshop (Linear Dodge для имитации аддитивного смешивания OpenGL) и получить совершенно такой же результат.

Аддитивное смешивание в сочетании с поддержкой теней и рельефного текстурирования (bumpmapping) создают в движке очень хорошую картинку даже по стандартам 2012 года:

Архитектура

В отличие от предыдущих движков idTech, рендерер не монолитен, а разбит на две части (фронтэнд и бекэнд):

• Фронтэнд:
  1. Анализирует базу данных и определяет, что влияет на область видимости.
  2. Сохраняет результат в промежуточное представление (def_view_t) и загружает/использует повторно кэшированную геометрию в VBO видеопроцессора.
  3. Выдаёт команду RC_DRAW_VIEW.
• Бекэнд:
  1. Команда RC_DRAW_VIEW приводит в действие бекэнд.
  2. Использует промежуточное представление в качестве входных данных и передаёт команды в видеопроцессор с помощью VBO.

Архитектура рендерера очень похожа на кросс-компилятор LCC, использованный для генерирования байт-кода виртуальной машины Quake3:

Я изначально думал, что на дизайн рендерера повлиял дизайн LCC, но рендерер разделён на две части, потому что он должен был стать многопоточным в SMP-системах. Фронтэнд должен был выполняться в одном ядре, а бекэнд — в другом. К сожалению, из-за нестабильности с некоторыми драйверами ещё один поток пришлось отключить и обе части выполняются в одном потоке.

Интересный факт о происхождении: С кодом тоже можно провести археологические исследования — если внимательно посмотреть на развёрнутый код рендерера, то чётко видно, что движок переходит от C++ к C (от объектов к статичным методам):

Так произошло из-за истории кода. Рендерер idTech4 писался Джоном Кармаком на основе движка Quake3 (кодовая база на C), пока он не стал специалистом по C++. Рендерер был позже интегрирован в кодовую базу idtech4 на C++.

Сколько от Quake осталось в Doom3? Сложно сказать, но забавно видеть, что основной метод в версии Mac OS X:

   - (void)quakeMain;

Фронтэнд, бекэнд, взаимодействие с видеопроцессором

На рисунке показано взаимодействие между фронтэндом, бекэндом и видеопроцессором:

1. Фронтэнд анализирует состояние мира и выдаёт два результата:
   • Промежуточное представление, содержащее список каждого из источников света, влияющих на область видимости. Каждый источник света содержит список взаимодействующих с ним поверхностей сущностей.
   • Каждое взаимодействие между источником света и сущностью, которое будет использоваться в текущем кадре, кэшируется в таблицу взаимодействий. Данные обычно загружаются в VBO видеопроцессора.
2. Бекэнд получает на входе промежуточное представление. Он проходит по каждому источнику света в списке и создаёт вызовы отрисовки OpenGL для каждой сущности, взаимодействующей с источником света. Команда отрисовки ссылается на VBO и текстуры.
3. Видеопроцессор получает команды OpenGL и выполняет рендеринг на экран.

Фронтэнд рендерера Doom3

Фронтэнд выполняет трудную задачу: определение видимых поверхностей (Visible Surface Determination, VSD). Её цель — найти все сочетания источников света и сущностей, влияющих на область видимости. Такие комбинации называются взаимодействиями. Когда все взаимодействия найдены, фронтэнд загружает всё необходимое бекэнду в ОЗУ видеопроцессора (он отслеживает всё с помощью «таблицы взаимодействий»). Последний этап заключается в генерировании промежуточного представления, которое будет считываться бекэндом для генерирования команд OpenGL.

Вот как это выглядит в коде:

  - idCommon::Frame
   - idSession::UpdateScreen
     - idSession::Draw
       - idGame::Draw
         - idPlayerView::RenderPlayerView
           - idPlayerView::SingleView
             - idRenderWorld::RenderScene
                - build params
                - ::R_RenderView(params)    // Это фронтэнд
                  {
                      R_SetViewMatrix
                      R_SetupViewFrustum
                      R_SetupProjection
              
                      // Самое важное находится здесь.
                      static_cast<idRenderWorldLocal *>(parms->renderWorld)->FindViewLightsAndEntities()
                      {
                          PointInArea              // Обходим BSP и находим текущую область
                          FlowViewThroughPortals   // Рекурсивно обходим порталы, чтобы найти источники света и сущности, взаимодействующие с областью видимости.
                      }
              
                      R_ConstrainViewFrustum     // Повышаем точность Z-буфера ограничивая дальний план самой дальней сущностью.
                      R_AddLightSurfaces         // Находим сущности, не находящиеся в видимой области, но отбрасывающие тень (обычно это враги)
                      R_AddModelSurfaces         // Создаём экземпляры анимированных моделей (для монстров)
                      R_RemoveUnecessaryViewLights
                      R_SortDrawSurfs            // Вызов простого qsort на C. Благодаря встраиванию сортировка на C++ стала бы быстрее.       
                      R_GenerateSubViews
                      R_AddDrawViewCmd 
                  }

Примечание: Здесь очевиден переход от C к C++.

Всегда проще разбираться на примере рисунка, поэтому вот уровень. Благодаря расположенным дизайнерами visplanes движок видит четыре области:

При загрузке .proc движок также загрузил .map, содержащий определения всех источников света и движущихся сущностей. Для каждого источника света движок создал список всех областей, на которые он влияет:

Источник света 1 :
=========

- Область 0
- Область 1

Источник света 2 :
=========

- Область 1
- Область 2
- Область 3

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

Вот в чём заключается процесс:

1. Находим, в какой области находится игрок обходом BSP-дерева в PointInArea.
2. FlowViewThroughPortals: начиная с текущей области выполняем заливку в другую видимую область с помощью системы порталов. Изменяем форму пирамиды видимости при каждом проходе портала. Это очень красиво объяснено в книге Realtime rendering:

   

   Теперь у нас есть список всех источников света, влияющих на экран, и большинства сущностей, хранящихся в таблице взаимодействий:

   Таблица взаимодействий (источник света/сущность) :
==================================

   Источник 1 - Область 0
   Источник 1 - Область 1
   Источник 1 - Монстр 1

   Источник 2 - Область 1
Источник 2 - Монстр 1

   Таблица взаимодействий пока ещё не заполнена: отсутствует взаимодействие «Источник 2 — Монстр 2», у монстра 2 не будет тени.

3. R_AddLightSurfaces проходит через список областей каждого источника света и находит сущность, отсутствующую в области видимости, но отбрасывающую тень.

   Таблица взаимодействий (источник света/сущность) :
==================================

   Источник 1 - Область 0
   Источник 1 - Область 1
   Источник 1 - Монстр 1

   Источник 2 - Область 1
Источник 2 - Монстр 1
Источник 2 - Монстр 2

4. R_AddModelSurfaces: все взаимодействия найдены, настало время загружать вершины и индексы в VBO видеопроцессора, если их там ещё нет. Здесь создаётся и экземпляр геометрии анимированного монстра (модель И объём тени).
5. Вся «интеллектуальная» работа завершена. С помощью R_AddDrawViewCmd выдаётся команда RC_DRAW_VIEW, заставляющая бекэнд начать рендеринг на экран.

Бекэнд рендерера Doom3

Бекэнд занимается рендерингом промежуточного представления с учётом ограничений видеопроцессора: Doom3 поддерживал пять способов рендеринга видеопроцессоров:

• R10 (GeForce256)
• R20 (GeForce3)
• R200 (Radeon 8500)
• ARB (OpenGL 1.X)
• ARB2 (OpenGL 2.0)

На 2012 год только ARB2 поддерживается современными видеопроцессорами: стандарты обеспечили не только портируемость, но и увеличили срок жизни игры.

Если видеокарта поддерживала рельефное текстурирование (bumpmapping) (туториал об использовании Hellknight, который я написал несколько лет назад) и карты отражений, то idtech4 включал их, но все они стремились изо всех сил как можно больше сэкономить пиксельную скорость заполнения (fillrate) следующими операциями:

• OpenGL Scissor test (отдельно для каждого источника света, созданного фронтэндом)
• Заполнением Z-буфера на первом этапе.

Ниже показан развёрнутый код бекэнда:

      idRenderSystemLocal::EndFrame
       R_IssueRenderCommands
         RB_ExecuteBackEndCommands
           RB_DrawView
            RB_ShowOverdraw
            RB_STD_DrawView
            {
               RB_BeginDrawingView     // очистка z-буфера, задание матрицы проекций и т.д.
               RB_DetermineLightScale
               
               RB_STD_FillDepthBuffer  // заполнение буфера глубины и очистка (заливка чёрным) буфера цвета.
               
                // Проход через каждый источник света и отрисовка прохода, накопление результата в буфере кадра
               _DrawInteractions  
               {
                   5 GPU specific path
                   
                   switch (renderer)
                   {
                      R10  (GeForce256)
                      R20  (geForce3)
                      R200 (Radeon 8500)
                      ARB  (OpenGL 1.X)
                      ARB2 (OpenGL 2.0)
                }
                
                // отключение теста теней шаблонов
                qglStencilFunc( GL_ALWAYS, 128, 255 );

                RB_STD_LightScale
                
                // отрисовка всех независящих от света проходов затенения (экраны, неон, и т.д...)
                int  processed = RB_STD_DrawShaderPasses( drawSurfs, numDrawSurfs )   
                
                // туман и смешивание источников света
                RB_STD_FogAllLights();

                // отрисовка всех эффектов постпроцессинга с помощью _currentRender
                if ( processed < numDrawSurfs ) 
                   RB_STD_DrawShaderPasses( drawSurfs+processed, numDrawSurfs-processed );
	
	                        
             }

Чтобы пройти пошагово этапы бекэнда я взял знаменитый экран из уровня Doom3 и останавливал движок на каждом этапе визуалиации:

Поскольку в Doom3 используется bumpmapping и карты отражений поверх диффузных текстур, рендеринг поверхности может использовать поиск в трёх текстурах. На пиксель могут влиять до 5-7 источников света, так что не будет безумием предположить возможность до 21 поиска текстур на пиксель… даже без учёта перерисовки. Первый этап бекэнда нужен для достижения 0 перерисовок: отключение всех шейдеров, запись только в буфер глубины и рендеринг всей геометрии:

Буфер глубины теперь заполнен. С этого момента запись глубин отключена и включен тест глубин.

Рендеринг в первую очередь в z-буфер может казаться контрпродуктивным, но на самом деле он чрезвычайно полезен для экономии fillrate:

• Предотвращает выполнение затратных шейдеров для невидимых поверхностей.
• Предотвращает рендеринг невидимых теней в буфер шаблонов.
• Поскольку поверхности рендерятся без определённого порядка (сзади вперёд или спереди назад), то будет большой объём перерисовки. Этот шаг полностью избавляет от перерисовки.

Заметьте, что буфер цвета очищен и залит чёрным: в естественном виде мир Doom3 кромешно чёрный, потому что нет никакого «окружающего» освещения — чтобы быть видимым, полигон/поверхность должны взаимодействовать с источником света. Это объясняет, почему Doom3 был таким тёмным!

После этого движок выполнит 11 проходов (по одному для каждого источника света.

Я разбил процесс рендеринга на части. На рисунках ниже показан каждый отдельный проход источника света.

Влияние источника света 1

Влияние источника света 2

Влияние источника света 3

Влияние источника света 4

Влияние источника света 5

Влияние источника света 6

Влияние источника света 7

Влияние источника света 8

Влияние источника света 9

Влияние источника света 10

Влияние источника света 11

Последний проход: проход окружающего освещения

А теперь о том, что происходит в буфере кадра видеопроцессора:

После прохода источника света 1

После прохода источника света 2

После прохода источника света 3

После прохода источника света 4

После прохода источника света 5

После прохода источника света 6

После прохода источника света 7

После прохода источника света 8

После прохода источника света 9

После прохода источника света 10

После прохода источника света 11

После прохода источника света 12

После прохода источника света 13

Буфер шаблонов и Scissors test:

Если источником света отбрасывается тень, то перед каждым проходом источника света необходимо выполнить тест шаблона. Я не буду подробно описывать противоречие depth-fail/depth pass и печально известный ход Creative Labs. В опубликованном исходном коде представлен более медленный алгоритм прохода глубины (depth pass), потому что он требует построения качественного объёма теней. Кому-то удалось вернуть в исходный код алгоритм depth fail, но учтите — это законно только в Европе!

Чтобы сэкономить fillrate, фронтэнд генерирует прямоугольник пространства экрана, который должен использоваться для scissor test в OpenGL. Это позволяет не выполнять шейдер для пикселей, чья поверхность всё равно будет чёрной из-за расстояния до источника света.

Буфер шаблонов применяется прямо перед проходом источника света 8. Все нечёрные области будут залиты, а для других запись в буфер кадра ограничена: чётко видим принцип маски.

Буфер шаблонов расположен прямо перед проходом источника света 7. Чётко виден scissor для экономии fillrate.

<img src=«fd.fabiensanglard.net/doom3/renderer/DOOM3-Context3-Static-StencilBuffer2.png»

Интерактивные поверхности

Последний этап рендеринга — это RB_STD_DrawShaderPasses: он рендерит все поверхности, которым не требуется света. К ним относятся экран и потрясающие интерактивные поверхности графического интерфейса пользователя. Этой частью движка Джон Кармак гордился больше всего. Не думаю, что она получила всё полагающееся ей уважение. В 2004 году начальной заставкой обычно было воспроизводимое во весь экран видео. После завершения ролика загружался уровень и в дело вступал движок, но в Doom III была совершенно другая история:

Этапы:

• Загрузка уровня.
• Начинается воспроизведение ролика.
• На пятой секунде пятой минуты камера отъезжает назад.
• Видео, которое мы только что видели, было ЭКРАНОМ В ДВИЖКЕ ИГРЫ!

Помню, что когда увидел это в первый раз, то решил, что это какой-то трюк. Думал, что видеопроигрыватель прерывался и дизайнер вставил на экран дисплея текстуру, а положение камеры соответствовало последнему кадру видео. Я ошибался: idTech4 действительно может воспроизводить видео в интерактивных элементах поверхностей интерфейса пользователя. Для этого использовалась RoQ: технология, которую принёс с собой Грэм Девайн, когда пришёл в id Software.

Интересный факт:

Использованная в интро RoQ была впечатляющей для 2005 года и применение её на экране внутри игры было смелым ходом:

• Видео воспроизводится с частотой 30 кадров в секунду.
• Каждый кадр имеет разрешение 512x512: довольно высокое по тем временам
• Каждый кадр генерировался в idCinematicLocal::ImageForTime внутри ЦП и на лету загружался в видеопроцессор как текстура OpenGL.

Но интерактивные поверхности благодаря скриптингу и возможности вызывать нативные методы способны на гораздо большее.

Кого-то это очень заинтересовало и им удалось запустить на них Doom 1!

Интересный факт: технология интерактивных поверхностей также использовалась для создания всех меню Doom3 (настроек, главного экрана и т.д.).

Ещё много интересного...

Этот раздел — только вершина айсберга рендеринга, и вы можете забраться намного глубже.

Часть 4: Профилирование

В XCode есть отличный способ профилирования: Instruments. Во время игры я использовал его в режиме сэмплирования (убрав полностью загрузку игры и предварительное кэширование уровня в видеопроцессор).

Обзор

В цикле высокого уровня есть три потока, выполняемых в процессе:

• Основной поток, в котором выполняется игровая логика и визуализация.
• Вспомогательный поток, в котором накапливаются вводимые пользователем данные и микшируются звуковые эффекты.
• Музыкальный поток (потребляющий 8% ресурсов), созданный CoreAudio и вызывающий через равные интервалы idAudioHardwareOSX (примечание: звуковые эффекты обеспечиваются с помощью OpenAL, но не выполняются в их собственном потоке).

Основной поток

Основной поток Doom 3 выполняет… QuakeMain! Удивительно, что команда, портировавшая Quake 3 на Mac OS X должно быть заново использовала старый код. Внутри выполняется перераспределение времени:

• 65% отдаётся на рендеринг графики (UpdateScreen).
• 25% отдаётся игровой логике: удивительно много для игры, созданной id Software.

Игровая логика

Игровая логика выполняется в пространстве gamex86.dll (или game.dylib на Mac OS X):

Игровая логика занимает 25% времени основного потока, что непривычно много. На это есть две причины:

• Интеллектуальные агенты (ИА): виртуальная машина работает и позволяет сущностям думать. Весь байт-код интерпретируется, и похоже, что скриптовый язык используется слишком активно.
• Физический движок более сложен (решатели задачи линейной комплементарности), а потому более затратен по сравнению с предыдущими играми. Он выполняется для каждого объекта и включает в себя ragdoll-моделирование и разрешение взаимодействий.

Рендерер

Как написано выше, рендерер состоит из двух частей:

• Фронтэнд (idSessionLocal::Draw) отнимает 43,9% времени процесса рендеринга. Стоит заметить, что Draw — довольно неподходящее имя, потому что фронтэнд не выполняет ни единого вызова отрисовки OpenGL!
• Бекэнд (idRenderSessionLocale:EndFrame) занимает 55,9% времени процесса рендеринга.

Распределение нагрузки достаточно сбалансировано, и это неудивительно:

• Фронтэнд выполняет много расчётов, относящихся к определению видимых поверхностей.
• Также фронтэнд занимается анимацией моделей и нахождением силуэтов теней.
• Фронтэнд загружает вершины в видеопроцессор.
• Бекэнд тратит много времени на настройку параметров шейдеров и обмен данными с видеопроцессором (например: передаёт индексы треугольников или матрицу нормалей вершин для рельефного текстурирования в glDrawElements).

Рендерер: фронтэнд

Фронтэнд рендерера:

Неудивительно, что бо́льшая часть времени (91%) тратится на загрузку данных в VBO в видеопроцессор (R_AddModelSurfaces). Небольшая часть времени (4%) тратится на проход между областями и поиск всех взаимодействий (R_AddLightSurfaces). Минимальное время (2,9%) тратится на определение видимых поверхностей: обход BSP и проход по системе порталов.

Рендерер: бекэнд

Бекэнд рендерера:

Очевидно, что бекэнд занимается сменой буферов (GLimp_SwapBuffers) и тратит часть времени на синхронизацию (10%) с экраном, потому что игра выполняется в среде с двойной буферизацией. 5% — это затраты на избежание полной перерисовки в первом проходе, выполняющем в первую очередь заполнение Z-буфера (RB_STS_FillDepthBuffer).

Голая статистика

Если вы настроены загрузить трассировку Instruments и начать исследование самостоятельно, то вот файл профиля.

Часть 4: скриптовая виртуальная машина

Единственной частью, полностью менявшейся каждый раз с idTech1 до idTech3, была скриптовая система:

• idTech1: QuakeC, выполняемый в виртуальной машине.
• idTech2: C, компилируемый в общую библиотеку x86 (без виртуальной машины).
• idTech3: C, компилируемый с помощью LCC в байт-код, выполняемый в QVM (Quake Virtual Machine). На платформе x86 байт-код преобразовывался в нативные команды во время загрузки.

idTech4 не стал исключением, всё снова изменилось:

• Скриптинг выполняется с помощью объектно-ориентированного языка, похожего на C++.
• Язык довольно ограничен (нет typedef, пять основных типов).
• Он всегда интерпретируется в виртуальной машине: нет никакого JIT-преобразования в нативные команды, как в idTech3 (Джон Кармак подробно рассказал об этом в интервью).

Знакомство будет неплохо начать с заметок о Doom3 Scripting SDK.

Архитектура

Вот общая картина:

Компиляция: во время загрузки idCompiler передаётся один заранее заданный файл .script. Серия директив #include создаёт скриптовый стек, содержащий строки всех скриптов и исходный код всех функций. Он сканируется idLexer, генерирующим базовые лексемы (токены). Лексемы поступают в idParser и генерируется один огромный байт-код, который сохраняется в синглтоне idProgram: он представляет собой ОЗУ виртуальной машины и содержит сегменты ВМ .text и .data.

Виртуальная машина: Во время выполнения движок назначает каждому потоку idThread время реального ЦП (одному за другим), пока не будет достигнут конец связанного списка. Каждый idThread содержит idInterpreter, хранящий состояние ЦП виртуальной машины. Если только интерпретатор не сойдёт с ума и не будет выполнять больше 5 миллионов инструкций, то его не сможет опустошить ЦП: это совместная многозадачность.

Компилятор

Конвейер компиляции похож на то, что вы увидите при чтении любого другого компилятора, например Google V8 или Clang, за исключением отсутствия препроцессора. Поэтому такие функции, как «пропуск комментариев», макросы, директивы (#include,#if), должны выполняться и в лексическом анализаторе, и в парсере.

Поскольку idLexer активно используется всем движком для парсинга всех текстовых ресурсов (карт, сущностей, маршрутов камер), он очень примитивен. Например, он возвращает всего пять типов лексем:

• TT_STRING
• TT_LITERAL
• TT_NUMBER
• TT_NAME
• TT_PUNCTUATION

Поэтому парсер выполняет гораздо больше работы, чем в «стандартом» конвейере компилятора.

При запуске игры idCompiler загружает первый скрипт script/doom_main.script, серия #include создаёт стек скриптов, соединяемый в один огромный скрипт.

Похоже, что парсер движка — это стандартный нисходящий парсер с рекурсивным спуском. Похоже, что грамматика скриптового языка — это LL(1), требующая 0 возвратов (даже несмотря на то, что лексический анализатор имеет возможность отмены чтения одной лексемы). Если вы уже читали эту книгу, то не потеряетесь… а если нет, то это хороший повод начать разбираться.

Интерпретатор

Во время выполнения события вызывают создание idThread, которые являются потоками не операционной системы, а виртуальной машины. ЦП выделяет им определённое время. Каждый idThread имеет idInterpreter, следящий за указателем команд, и два стека (один для данных/параметров, другой для отслеживания вызовов функций).

Выполнение происходит в idInterpreter::Execute, пока интерпретатор не перестаёт управлять виртуальной машиной: это совместная многозадачность.

  idThread::Execute
   bool idInterpreter::Execute(void)
   {
       doneProcessing = false;
       while( !doneProcessing && !threadDying ) 
       {
           instructionPointer++;
       
           st = &gameLocal.program.GetStatement( instructionPointer );
           
           //op - это короткое число без знака (unsigned short), ВМ может иметь до 65 535 опкодов 
           switch( st->op ) {
                   .
                   .
                   .
           }
       }    
   }

После того, как idInterpreter передаёт управление, вызывается следующий метод idThread::Execute, пока не останется больше потоков, требующих времени выполнения. Общая архитектура сильно напомнила мне схему виртуальной машины Another World.

Интересный факт: байт-код никогда не преобразуется в команды x86, потому что не был предназначен для активного использования. Но в результате многое выполняется через скрипты, поэтому Doom3 очень выиграл бы от JIT-преобразования в команды x86, как в Quake3.

Автор: PatientZero

Источник