Russian Qt Forum

Добрый день

Картинка 1: есть множество точек/частиц  ("фотонов") на поверхности 3D объектов.

C++ (Qt)
struct CPhoton {
 QVector3D p;   // позиция фотона
 RGB color;       // цвет
 QVector3D n;   // нормаль к поверхности в точке p
 QVector3D dir;  // направление (откуда пришел фотон)
};

Задача получить цвет в заданной точке на основании фотонов в заданном радиусе R. Просто складываем все color и делим на площадь круга. Как находить ближайших - дело техники, эти подробности опускаем. Все это выглядит уж слишком просто, но, как всегда, "devil is in details". Ну точно

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

Картинка 4: просто как это проявляется в конечном рез-те. Отмахнуться от этой проблемы не удается.

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

Я оцениваю эту ЗАДАЧУ как исключительно трудную, ну хз - может и неразрешимую. Поэтому если кто-то хоть ответит "в тему" - уже хорошо.

Спасибо

если я все правильно понял:
1) определить где круг пересекается со стенкой (координаты доступных стенок и круга известны)
2) если нет пересечений, то «все слишком уж просто», иначе...
3) если за стенкой, то темно, иначе...
4) выделяем точки внутри и считаем площадь куска

Если "есть стенки", то отбраковываем фотоны за стенкой (они "не из нашего муравейника", не включаем их в сумму). При этом необязательно "все темно" как на картинке 3, могут быть и неперекрытые фотоны. Др словами здесь одна песня, а за стенкой другая.

Во-вторых, если стенка есть, то надо из исходной площади вычесть ту что оказалась за стенкой - ведь мы исключили ее из рассмотрения. Довольно мерзкая подзадачка

Ну и самое главное - надо как-то получить стенки (пока не знаю как)

так проблема «как понять, что данный полигон — стенка»?
не совсем понимаю что тут мерзкого, если известна стенка (ну, будет известна) и круг :) стенка является хордой для круга, а площадь круга, ограниченного хордой, считается по школьной формуле. или сложность будет при ситуации как на рисунке 2б?

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

Так это на первом вычитании (одна стенка). Но ведь их может быть и больше. Хотя бы второе вычитание уже совсем не так просто. Да и хорда не всегда - одна или обе точки могут быть и внутри круга.

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

Вот сразу дополнительные условия к изначальной постановке задачи нарисовались :)

Найти все "фотоны" в сфере радиуса R это "приемлемо по скорости", а полигоны (хотя бы по их bounding boxes/speheres) уже нет? Странно:

На мой взгляд, умение фантазировать - важнейшее качество разработчика

У Вас есть хотя бы один вариант "не хотя бы"?  :) (у меня нет). А по bounding (напр ocTree) поймает слишком много кандидатов и быстро сдохнет по скорости на анализах сфера-полигон. Кстати и нахождение ближайших фотонов тоже не тянет по скорости и решается через "baking" - ну это за рамками данной темы, здесь мы полагаем они найдены.

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

Как по мне, очень схоже с идеей Ray Tracing.
Т.е. первое - луч имеет направление и цвет.
Второе - много препятствий в виде "стен" и прочих полигонов.
Третье - поверхность может быть неоднородной, судя по всему (не просто кружок).
Я бы смотрел в сторону движков для рейтрейсинга в реальном времени. Ибо задача неординарная и тут велосипедить, имхо, будет себе дороже.

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

Здесь я первый "попользоваться готовым" :) Ах как мне по душе "проверенные решения"! :) Только вот беда: найти их не удается. Подробнее об этом:

Техника фотонов довольно бородатая - лет 20 ей уже есть. Да, лучи выбрасываются raytracing'ом от источника света и всяко пере-отражаются в сцене, оседая на объектах в виде фотонов. Большое число публикаций (я просмотрел неск сотен) в основном перепевают автора идеи (Дженсена). Проблема темных стен/углов - неизменный спутник фотонов. Но вот говорить о ней почему-то не любят. Только очень немногие статьи (хватит пальцев одной руки) упоминают/рассматривают как с этим бороться. И то, обычно мутно, типа "ну вот тут надо применить корректирующий хвактор". А где/как его посчитать - молчок. Да, есть и реальные предложения, но они спорны, бросается в глаза что нет какого-то стандартного (каноничнского, хорошо известного) решения. О нем бы постоянно писали/перепечатывали - но этого нет. 3D пакеты как-то убирают этот дефект (с меньшим или большим успехом) - но вот делиться деталями реализации никто не спешит  :)

