Russian Qt Forum

Добрый день

Вот обдумываю (типа "с карандашом и блокнотом") предстоящую задачу, и, правду сказать, боюсь начинать :) По сути все сводится с графу, есть "вершины" и есть дуги/ребра. Физически вершины - точки на поверхности объектов 3D сцены. Каждая имеет по меньшей мере позицию (x, y. z) в пространстве, плюс нормаль, материал и др. Дуги образуются выбросом лучей из каждой точки, рабочее число дуг от 200 до 1000

Проблем море. Для начала такие квешнзы

1) Как эффективно хранить данные? Прямолинейное юзание контейнеров для дуг забивает всю память практически сразу, и дальше печальное лазание по свопам, 64-бита не спасают. Пока наметил хранить в RAM только точки, дуги как-то подкачивать (а как ?)

2) Как считать дуги? Не, ну выброс лучей конечно thread-safe, но дугу "из A в B" надо считать один раз, а не два. Т.е. просто так "выбрасываться" нехорошо

3) Как создавать новые точки? Начальные получаются из того "что видно на экране". Но лучи могут стрелять куда угодно, т.е. просто так дело никогда не кончится. И опять больное место multi-threading

[off]
Шансы на интересный/продуктивный разговор здесь невелики, но почему бы не попробовать ? Без нормальных тем становится скучно  :)
[/off]

Спасибо

Ответ напрашивается сам собой (во всяком случае, пока не ясны детали): Не запоминать рёбра, а придумать/заюзать алгоритм, который по известным точкам их генерирует..

Ну ладно, расскажу известные/популярные вещи.

Первый способ brute force, типа "а мне похер". Есть точка, выбросили из нее 200 лучей.  В замкнутой сцене (комната) получили 200 новых точек. Из них опять по 200. И.т.д Надо что-то делать, как-то гасить эту "цепную реакцию". Выбора тут особо нет, ну ограничить число рекурсий и уменьшать число лучей для второй и последующих. Последние GPU SDK с поддержкой raytrace вдохнули в этот совершенно тупой способ новую жизнь (ну это ненадолго)

Второй способ - популярный "path tracing". Выбросили луч, нашли новую точку. Из нее в случайном направдении с какой-то вероятностью (называется "pdf") опять выбросили луч. И просто повторяем этот процесс осредняя/накапливая рез-т для исходной точки. Привлекает простота реализации и ноль расхода памяти (ничего не храним). Также доказано что "сходится", если pdf грамотная и вот так долбить, долбить и долбить - получается рез-т высокого квачесnва.

Оба способа страдают всего лишь одним недостатком - расчет одного кадра длится не то что "часами", а "днями", а то и "неделями". Возможно научных работников это и устраивает (концепция доказана и все такое), но простого человека нет.

Хорошо, остановимся на втором методе. (Весьма логичный подход) Если ситуация такая, что кадр за кадром следует, и как я понимамю, перемещение объектолв происходить непрерывно (т.е. два соседних кадра "мало" отличаются друг от друга) то наивный подход к решению: а давайте не все точки трогать будем, а только N случайных, и для них будем подкручивать рёбра..
Проблема здесь только в том, что всё равно нужно запоминать их (рёбра).. И это не универсально..

Нет, неделю я бы не выдержал) Хотя бесконечности "под ковёр" приходится ножкой прятать)

"Междукадровая" оптимизация - это типовая доп задача, обычно тянет нехилые временные файлы. Применяется если только камера движется  ("camera fly"), любые др изменения- полный пересчет. В общем, это "не в тему"

Я не говорю о полном пересчёте.. Кадр за кадром берём случайные N вершин и для них только пересчитываем рёбра. Конечно (N << N_total)
Если всё более-менее непрерывно происходит, то такой фйинт может сработать..(Но это так, наивный взгляд на проблему..)

Но проблема остаётся. Всё равно нужно запоминапь рёбра на каждом кадре..

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

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

 Не важно..
Если Вы вот так вопрос ставите, то как Вы вообще подразумеваете, хотя бы в принципе, эту проблему решить? С либой ли левой, али нет..и Всё равно придётся на каждом кадре пересчитовать..

Придется, с этим никто не спорит. Но это должны быть "минуты", а не "часы/дни". Как решить - можно ответить одним словом "кеш" (Ване понравится, он любит играть в краткость :)).

Правда сделать это совсем непросто, хотя соображения повторно юзать точки и/или лучи очевидны/напрашиваются

Ох, как Вы вот так просто с недель на минуты перескочили.. Узкое место в Вашем подходе - это пересчёт рёбер? Тогда не понимаю как кэширование здесь сможет спасти.. Мне самому приходится числодробилками заниматься, и какого то универсального подхода точно не существует. Да, приходится идти на компромисы (скорость/точность) А то и вообще от теории отказываться

Ну это "хотелось бы" :)

Ну что просто так хранить тучу ребер в памяти не удастся - то ясно,  но это далеко не единственное и не самое страшное место.

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

Что здесь плохо? Сразу бросается в глаза что многие точки будут "достаточно близки" доуг к доугу, их можно слить, и вместо 200 лимонов с успехом обойтись напр 10. Это конечно "как фишка ляжет", можно придумать сцену где все "расходится". Но в принципе задача посвящена interior сценам, (по-простому комнатам).

Да, но как "сливать"? Нахрюкать все 200 и потом "проредить"? Это спорно. И здесь вылазит та самая головная боль - конечно считать надо всеми ядрами..

Далее. "из каждой по 200" - тоже не "абсолютная истина". Напр бросаем "из A в B" - но очень может быть что уже был луч "из B в A", (вернее в точку близкую к A).

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

