Shiva

27/01/2009, 14:55

Далече, пятью днями ранее, ваш покорный слуга разродился скриптиком для 3dsmax 5 и выше, позволяющего нарезать любую геометрию ячейками Вороного на основе облака точек другой геометрии или системы частиц.
Скрипт распространаяется на доброволных началах, тобишь Даром.
Любопытствующие могут погуглить с ключевым словом "Voronoi".
На вопрос "И шо мне с этого" отвечаю - с помощью этого скрипта можно красиво разбивать геометрию на осколки для последующего просчета динамики, либо можно генерировать всякие красивые абстрактные геометрические структуры (крайне полезно для Дезигнеров разной руки), или соты прям как у пчел, или плотно прилегающие друг к другу клетки живой ткани. Вобщем все зависит от вашей фантазии.
Скачать скрипт и ознакомится с примерами его работы можно тут: http://www.shiva3d.net/index.php?page=scripts.html
Если есть замечания/поженлания - пишите письма.

protactinium

27/01/2009, 15:03

че-то не открывается сайт по ссылке (

[Vitus]

27/01/2009, 15:27

Shiva: Замечательная идея.
А ты не это написал? Вышеозначеный скрипт не лишён недостатков, не назначает ID на нарезаные фейсы, и написан неоптимально очень, из-за этого тормозной. У тебя как, покажи, а то действительно ссылка нерабочая.

90rpm

27/01/2009, 15:28

Скачать скрипт и ознакомится с примерами его работы можно тут: http://www.shiva3d.net/index.php?page=scripts.html

Супер. Впечатлил видеоролик. Получается очень естественно.
А пожелание такое - сделать ролик более детализировванным. А то всё как-то очень быстро.

P.S. Не знаю что у вас там такое, у меня всё открывается по ссылке.

1асс

27/01/2009, 15:49

Эх, я тоже три дня назад с подачи Shiva, Vitsly и Mir-Vadim заболел Вороным и Делоне (кстати первый украинский математик, а второй русский) и сейчас усиленно думаю над собственной реализацией алгоритма.

Shiva

27/01/2009, 16:15

Странно что не открывается. =(
попробуйте через главную www.shiva3d.net

2 megavitus: да, суть та-же. Диаграммы вороного они диаграммы вороного и есть.
Мой скрипт тоже медленный. Я в математике не силен, по этому делал как умел.
Но вот возможностей у моего больше. Делал спецом под пожелания Visty.
Тема тута раскрыта: http://vitsly.livejournal.com/9113.html#cutid1

Насчет назначения ID а вот только сегодня об этом подумал. Надо будет дописать.

2 1acc: Угу, если чистую матмодель взять то думаю будет значительно быстрее. Но проблемма в том что допустим ячейки то построить по ней можно, а краевые, которые являются оболочкой базового обьекта, полюбому надо булить из оригинала. Да и как определить какие надо булить а какие нет? ячейки очень непредсказуемы по форме.

1асс

27/01/2009, 16:37

определить-то можно по формуле Эйлера, начитался я теории много, вопрос в том как это все быстро делать. точки вокруг центра ограничивать.

[Vitus]

27/01/2009, 16:44

Через IE не открывается, оперой нормально.
В седьмой и девятой-32 версии макса ошибка по run script, видимо из-за зашифровки новой(эх что-ж вы всё криптуете и криптуете). А вообще молодец.

p.s. Visty конечно монстрище

[Vitus]

27/01/2009, 16:48

1асс: Там отсекать нужно лишние точки после каждого разреза плоскостью.

-- Уравнение плоскости, проходящей через
-- точку M0(x0,y0,z0) перпендикулярно вектору N = (A, B, C):
-- A(x-x0)+ B(y-y0) + C(z-z0) = 0
-- признак в какой полуплоскости: >0, <0

1асс

27/01/2009, 16:55

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

[Vitus]

27/01/2009, 17:01

1асс: А, ты хочешь вообще строить сам? Геморно и не факт что быстрее будет. В том скрипте что я ссылку давал, вообще попростому: в каждый партикл копируется полная копия базового объекта, и потом модификатором slice обрубается всё лишнее

Shiva

27/01/2009, 17:02

1асс: Там отсекать нужно лишние точки после каждого разреза плоскостью.

-- Уравнение плоскости, проходящей через
-- точку M0(x0,y0,z0) перпендикулярно вектору N = (A, B, C):
-- A(x-x0)+ B(y-y0) + C(z-z0) = 0
-- признак в какой полуплоскости: >0, <0

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

By Shiva3d

1асс

27/01/2009, 17:02

2 Megavitus: да это я понял конечно. и у всех остальных такие же алгоритмы. Не факт что будет, но мне охота уж больно попробовать.

protactinium

27/01/2009, 22:12

Открылся сайт в мозиле (в ие7 так и не открылся).

Отличный скрипт. Очень полезный.

Shiva

29/01/2009, 01:00

Сайт починил.

protactinium

29/01/2009, 11:00

Да сайт почти работает )
Открываются все страницы, кроме страницы "scripts" )

