Засеять поле

[Igors]

Добрый день

Изначальная (бедненькая) постановка

Поле: любой заданный юзером объект имеющий площадь, для примера просто регулярная сетка (меш) 200x200.

Что сеять: любые объекты заданные юзером (см первый аттвч)

Требование: посеянное не должно само-пересекаться

Второй аттач - рез-т прямолинейной/бесхитростной реализации. Алгоритм

Юзер задает "сколько сеять", напр 5К, и далее в цикле
 
  - случайно выбираем объект для посева
  - случайно выбираем вертекс(узел) сетки(поля)
  - ставим объект. Если его bounding box пересекается с другими - удаляем

И так до тех пор пока или поставлено заданное юзером число объектов или кончились все узлы сетки

Как это улучшить? Какие еще опции (кроме счетчика) предложить юзеру? Что они должны делать? Не надо спрашивать юзера, ничего путного он не предложит (вот покритиковать сделанное - то да). Словом нужно проявить "креатив" (как сейчас говорят). Можно пойти и др путем - что сейчас плохо? Как это улучшить?

Спасибо

[Apktyc]

Было бы очень кстати иметь возможность задать карту засевания (по минимуму черно белую, по максимум - регулирующую плотность), чтобы быстро и эффективно тропинки прокладывать.

[Igors]

Было бы очень кстати иметь возможность задать карту засевания (по минимуму черно белую, по максимум - регулирующую плотность), чтобы быстро и эффективно тропинки прокладывать.

И сразу нормальная мысль! (боюсь сглазить). Как раз "по максимуму" я и застрял . Пусть сеем всего один объект (чайник) применяя простецкий алгоритм выше

Первый аттач: юзер заказал 200 чайников, ну "влезло" гораздо меньше. Все норм

Второй аттач: то же + юзер добавил булевскую карту (точнее "цвет вертексов", ну это не принципиально). Опять все "как доктор прописал"

Третий аттач: а вот с такой маской (50% + круг) не бычит  (рез-т практически тот же что и первый)

Конечно напрашивается "давайте сгенерим все (случай 1), а потом удалим 50% по маске)". Но это уже не вписывается в простой алгоритм выше. И это будет работать для одного чайника (ну или для всех но с одной и той же маской)

[Apktyc]

Если очень врукопашно... я бы собрал массивы вертексов по цвету (читай плотности) и сеял бы туда пока не превышена та самая плотность.
Начинать надо с максимальной, потому что, скорее всего она не будет достигнута, и надо будет поправлять меньшие плотности.

Т.е. сеем туда, где максимальная плотностью. Она скорее всего не достигается, но мы получаем некий коэффициент для поправки остальных (дабы сохранить отношение).

[ecspertiza]

Я бы подумал в сторону случайности выбранного места на поле. Есть вероятность что все случайности попадут в одну точку (стремится к нулю) и у нас на поле будет один чайник. Я конечно ультрирую, но веду к тому что может быть выброшено много объектов из за пересечения. По идее 1ое можно заранее просчитать кол-во объектов которые могут поместиться, что бы не совершать лишние операции. Грубо говоря, если площадь поля вмещает 2к объектов и уж больше никак, то нет смысла давать возможность выбрать 5 или 10к. Из количества объектов высчитать плотность и играться с случайностью только в расстоянии между дистанцией между объектами от 0 до маскимум плотности, что бы создать эффект случайной засейки поля. И сеять их не рандомом в этом случае, а просто по сетке.

[Igors]

.. и сеял бы туда пока не превышена та самая плотность.
..
получаем некий коэффициент для поправки остальных (дабы сохранить отношение).

По идее 1ое можно заранее просчитать кол-во объектов которые могут поместиться, что бы не совершать лишние операции.

Если я верно понял, то оба предложения по существу - как-то посчитать "плотность". Ну прикинем во что это вольется. Считаем площади всех полигонов - не вопрос. Как-то (приблизительно) считаем площадь занимаемую объектом. Ну допустим (хотя в деталях пока не знаю как). Хорошо, получили (макс) "плотность". И.. что с ней делать? К тому же объекты посева разные (38 попугаев и.т.д).

  - случайно выбираем вертекс(узел) сетки(поля)

Как я делаю это сейчас

Код

C++ (Qt)
struct CLocation {
  int mIndex;       // индекс вертекса
  float mFactor;   // значение "карты" или 1.0f если карты нет
  float mSum;      // см ниже
};
 

Создаю вектор CLocation и перемешиваю его (random_shuffle)и прописываю mSum

Код

C++ (Qt)
vec[0].mSum = 0.0f;
for (size_t i = 1; i < vec.size(); ++i) 
 vec[i].mSum += vec[i - 1].mSum;
 

Теперь выбор сводится к lower_bound (ищем нарастающий счетчик), вертексы с mFactor = 0 автоматом пропускаются, булевская маска работает.

[Igors]

