Большой граф

[Old]

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

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

[Igors]

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

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

[m_ax]

m_ax имел ввиду, что можно любую постановку задачи довести до абсурда, не имеющего приемлемого решения.

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

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

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

[Igors]

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

Код

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 проходов (что не так уж дешево)

Спасибо

[m_ax]

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

[m_ax]

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

[Igors]

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

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

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

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

[m_ax]

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

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

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

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

[Igors]

Если речь идёт о поряка ляма точек

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

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

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

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

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

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

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

[Igors]

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

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

[m_ax]

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

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

[Igors]

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

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

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

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

[m_ax]

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

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

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

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

[Igors]

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

Точка на поверхности единичной сферы с центром (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), но до заданной уж как-то довернем, там "достаточно пройти дальше по ссылке" (як каже молодь  )

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

[m_ax]

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

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