Преобразуем карты DOOM в SVG для лазерной резки

Я много слышал о формате данных классического Doom, поэтому решил написать код на Rust для извлечения его карт и преобразования в векторную графику для лазерной резки.

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

Формат WAD DOOM

Данные DOOM спроектированы с целью удобства моддинга: вся игра состоит из исполняемого файла и блока данных .WAD. Shareware/демо-версия поставлялась с DOOM1.WAD, который по-прежнему свободно доступен.

Формат WAD Doom, проиллюстрированный при помощи MotionCanvas

Формат WAD хорошо задокументирован, см. неофициальную спецификацию DOOM или ZDoom wiki. Если вкратце:

• Файл WAD начинается с заголовка, за которым следуют сами данные, а завершается элементами папки, описывающими эти данные
• Заголовок содержит указатель на первый элемент папки и количество элементов
• Каждый элемент папки содержит указатель на данные и их размер

Я пропущу некоторые (потрясающие!) подробности, потому что все они рассмотрены в DOOM game engine black book чудесного Фабьена Санглара.

В терминологии Doom эти элементы данных называются «lump». Некоторые из них содержат геометрию карт, другие текстуры, звуки, текст… всё, что необходимо для игры.

Карта описывается несколькими lump.

• VERTEXES — это список позиций мира
• LINEDEFS описывает линии, соединяющие два отрезка и ссылающиеся на одну SIDEDEF для «стороны» линии
• SIDEDEFS — это «стены», текстуры для линии, принадлежащие SECTOR
• SECTORS — это многоугольники с высотой пола и потолка

Также данные карты содержат BSP-дерево, листья которого — подсекторы (секторы разделены так, чтобы быть выпуклыми многоугольниками); также там содержатся определения текстур, объединяющие несколько спрайтов, и многое другое.

Реализация

Я воспользовался nom — Rust-библиотекой комбинаторов парсеров, которая может парсить текст и двоичные форматы. Вот типичный пример использования: парсинг THINGS (предметов/бонусов) карты:

pub struct Thing {
    pub pos_x: i16,
    pub pos_y: i16,
    pub angle: i16,
    pub thing_type: u16,
    pub flags: ThingFlags,
}

impl Lump for Thing {
    // определяем, сколько предметов находится в lump
    const SIZE: usize = 10;
}

pub fn parse_thing(input: &[u8]) -> IResult<&[u8], Thing> {
    map(
        // парсим 5 беззнаковых short
        tuple((le_i16, le_i16, le_i16, le_u16, le_u16)),
        // сопоставляем их с полями структуры
        |(pos_x, pos_y, angle, thing_type, flags)| Thing {
            pos_x,
            pos_y,
            angle,
            thing_type,
            flags: ThingFlags::from_bits(flags).unwrap(),
        },
    )(input)
}

У меня есть удобная функция parse_lump в структуре WAD, получающая имя lump и функцию парсинга:

let things: Vec<Thing> = wad.parse_lump("THINGS", thing::parse_thing);

Геометрия

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

Распарсенные данные WAD — это неупорядоченный набор граней. Мы знаем, что грани точно не пересекаются. Слияние многоугольников — это простая операция объединения множеств, а удаление внутренних линий — это вопрос нахождения дублирующихся граней в многоугольнике.

Строго говоря, этого достаточно для создания SVG и дальнейшей лазерной резки.

Снижаем количество слоёв

Настало время разделить секторы на слои согласно их высоте полов. Это выполняется передачей высот и группировкой секторов по наименьшей верхней границе, например, для E1M1 я использовал [-70, -24, 0, 40].

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

Возможно, я изучу это позже; интуитивно мне кажется, что эта задача связана с задачей раскрашивания карты.

Записываем SVG

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

Для лазерной резки мне понадобятся:

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

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

Интерлюдия: последовательность Холтона

Я потратил много времени на генерацию SVG с разными цветами, чтобы проверить свою работу. Я снова воспользовался трюком для генерации полуслучайных цветов, которым горжусь: применением результатов последовательности Холтона в качестве hue HSL-цвета.

// base, f - это параметры
let mut halton = halton::Sequence::new(base);

for i in 0..sectors.len() {
    let color = colorsys::Hsl::from((
        // hue 0-360
        (h * 360.0 * f) % 360.0,
        // saturation 0-100
        80.0,
        // lightness 0-100
        50.0
    )).to_css_string();
}

Это схоже с использованием псевдослучайного генератора с постоянным seed, однако последовательность Холтона имеет более равномерное распределение. Вот результат для 100 значений с несколькими сочетаниями base/f:

Кроличья нора: 3D-рендеринг и триангуляция

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

Я накидал простое Bevy-приложение. Для рендеринга слоёв мне нужно было их триангулировать. Оказалось, существует крейт triangulate, но у него есть ограничения.

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

1. простой многоугольник, имеющий конкретное определение (см. Википедию):
   
   • В каждой вершине соединяются ровно две грани
   • Количество граней равно количеству вершин
   
   
   
   
2. Один многоугольник с отверстиями (называемый «слабо простым многоугольником», в простейшем случае схож с диском). Это значит, что сектор описывает несколько многоугольников, один из которых содержит остальные.
   
   
   
3. Несколько многоугольников, делящих одну вершину: если быть точным, несколько многоугольников, где каждая пара имеет не более одной смежной вершины, что делает это сложным многоугольником. То, что пересечения граней являются вершинами, означает, что многоугольник можно разделить на простые многоугольники.
   
   
   

Крейту triangulate (и, насколько я знаю, всем остальным реализациям) нужны реальные контуры — упорядоченный список вершин. Также он не поддерживает непростые многоугольники, что не позволяет использовать случай 3.

Чтобы воссоздать контур из неупорядоченного списка граней, я изначально выбирал грань и находил соединённую с ней грань. Это работает для случаев 1 и 2, но не для последнего, потому что у таких многоугольников в некоторых вершинах встречается более двух граней.

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

Если сектор Doom содержит несколько петель, то это значит, что он относится к случаю 2 или 3. Чтобы определиться с этим, можно положиться на эмпирические допущения:

• Случаи 2 и 3 взаимно друг друга исключают, то есть если вершина общая, она не должна быть отверстием. Только я не уверен, что это правда
• Это также значит, что если петля содержит другую, то это внешняя петля многоугольника с отверстиями

Я выбрал второй вариант и воспользовался крейтом geo, имеющим обширную поддержку операций с многоугольниками.

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

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

Попытка с подсекторами

Но постойте, в WAD ведь хранятся простые выпуклые многоугольники? Они получены в результате двоичного разбиения пространства. Так и есть, однако эти многоугольники иногда имеют неявные грани, определяемые линиями разделения. Я начал работать над этим, но затем понял, что слишком много приходится возиться с определением сторон. Однако это должно сработать. Возможно, займусь позже…

Возвращаемся назад

На этом этапе я сдался. Решение актуальной задачи получения превью оказалось проще: использовать TinkerCad для импорта слоёв в SVG, экструдировать их, наложить друг на друга и экспортировать в .glb, который можно отрендерить в Blender. Именно так я получил изображение из начала статьи. Стоит заметить, что импорт SVG в Tinkercad ожидает правильных контуров SVG без несоединённых линий; поэтому часть этой работы действительно послужила для получения красивого рендера.

Рендер E1M1 в Blender

Рендер E1M2 в Blender

Готовый результат

Теперь осталось только их склеить! Мне определённо нужно попробовать с прозрачным акрилом или с несколькими цветами.