Russian Qt Forum

Добрый день

http://www.2shared.com/photo/dpvZCXAw/Fluid_elements.html (http://www.2shared.com/photo/dpvZCXAw/Fluid_elements.html) (излбражение слишком велико для аттача)

Есть коммерческое приложение специализирующееся на динамике жидкостей, воды. Оно экспортирует различные файлы которые используются для конечной визувлизации (моя задача). С самой водой (внизу на аттаче) разобрался быстро - это просто треугольники (3D модель). Но вот что делать с доп эффектами - хз. Строить полигоны глупо - терабайты данных, а качества нет. Все точки я имею (из импортируеиого файла, тоже объем приличный), ну и что с ними делать? Просто так нарисовать - зальет все одним цветом, нiчого цiкавого. Нужно их как-то освещать чтобы создать (богатую) игру тени/света/бликов. Но как это сделать?

Да, надоели мелкие темы и лекции для начинающих, хочется поговорить о чем-то большом и светлом, пусть и фантастичном  :)

Спасибо 

После изучения доки и SDK: приложение экспортирует файл "силового поля" (условное название), формат в псевдокоде

C++ (Qt)
struct CVolumeInfo {
 Point center;   // центр куба
 int numX, numY, numZ;  // число шагов по каждой из осей
 float sizeX, sizeY, sizeZ;  // размер по каждой из осей
 float * data;     // плотность ячеек (всего numX * numY * numZ)
};

Теперь для каждой точки внутри поля худо-бедно посчитать осещенность можно - протыкаем каждую ячейку вдоль направления точка-источник и уменьшаем свет по плотности ячейки. Всего не более чем max(numX, numY, numZ) шагов. Не то чтобы уж очень быстро, но приемлемо.

Однако растущий в кубе объем ужасен. Напр скромное поле 256х256х256 - уже 64 метра, а качество еще и конь не валялся. И это на кадр, а их сотни и больше. 

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

Это похоже на расчёт многомерных интегралов, а для таких вещей (ели размерность больше 3) ничего кроме Монте Карло не остаётся..
К тому же они хорошо параллелются.

Вообще не совсем понятна сама суть вопроса..
 

Не вижу никакой связи c MC (Monte-Carlo). Точки даны, решетка дана, направление на источник известно, зачем же мне делать какие-то случайные выборки? Др дело прямолинейная реализация ничего хорошего не обещает - слишком уж расходна (см. детали выше). Меня удивил предоставляемый файл - ведь дерево можно создать практически бесплатно (2 бита на точку). правда хз что с ним дальше делать. Поговорить с разработчиками можно, но не хочется так сразу лезть.

Просто вы писали:

С MC можно делать случайную выборку из этого ужасного объёма (с каким либо распределением) и дальше уже работать с ним.. 

Как это связано с темой - хз. Наверное просто случайно уцелевший осколок знаний в голове выжженной дустом :)

В общем приятного мало - придется читать диссеры и искать open-source, и неизвестно чем все закончится. Если же велосипедить, то есть такие соображения

- строим банальное двоичное дерево, разбивая куб на 2 куба по числу точек вдоль одной из осей - до тех пор пока в каждом кубе не будет по 1 точке

- теперь "хоть как-то" считать можем, по каждому кубу известна плотность d = число точек в кубе / его объем. Если научный работник забыл, то падение освещенности = 1 - e ^ (-kdt)

- конечно это загнется по скорости, т.к. число протыкаемых кубов огромно. Есть такая идейка - хранить значение "анизотропии" для каждого куба. Пример: проткнули "большой" куб, нужно ли протыкать 2 его child куба? Смотрим anisotropy большого, ага, оно достаточно мало, значит его плотность примерно однородна, чилдренов сканировать не надо. Но как это реализовать?

Смущает полное отсутствие знатоков, поучающих, что-то "настоятельно рекомендующих" и.т.п. Ну где же Вы - я очень хочу Вас послушать  :)