Так, сходу не вышло. Гугление тоже ничего реального не дает. Что бум делать? Или Вы в такой ситуации никогда не оказываетесь? Странно если так, я - частенько  :)

Ладно, попробуем переформулировать/упростить задачу. Считаем что запросная точка принадлежит какому-то полигону (хотя в общем случае это не всегда так). Также считаем что полигоны объединены в группы/модели которые есть нормальные/цивильные поверхности. В принципе проблемы те же самые, см аттач. В круге части поверхности может просто не быть. Задача та же самая - скорректировать площадь и отбраковать фотоны за пределами поверхности (это "нашей" поверхности там нет, а другие могут быть).  Разница - мы знаем "открытый край" т.е. где наша поверхность закончилась

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

Вы не пробовали задавать вопросы по 3д графике на форуме, связанных с 3д графикой?
Я в жизни работал с ней один раз - в универе.
Все эти "полигоны, вертексы, трассировка" для меня - пустой звук.
Как для вас какой-нибудь хадуп или hbase.
Более того, даже Qt я не использую.
Не очень понятно, от кого вы ждете помощи, если тут с графикой работает полтора человека и один из них - вы.

Интересно, а кто остальные половиначеловека?  ;D

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

Ну я за 0.05 сойду :)

"Ждут помощи" студенты что хотят проскочить на халяву с лабой - ни или совсем уж глупые люди :) Когда гуглюсь и встречаю ссылку на форум - я ее всегда пропускаю, хоть с виду она 100% подходит. Будет "много базара", но не ответ/решение. Мои темы по существу пинг - а вдруг есть люди которые этим/подобным занимались, а главное - хотят этим заниматься.   

Разумеется, но там успехи ничуть не лучше :) Либо громадная масса нерадивых студентов ("ты, дай списать") , либо железячников с упором на OpenGL о котором здесь речь не идет. Напр хваленый gamedev страдает именно этим. А здесь Qt играет роль фильтра, по уровню профессионализма данный форум хорош.

Возможно лучший способ привить человеку отвращение к предмету - это заставить его изучать. Напр после "Пушкина в школе" .. :'(  А ведь это действительно гениальный поэт

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

Забавно, спасибо, возможно я пересмотрю отношение к вашим темам:)

Совсем не понял Ваш острожный намек  :)

Непонятно почему никто не предложил поанализировать "расклад" фотонов? Вот неск "паттернов" (аттач). Есть напр такой метод (встречал неск перепечаток)

- находим все фотоны в радиусе R и сортируем их по расстоянию от центра (целевой точки)
- добавляя фотон за фотоном получаем ф-цию F(R). Напр для радиуса 1 имеем такую плотность, для R = 2 другую и.т.д.
- отлавливаем значение R когда ф-ция начинает "монотонно убывать/возрастать".  По-простому это как бы мы "зацепили" чужой свет/тень. Все, возвращаем значение плотности для пойманного R

Что Вы об этом думаете?

Из условий задачи не ясно:
- надо посчитать освещение ТОЛЬКО в видимой части круга или же на ВСЕХ видимых объектах, включая стены?
- предполагается ли, что фотоны лежат "где угодно" в пространстве (не только на круге), а еще и "за стенами"?

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

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

[OFF]Народная примета: за толковыми (как эти) вопросами обычно ничего не следует  :)[/OFF]

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

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

С увеличением R, рано или поздно функция конечно будет сглаживаться всё больше и больше, если мы говорим о плотности F(R) = N/S, (S = pi R^2 - площадь). Чем больше R - тем более сильное усреднение мы получаем - более размазанное и сглаженное описание.  
Как по интегральной, усреднённой величине мы делаем вывод о том, что мы там чего то зацепили?

    

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

Ну это смотря какая цель преследуется спрашивающим :)

Я бы, скорее всего, начал решать задачу с определения видимых полигонов. Либо же видимых пикселей, с соответствующими им 3д-координатами (не знаю, как у Вас z-буфер организован и можно ли в него поместить для каждой видимой точки ее разположение в пространстве).
После этого отбросил бы те фотоны, которые заведомо не видны.
А дальше можно попытаться уже "освещать" полигоны исходя из оставшихся видимых точек. Как первый вариант, тупо смотрим, попали ли в конкретный полигон те или иные точки, и считаем суммарную интенсивность. А дальше по результату.

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

Это реализуется очень просто, но чего мы добились? Вместо радиуса R теперь используем площадь полигона что гораздо менее удобно. Напр полигон может оказаться слишком мал или слишком велик, получим мусор/звон или "на душу населения". С др стороны ни одна проблема не решена, (у)течки все те же