Как создать 3D графику для игры в Excel с помощью формул

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

Примеры создания 3D графики для игры в Excel

Освоив информацию из этой статьи, вы научитесь создавать из формул Excel произвольные 3D модели и даже простые 3D игры даже без использования макросов и навыков программирования. Все что вам потребуется это умение работать с формулами и функциями в Excel. Примеры 3D игры и генератора моделей для 3D графики можно скачать в конце статьи по ссылкам на файлы Excel.

Осторожно! В статье много полезного материала с примерами - всего 20 картинок и 3 анимации под катом.

В Excel-файлах можно скачать в конце статьи и менять следующие ячейки:

• alpha: горизонтальное вращение камеры в градусах;
• beta: вертикальное вращение камеры в градусах;
• dist: расстояние от камеры до начала координат;
• fov: «зум» камеры.

Чтобы вращать камеру, необходимо дать Excel права на изменение файла.

В случае скачивания своего Excel-файла с ObservableHQ, ячейки необходимо раскрасить вручную. Нужно выделить все маленькие квадратные ячейки и выбрать «Условное форматирование» > «Цветовые шкалы».

3D алгоритм Ray marching в формулах Excel

Алгоритм Ray Marching был популяризован Inigo Quilez в 2008 году после презентации: "Rendering Worlds with Two Triangles" о компактном трехмерном движке для демосцены.

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

Ray Marching — это очень простой в реализации и эффективный алгоритм, позволяющий рендерить довольно сложные сцены. Почему тогда он не используется на видеокартах? Дело в том, что видеокарты заточены под работу с трехмерными фигурами, состоящими из треугольников, для чего Ray Marching не так эффективен.

Принцип работы 3D движка для игры на формулах Excel

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

Думаю, что в том или в ином виде все эти подзадачи решаются в любом трехмерном движке для создания 3D игр.

Описание объекта

Можно придумать три способа описания трехмерного объекта:

1. Явная формула, которая по лучу, выходящему из камеры, возвращает точку пересечения с объектом (или, например, направление касательной в ней).
2. Функция принадлежности. По точке в пространстве сообщает, принадлежит она объекту или нет.
3. Вещественная функция. Для точек внутри объекта она отрицательная, снаружи — положительная.

В этой статье будет использоваться частный случай третьего варианта, называемый signed distance function (SDF).

SDF получает на вход точку пространства и возвращает расстояние до ближайшей точки объекта. Для точек внутри она равна расстоянию до границы объекта со знаком «минус».

Нахождение пересечения луча и 3D объекта

Допустим, у нас есть луч, исходящий из камеры, и мы хотим найти точку его пересечения с объектом.

В голову приходит несколько способов найти эту точку:

1. Перебрать точки на луче с некоторым шагом.
2. Имея точки внутри объекта и снаружи, запустить двоичный поиск для уточнения места пересечения.
3. Либо запустить любой метод нахождения корней функции SDF (которая внутри объекта отрицательна, а снаружи положительна), ограниченной на луче.

Но здесь мы будем использовать другой метод: Ray Marching.

Это простой алгоритм, который работает только с SDF.

Давайте параметризуем луч по расстоянию от его начала функцией: ray(t) = (x,y,z).

Тогда ray(0) — это сама камера. Вот алгоритм:

• t = 0;
• повторять N раз: t = t + SDF(ray(t));
• если t < TMax, то вернуть ray(t) как точку пересечения, иначе сообщить, что луч не пересекает объект.

Здесь N число итераций, которое мы можем себе позволить.

Чем больше N, тем точнее алгоритм.

Число TMax это расстояние от камеры, в пределах которого мы ожидаем найти объект.

Принцип работы алгоритма генерации 3D графики в Excel

Всегда ли алгоритм дойдет до точки пересечения с объектом (точнее, будет стремиться к ней)? Объект может иметь сложную форму и другие ее части могут близко приближаться к лучу, не давая алгоритму сойтись к точке пересечения. На самом деле такого быть не может: другие части объекта обязательно будут на некотором ненулевом расстоянии от луча (иначе он бы их пересекал), которое мы обозначим δ<0. Тогда функция SDF будет больше δ для любой точки луча (кроме точек, совсем близких к точке пересечения). Поэтому рано или поздно он приблизится к точке пересечения.

С другой стороны, если алгоритм сошелся к некоторой точке, то расстояние между соседними итерациями стремится к нулю ⇒ SDF (расстояние до ближайшей точки объекта) тоже стремится к нулю ⇒ в пределе SDF = 0 ⇒ алгоритм сходится к точке пересечения луча с объектом.

Получение цвета пикселя по точке пересечения

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

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

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

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

Искомый угол Φ я обозначил одной дугой на чертеже. Значение его синуса обозначено как k.