Вы уж простите, на знатока не претендую, но я вам "настоятельно рекомендую" научиться формулировать свои мысли.
Перечитайте ваши сообщения и подумайте, что должен из этого понять человек, который не знает о чем вы думали, когда набирали эти сообщение.
Потому, что я вообще ничего не понял, а самое главное что нужно обсудить.
Из первого сообщения: вода есть поверхность из треугольников - ок, дальше идет куб, который непонятно как относиться с этой поверхностью и вообще что содержит. Что можно посоветовать? Перед сном 10 раз осторожно посчитать все malloc'и, и написать на форуме еще одно сообщение в духе "как я крут, я считаю malloc".

 /* шёпотом */
Igors не любит, когда ему настоятельно рекомендуют  ;D
 

Зато по помпезным постам в свой адрес он спец. :)

А пока мне эта тема напоминает:

Исхитрись-ка мне добыть
То, чего не может быть.
Запиши себе названье,
Чтобы в спешке не забыть.

(c)

Для тех кто не понял объясняю еще раз

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

Если что-то еще непонятно - я поясню, а писять кипятком не надо  :)

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


Извини, поучал в другой теме - увлекся!  >:(

Это столько ошибок в слове октодерево? :)

Что подумалось, это octree + LOD. Думаю, это позволит не обсчитывать центр облака. Для расчета останется ближний к камере слой с заданной глубиной.

Каждый куб сохраняет "свою заполненность", например, в процентах. Тогда можно считать, что куб заполненный на 70% полностью не прозрачен и не пропускает дальше свет. Плотность накапливается, т.е. если луч прошел куб заполненный на 25%, а дальше находиться куб заполненный на 60%, то луч глубже не пойдет. Уровень детализации кубов (LOD) будет зависеть от расстояния до камеры: ближайшие кубы очень маленькие (может даже то отдельной точки), чем дальше - тем детализация уменьшается.

Мои (настоятельные  ;D) пять копеек ...

Если речь идет о "водяных" каплях, для реалистичной картины - освещения мало.

Вода умеет:

• Пропускать свет, уменьшая яркость
• Преломлять свет
• Отражать свет

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

Моя задача - нарисовать кадр, их много, но на каждом все с нуля. Конечно o real-time речь не идет, разумное время обсчета кадра (5 миллионов точек с хорошим качеством) - до 10 минут, больше нежелательно, где-то начиная с 30 минут - практически unusable, неприемлемо медленно.

Месите там какой-то перл, читаете лекции начинающим (а оно брыкается и слушать не хотят) - оно Вам надо? Вот задача дает широчайший простор для искусства программирования - оптимизируйте на здоровье!

Задача, по сути, просчет иррационального состояния кусочка пространства. Точность просчета которого практически не обозрима. Посему, мое очень скромное ИМХО - нужно сперва определить наиболее важные и значимые критерии реалистичности, и "бить" по ним, находя эффективные мат.методы. "В лоб" - явно не получится.

Аналогия - вычисление числа Пи. Много попыток, много формул ... Но некоторые интересно выстреливают. Закономерность "выстреливания" определить сложно, но как пища для размышления - годная для еды (http://ru.wikipedia.org/wiki/%D0%A1%D1%80%D0%B8%D0%BD%D0%B8%D0%B2%D0%B0%D1%81%D0%B0_%D0%A0%D0%B0%D0%BC%D0%B0%D0%BD%D1%83%D0%B4%D0%B6%D0%B0%D0%BD_%D0%90%D0%B9%D0%B5%D0%BD%D0%B3%D0%BE%D1%80).

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

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

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

Для имитации я бы попробовал бы такой подход (первое, что пришло в голову):

• Состояния макро-объектов оценивать не как точные численные значения, а как функторы от мико-объектов
• Численные значения постараться перевести в вероятности
• Для просчета состояний, соответственно, использовать fuzzy logic вместо булевой
• Естественно большую долю времени потратить на поиски закономерностей п.1, сделать джельтменский набор

Понимаю, сумбурно, но так рисует воображение  :-\

Не предлагал OcTree т.к. здесь не вижу для него резонов

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

Кстати
0.25 + 0.6 = 0.85  // неверно
0.25 + 0.6 * 0.75 = 0.7  // правильно

Резоны те же: уменьшить количество данных для расчета/визуализации.

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

0.25 + 0.7 * 0.5 = 1 // так себе

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

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

Это никак не связано с 25 и 60% что Вы привели. Да и с арифметикой что-то напутали  :)

