Помогите улучшить решение.

← →
@!!ex © (2007-07-08 16:16) [0]

Суть задачи:
Есть 3Д модель состоящая из треугольников.
Нужно порезать эту модель на части.

Придумал такое решение:
Составляем список из всех тругольников.
Берем N(сколько нужно частей) случайных треугольников.
Записываем из в отдельные списки, отмечаем как использованные. У каждого списка есть центр.
Проходимся по каждому списку, для каждого списка находим ближайший не заюзанный треугольник, прикрепляем к списку и отмечаем как заюзанный.

Лично я вижу две проблемы:
1) Медленно работает, поскольку для каждого шага нужно вычислать квадратный корень и два квадрата.
2) Не знаю как вычислить центр полученного куска.
Можно считать, что все треугольники равного размера.
Как сделать лучше?

← →
TUser © (2007-07-08 16:27) [1]

Он не из-за этого медленно работает, а потому что алгоритм - кубический.

Представь граф, где вершины соотвествуют треуголькам. Найди мин. остовное дерево. Выброси из него N-1 ребер с минимальным весом (придется придумать, что такое вес ребра).

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

← →
TUser © (2007-07-08 16:32) [2]

Вот тут почитай, конспект семинара по кластеризации, кодировка - Cyrilic (DOS)

http://monkey.belozersky.msu.ru/~evgeniy/Rubinov_clauster

← →
@!!ex © (2007-07-08 16:35) [3]

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

← →
@!!ex © (2007-07-08 16:38) [4]

Суть в том, что нужно поделить машину на куски и при взрыве, она на куски развалится...

← →
@!!ex © (2007-07-08 16:39) [5]

Статья интресная, кстати. Спасибо!

← →
engine © (2007-07-08 16:39) [6]

> [4] @!!ex © (08.07.07 16:38)

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

← →
@!!ex © (2007-07-08 16:42) [7]

> [6] engine © (08.07.07 16:39)

Нет. С чего. Я же не применяю к частям законы физики, а применяю один и тотже вектор движения. Соответственно пока я не скажу - не развалится.

← →
Zeqfreed © (2007-07-08 18:42) [8]

По-моему, нет смысла «делить на куски». Эффектнее и реалистиченее будет выглядеть, если при взрыве вместо непонятно как определенных алгоритмически кусков будут разлетаться заранее подготовленные (смоделированные) ее части (капот, крылья, двери, колеса и т.п.). Т.е. делить на части должен человек, но никак не алгоритм. «Разлетающиеся треугольники» выглядят убого.

← →
ANTPro © (2007-07-08 19:06) [9]

> [8] Zeqfreed © (08.07.07 18:42)

+1, это дизайнеру решать что должно отваливаться :)

← →
Юрий Зотов © (2007-07-08 19:11) [10]

> Составляем список из всех тругольников.

И как только мы его составили, задача УЖЕ решена. Осталось только пройти по этому списку и рабросать его элементы случайным образом.

> [8] Zeqfreed © (08.07.07 18:42)

Ога. В проекте на три десятка машин, когда сроки уже просрочены, заваливать моделлеров работой по разбору машин на детали. Ништяк.
Никто не говорит о разлетающихся треугольниках. Разделение на куски дает вполне приятную картину и при это разную каждый раз.
ИМХО не стоит обсуждать результат работы алгоритма, который вы не видели. ;)

> [10] Юрий Зотов © (08.07.07 19:11)

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

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

> @!!ex © (08.07.07 20:51) [11]

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

> [12] Zeqfreed © (08.07.07 21:41)

Колесо же не явялется частью машины. :)
Тоесть оно в любом случае отделено от меша машины, посколку как иначе крутить?

> @!!ex © (08.07.07 21:55) [13]

Ну это не важно. Стекла тоже отдельно? Я все же настаиваю на том, что твой вариант не является хорошим ни с какой стороны. По трудозатратам и по красочности (реалистичности), ручная «разметка» частей выглядит явно более привлекательной. Разумеется, лишь мое мнение :)

Помогите улучшить решение. Найти похожие ветки