Описание формата .MAP файла, алгоритмы и код (Часть 1)

[bionext]

Ниже я привожу первую часть перевода документа Stefan Hajnoczi (оригинал документа и исходные коды на GitHub). Как видно из названия темы, он описывает формат .map файлов и методы чтения и обработки информации полученной из них. Текст был переведён машинным переводом и в дальнейшем я придал ему более менее удобочитаемый вид, а так же исправил некоторые неточности и ошибки (но я не гарантирую, что их больше нет). На данный момент отредактировано половина перевода и в дальнейшем я планирую выложить переведённый и дополненный документ одним файлом. Я надеюсь кому-то эта информация будет полезной.

.MAP файлы
описание формата файла,
алгоритмы и код
Stefan Hajnoczi
[email protected]​

Содержание:
Часть 1
Отказ от ответственности
Вступление
.MAP файлы
Формат .MAP файлов
Дизайн парсера .MAP
Преобразуем браш в полигоны
Расчет координат текстуры
Часть 2
Сортировка вершин
Выполнение конструктивного объединения твердотельной геометрии на всех брашах(CSG)
Классификация полигона относительно плоскости
Разбиение полигона плоскостью
Исходный код
Специальная благодарность
Библиография / Ссылки

Отказ от ответственности
Хотя я (Stefan Hajnoczi) много поработал над этой статьей, я не могу гарантировать, что в ней нет ошибок. Я не несу ответственности за любой ущерб или проблемы, вызванные кодом, предоставленным в этой статье (как скомпилированным двоичным, так и исходным кодом).
Я никоим образом не являюсь сотрудником iD Software или Valve Software, и этот документ не является официальным руководством по WorldCraft (Hammer editor) или любому из описанных форматов файлов. По этой причине я не могу гарантировать точность предоставленной информации.
Чтобы понять эту статью, вы должны быть знакомы с WorldCraft 3.3, C ++, векторами и плоскостями. Наконец, я также хотел бы сказать, что много кода, имеющего дело с файлами .MAP и .WAD, можно найти в Half-Life SDK (

http://www.valvesoftware.com/hlsdk.htm

).

Вступление
После того, как вы создали карту в WorldCraft, выберите меню File|Export to .MAP, чтобы сохранить карту как файл .MAP. Сохраненный файл .MAP содержит все браши (brash – включают в себя геометрию всех полигонов на уровне, имена и ориентацию текстур) и объекты (entity – объект, сущность, подразделяются на brush-based, model-based и невидимые (логические) объекты) уровня. Поскольку вы создаете свой собственный движок, вам потребуется написать свои собственные инструменты для компиляции карты. Первым шагом к созданию пользовательских инструментов компиляции является анализ .MAP файла для получения списка всех объектов, свойств объектов и полигонов. К сожалению, разобрать .MAP файлы непросто. В этом документе представлен обзор того, как это сделать, а также описание каждого шага. Если вы загрузите этот документ, в него будет включен исходный код моего парсера .MAP файлов.
Как я всему этому научился? Я просто перерыл всю доступную информацию о WorldCraft. К сожалению, многое повторялось, в то время как немаловажные детали отсутствовали. Мне пришлось самому разбираться с форматом .MAP файла, потому что та немногая информация о нем в Интернете была устаревшей. Вот почему я составил этот документ. Я надеюсь, что этот документ предоставит исчерпывающую информацию о том, как модифицировать WorldCraft, чтобы использовать его с вашим собственным движком. Несколько человек помогли мне на этом пути, и я хотел бы поблагодарить этих людей в разделе особой благодарности.

