Q2VKPT: полностью переписанный Quake II с реалистичным освещением / Хабр

Quake ii rtx on steam

R_calcpalette: операции постэффектов и гамма-коррекция

Движок способен выполнять не только «попиксельное смешивание палитры» и «выбор цветового градиента на основе палитры», он может также изменять целую палитру для передачи информации о снижении здоровья или собирании предметов:

Если «анализатору» в DLL игры на стороне сервера необходимо было смешать цвета в конце процесса визуализации, ему нужно было просто задать значение переменной RGBA float player_state_t.blend[4] для любого игрока в игре. Это значение передаётся по сети, копируется в refdef.

R_CalcPalette в r_main.c:

    // newcolor = color * alpha   blend * (1 - alpha)
    
    alpha = r_newrefdef.blend[3];
    
    premult[0] = r_newrefdef.blend[0]*alpha*255;
    premult[1] = r_newrefdef.blend[1]*alpha*255;
    premult[2] = r_newrefdef.blend[2]*alpha*255;

    one_minus_alpha = (1.0 - alpha);

    in = (byte *)d_8to24table;
    out = palette[0];
    
    for (i=0 ; i<256 ; i  , in =4, out =4)
        for (j=0 ; j<3 ; j  )
            v = premult[j]   one_minus_alpha * in[j];

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