Судя по постановке проблемы и хотелок товарища igorsа у этой проблемы нет не то что универсального, даже хотя бы адекватного алгоритма..  :( 

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

А почему (или откуда) он должен "быть"? Не все в этой жизни сводится к тасканию "ис каропки" и усердному заучиванию справочника  :)

Зачем же так передергивать? :)
m_ax имел ввиду, что можно любую постановку задачи довести до абсурда, не имеющего приемлемого решения. Вот как сейчас. А можно вообще в требовании поставить, чтобы кадры рендерились с часотой 60 кадров секунду и продолжить важно страдать на форуме. :)

А если тупо ребра лить в файл? Для передачи энергии от одной точки к другой - вроде устраивает, просто проход по файлу. Правда извлечь/получить ребра "по запросу" будет большая забота, ну пока неясно нужно ли это.

Ну и вроде "фокусируется" на том как грамотно создавать/объединять точки. Здесь наверно лучше сразу планировать "как задействовать все ядра"

Да, всё верно) Как с языка сняли)

БД какую-нибудь вместо файла?

Ну хорошо, вот маленькая подзадачка, чисто математика. Граф задуман для "перекачки энергии" между точками, псевдокод

C++ (Qt)
void Transfer( Point * p0, Point * p1 )
{
  auto e01 = p0->Energy() * p0->GetIn() * p1->GetOut();
  auto e10 = p1->Energy() * p1->GetIn() * p0->GetOut();
  p0->AddEnergy(e10);
  p1->AddEnergy(e01);
}
 

Для простоты геттеры просто возвращают константы. Да, но это одна итерация. Вопрос: могу ли я учесть все итерации (напр 5) за одно вычисление/проход ? Или нужно 5 проходов (что не так уж дешево)

Спасибо

Если математически (я не математик, так что помидорами не закидывать)
Есть граф. Грав это набор нодов (вершин) и рёбер между ними..
Каждому ребру мы ставим в соответствии два числа: первое, если проходим из точки A в B, и второе, если идём из B в A.
Ну и сам узел может иметь некую скалярную характеристику..
Вот в Вашей конкретной задачи, если её перевести на математический язык, что вообще значит "один проход", что должно оставаться инвариантом, как "один проход" выгодно отличается от другого?Ну ведь граф можно обойти туевой хучей способами..

Я тут на один канал подписан, там, в частности, есть проблема графа.. Чувак просто чудеса творит https://www.youtube.com/user/foo52ru (https://www.youtube.com/user/foo52ru)
Может кому интересно будет :)

Если "лить ребра в файл" (а иначе хана с памятью) то способ только один - перебирать ребро за ребром из файла полагая что все точки в RAM

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

Так, ну ладно, чтобы оживить обсуждение предлагаю пожевать выброс лучей. Вот есть точка, из нее надо выбросить заданное число N лучей чтобы оценить как точка освещена окружающей сценой. Откуда бросать ясно - сама точка. Но как или куда ? Т.е. как выбирать напр-я лучей и как их распределять ?

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

Ну вот опять пример непоставленной проблемы.. Что Вы ожидаете, от тех, кто не в этой свферы находится, какое решение?

Точек минимум на порядок больше, у каждой 200-1000 ребер

А что тут "разпоточивать", отот несчастный transfer выше? Время в основном будет тратиться на чтение

Ожидаю общей культуры и простейших познаний в рамках школьного курса (даже не старших классов)  :) Точка освещена тем больше чем напр-е на свет ближе к ее нормали. Макс освещенность получается если свет падает перпендикулярно поверхности. Миллионы людей переписывают код шейдера типа

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

Поэтому можно просто генерить случайные вектора напр-й, инвертируя их если dot < 0. Это корректное решение, вот правда неоптимальное: приносимый лучом рез-т придется множить на dot, лучей потребуется намного больше. Как это порешать ?

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

Да, но как посчитать размеры ячеек чтобы перейти к конкретному коду? На картинке есть подсказка

Размер ячейки - это её площадь на сфере? Если так, то как мы обычно считаем элемент площади? (см. аттач)

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

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

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

Очень просто (см. аттач)

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

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

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

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

Однако это совсем не так. Все не то что "просто", а "очень просто" если уловить идею решения. Подсказка: внизу нарисована плоская сетка, проекция на касательную плоскость. Площади проекций всех ячеек одинаковы (увы, никто не допер :'(). Оказывается проекции ячеек/лучей распределены равномерно внутри круга (сами ячейки конечно нет). Дальше "элементарщина", для нормали по Y

C++ (Qt)
QVector3D RandomDiffuseRay( void )
{
// случайная длина в плоскости XZ
  float R = RandomFloat();
 
// случайное напр-е - угол в плоскости XZ
  float angle = RandomFloat() * M_PI * 2;
 
  return QVector3D(cos(angle) * R, sqrt(1 - R * R), sin(angle) * R);
}

Найти в какую ячейку попал луч - тоже просто, надо только запастись табличкой "широт" для заданного разрешения, и потом по ней lower_bound(y). А "долгота" = atan2(z, x). Правда это для нормали (0, 1, 0), но до заданной уж как-то довернем, там "достаточно пройти дальше по ссылке" (як каже молодь  :))

Как видим, никакие интегралы не нужны. Зачем же их упорно рисуют?  :)

.. Возвёл очи к небу..

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 порядка больше. Хорошо бы парить "ребро за ребром" из файла, но нужно знать общий вес всех ребер для данной ячейки, а откуда его взять, др словами, как/где хранить?

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

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

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

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

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

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

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

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

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