Как сделать сферу в excel

Трехмерный движок на формулах Excel для чайников

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

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

Также я сделал небольшое веб-приложение, где можно потренироваться в создании формул для произвольных фигур и сгенерировать свой файл Excel.

Осторожно: 19 картинок и 3 анимации под катом.

Что получилось

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

Ray marching

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

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

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

Update: См. также этот комментарий от DrZlodberg о недостатках этого метода.

Принцип работы движка

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

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

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

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

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

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

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

Давайте параметризуем луч по расстоянию от его начала функцией .
Тогда — это сама камера. Вот алгоритм:

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

Почему алгоритм работает

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

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

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

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

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

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

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

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

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

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

Нарисуем чертеж. Обозначим и — точки, полученные на соседних итерациях алгоритма. Предположим, что точки находятся достаточно близко к объекту, что его можно заменить на плоскость, угол с которой мы хотим найти. Пусть , — расстояния от точек и до плоскости. Тогда, согласно алгоритму, расстояние между и равно .

С другой стороны, если обозначить — точку пересечения луча и фигуры, то
, а , следовательно

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

Описываем простые фигуры

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

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

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

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

Это малая часть того, что можно делать при помощи SDF, полный список фигур и операций можно найти на странице www.iquilezles.org/www/articles/distfunctions/distfunctions.htm

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

Формула чайника

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

Аккуратно записываем формулу:

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

Камера

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

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

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

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

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

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

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

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

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

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

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

Далее, применяя матрицу поворота к векторам и , получаем вектора и , задающие горизонтальные и вертикальные направления экрана (для упрощения расчетов они также предварительно домножены на ):

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

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

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

Excel

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

Тот движок подходит только для рендера лабиринтов и эллипсоидов. Используется одномерный Raycaster, из данных которого вверх и вниз рисуются полосы, создающие иллюзию стен. Но зато там реализована полноценная игровая логика, здесь же целью является только трехмерный движок.

Источник