Ну хорошо, вот пока сосредоточились на трассировании кубов/дерева. А есть ли др мысли/подходы? Ну напр с наглой мордой строить буфер...

Причем здесь перспектива? Я сейчас говорю про отбрасывание или укрупнение далеких объектов - LOD.

Вот поэтому я и предлагаю накапливать "плотность", что позволит не анализировать данные по всей длине куба, а остановиться на заданной глубине.

Ничего я не напутал. Там для этого указано "Так себе".

Да вы как-то не сосредоточились...

Пока я хочу предложить не использовать vector.  :)

Накапливается "opacity", она же известная альфа

opacity = 1 - transparency
transparency = e ^ (-k * d * t)

где

t - длина отрезка внутри куба (пройденный объем)
d - плотность куба
k - задаваемая константа

Если мы "останавливаемся на заданной глубине" то значит облако поглотило бОльшую часть света. Случай возможный но не очень интересный - вряд ли пена так уж сильно поглощает. И даже если так, то сколько мы будем топать по лучу до приличной альфы? В общем, не вижу пресловутой оптимизации.

Что-то научный работник примолк, может перелистывает Ландау?  :)

Ну как же. Рендерить всю длину куба или первые несколько точек.
Предположим, что каждая капля поглощает 10% света. Тогда двигаясь по лучу мы можем остановиться на 10 капле, дальше смысла двигаться нет, свет уже и так полностью поглощен.

С вашей манерой общения это не удивительно. Поэтому в ваших темах так мало людей делятся своими мыслями. Так сказать, оставляют возможность блеснуть большому специалисту.

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

А на 10-й капле света останется еще много
alpha[0] = 0.1   // 10%
alpha[1] = 0.1 + 0.1 * (1 - 0.1) = 0.19
alpha[2] = 0.19 + 0.1 * (1 - 0.19) = 0.271
и.т.д.

Эта та же экспонента выраженная численно

Поэтому я и предлагаю использовать LOD. Ближние точки можно будет обрабатывать по отдельности (или небольшими кубами), а чем от камеры тем размеры куба можно увеличивать. Неоднородность заполнения не особо важна, куб имеет плотность (%) = количество точек в кубе от общего объема куба.

Если вы хотите считать все честно, тогда смиритесь со временем. Если вы хотите ускориться, то придется пойти на некоторые допущения/упрощения.
Количество точек для полного поглощения можно в дальнейшем подобрать экспериментально или вообще оставить это пользователю. Главное, что объем точек для обработки будет существенно снижен.

Ну вот юзер захотел сделать пену как легкое, почти полностью прозрачное облачко. Как-то его ограничить - ну не видно как, ничего плохого он не хотел :) Поэтому в каких-то случаях придется считать и все точки. Но для таких случаев я могу сильно загрубить расчет света - ведь вес каждой точки мал.

Не вижу зачем здесь прилагать усилия, ведь иерархия кубов - по сути LOD. Точка далеко - ну прекрасно, просчитали 2-3 уровня, и все. Однако см картинку первого поста - вряд ли удастся что-то значительно сэкономить, все "достаточно близко".

Вот примерчик попроще. Как видим, вариации освещенности водопада очень тонкие, вообще-то он белый/серый. Но как только эти вариации убрать и залить все "просто белым" - все впечатление пропадет

С помощью "плотности куба" можно полностью отбрасывать незаполненные кубы. Например, есть удаленные от капли, с помощью LOD мы решаем, что они находятся в кубе со стороной 32 точки. Плотность такого куба будем минимальной и мы смело сможем отбросить его и эти пару капель. А если дистанция то этих капель будет меньше, размер рассматриваемого куба тоже будет меньше и плотность его будет выше.
Так же при визуализации, эту плотность можно суммировать и останавливать дальнейших ход луча.
Представьте гребень волны, реально мы видим тонкий слой воды, не середину, не тем более заднюю часть гребня мы не видим. Зачем нам рисовать эти точки?

Вы бы отключили эти кубы и показали водопад без брызг. Что бы мы визуально это смогли посмотреть.
И еще такой вопрос, а вот для этой картинки сколько используется кубов со стороной 256 точек?

Теоретически экспонента никогда не станет равной нулю, поэтому отсекать по альфе придется. Часто делают примерно так