после изменения палитры вышеуказанным способом для неё необходимо выполнить гамма-коррекцию (в

R_GammaCorrectAndSetPalette

Гамма-коррекция — это ресурсоёмкая операция, включающая в себя вызов pow и деление… к тому же, её нужно было выполнять для каждого из каналов R, G и B значения цвета!

      int newValue = 255 * pow ( (value 0.5)/255.5 , gammaFactor )   0.5;

Всего получается три вызова

pow

, три операции деления, шесть операций суммирования и три умножения для каждого из 256 значений в индексе палитры — это

очень много

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

    void Draw_BuildGammaTable (void)
    {
        int     i, inf;
        float   g;

        g = vid_gamma->value;

        if (g == 1.0)
        {
            for (i=0 ; i<256 ; i  )
                sw_state.gammatable[i] = i;
            return;
        }
	
        for (i=0 ; i<256 ; i  )
        {
            inf = 255 * pow ( (i 0.5)/255.5 , g )   0.5;
            if (inf < 0)
                inf = 0;
            if (inf > 255)
                inf = 255;
            sw_state.gammatable[i] = inf;
        }
    }

Поэтому для этого трюка используется таблица поиска (

sw_state.gammatable

) и она сильно ускоряет процесс гамма-коррекции.

    void R_GammaCorrectAndSetPalette( const unsigned char *palette )
    {
        int i;

        for ( i = 0; i < 256; i   )
        {
            sw_state.currentpalette[i*4 0] = sw_state.gammatable[palette[i*4 0]];
            sw_state.currentpalette[i*4 1] = sw_state.gammatable[palette[i*4 1]];
            sw_state.currentpalette[i*4 2] = sw_state.gammatable[palette[i*4 2]];
        }

        SWimp_SetPalette( sw_state.currentpalette );
    }

Примечание:

вы можете решить, что у ЖК-экранов нет таких проблем с гаммой, как у ЭЛТ… однако они обычно

R_drawentitiesonlist: спрайты и объекты

На этом этапе процесса визуализации уровень уже отрендерен на экране:

Движок также сгенерировал 16-битный z-буфер (он был записан, но ещё не считывался):

Примечание: мы видим, что чем ближе значения, тем они «ярче» (в противоположность OpenGL, где ближе — это «темнее»). Так происходит потому, что в Z-буфере вместо Z хранится 1/Z.

16-битный z-буфер хранится начиная с указателя d_pzbuffer:

   short *d_pzbuffer;

Как сказано выше, 1/Z сохраняется с помощью прямого применения формулы, описанной в статье Майкла Абраша «Consider the Alternatives: Quake’s Hidden-Surface Removal».

Она находится в D_DrawZSpans:

    zi = d_ziorigin   dv*d_zistepv   du*d_zistepu;

Если вам интересно математическое доказательство того, что можно действительно интерполировать 1/Z, то вот статья Кок-Лим Ло (Kok-Lim Low):

Z-буфер, выведенный на этапе визуализации уровня, теперь используется в качестве входных данных для правильной обрезки сущностей.

Немного об анимированных сущностях (игроках и врагах):

В отношении освещения:

R_edgedrawing: визуализация уровня

R_EdgeDrawing

— это монстр программного рендерера, наиболее сложный для понимания. Чтобы разобраться с ним, нужно посмотреть на основную структуру данных:

Стек surf_t (действующий в качестве прокси m_surface_t) размещается в стеке ЦП.

    //Система стека поверхностей                                                                     
    surf_t  *surfaces  ;   // Массив стека поверхностей                                              
    surf_t  *surface_p ;   // Вершина стека поверхностей                                                
    surf_t  *surf_max  ;   // Верхний предел стека поверхностей     
                                       
    // поверхности генерируются bsp-деревом в порядке "сзади вперёд", поэтому если указатель                  
    // больше другого, то должен отрисовываться перед                         
    // surfaces[1] как фон, и используется как стек активных поверхностей
    
    
    Note: первый элемент surfaces - это пустая поверхность
    Note: второй элемент в surfaces - это фоновая поверхность

Этот стек заполняется при обходе BSP спереди назад. Каждый видимый полигон вставляется в стек как прокси поверхности. Позже, при обходе таблицы активных рёбер для генерирования строки экрана он позволяет очень быстро увидеть, какой полигон находится перед всеми остальными простым сравнением адреса в памяти (чем ниже в стеке, тем ближе к точке обзора). Именно так реализуется «связность» для алгоритма преобразования построчного построения изображения.

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

Стек инициализируется в самом начале R_EdgeDrawing:

R_markleaves: групповая разархивация pvs

То, как я понимал разархивацию PVS в моём

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

В первом случае ничего не сжимается. Групповое сжатие выполняется только во втором случае:

    byte *Mod_DecompressVis (byte *in, model_t *model)
    {
        static byte  decompressed[MAX_MAP_LEAFS/8];  // Лист = 1 бит, поэтому всего 65536 / 8 = 8 192 байт
                                                     // нужно для хранения полностью разархивированного PVS.
        int   c;
        byte   *out;
        int    row;

        row = (model->vis->numclusters 7)>>3;	
        out = decompressed;

        do
        {
            if (*in)            // Это ненулевой байт, записываем его в том же виде и продолжаем и переходим к следующему сжатому байту.
            {
                *out   = *in  ;
                continue;
        }
	
        c = in[1];              // Мы не "продолжили", поэтому это нулевой байт: считываем следующий байт (in[1]) и записываем
        in  = 2;                // соответствующее количество байтов в разархивированный PVS.
        while (c)
        {
            *out   = 0;
            c--;
        }


        } while (out - decompressed < row);
	
        return decompressed;
        }

Можно пропустить до 255 байт (255*8 листьев), при необходимости после них нужно снова добавить ноль с числом, которое нужно пропустить у следующих 255 байт. То есть пропуск 511 байт (511*8 листьев) занимает 4 байта: 0 — 255 — 0 — 255

Пример:

    // Пример системы с 80 листьями, представленная в 10 байтах: видимый=1, невидимый=0

    Двоичный разархивированный PVS
  
      0000 0000    0000 0000  0000 0000   0000 0000    0011 1100     1011 1111    0000 0000    0000 0000    0000 0000   0000 0000 
  
    Десятичный разархивированный PVS
    
      0x00 0x00 0x00 0x00 0x39 0xBF 0x00 0x00 0x00 0x00
  
      
    // !! СЖАТИЕ!!  
      
      
    Двоичный сжатый PVS
  
      0000 0000    0000 1000  0011 1100     1011 1111    0000 0000    0000 1000
      
    Десятичный сжатый PVS
    
      0x00 0x04 0x39 0xBF 0x00 0x04

После разархивирования PVS текущего кластера, каждая отдельная грань, принадлежащая кластеру, считающемуся в PVS видимым, тоже помечается как видимая:

В: как проверить видимость кластера с заданным идентификатором i с помощью разархивированной PVS?

О: битовым И между байтом i/8 PVS и 1 << (i % 8)

    char isVisible(byte* pvs, int i)
    {
		
	    // i>>3 = i/8    
	    // i&7  = i%8
	    
	    return pvs[i>>3] & (1<<(i&7))
	    
    }

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

int

. При начале каждого кадра счётчик кадров

r_visframecount

увеличивается на единицу в

R_MarkLeaves

. После разархивировании PVS все зоны помечаются как видимые присвоением полю

visframe

текущего значения

r_visframecount

Позже в коде видимость узла/кластера всегда проверяется следующим способом:

    if (node->visframe == r_visframecount)
	{
       // Узел видимый
	}

Архитектура quake2

Когда я читал код Quake 1, разделил

(её перевод находится

) на три части: «Сеть», «Прогнозирование» и «Визуализация». Такой подход был бы уместен и для Quake 2, потому что в основе своей движок не сильно отличается, но усовершенствования проще заметить, если разделить статью на три основных типа проектов:

Quake2 имеет однопоточную архитектуру, точка входа находится в

win32/sys_win.c

. Метод

WinMain

выполняет следующие задачи:

  game_export_t   *ge;	// Содержит указатели функций на dll игры
  refexport_t      re;  // Содержит указатели функций на dll рендерера

  WinMain()	//Из quake2.exe
  {
	  
        Qcommon_Init (argc, argv);
	
        while(1)
        {
            Qcommon_Frame
            {
                SV_Frame()  // Серверный код
                {
                    //В сетевом режиме не используется в качестве сервера
                    if (!svs.initialized) 
                       return;
                       
                    // Переход в game.dll через указатель функции
                    ge->RunFrame();
                }
            	
                CL_Frame()  // Клиентский код
                {
                    // Если только сервер ничего не рендерит
                    if (dedicated->value) 
                       return;    
                       
                    // Переход к renderer.dll через указатель функции
                    re.BeginFrame();
                    //[...]
                    re.EndFrame();
                }	
            	
            }
        }
  }

Полностью разобранный цикл можно найти в моих

Вы можете спросить: «зачем нужны такие изменения в архитектуре?». Для ответа на этот вопрос давайте посмотрим на все версии Quake с 1996 по 1997 год:

Было создано множество исполняемых файлов, и каждый раз требовалось форкать или настраивать код через препроцессор

#ifdef

. Это был полный хаос, и чтобы избавиться от него, нужно было:

Новый подход можно проиллюстрировать таким образом:

Два основных улучшения:

Эти два изменения сделали базу кода чрезвычайно элегантной и более удобной для чтения, чем у Quake 1, который страдал от энтропии кода.

С точки зрения реализации проекты DLL должны раскрывать только один метод GetRefAPI для рендереров и GetGameAPI для игры (посмотрите на файл .def в папке «Resource Files»):

reg_gl/Resource Files/reg_soft.def

    EXPORTS
        GetGameAPI

Когда ядру нужно загрузить модуль, он загружает DLL в пространство процесса, получает адрес

GetRefAPIGetProcAddress

, получает нужные указатели функций и на этом всё.

Интересный факт: при локальной игре связь между клиентом и сервером не выполняется через сокеты. Вместо этого команды скидываются в «кольцевой» (loopback) буфер с помощью NET_SendLoopPacket в клиентской части кода. Сервер реконструирует команду из того же буфера с помощью NET_GetLoopPacket.

Случайный факт: если вы видели когда-нибудь эту фотографию, то наверно интересовались, что за гигантский дисплей использовал Джон Кармак примерно в 1996 году:

Это был 28-дюймовый монитор InterView 28hd96, изготовленный Intergraph. Эта зверюга обеспечивала разрешение до 1920×1080, что довольно впечатляюще для 1995 года (подробнее можно почитать здесь (зеркало)).

Библиотека рендерера

Метод, получающий модуль рендерера, называется

VID_LoadRefresh

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

Вот что происходит на стороне ядра Quake2:

    refexport_t	re;

    qboolean VID_LoadRefresh( char *name )
    {
        refimport_t	ri;
        GetRefAPI_t	GetRefAPI;

        
        ri.Sys_Error = VID_Error;
        ri.FS_LoadFile = FS_LoadFile;
        ri.FS_FreeFile = FS_FreeFile;
        ri.FS_Gamedir = FS_Gamedir;
        ri.Cvar_Get = Cvar_Get;
        ri.Cvar_Set = Cvar_Set;
        ri.Vid_GetModeInfo = VID_GetModeInfo;
        ri.Vid_MenuInit = VID_MenuInit;
        ri.Vid_NewWindow = VID_NewWindow;        
        
        
        GetRefAPI = (void *) GetProcAddress( reflib_library, "GetRefAPI" );
        re = GetRefAPI( ri );
        
        ...
        
    }

В представленном выше коде ядро Quake2 получает указатель функции метода

GetRefAPI

от DLL рендерера с помощью

GetProcAddress

(встроенный метод win32).

Вот что происходит в GetRefAPI внутри DLL рендерера:

    refexport_t GetRefAPI (refimport_t rimp )
    {
        refexport_t	re;

        ri = rimp;

        re.api_version = API_VERSION;

        re.BeginRegistration = R_BeginRegistration;
        re.RegisterModel = R_RegisterModel;
        re.RegisterSkin = R_RegisterSkin;
        re.EndRegistration = R_EndRegistration;
        re.RenderFrame = R_RenderFrame;
        re.DrawPic = Draw_Pic;
        re.DrawChar = Draw_Char;

        re.Init = R_Init;
        re.Shutdown = R_Shutdown;

        re.BeginFrame = R_BeginFrame;
        re.EndFrame = GLimp_EndFrame;

        re.AppActivate = GLimp_AppActivate;

        return re;
}

В конце устанавливается двусторонний обмен данными между ядром и DLL. Он является полиморфным, потому что DLL рендерера возвращает внутри структуры свои собственные адреса функций и ядро Quake2 не видит разницы, оно всегда вызывает одинаковый указатель функции.

Видео работы r_edgedrawing

В видео ниже движок работает с разрешением 1024×768. Также он замедлен с помощью специальной cvar

sw_drawflat 1

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

В этом видео можно заметить очень много интересного:

1. Экран генерируется сверху вниз, это типичный алгоритм построчного построения изображений.
2. Горизонтальный интервал пикселей не записывается так, как генерировался. Это выполняется для оптимизации кэша упреждающей выборки Pentium: интервалы группируются по textureId с помощью механизма, называемого «цепочками текстур». Интервалы сохраняются в буфер. Когда буфер заполнен, интервалы отрисовываются с цепочками текстур ОДНОЙ группой.
3. Момент заполнения буфера интервалов и запуска процесса рендеринга очевиден, потому что рендеринг полигонов останавливается примерно на пятидесятой строке пикселей.
4. Интервалы генерируются сверху вниз, но отрисовываются снизу вверх: поскольку интервалы вставляются в цепочку текстур наверху списка указателей, они отрисовываются в порядке обратном их созданию.
5. Последняя группа занимает 40% экрана, а первая занимала 10%. Так происходит потому, что здесь гораздо меньше полигонов, интервалы не обрезаны и они занимают гораздо большее пространство.
6. OMG, нулевая перерисовка на этапе визуализации сплошного мира.

Визуализация сущностей

Сущности рендерятся группами: вершины, координаты текстур и указатели массивов цветов собираются и отправляются с помощью

glArrayElement

Перед визуализацией для вершин всех сущностей выполняется LERP для сглаживания анимации (в Quake1 использовались только ключевые кадры).

Используется модель освещения Гуро: массив цветов перехватывается Quake2 для хранения значения освещения. Перед визуализацией для каждой вершины выполняется расчёт значения освещения и сохраняется в массив цветов. Значение этого массива интерполируется в видеопроцессоре и получается хороший результат с освещением по Гуро.

    R_DrawEntitiesOnList 
    {
        if (!r_drawentities->value)
            return;

        // Непрозрачные сущности
        for (i=0 ; i < r_newrefdef.num_entities ; i  )
        {
          R_DrawAliasModel
          {
            R_LightPoint    /// Определение цвета освещения для применения к модели целиком
            GL_Bind(skin->texnum);  // Привязка текстуры сущности
            
            GL_DrawAliasFrameLerp()  // Отрисовка
            {
              GL_LerpVerts // Интерполяция LERP всех вершин
              
              // Расчёт освещения для каждой вершины, сохранение в массиве цветов colorArray
              for ( i = 0; i < paliashdr->num_xyz; i   )
              {
              }
              
              qglLockArraysEXT
              qglArrayElement       // ОТРИСОВКА!
              qglUnlockArraysEXT
            }
          }
        }
        
        
        
        // Сущности с прозрачностью
        for (i=0 ; i < r_newrefdef.num_entities ; i  )
        {
          R_DrawAliasModel
          {
            [...]
          }
        }
        
        
        
    }

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

Примечание: для ускорения расчётов направление света всегда принималось одинаковым ({-1, 0, 0} ), но это не отражено в движке. Цвет освещения точен и подбирается по текущему полигону, на котором основана сущность.

Это очень хорошо заметно на скриншоте ниже, где свет и тень имеют одно направление, несмотря на неправильное определение источника света.

Примечание: конечно, эта система не всегда идеальна, тень выдаётся в пустоту, а грани перезаписывают друг друга, приводя к разным уровням теней, но это всё равно довольно впечатляюще для 1997 года.

Подробнее о тенях:

Многим неизвестно, что Quake2 был способен вычислять приблизительные тени сущностей. Хотя по умолчанию эта функция отключена, её можно включить командой gl_shadows 1.

Тень всегда направлена в одну сторону (не зависит от ближайшего источника света), грани проецируются на плоскость уровня сущности. В коде R_DrawAliasModel генерирует вектор shadevector, используемый GL_DrawAliasShadow для проецирования граней на плоскость уровня сущности.

Глобальная архитектура кода

Фаза рендеринга очень проста и я не буду подробно её рассматривать, потому что она практически идентична программному рендерингу:

        R_RenderView
        {
          
            R_PushDlights          // Пометка полигона, на который воздействует динамическое освещение
            R_SetupFrame
            R_SetFrustum
            R_SetupGL              // Настройка GL_MODELVIEW и GL_PROJECTION
            
            R_MarkLeaves           // Разархивирование PVS и пометка потенциально видимых полигонов
            
            R_DrawWorld            // Рендеринг уровня, отсечение целых кластеров полигонов тестированием BoundingBox
            {
               
            }
            
            R_DrawEntitiesOnList   // Рендеринг сущностей

            R_RenderDlights        // Смешивание динамического освещения
    
            R_DrawParticles        // Отрисовка частиц

            R_DrawAlphaSurfaces    // Просвечивающие поверхности с смешиванием альфа-канала

            R_Flash                // Постэффекты (добавление красного цвета на весь экран при потере здоровья и т.п...)
        }

Все этапы наглядно показаны в видео, в котором движок «замедлен»:

Порядок визуализации:

Основная сложность кода возникает из-за разных путей в зависимости от того, поддерживает ли видеокарта мультитекстурирование и включён ли групповой рендеринг вершин. Например, если мультитекстурирование поддерживается, то

DrawTextureChainsR_BlendLightmaps

в следующем куске кода ничего не делают и только запутывают при чтении кода:

Динамическое освещение

В самом начале фазы визуализации все полигоны помечаются, чтобы показать, что они подвержены влиянию динамического освещения (

R_PushDlights

). Поэтому предварительно рассчитанная статичная карта освещения не используется. Вместо неё генерируется новая карта освещения, сочетающая в себе статичную карту освещения с добавлением света, проецируемого на плоскость полигона (

R_BuildLightMap

Поскольку карта освещения имеет максимальный размер 17×17, фаза генерирования карты динамического освещения не слишком затратна, но загрузка изменений в видеопроцессор с помощью qglTexSubImage2Dочень медленная.

Для хранения всех динамических карт освещения используется блок карт освещения размером 128×128, его id=1024. См. в разделе «Управление картами освещения» объяснение того, как все динамические карты освещения комбинируются на лету в атлас текстур.

1. Первоначальное состояние блока динамического освещения. 2. После первого кадра. 3. Через десять кадров.

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

Излучение

Как и в Quake1, влияние освещения уровня рассчитывается предварительно и хранится в текстурах, которые называются картами освещения. Однако в отличие от Quake1 Quake2 использует в предварительных расчётах излучение и цветное освещение. Карты освещения затем сохраняются в архиве

PAK

и используются в процессе выполнения игры:

Пара слов от одного из создателей: Майкл Абраш в «Black Book of Programming» (глава «Quake: a post-mortem and a glimpse into the future»):

Самые интересные изменения графики заключались в предварительных расчётах, куда Джон добавил поддержку излучаемого света…Обработка уровней Quake 2 занимала до часа времени.

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

Если вы хотите узнать об излучаемом освещении, то прочитайте эту потрясающе хорошо иллюстрированную

): это просто шедевр.

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

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

Интересный факт: карты освещения могут иметь любой размер от 2×2 до 17×17 (несмотря на заявленный максимальный размер 16 в статье flipcode (зеркало)) и не обязаны быть квадратными.

Использование указателей функций

После передачи указателей методов включается полиморфизм. Здесь в коде ядро «перепрыгивает» к разным модулям:

Рендерер «перепрыгивает» к SCR_UpdateScreen:

    // это метод quake.exe, рендерер абстрагирован, поэтому quake2.exe не знает, какой рендерер используется.
    SCR_UpdateScreen()
    {
        // re - это struct refexport_t, BeginFrame указывает на BeginFrame в DLL.
        re.BeginFrame( separation[i] );
	    
        // С этого момента методы принадлежат DLL
            SCR_CalcVrect()
            SCR_TileClear()
            V_RenderView()
            SCR_DrawStats
            SCR_DrawNet
            SCR_CheckDrawCenterString
            SCR_DrawPause
            SCR_DrawConsole
            M_Draw
            SCR_DrawLoading
        
        re.EndFrame();
        // Возврат к методам quake.exe.
    }

Игра «перепрыгивает» к

SV_RunGameFrame

    void SV_RunGameFrame (void)    
    {        
	    sv.framenum  ;        
	    sv.time = sv.framenum*100;        // не выполняется, если игра поставлена на паузу
	    
	    if (!sv_paused->value || maxclients->value > 1)            
	        
	        ge->RunFrame ();
	        
	        ....
        }
    }

