Процедурная генерация трёхмерных моделей
Процедурная генерация — замечательная штука! Интереснее всего работать именно с графикой, особенно трёхмерной — сразу видно результат. Всего пары инструкций достаточно, чтобы создать облако треугольников как на картинке выше.
Процедурная генерация моделей может помочь сэкономить размер дистрибутива, добавить кастомизацию игровых персонажей, на худой конец её просто можно использовать для создания спецэффектов.
На примере движка Unity и C# я покажу как можно работать с моделями и превращать текст в графику. Большинство приводимого кода легко портируется на другие фреймфорки и языки.
Треугольник
Начнём с простейшей формы — треугольника. В Unity и во многих других движках используется популярный способ описания моделей: с помощью массивов вершин, треугольников и нормалей. Дополнительно для текстурирования используются uv-координаты вершин. Для работы с моделями есть класс Mesh, в котором для каждого набора данных имеется отдельный массив. В Mesh.vertices хранятся координаты вершин, в Mesh.triangles — индексы вершин группами по три. А в Mesh.normals и Mesh.uv лежат векторы нормалей и координаты uv-карт, индексы которых должны совпадать с индексами соответствующих вершин, т. е. порядок в массивах должен быть одинаковым. Покажу на примере, чтобы было понятнее.
Сделаем функцию, которая на вход принимает три вершины треугольника, а отдаёт готовую модельку. Начнём с основы.
Упаковываем три вершины в массив и передаём мешу. Треугольник описывается элементарно, но есть нюанс, про который нужно помнить. Если смотреть на модель снаружи, то вершины её треугольников должны располагаться по часовой стрелке. Это сделано для того, чтобы во время отрисовки можно было отсечь треугольники, которые «не смотрят в камеру», и обрабатывать их отдельно. Порядок вершин рассчитывается очень просто, поэтому такой способ фильтрации очень эффективен. Если взять произведение двух векторов, то можно найти третий вектор, перпендикулярный плоскости, образуемой сомножителями. Если пробежаться по треугольнику и посчитать произведения, то можно узнать порядок вершин. Кстати эти перпендикулярные вектора нам тоже нужны для описания моделей — это ведь нормали. Нормаль считается следующим образом:
Сначала сделали из трёх точек два вектора, а потом перемножили. Эта нормаль будет одинаковой на всех вершинах треугольника.
Осталось добавить uv-координаты, для трёх вершин это просто.
Ну и всё, треугольник готов. Теперь его можно использовать.
Четырёхугольник
Помимо треугольников есть ещё один популярный примитив для моделирования — четырёхугольник, ну или квад, если вам так больше нравится.
Описать четырёхугольник капельку сложнее, нужно добавить одну вершину с её характеристиками и дополнительный треугольник. Я немного изменил входные параметры по сравнению с треугольником, теперь нужно указывать левый нижний угол и две стороны, с настоящими квадами Mesh в Unity всё равно не работает.
Напоминаю, что вершины по-прежнему записываются по часовой стрелке.
Теперь, когда мы имеем два базовых примитива, мы можем собрать любую модель.
Плоскость
Поэкспериментируем со сборкой моделей на примере плоскости. Возьмём много квадратов и разложим стык в стык.
Лень — двигатель прогресса, поэтому для сборки квадратов в модель будем использовать Mesh.CombineMeshes. Этот метод принимает на вход структуру CombineInstance, в которой можно указать модельку, её индекс и матрицу трансформирования. Для нас важно только первое, остальное игнорируем.
На вход метода подаётся стартовая позиция плоскости, ширина и длина сегмента, количество сегментов. В двойном цикле все квадраты складываются в массив CombineInstance, после чего массив собирается в готовую модель.
Параллелепипед
Раскладывать плитки по плоскости слишком просто, пора перейти к третьему измерению.
Из квадратов хорошо получаются кубы. Даже лучше, с помощью наших псевдоквадов можно делать не только кубы, но и параллелепипеды. Только тссс! Никому не говорите.
Нужно всего шесть четырёхугольников. Зная длину, ширину и высоту параллелепипеда, можно рассчитать все его вершины. Удобно сначала найти два противоположных угла параллелепипеда, а потом от них отстраивать всё остальное. Также имеет смысл отцентрировать модель. Как это выглядит на практике можете посмотреть ниже.
Октаэдр
Октаэдр во многом похож на куб, его вершины очень легко рассчитать, самая большая сложность — сообразить порядок вершин в треугольниках. Октаэдр вписывается в сферу, поэтому имеет смысл строить его по радиусу этой сферы. Все вершины элементарно создаются, так что я не буду здесь останавливаться
Хотя есть ещё один момент. До сих пор многие из вершин в наших моделях дублировались, хотя, как вы возможно слышали, при создании моделей наоборот всегда стараются сократить число вершин и треугольников. Почему же с кубом и октаэдром не так? Покажу на примере, вот код сборки октаэдра с минимально необходимым числом вершин:
В конце я применил Mesh.RecalculateNormals, который автоматически считает нормали, так проще.
Посмотрите на разницу в освещении между двумя октаэдрами на соседней картинке. В первом случае шэйдеру приходится интерполировать между нормалями, смотрящими совсем в разные стороны, поэтому освещение получается нереалистичным. А во втором случае все грани острые, чёткие. Общие нормали подходят для сфер, гладких поверхностей или если необходимо скрыть малое количество полигонов. А для нашего случая вершин нужно больше.
Тетраэдр
Теперь можно взяться за фигуры поинтереснее. Расчёт вершин даже для простого тетраэдра требует потребует пятёрки по школьной геометрии, поэтому сразу предупреждаю, если не помните что на что делится в синусе, то лучше сначала заглянуть в учебник, как это пришлось сделать мне.
Освежили память? Продолжим.
Пусть наш тетраэдр стоит на одной из граней, тогда противоположную вершину можно добавить сразу:
Остальные вершины должны образовывать равносторонний треугольник. Их координаты можно найти с помощью синусов и косинусов. В Unity есть функции Mathf.Sin и Mathf.Cos, которые ведут расчёт в радианах. Делим окружность на три части и находим на ней три точки:
Из этих вершин уже можно собрать пирамидку, но это не будет тетраэдром, потому что у настоящего тетраэдра все грани одинаковые. Для настоящего тетраэдра основание пирамиды нужно немного уменьшить и сдвинуть ниже. Тут опять пригодятся синусы и косинусы, но чтобы ими воспользоваться, немного смухлюем и подсмотрим один угол в Википедии. «Edge central angle» это угол между радиусами описанной сферы, пересекающими вершины тетраэдра. Кхм, или что-то в этом роде, я успел запутаться пока формулировал мысль. В общем присовокупив этот угол получаем следующий код:
Не так уж и сложно, надеюсь, что все всё поняли. Вот так выглядит всё в итоге, с добавлением масштабирования:
А вот тот же тетраэдр без математики, с захардкоденными вершинами, почувствуйте разницу:
Икосаэдр
Напоследок самое вкусное — икосаэдр. Если выровнять икосаэдр и посмотреть на него под правильным углом, то можно заметить, что две его вершины лежат на одной оси друг под другом, а остальные расположены на двух окружностях.
На каждой окружности их по пять штук, а значит интервал между ними 72 градуса. Смещение между окружностями — 36 градусов. Для выравнивания вершин нам опять понадобится волшебный угол из Википедии: «If two vertices are taken to be at the north and south poles (latitude ±90°), then the other ten vertices are at latitude ±arctan(1/2) ≈ ±26.57°». В переводе на русский это означает, что волшебный угол — арктангенс одной второй.
В конечном итоге всё похоже на тетраэдр, просто окружностей две и немного сложнее сцепка вершин. Сразу добавляем две вершины, считаем одну половинку, затем другую. Собираем в треугольники четырьмя порциями.
Заключение
Если вы внимательно читали код в статье, то наверняка заметили, что там много ненужных вычислений, тот же Mathf.Cos(magicAngle) из примера выше. При желании его можно посчитать только один раз и занести в переменную, это будет не так наглядно и понятно зато быстрее.
Кроме того в генерируемых моделях не самые удобные uv-карты, было бы неплохо их исправить, но для этого придётся переделывать очень много кода, пока и так сойдёт.
А где же сферы и цилиндры? – спросите вы. Редактор статей на Хабрахабре, конечно, замечательный, но навигация по большим объёмам текста в нём не очень удобная, так что оставлю сферы на следующий раз.
Исходники и бинарники для разных платформ можете скачать по ссылкам ниже.
Программа для рисования четырёхмерного куба
Начнём с объяснения, что же такое четырёхмерное пространство.
Это — одномерное пространство, то есть просто ось OX. Любая точка на ней характеризуется одной координатой.
Теперь проведём ось OY перпендикулярно оси OX. Вот и получилось двумерное пространство, то есть плоскость XOY. Любая точка на ней характеризуется двумя координатами — абсциссой и ординатой.
Проведём ось OZ перпендикулярно осям OX и OY. Получится трёхмерное пространство, в котором у любой точки есть абсцисса, ордината и аппликата.
Логично, что четвёртая ось, OQ, должна быть перпендикулярной осям OX, OY и OZ одновременно. Но мы не можем точно построить такую ось, и потому остаётся только попытаться представить её себе. У каждой точки в четырёхмерном пространстве есть четыре координаты: x, y, z и q.
Теперь посмотрим, как появился четырёхмерный куб.
На картинке изображена фигура одномерного пространства — линия.
Если сделать параллельный перенос этой линии вдоль оси OY, а потом соединить соответствующие концы двух получившихся линий, получится квадрат.
Аналогично, если сделать параллельный перенос квадрата вдоль оси OZ и соединить соответствующие вершины, то получится куб.
А если сделать параллельный перенос куба вдоль оси OQ и соединить вершины двух этих кубов, то мы получим четырёхмерный куб. Кстати, он называется тессеракт.
Чтобы нарисовать куб на плоскости, нужно его спроецировать. Наглядно это выглядит так: 
Представим, что в воздухе над поверхностью висит каркасная модель куба, то есть как бы «сделанная из проволоки», а над ней — лампочка. Если включить лампочку, обвести карандашом тень от куба, а потом выключить лампочку, то на поверхности будет изображена проекция куба.
Перейдём к немного более сложному. Ещё раз посмотрите на рисунок с лампочкой: как видите, все лучи сошлись в одной точке. Она называется точкой схода и используется для построения перспективной проекции( а бывает и параллельная, когда все лучи параллельны друг другу. Результат — не создаётся ощущения объёма, но она легче, и при том если точка схода достаточно сильно удалена от проецируемого объекта, то разница между этими двумя проекциями мало заметна). Чтобы спроецировать данную точку на данную плоскость, используя точку схода, нужно провести прямую через точку схода и данную точку, а потом найти точку пересечения получившейся прямой и плоскости. А для того, чтобы спроецировать более сложную фигуру, скажем, куб, нужно спроецировать каждую его вершину, а потом соответствующие точки соединить. Следует заметить, что алгоритм проекции пространства на подпространство можно обобщить для случая 4D->3D, а не только 3D->2D.
Как я уже говорил, мы не можем себе точно представить, как выглядит ось OQ, равно как и тессеракт. Зато мы можем получить ограниченное представление о нём, если мы спроецируем его на объём, а потом нарисуем это на экране компьютера!
Теперь поговорим о проекции тессеракта.
Слева находится проекция куба на плоскость, а справа — тессеракта на объём. Они довольно схожи: проекция куба выглядит как два квадрата, маленький и большой, один внутри другого, и у которых соответствующие вершины соединены линиями. А проекция тессеракта выглядит как два куба, маленький и большой, один внутри другого, и у которых соответствующие вершины соединены. Но мы все видели куб, и можем с уверенностью сказать, что и маленький квадрат, и большой, и четыре трапеции сверху, снизу, справа и слева от маленького квадрата, на самом деле являются квадратами, при чём равными. И у тессеракта тоже самое. И большой куб, и маленький куб, и шесть усечённых пирамид по бокам от маленького куба — это всё кубы, при чём равные.
Моя программа умеет не только рисовать проекцию тессеракта на объём, а ещё и вращать его. Рассмотрим, как делается это.
Для начала я вам расскажу, что такое вращение параллельно плоскости.
Представьте себе, что куб вращается вокруг оси OZ. Тогда каждая из его вершин описывает окружность вокруг оси OZ. 
А окружность — фигура плоская. И плоскости каждой из этих окружностей параллельны между собой, и в данном случае параллельны плоскости XOY. То есть мы можем говорить не только о вращении вокруг оси OZ, а ещё и о вращении параллельно плоскости XOY.Как видим, у точек, которые вращаются параллельно оси XOY меняются только абсцисса и ордината, аппликата же остаётся неизменной И, вообще-то, мы можем говорить о вращении вокруг прямой только тогда, когда имеем дело с трёхмерным пространством. В двумерном всё вращается вокруг точки, в четырёхмерном — вокруг плоскости, в пятимерном пространстве мы говорим о вращении вокруг объёма. И если вращение вокруг точки мы можем себе представить, то вращение вокруг плоскости и объёма — что-то немыслимое. А если будем говорить о вращении параллельно плоскости, то тогда в любом n-мерном пространстве точка может вращаться параллельно плоскости.
Многие из вас, вероятно, слышали о матрице поворота. Умножив точку на неё, получим точку, повёрнутую параллельно плоскости на угол фи. Для двумерного пространства она выглядит так: 
Как умножать: икс точки, повёрнутой на угол фи = косинус угла фи*икс первоначальной точки минус синус угла фи*игрек первоначальной точки;
игрек точки, повёрнутой на угол фи=синус угла фи*икс первоначальной точки плюс косинус угла фи*игрек первоначальной точки.
Xa`=cosф*Xa — sinф*Ya
Ya`=sinф*Xa + cosф*Ya
, где Xa и Ya — абсцисса и ордината точки, которую нужно повернуть, Xa` и Ya` — абсцисса и ордината уже повёрнутой точки
Для трёхмерного пространства это матрица обобщается следующим образом: 
Вращение параллельно плоскости XOY. Как видим, координата Z не меняется, а меняются только X и Y
Xa`=cosф*Xa — sinф*Ya + Za*0
Ya`=sinф*Xa +cosф*Ya + Za*0
Za`=Xa*0 + Ya*0 + Za*1 (по сути, Za`=Za)
Вращение параллельно плоскости XOZ. Ничего нового,
Xa`=cosф*Xa + Ya*0 — sinф*Za
Ya`=Xa*0 + Ya*1 + Za*0 (по сути, Ya`=Ya)
Za`=sinф*Xa + Ya*0 + cosф*Za
И третья матрица.
Xa`=Xa*1 + Ya*0 + Za*0 (по сути, Xa`=Xa)
Ya`=Xa*0 + cosф*Ya — sinф*Za
Za`=Xa*0 + sinф*Ya + cosф*Za
А для четвёртого измерения они выглядят вот так: 
Думаю, вы уже поняли, что на что множить, потому лишний раз расписывать не буду. Зато замечу, что она делает то же самое, что и матрица для поворота параллельно плоскости в трёхмерном пространстве! И та, и эта изменяют только ординату и аппликату, а остальные координаты не трогают, потому её можно использовать и в трёхмерном случае, просто не обращая внимания на четвёртую координату.
А вот с формулой проекции не всё так просто. Сколько я ни читал форумов, мне не подошёл ни один из способов проекции. Параллельная мне не подходила, так как проекция не будет выглядеть объёмной. В одних формулах проекции для нахождения точки нужно решить систему уравнений( а я не знаю, как научить компьютер их решать), другие я просто-напросто не понял… В общем, я решил придумать свой способ. Рассмотрим для этого проекцию 2D->1D.
pov значит «Point of view» (точка зрения), ptp значит «Point to project» (точка, которую нужно спроецировать), а ptp` — это искомая точка на оси OX.
Углы povptpB и ptpptp`A равны как соответствующие( пунктирная линия параллельна оси OX, прямая povptp — секущая).
Икс точки ptp` равен иксу точки ptp минус длина отрезка ptp`A. Этот отрезок можно найти из треугольника ptpptp`A: ptp`A = ptpA/тангенс угла ptpptp`A. Мы можем найти этот тангенс из треугольника povptpB: тангенс угла ptpptp`A = (Ypov-Yptp)(Xpov-Xptp).
Ответ: Xptp`=Xptp-Yptp/тангенс угла ptpptp`A.
Я не стал подробно расписывать этот алгоритм тут, так как там куча частных случаев, когда формула несколько меняется. Кому это интересно — посмотрите в исходниках программы, там всё расписано в комментариях.
Для того, чтобы спроецировать точку трёхмерного пространства на плоскость, просто рассмотрим две плоскости — XOZ и YOZ, и для каждой из них решим эту задачу. В случае четырёхмерного пространства нужно рассмотреть уже три плоскости: XOQ, YOQ и ZOQ.
И наконец, про программу. Она действует так: инициализировать шестнадцать вершин тессеракта -> в зависимости от введённых пользователем команд повернуть его -> спроецировать на объём -> в зависимости от введённых пользователем команд повернуть его проекцию -> спроецировать на плоскость -> нарисовать.
Проекции и повороты я написал сам. Они работают по формулам, которые я только что описал. Библиотека OpenGL рисует линии, а так же занимается смешиванием цветов. А координаты вершин тессеракта вычисляются таким образом:
Координаты вершин линии с центром в начале координат и длинной 2 — (1) и (-1);
— » — » — квадрата — » — » — и ребром длинной 2:
( 1; 1 ), ( -1; 1), (1; -1) и (-1; -1);
— » — » — куба — » — » -:
( 1; 1; 1 ), ( -1; 1; 1), (1; -1; 1), (-1; -1; 1), ( 1; 1; -1 ), ( -1; 1; -1), (1; -1; -1), (-1; -1; -1);
Как можно было заметить, квадрат — это одна линия над осью OY и одна линия под осью OY; куб — это один квадрат спереди от плоскости XOY, и один за ней; тессеракт — это один куб по ту сторону объёма XOYZ, и один — по эту. Но куда легче воспринять это чередование единиц и минус единиц, если их записать в столбик
1; 1; 1
-1; 1; 1
1; -1; 1
-1; -1; 1
1; 1; -1
-1; 1; -1
1; -1; -1
-1; -1; -1
В первом столбце один и минус один чередуются. Во втором столбце сначала идёт два плюса, потом два минуса. В третьем — четыре плюс единицы, а потом четыре минус единицы. Это были вершины куба. У тессеракта их в два раза больше, и потому нужно было написать цикл для их объявления, иначе очень легко запутаться.
Моя программа так же умеет рисовать анаглиф. Счастливые обладатели 3D-очков могут наблюдать стереоскопическую картинку. В рисовании картинки нет ничего хитрого, просто рисуется две проекции на плоскость, для правого и левого глаз. Зато программа становится намного более наглядной и интересной, а главное — даёт лучшее представление о четырёхмерном мире.
Менее значительные функции — подсветка одной из граней красным, чтобы лучше можно было разглядеть повороты, а так же мелкие удобства — регуляция координат точек-«глаз», увеличение и уменьшение скорости поворота.