Привет!

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

Основы

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

Чтобы в консоли можно было придать RGB цвет символу, я использовал следующую библиотеку

Положение точки на экране

(*) В этой статье понятия пикселя и консольного символа у меня равноценны.

Пусть S - точка в пространстве. Положение точки S на экране определяется в зависимости от горизонтального и вертикального углов(1.1*) между вектором направления камеры и вектором, выпущенным из камеры в точку S. Смысл здесь в том, что мы определяем, на сколько нужно повернуть вектор направления камеры, чтобы получить точку S. Соответственно горизонтальный угол будет показывать, на сколько нам нужно отступить от центра экрана по горизонтали чтобы получить координату X нашей точки на экране, а вертикальный угол будет показывать на сколько нам нужно отступить от центра экрана по вертикали, чтобы получить координату Y нашей точки на экране.

(*) Стоит также заметить, что у нас 1 градус равен одному пикселю на экране. То есть, если например горизонтальный угол будет равен 5, а вертикальный 10 градусам, то нужно будет отступить от центра экрана по горизонтали на 5 пикселей, а по вертикали на 10 пикселей.

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

1) Отступ по горизонтали:

Пусть V1 - вектор направления камеры, а V2, V3, V4 - остальные координатные оси горизонтальной плоскости камеры. Пусть также угол между векторами V1 и V2 = 90° и угол между векторами V1 и V4 также равен 90°. Вектор V2 находится левее вектора V4 (относительно вектора V1).

Проецируем нашу точку на горизонтальную плоскость камеры и определяем, в какой из четвертей координатной системы этой плоскости она находится (Нам нужны только две четверти, так как угол обзора игрока не будет превышать 180°). Соответственно, если точка находится в левой четверти (относительно вектора направления камеры), то мы должны прибавить величину горизонтального угла к координате X центра экрана. Иначе (правая четверть), мы должны будем отнять горизонтальный угол от координаты X центра экрана.

2) Отступ по вертикали:

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

Теперь мы получили положение точки на экране!

(1.1*) Горизонтальный угол в данном случае - это угол между вектором направления камеры и вектором, выпущенным из камеры в проекцию точки S на горизонтальную плоскость камеры(1.2*). Вертикальный угол определяется аналогичным образом, только проекцией точки S на вертикальную плоскость камеры.

(1.2*) Чтобы получить горизонтальную плоскость камеры, нужно повернуть вектор направления камеры на произвольное кол-во градусов используя обычную формулу поворота вокруг оси Z, но при этом разделить координату z полученного вектора после поворота на cos(a) (так как при a = 0° -> cos(a) = 1, а при a = 180° -> cos(a) = 1). Таким образом горизонтальную плоскость камеры будут составлять вектор направления камеры и полученный после поворота вектор. Вертикальную плоскость получить еще проще, используя векторное произведение векторов горизонтальной плоскости. Аналогично вертикальную плоскость камеры составляют вектор направления камеры и вектор, полученный после векторного произведения векторов горизонтальной плоскости.

Точка пересечения луча и параллелепипеда

Пусть sc - конечная точка бросания луча (в зависимости от дальности прорисовки); cam - координаты камеры в пространстве; a - точка, содержащая начальные данные о диапазоне параллелепипеда в пространстве (x1, y1, z1); b - точка, содержащая конечные данные о диапазоне параллелепипеда в пространстве (x2, y2, z2).

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

Смысл этой системы в том, что мы пускаем единичный вектор N того же направления, что и вектор (sc - cam), и ищем такие числа t, что при домножении на него вектора N мы получим точку из множества точек (sc - cam), лежащую в диапазоне нужного параллелепипеда.

Результатом решения данной системы будут числа t = r1 и t = r2, где минимальное из этих чисел при подстановке в систему будет ближайшей точкой пересечения луча и параллелепипеда, а максимальное - дальней (относительно камеры).

Поворот параллелепипеда

Будем рассматривать поворот параллелепипеда только вокруг оси Z, так как поворот вокруг других осей будет аналогичным.

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

Сначала мы определяем в каком именно из четырех многоугольников находится точка (S1, S2, S3, S4). Если луч из камеры пересекает "реальную" (повернутую) сторону параллелепипеда вне нового диапазона, то эту точку пересечения луча и параллелепипеда можно не учитывать. Иначе, мы отодвигаем данную точку по направлению нашего луча до тех пор, пока она не окажется в параллелепипеде.

Точка пересечения луча и треугольника в пространстве

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

Кубическая интерполяция

Кубическая интерполяция - способ получения кубической параболы, проходящей через две заданные точки (в нашем случае через некоторую точку на прямой x = 0 и точку на прямой x = 1).

Смысл куб. интерполяции заключается в том, чтобы плавно перевести точку из состояния y1 в состояние y2, с постепенным уменьшением скорости данной точки начиная с середины.

Кубическая интерполяция будет использоваться в дальнейшем.

