10 октября 2026Команда Сарнас

Quake на безопасном Rust: как устроен движок в браузере

Как оригинальный движок Quake управляет ресурсами и строит геометрию уровня — от кэширования моделей до обхода BSP-дерева при рендере и трассировке коллизий. Разбор показывает, как классические приёмы идемпотентной загрузки и рекурсивного обхода ложатся на безопасный Rust при переносе движка в браузер. Полезно тем, кто хочет понять внутренности игровых движков и оценить, какие компромиссы возникают при переписывании legacy-кода на современный язык.

Разбираем механику оригинального движка Quake: как модели попадают в кэш и покидают его, как строится BSP-дерево и обходится при рендере, как распаковывается видимость, как формируются спаны сканлайнов, как трассируются коллизии и как всё это видит игрок в браузере.

Жизненный цикл модели: поиск, кэш, выгрузка

Модель опознаётся по имени. Mod_FindName перебирает известные модели и при совпадении имени прекращает поиск. Если совпадения нет и число известных моделей меньше MAX_MOD_KNOWN, счётчик известных моделей увеличивается, имя копируется, а модель помечается как NL_NEEDS_LOADED — «ещё не загружена»: это одно из состояний NL_*.

Когда предел MAX_MOD_KNOWN достигнут, начинается переиспользование: берётся ранее найденная «доступная» модель (состояние NL_UNREFERENCED), и если это alias-модель, её кэш освобождается через Cache_Free. кэш модели. Если доступной модели нет — Sys_Error, аварийное завершение.

Загрузка начинается с проверки кэша. Для alias-модели вызывается Cache_Check: при попадании модель помечается NL_PRESENT и возвращается без чтения файла. Для остальных типов достаточно проверить, что состояние уже NL_PRESENT. Если модель не в кэше, файл читается целиком одним вызовом COM_LoadStackFile, и по первому слову заголовка выбирается загрузчик: IDPOLYHEADER — alias, IDSPRITEHEADER — спрайт, иначе — brush-модель (геометрия уровня).

Отдельная функция Mod_TouchModel вызывает Mod_FindName, и если модель уже NL_PRESENT и является alias-моделью, дёргает Cache_Check — это отметка «недавно использована», чтобы кэш её не выгрузил.

Комментарий «because the world is so huge, load it one piece at a time» стоит непосредственно перед чтением файла. Он относится к тому, что модель читается целиком одним вызовом, а не к разбиению мира на части: сам мир потом грузится по отдельным lump через последовательность Mod_Load*-функций.

Ошибки загрузки и что видит клиент

Порядок такой: сначала проверка «уже загружена» (для alias — через Cache_Check, иначе по NL_PRESENT), затем чтение файла. Если буфер пуст и флаг crash истинен — Sys_Error с сообщением об отсутствии модели; если crash ложен — возврат NULL, при этом mod->type не меняется. После успешного чтения состояние становится NL_PRESENT, и по заголовку выбирается загрузчик.

Тип модели выставляется внутри конкретного загрузчика: например, brush-загрузчик первым делом ставит mod_brush. При повреждённом файле — неверная версия, отсутствие вершин, слишком высокий скин, ненулевой интервал — соответствующий загрузчик вызывает Sys_Error, что аварийно завершает программу.

Клиент видит результат через возвращаемое значение Mod_ForName: при crash=false и отсутствии файла — NULL, при crash=true — падение с сообщением об ошибке.

BSP-дерево: узлы, листья, порядок обхода

Загрузчик узлов читает их из lump и для каждого заполняет границы, плоскость разреза и двух детей. Индекс ребёнка кодирует его тип: неотрицательный — это узел, отрицательный — лист (по формуле -1 - p). После загрузки узлов и листьев вызывается Mod_SetParent от корня, который рекурсивно проставляет каждому узлу поле parent и останавливается на листьях: у листа contents меньше нуля.

При рендере порядок обхода детей задаёт R_RecursiveWorldNode: сторона выбирается по знаку скалярного произведения (side = 0, если dot >= 0, иначе 1), сначала рекурсивно обходится ближний ребёнок children[side], затем рисуются поверхности узла, и только потом — дальний children[!side]. Это и есть «front side first».

В трассировке SV_RecursiveHullCheck порядок другой: при t1 >= 0 && t2 >= 0 идём в children[0], при t1 < 0 && t2 < 0 — в children[1]. При пересечении плоскости сначала рекурсивно проверяется ближняя половина отрезка (children[side]), затем проверяется содержимое children[side^1] в средней точке mid, и только если та не сплошная — проверка продолжается по дальней половине. Порядок обхода определяет, какая поверхность обрабатывается первой и какая точка столкновения будет найдена первой.