C++ (Qt)
float AdjustAlpha( float a, float t1 = 0.8f, float t2 = 0.9f )
{
 if (a <= t1) return a;
 if (a >= t2) return 1.0f;
 a = (a - t1) / (t2 - t1);
 return t1 + (3 * a * a - 2 * a * a * a) * (1 - t1);  // сглаживаем переход
}

Т.к. рендер выполняется "от ближних к дальним", то если мы установим alpha = 1, задние точки рендериться не будут. Возможен и др подход - вообще не рендерить точки как таковые, а работать непосредственно с лучами. Если интересно расскажу, но в общем это дело техники и к задаче прямого отношения не имеет.

Пока не вижу алгоритма/сценария. Есть точка и она находится в main cube. Куб имеет 2 чайлд куба, те своих чайлдов и.т.д. до упора. Известно направление луча на источник света. Ну и что мы должны делать? Кстати а как делить - по пр-ву или по числу точек? (мне кажется по числу лучше)

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

Почему два? Их будет 8. Куб разбивается по середине вертикальной и горизонтальной плоскостью, получаем 8 кубов в два раза меньше родительского.

С помощью октодерева и LOD отбрасываем невидимые данные + минимизируем удаленные, дальше рендерим оставшиеся точки лучом, но только контролируя плотность и если плотность становиться максимальной, то переходим к следующей точке.

А картинки откуда?

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

Я имею ввиду расчет освещенности одной/заданной точки. Ну спустились по дереву в чайлд куб где находится точка. Дальше что?

Да октодеревья очень затратны к памяти. Да и их целесообразность у меня стала вызывать сомнения, в связи с этим:
Если куб всегда будет полность попадать в фрустум камеры, то нет никакого смысла пытаться что-то отсечь.

Дальше стреляем лучом из каждой точки куба в камеру или объединяем несколько точек в одну, если они удалены.
От источника света идет луч до целевой точки-капли, если луч проходит другие точки, то его интенсивность снижается. А от капли луч идет прямо в камеру. Чем ниже интенсивность, тем более темная капля будет. Как-то так, я не специалист в этом и этим уже очень давно не занимался.

Сама трассировка - дело нехитрое, напр (псевдокод)

C++ (Qt)
// рекурсивная ф-ция, возвращает true если результат уже достигнут
bool Trace( 
    const Node * node,   
    const Point & minP,  // min угол куба  
    const Point & maxP,  // max угол куба  
    Point ray[2] )            // 2 точки луча в кубе 
{
 if (node->IsLeaf()) {    // у нода нет чилдренов
  ... // накапливаем альфу
  return false;  // или true если альфы хватает (вряд ли)
 }
 
 Node * child;
 Point minP2, maxP2, ray2[2];
 
 if (node->IntersChild0(&child, minP, maxP, &maxP2, ray, ray2))  // луч пересекается с первым чайлдом
  if (Trace(child, minP, maxP2, ray2)) return true;
 
 if (node->IntersChild1(&child, minP, maxP, &minP2, ray, ray2))  // луч пересекается со вторым
  if (Trace(child, minP2, maxP, ray2)) return true;
 
 return false;
}
 

Расписывние внутренностей IntersChild опускаем ввиду его длинности/нудности. Понятно что если куб "полностью заполнен", мы для него просто не создаем chilldren. Но если нет? "Спускаться до упора" явно дороговато. Построение дерева в наших руках, какие решения Вы предлагаете?

Я говорил про то, что если вся сцена (куб 256x256x256) попадает в фрустум камеры, то вообще нет никакого смысла в октодереве. Мы все равно с его помощью не сможем отсечь ни одной точки.
Если это так, то октодерево можно отложить. А еще лучше нарисуйте, как эти куб(ы) с пеной соотносятся с поверхностями воды или скалы. Они как бы лежат на этих поверхностях?

1) Само приложение делает просто "партиклы" (желтые) имеющие позицию, скорость, ID и.т.п.
2) Затем к ним лепятся хвосты (на основании вектора скорости) и возможно они размножаются. Это несложно
3) А вот в приложении их надо осветить (последняя картинка, цвет специально циан). Вот это самое сложное

Последняя картинка не влезла, прилагаю

Пока хромая/косая альфа, сильный алиас + куча др проблем.