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

[EngineEnergy]

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

Задача. Имеем миллион лучей и миллион сфер в трехмерном пространстве(сфера задана декартовыми координатами), расположенных хаотично. Требуется найти пересечение каждого конкретного луча со сферой.

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

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

[longstreet]

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

касательно вопроса мгновенного вывода фотореалистичного изображения

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

Требуется найти пересечение каждого конкретного луча со сферой.

Это какие-то разные вещи, всё-таки.

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

расположенных хаотично

Конкретно как? Просто неизвестно их расположение, или оно как-то таки генерируется?

-- 16.11.2014, 22:13 --

Так же поясните: что Вы понимаете под пересечением?

[EngineEnergy]

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

Хаотично - значит со случайными координатами (x, y и z) в пространстве. Представьте что сферы - это молекулы воздуха, на которые мы направили лазерный луч. Требуется узнать с какими "молекулами" в данный момент времени пересекается лазерный луч.

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

[longstreet]

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

Выше я не упомянул что имею в виду технику "трассировки лучей".

Зря я тогда говорить начал. Ничего не знаю на эту тему.

(Оффтоп)

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

Хаотично - значит со случайными координатами (x, y и z) в пространстве.

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

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

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

Мне непонятно: почему Вы в формулировке именно трёхмерные сферы упоминаете? Что ли, лучи направляются под произвольными углами?

[arseniiv]

EngineEnergy
Ну найдёте вы пересечения (и даже новый луч) — а дальше что? Не факт, что отражённый луч не попадёт в какую-нибудь другую сферу.

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

Графика - это та же математика.

Знатная путаница понятий. Если что-то использует математику, это не значит, что это — математика.

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

На практике лучей и сфер может быть в разы больше.

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

[longstreet]

arseniiv в сообщении #932077 писал(а):

Не факт, что отражённый луч не попадёт в какую-нибудь другую сферу.

Про отражения ничего сказано не было. А вообще интересно откуда задача.

[EngineEnergy]

arseniiv писал(а):

Ну найдёте вы пересечения (и даже новый луч) — а дальше что? Не факт, что отражённый луч не попадёт в какую-нибудь другую сферу.

Верно. Но это можно пока проигнорировать.

arseniiv писал(а):

Знатная путаница понятий. Если что-то использует математику, это не значит, что это — математика.

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

arseniiv писал(а):

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

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

[arseniiv]

longstreet в сообщении #932078 писал(а):

Про отражения ничего сказано не было.

Меня смутило вот это:

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

фотореалистичного изображения

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

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

Почему не выйдет? Допустим, сферы распределены внутри какого-то куба «хорошо». Разобъём его на $N^3 < S$ кубиков со в среднем $S/N^3$ сферами в каждом, определим каждую сферу в свой(и) кубик(и). Потом для каждого луча найдём кубики, в которые он попадает. Это, если не ошибаюсь, можно сделать за $O(N)$. Кубиков получится тоже $O(N)$. Теперь проверяем $O(N\cdot S/N^3)$ раз проверяем пересечения со сферами в кубиках. Итак, на один луч при проверке с каждой сферой $S$ проверок, а при этом подходе — $c S/N^2$, где [дальше поменял текст] $c$ вряд ли сравнится с правильно выбранным $N^2$. А если сравнится, то распределение сфер должно быть ужасным…

Что не так?

[Deggial]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Математика (общие вопросы)»

[Pavia]

Это называется квадва-деревья. Стандартная техника рендеринга, применяется во всех движках. Или почти во всех.

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

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

С чего вдруг не эффективной? Дайте оценку и сравните с алгоритмом из сообщения p932042

(Оффтоп)

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

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

[upgrade]

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

-- 17.11.2014, 11:05 --

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

Имеем миллион лучей и миллион сфер

может это заменить на "Имеем миллион источников света и миллион сфер..." ?

[EngineEnergy]

Pavia в сообщении #932239 писал(а):

Это называется квадва-деревья. Стандартная техника рендеринга, применяется во всех движках. Или почти во всех.

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

Pavia в сообщении #932239 писал(а):

С чего вдруг не эффективной? Дайте оценку и сравните с алгоритмом из сообщения .

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

upgrade в сообщении #932240 писал(а):

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

Проблема в её сложности, не в качестве самого решения, а его эффективности, когда дело идёт о работе с очень большим массивом данных.

upgrade в сообщении #932240 писал(а):

может это заменить на "Имеем миллион источников света и миллион сфер..." ?

Напомните, из чего состоит каждый источник света? Из лучей. Любой источник света испускает собой лучи. В задаче был дан источник света, испускающий один миллион лучей.

Для каждого луча можно определить свои варианты:

1. Луч не пересекается ни с одной из сфер.
2. Луч пересекается с какой-либо сферой.
3. Луч пересекается одновременно с двумя или большим количеством сфер.

[geezer]

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

Напомните, из чего состоит каждый источник света? Из лучей. Любой источник света испускает собой лучи.

Источник света, состоящий из лучей и испускающий лучи - это нонсенс.

[Pavia]

EngineEnergy
$N=1000000$ - число лучей
$M=1000000$ - число шаров.
1) Тривиальный алгоритм
$T_1(N\cdot M)$
2) Алгоритм на основе kd-дерева
$T_2(M\cdot Log_2(M))+T_1(N\cdot Log_2(M))$
3) Очевидно, что оптимальный случай - это перебрать всех лучей ровно 1 раз.
$T_1(N)$

Так вот 2) меньше 1) он более оптимален.
Если приравнять $T_1=T_2$ и подставить числа получим
40 шагов на луч, что больше дополнительного условия.
Думаю достаточно для следующего луча проверку по дереву начинать с узла предыдущего луча. Тогда в худшем случае нам понадобится 40 проверок на луч. А в лучшем 1.

-- Пн ноя 17, 2014 21:15:06 --

PS. Думаю что можно придумать алгоритм близкий к оптимальному. Дерево можно представить массивом. Тем самым свести поиск элемента можно вести по аналогии, как это делается при поиске K-статистики. А для неё известен алгоритм поиска O(N) в не отсортированном массиве.

[EngineEnergy]

Pavia в сообщении #932548 писал(а):

EngineEnergy
40 шагов на луч, что больше дополнительного условия.
Думаю достаточно для следующего луча проверку по дереву начинать с узла предыдущего луча. Тогда в худшем случае нам понадобится 40 проверок на луч. А в лучшем 1

Довольно интересно. Уже ближе к цели. Правда, 40 проверок это весьма не мало, если помножить на миллион. В хаотичной сцене худший сценарий будет часто преобладать. Идеалом является осуществление всего одной проверки на каждый луч вне зависимости от роста числа сфер в пространстве. Такой подход практически малоосуществим.

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

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