-=VG=-

29/01/2009, 13:28

Хотел посмотреть сайт тоже - не получилось. Я в свое древнее время тоже Delone смотрел, но не с точки зрения разбиения пов-ти, а просто перетриангулировать на основе базовых, в общем задачка еще та, посему не стал изобретать колеса и взял существующею библиотеку, просто применив ее для своих целей, причем там есть и разбиение, только мне это не нужно. А сама библиокека поддерживает это по задаваемому параметру площади и(или) по длине ребра. Точно уже не помню.

Shiva

29/01/2009, 13:36

блин, да чтож за наказание то такое... =(

LevaLeva

29/01/2009, 14:21

Красиво! Снимаю шляпу перед теми, кто делает своими руками, кто способен программировать и не забыл математику!

1асс

29/01/2009, 15:39

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


Мои раздумья на тему сабжа после прочтения кучи теоретической инфы.

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

Все приведенные скриптовые алгоритмы в максе обрабатывают это дело следующим образом. Исходная фигура копируется, выбирается любая точка, проводятся линии от нее до всех остальных точек, через середину каждой линии строится ей перпендикулярная плоскость, которая "отрезает" кусок от исходной фигуры и так до тех пока точки не кончатся и так далее, для каждой оставшейся точки. Т.е. допустим, если у нас 1000 точек, то это будет 999000 операций обрезания - скорость N^2. Нерационально, потому предлагаю подумать над альтернативными решениями.

Я долго ломал голову над вопросом, как выбрать точки одного многогранника, не перебирая все остальные точки и ничего толкового не придумал, зато из прочитанной теории узнал, что построив симплексы Делоне (теория пустого шара) можно однозначно получить многогранники Вороного, посему пишу алгоритм сначала для симплексов и попутно рассказываю что это вообще есть такое.

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

До чего я додумался:
1. Выбираю одну точку например в центре набора. И тащу ее в ноль вместе со всем хозяйством.
2. Ищу среди остальных точек вектор с минимальной длиной, т.е. точку - ближайшую к первой. Нашел. Имею две точки.
3. Провожу отрезок от одной точки до другой и нахожу плоскость, проходящую через середину отрезка и перпендикулярную ему.
4. Обзываю центром середину этого отрезка.
5. Нахожу среди оставшихся точек ту, чья проекция вектора из центра до точки на плоскость будет минимальной. Получаю три точки на шаре, точки образуют ессна треугольник - одна из граней симлпекса.
6. Нахожу среди оставшихся точек ту, чья проекция на плоскость треугольника будет минимальной. Вектор растет из центра описанной вокруг треугольника окружности.
7. Опа, первый симплекс готов. Можно строить меш из треугольных граней.
8. Остальные симплексы строятся на гранях найденных, т.е. повторяются только 6 и 7 пункты.

Если есть какие комментарии - выкладывайте, пока не успел написать алгоритм.

Shiva

29/01/2009, 22:15

Струдом уловил суть.
Походу все равно придется перебрать всё облако, и сетка получится триангулированной, хотя это мелочи.

-=VG=-

29/01/2009, 23:50

Струдом уловил суть.
Походу все равно придется перебрать всё облако, и сетка получится триангулированной, хотя это мелочи.

Не берусь утверждать что это будет правильный или неправильный алгоритм. Скорее всего неполный т.к навскидку я вижу проблему после построения второго симплекса - как он будет через третий (который должен еще построится) соединяться с первым. Ну да ладно. Я еще раз повторюсь - время на это тратить незачем я считаю. Создавать заново колесо - ну можно конечно - только круглее не будет.
Вот например:
http://www.cgal.org/
очень неплохой сборник алгоритмов с исходными текстами, примерами, хелпом. Там есть и триангуляция и диаграммы Воронова, и симплексы и еще всего полно. Только применяй. Конечно это все не на макс скрипте, но и задачи такие не для 10 точек обычно применяют. Хотя указанная там производительность вычислений впечатляет. Даже видео неплохое- по крайней мере познавательное. Не уверен что можно переписать под макс скрипт но если уж очень хочется - выудить алгоритм можно.

1асс

30/01/2009, 08:07

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

2 Shiva:
1. Я сортирую точки, а потом выбираю нужную, встроеный алгоритм сортировки работает гораздо быстрее, чем перебор точек скриптом.
2. Число точек с каждым этапом будет уменьшаться.
3. Зная симплексы для одной точки я многократно сокращаю количество операций обрезания. Можно даже не париться с ручным построением многогранника и резать. Сразу будет столько обрезаний, сколько надо.

1асс

30/01/2009, 08:55

Поправка: нашел про симплексы и триангуляцию Делоне, но как из них получить многогранники нету, как и объяснения принципа отбора точек для симплекса Код копать ради этого тоже не хочу, его там много слишком.

1асс

30/01/2009, 12:55

ого, первооткрыватель А какая скорость со скриптом из альтернативного варианта в жж, можно узнать ?

1асс

30/01/2009, 13:24

разница впечатляет.

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

[Vitus]

30/01/2009, 14:33

Shiva: Я только одного не понял, ты что-ли взял со скриптспота за основу, приделал кнопку для мануального указания частиц и всё?

Shiva

30/01/2009, 16:30

Shiva: Я только одного не понял, ты что-ли взял со скриптспота за основу, приделал кнопку для мануального указания частиц и всё?

Да, только кнопку прилепил.

Да, за основу взят скрипт со скриптспота который работает так - запихивает в любой обект PCloud и по его частицам режет геометрию - получается равномерно раздробленная геометрия, дробление делается модифером Slice + Cap holes.
Вот только идею Slice+CapHoles я и взял. Остально свое.
В моем скрипте ты можешь указывать не систему частиц, а Любой обькет или любую систему частиц. Более того это могут быть несколько обьектов и систем частиц вперемешку. Делалось это потому что задача другая. Указывая геометрию можно получать не случайно нарезанные куски, а красивые кристалические структуры (см. картинки Visty). К тому-же фрагменты заимствуют цвет обьекта родителя, что упрощает отфильтровку ненужных укусков.

[Vitus]

30/01/2009, 17:14

Это немного напоминает ситуацию, когда наш русский писатель переписал итальянскую сказку пиноккио, и подписал: золотой ключик, Лёша Толстой!

В том смысле, что идеи заимствовать конечно никто не запрещает, тем более что автор там указал "Feel free to share and modify at will...", но исходный скрипт был в лучших традициях опенсурса, а тут традиция неожиданно прервалась.

Можно было хотя-бы сделать about и там указать что так мол и так, основано на том-то.

Shiva

30/01/2009, 18:40

Это немного напоминает ситуацию, когда наш русский писатель переписал итальянскую сказку пиноккио, и подписал: золотой ключик, Лёша Толстой!

В том смысле, что идеи заимствовать конечно никто не запрещает, тем более что автор там указал "Feel free to share and modify at will...", но исходный скрипт был в лучших традициях опенсурса, а тут традиция неожиданно прервалась.

Можно было хотя-бы сделать about и там указать что так мол и так, основано на том-то.


Ты в моем лице прям всех скриптеров пристыдил. )) Я прям чую как -=VG=-, Mir Vadim и 1acc тоже покраснели. ))
Если чесно мне пофиг что это напоминает.
Те кому надо исходник видели в первый же день. Спроси у 1acc что там в верхних строчках написанно.
А дать ковырятся в нем всем подрят я не захотел. Ну вот такой я вредный. В конце концов от оригинального скрипта там всего несколько срочек и неделя моего труда.