Видимость: распаковка PVS

PVS хранится в сжатом виде. Mod_DecompressVis распаковывает её в статический буфер размером MAX_MAP_LEAFS/8 байт. Длина строки вычисляется как (model->numleafs+7)>>3 — число байт, нужное для битовой маски по всем листьям модели.

Если входной указатель in равен NULL, информации о видимости нет, и все листья помечаются видимыми: каждый байт заполняется 0xff, то есть восемью единичными битами. Иначе идёт цикл: ненулевой байт копируется как есть, а нулевой — признак RLE, где следующий байт задаёт количество нулевых байт для записи. Цикл продолжается, пока не заполнено ровно row байт.

Mod_LeafPVS возвращает указатель на видимость листа: для нулевого листа (leaf == model->leafs) возвращается mod_novis, иначе распаковываются сжатые данные листа.

Пометка листьев перед рендером

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

Если vis-информация отсутствует, распаковка делает все листья видимыми. При отключённой видимости (когда лист совпадает с model->leafs) возвращается mod_novis, что приводит к пометке всех листьев как видимых.

Обход дерева при рендере: отсечения

R_RecursiveWorldNode отбрасывает узел, если он сплошной (contents == CONTENTS_SOLID) или не помечен видимым в текущем кадре (visframe != r_visframecount). Затем, если заданы clipflags, для каждого из четырёх плоскостей проверяется, нужно ли клипать по этому плану. Из границ узла берётся «отвергающая» точка, и если её скалярное произведение с нормалью плана минус dist не больше нуля — узел отбрасывается целиком. Если же «принимающая» точка даёт неотрицательное значение, соответствующий бит сбрасывается: узел полностью на экране, клипать по этому плану не нужно.

Для листа помечаются видимыми его поверхности, обрабатываются фрагменты моделей и присваивается ключ. Для внутреннего узла выбирается сторона по знаку dot, рекурсивно обходится передняя сторона, рисуются поверхности узла, затем обходится задняя.

Комментарий «FIXME: use bounding-box-based frustum clipping info?» стоит в функциях отрисовки submodel-полигонов — там поверхности проверяются по одной через скалярное произведение, без использования bounding box для отсечения по пирамиде видимости.

Клиппинг submodel-полигонов и трансформация плоскостей

R_DrawSolidClippedSubmodelPolygons перебирает поверхности модели, и для каждой по знаку скалярного произведения решает, рисовать ли полигон — с учётом флага SURF_PLANEBACK и BACKFACE_EPSILON. Затем рёбра поверхности копируются в локальный массив, при отрицательном surfedge вершины меняются местами, чтобы сохранить порядок обхода, и вызывается R_RecursiveClipBPoly.

Тот для каждого узла BSP преобразует плоскость узла в пространство модели: dist уменьшается на проекцию начала координат сущности на нормаль, нормаль умножается на матрицу поворота сущности. Каждое ребро проверяется по этой плоскости: вычисляются расстояния до неё у концов, и если знаки различаются, ребро разрезается в точке с долей пути frac = lastdist / (lastdist - dist), создаётся новая вершина и два ребра — по одному на каждой стороне. Если что-то было отрезано, вдоль плоскости разреза добавляются два противоположно направленных ребра. Затем рекурсия спускается в детей узла, рисуя непустые листья.

R_EntityRotate умножает вектор на матрицу поворота построчно, а R_RotateBmodel строит эту матрицу из углов сущности (yaw, pitch, roll) и применяет её к направлению взгляда и базису камеры.

Порядок отрисовки поверхностей

R_RenderWorld устанавливает текущую сущность в нулевую (мир), копирует позицию камеры в modelorg, берёт модель этой сущности и запускает рекурсивный обход дерева с clipflags=15. Внутри для каждого узла поверхности обрабатываются в зависимости от знака dot: при положительном значении поверхность с совпадающим visframe либо сразу рисуется, либо, если включён режим отложенной отрисовки полигонов, откладывается в массив, иначе сразу идёт на отрисовку.

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

Спаны сканлайнов: активный список рёбер и поверхностей