Наложение текстуры на параллелепипед

Сначала нужно определить, на какой именно из сторон параллелепипеда лежит наша точка (это можно сделать через уравнение плоскости: просто подставляя координаты нашей точки в уравнения плоскостей сторон параллелепипеда, и нахождения значения самого близкого к нулю). Затем нужно выбрать "точку отсчета" из вершин на этой стороне, и перевести нашу точку в 2D систему координат данной плоскости:

sc - точка, лежащая на некоторой стороне параллелепипеда в пространстве; centre - точка отсчета стороны параллелепипеда; newSC - получившаяся точка после перевода sc в 2D систему координат этой плоскости.

Итого:

Далее мы должны будем координаты X и Y точки newSC домножить на следующие отношения: Wk / Ws и Hk / Hs, где Wk, Hk - длина и высота стороны параллелепипеда, а Ws, Hs - длина и высота картинки (в пикселях).

Мы домножаем newSC на Wk / Ws и Hk / Hs для того, чтобы самый отдаленный край нашей стороны соответствовал самому отдаленному краю картинки, т. е.

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

(*) Чтобы увеличить кол-во картинок на стороне по горизонтали в K раз, нужно итоговую точку (на текстуре) по координате X домножить на K: newSC.x * (Wk / Ws) * K. А затем взять остаток от деления на Wk: (newSC.x * (Wk / Ws) * K) % Wk. (По вертикали все происходит аналогичным образом)

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

Наложение текстуры на круг

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

Пусть вектора UP, RIGHT и N являются осями локальной системы координат круга, где центром этой системы является координата центра круга, а N - нормаль к плоскости этого круга. Пусть также centre - точка отсчета.

Где rad - радиус круга.

Остальные пункты аналогичны.

Наложение текстуры на модель

Чтобы решить задачу с наложением текстуры на модель, нам нужно решить задачу с наложением текстуры на треугольник.

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

У нас имеется наш треугольник и треугольник на текстуре (скорее всего они совпадают по форме). Сначала нам, как и в параллелепипеде, нужно перевести наш треугольник в систему координат текстуры (будем переводить так же как и в параллелепипеде, но за центр системы координат текстуры будем брать одну из вершин треугольника (если мы импортируем модель из блендера в obj формате, то за центр всегда будем брать первую вершину треугольника, так как в obj при наложении текстуры на треугольник вершины модельного треугольника и текстурного в основном соответствуют друг другу по порядку)). Итого мы перевели координаты нашего треугольника в координаты текстуры (зеленым цветом обозначен модельный треугольник, а красным - текстурный):

Далее переносим текстурный треугольник в начало координат (чтобы одна из его вершин имела координаты {0;0}). И затем мы должны поровнять наш треугольник с текстурным:

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

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

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

Пусть S1, S2, S3 - вершины модельного треугольника. SO1, SO2, SO3 - вершины текстурного треугольника соответственно. Далее нам нужно преобразовать вершины нашего треугольника так, чтобы max(SO.y) - min(SO.y) = max(S.y) - min(S.y). То есть нам нужно домножить стороны нашего треугольника на некоторый множитель K:

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

(*) Иногда так же бывают случаи, когда наш треугольник после масштабирования нужно переместить по оси Y так, чтобы min(S.y) = min(SO.y) и max(S.y) = max(SO.y).

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

Пусть Q - некоторая точка модельного треугольника, которая получилась после всех приведенных выше преобразований. Проведем через эту точку прямую, параллельную прямой y = 0 и найдем точки пересечения этой прямой со сторонами треугольников. Пусть P1 - наименьшая точка пересечения (по X) нашей прямой с текстурным треугольником, а P2 - наименьшая точка пересечения (по X) нашей прямой с модельным треугольником. Тогда Wk - длина прямой QP1, а Ws - длина прямой QP2.

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

Где p - единичный вектор, выпущенный из точки P1; a - длина прямой QP2.

Далее просто к полученной точке I прибавляем изначальные координаты точки SO1 (которую мы изначально вычитали, чтобы перенести текстурный треугольник в центр системы координат).

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

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

Увелечение/уменьшение модели

Чтобы увеличить модель в 2 раза (к примеру), нужно все вершины полигонов отдалить от центра модели в 2 раза.

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

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

Пункты редактора карт

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

Ареа порталы

Ареа портал - это по сути своей обычный параллелепипед, только он проводит некоторые манипуляции с лучами, выпущенными из камеры и попавшими в этот ареа портал. Суть ареа порталов заключается в том, чтобы при попадании в них луча уменьшить длину этого луча соответственно. Их полезно вставлять в различные стены, так как благодаря этому рендер не будет тратить ресурсов на проверку попадания луча в объекты за стеной.

Реализация прозрачности текстур

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

(*) Некоторые части на текстуре могут быть не прозрачными (как например надпись Area Portal на текстуре ареа портала). Тогда наша точка на экране окрасится в цвет этой непрозрачной части прозрачной текстуры.

