Моя последняя игра будет проходить на небольшом планетоиде. Я ищу хорошую структуру данных для представления ячеек на поверхности сферы. Треугольники, квадраты, пятиугольники, шестиугольники? Какой из них минимизирует растяжку и создает наилучшую плитку?
Сферическое отображение является самым простым, но растяжение на полюсах недопустимо. Cubemapping также довольно легко, но все еще будет значительное растяжение вблизи углов куба. Подразделение икосаэдра кажется лучшим с точки зрения растяжения, но существует проблема индексации многих треугольных массивов, и было бы трудно найти соседние ячейки на границах.
Думаю, я мог бы использовать один линейный массив точек, представляющих N-угольники, каждая из которых имеет массив из N индексов соседей, но это кажется огромной тратой пространства.
В игре есть элементы RTS, поэтому я буду хранить такие вещи, как карты влияния и выполнение A * поиска пути и свертки, поэтому представление должно быть эффективным.
Ответы:
Хорошо, для тех, кто интересуется этой темой, я сейчас подробно опишу решение, которое я выбрал. Спасибо всем, кто ответил и дал мне идеи.
Во-первых, для «лучшего» тесселяции я выберу усеченный икосаэдр в качестве отправной точки. Подразделение приводит к очень хорошему тесселяции шестиугольников с 12 пятиугольниками, обеспечивающими кривизну. Кроме того, продолжение подразделения на его двойном даст мне очень хорошую треугольную сетку для рендеринга с хорошими свойствами. Что касается 12 пятиугольных ячеек: я могу их игнорировать, делать их особенными (например, единственные места, где можно строить базы), или я могу скрывать их под декорациями.
Шестиугольные и пятиугольные ячейки будут храниться в структуре данных с половинным краем для легкого доступа к соседям и быстрого обхода. Единственная сложность - найти ячейку, в которой находится данная точка мира, но это можно сделать, начав со случайной ячейки и пройдя к этой точке через соседей.
Я надеюсь, что кто-то найдет эту информацию полезной. Я многому научился и с нетерпением жду результатов.
Редактировать:
Вот изображение, показывающее результат моего подразделения икосаэдра и переключения двойной сетки с использованием структуры данных с половинным краем.
Я могу сделать несколько итераций расслабления, чтобы сделать области клеток еще более однородными.
источник
Есть способ сделать это довольно изящно, основанный на подразделении икосаэдра, как вы предложили в своем вопросе. Икосаэдр состоит из 20 равносторонних треугольников, и эти треугольники можно сгруппировать в 5 наборов, где 4 треугольника в наборе образуют форму параллелограмма:
(Группы из четырех треугольников с волнистой линией, проведенной через них, являются параллелограммами, о которых я говорю. Стрелки указывают, какие края будут склеены, чтобы сложить их в икосаэдр.)
Если эти треугольники подразделяются на более мелкие треугольники, весь параллелограмм можно индексировать, как прямоугольный массив n на 4n (в данном примере n = 4):
Числа в каждой ячейке являются номерами столбцов прямоугольного массива. Правила поиска соседей в массиве довольно просты: горизонтальные соседи - это столбец плюс или минус 1, а вертикальный сосед - либо минус одна строка и плюс один столбец, либо плюс одна строка и минус один столбец, в зависимости от того, Номер столбца является четным или нечетным, соответственно.
Тем не менее, вам все равно придется написать специальный код для поиска соседей, которые пересекают границу от одного параллелограмма к следующему. Это немного сложно, так как в некоторых местах верх или низ одного параллелограмма будет связан со стороной другого, или верх и низ будут связаны с горизонтальным смещением между ними и т. Д. Возможно, структура с половиной края или подобное для параллелограммов было бы здесь полезно. Тем не менее, по крайней мере, отношения являются симметричными среди всех 5 параллелограммов: все они следуют той же схеме, в которой сторона связана с другой стороной своих соседей.
источник
Хммм - комментарии о растяжении указывают на то, что вы перемещаетесь между сферическим и планарным отображением, вот что приводит к искажениям на полюсах
Если вы хотите, чтобы плитки были плоскими и однородными, вы правы в том, что икосаэдр, в частности усеченный икосаэдр, довольно распространен
Вы можете найти все различные отображения здесь - Сферические многогранники в Википедии.
Что касается поддержания отношений между гранями, это проблема топологии - вам может пригодиться крылатый край или четырехугольный край (и вы получите прекрасную возможность познакомиться с совершенно новой формой алгебры) Winged Edge
источник
Думаю, я немного опаздываю на вечеринку, но вот возможное решение, которое можно использовать для поддержания сферического мира произвольных размеров и однородного внешнего вида.
Главное, что здесь необходимо понять, это то, что мир не плоский, и поэтому 100% равномерное разбиение будет невозможно (это следует из так называемой теоремы о волосатых шариках ). Необходимо допустить некоторые неровности, и лучшее, на что мы могли бы надеяться, это равномерное распределение этих неровностей по поверхности, делая каждое из них как можно меньшим.
Это на самом деле довольно легко сделать недетерминированным способом. Сначала выберите N случайных точек равномерно вокруг поверхности. Удостоверьтесь, что эти точки фактически одинаковы (см. Выбор точек сферы , формулы 9-11). На втором этапе мы делаем эти точки менее случайными и более однородными: предположим, что все эти точки имеют отрицательный электрический заряд, чтобы они отталкивали друг друга. Смоделируйте движение точек за несколько шагов, пока они не сойдутся в состояние равновесия. Эта окончательная конфигурация точек даст вам сетку, которая почти равномерно распределена по поверхности сферы.
источник