Серия «Делаем 3D игру»

Всем добрый вечер! Материал к данному посту уже давно был готов, но не получилось выпустить его так быстро, как хотелось. Но, тем не менее.
Часть 1. Введение, строим 2D объект

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

Итак, в прошлый раз мы остановились на том, что научились поворачивать 2D-область с помощью матриц. Некоторые просили рассказать подробнее о том, как их решать. Думаю, в этом посте завеса тайны будет чуть приоткрыта. Давайте начнём операции по расширению пространства до трёхмерного и добавим z-ось. Для этого мы сделаем следующее:

Задача 1. Изменим структуру нашего объекта, позволив хранить трёхмерные координаты.

Было:

Стало:

Для того, чтобы понять, почему количество значений увеличилось на столько порядков,  сразу же небольшая беседа о структуре 3D объекта. По-научному это называется "полигональная сетка".
Если кратко, то мы можем хранить описание 3D объекта в виде:
1. Списка вершин (Vertices)
2. Списка ребёр (Edges)
3. Списка, ну скажем так, граней (Faces)

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

Рассмотрим куб. Куб имеет 8 крайних точек. Описываются их координаты по 3 осям, скажем так, в явно заданном виде (обычно они задаются в виде векторов, т.е. {0.5f, 0.23f, -0.09f} и т.п.). Далее следует порядок их объединения.

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

