Кто-нибудь знает, где я мог бы найти алгоритм или иметь алгоритм, которым они могли бы поделиться, чтобы разделить сферу (меш) на случайные части?

Question

У меня есть список вершин и список треугольников.Я хотел бы разделить эту одиночную сетку на, скажем, 5 мешей произвольной формы.Когда 5 ячеек произвольной формы находятся на месте, сфера должна выстроиться в линию и выглядеть как 1 сплошная сетка.

Мне нужен алгоритм, чтобы делать это программно, а не инструмент, который формирует меня.Любые указатели были бы великолепны!

Answer 1

Аналогично предложению Сванте, но немного другой подход:

1. Выберите пять случайных вершин, отметьте эти вершины как "посещенные" с числом от 1 до 5
2. Из каждой посещенной вершины перейдите ко всем смежным вершинам. Храните там же номер.
3. Если вы посещаете вершину, которой уже присвоен номер, остановитесь там
4. Стоп, если все вершины посещены. Все вершины, отмеченные одним и тем же номером, заканчиваются одним и тем же фрагментом

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

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

Answer 2

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

Answer 3

Когда вы разбиваете треугольник вдоль плоскости, вы попадаете в одну из двух ситуаций: либо плоскость не пересекает отрезки линии в треугольнике, либо она пересекает ровно два отрезка. Интересны только пересекающиеся треугольники.

Если у вас есть треугольник (A, B, C), где A, B и C являются вершинами.

Предположим, что плоскость пересекает отрезки (A, B) и (A, C) в точках D и E. Определите вершину F между B и C (например, B + (C - B) / 2), но подойдет любая вершина на отрезке между B и C).

Тогда ваши новые треугольники следующие (A, D, E), (B, D, F), (D, E, F) и (C, E, F)

Answer 4

Выберите 3 случайных точки и разделите вдоль этой плоскости. В чем проблема?