В наше время все друг у друга Что-то взаимствуют и усом не шевелят. Это тоже в лучших традициях Русских.
Если хочется справедливости - начни с галереи Рендер.ру где народ не только идеи, но и модели чудесно друг у друга "заимствует" и ставит под ними свое имя. При этом еще и аварды не стыдится зарабатывать.

1асс

30/01/2009, 19:13

А я не покраснел , я свой алгоритм пишу. Вообще megavitus зря наехал, ну хочется человеку закодировать дык ну и что, он же не продает его. Под опенсурс никто не подписывался, значит каждый сам решает в каком виде ему что выкладывать. Скрипты это в максе вообще едва ли не единственное, что более-менее можно защитить. И причин для шифрования может быть куча самых разных, например хочется единолично продолжать делать новые версии не парясь, что где-то есть конкурент, которого надо обгонять или код не оптимальный и не хочется чтобы все подряд придирались - вот две вполне легальные причины не выкладывать исходники.

1асс

30/01/2009, 19:51

Скриптую симплексы, алгоритм первый мой неточный оказался, вот новый вариант:

1. Выбираю одну любую точку (я беру первую). И тащу ее в ноль вместе со всем хозяйством.
2. Ищу среди остальных точек точку - ближайшую к первой. Нашел. Имею две точки.
3. Ищу третью точку, такую что окружность, описанная вокруг моих трех точек будет минимального радиуса.
4. Ищу 4 точку, такую что сфера построенная на 4 точках будет минимального радиуса.
5. Опа, первый симплекс готов. Можно строить меш из треугольных граней.