Обычно, когда используется метод Ray Marching, для нахождения нормали к объекту делают следующее: считают значение SDF в шести точках (несложно уменьшить число точек до четырех) рядом с точкой пересечения и находят градиент этой функции, который должен совпадать с нормалью. Мне показалось, что это слишком много вычислений для Excel, и хотелось бы находить искомый угол проще.

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

Нельзя ли получить информацию об угле к поверхности исходя из скорости сходимости алгоритма? Если это так, что вообще никаких дополнительных вычислений не потребуется: достаточно проанализировать значения предыдущих итераций.

Нарисуем чертеж. Обозначим I_n и I_n+1 — точки, полученные на соседних итерациях алгоритма. Предположим, что точки находятся достаточно близко к объекту, что его можно заменить на плоскость, угол с которой мы хотим найти. Путь R = SDF(I_n), r = SDF(I_n+1) — расстояния от точек I_n и I_n+1 до плоскости. Тогда, согласно алгоритму, расстояние между I_n и I_n+1 равно R.

С другой стороны, если обозначить X — точку пересечения луча и фигуры, то: _InX = R / k, а In + 1X = r / k. Следовательно:

$R=I_n{I}_{n+1}=I_{n}X-I_{n+1}X=\frac{R-r}{k}$

$k=\frac{R-r}{R}=1-\frac{r}{R}=1-\frac{\mathrm{SDF}\left(I_{n+1}\right)}{\mathrm{SDF}\left(I_n\right)}$

То есть интенсивность пикселя равна единица минус отношение функций SDF соседних итераций!

Описываем простые фигуры с помощью формул

Примеры SDF для сферы, куба и тора:

Таблица формул для генерации 3D моделей в Excel
$\sqrt{x^2+y^2+z^2}-r$
$\max \left(\right|x|,|y|,|z\left|\right)-\frac{\mathrm{side}}{2}$
$\sqrt{{\sqrt{x^2+z^2}-R}^2+y^2}-r$

Фигуры можно перемещать и сжимать вдоль осей:

Примеры формул для модифицирования 3D моделей сделанных в Excel
$\mathrm{cube}(x,y+0.3,z)$
$\mathrm{cube}(x,2\cdot y,z)$

Фигуры также можно объединять, пересекать и вычитать. То есть SDF поддерживает основные операции конструктивной сплошной геометрии:

Формулы слияния и вычитания 3D моделей в Excel
min(sphere(x, y, z), cube(x, y, z))
max(sphere(x, y, z), cube(x, y, z))
max(-sphere(x, y, z), cube(x, y, z))

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

Это малая часть того, что можно делать при помощи SDF.

Совмещая все приведенные формулы, получаем первую фигуру:

Пример формулы создания сложной 3D модели в Excel

$$\min \left( \max \left(\right|x|-0.3,|y|-0.3,|z|-0.3,-\sqrt{x^2+y^2+z^2}+0.375), \sqrt{{\sqrt{{(x-0.25)}^2+{(z-0.25)}^2}-0.25}^2+y^2}-0.05\right)$$

Формула для создания 3D модели чайника

С чайником немного сложнее - сначала нужен план:

$$\min ( \sqrt{x^2+{(y-0.27)}^2+z^2}-0.05, \sqrt{x^2+{2.5\cdot y^2}^{}+z^2}-0.4, \sqrt{{\sqrt{x^2+z^2}-0.3}^2+{(y-0.18)}^2}-0.02, \max \left( x+y-0.7, -y+0.09, \sqrt{{\sqrt{{(x-0.55)}^2+{(y-0.09)}^2}-0.1}^2+{(z-0.1)}^2}-0.04\right), \max \left( -(-y+0.09), \sqrt{{\sqrt{{(x-0.35)}^2+{(y-0.09)}^2}-0.1}^2+{(z-0.1)}^2}-0.04\right))$$

И подбираем нужный ракурс. Готово:

Формулы настройки камеры

Все, что нам осталось — для данного пикселя на экране найти соответствующий ему луч в пространстве, выходящий из камеры. Если точнее, то надо уметь находить точку этого луча по расстоянию до камеры. То есть нам нужна функция ray(s, t, d), где s, t — координаты пикселя, а d — расстояние от начала луча (камеры).

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

$$s\in [-\frac{\mathrm{cols}}{2},\frac{\mathrm{cols}}{2}],t\in [-\frac{\mathrm{rows}}{2},\frac{\mathrm{rows}}{2}]$$

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

Большей части вычислений в этой главе можно было бы избежать, например, поместив камеру в точку (1, 0, 0) и направив вдоль оси $X$. Но с учетом того, что фигуры также выровнены вдоль осей, в итоге получился бы не очень интересный ракурс. Так в случае куба мы бы видели его как квадрат.