Мой quake2

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

printf

данные в процессе, а не ставить игру на паузу для изучения консоли Quake:

Добавить консоль в стиле DOS в окно Win32 довольно просто:

    // sys_win.c

    int WINAPI WinMain (HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow)
    {
	    
	   AllocConsole();
	   freopen("conin$","r",stdin);
	   freopen("conout$","w",stdout);
	   freopen("conout$","w",stderr);
	   consoleHandle = GetConsoleWindow();
	   MoveWindow(consoleHandle,1,1,680,480,1);
	   printf("[sys_win.c] Console initialized.n");
	    
     
	   ...   
	   
    }

Поскольку я запускал Windows на Mac с помощью Parallels, было сложно нажимать «printscreen» при выполнении игры. Для создания скриншотов я задал клавишу «*» с цифрового блока:

    // keys.c
    
    if (key == '*')
    {
        if (down)  //Избегаем автоматического повтора!
            Cmd_ExecuteString("screenshot");
    }

И, наконец, я добавил множество комментариев и схем. Вот «мой» полный исходный код:

Общая архитектура

Определившись с основным ограничением (палитрой), можно перейти к общей архитектуре рендерера. Его философия использовала сильные стороны Pentium (вычисления с плавающей точкой) для снижения влияния слабых сторон: скорости шины, влиявшей на запись пикселей в память. Бóльшая часть пути рендеринга сосредоточена на достижении