Формат .MAP файлов
Я думаю, что лучший способ изучить формат .MAP файла это сразу перейти к простому примеру. Это пример .MAP файла, содержащего только поле:
{
"classname" "worldspawn"
"mapversion" "220"
"wad" "\games\half-life\cstrike\cstrike.wad;\games\half-life\valve\halflife.wad"
{
( 0 64 64 ) ( 64 64 64 ) ( 64 0 64 ) BCRATE02 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( 0 0 0 ) ( 64 0 0 ) ( 64 64 0 ) BCRATE02 [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( 0 64 64 ) ( 0 0 64 ) ( 0 0 0 ) BCRATE02 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 64 64 0 ) ( 64 0 0 ) ( 64 0 64 ) BCRATE02 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 64 64 64 ) ( 0 64 64 ) ( 0 64 0 ) BCRATE02 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 64 0 0 ) ( 0 0 0 ) ( 0 0 64 ) BCRATE02 [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
}
}
Фигурные скобки ('{' и '}') помещаются вокруг каждого объекта, отсюда и фигурная скобка в начале файла. Все в .MAP файле является частью объекта. Очевидными объектами являются двери, огни, старты игрока и т.д., поскольку они в WorldCraft называются объектами. Однако даже геометрия базового уровня, которая, казалось бы, не является частью объектов, на самом деле является таковой. Каждый объект может состоять из двух вещей: свойств и брашей. Свойства состоят из имени (выделено зеленым цветом), которое сообщает вам, какой это тип свойства и его значения (выделено розовым цветом). Свойства помогают хранить не геометрические данные об объекте. Они включают в себя такие пункты, как здоровье, для монстра, или имя файла звука, используемого при срабатывании чего-либо. Браши заключены в фигурные скобки ('{' и '}'). Браши представляют собой фактическую геометрию уровня. Они включают в себя стены, полы, столы и т. д. (все, что состоит из полигонов). Каждый браш состоит из четырех или более граней. Грань - это плоскость, название текстуры и информация о текстуре. Я расскажу о брашах более подробно позже.
У каждого объекта обязательно должно быть свойство: имя класса (classname). Имя класса указывает, какой тип объекта описывается. Например это может быть: "classname" "worldspawn", "classname" "light”, или "classname" "button”. Имя класса - это первое свойство любого объекта.
Worldspawn это объект, который должен присутствовать в каждом .MAP файле. Worldspawn - является первым объектом в любом .MAP файле. Он содержит все браши, которые не являются какими-либо специальными объектами. В типичном уровне Worldspawn содержит стены, полы, потолки и т.д. Независимо от того, насколько велик или мал уровень, он должен иметь один Worldspawn. Worldspawn содержит не только геометрию уровня, но также информацию о версии .MAP файла и имена используемых .WAD файлов. Версия .MAP файла указывается в свойстве mapversion. Здесь мы рассматриваем 220 версию .MAP файлов используемых в WorldCraft 3.3. Используемые .WAD файлы перечислены в свойстве wad, они разделяются точкой с запятой (';').
Браши состоят из четырех или более граней. Нет ограничений на количество брашей, которые могут быть в объекте. Браши всегда выпуклые, что является очень полезным свойством (в будущем мы в этом убедимся). Вместо того, чтобы описываться как набор полигонов, браши описываются как набор граней.
Давайте рассмотрим, как именно определяются браши. (Говоря о «линии», я буду иметь в виду строки текста в определении браша.) Каждая линия определяет одну плоскость (плоскость - это бесконечно тонкий, бесконечно большой «лист» в трехмерном пространстве), который, по сути, определяет одну плоскость грани. Грань браша это область на плоскости грани ограниченная вместе взятыми плоскостями граней браша. Пример описания структуры грани:

( x1 y1 z1 ) ( x2 y2 z2 ) ( x3 y3 z3 ) TEXTURE_NAME [ tx1 ty1 tz1 toffs1 ] [ tx2 ty2 tz2 toffs2 ] rotation scaleX scaleY

Чтобы определить одну фактическую плоскость, необходимо задать три точки (обозначенные как x1, y1, z1, x2, y2, z2 и x3, y3, z3). Они должны располагаться по часовой стрелке, если смотреть на внешнюю сторону плоскости, то есть на сторону, которая направлена наружу от браша, и эти точки должны лежать на поверхности плоскости. Они также должны отличаться друг от друга и не лежать на одной линии - при соединении они должны образовывать три угла треугольника. (Часто бывает достаточно трех вершин грани, представленных этой плоскостью.)
После этих трех точек идет определение, как будет текстурирована грань, находящаяся на этой плоскости. Первая часть говорит сама за себя - TEXTURE_NAME название текстуры - но следующую часть довольно сложно как объяснить, так и понять. Для определения ориентации текстур используется пара осей. Они задают плоскость пространства текстуры грани. Представьте себе плоскую поверхность, покрытую текстурой, с двумя осями, лежащими на этой поверхности, это и есть плоскость текстуры. Затем она проецируется на плоскость грани. Это означает, что если вы хотите, чтобы текстура имела идеальный масштаб на грани, оси должны образовывать плоскость, параллельную плоскости грани, иначе вы получите растяжение текстуры.


