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

Все вычисления я выполнил в своём коде на github, однако стоит объяснить, как и зачем нужно использовать такие сетки.

Что такое «сетка треугольников»

Когда я говорю о сетке треугольников, то подразумеваю тайловую карту, в которой все тайлы являются одинаковыми равносторонними треугольниками, выстроенными в переменные строки (или столбцы).


Важно здесь то, что каждая ячейка имеет ровно трёх соседей. Иногда встречаются игры, где отрисована сетка треугольников, но на самом деле фигуры расположены в углах. Каждый угол соединяется с шестью другими, то есть на самом деле это сетка не треугольников, а шестиугольников.


В китайские шашки (Халма) играют на сетке шестиугольников, стилизованной на фотографии под сетку треугольников.

И наоборот: если в игру играют на углах сетки шестиугольников, то на самом деле это сетка треугольников. Из-за этого свойства равномерные сетки шестиугольников и треугольников называют двойными.

Зачем использовать сетки треугольников

Треугольники обладают тремя потрясающими свойствами:

1. Они всегда планарны
2. Они просты
3. Их геометрия более удобна

Планарность

Если выбрать любые три точки в трёхмерном пространстве, то через них всегда можно прочертить плоскость. То есть имея эти три точки, всегда можно нарисовать треугольник на поверхности этой плоскости. Для многоугольников с большим количеством вершин это не всегда верно. Если взять четыре 3D-вершины, то соединить их в многоугольник с четырьмя вершинами однозначным образом становится сложно. Страдающие подобной проблемой многоугольники называются непланарными, и в компьютерной графике они могут становиться серьёзной помехой, поэтому почти вся графика реального времени преобразует все объекты в треугольники.

Даже несмотря на то, что мы будем говорить о заполнении 2D-пространства, это свойство всё равно для нас полезно на случай, если мы захотим добавить карту высот. В сетке треугольников каждая вершина может располагаться на своей высоте, но в сетке не будет возникать проблем. Если проделать подобное с сеткой квадратов, то мы сразу же столкнёмся с появлением непланарных вершин.


В Sim City 2000 использовались сетки квадратов и карты высот. Обратите внимание, что многие наклонные тайлы разделены на пары треугольников, потому что тайл непланарен.


Карта высот сетки треугольников. Никаких проблем с наклонами.

Простота

Математически понятно, что 3 меньше, чем 4 или 6. Это наименьшее количество вершин, которое может иметь многоугольник, поэтому треугольники — самая лучшая фигура для любого алгоритма, масштабирующегося в зависимости от количества точек или рёбер.

Например, в своём туториале по Marching Cubes я говорил, что для учёта всех случаев в 2D требуется создать различных тайлов. Так получается потому, что у каждого из четырёх углов есть два варианта. Треугольники имеют два варианта: смотрящий вверх и вниз, то есть для двух вариантов требуется по разных тайлов. То есть в обоих случаях получаем 16 тайлов.


Обратите внимание, что для треугольников нет «противоречивых» случаев.

Но это самый простой случай. Если мы допускаем возможность поворота тайлов, то вариантов у треугольников становится меньше (4 против 6). А если нам нужно больше чем два возможных значения в каждом из углов (54 против 81 или 10 против 21 с поворотами/отражениями).


Поворачиваемые тайлы, необходимые для marching cubes

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

Геометрия лучше, чем у шестиугольников

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

В следующем разделе мы активно будем использовать прямые линии рёбер для понимания того, как работают сетки треугольников.

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

Как использовать сетки треугольников

Примечание: в данном туториале в основном рассматриваются концепции и идеи, а не методы и код. Если вам интереснее реализация, то изучите написанную мной справочную реализацию.

Для начала нужно сказать, что существует множество способов работы с сетками треугольников. В этом разделе я опишу тот, который считаю лучшим — его легко понять и он имеет простые выражения практически для всех действий, которые вам понадобятся для работы с треугольниками. Я буду описывать треугольники, выстроенные в строки (треугольники «смотрящие» вверх и вниз), но для сеток, повёрнутых на 90 градусов, всё будет устроено так же.

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


Пространство между каждой из этих параллельных линий называется полосами. Мы обозначим три направления полос как a, b и c, а сами полосы пронумеруем по порядку.


Тогда координатой треугольника будут три целых числа a, b, c, определяющие, в каких полосах находится треугольник. Всё очень просто!


Вероятно, вы зададитесь вопросом, почему мы используем три числа для описания ячейки в 2d-сетке. Просто так нам будет удобнее работать. Если попробовать использовать систему координат из двух чисел, то в конечном итоге придётся добавлять больше исключений для чётных и нечётных координат, или других аспектов. Похожий трюк используется и при работе с сетками шестиугольников, см. эту статью о «кубических» координатах сеток шестиугольников. Впрочем, третья координата практически избыточна — в этой системе сумма a + b + c всегда равна или 1, или 2. Поэтому можно просто хранить a, b и c в дополнительной булевой переменной.

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

Соседи

Когда мы переходим с одного треугольника на другой, то пересекаем одну из линий, разделяющих полосы. Я создал такую систему, что при перемещении из треугольника, указывающего вершиной вниз, мы прибавляем к координате единицу. А при выходе из треугольника вершиной вверх — вычитаем единицу.

def tri_neighbours(a, b, c):
    """Returns the tris that share an edge with the given tri"""
    points_up = a + b + c == 2
    if points_up:
        return [
            (a - 1, b    , c    ),
            (a    , b - 1, c    ),
            (a    , b    , c - 1),
        ]
    else:
        return [
            (a + 1, b    , c    ),
            (a    , b + 1, c    ),
            (a    , b    , c + 1),
        ]

Центр треугольника

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

def tri_center(a, b, c):
    """Returns the center of a given triangle in cartesian co-ordinates"""
    return ((       0.5 * a +                      -0.5 * c) * edge_length,
            (-sqrt3 / 6 * a + sqrt3 / 3 * b - sqrt3 / 6 * c) * edge_length)

Расстояние между треугольниками

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

def tri_dist(a1, b1, c1, a2, b2, c2):
    """Returns how many steps one tri is from another"""
    return abs(a1 - a2) + abs(b1 - b2) + abs(c1 - c2)

В следующей статье я рассмотрю альтернативную функцию расстояния.

В каком треугольнике находится точка

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

def pick_tri(x, y):
    """Returns the triangle that contains a given cartesian co-ordinate point"""
    return (
        ceil(( 1 * x - sqrt3 / 3 * y) / edge_length),
        floor((    sqrt3 * 2 / 3 * y) / edge_length) + 1,
        ceil((-1 * x - sqrt3 / 3 * y) / edge_length),
    )

ceil округляет число вверх до ближайшего целого, а floor округляет вниз. Нельзя просто округлить все три полосы в одном направлении, иначе возникнут сложности, например, с точкой с координатой (0, 0), которая находится в углу шести разных треугольников.

Другие операции

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

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

Надеюсь, я убедил вас, что сетки треугольников — недооценённый инструмент.


Процедурная генерация сетки треугольников, выполненная Tessera

Дополнительные материалы

В моей следующей статье рассказывается о расширенных возможностях сеток треугольников.

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

Также могу порекомендовать вам статью Джастина Помбрио о преобразовании из пикселей в шестиугольники, из которой я узнал, как удобно работает система треугольников и как она связана с сетками шестиугольников.