нулевой

перерисовки. В сущности, путь программного рендеринга аналогичен способу программного рендеринга Quake 1. В нём для обхода карты активно использовались BSP и PVS (набор потенциально видимых полигонов) для получения набора полигонов, которые нужно рендерить. Каждый кадр рендерятся три различных элемента:

Примечание:

если вы не знакомы с этими «старыми» алгоритмами, крайне рекомендую прочитать главы 3.6 и 15.6 книги

Джеймса Д. Фоли (James D. Foley). Также можно найти множество информации в главах 59-70 книги

Майкла Абраша (Michael Abrash).

Вот псевдокод высокого уровня:

1. Рендеринг карты
2. Рендеринг сущностей, использование Z-буфера для определения видимых частей сущностей.
3. Рендеринг просвечивающих текстур с помощью остроумного трюка с палитрой для попиксельного вычисления индексов палитры просвечивания.
4. Рендеринг частиц.
5. Добавление постэффектов (полноэкранное смешивание с красным цветов в случае снижения здоровья).

Визуализация экрана:

индексы палитры записываются в закадровый буфер. В зависимости от режима (полноэкранный/оконный) используется DirectDraw или GDI. После завершения закадрового буфера кадров он передаётся в экранный буфер видеокарты (GDI=>

rw_dib.c

DirectDraw=>

rw_ddraw.c

) с помощью либо