R_ScanEdges подготавливает буфер спанов и инициализирует активный список рёбер: голова, хвост и «после хвоста». R_GenerateSpans обнуляет счётчик активных bmodel-поверхностей, сбрасывает активные поверхности до фоновой и проходит по рёбрам: для левой поверхности ребра вызывается R_TrailingEdge, затем R_LeadingEdge, в конце — R_CleanupSpan. Обратный вариант делает то же, но для правой поверхности вызывает R_LeadingEdgeBackwards.

Сортировка активных поверхностей поддерживается вставкой новой поверхности перед surf2 по ключу. R_CleanupSpan завершает незакрытые поверхности: для верхней поверхности создаёт span от её last_u до хвоста, затем сбрасывает состояние у всех поверхностей в стеке. Комментарий «push it back to keep it sorted» относится к рёбрам: после прибавления шага к координате, если ребро оказалось левее предыдущего, оно вынимается из списка и вставляется обратно в отсортированную позицию, чтобы порядок по u сохранялся.

Вход и выход поверхности на сканлайне

R_LeadingEdge вызывается для ребра с правой поверхностью, увеличивает счётчик её появлений и, если это первое появление, вставляет поверхность в стек по ключу. При совпадении ключей у двух bmodel-поверхностей сравнивается 1/z через параметры перспективы. Если новая поверхность оказывается ближе, эмитится span для ранее верхней поверхности и обновляется её last_u, после чего новая вставляется перед ней. Обратный вариант ищет позицию по обратному сравнению ключей, без z-сравнений, и тоже эмитит span при новом верхе.

R_TrailingEdge уменьшает счётчик появлений и, если стало ноль, при необходимости уменьшает счётчик активных bmodel-поверхностей. Если поверхность была верхней, эмитится span до текущей координаты, обновляется last_u следующей и поверхность удаляется из стека.

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

Трассировка по hull-дереву и эпсилон 1/32

SV_RecursiveHullCheck рекурсивно обходит hull-дерево, проверяя, с какой стороны плоскости узла находятся концы отрезка. Для осевых плоскостей расстояние берётся как разность координаты и dist, иначе — через скалярное произведение. Если оба конца по одну сторону, рекурсия идёт в соответствующего потомка без вычисления пересечения.

При пересечении вычисляется доля пути до точки пересечения, сдвинутая на DIST_EPSILON (0.03125, то есть 1/32) в сторону ближней стороны — «put the crosspoint DIST_EPSILON pixels on the near side». Доля ограничивается диапазоном от 0 до 1, затем вычисляется промежуточная точка. Рекурсия сначала идёт в сторону ближнего конца, затем проверяется, не является ли промежуточная точка в противоположном потомке сплошной; если нет — рекурсия продолжается от середины до конца. Если противоположная сторона сплошная, фиксируется точка удара: нормаль и dist плоскости копируются в результат с учётом знака стороны.

Эпсилон 1/32 нужен, чтобы точка пересечения не попадала точно на плоскость и не вызывала ошибок плавающей точки: «1/32 epsilon to keep floating point happy».

Клиппинг движения: bounding box и обход area-дерева

SV_ClipMoveToEntity сначала заполняет результат по умолчанию: обнуляет структуру, ставит долю пути в 1, помечает «всё сплошное» и копирует конечную точку. Затем выбирает клип-оболочку для сущности, смещает начало и конец на смещение оболочки и запускает трассировку по hull-дереву.

SV_ClipToLinks обходит сущности узла area-дерева, пропуская не-твёрдые, самого инициатора и триггеры (для триггера — ошибка). Для режима «без монстров» пропускается всё, кроме brush-моделей. Отсекается по пересечению bounding box движения с границами объекта, затем вызывается клиппинг с расширенными или обычными границами в зависимости от флага монстра. Результат заменяется, если новый сплошной, начинается в сплошном или даёт меньшую долю пути.

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

SV_MoveBounds строит bounding box движения покомпонентно: если конец больше начала, нижняя граница — начало плюс минимум минус 1, верхняя — конец плюс максимум плюс 1; иначе наоборот. SV_Move создаёт структуру движения, копирует параметры, для ракеты задаёт расширенные границы ±15, иначе копирует обычные, строит bounding box и запускает обход area-дерева.

Связь edict с листьями и area-нодами

edict привязывается к area-дерево, чтобы движок мог быстро находить сущности рядом с заданной точкой, не перебирая все подряд. Привязка нужна, когда сущность появляется или двигается; отвязка — когда она покидает мир или меняет положение, чтобы не оставаться в списке старой области.