Представим куб в виде пар координат. Две крайние точки, соединяются в ребро, которое будет отображено в виде линии на экране. Тогда одно такое ребро будет задано координатами (x1, y1, z1, x2, y2, z2). Логичнее разместить их попарно ({x1,y1,z1}, {x2,y2,z2}, но, для упрощения алгоритма, они будут размещены в линию. У куба 8 вершин. А рёбер уже 12. Поэтому и получаем такую картину:

Если 2D прямоугольник в виде точек описывался массивом [4][2], то куб в виде рёбер уже [12][6].
Также, к центру объекта добавляется третье измерение: float center[3] = { 0.f, 0.f, 0.f };

Задача 2. Организуем проекцию трёхмерного пространства на двумерное
Как я уже упоминал в первом посте, который некоторые незаслуженно назвали "бредом", модель находится где-то там, в невидимом пространстве, а вот практическую реализацию мы можем увидеть. Проекция двумерных координат очень проста по своей сути: x точки отображаем как x на экране, а y, как y. Здесь же мы имеем дело так же с x и y, но при этом куда-то нужно ещё вставить зависимость от координаты z. Можно сделать это также несколькими способами:

1. Построить ортогональную проекцию,  например, представив x как x+ k*cos(a)*z, но этот вариант рассматривать мы сейчас не будем.

2. Непосредственно разделить на z: x'=kx/z и y'=ky/z
Второй вариант, на самом деле, очень прост. формулы расскажут его лучше, чем я:

Для получения двумерной координаты достаточно лишь сделать вот так. WW/2 - половина ширины экрана (x), FOV - коэффициент поля видимости, x - координата из массива (value[0]), z - то же самое (value[2]).

Здесь вводится коэффициент FOV, характеризующий глубину поля зрения. Если кто-то когда-либо интересовался анаглифными 3D-очками, то он мог заметить, что при изменении FOV на рендерере изменяется нагрузка на глаза. При сильных значениях изображение вообще перестаёт сходится. Проще показать наглядно, что я и сделаю в примере. В нашем случае примем его как константу 200-300 единиц, и более не будем трогать. Получив все координаты x' и y', осуществляем рендеринг, аналогично 2D из первого поста.

Так как я демонстрирую алгоритм, а не работу с библиотекой, я не использую вспомогательные средства SFML, а только лишь отображение объектов по явным координатам, подобно тому, как это делалось на древних компьютерах типа ZX Spectrum.

Ии.. мы получили вот такую картину:

Четыре точки на поле. А чем она отличается от той, что была в первом посте, спросите вы? Не торопитесь. Давайте теперь включим отображение линий:

Что-то начинает проясняться.. Мы находимся в центре куба, и смотрим прямо. Потому и видим четыре точки одной из его граней. Так и должно быть. При таком способе проекции наш экран соответствует координате z = 0. Таким образом, остальные 4 точки остались за нашей спиной, и к ним уходят соответствующие рёбра. Так же, чтобы избежать вылета приложения при делении на z = 0, нужно перед операцией деления явно указать: if (z=0) z=(0.01f). На этом задача по рендерингу окончена.

Задача 3. Расширяем функции поворота для 3D пространства
Вот здесь мы снова сталкиваемся с матрицами. Только для двумерного прямоугольника они были второго порядка, а сейчас нас ожидают матрицы 3 порядка (иллюстрация с сайта Wikipedia):

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

(цифры выше для примера). В нашем столбце будут координаты трёх вершин 1-й точки. Для линии, соответственно, делается два умножения. Более подробно для людей, мало знакомых с матрицами:
1. Сначала составляется матрица Mx, My, Mz в зависимости от того, вращение вокруг какой оси вам потребовалось: x,y,z.
2. Затем полученная матрица векторно перемножается на данные координаты
3. Полученные координаты записываются в новый объект, который будет являться уже повёрнутой копией старого объекта (в ООП), либо просто в поля (область памяти) старого объекта, как делалось на старинных компьютерах.

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

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

newValue[i] - новое значение x[0], y[1], z[2] для первой точки линии. Для второй точки - аналогично.
oldData[i] - старое значение x[0], y[1], z[2] для первой точки линии. Аналогично newValue
center[i] - аналогично заданные координаты центра объекта.

Именно здесь нам и пригодился центр объекта. При повороте относительно произвольной оси, если объект уже был сдвинут, при неверно заданном центре объект начнёт вращаться либо с большим радиусом, либо вообще непредсказуемо. Поэтому при операции сдвига, например, +100 по z, в center так же записывается z: 0,0,100.

Грубо говоря, в процессе перемножения матрицы, координата центра вычитается, и объект как бы "возвращается" в центр поля, вычисляется, и затем сдвигается обратно. Скорее всего, есть и более эффективные алгоритмы для решения данной задачи.

Давайте теперь испытаем полученные функции, и попробуем повернуть куб (как я и говорил, поворот осуществляется по прерыванию, т.к. игровой таймер всё ещё отсутствует):

Я кружусь в фантастическом танце. Я почти итальянец!

Также, демонстрация изменения константы FOV из задачи 2 на развёрнутом кубе:

Т.е. изменение FOV как бы искажает отклонение осью z оси x. Проявляется это увеличением количества видимых на экране объектов.

Задача 4. Элементы "гейм-дизайна"
Давайте теперь попробуем реализовать элемент игры, а именно, космический корабль, которым мы управляем. Нам понадобится модель корабля. Так как пишем мы примитивную игру, так сказать, "следуя по стопам" за гигантами прошлого века, модель тоже должна быть несложной в исполнении. Я смоделировал её в 3D редакторе:

Теперь нужно получить её рёбра. Сделать это явно мы не сможем, поэтому получим хотя бы вершины. Экспортируем модель в формате .obj. На примере куба:

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

4 вершины, 1 "face": задан как 1//1 2//1 4//1 3//1. Но наша программа устроена по другому принципу. Возьмём отсюда только лишь вершины. Так как писать автоматизированное ПО для одной модели нецелесообразно, порядок соединения выставим вручную. Воссоздаём модель корабля:

Вот, как будет выглядеть модель, если неправильно были выставлены оси координат. Помните ложку из 1 части поста? А это в подобном представлении наш корабль..

Но, тем не менее, каркасная модель выполнена и состоит из 36 рёбер:

Давайте запустим программу:

В движении смотрится более эффектно:

К полёту готов! Также сразу же можно выполнить некоторую "постановку" сцены: корабль сдвигается вместо центра примерно на 0,7 экрана по y. Однако, конечно, пока это ещё не игра, а всего лишь просмотрщик 3D модели. Но, всё это, как и прежде, поправимо. Вопрос только, когда..

Всем спасибо, с вами был Kekovsky, надеюсь, пост был для вас информативным, комментируйте, поддерживайте автора и т.д.

Всем привет! В предыдущих постах я программировал посудомоечную машину. Теперь решил сделать мини-серию постов о программировании, а точнее, о том, как надо мыслить для того, чтобы программа получилась. Я не буду вдаваться в нюансы написания самого кода. Здесь, скорее, будут размышления на тему, так что быть программистом для чтения не обязательно (и не желательно). Поехали.

Для начала, небольшой ракурс в историю. Первая игровая приставка (в привычном нам понимании) появилась в 1972 году. Разработала её группа военных инженеров во главе с Ральфом Бером  -"Отцом видеоигр". Эта самая приставка была впоследствии названа Magnavox Odyssey. Выполнена она была полностью на транзисторах. Можете себе представить? (фото взято с сайта Wikimedia).

Такая приставка умела немного. Однако, важнее всего была суть - возможность генерировать свой управляемый телевизионный канал. До этого подобное не приходило никому в голову. Так вот, примерно спустя 10 лет после этих событий, появились в продажу компактные ЭВМ для массового потребления - ZX Spectrum, IBM PC и другие. Каждый получил возможность изучить компьютеры и обрёл пространство для своих творческих экспериментов. А пятьдесят лет спустя, мы привыкли видеть компьютерные игры уже так:

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

Кстати говоря, скоро наступает 1 сентября. Вспоминаются мои институтские годы - как мы пришли, и первой парой стояла высшая математика. До сих пор во многих провинциальных вузах программа первого семестра начинается с матриц. Я помню ребят, которые невесть как попали в институт, смотрели с задних парт круглыми глазами и только повторяли "- И чё мы тут вообще забыли?". Кстати говоря, ребята эти в итоге семестр не пережили и были отчислены. Но это уже их проблемы. Однако, даже у тех, кто остался, часто возникали вопросы: зачем? что это мы такое учим?

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

Но давайте приступать. Для начала, чтобы программа получилась, необходимо мышление программиста. Я его понимаю, как две составляющие: некая абстрактная модель и её реализация. Короче говоря, теория и практика. Чтобы было более понятно, о чём я говорю, давайте представим, что мы программируем обычную столовую ложку, как в фильме "Матрица"

Так вот, если думать, как программист, то эту ложку можно разделить на две составляющие.

1. Теория ложек
Какие параметры существуют у ложки? Такие, какие вы ей сами зададите. Вы можете взять тарелку, зачерпывать ей суп, и тем самым объявить тарелку ложкой. Но немногие с вами согласятся, ведь, во-первых, это неудобно. Во-вторых, все привыкли видеть ложку привычной ложкой. Поэтому рассмотрим более детальные требования:
- Ложка имеет хлебало и держало черенок и чашечку. Чашечка, в свою очередь, имеет форму полусферы. Мы можем задать чашечку, например как функцию z^2 = x^2 + y^2

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

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

Или так:

И то и это - нормально. Всё дело в представлении ложки. В том, как мы её видим и в том, как мы её задали. Последнее компьютер выполняет, в отличие от людей, весьма чётко. Мы задали какую-то задачу, и получили конкретный результат.

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

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

Давайте рассмотрим одну из таких задачек. Вспомним ракурс в историю, который был в начале поста. Первые 3D игры для первых ЭВМ были примерно такие: Battle Tank

Star Wars: Empire strikes back.

Всё это было до Джона Кармака, появления Direct3D, OpenGL и т.д. Примерно в таком ракурсе мы и будем с вами сегодня сегодня работать. Писать будем пока на плюсах, хотя для новичков проще это будет сделать, наверное, на питоне. В качестве подспорья возьмём графическую библиотеку SFML. С 2018 года она уже не поддерживается, но, для иллюстрации сути поста её будет достаточно. Мы хотим получить что-то вроде этого:

Для того, чтобы обдумать реализацию, и, в дальнейшем, это получить, мы должны разобрать "по косточкам" происходящее на экране. Мы видим:
1. GUI (интерфейс с очками и временем). Пока отбросим его.
2. Пространство с астероидами
3. Космический корабль
Также мы знаем, что происходит при нажатии клавиши:
1. Космический корабль наклоняется в сторону
2. Пространство поворачивается вокруг корабля, создавая иллюзию того, что корабль куда-то летит (да, когда вы играете в компьютерную игру, это не игрок поворачивается в пространстве, а пространство вокруг игрока).

Теперь рассмотрим более подробно первую задачу: по нажатии клавиши космический корабль поворачивается. Давайте разберём корабль, по аналогии с ложкой. Он представляет собой проекцию трёхмерного объекта на двумерное, группу точек, соединённых рёбрами (в случае Wireframe моделей - линиями, в остальных - треугольниками, полигонами). Значит, теория корабля следующая:
1. Где-то есть группа точек. Её мы просто задаём, как набор переменных. Произвольно. Но хотя бы один экземпляр её должен существовать.
2. Есть способ изменения этой группы точек по внешним параметрам. Для этого есть матрицы сдвига, масштабирования и поворота в трёхмерном пространстве (материал взят с сайта Wikipedia):

3. Есть способ отображения их на мониторе (хотя это уже больше относится к реализации)
Прежде, чем приступать к реализации 3D варианта (он будет во второй части поста), давайте упростим наш корабль до прямоугольника, и одно измерение уберём. Таким образом, будет проще разобрать задачи на начальном этапе. Да и матрица поворота сильно упрощается и теряет один порядок:

С теорией понятно, давайте перейдём к практике.

1. Развернём IDE, подключим библиотеки, подготовим точку входа.

2. Создадим класс Box2D. Зададим группу точек нашего прямоугольника как двумерный массив - массив пар координат. Пока что с конечным размером.:
float vertices[4][2] = { {-50.f, 50.f}, {-50.f, -50.f}, {50.f, -50.f}, {50.f, 50.f} };

Также добавим переменную center, характеризующую сдвиг центра объекта. Это необходимо для возможности дальнейшего поворота относительно произвольной оси, но пока не нужно.

3. Добавим методы, осуществляющие поворот объекта по заданному углу. Код здесь получился несколько кривой в результате быстрого его портирования с питона, но, в дальнейшем, поправим:

Обратите внимание.
В generateMatrix переменная newMatrix - та самая матрица поворота. Вспоминаем нашу математику. Функция подготовит матрицу поворота на конкретно заданный градус. Именно на неё мы будем перемножать имеющиеся ранее заданные значения точек, чтобы получить новые координаты.
calculatePerVertex - перемножает координаты на матрицу.
recalculateRotation - проходит по всем координатам объекта и выполняет их обработку.

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

Ну и осталось спроецировать эти точки на экран. Тут есть множество вариантов - можно также создать копию массива точек, соответствующих полученным значениям, если в дальнейшем нам нужно применять к точкам ещё какие-либо операции. В нашем случае это не нужно, поэтому все точки можно просто забить поочерёдно в дисплейную область оперативной памяти посредством средств библиотеки SFML - объекта "Circle" со смещением на координаты, задаваемые вершинами.

Готовый результат при таком способе проекции будет выглядеть так:

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

Обобщим вышесказанное:
Мы имеем некоторую воображаемую модель множества точек. Над которой осуществляем операции, и затем практически отображаем результат этих операций. Именно за это и отвечает математика. Хотя, конечно, это чуть ли не школьный уровень.

Давайте изменим практическую реализацию и соединим наши точки линиями. Для этого мы сообщаем в модель ещё один внешний параметр - порядок соединения этих линий. Он может быть произвольным. Но, как мы знаем, у прямоугольника каждая вершина соединяется лишь с двумя другими под углом 90 градусов. Поэтому порядок соединения будет 1-2-3-4-1.

Центр обозначен красной точкой. Уже становится немного понятно, каким образом осуществляется управление воображаемым космическим кораблём. Далее остается лишь добавить третье измерение, и получить куб. Немного забежим вперёд:

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

А для тех, кто дочитал и кто любит компьютерные игры, забежим ещё очень сильно вперёд. В 2009 году Маркус Перссон, изобретатель игры "Minecraft" написал маленький апплет, под названием Minecraft 4k. Вот, как он выглядел:

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

С вами был Kekovsky, на сегодня всё, приятных выходных. Если какие-то из моих постов понравились или были для вас информативными, можете поддержать меня, благодаря стараниям администрации Пикабу у меня теперь так же есть донатная кнопка.
Всем успехов в освоении новых наук!