Сверхбыстрый рендеринг. Что скажет математика?

[Pavia]

EngineEnergy в сообщении #932644 писал(а):

Поэтому чтобы уложиться в заданные выше 30 или меньшее количество шагов - стоит подумать об отсечение "неправильных" сфер ровно в два раза на каждом последующем шаге.
Привести алгоритм к: 2^(количество проверок) = (количество сфер).

Совместите построение дерева с проверкой будет менее 20 шагов.

EngineEnergy в сообщении #932644 писал(а):

В хаотичной сцене худший сценарий будет часто преобладать.

С чего бы вдруг?

[EngineEnergy]

Pavia писал(а):

С чего бы вдруг?

Упорядоченные данные всегда проще для просчета нежели случайные, хаотичные, которые не имеют под собой никаких закономерностей. Отсутствуют любые зацепки для построения эффективного алгоритма.

Вышеприведенную задачу возможно уложить ровно в 20 шагов если на каждом шаге мы будем отсеивать половину сфер, так как 2^20 = 1048576. Как раз наш миллион. С помощью бинарного разбиения пространства, 20 шагов - практически идеальный вариант, но, поскольку сферы распределены хаотично, реальный результат будет весьма печален.

Также, обратите внимание, что вычислив конечный результат первого луча не всегда возможно на основе данного вспомогательного результата вычислить результат второго луча. Об этом например говорят особенности строения GPU. Следовательно, расчет каждого конкретного луча будет производится в индивидуальном порядке.

[Deggial]

EngineEnergy в сообщении #933482 писал(а):

2^20 = 1048576

EngineEnergy, замечание за неоформление формул $\TeX$ом.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).

[electric_retard]

EngineEnergy
Ответ на ваш вопрос: "Ускоряющие структуры". Эта задача давно решена в компьютерной графике.
Гуглите:
packet traversal
bounding volume hiecracy — BVH
kd-tree
oct-tree
и т.п.
русскоязычный сайт, конкретно по интересующему вас вопросу раздел быстрая трассировка лучей.
Хорошая книга: PBRT Physically Based Raytracing
...
Почитал тред, выходит очередная сверхценная идея. Когда найдете решение не забудьте сравнить производительность с известными техниками. Заодно резюме закиньте в NVIDIA/AMD/Intel.

[EngineEnergy]

electric_retard писал(а):

Ответ на ваш вопрос: "Ускоряющие структуры". Эта задача давно решена в компьютерной графике.

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

electric_retard писал(а):

Почитал тред, выходит очередная сверхценная идея. Когда найдете решение не забудьте сравнить производительность с одной из известных техник.

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

[electric_retard]

EngineEnergy в сообщении #933606 писал(а):

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

Что за сцена, каким движком рендерится, какое железо? А главное откуда вы знаете за какое время все это дело должно рендерится? Это где-то написано?

EngineEnergy в сообщении #933606 писал(а):

Производительность всех перечисленных техник оставляет желать лучшего

По сравнению с чем?
Что за способ, который упускают из виду все воротилы визуализации и знает только автор темы?

[EngineEnergy]

electric_retard в сообщении #933608 писал(а):

Что за сцена, каким движком рендерится, какое железо? А главное откуда вы знаете за какое время все это дело должно рендерится? Это где-то написано?

Сцена... самая обыкновенная. Поставьте на стол ноутбук, чашку чая и настольную лампу. Чтобы отрендерить всё это в оригинальном качестве потребуются часы работы, в некоторых случаях - возможно, даже дни. Я не беру в расчет навороченные вычислительные агрегаты, суперкомпьютеры, которые сделают это почти мгновенно. Ибо не слишком практично.

EngineEnergy в сообщении #933606 писал(а):

По сравнению с чем?
Что за способ, который упускают из виду все воротилы визуализации и знает только автор темы?

По сравнению с чем? Да, хороший вопрос. Я предложил вариант двойного усечения геометрии на каждый шаг, но опасаюсь, что данная технология математически нереализуема.
Воротилы визуализации пользуются тем, что есть, иногда задействую мощности суперкомпьютеров. Большой бюджет вполне позволяет. Но, насколько Вы могли знать, современная трассировка лучей до сих пор неэффективна. Персональным компьютерам она часто бывает просто не по зубам в плане затратного времени.

[electric_retard]

EngineEnergy в сообщении #933632 писал(а):

в оригинальном качестве

У этого понятия есть определение? Что за оригинальное качество?

EngineEnergy в сообщении #933632 писал(а):

Я предложил вариант двойного усечения геометрии на каждый шаг

Похоже на дерево. А в каком сообщении? И чего опасаться, пишите программный код, сравнивайте с техниками, которые уже есть.
Ускорение построения сцены как правило осуществляется за счет погружения объектов сцены и источников излучения в деревья. Я пока не очень понял что у вас за альтернатива.

[Pavia]

EngineEnergy
Это научный форум посещенный метаматематики. Поэтому попрошу излагать свои мысли более научными понятиями.

EngineEnergy в сообщении #933632 писал(а):

По сравнению с чем? Да, хороший вопрос. Я предложил вариант двойного усечения геометрии на каждый шаг, но опасаюсь, что данная технология математически нереализуема.