Эти оси определены координатами tx1 / y1 / z1 и tx2 / y2 / z2, что дают два вектора, которые определяют направление «вправо» и «вверх» относительно текстуры - так что, если вы хотите переместиться «вправо» на 1 единицу, вам нужно сместиться по направлению первой оси на 1 единицу. Смещение «вниз» на 2 единицы перемещение в обратном направлении вдоль второй оси на 2 единицы. Насколько текстура смещена по этим осям, определяется параметрами toffs1 и toffs2, измеряемыми в условных единицах WorldCraft.
Последние три параметра довольно просты, но вот rotation - странный. Вопреки тому, что вы думаете, он не определяет, на сколько нужно повернуть текстуру; он определяет, на сколько она УЖЕ была повернута. Это сделано для того, чтобы Worldcraft мог соответствующим образом вращать оси текстуры, а это означает, что если вы хотите написать программу для поворота текстуры на 45 градусов, вам нужно будет добавить 45 к rotation (чтобы показать WorldCraft, что она повернута на 45 градусов) и повернуть обе оси текстуры на 45 градусов.
К счастью, параметры scaleX и scaleY очень просты. Они определяют, насколько текстура растянута по осям UV. Значение больше 1 растягивает, меньше 1 сжимает, отрицательное значение то же самое в зеркальном отображении.
Типичный .MAP файл состоит из одного большого мира и множества (200+) объектов, являющимися огнями, дверьми, переключателями, триггерами и т.д. Следующий пример .MAP файла описывает несколько объектов и брашей. Это простенький уровень Counter-Strike, который я сделал на скорую руку. В нем есть одна комната, свет, цель и место спавна игрока. Не сосредотачивайтесь на том, что каждый объект делает или означает, лучше сосредоточьтесь на синтаксисе .MAP файла.

Спойлер: Пример карты

