Как состыковать узоры на сторонах 3D-объекта?

Question

[низкомолекулярный макрос]

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

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



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

Мне бы хотелось знать, какие есть подходы к реализации такой задачи? Какие существуют алгоритмы? Что почитать/посмотреть на эту тему?

Answer 1

[Wataru]

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

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

Алгоритм генерации лабиринта, как у вас на картинке: у вас есть граф, вершины - точки на решотке, а ребра - линии между соседними. Вы добавляете случайные ребра, которые не создают циклов в графе.

Доя этого используйте структуру данных непересекающиеся множества (disjoint set union). При добавлении ребра объединяйте два множества. Ребро можно добавить, только если оно между разными множествами. Вместо выбора случайного ребра - советую взять массив всех ребер и случайно перемешать его. Потом в таком порядке добавлять ребра, если можно.

Второй способ с выпрямлением имеет точно такой же алгоритм генерации лабиринта, но там решотка уже не прямоуголная, а на основе ромбов. Надо только порисовать и аккуратно ввести систему координат и понять формулы, какие координаты у 4 соседних точек в решотке и какие точки относятся к какой грани. А потом опять DSU и случайные ребра.

Comments

[низкомолекулярный макрос]

звучит так сложно, что не хочется и браться за реализацию((( спасибо за ответ

[Wataru]

низкомолекулярный макрос, Ой да ладно

DSU реализуется за 10 строчек. Можно скопировать отсюда или отсюда

Дальше надо аккуратно нарисовать вашу картинку, ввести систему координат, занумеровать все точки и сгенерировтаь список всех пар соседей.

На самом деле тут будет решетка на основе шестиукгольников, но можно и проще. Можно ввести обычную прямоугольную систему координат, только трехмерную. Путь (0,0,0) - это точка за этой фигурой в ее невидимом углу. В центре, где пересекутся 3 плоскости границы фигуры.

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

Точка в вершине - имеет все координаты делящиеся на n (если длина куба - n). Дальше есть три варианта. У точки или 3 соседа с +1 по каждой координате (если она вогнутый угол). Или 3 соседа с -1 по каждой координате (если она выпуклый угол), или все 6 соседей. Понять, какой там из трех случаев можно, если посмотреть на сумму трех координат. Она равна 0 для nk для вогнутых углов, n(k+2) для выпуклых и n(k+1) для вогнутых.

Точка на границе - ровно 2 координаты, делящиеся на n. У нее 2 соседа на +1 и -1 вдоль третьей координаты. И 2 соседа на +1 или -1 по одной из оставшихся координат. Опять же, в какую сторону можно поять через четность (x+y)/n (если x и y делятся на n).

Ну и точка на грани имеет ровно одну координату делящуюся на n. У нее 4 соседа +1 или -1 вдоль оставшихся двух координат.

Еще надо рассмотреть случай границ - но тут все просто. Вам надо лишь запретить точки с отрицательными координатами. Ну и понимать, а лежит ли точка с заданными координатами на фигуре. Тут тоже все просто - у нее сумма координат между nk и n(k+2) включительно.

[низкомолекулярный макрос]

Wataru, спасибо вам большое за такие развернутые ответы)))

Answer 2

[Alexandroppolus]

Взять обычный алгоритм генерации клеточного лабиринта, например, https://habr.com/ru/post/321210/
Только у тебя будет дополнительное условие - крайние клетки грани считаются смежными с крайними клетками соседней грани.