Russian Qt Forum
Ноябрь 22, 2024, 00:34 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: 1 [2] 3   Вниз
  Печать  
Автор Тема: Большой граф  (Прочитано 14107 раз)
Old
Джедай : наставник для всех
*******
Online Online

Сообщений: 4350



Просмотр профиля
« Ответ #15 : Август 04, 2021, 10:56 »

А почему (или откуда) он должен "быть"? Не все в этой жизни сводится к тасканию "ис каропки" и усердному заучиванию справочника  Улыбающийся
Зачем же так передергивать? Улыбающийся
m_ax имел ввиду, что можно любую постановку задачи довести до абсурда, не имеющего приемлемого решения. Вот как сейчас. А можно вообще в требовании поставить, чтобы кадры рендерились с часотой 60 кадров секунду и продолжить важно страдать на форуме. Улыбающийся
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #16 : Август 04, 2021, 12:08 »

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

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

Сообщений: 2095



Просмотр профиля
« Ответ #17 : Август 05, 2021, 15:50 »

Цитировать
m_ax имел ввиду, что можно любую постановку задачи довести до абсурда, не имеющего приемлемого решения.
Да, всё верно) Как с языка сняли)

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

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #18 : Август 06, 2021, 10:01 »

Ну хорошо, вот маленькая подзадачка, чисто математика. Граф задуман для "перекачки энергии" между точками, псевдокод
Код
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
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2095



Просмотр профиля
« Ответ #19 : Август 08, 2021, 10:52 »

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

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2095



Просмотр профиля
« Ответ #20 : Август 08, 2021, 11:03 »

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

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #21 : Август 08, 2021, 15:03 »

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

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

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

Сообщений: 2095



Просмотр профиля
« Ответ #22 : Август 08, 2021, 18:04 »

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

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

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #23 : Август 09, 2021, 15:58 »

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

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

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

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

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

Сообщений: 11445


Просмотр профиля
« Ответ #24 : Август 13, 2021, 07:22 »

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

Да, но как посчитать размеры ячеек чтобы перейти к конкретному коду? На картинке есть подсказка
Записан
m_ax
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2095



Просмотр профиля
« Ответ #25 : Август 14, 2021, 11:34 »

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

Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #26 : Август 14, 2021, 12:27 »

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

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

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

Сообщений: 2095



Просмотр профиля
« Ответ #27 : Август 14, 2021, 13:28 »

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

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

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #28 : Август 14, 2021, 15:38 »

И в чём проблема задать компоненты луча, чтобы он попадал в заданную точку на поверхности сферы?
Точка на поверхности единичной сферы с центром (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
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2095



Просмотр профиля
« Ответ #29 : Август 14, 2021, 16:37 »

Цитировать
Как видим, никакие интегралы не нужны. Зачем же их упорно рисуют?  Улыбающийся

.. Возвёл очи к небу..
Записан

Над водой луна двурога. Сяду выпью за Ван Гога. Хорошо, что кот не пьет, Он и так меня поймет..

Arch Linux Plasma 5
Страниц: 1 [2] 3   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.092 секунд. Запросов: 22.