Большой граф

[Igors]

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

Вот бросаем луч из точки p1, первая ячейка. И луч нашел точку p2. Это "хороший" вариант, новую точку создавать не нужно. Пишем в файл ребро p1-p2 и поехали дальше. Но не все так просто. Во-первых, луч может найти не "чистую" p2, а интерполяцию 2 и более точек, напр p2, p3 и p4. Выходит надо писать 3 ребра, причем ребра уже имеют вес.

Дальше. А чего это мы бросаем из первой ячейки - может ребро для нее уже есть? Напр уже был выброс из той же p2 и луч нашел ту же p1 (необязательно конечно, но возможно). И не видно как это проверить не имея огромную ораву ребер в памяти. Проверка тоже проблематична - напр ребро есть но имеет вес 0.5, и что, его достаточно или нужен еще луч ?

Интуитивно понятно что надо как-то парить "по частям", но пока нет никаких идей как это сделать. Ну разве прогонять (громадный) файл ребер "извлекая" из него ребра что приходят в точки выброса (наша p1). Ну как-то совсем коряво

[m_ax]

Ну ладно, считаем что с выбросом лучей разобрались.

Нет, не разобрались. Вы писали:

Из точки выбросить заданное кол-во случайных лучей M так чтобы они группировались вокруг заданной нормали N как показано в моем предыдущем посте - по нормали больше лучей, по касательной меньше. Т.е. требуется заменить "больше/меньше" на конкретные формулы, а еще лучше на алгоритм, код напишем - не проблема.

Такая постановка как "по нормали больше, по касательной меньше" уже очень расплывчата.. Хорошо, я привёл в .pdf фактически алгоритм, который конкретизирует эту проблему. Задайте свою плотность распределения угла тета (угол между нормалью к поверхности и случайным единичным вектором) и всё. Сегодня Вам понадобиться чтоб практически все лучи были близки к нормали, а завтра напротив - полностью равномерно распределены..

Вот бросаем луч из точки p1, первая ячейка. И луч нашел точку p2. Это "хороший" вариант, новую точку создавать не нужно.

Я не понимаю.. 

[Igors]

Такая постановка как "по нормали больше, по касательной меньше" уже очень расплывчата.. .

Вот простая формула которая есть в каждом шейдере

shade_color = light_color * material_color * dot(N, L)

Где N - нормаль, L - вектор света (точка - источник). Это простейшая модель освещенности, в просторечии "диффузный косинус". Но это точечный источник, а у нас как бы светит вся сцена. Пример: комната, в ней горит лампочка, но далеко не все части комнаты освещены напрямую. Однако темноты нигде нет, вот этот (пере)отраженный свет мы и хотим считать. Имитируем его серией виртуальных лампочек, поэтому лучи должны быть  распределены по диффузному косинусу.

Я не понимаю.. 

Конкретнее, что неясно? Мы хотим отделаться минимальным числом просчитанных точек (лампочек выше), хотя оно и будет достаточно велико (мульены)

[Igors]

И опять слился   Ну да, академическая часть здесь есть, но невелика, в основном дела программистские. При этом до "современного С++" дело не доходит, сначала нужно понять что делать. Ладно, пожуем работу с данными

Есть N начальных точек (напр лимон), из каждой выбрасывается от 200 до 1000 лучей которые так или иначе находят др точки (может имеющиеся, может новые). Эти ребра нужно как-то хранить, как? Формат ребра

Код

C++ (Qt)
struct Edge {
  uint32 src, dst;  // индексы начальной и конечной точек/вершин
  float weight;     // вес ребра, без него не обойтись 
...
};
 

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

Какие есть предложения?

[m_ax]

И опять слился

Ну почему же.. Я читаю.. Просто непросто (прошу проощения за каламбур) предложить что-то адекватное)
Тут ещё статью нужно писать..

Не курили в сторону AI? Нейросети там, может Vanda) Но это так, мысли вслух) 

[m_ax]

Тут на канале ТехноШамана ролик вышел https://www.youtube.com/watch?v=U5yVw4uQNDo о непрерывном преобразовании одной картинки в другую) Вот будет время опробую это на Vande) Думаю, это даже круче будет его реализации на tensorflow 

[Igors]

Не курили в сторону AI?

Это типа "мечта сачка", вот есть штука, она все-все за меня сделает! А программисты не нужны, ну максимум "собирать" Да и как-то это "не в духе" нейросети, никаких "решений" тут не требуется

Код

C++ (Qt)
void CalcEnegry( Point * p )
{
  float sum = 0.0f;
  for (int x = 0; x < cellX; ++x)
   for (int y = 0; y < cellY; ++y)
    sum += GetCell(x, y);
 
  p->energy += sum / (cellX * cellY);
}

Где cell(s) - те самые ячейки что показаны на полусфере. Ф-ция GetCell должна собрать все ребра связанные с точкой p, ячейкой (x, y) и посчитать среднюю energy c учетом весов ребер. Поскольку ребро связывает 2 точки, значит напр-е известно, индексы ячейки можно и не хранить, а всякий раз считать.

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

Вот собсно и все, очень просто "в прынцыпе". Одна из проблем - точек мульены, а рабер на 2-3 порядка больше. Хорошо бы парить "ребро за ребром" из файла, но нужно знать общий вес всех ребер для данной ячейки, а откуда его взять, др словами, как/где хранить?

[Igors]

Не курили в сторону AI? Нейросети там, может Vanda) Но это так, мысли вслух) 

Давно заметил что мысли (ну или то что ими называют) работают строго а одном направлении: попастись, хапнуть готовое. Не, я конечно не против, более того, я уверен что эта задача "давно написана" (лет 10 точно) - но вот делиться подробностями реализации никто не собирается. Это нормально, не все должно быть общедоступно

Между тем рабочее решение очевидно, и я о нем упоминал. Вспомним как Дуремар добывал ключик вычерпывая воду из пруда

Еще десять тысяч вёдер воды, синьор, — и золотой ключик у нас в кармане!

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

А если на дне не один, а напр 100 ключиков? Или тысяча? Тогда идиотская затея вычерпать пруд выглядит привлекательнее - черпать-то столько же, а "выйгрышь"  куда больше.

Итого: намечаем точки которые надо обсчитывать. Их должно быть "достаточно много" (в идеале сколько хватит памяти). Просматриваем/просеиваем файл и создаем для данных точек нормальные контейнеры данных. Используем их в GetCell().

Смущает: а созданные контейнеры потом просто удаляем - и все? Как-то "не по-хозяйски".

[Igors]

Так, с техническими вещами (как хранить и все такое) у нас "не пошло". Ну ладно, какой-то вариант есть, может и получше удастся найти. Наверно это товарищам неинтересно, хочется больше "креатива" - без проблем, вот интересное и трудное место.

Ясно мы хотим кешировать точки, если подходящая есть - юзаем ее, новую не создаем. При этом часто звучит фраза типа

Если в заданном радиусе R...

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

Хорошо, вот выбросили N лучей из точки (луч в каждой ячейке). Теперь тест: выбрасываем еще раз из нее же (или близкой к ней), только варьируя лучи в пределах ячеек. Если все сделано верно - кеш должен сработать 100%, все лучи должны найти имеющиеся точки. Очевидно радиус(ы) поиска должны зависеть от размера ячеек, значит от радиуса нарисованной полусферы. Но это абстрактная модель, на деле будет реальная сцена со множеством объектов.

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