BitBltWinGDI.h

или

BltFastddraw.h

Перспективное проецирование для бедных?

В разных статьях в Интернете предполагается, что Quake2 использует «перспективное проецирование для бедных» с помощью простой формулы и без гомогенных координат или матриц (код ниже из

R_ClipAndDrawPoly

    XscreenSpace = X / Z * XScale
    YscreenSpace = Y / Z * YScale

Где XScale и YScale определяются по области обзора и соотношению сторон экрана.

Такое перспективное проецирование на самом деле аналогично тому, что происходит в OpenGL на этапе деления GL_PROJECTION W:

    Перспективное проецирование:
    =======================
                                                 Вектор координат глаза
                                                        
                                            |      X                              
                                            |      Y
                                            |      Z
                                            |      1
     --------------------------------------------------  
            Матрица перспективного проецирования   |
                                            |
       XScale       0        0        0     |     XClip
          0      YScale      0        0     |     YClip
          0         0        V1       V2    |     ZClip
          0         0        -1       0     |     WClip
          
          
          
     Координаты обрезки:    
     ================                             XClip =  X * XScale
                                                  YClip =  Y * YScale     
                                                  ZClip =  /
                                                  WClip = -Z
      
     Координаты NDC с делением W:
     =========
     
                      XNDC = XClip/WClip =  X * XScale / -Z
                      YNDC = YClip/WClip =  Y * YScale / -Z

Первое наивное доказательство: сравните наложенные скриншоты. Если мы посмотрим в код: проецирование для бедных? Нет!

Подсистема консоли

Ядро Quake2 содержит мощную систему консоли, активно использующую списки указателей и линейный поиск.

В ней есть три типа объектов:

С точки зрения кода каждый тип объектов имеет список указателей:

    cmd_function_t    *cmd_functions     // Список указателей, каждый элемент содержит имя строки и указатель функции: void (*)() .
	      
	      
    cvar_t            *cvar_vars         // Список указателей, каждый элемент содержит имя строки и строковое значение.
	      
	      
    cmdalias_t        *cmd_alias         // Список указателей, каждый элемент содержит имя строки и псевдоним строки.

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

cmd_argccmd_argv

    static   int       cmd_argc;                     
    static   char     *cmd_argv[MAX_STRING_TOKENS];

Пример:

Каждый идентифицированный в буфере токен копируется memcpy в место, указанное malloc записью cmd_argv. Процесс довольно неэффективный и показывает, что этой подсистеме уделили мало внимания. И это, кстати, полностью оправданно: она редко используется и мало влияет на игру, так что оптимизация не стоила усилий. Лучшим подходом был бы патчинг исходной строки на месте и запись значения указателя для каждого токена:

Поскольку токены находятся в массиве аргументов, то cmd_argv[0] проверяется очень медленным и линейным способом на соответствие всем функциям, объявленным в списке указателей функций. Если соответствие находится, то вызывается указатель функции.

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

И, наконец, если ничего из вышеперечисленного не срабатывает, то Quake2 обрабатывает токен как объявление переменной (или как её обновление, если переменная уже находится в списке указателей).

Здесь выполняется множество линейных поисков в списке указателей: идеальным выходом было бы использование таблицы хэшей. Она позволила бы достичь сложности O(n) вместо O(n²).

Интересный факт о парсинге 1: таблица ASCII организована умно: при парсинге строки для создания токенов можно пропустить разделители и символы пробела, просто проверяя, меньше ли ли символ i символа ‘ ‘ (пробела).

    char* returnNextToken(char* string)
    {
        while (string && *string < ' ')
            string  ;
						    
        return string;
    }

Интересный факт о парсинге 2:

таблица ASCII была организована очень умно: можно было преобразовать символ c в целое число следующим образом:

int value = c — ‘0’;

    int charToInt(char v)
    {
        return  v  - '0' ;
    }

Кэширование значения cvar:

Поскольку поиск места cvar в памяти (Cvar_Get) в этой системе имеет сложность O(n²) (линейный поиск strcmp для каждой записи), рендереры кэшируют место cvar в памяти:

    //Кэширование переменной
    cvar_t		*crosshair;
	    
    // На этапе инициализации движка, здесь создаётся 
    // и возвращается место Cvar в памяти.
    
    crosshair = Cvar_Get ("crosshair", "0", CVAR_ARCHIVE);    //ЭТО МЕЕЕДЛЕННО 
    
    
    //В рендерере, при выполнении программы.
    void SCR_DrawCrosshair (void)
    {                          
	      
        if (!crosshair->value)                                 //ЭТО БЫСТРО   
            return;
    }

Доступ к этому значению затем можно получить за O(1).

Подсистема поверхностей: mip-текстурирование

При проецировании полигона в экранное пространство генерируется 1/Z его расстояния. Ближайшая вершина используется для определения того, какой нужно использовать уровень MIP-текстур. Вот пример карты освещения и того, как она фильтруется в соответствии с уровнем MIP-текстур:

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

Ниже представлены результаты теста, выполненного для карты освещения размером 13×15 текселов:

Уровень 3 MIP-текстур: блок имеет размер 2×2 тексела.
Уровень 2 MIP-текстур: блок имеет размер 4×4 тексела.
Уровень 1 MIP-текстур: блок имеет размер 8×8 текселов.
Уровень 0 MIP-текстур: блок имеет размер 16×16 текселов.

Ключ к пониманию фильтрации заключается в том, то всё основано на размере полигонов в пространстве мира (ширина и высота называются extent):

На рисунке ниже размеры полигона (3,4), карты освещения — (4,5) текселов, а вырожденная поверхность

всегда

имеет размер (3,4) блока. Уровни MIP-текстур определяют размеры блока в текселах, а значит и общий размер поверхности в текселах.

Всё это выполняется в R_DrawSurface. Уровень MIP-текстур выбирается с помощью массива указателей функций (surfmiptable), выбирающего нужную функцию растеризации:

Подсистема поверхностей: кэширование

Даже несмотря на то, что движок активно использует для управления памятью

mallocfree

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

    size = SURFCACHE_SIZE_AT_320X240; 

    pix = vid.width*vid.height;		
    if (pix > 64000)				
        size  = (pix-64000)*3;	

        
    size = (size   8191) & ~8191;
        
    sc_base = (surfcache_t *)malloc(size);
	sc_rover = sc_base;

Ровер

sc_rover

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

Вот как новый фрагмент памяти выделяется из блока:

    memLoc = (int)&((surfcache_t *)0)->data[size];     // Пропуск размера   обеспечение достаточного места для заголовка фрагмента памяти.
    
    memLoc = (memLoc   3) & ~3;                         // FCS: округление до числа, кратного 4
    
    sc_rover = (surfcache_t *)( (byte *)new   size);

Примечание:

трюк с быстрым назначением кэша (может перейти в систему памяти)

Примечание: заголовок размещается поверх запрошенного объёма памяти. Очень странная строка, использующая указатель NULL (((surfcache_t *)0)) (но с ней всё в порядке, потому что нет задержки).

Программный рендерер

Программный рендерер Quake2 — это самый большой, наиболее сложный, а потому самый интересный модуль для исследований.

Здесь нет никаких скрытых механизмов, начиная с диска и заканчивая пикселями.

Весь код написан аккуратно и оптимизирован вручную. Он — последний в своём роде и ознаменовал конец эры. Позже индустрия полностью перешла исключительно к рендерингу с аппаратным ускорением.

Фундаментальное отличие программного рендеринга и рендеринга OpenGL — использование системы 256-цветной палитры вместо привычной сегодня системы 24-битного True Color RGB:

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

Но за исключением этого движку удавалось выполнять потрясающую работу с помощью очень умного использования палитры, о котором я расскажу позже:

Сначала загружается палитра Quake2 из архивного файла PAK

pics/colormap.pcx

Примечание: значение чёрного цвета равно 0, белого — 15, зелёного — 208, красного — 240 (в левом нижнем углу), прозрачного — 255.

Первым делом выполняется перестановка этих 256 цветов в соответствии с pics/colormap.pcx:

Такая схема 256×320 используется как таблица поиска, и это необыкновенно умно, потому что даёт множество интересных возможностей:

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

программный рендерер Quake2 изначально благодаря технологии MMX должен был быть основан на RGB, а не на палитре, о чём Джон Кармак заявил после выпуска Quake1 в этом видео (момент на 10 минуте 17 секунде):

MMX — это SIMD-технология, позволявшая работать со всеми тремя каналами RGB с затратой всего одного канала, обеспечивая таким образом смешивания с допустимым потреблением ресурсов ЦП. Я предполагаю, что от неё отказались по следующим причинам:

Профайлинг

Я пробовал использовать разные профайлеры, все они интегрированы в Visual Studio 2008:

Привязка к сэмплированию времени показала

очень

разные результаты. Например, Vtune учитывал затраты на передачу из ОЗУ в видеопамять (

BitBlit

), но другие профайлеры упустили их.

Профайлерами Intel и AMD не удалось проверить оборудование (и я не настолько мазохист, чтобы выяснять, почему так получилось), но профайлер VS 2008 Team справился… хотя я и не рекомендую его: игра работала с частотой три кадра в секунду, и на анализ 20-секундной игры потребовался целый час!

Профайлинг VS 2008 Team edition:

Результаты говорят сами за себя:

Взглянем повнимательней на траты времени ref_soft.dll:

Профайлинг Intel VTune:

Заметно следующее:

А вот более

с помощью VTune.

Профайлинг AMD Code Analysis

Ядро здесь и ref_sof здесь.

Рендерер opengl

Quake2 стал первым движком, выпущенным с нативной поддержкой рендеринга с аппаратным ускорением. Он демонстрировал несомненные улучшения благодаря билинейной фильтрации текстур, увеличению мультитекстурирования и 24-битному смешиванию цвета.

С точки зрения пользователя версия с аппаратным ускорением обеспечивала следующие улучшения:

Не могу удержаться от цитаты из «Masters of Doom» о том, как Джон Ромеро впервые увидел цветное освещение

[прим. пер.: до начала работы над Quake 2 он уже покинул id Software и создал собственную компанию Ion Storm]Затем Ромеро подошёл к стенду id […].

Он пробился сквозь толпу, чтобы посмотреть на демо Quake II. Его лицо стало жёлтым, а челюсть отвисла: цветное освещение! Ромеро не мог поверить в то, что он видит. На экране был похожий на подземелье военный уровень, но когда игрок стрелял из оружия, жёлтый луч выстрела отбрасывал такой же жёлтый свет на стены. Он был слабым, но Ромеро видел динамическое цветное освещение. В тот момент он ощутил те же чувства, которые испытал в Softdisk, когда впервые увидел Dangerous Dave in Copyright Infringement [прим. пер.: созданное Кармаком в 1990 году демо первого платформера на PC с скроллингом экрана].

«Твою мать», — пробормотал он. Кармаку снова удалось удивить его.

Эта особенность оказала сильное влияние на разработку Daikatana.

С точки зрения кода рендерер на 50% меньше, чем программный рендерер (см. «Статистику кода» в конце страницы). Это значило, что разработчикам требовалось меньше работы. Также такая реализация была гораздо проще и элегантнее, чем программная/оптимизированная на ассемблере версия:

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

Интересный факт: кадр Quake2 обычно содержит по 600-900 полигонов: разительное отличие от миллионов полигонов в любом современном движке.

Старый добрый opengl…

Где моя glGenTextures?!:

Сегодня openGL-разработчики запрашивают textureID из видеопроцессора через glGenTextures. Quake2 не утруждался этим и выбирал идентификатор самостоятельно. Поэтому цветовые текстуры начинались с 0, текстура динамической карты освещения всегда имела идентификатор 1024, а статичная карта освещения с 1025 по 1036.

Печально известный режим Immediate mode:

Данные вершины передаются в видеокарту с помощью ImmediateMode. По два вызова функции на вершину (glVertex3fv и glTexCoord2f) для рендеринга мира (поскольку полигоны отсекались индивидуально, невозможно было собрать их в группы).

Групповая визуализация выполнялась для моделей (врагов, игроков) с помощью glEnableClientState (GL_VERTEX_ARRAY). Вершины, передаваемые в glVertexPointer и glColorPointer, использовались для передачи значения освещения, вычисляемого в ЦП.

Мультитекстурирование:

Код усложнён тем, что стремится подстроиться к оборудованию поддерживающему и не поддерживающему новую технологию… мультитекстурирования.

Нет использования GL_LIGHTING:

Поскольку все вычисления выполнялись в ЦП (генерирование текстур для мира и значение освещённости вершин для сущностей), в коде нет следов GL_LIGHTING.

Поскольку OpenGL 1.0 всё равно выполнял затенение по Гуро (интерполируя цвета между вершинами) вместо затенения по Фонгу (где нормали интерполируются для реального «попиксельного освещения»), то использование GL_LIGHTING плохо бы выглядело для мира, потому что требовало бы создания вершин на лету.

Его «можно» было применить для сущностей, но при этом пришлось бы отправлять и векторы нормалей вершин. Похоже, это сочли неподходящим, поэтому вычисление значений освещения выполняется в ЦП. Значение освещения передаётся из массива цветов, значения интерполируются в ЦП для получения затенения по Гуро.

Технические подробности

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

). Этот фильтр используется поверх уже широко распространённого временного сглаживания (temporal anti-aliasing) и расширяет процесс отслеживания временнЫх изменений из простого пространства изображения в высокоразмерное пространство путей распространения света.

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

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

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