Делегаты

Делегаты - это по сути реализация паттерна Observer. Сам по себе делегат представляет собой хранилище, которое хранит указатели на методы и их аргументы, и в нужный момент может разом вызвать все эти функции.

Хитрость в реализации делегатов заключается в том, что все классы этих методов наследуются от одного общего класса. Благодаря этому мы можем с помощью reinterpret_cast прочитать указатель на метод наследника базового класса как указатель на метод базового класса, и из-за этого мы можем хранить все указатели на методы в одном векторе.

Делегаты в основном используются вместе с триггерами.

Реализация класса Delegate:

#define DECLARE_DELEGATE(DelegateName, ...)\
	using DelegateName = Delegate<__VA_ARGS__>

template <typename... Args>
class Delegate
{
private:
	std::vector<AActor*> Observers;
	std::vector<void(AActor::*)(Args...)> ObserversFunctions;
	std::vector<std::tuple<Args...>> ObserversFunctionsArgs;

	static void RunObsFuncWithArgs(AActor* Observer, void(AActor::* Func)(Args...), Args... args);

public:
	void Broadcast();

	template <typename Type>
	void AddUObject(AActor* Observer, void(Type::* Func)(Args...), Args... args);
};

template <typename... Args>
void Delegate<Args...>::RunObsFuncWithArgs(AActor* Observer, void(AActor::* Func)(Args...), Args... args)
{
	(Observer->*Func)(args...);
}

template <typename... Args>
void Delegate<Args...>::Broadcast()
{
	for (size_t i = 0; i < Observers.size(); ++i)
	{
		if constexpr (sizeof...(Args) == 0)
			(Observers[i]->*ObserversFunctions[i])();
		else
		{
			std::tuple<AActor*, void(AActor::*)(Args...)> ObsAndObsFuncs(Observers[i], ObserversFunctions[i]);

			std::apply(Delegate::RunObsFuncWithArgs, std::tuple_cat(ObsAndObsFuncs, ObserversFunctionsArgs[i]));
		}
	}
}

template <typename... Args>
template <typename Type>
void Delegate<Args...>::AddUObject(AActor* Observer, void(Type::* Func)(Args...), Args... args)
{
	Observers.push_back(Observer);
	ObserversFunctions.push_back(reinterpret_cast<void(AActor::*)(Args...)>(Func));

	if constexpr (sizeof...(Args) != 0)
		ObserversFunctionsArgs.push_back(std::tuple<Args...>(args...));
}

Реализация триггеров

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

В итоговой игре мы под каждый триггер создаем свой объект, в котором создаются делегаты под каждый тип соединения. При загрузке карты во время чтения объектов, связанных с триггерами, в эти делегаты записывается информация о функциях (в зависимости от читаемого в данный момент объекта), а сам объект триггера проверяет на вхождение в него игрока (или какого-либо другого объекта в зависимости от того за кем следит триггер), и при вхождении вызывает методы Broadcast у всех доступных делегатов.

Реализация env_shake (землетрясение)

Объект env_shake имеет смысл использовать только вместе с триггерами.

Реализация: Рисуем окружность в 2D плоскости произвольного радиуса (от величины этого радиуса зависит сила тряски камеры) с центром в точке { 0;0 }. Затем на этой окружности выбираем случайную точку. Получив координаты этой точки в 2D системе, мы должны перевести эти координаты в 3D систему.

Итоговая точка в 3D системе вычисляется следующим образом:

Пусть S - случайная точка в 2D на окружности; UP - вектор направления камеры N, повернутый вверх на 90°; LEFT - вектор, полученный путем векторного произведения векторов UP и N. Тогда,

Где cam - координаты камеры; I - итоговая точка.

(*) Для коллизии и рендеринга используются две разные точки (камеры)

Реализация 3D скайбокса

3D скайбокс - это некий малый участок карты, на котором существует своя камера (sky camera). Благодаря этому участку создается иллюзия большой карты.

Реализация: Мы пускаем луч из нашей камеры, и если этот луч попадает в skybox текстуру, то я пускаю этот же луч но уже из другой камеры (чтобы пиксель луча, который попал в skybox текстуру закрасился в соответствующий цвет с другой камеры (sky camera)).

Из-за того что sky camera находится близко к некоторой плоскости, создается эффект большой карты.

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

Реализация коллизии игрока

Примечание: в моем движке коллизию поддерживают только два объекта: параллелепипед и пирамида.

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

Затем мы должны нашу камеру вытолкнуть наружу этого параллелепипеда: Пусть S - координаты камеры в настоящий момент (внутри параллелепипеда), а K - проекция точки S на сторону параллелепипеда, с которой столкнулась камера. Тогда новые координаты камеры будут равны:

Коллизия для падения определяется аналогично, за исключением того, что вектор направления движения камеры всегда равен { 0; 0; -0.1 }.

Заключение

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