Другая вещь типа "обязательная программа". Для простоты рассматривается пример с регулярной сеткой, но юзер может выбрать в качестве "поля" объект любой деталировки, вплоть до одного полигона. Конечно у него есть тулзы для деталировки, но хорошим тоном считается деталировать автоматом. Тогда возникает вопрос "а насколько?". Конечно вопрос "как" с полным правом можно считать "делом техники" - но он тоже интересен и заслуживает обсуждения. Заметим что "полная геометрия" (больше полигонов и вертексов) здесь не нужна, нас интересуют только "позиции" (для расстановки), а они может быть записана напр в координатах оригинальных полигонов.

[Apktyc]

Все возможно интересные опции, советую подсмотреть в multiscatter и iToo Forest (там учтено пожалуй 90% хотелок художника).

Если я верно понял, то оба предложения по существу - как-то посчитать "плотность". Ну прикинем во что это вольется. Считаем площади всех полигонов - не вопрос. Как-то (приблизительно) считаем площадь занимаемую объектом. Ну допустим (хотя в деталях пока не знаю как). Хорошо, получили (макс) "плотность". И.. что с ней делать? К тому же объекты посева разные (38 попугаев и.т.д).

Если исходить из условий (что пока сажаем только вершинах), и лобовой атаки... как я и говорил, делим все вершины по плотности (цвету). Дальше, берем вершины с максимальной плотностью (пусть 1), и случайно сеем по ним до тех пор, пока они не кончатся (либо физически, либо будут помечены как узлы не проходящие в силу ограничений).
По идее, сеем объекты с минимально возможным масштабом, потом начинаем их увеличивать их с разной скоростью, до стоп условия (по масштабу, по пересечению, ...).
Если сетка регулярная, то здесь мы получим процент использования вершин при максимальной плотности (допустим мы заняли 90%).
Допустим следующая заказанная плотность 0.8, и тут при случайном засеве у нас появляется дополнительное ограничивающее условие в 72% от доступных вершин.
Вроде так. Но это не точно.

З.Ы. "Деталировка" определяется указанным пользователем необходимым количеством объектов (т.е. дробить на как минимум столько же посадочных мест). Хотя условие спорное.

[Igors]

Сначала сеять там где объект-кандидат 100% есть. Пусть это еще не значит что он будет посеян (collision), но смысл в этом есть. Хорошо, отстрелялись, начинаем парить "разреженные" площади

Допустим следующая заказанная плотность 0.8, и тут при случайном засеве у нас появляется дополнительное ограничивающее условие в 72% от доступных вершин.

Так доступных может оказаться "до фига", напр в исходном примере 200х200= 40K. Допустим юзер заказал 5K - ну они и будут ставиться, плотности 0.8 или 0.7 или 0.5 все дадут равноценный рез-т, пусть не идентичный, но никакого "разрежения" не будет. Вот если бы он заказал "тот самый" счетчик что соответствует "разрежению" - но руками он это не сделает

Edit: вот сетка 30х30, вертексов (посадочных мест) 961, этот счетчик и заказан. Collisions = off. Используется тот же самый алгоритм (код не менялся). Все нормуль, рез-т соответствует маске выше (50% + круг).  Осталось (всего лишь  ) сделать это для произвольного числа счетчика и посадочных мест

[Igors]

Все возможно интересные опции, советую подсмотреть в multiscatter и iToo Forest (там учтено пожалуй 90% хотелок художника).

Смотрел, и эти тоже, но все равно спасибо за наводки.

Проблема в том что здесь "подсмотреть" оказывается далеко не тривиальной задачей. Это хорошо для типовых, хорошо изученных задач, там да, "наливай да пей". Что впрочем порождает массу извращений ("все давно написано" и.т.п.). Но в данном случае такой "тиражируемости" нет, и что (творчески) позаимствовать? Да хз

Вот для удобства ссылки

https://docs.rendering.ru/en:multiscatter
https://docs.itoosoft.com/forestpack

И что отсюда можно/нужно взять? Я прекрасно знаю что ответа не будет, дальше "тыц" дело никогда не идет 

[Igors]

Ладно, вернемся к плотности. Поразмыслил, похоже "ларчик просто НЕ открывался", достичь соответствия расставленного заказанной мапе не удается при произвольных счетчике и числе мест. Что есть "плотность 50%"? Это значит на 10 посадочных мест будет отпущено 5 объектов. Что будет если для предыдущего примера заказать не все 961 вертексов в только половину? Ну уберутся какие-то в центре, какие-то по краям, картина "размоется". А с отказами collision "сгущения в круге" вообще можно и не увидеть. Ставить сначала там где плотность выше - тогда при каком-то счетчике в центре густо, по краям пусто (а обещали 50%).

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

Ну ладно, это всего лишь фрагмент/эпизод, поехали с др проблемами. Как сажать на произвольной поверхности? Есть полигоны имеющие площади, что могут быть примерно одинаковы (uniform), но могут и сильно (на порядки) отличаться. По сути дело сводится к

Дайте (сгенерируйте) заданное число посадочных мест (N) на заданном полигоне

Определимся что есть полигон - это  треугольник или 4-угольник, большее число вертексов не рассматриваем. Ну позиции вертексов конечно известны. При желании и 4-угольник можно побить на 2 тр-ка, но это упрощение не так уж очевидно, как ни странно, некоторые алгоритмы для 4-угольника работают лучше.

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