Однако оказалось, что такие вычисления сложно сделать точными, а вычислительные затраты на обход иерархии сложно контролировать. Так как в оригинальном Quake II использовались множества потенциально видимых пространств (Potentially-Visible-Set) для отсечения невидимых частей сцены, мы решили обойтись извлечением из этих множеств списков потенциально видимых источников для каждой части сцены.

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

Управление памятью

У Doom и Quake1 был собственный диспетчер памяти под названием «Zone Memory Allocation»: при запуске выполнялась

malloc

и блок памяти управлялся с помощью списка указателей. Зону памяти (Memory Zone) можно было пометить для быстрой очистки нужной категории памяти. Zone Memory Allocator (

common.c: Z_Malloc, Z_Free, Z_TagMalloc , Z_FreeTags

) остался в Quake2, но он довольно бесполезен:

По-прежнему очень полезно измерять потребление памяти благодаря атрибуту

size

в заголовке, вставляемому перед распределением каждого блока памяти:

    #define    Z_MAGIC    0x1d1d


    typedef struct zhead_s
    {
	    
    struct   zhead_s    *prev, *next;
    short    magic;
    short    tag;			// для групповой очистки
    int      size;
    
    } zhead_t;

Система кэширования поверхностей имеет собственный диспетчер памяти. Объём распределённой памяти зависит от разрешения и определяется странной формулой, которая однако, очень эффективно защищает от мусора:

      Первоначальная malloc кэширования поверхностей:
      ==============================
      
        size = SURFCACHE_SIZE_AT_320X240;  //1024*768

        pix = vid.width*vid.height;	
        	
        if (pix > 64000)				
           size  = (pix-64000)*3;

