Большой граф

[Igors]

Добрый день

Вот обдумываю (типа "с карандашом и блокнотом") предстоящую задачу, и, правду сказать, боюсь начинать По сути все сводится с графу, есть "вершины" и есть дуги/ребра. Физически вершины - точки на поверхности объектов 3D сцены. Каждая имеет по меньшей мере позицию (x, y. z) в пространстве, плюс нормаль, материал и др. Дуги образуются выбросом лучей из каждой точки, рабочее число дуг от 200 до 1000

Проблем море. Для начала такие квешнзы

1) Как эффективно хранить данные? Прямолинейное юзание контейнеров для дуг забивает всю память практически сразу, и дальше печальное лазание по свопам, 64-бита не спасают. Пока наметил хранить в RAM только точки, дуги как-то подкачивать (а как ?)

2) Как считать дуги? Не, ну выброс лучей конечно thread-safe, но дугу "из A в B" надо считать один раз, а не два. Т.е. просто так "выбрасываться" нехорошо

3) Как создавать новые точки? Начальные получаются из того "что видно на экране". Но лучи могут стрелять куда угодно, т.е. просто так дело никогда не кончится. И опять больное место multi-threading

[off]
Шансы на интересный/продуктивный разговор здесь невелики, но почему бы не попробовать ? Без нормальных тем становится скучно  
[/off]

Спасибо

[m_ax]

Как эффективно хранить данные? Прямолинейное юзание контейнеров для дуг забивает всю память практически сразу, и дальше печальное лазание по свопам, 64-бита не спасают. Пока наметил хранить в RAM только точки, дуги как-то подкачивать (а как ?)

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

[Igors]

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

Ну ладно, расскажу известные/популярные вещи.

Первый способ brute force, типа "а мне похер". Есть точка, выбросили из нее 200 лучей.  В замкнутой сцене (комната) получили 200 новых точек. Из них опять по 200. И.т.д Надо что-то делать, как-то гасить эту "цепную реакцию". Выбора тут особо нет, ну ограничить число рекурсий и уменьшать число лучей для второй и последующих. Последние GPU SDK с поддержкой raytrace вдохнули в этот совершенно тупой способ новую жизнь (ну это ненадолго)

Второй способ - популярный "path tracing". Выбросили луч, нашли новую точку. Из нее в случайном направдении с какой-то вероятностью (называется "pdf") опять выбросили луч. И просто повторяем этот процесс осредняя/накапливая рез-т для исходной точки. Привлекает простота реализации и ноль расхода памяти (ничего не храним). Также доказано что "сходится", если pdf грамотная и вот так долбить, долбить и долбить - получается рез-т высокого квачесnва.

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

[m_ax]

Хорошо, остановимся на втором методе. (Весьма логичный подход) Если ситуация такая, что кадр за кадром следует, и как я понимамю, перемещение объектолв происходить непрерывно (т.е. два соседних кадра "мало" отличаются друг от друга) то наивный подход к решению: а давайте не все точки трогать будем, а только N случайных, и для них будем подкручивать рёбра..
Проблема здесь только в том, что всё равно нужно запоминать их (рёбра).. И это не универсально..

[m_ax]

Оба способа страдают всего лишь одним недостатком - расчет одного кадра длится не то что "часами", а "днями", а то и "неделями". Возможно научных работников это и устраивает (концепция доказана и все такое), но простого человека нет.
Отправлено: Июль 29, 2021, 15:37

Нет, неделю я бы не выдержал) Хотя бесконечности "под ковёр" приходится ножкой прятать)

[Igors]

Хорошо, остановимся на втором методе. (Весьма логичный подход) Если ситуация такая, что кадр за кадром следует, и как я понимамю, перемещение объектолв происходить непрерывно (т.е. два соседних кадра "мало" отличаются друг от друга) то наивный подход к решению: а давайте не все точки трогать будем, а только N случайных, и для них будем подкручивать рёбра..

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

[m_ax]

Я не говорю о полном пересчёте.. Кадр за кадром берём случайные N вершин и для них только пересчитываем рёбра. Конечно (N << N_total)
Если всё более-менее непрерывно происходит, то такой фйинт может сработать..(Но это так, наивный взгляд на проблему..)

Но проблема остаётся. Всё равно нужно запоминапь рёбра на каждом кадре..

[Igors]

Но проблема остаётся. Всё равно нужно запоминапь рёбра на каждом кадре..

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

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

[m_ax]

 Не важно..

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

Если Вы вот так вопрос ставите, то как Вы вообще подразумеваете, хотя бы в принципе, эту проблему решить? С либой ли левой, али нет..и Всё равно придётся на каждом кадре пересчитовать..

[Igors]

Если Вы вот так вопрос ставите, то как Вы вообще подразумеваете, хотя бы в принципе, эту проблему решить? С либой ли левой, али нет..и Всё равно придётся на каждом кадре пересчитовать..

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

Правда сделать это совсем непросто, хотя соображения повторно юзать точки и/или лучи очевидны/напрашиваются

[m_ax]

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

[Igors]

Ох, как Вы вот так просто с недель на минуты перескочили..

Ну это "хотелось бы"

Узкое место в Вашем подходе - это пересчёт рёбер?

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

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

Что здесь плохо? Сразу бросается в глаза что многие точки будут "достаточно близки" доуг к доугу, их можно слить, и вместо 200 лимонов с успехом обойтись напр 10. Это конечно "как фишка ляжет", можно придумать сцену где все "расходится". Но в принципе задача посвящена interior сценам, (по-простому комнатам).

Да, но как "сливать"? Нахрюкать все 200 и потом "проредить"? Это спорно. И здесь вылазит та самая головная боль - конечно считать надо всеми ядрами..

Далее. "из каждой по 200" - тоже не "абсолютная истина". Напр бросаем "из A в B" - но очень может быть что уже был луч "из B в A", (вернее в точку близкую к A).

[qtkoder777]

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

Ну ладно, расскажу известные/популярные вещи.

Первый способ brute force, типа "а мне похер". Есть точка, выбросили из нее 200 лучей.  В замкнутой сцене (комната) получили 200 новых точек. Из них опять по 200. И.т.д Надо что-то делать, как-то гасить эту "цепную реакцию". Выбора тут особо нет, ну ограничить число рекурсий и уменьшать число лучей для второй и последующих. Последние GPU SDK с поддержкой raytrace вдохнули в этот совершенно тупой способ новую жизнь (ну это ненадолго)

Свет постепенно гаснет. Каждая следующая пачка лучей слабее предыдущей. Когда стало совсем темно - новую пачку не выпускаем.
Как иначе Вы будете рисовать два зеркала друг напротив друга?

[m_ax]

Судя по постановке проблемы и хотелок товарища igorsа у этой проблемы нет не то что универсального, даже хотя бы адекватного алгоритма..   

[Igors]

Свет постепенно гаснет. Каждая следующая пачка лучей слабее предыдущей. Когда стало совсем темно - новую пачку не выпускаем.
Как иначе Вы будете рисовать два зеркала друг напротив друга?

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

Судя по постановке проблемы и хотелок товарища igorsа у этой проблемы нет не то что универсального, даже хотя бы адекватного алгоритма..   

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