Реализуем. Читайте "основы вычислительной геометрии". Во-вторых алгоритм я уже привел.

EngineEnergy в сообщении #933606 писал(а):

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

Классифицировать можно. Решение как решение.

EngineEnergy в сообщении #932644 писал(а):

Поэтому чтобы уложиться в заданные выше 30 или меньшее количество шагов - стоит подумать об отсечение "неправильных" сфер ровно в два раза на каждом последующем шаге.
Привести алгоритм к: 2^(количество проверок) = (количество сфер).

По такому принципу задача может быть относительно эффективно решена.

Как раз таки нет. Поэтому и используют вероятностные методы. Так как они эффективнее. Эффективность можно доказывать при помощи теоремы Байеса.
На самом деле их используют по другим причинам. При реализации они эффективнее работают, за счёт сокращения расходов по памяти.

EngineEnergy в сообщении #933632 писал(а):

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

Время рендеринга такой сцены в фото реалистичном качестве на GPU занимает 1-3 минуты и это было несколько лет назад.

electric_retard
Не видел работ что-бы приводилась сложность O(N).

[EngineEnergy]

electric_retard в сообщении #933700 писал(а):

У этого понятия есть определение? Что за оригинальное качество?

Оригинальное качество - это, может быть, реальная фотография сцены, взятая в качестве образца изображения - как ориентира. Задача - провести качественный рендеринг с минимум отличий конечного результата от взятого оригинала изображения.

electric_retard в сообщении #933700 писал(а):

Похоже на дерево. А в каком сообщении? И чего опасаться, пишите программный код, сравнивайте с техниками, которые уже есть.
Ускорение построения сцены как правило осуществляется за счет погружения объектов сцены и источников излучения в деревья. Я пока не очень понял что у вас за альтернатива.

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

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

Мы можем попытаться разбить куб на три части. Но и здесь не всё так гладко как хотелось бы. Луч сможет пересечь эти три области. Откинуть геометрию снова не получится. В результате потребуется разбивать кубическую область на более сложные и замысловатые фрагменты отичные от обычных параллепипедных форм. Что само по себе породит новые сложности.

-- 20.11.2014, 19:01 --

Pavia писал(а):

Время рендеринга такой сцены в фото реалистичном качестве на GPU занимает 1-3 минуты и это было несколько лет назад.

Не факт. Если изображение рендерится в Ultra HD качестве GPU здесь не сильно поможет в силу своего параллельного исполнения. Каждый луч придется обрабатывать индивидуально без связей с соседними лучами. 1-3 минуты Вы получите при выводе изображения в формате 640x480, да и то если геометрия будет не слишком детализирована. Не случаен ведь тот факт, что трассировка лучей очень редко используется в режиме реального времени, даже в компромиссном варианте.

[itmanager85]

EngineEnergy в сообщении #933632 писал(а):

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

трассировка лучшей в реальном времени (1024x768 60 fps) (10 переотражений) на gpgpu, моя программка .
http://www.youtube.com/watch?v=1MFSnMGA3BY

используется ускоряющая структура bvh.

можно скачать и запустить у себя на компе .

наслаждайтесь

[Dmitriy40]

itmanager85
Зеркальные поверхности не интересно, до фотореалистичности тут весьма далеко. Хотя и красиво.

EngineEnergy
С чего Вы взяли что миллиона (или миллиарда) лучей будет достаточно для фотореалистичности?! Это верно только при не слишком больших разрешениях картинки и только при зеркальных поверхностях! А таких поверхностей в реале достаточно мало. Любая другая же поверхность будет приводить к размножению лучей, очень быстрому - если с преломляющим и отражённым лучами всё просто, то с диффузным отражением ... По идее из каждой точки падения луча на диффузную поверхность надо выпускать десятки новых лучей во все стороны.
Да и миллиона сфер может быть слишком мало для детального описания поверхностей тел, тем более детализировано. Любая пылинка/крупинка может заметно изменить отражение лучей, даже издалека. А ведь в неё может и не попасть ни один из выпущенных лучей ... Тоже проблема.
И таких проблем - много.

[itmanager85]

Dmitriy40 в сообщении #1024906 писал(а):

до фотореалистичности тут весьма далеко.

речь шла про трассировку , а не фотореалистичность

[Dmitriy40]

itmanager85
Читайте внимательнее слова ТС:

EngineEnergy в сообщении #933632 писал(а):

Сцена... самая обыкновенная. Поставьте на стол ноутбук, чашку чая и настольную лампу. Чтобы отрендерить всё это в оригинальном качестве ...

EngineEnergy в сообщении #933881 писал(а):

Оригинальное качество - это, может быть, реальная фотография сцены, взятая в качестве образца изображения - как ориентира. Задача - провести качественный рендеринг с минимум отличий конечного результата от взятого оригинала изображения.

Отрендерить можно, даже и быстро. Но вот с желаемым качеством - нет.

[itmanager85]

Dmitriy40 в сообщении #1024962 писал(а):

Читайте внимательнее слова ТС:

в данном сообщении речь шла только про неэффективность трассировки, что и было мной опровергнуто . трассировка лучей и путей разные вещи вообще то . реально фотореалистичный рендеринг возможен только трассировкой путей .

EngineEnergy в сообщении #933632 писал(а):

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