Area-дерево строится рекурсивно. SV_CreateAreaNode обнуляет списки триггеров и твёрдых сущностей, и если достигнута глубина AREA_DEPTH, помечает узел листом. Иначе выбирает ось по большей стороне, вычисляет dist как середину по этой оси и создаёт двух детей. SV_ClearWorld обнуляет массив узлов и создаёт корневой узел по границам модели мира.

SV_LinkEdict вычисляет абсолютные границы сущности (с расширением для предметов на 15 по горизонтали, иначе на 1 по всем осям), обнуляет число листьев и при наличии модели находит затронутые листья. SV_FindTouchedLeafs рекурсивно обходит BSP-дерево, пропускает сплошное, добавляет лист в список при достижении листа и рекурсирует по сторонам, которые пересекает абсолютный бокс.

Далее SV_LinkEdict ищет первый узел area-дерева, который пересекает бокс, и вставляет сущность в список триггеров или твёрдых сущностей, а при необходимости вызывает обработку касаний. SV_TouchLinks обходит триггеры узла, пропускает себя, сущности без обработчика касания и не-триггеры, проверяет пересечение боксов, выставляет контекст и выполняет обработчик, затем рекурсивно спускается в детей по условиям выхода границ за dist. SV_UnlinkEdict удаляет сущность из списка и обнуляет связи.

Загрузка alias-моделей: кадры и группы

Загрузчик alias-модели читает заголовок, проверяет версию и размеры, затем последовательно грузит скины, координаты текстур, треугольники и кадры. Кадры обрабатываются циклом: для каждого читается тип, и в зависимости от него вызывается загрузчик одиночного кадра или группы.

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

Комментарий «these are byte values, so we don't have to worry about endianness» относится к полям ограничивающих рамок: они имеют тип byte, поэтому не требуют преобразования порядка байтов — в отличие от многобайтовых полей, для которых применяются LittleLong и LittleFloat.

Спрайты и ремап игрока

В загрузчике группы спрайтов интервалы читаются через LittleFloat, и если значение не положительно — Sys_Error. Обе версии загрузчика (в model.c и gl_model.c) делают это одинаково. Загрузчик модели спрайта читает длину луча через LittleFloat. Загрузчик кадра спрайта интервалы не обрабатывает: он читает ширину, высоту и начало координат через LittleLong.

Mod_FloodFillSkin заполняет фон, чтобы mipmapping не давало ореолов. Он берёт цвет заливки из первого пикселя скина, ищет непрозрачный чёрный в таблице палитры и использует его как цвет заполнения. Если цвет заливки совпадает с цветом заполнения или равен 255, функция возвращается без изменений. Иначе пиксели обходятся через FIFO: посещённые помечаются значением 255 и заменяются на цвет заполнения, который может обновиться из соседнего пикселя, не равного 255.

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

Что видит игрок в браузере

При загрузке страница показывает текст «fetching engine…», затем «loading…». Игроку предлагается кликнуть или нажать Enter для старта, затем любую клавишу для меню, и кликнуть для захвата мыши. Во время проигрывания демо любая клавиша открывает меню.

Захват мыши реализован через клик. Esc при захваченной мыши освобождает её и открывает меню. В полноэкранном режиме Chrome/Edge Esc просто переключает меню (удержание выходит из полноэкранного режима); в остальных случаях второе нажатие Esc выходит из полноэкранного режима — это правило браузера.

Консольные команды вызываются нажатием ~. Команда god даёт неуязвимость, noclip позволяет проходить сквозь стены, fly включает режим полёта, give a выдаёт полную броню — также h s n r c для здоровья и патронов или 1–8 для оружия.

Что из этого следует на практике

Кэш моделей ограничен жёстким пределом MAX_MOD_KNOWN: при его достижении движок переиспользует доступные модели, освобождая кэш alias-моделей, а при отсутствии таковых аварийно завершается. Поэтому число одновременно «живых» моделей — ресурс, который нужно расходовать осознанно.

Видимость — это битовая маска по листьям, сжатая RLE. Отсутствие vis-информации не отключает рендер, а делает все листья видимыми: движок корректно работает без предвычисленной видимости, но теряет отсечение.

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

Эпсилон 1/32 в трассировке сдвигает точку пересечения от плоскости, чтобы избежать ошибок плавающей точки. Это влияет на то, где именно фиксируется удар.

Area-дерево разбивает мир до глубины AREA_DEPTH по большей стороне, а bounding box движения расширяется на 1 по всем осям (или на 15 по горизонтали для предметов) — потому что движение клипается на эпсилон от края, и боксы, которые «почти касаются», всё равно должны проверяться.