Чтобы обеспечить возможность поворота камеры, нужно аккуратно провести некоторое количество вычислений с Эйлеровыми углами. Таким образом мы получаем три переменные на входе: угол alpha, угол beta и расстояние dist. Они определяют как положение, так и направление камеры (камера всегда смотрит в начало координат).

При помощи WolframAlpha находим матрицу поворота:

$$\left(\begin{array}{c}x\\ y\\ z\end{array}\right)=\underset{\underset{x}{-\left(M\right(\alpha ,\beta \left)\right)}}{\begin{array}{c}\left(\pi ʠ\right)\\ \backslash cos\left(\alpha \right)ʠ\backslash cos\left(\beta \right)-\backslash cos\left(\alpha \right)ʠ\backslash sin\left(\beta \right)& \backslash sin\left(a\right)\\ \backslash sin\left(\beta \right)& \backslash cos\left(\beta \right)& 0\\ -\backslash cos\left(\beta \right)ʠ\backslash sin\left(\alpha \right)& \backslash sin\left(\alpha \right)ʠ\backslash sin\left(\beta \right)& \backslash cos\left(\alpha \right)\end{array}}\angle \begin{array}{c}\mathrm{x\text{'}}\\ \mathrm{y\text{'}}\\ \mathrm{z\text{'}}\end{array}$$

Если применить ее к вектору (dist, 0, 0), получим координаты камеры (не спрашивайте меня, куда пропал минус):

$$\left(\begin{array}{c}\mathrm{camX}\\ \mathrm{camY}\\ \mathrm{camZ}\end{array}\right)=\begin{array}{c}M\\ (\alpha ,\beta )\end{array}\cdot \begin{array}{c}\mathrm{dist}\\ 0\\ 0\end{array}=\mathrm{dist}\cdot \begin{array}{c}\backslash cos\left(\alpha \right)\cdot \backslash cos\left(\beta \right)\\ \backslash sin\left(\beta \right)\\ \backslash sin\left(\alpha \right)\cdot \backslash cos\left(\beta \right)\end{array}$$

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

У экрана нет точного местоположения и размера. Точнее, они зависят от расстояния до камеры: если экран отодвинуть дальше, его потребуется сделать больше. Поэтому условимся, что расстояние от камеры до экрана равно 1. Тогда мы можем вычислить значение вектора (x0, y0, z0), соединяющего точку камеры и центр экрана (он такой же как и у центра камеры, только домноженный не на dist, а на -1):

$$\left(\begin{array}{c}\mathrm{x0}\\ \mathrm{y0}\\ \mathrm{z0}\end{array}\right)=M(\alpha ,\beta )\cdot \begin{array}{c}-1\\ 0\\ 0\end{array}=-\begin{array}{c}\backslash cos\left(\alpha \right)\cdot \backslash cos\left(\beta \right)\\ \backslash sin\left(\beta \right)\\ \backslash sin\left(\alpha \right)\cdot \backslash cos\left(\beta \right)\end{array}$$

Теперь нам надо определить размер экрана. Он зависит от угла обзора камеры, который измеряется в градусах и соответствует тому, что в видеокамерах называется «zoom». Пользователь задает его при помощи переменной fov (field of view). Так как экран не квадратный, необходимо уточнить, что имеется в виду вертикальный угол обзора.

Итак, чтобы определить высоту экрана, нужно найти основание равнобедренного треугольника с вершинным углом fov и высотой 1: вспоминая тригонометрию, получаем 2tan(fov / 2). На основании этого можно определить размер одного пикселя на экране:

$$\mathrm{pixelSize}=\genfrac{}{}{0ex}{}{2\backslash tan\left(\frac{\mathrm{fov}}{2}\right)}{\mathrm{rows}}$$

Далее, применяя матрицу поворота к векторам (0, 0, 1) и (0, 1, 0), получаем вектора $$\bar{u}$$ и $$\bar{v}$$ , задающие горизонтальные и вертикальные направления экрана (для упрощения расчетов они также предварительно домножены на pixelSize):

$$\left(\begin{array}{c}\mathrm{ux}\\ \mathrm{uy}\\ \mathrm{uz}\end{array}\right)=\mathrm{pixelSize}\cdot M(\alpha ,\beta )\cdot \begin{array}{c}0\\ 0\\ 1\end{array}=\mathrm{pixelSize}\cdot \begin{array}{c}\backslash sin\left(\alpha \right)\\ 0\\ \backslash cos\left(\alpha \right)\end{array}$$

$$\left(\begin{array}{c}\mathrm{vx}\\ \mathrm{vy}\\ \mathrm{vz}\end{array}\right)=\mathrm{pixelSize}\cdot M(\alpha ,\beta )\cdot \begin{array}{c}0\\ 1\\ 0\end{array}=\mathrm{pixelSize}\cdot \begin{array}{c}\backslash cos\left(\alpha \right)\cdot \backslash sin\left(\beta \right)\\ \backslash cos\left(\beta \right)\\ \backslash sin\left(\alpha \right)\cdot \backslash cos\left(\beta \right)\end{array}$$

Таким образом у нас теперь есть все компоненты, чтобы найти направление луча, выходящего из камеры и соответствующего пикселю с координатами s, t

$$\mathrm{raydir}(s,t)=\left(\begin{array}{c}\mathrm{x0}\\ \mathrm{y0}\\ \mathrm{z0}\end{array}\right)+s\cdot \left(\begin{array}{c}\mathrm{ux}\\ \mathrm{uy}\\ \mathrm{uz}\end{array}\right)+t\cdot \left(\begin{array}{c}\mathrm{vx}\\ \mathrm{vy}\\ \mathrm{vz}\end{array}\right)$$

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

$$\mathrm{ray}(s,t,d)=\left(\begin{array}{c}\mathrm{camX}\\ \mathrm{camY}\\ \mathrm{camZ}\end{array}\right)+d\cdot \frac{\mathrm{raydir}(s,t)}{\parallel \mathrm{raydir}(s,t)\parallel }$$

Так мы получили искомую функцию ray(s, t, d), которая возвращает точку луча на расстоянии d от его начала, соответствую пикселю с координатами s, t.

Как сделать 3D движок для создания игр в Excel

Файл Excel, который получается в результате, является книгой, состоящей из >6 листов:

1. Первый лист R содержит все, что нужно конечному пользователю: клетки с параметрами rows, cols, fov, alpha, beta, dist, а также клетки с результатом, раскрашенные по черно-белой шкале.
2. Лист N предрассчитывает значения $$\frac{1}{\parallel \mathrm{raydir}(s,t)\parallel }$$ .
3. Листы X, Y, Z вычисляют координаты X, Y, Z векторов raydir(s, t) и $$\frac{\mathrm{raydir}(s,t)}{\parallel \mathrm{raydir}(s,t)\parallel }$$ .
4. Листы i1, i2,… содержат итерации алгоритма Ray Marching по каждому пикселю.

Все листы построены по одинаковой схеме:

1. В первой строчке находится 1-6 «глобальных» переменных (голубые). Они могут использоваться во всех листах.
2. Большая часть листа занята вычислениями по пикселям (зеленые). Это прямоугольник размера rows\times cols. В таблицах в конце статьи эти ячейки обозначены как **
3. В листах X, Y и Z также используются промежуточные вычисления по строкам и столбцам (оранжевые). Для них зарезервированы вторая строка и первый столбец. В таблицах в конце статьи эти ячейки обозначены A* и *2. Идея состоит в том, что для хранения значений raydir(s, t) по всем пикселям не обязательно добавлять еще три листа (для каждой из координат) так как формула его вычисления разбивается в сумму двух компонент:

$$\mathrm{raydir}(s,t)=\underset{\text{по столбцам}}{\left(\begin{array}{c}\mathrm{x0}\\ \mathrm{y0}\\ \mathrm{z0}\end{array}\right)+s\cdot \left(\begin{array}{c}\mathrm{ux}\\ \mathrm{uy}\\ \mathrm{uz}\end{array}\right)}+\underset{\text{по строкам}}{t\cdot \left(\begin{array}{c}\mathrm{vx}\\ \mathrm{vy}\\ \mathrm{vz}\end{array}\right)}$$

Таким образом мы предвычисляем первое слагаемое по столбцам и второе по строкам и, когда нам нужно получить значение raydir(s, t), мы складываем значение ячейки для строки s и столбца t.

I1

V1

AI1

AV1

BI1

BV1

**

I1

**

I1

V1

AI1

AV1

A*

*2

**

I1

V1

AI1

A*

**

I1

V1

AI1

AV1

A*

*2

**

I1

**

**

Примечания:

Так как в Excel вычисления производятся в радианах, аргументы всех тригонометрических функций домножаются на $$\frac{\pi }{180}$$ (в Excel для этого есть функция RADIANS). Чтобы не запутывать формулы, я убрал эти умножения в таблицах выше. Все они есть в файлах с примерами:

Скачать пример создания 3D графики в Excel

Скачать шаблон генерации 3D модели чайника в Excel

Скачать 3D игру с использованием формул Excel

В итоге можно утверждать, что с помощью формул Excel можно сделать простой 3D движок или даже 3D игру в Excel. Наибольшая польза этих примеров – это возможность легко освоить базовые принципы создания 3D графики на простых примерах формул Excel. Освоив эти принципы, можно перенести их на любой язык программирования для расширения возможностей и достижения существенных результатов в области разработки. Порог входа в освоение формул Excel всегда ниже любого языка программирования. Я рекомендую начинать обучение программированию с помощью формул и функций Excel. Их легко освоить, а принципы работы функций Excel очень похожи на функции языков программирования.

Источник: https://habr.com/ru/articles/353422/