За стенкой или нет?

[Igors]

Добрый день

Картинка 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: просто как это проявляется в конечном рез-те. Отмахнуться от этой проблемы не удается.

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

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

Спасибо

[kambala]

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

[Igors]

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

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

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

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

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

[kambala]

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

так проблема «как понять, что данный полигон — стенка»?

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

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

[Igors]

так проблема «как понять, что данный полигон — стенка»?

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

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

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

[ssoft]

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

[kamre]

Найти полигон(ы) пересекающие сферу радиуса R - ну простыми/стандартными средствами это неприемлемо по скорости.

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

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

Как находить ближайших - дело техники, эти подробности опускаем.

[Igors]

На ум пришли пока только фантазии).

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

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

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

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

[Racheengel]

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

[Igors]

Я бы смотрел в сторону движков для рейтрейсинга в реальном времени.

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

Ибо задача неординарная и тут велосипедить, имхо, будет себе дороже.

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

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

[Igors]

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

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

[m_ax]

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

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

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

[Авварон]

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

[m_ax]

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

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

[Авварон]

Ну я за 0.05 сойду