{
"classname" "worldspawn"
"MaxRange" "4096"
"mapversion" "220"
"wad" "\games\half-life\cstrike\cstrike.wad;\games\half-life\valve\halflife.wad"
{
( 0 0 256 ) ( 0 256 256 ) ( 256 256 256 ) AAATRIGGER [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( 0 256 224 ) ( 0 256 256 ) ( 0 0 256 ) AAATRIGGER [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 256 0 224 ) ( 256 0 256 ) ( 256 256 256 ) AAATRIGGER [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 256 256 224 ) ( 256 256 256 ) ( 0 256 256 ) AAATRIGGER [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 0 0 224 ) ( 0 0 256 ) ( 256 0 256 ) AAATRIGGER [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 0 256 224 ) ( 0 0 224 ) ( 256 0 224 ) C1A0_W2 [ 1 0 0 0 ] [ 0 -1 0 160 ] 0 2 1.6
}
{
( 0 256 0 ) ( 0 0 0 ) ( 256 0 0 ) AAATRIGGER [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( 0 0 32 ) ( 0 0 0 ) ( 0 256 0 ) AAATRIGGER [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 256 256 32 ) ( 256 256 0 ) ( 256 0 0 ) AAATRIGGER [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 0 256 32 ) ( 0 256 0 ) ( 256 256 0 ) AAATRIGGER [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 256 0 32 ) ( 256 0 0 ) ( 0 0 0 ) AAATRIGGER [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 0 0 32 ) ( 0 256 32 ) ( 256 256 32 ) C1A0_LABFLRB [ 1 0 0 0 ] [ 0 -1 0 128 ] 0 2 2
}
{
( 0 0 224 ) ( 0 0 32 ) ( 0 256 32 ) AAATRIGGER [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 0 256 224 ) ( 0 256 32 ) ( 32 256 32 ) AAATRIGGER [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 32 0 32 ) ( 0 0 32 ) ( 0 0 224 ) AAATRIGGER [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 0 0 224 ) ( 0 256 224 ) ( 32 256 224 ) AAATRIGGER [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( 0 256 32 ) ( 0 0 32 ) ( 32 0 32 ) AAATRIGGER [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( 32 256 224 ) ( 32 256 32 ) ( 32 0 32 ) C1A0_W1D5 [ 0 1 0 0 ] [ 0 0 -1 26.6667 ] 0 2 1.2
}
{
( 256 256 224 ) ( 256 256 32 ) ( 256 0 32 ) AAATRIGGER [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 224 256 32 ) ( 256 256 32 ) ( 256 256 224 ) AAATRIGGER [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 256 0 224 ) ( 256 0 32 ) ( 224 0 32 ) AAATRIGGER [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 224 256 224 ) ( 256 256 224 ) ( 256 0 224 ) AAATRIGGER [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( 224 0 32 ) ( 256 0 32 ) ( 256 256 32 ) AAATRIGGER [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( 224 0 224 ) ( 224 0 32 ) ( 224 256 32 ) C1A0_W1D5 [ 0 1 0 0 ] [ 0 0 -1 26.6667 ] 0 2 1.2
}
{
( 32 256 32 ) ( 224 256 32 ) ( 224 256 224 ) AAATRIGGER [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 32 224 224 ) ( 32 256 224 ) ( 224 256 224 ) AAATRIGGER [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( 224 256 32 ) ( 32 256 32 ) ( 32 224 32 ) AAATRIGGER [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( 32 224 32 ) ( 32 256 32 ) ( 32 256 224 ) BCRATE02 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 224 256 224 ) ( 224 256 32 ) ( 224 224 32 ) BCRATE02 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 224 224 32 ) ( 32 224 32 ) ( 32 224 224 ) C1A0_W1D5 [ 1 0 0 -21.3333 ] [ 0 0 -1 26.6667 ] 0 1.5 1.2
}
{
( 224 0 32 ) ( 32 0 32 ) ( 32 0 224 ) AAATRIGGER [ 1 0 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 224 0 224 ) ( 32 0 224 ) ( 32 32 224 ) AAATRIGGER [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( 32 32 32 ) ( 32 0 32 ) ( 224 0 32 ) AAATRIGGER [ 1 0 0 0 ] [ 0 -1 0 0 ] 0 1 1
( 32 0 224 ) ( 32 0 32 ) ( 32 32 32 ) BCRATE02 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 224 32 32 ) ( 224 0 32 ) ( 224 0 224 ) BCRATE02 [ 0 1 0 0 ] [ 0 0 -1 0 ] 0 1 1
( 32 32 32 ) ( 224 32 32 ) ( 224 32 224 ) C1A0_W1D5 [ 1 0 0 -21.3333 ] [ 0 0 -1 26.6667 ] 0 1.5 1.2
}
}
{
"classname" "info_player_start" "angles" "0 0 0"
"origin" "64 64 80"
}
{
"classname" "light" "_light" "255 255 128 200"
"target" "Light01.Target" "targetname" "Light01" "origin" "128 128 208"
}
{
"classname" "info_target" "targetname" "Light01.Target" "origin" "128 128 32"
}

Дизайн парсера .MAP файлов
Теперь, когда вы знакомы с форматом .MAP файлов, мы можем начать размышлять о том, как мы собираемся писать синтаксический анализатор .MAP файла. Результатом синтаксического анализа .MAP файла должен быть список объектов. У каждого объекта должен быть набор свойств и полигонов. Обратите внимание, что это не сильно отличается от .MAP файлов. Проблема в том, что вместо хранения геометрии в виде списка полигонов, .MAP файлы состоят из брашей, которые являются выпуклыми многогранниками, определяемые плоскостями. Таким образом, задача парсера .MAP файлов - загрузить .MAP файл в память, преобразовать браши в набор полигонов и в уточненный список объектов.
Система координат, которую использует WorldCraft, выглядит так:

Чтобы преобразовать координаты WorldCraft в левостороннюю систему координат, вам необходимо: поменять местами у и z компоненты каждой координаты.
Вы спросите, как можно создать сложные здания и объекты, если браши являются выпуклыми полигонами. Во-первых, как вы уже знаете, каждый объект может содержать более одного браша. Если поставить рядом два выпуклых многогранника, можно образовать более сложный вогнутый многогранник. Однако внутри самого объекта образуются скрытые полигоны.
Чтобы помочь вам понять, о чём идёт речь, представьте, что два кубика поставлены рядом друг с другом, так что они соприкасаются. Они образуют прямоугольный многогранник, который на одной из осей длиннее, чем на других, однако две соприкасающиеся стороны окажутся внутри нового объекта. Во-первых, хранить эти полигони - пустая трата памяти, потому что их невозможно увидеть. Во-вторых, такая геометрия может быть недопустимой для компиляции BSP. Вот картина ситуации, которую я описываю:

Эта проблема может быть решена с помощью операции объединения Constructive Solid Geometry (CSG). CSG операция удалит любые полигони внутри объекта и позволит вам соединить два многогранника, удалив при этом любую ненужную геометрию.
Еще одна проблема, с которой мы сталкиваемся при написании парсера .MAP файлов, - это точность. С самого начала я решил использовать тип данных double вместо float. Это позволяет повысить точность. Тем не менее, появляются неточности округления, и в конечном итоге при сравнении координат могут возникнуть ошибки. Для борьбы с этой проблемой вводится epsilon. Вместо проверки точных значений, таких как ноль, вы проверяете, что значение находится в определенном диапазоне от нуля. Это необходимо, нравится вам это или нет. В этой статье я не использовал epsilon в псевдокоде, потому что он зависит от вашего типа данных, а также от масштаба и размеров вашего уровня. Чтобы понять, как и когда они используются, просмотрите исходный код, особенно математические процедуры и процедуры классификации. «Нечеткие» сравнения могут использоваться не только при сравнении двух чисел, но и при сравнении двух векторов. Например, чтобы проверить, равны ли два нормализованных вектора, a ∙ b≈1. Пример реализации этого в псевдокоде:

double    Angle = a.Dot ( b ) - 1;

if ( ( Angle > -epsilon ) && ( Angle < epsilon ) )
{
    …they are equal…
}

Ниже перечислены основные шаги в синтаксическом анализе .MAP файла, для того, чтобы убедиться, что вы все поняли.
Загрузить .MAP файл в память
Создать полигоны из брашей
Выполнить объединение CSG для каждой браша в объекте
Сохранить список объектов в любом формате, который вам нравится

Превращаем браш в набор полигонов
Когда список объектов находится в памяти, первая задача - преобразовать браш в полигоны. Это можно сделать двумя способами. Первый метод пересечение 3-х плоскостей. Этот метод быстрый и требует относительно небольшой код. Второй метод - создать огромные потенциальные полигони вдоль плоскости каждой грани, а затем соединить их друг с другом. Мне лично этот метод не нравится, поэтому я решил использовать первый.
Псевдокод для превращения браша в массив полигонов:

For i = 0 to NumberOfFaces – 1
{
    For j = 0 to NumberOfFaces – 1
    {
        For k = 0 to NumberOfFaces – 1
        {
            if ( i != j != k )
            {
                Polys[ i ].AddVertex ( GetIntersection ( i,  j, k ) );
            }
        }
    }
}

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

Каждая плоскость состоит из нормали n и расстояния от плоскости до начала координат d. Это логично, поскольку все эти переменные происходят из уравнения плоскости ax + by + cz + d = 0 (или, более компактно n ∙ x + d=0). Обратите внимание: если знаменатель равен 0, пересечения нет (плоскости параллельны). Псевдокод для поиска пересечения трех плоскостей:

bool GetIntersection ( n1, n2, n3, d1, d2, d3, &p  )
{
    double denom = n1.Dot ( n2.Cross ( n3 ) );

    if ( denom == 0 )
    {
        return false;
    }

    p = -d1 * ( n2.Cross ( n3 ) ) – d2 * ( n3.Cross ( n1 ) ) – d3 * ( n1.Cross ( n2 ) ) / denom;

    return true;
}

Функция возвращает true и устанавливает p, если было пересечение. В противном случае возвращается false.

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

Здесь видно, что будет создана дополнительная точка в месте пересечения трёх плоскостей. К сожалению, эта точка не является частью объекта. Первая пересекаемая плоскость - это горизонтальная линия. Вторая плоскость - это диагональная линия. Третья плоскость - это еще одна плоскость, которую нельзя увидеть в двухмерном представлении. Хотя есть пересечение, точка лежит за пределами объекта. Причина этой ошибки в том, что вертикальная плоскость справа не используется в тесте на пересечение. Вот еще один вид того же объекта (на этот раз в 3D):

Синими линиями обозначена модель, которая нам требуется. Красными обозначено место, где образуется недопустимая точка пересечения. Теперь, когда вы, надеюсь, разобрались в проблеме, я покажу вам её решение.
Перед добавлением точки к полигону необходимо убедиться, что точка не находится за пределами объекта. Это можно легко проверить, так как все браши выпуклые, а это значит, что если какая-либо точка находится перед любой из плоскостей браша, она находится за пределами модели. Подумайте, насколько это актуально для любого выпуклого браша. Усовершенствованный псевдокод:

Faces – массив всех граней браша
Создаём массив полигонов Polys содержащий количество элементов равное количеству граней

for i = 0 to NumberOfFaces – 1
{
    for j = 0 to NumberOfFaces – 1
    {
        for k = 0 to NumberOfFaces – 1
        {
            if ( i != j != k )
            {
                illegal = false;
                newVertex = GetIntersection ( i, j , k );

                for m = 0 to NumberOfFaces – 1
                {
             
                    if ( DotProduct ( Faces[ m ].normal, newVertex ) + Faces[ m ].d > 0 )
                    {
                        illegal = true;
                    }
                }

                if ( illegal == false )
                {
                    Polys[ i ].AddVertex ( newVertex );
                }
            }
        }
    }
}

Можно ещё оптимизировать код, но это может зависеть от структуры данных. Во-первых, вместо того, чтобы сравнивать каждый элемент со всеми другими элементами массива Faces во всех возможных комбинациях, нужно в первом цикле перебирать элементы от 0 до NumberOfFaces - 3, в двух других циклах перебирать элементы от i до NumberOfFaces - 2 и от j до NumberOfFaces - 1 соответственно. Во-вторых, не добавлять новую вершину только к одному полигону за раз, ее можно добавлять ко всем трем полигонам сразу. Оптимизированный псевдокод выглядит так:

Faces – массив всех граней браша
Создаём массив полигонов Polys содержащий количество элементов равное количеству граней

For i = 0 to NumberOfFaces – 3
{
    For j = i to NumberOfFaces – 2
    {
        For k = j to NumberOfFaces – 1
        {
            if ( i != j != k )
            {
                legal = true;
                newVertex = GetIntersection ( i, j , k );

                for m = 0 to NumberOfFaces – 1
                {
                    // Проверяем находится ли точка за пределами браша
                    if ( DotProduct ( Faces[ m ].normal, newVertex ) + Faces[ m ].d > 0 )
                    {
                        legal = false;
                    }
                }
            
                if ( legal )
                {
                    Polys[ i ].AddVertex ( newVertex ); // Добавляем точку
                    Polys[ j ].AddVertex ( newVertex ); // к 3 полигонам
                    Polys[ k ].AddVertex ( newVertex ); // за раз
                }
            }
        }
    }
}

На этом заканчивается превращение браша в набор полигонов. Следующим шагом будет вычисление координат текстуры для каждой вершины.

Расчет координат текстуры
Вычислить координаты текстуры для любого полигона совсем несложно. Я просто предоставлю формулы:

t_u и t_v - две координаты текстуры. v ⃑ - вершина, для которой вычисляется координата текстуры. n_u и n_v - нормали осей текстуры. w и h - ширина и высота текстуры соответственно. S_u и S_v - масштаб текстуры. O_u и O_v - смещение или сдвиг текстуры. Чтобы определить размеры используемой текстуры, вам нужно будет найти текстуру в одном из .WAD файлов, используемых уровнем. Посмотреть, как реализовать это в коде можно в моей статье о .WAD файлах.
Проблема с координатами текстур в том, что они не нормализованы. Под нормализацией я подразумеваю значение координат как можно более близкое к 0. Некоторые видеокарты могут не справляться с очень большими координатами текстуры. Если вы посмотрите на координаты текстуры, сгенерированные с использованием этой формулы, вы увидите, что они верны (если у вас включен перенос текстуры), но их нужно поместить в диапазон от –1 до +1.
Способ сделать это - найти координату, наиболее близкую к 0. U и V нормализуются отдельно. Однако если координата находится в диапазоне от –1 до +1, то эти координаты уже нормализованы. Нормализация выполняется на уровне полигона. Принцип заключается в том, чтобы найти координату текстуры, ближайшую к 0 (но не в диапазоне от –1 до +1), а затем вычесть ее округленное ближайшее к 0 значение из всех текстурных координат полигона текущей оси. Эту операцию необходимо проделать как с осью U, так и с осью V. Реальный код C ++ вы можете просмотреть в моих исходниках (https://github.com/stefanha/map-files).
Псевдокод нормализации:

float Nearest_u = poly.verts[ 0 ].u;
float Nearest_v = poly.verts[ 0 ].v;
bool NeedNormalise_u = true;
bool NeedNormalise_v = true;

for i = 0 to NumberOfVertices - 1
{
    if ( NeedNormalise_u )
    {
        if ( poly.verts[ i ].u > 1 )
        {
            if ( poly.verts[ i ].u < Nearest_u)
            {
                Nearest_u = poly.verts[ i ].u;
            }
        }
        else if ( poly.verts[ i ].u < -1 )
        {
            if ( poly.verts[ i ].u > Nearest_u)
            {
                Nearest_u = poly.verts[ i ].u;
            }
        }
        else
        {
            Nearest_u = 0;
            NeedNormalize_u = false; // координаты уже нормализованны
        }
    }

    if ( NeedNormalise_v )
    {
        if ( poly.verts[ i ].v > 1 )
        {
            if ( poly.verts[ i ].v < Nearest_v)
            {
                Nearest_v = poly.verts[ i ].v;
            }
        }
        else if ( poly.verts[ i ].v < -1 )
        {
            if ( poly.verts[ i ].v > Nearest_v)
            {
                Nearest_v = poly.verts[ i ].v;
            }
        
        }
        else
        {
            Nearest_v = 0;
            NeedNormalize_v = false; // координаты уже нормализованны
        }
    }
}

if ( NeedNormalize_u )
{
    if ( Nearest_u > 0 )
    {
        Nearest_u = floor ( Nearest_u ); // Округляем до ближайшего меньшего числа
    }
    else
    {
        Nearest_u = ceil ( Nearest_u ); // Округляем до ближайшего большего числа
    }
}

if ( NeedNormalize_v )
{
    if ( Nearest_v > 0 )
    {
        Nearest_v = floor ( Nearest_v ); // Округляем до ближайшего меньшего числа
    }
    else
    {
        Nearest_v = ceil ( Nearest_v ); // Округляем до ближайшего большего числа
    }
}

for i = 0 to NumberOfVertices - 1
{
    poly.verts[ i ].u = poly.verts[ i ].u – Nearest_u;
    poly.verts[ i ].v = poly.verts[ i ].v – Nearest_v;
}

 

[karaulov]

А я раньше, очень очень давно писал генератор карт https://gamebanana.com/tools/5717 лабиринтов, с предметами, освещением и разрушаемыми стенами, сам разбирался как работает этот формат .map )


Хотел недавно генератор карт из готовых "комнат" сделать , но не знаю как перемещать по X/Y и вращать карту что бы соединить входы, допустим какой-то стандарт переходов сделать. А иначе придется делать очень много одинаковых комнат (

 

[bionext]

karaulov, Матрица преобразований.

 

[Neshropl]

Спасибо за перевод. Никогда бы сам даже подобного не нашёл документа. Полезно. ^^

 

[SergeyShorokhov]

Благодарю за перевод великолепной статьи! Полезный материал.

Исправьте пожалуйста пару ошибок
(в бедующем мы в этом убедимся)

13 Сен 2021

Представите себе плоскую поверхность

13 Сен 2021

то же самое в зеркальном отображение.

13 Сен 2021

хранить эти полигони

 

[hajimura]

Наконец-то что-то годное к прочтению. Спасибо

 

[bionext]

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