6. Остальные симплексы строятся на гранях найденных, т.е. повторяется только 4 пункт.

Загадка: Если отсортировать точки на третьем этапе по возрастанию радиуса, то будет ли 4ая точка искомой для этапа 4?

Shiva

30/01/2009, 19:55

1acc. ))) я считаю что заимствование алгоритмов или формул с других сайтов это все равно взаимствование. Какая разница будет это готовый код или готовый код на Другом языке. )) суть не меняется.
"Вопрос этики, повернутся к вам жопой или членом" © Тайлер.
Так что как ни крутись - все мы что-то пи_дим друг у друга. Тут главное не лицемерить. =)

1асс

30/01/2009, 19:58

ну тогда мы сперли алфавит у кирилла с мефодием и математику у евклида

[Vitus]

30/01/2009, 20:02

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

А по поводу "легальных причин" то давно подозреваю за 1асс вторую

У меня кстати есть уже и своя версия этого дела, процентов на 15-20 быстрее оригинала, но всё равно О(N^2). Придумал как оптимизировать до O(N*log(N)), и тут -=VG=- напомнил про cgal(именно я давал ему ссылку). Буду разбираться.

1асс

30/01/2009, 20:08

Угу, а я и не отказываюсь, мои первые скрипты я бы и сам переписал бы с нуля, все только никак не соберусь.

1асс

04/02/2009, 05:24

4 дня, 4 ночи и 5 утра среды. Сделал. Решение простое как две копейки. Обрезаю только нужные точки, лишние пропускаю, в результате каждый многогранник режется примерно 20 раз (а не по числу точек).

Итого: 508 случайных точек за 1.3 минуты скриптом. 1008 точек примерно за 3 минуты.
Наведу марафет и обязательно сделаю урок на эту тему.

Shiva

04/02/2009, 21:43

Аха... я вот тоже пытался сделать это простое решение как две копейки, только отделить Нужные точки от Ненужных оказалось не так-то просто. ))
Ты молодец. ) Интересно будет посмотреть урок. Ждемс.

