Как создать графический движок с нуля на Python
Заявление об ограничении ответственности: я делал это не один — Мэтт и Девин также внесли большой вклад в этот проект. Кроме того, мы продолжим вносить улучшения, поэтому следите за обновлениями и не стесняйтесь вносить свой вклад на GitHub.
Честно говоря, мы не знали, насколько легко / сложно на самом деле заставить графический движок работать. Оказывается, линейная алгебра относительно проста, а код довольно прост. Эта статья будет довольно общим обзором того, как мы подошли к проблемам кода с более глубоким погружением в линейную алгебру, которую мы использовали.
Код
Чтобы проект оставался чистым, мы разделили код на три отдельных модуля.
Модуль дисплея
Прежде чем мы начали, мы поняли, что для того, чтобы наш графический движок хоть как-то работал, нам нужно иметь возможность отображать изображение на экране. Теперь библиотека пользовательского интерфейса по умолчанию в Python называется Tkinter, у которой есть свои плюсы и минусы. (Главный недостаток, с которым мы столкнулись, заключается в том, что он блокирует основной поток, и некрасиво работать с потоками, хотя это в нашем списке потенциальных оптимизаций.)
Чтобы справиться со всем этим, мы создали модуль display в нашем проекте, где находятся классы Screen и Bitmap . Screen обрабатывает задачи окна, настраивает и отключает, а также отвечает на вводимые пользователем данные. Bitmap принимает три точки и цвет и рисует соединяющий их треугольник заданного цвета (раньше это был обычный Python с Tkinter, но с тех пор добавили numpy и подушку для ускорения).
Модуль алгебры
Поскольку графический движок по своей сути содержит так много линейной алгебры, мы создали удобный модуль, который имеет несколько классов: Vec3 , Vec2 и Mat3 (матрица 3×3). На самом деле это не более чем оболочки для массива или массива массивов, но они реализуют перегрузку операторов и некоторые вспомогательные методы (подумайте о скалярном произведении, перекрестном произведении и умножении матриц), которые делают остальную часть кода намного чище. .
Модуль двигателя
Решая, как структурировать наш графический движок, я опирался на опыт работы с OpenGL, Apple SceneKit, Unity, Roblox и программу 3D-моделирования Blender. Результат наиболее точно соответствует структуре, которую использует Unity.
Самый фундаментальный объект в нашем движке — это Node . Node имеет три свойства: Mesh , Transform и Shader , а также массив дочерних узлов. Mesh — это объект, который содержит список точек ( Vec3 ) и граней (массив индексов трех точек, которые соединяет это лицо). Transform кодирует, как масштабировать, вращать и перемещать этот узел и все дочерние элементы относительно родительского узла. И Shader в настоящее время просто сохраняет цвет узла, но это в списке улучшений.
От Node идет объект Camera , который кодирует важную информацию о рендеринге сцены. И хотя Camera происходит от Node, он не поддерживает Mesh или Shader — только Transform . Он также имеет несколько других важных свойств: фокусное расстояние, ширину изображения, высоту изображения, ближнюю глубину и большую глубину. Ширина и высота довольно просты, фокусное расстояние мы рассмотрим в линейной алгебре, а ближняя глубина и дальняя глубина — это просто точки отсечки для «слишком близко» и «слишком далеко», в которых мы отбрасываем треугольники от рендеринга. — часть более крупного процесса, называемого отбраковкой.
Объект самого высокого уровня в движке — это Scene . Scene довольно прост — он просто содержит корень Node , дочерним элементом которого должно быть все в сцене, и ссылку на Camera , который следует использовать для рендеринга. У него также есть самый важный метод: render() , который заставляет все отображаться на Bitmap с использованием большого количества линейной алгебры.
Линейная алгебра
Что меня больше всего удивило, так это то, что линейная алгебра, которая заставила все работать, была действительно довольно простой. Хотя большинство людей забыли об этом, умножение матриц и векторов, которым изучают в старших классах, действительно все, что вам нужно, чтобы заставить этот движок работать.
Чтобы объяснить линейную алгебру, мы рассмотрим один вызов метода render() в нашем Scene объекте. Представим, что наша сцена содержит единственный узел со следующей сеткой:
И чтобы было интересно, почему бы нам не переместить его на (5, 20, 3) , повернуть вокруг оси z на 45 ° и удвоить его размер. Используя стандартную камеру (фокусное расстояние: 2, ширина: 4, высота: 3), мы должны получить следующее изображение:
Шаг 1. Примените преобразование
Когда мы только начинаем, каждый отдельный узел определяет свое собственное пространство. Наш куб существует в другом пространстве, чем наша камера, которая существует в другом пространстве, чем любой другой узел. Чтобы увидеть, где на самом деле вершины находятся по отношению друг к другу, нам нужно применить масштабирование, поворот и перенос каждого узла ко всем его вершинам и дочерним элементам.
Во-первых, давайте посмотрим на сам объект Transform . Для его создания мы предоставляем три вектора: перевод, поворот и масштаб. Поскольку действия поворота и масштабирования являются линейными преобразованиями, они могут быть описаны с помощью матриц и реализованы с помощью умножения матриц, поэтому код для Transform просто содержит одну комбинированную матрицу для поворота и масштабирования. С другой стороны, преобразование отображает нулевой вектор в другое место, кроме нуля, поэтому это не линейное преобразование и не может быть описано матрицей. Вместо этого он просто держится за вектор трансляции.
Учитывая Transform , довольно просто переместить вершину из одного пространства в пространство, описанное преобразованием — манипулировать указанным вектором с помощью матрицы преобразования, а затем смещать его вектором преобразования. Но что, если нам нужно выполнить преобразование для другого преобразования? (Представьте себе случай, когда у вас есть еще один узел, являющийся дочерним по отношению к нашему кубу — нам нужно применить как родительские, так и дочерние преобразования к вершинам дочернего элемента.) Что ж, оказывается, умножение матриц эквивалентно выполнению одного преобразования и потом еще один! Это означает, что мы можем создать новый Transform , который учитывает как родительские, так и дочерние преобразования, умножая матрицы и складывая переводы.
Итак, чтобы переместить каждую вершину в единое мировое пространство, мы начинаем с корня и продвигаемся вниз к каждому узлу и каждой вершине, применяя и связывая преобразования по пути. Затем мы сохраняем большой список всех новых вершин и граней (важно обновить грани, чтобы они соответствовали новому индексу каждой вершины) и передаем его следующему шагу.
Шаг 2: сортировка по W-индексу
W-индекс — одна из основных частей растеризации, которая не является стандартной линейной алгеброй. Идея проста, но важна: мы хотим нарисовать ближайшие поверхности поверх самых удаленных поверхностей. Если в вашей сцене красивое голубое небо, которое находится очень далеко, мы хотим, чтобы дерево на переднем плане не было перезаписано визуализацией треугольников неба. Чтобы решить эту проблему, для каждого лица рассчитывается индекс w или расстояние до камеры. Лица с наивысшим индексом w рисуются первыми, а лица с самым низким индексом w рисуются последними и оказываются наверху.
Чтобы вычислить лицо, нам нужно найти центр лица и вычислить квадрат расстояния от этого положения до точки фокусировки камеры. (Мы используем квадрат, потому что извлечение квадратного корня затратно с вычислительной точки зрения и замедлило бы работу нашего двигателя.) Мы столкнулись с проблемами, когда использовали среднее положение точек в качестве центра, потому что центр в конечном итоге сдвигался бы к основанию треугольник, что иногда приводит к неправильному порядку. Теперь мы вычисляем ограничивающую рамку трех точек и используем ее центр, что отлично работает.
После того, как все w-индексы вычислены, грани переупорядочиваются в соответствии с убывающим w-индексом и переходят к следующему шагу.
Шаг 3. Рисование в растровое изображение
Теперь, когда у нас есть все лица, которые мы хотим нарисовать в мировом пространстве, и они упорядочены правильно, последний шаг — превратить трехмерный мир в двухмерное изображение, которое мы можем поместить на экран.
Мы делаем это, отображая каждую вершину из мирового пространства в 2D-пространство, определяемое камерой, которое мы называем экраном. Помогает представить нашу камеру такой:
Двухмерное положение вершины задается путем рисования линии между точкой фокусировки и этой вершиной в мировом пространстве, а затем вычисления ее пересечения с экраном. Затем мы превращаем это положение пересечения в 2D-координату. Все, что не пересекает экран (который имеет определенную ширину и высоту), считается вне поля зрения камеры и не отображается, как в реальной жизни.
Математически мы достигаем этого, находя два вектора: вектор от точки фокуса к вектору, который мы хотим нарисовать, который мы назовем a, и вектор от точки фокусировки к центру экран, который мы назовем f. Точка пересечения должна находиться в плоскости экрана, а это значит, что ее компонент вдоль f должен быть равен длине f. И поскольку он будет проходить вдоль линии, соединяющей точку фокусировки и нашу вершину, это будет скалярное число, кратное a. Если мы назовем вектор от фокальной точки до точки пересечения v,, мы получим следующую систему уравнений:
Теперь, когда у нас есть положение точки пересечения в мировом пространстве, мы можем превратить его в экранные координаты, найдя вектор от центра экрана к точке пересечения и вычислив компонент вдоль w и h, векторы от центра до правой границы экрана и верхней границы экрана соответственно.
Благодаря процессу преобразования вершин в координаты экрана рисование граней становится упражнением по заполнению треугольников. Мы вычисляем три линейных уравнения, которые соединяют точки, затем шагаем по оси x, используя уравнения, чтобы определить минимальное и максимальное значения y для заданного значения x.
Мой главный вывод из этого проекта состоит в том, что линейная алгебра, которая используется при создании графического движка, не является недосягаемой для всех. В качестве курса средней школы или университета по линейной алгебре и Python или как способ самообучения конечный продукт чрезвычайно полезен, а работа вполне выполнима.
Конечно, есть много улучшений, которые можно и будут делать. Эта статья будет обновляться по мере внесения серьезных изменений (особенно повышения производительности). Две функции, которыми меня интересуют: отбраковка (выяснение, какие грани не нужно рисовать) и освещение или шейдеры (так что узлов может быть больше, чем только один сплошной цвет).
Каэден Уайл — студент Вашингтонского университета, соучредитель Offsite и основатель Kilometer Creative, где он выпустил несколько игр в App Store, включая TileForm и Landr.