«Hunk allocator» используется для загрузки ресурсов (изображений, звуков и текстур). Он довольно хорош, пытается использовать virtualAlloc и соотносить данные с размером страницы (8 КБ, несмотря на то, что в Win98 использовался 4 КБ?! Что за дела?!).

И, наконец, есть также множество стеков FIFO (среди прочего, для хранения интервалов), и несмотря на очевидно ограниченные возможности, они работают очень хорошо.

Управление текстурами

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

С помощью отладчика OpenGL gDEBugger можно с лёгкостью покопаться в памяти видеопроцессора и получить статистику:

Как мы видим, у каждой цветовой текстуры есть собственный идентификатор текстуры (textureID). Статичные карты освещения загружаются как атлас текстур (называемый в quake2 «блоком») в таком виде:

Почему же цветовая текстура находится в отдельной текстуре, если карты освещения собраны в атлас текстур?

Причина заключается в оптимизации цепочек текстур:

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

     for(i=0 ; i < polys.num ; i  )     
     {
         glBindTexture(polys[i].textureColorID , GL_TEXTURE0);
         glBindTexture(polys[i].textureLightMapID , GL_TEXTURE1);
         RenderPoly(polys[i].vertices);
     }

Если каждый полигон имеет цветовую текстуру и текстуру карты освещения, то тут мало что можно сделать, но Quake2 собирает свои карты освещения в атласы, которые легко сгруппировать по идентификатору. Поэтому полигоны не рендерятся в порядке, возвращаемом из BSP. Вместо этого они группируются в цепочки текстур на основании того, к какому атласу текстур карт освещения они относятся:

     glBindTexture(polys[textureChain[0]].textureLightMapID , GL_TEXTURE1);
  
     for(i=0 ; i < textureChain.num ; i  )     
     {
         glBindTexture(polys[textureChain[i]].textureColorID , GL_TEXTURE0);
         RenderPoly(polys[textureChain[i]].vertices);
     }

В видео ниже показан процесс визуализации «цепочек текстур»: полигоны рендерятся не в зависимости от расстояния, а на основании блока карт освещения, к которым они относятся:

Примечание:

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