Поговорим о сетках треугольников. Сетки квадратов используются практически повсюду, от пикселей изображения до расположения домов в квартале. Сетки шестиугольников представлены тоже довольно широко, особенно в настольных играх. Однако сетки треугольников (равномерное заполнение 2D-плоскости равносторонними треугольниками) почему-то не очень популярны. Я встречал заявления, что они бесполезны, или что у них сложная математика. Но этой статьёй я докажу, что оба заявления ошибочны: вычисления на самом деле проще, чем при работе с шестиугольниками, к тому же треугольники обладают множеством преимуществ.
Все вычисления я выполнил в своём коде на github, однако стоит объяснить, как и зачем нужно использовать такие сетки.
Что такое «сетка треугольников»
Когда я говорю о сетке треугольников, то подразумеваю тайловую карту, в которой все тайлы являются одинаковыми равносторонними треугольниками, выстроенными в переменные строки (или столбцы).
Важно здесь то, что каждая ячейка имеет ровно трёх соседей. Иногда встречаются игры, где отрисована сетка треугольников, но на самом деле фигуры расположены в углах. Каждый угол соединяется с шестью другими, то есть на самом деле это сетка не треугольников, а шестиугольников.
В китайские шашки (Халма) играют на сетке шестиугольников, стилизованной на фотографии под сетку треугольников.
И наоборот: если в игру играют на углах сетки шестиугольников, то на самом деле это сетка треугольников. Из-за этого свойства равномерные сетки шестиугольников и треугольников называют двойными.
Зачем использовать сетки треугольников
Треугольники обладают тремя потрясающими свойствами:
- Они всегда планарны
- Они просты
- Их геометрия более удобна
Планарность
Если выбрать любые три точки в трёхмерном пространстве, то через них всегда можно прочертить плоскость. То есть имея эти три точки, всегда можно нарисовать треугольник на поверхности этой плоскости. Для многоугольников с большим количеством вершин это не всегда верно. Если взять четыре 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 о сетках по-прежнему остаётся лучшим ресурсом для изучения сеток. Я слышал, что он работает над обновлённой версией.
Также могу порекомендовать вам статью Джастина Помбрио о преобразовании из пикселей в шестиугольники, из которой я узнал, как удобно работает система треугольников и как она связана с сетками шестиугольников.