90rpm

08/02/2009, 01:03

Пожалста скажите - это больше скрипт или целый SDK ?

Shiva

09/02/2009, 14:39

Пожалста скажите - это больше скрипт или целый SDK ?

Очень странный вопрос. Что в твоем понятии SDK?
И в каких пропорциях ты определяешь Больше или Меньше это скрипт?
=)

1асс

12/02/2009, 16:31

Публикация урока затягивается, выкладываю алгоритм отдельно.

Алгоритм поиска стопроцентных соседей

...Эврика, решение оказалось элементарным.
Создаю двумерный массив (у меня используется конструкция struct), в первом элементе которого содержится номер текущего центра, а во втором – массив номеров всех остальных центров, отсортированный по расстоянию до текущего (по возрастанию). То есть по уменьшению вероятности влияния этой точки на многогранник. Ведь чем дальше находится точка, тем меньше у нее возможностей отрезать кусок от рабочего объема, так как сначала отрезают ближайшие соседние точки и если они уже все отрезали, то секущая плоскость дальней по расстоянию точки не пересечется с создаваемым многогранником и отрежет пустоту. И теперь нужно определить только этот предел – за которым точки всегда будут резать пустоту и тогда их можно смело пропустить и перейти к построению нового многогранника. Итак, начинаем резать: первая точка отрезала часть от объема базовой фигуры, рабочий объем уменьшился, дальше вторая, объем опять уменьшился, третья и т.д. до тех пор, пока новая точка уже не сможет ничего отрезать. Критерий простой – эта точка будет та, половина расстояния от которой до центра многогранника больше, чем длина радиуса описанной вокруг многогранника сферы. Я даже делаю проще – беру сферу, описанную вокруг габаритного контейнера многогранника, ибо ее радиус заведомо больше, а поиск описанной сферы минимального радиуса – та еще задачка и ее внедрение в алгоритм его только замедлит. Радиус сферы, описанной вокруг габаритного контейнера находится элементарно – он равен половине расстояния между максимальной и минимальной точками контейнера. Габаритный контейнер с каждым обрезанием уменьшается вместе с многогранником и как только он будет достаточно малым, чтобы секущая плоскость новой точки не пересекла сферу – это значит, что дальше резать не нужно и бесполезно, текущий многогранник готов, можно пропустить оставшиеся точки и строить следующий многогранник Вороного. Написал много слов, поясняю на картинке:

Нажмите для просмотра прикрепленного файла

Точки в массиве отсортированы по расстоянию, и идут в порядке красная, желтая, голубая. Зеленая сфера описана вокруг розового габаритного контейнера. Начинаю строить, красная точка отрезает объем от многогранника и формирует одну из граней. Идем дальше и видим, что плоскость от желтой точки не пересекает сферу габаритного контейнера. Ага, значит все, красная точка была последняя, многогранник готов и по плоскостям желтой и голубой точки можно не резать – новых пересечений все равно не будет и голубая алгоритмом даже вообще не проверяется. У себя в скрипте я не делаю эту проверку каждый проход, так как гарантированно первые 4 точки образуют грани и в принципе, если точек много, то можно начинать проверять примерно после 16-ой, а до этого отрезать не задумываясь. Вот такой простой и главное быстрый алгоритм. Например для 1000 точек будет около 20000 обрезаний. 20000 и 999000 – разница более чем заметная.

[Vitus]

12/02/2009, 17:17

Браво!

Shiva

13/02/2009, 14:23

1acc, ты не против если я впихну эту оптимизацию в свой скрипт? )

[Vitus]

13/02/2009, 15:12

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

Маленькая поправка: Радиус сферы по моему нужно считать как максимальное расстояние от центра ячейки до угловых точек контейнера. Так как центр контейнера далеко не всегда будет совпадать с центром ячейки.

Edge

13/02/2009, 16:41

Сладость - козенака), мощение, некие органические вещи делать..

BorisK

13/02/2009, 16:49

какашке тоже хорошо